Disk Storage Decisions¶

This page records the design decisions that constrain Grafeo's tiered RAM-to-disk storage path. These decisions are baked into the v1 implementation and will not be revisited without a corresponding architectural review.

D1. Mmap with explicit eviction control¶

Decision. The v1 disk path uses memmap2::Mmap for read access, wrapped behind a PageFetcher trait so the mechanism can be swapped later without touching consumers.

Why. Pure mmap is the cheapest path to ship and works well up to roughly 100 GB on a single node. Above that, well-documented mmap pathologies (TLB shootdown under contention, unrecoverable SIGBUS, no I/O scheduling) become limiting. The PageFetcher indirection costs one virtual call per page touch, which is negligible compared to a page fault, and lets us swap in vmcache or an explicit pager later without touching consumers.

Alternatives considered.

Sources.

• Are You Sure You Want to Use MMAP in Your DBMS? (Crotty/Leis/Pavlo, CIDR 2022)
• Virtual-Memory Assisted Buffer Management (vmcache, TUM)
• LeanStore: A High-Performance Storage Engine for NVMe SSDs (VLDB 2024)

Implementation.

• Trait: crates/grafeo-storage/src/container/page_fetcher.rs, PageFetcher + AccessHint
• Initial impl: MmapPageFetcher wrapping Arc<MmapSection> in the same module

D2. Packed byte-stable disk format for the RDF Ring¶

Decision. Replace the bincode'd RdfRingSection with a packed v2 format: sorted-dictionary string table + bit-packed wavelet level bytes (fixed little-endian) + permutation arrays. Auxiliary rank/select samples are rebuilt on open per the existing SuccinctBitVector pattern.

Why. Bincode requires a full O(n) deserialize on load, which defeats the purpose of putting the Ring on disk. A packed layout gives O(1) load + paged reads through the OS page cache. Published evidence shows roughly 3x cold-cache query latency improvement at billion-triple scale.

Layout sketch. A short header carrying magic, endianness marker, triple count and dictionary size; then the sorted UTF-8 string table with a u64 offset index, the three wavelet trees (subjects, predicates, objects) as packed u64 bitvector words in little-endian, the two permutation arrays (spo→pos, spo→osp) as u32 arrays, and a CRC32 trailer. Endianness is locked to little-endian and validated at open.

Sources.

• qEndpoint: A Novel Triple Store Architecture (Willerval/Diefenbach/Bonifati, 2024)
• HDT Technical Specification
• Compressed and queryable self-indexes for RDF archives (Cerdeira-Pena et al., KAIS 2023)
• Faster Wavelet Tree Queries (arXiv 2023)

D3. Paged HNSW (not a DiskANN port) for the vector index¶

Decision. Extend the existing HNSW topology with a paged neighbor format (4 KiB blocks of neighbor lists, indexed by node-offset table). Combine with TurboQuant so quantized codes stay hot in RAM while full embeddings spill to mmap.

The two-phase search keeps the quantized codes plus the rotation matrix and norms in RAM (roughly 245 MB per million 384-dim vectors), and pages full-precision embeddings from disk only during rescoring of the top-K candidates.

Why. Paged HNSW reuses the existing search code and quantization integration, costs around six weeks, and serves indexes up to roughly 10M vectors with acceptable latency. DiskANN's single-hop diameter design would deliver O(1) page faults per query but requires a new index module, build pipeline, and optimizer cost model: roughly sixteen weeks of work without a workload that today demands it.

Future option. A DiskAnnIndex could be added as a parallel vector-index-disk feature if real workloads justify it. The optimizer already routes through VectorAccessor, so a second index type is pluggable.

Sources.

• TurboQuant: Asymmetric Vector Quantization (Google Research, ICLR 2026)
• DiskANN family (Microsoft Research) for the deferred design alternative

D4. Per-block zone maps in LPG columns are the keystone¶

Decision. Bump the LPG section format to v3: block-based columnar layout (4 KiB blocks default, configurable) with per-block min/max + null count + optional bloom filter. Per-label statistics stay as a higher-level summary.

Why. Per-label zone maps prune entire labels but cannot terminate a within-label scan early. Per-block maps unlock both block-skip and iterator early-termination. Without them, iterator bounds (D5) are dead code because Grafeo's columns are not value-sorted.

Tradeoff. Format-breaking change. The v2 reader stays in the codebase for one release for read-only access; v2 sections are upgraded to v3 on the next checkpoint.

Sources.

• Lance Zone Map Index
• DuckDB filter pushdown into zone maps (PR #14313)
• LSM Design Space Read Optimizations (Sarkar, ICDE 2023 tutorial)

Implementation (0.6.0). The LPG section's version 3 stores every column in chunks of at most 65,536 rows and 1 MiB instead of 4 KiB blocks, and each chunk of Int64, Float64, Bool or short String values carries its minimum and maximum (see Column Chunks). A chunk stores only the rows that have a value, so its presence bitmap and value count stand in for the null count; there is no bloom filter. An open decodes every chunk into memory, so nothing skips chunks on disk yet: that comes with the compact-core store (#432), whose cold chunks are these chunks. The 0.5.x reader stays in 0.6 only: a read-write open migrates a 0.5.x file to the new layout, and a read-only open reads it in place (see Files Written by 0.5.x).

D5. Property column sort order stays insertion-order¶

Decision. Property columns remain stored in insertion order. Iterator bounds rely on per-block zone-map skip, not on a sorted physical layout.

Why. A sort index would deliver true binary-search early termination but doubles write cost and adds a second physical layout. Block skip captures roughly 80 percent of the win at roughly 20 percent of the cost. This decision will be revisited only if benchmarks justify the added cost.

Sources.

• LSM Design Space Read Optimizations (Sarkar, ICDE 2023 tutorial) (informs the cost-of-sorting tradeoff)

Status¶