Indexing Lance files without the Dataset API

Ryle · Aug 21, 2026

An append-only data engine I've been working on as a side project keeps its cold data in Lance files. I use the Lance file format but skip the Lance dataset layer entirely, so there's no manifest, no version log and no _indices/ directory. Every write produces one immutable part file, and every index for that part lives in small sidecar files sitting next to it, tied to the part by name and by hash. I'll go through why I did it this way, what the sidecars got me on a 7.67 million row test, what they cost in bytes, and a write-path mistake that undid a lot of the benefit once real data started flowing through.

Why not the Dataset API

Lance has good native indexes (B-tree, bitmap, inverted text, label-list, zone maps, vector), but they're attached to a Lance dataset rather than a single Lance file. A dataset is a directory with a manifest per version, transaction files, deletion vectors and an index directory the manifest points into.

My storage model is simpler and I wanted to keep it that way. The engine is append-only. A store() writes one Lance file through the low-level file writer and publishes it to content-addressed object storage. If I adopted the native indexes I'd also be adopting the manifest and its commit protocol, which turns "immutable parts in a content-addressed store" into "versioned dataset with a mutable head." That's a storage redesign, and I didn't want to do one just to get an index.

This choice does cost something. There's no global index, so a query that wants one row has to check some per-part structure for every candidate part, and the engine has to do its own pruning, row selection and rechecking. What I get back is that a part and its sidecars are a self-contained, immutable unit. You can copy, cache, verify or delete them without touching anything else.

What a sidecar is

Each part p.lance can have up to four companions:

• p.lance.idx: the full index for the part.
• p.lance.idxh: a slim prune header, fetched before the part is opened.
• p.lance.stats: column statistics.
• p.lance.vidx: an HNSW graph over an embedding column, only for datasets that opt in.

The index body is a Rust struct serialized with bincode and compressed with zstd. In front of it there's a fixed 64-byte header:

magic                  [u8; 8]   fixed 8-byte file magic
format_version         u16
reserved               [u8; 6]
schema_descriptor_hash [u8; 16]  blake3(column names + types)
source_part_hash       [u8; 16]  blake3(source part identity)
row_count              u64
payload_len            u64

With the header a reader can reject a sidecar that was built for a different column schema or a different part, sanity-check the row count, and catch a truncated write by comparing the declared payload length with the bytes it actually got. If a part only has an old headerless sidecar, it gets scanned, which is slow but correct.

The full index struct carries about twenty families. That includes bloom and cuckoo filters, HyperLogLog cardinality estimates, numeric min/max, an inverted index from value to a roaring bitmap of row offsets, zone maps over row groups, sorted-column flags, null bitmaps, and trigram and word-token text indexes. Nested List and Struct columns get flattened into dotted-path leaves and folded into the inverted index, so list membership queries end up with the same value-to-bitmap shape as Lance's label-list index.

Before any of that is built, columns go through one normalization function. Booleans, dates, timestamps and unsigned integers become Int64, Float16 and Float32 become Float64, and dictionary columns become their value type. The build and the query-time recheck both call the same function, so they agree on what a value is.

The read path

A filtered read has four steps. First the prune header decides whether a part can be skipped entirely. For the parts that survive, the full index turns the predicates into candidate row ranges. The engine then decodes only those rows from the Lance file, and finally a recheck evaluates the original predicates against the decoded rows and throws out false positives.

The recheck is what makes everything else safe. Bloom filters, zone maps and float buckets can all be coarse because the recheck is exact. The one rule every index has to follow is that it can only say "these rows might match" or "I can't help." It can never report zero matches when it doesn't actually know. Most of the correctness bugs I've found came from breaking that rule.

The vector sidecar has its own path, because nearest-neighbor search ranks rows instead of filtering them. Each part has an HNSW graph over unit-normalized vectors. A query overfetches from each part's graph, rescores with exact cosine, applies scalar filters through the same recheck, and merges the per-part top-k. The graphs are big, so they never get fetched during scalar pruning.

What it buys

The main measurement is a scale test that writes three parts, each sized to about 1 GiB of in-memory Arrow: 2,556,528 rows per part, 7,669,584 rows total, about 243 MiB per part on disk after compression. It runs each query twice against the same parts, once with the sidecars present and once with them moved aside, and asserts that the answers are identical and that the indexed run decodes strictly fewer rows. The metric I use is rows physically decoded from the Lance files, which is deterministic for fixed data. Wall-clock time on a shared machine is too noisy to be worth reporting.

These ratios are only as good as the baseline, and the baseline is a full scan of the same three parts. So they tell you how much less the engine reads. They don't tell you how much faster a query returns, and they aren't a comparison against Lance's own indexes. Most of the spread comes from selectivity. The UInt32 and Int64 probes match a handful of rows, while the low-cardinality string probe matches a fifth of the data, so 5× is about as good as it can get there. The timestamp range covers exactly one part, so it gets part pruning and nothing else.

The Int64 id column has 2.56 million distinct values per part, which is over the inverted index's cardinality cap, so the point lookup falls back to the zone map and reads one 1,024-row chunk. Floats only get min/max and zone-map narrowing, on purpose. The current code can't narrow IS NULL, so the speedup on the nullable column only applies to equality.

Testing it

The thing an index has to get right, more than being fast, is that it never changes which rows a query returns. The core test for that is a property test. It generates rows over small domains so predicates sometimes match nothing, some rows, or everything. It writes them through the real storage backend as several parts, runs a filter through the normal read path, and compares the result as a multiset against a brute-force oracle that applies the same parsed predicates to all the parts concatenated together. Any difference is a pruning bug. The change that added this test also fixed a numeric-only skip-scan that was reading more rows than it needed to.

The scale tests are the second layer. They're gated behind an environment flag and run as a batch job close to the storage, because 7.67 million rows is too much to pull down to a development machine. They assert exact part-prune sets and rows decoded per probe. The vector test asserts recall@k of at least 0.95 against brute-force cosine on 384-dimension synthetic embeddings.

Writing the typed speedup test is what turned up the worst bug so far. The recheck only handled Int64, Float64 and string arrays. A predicate on a timestamp, unsigned integer, boolean or dictionary column just passed every candidate row through, which was only correct when the index happened to be exact. I fixed it by running the recheck against the same normalized view the index is built from.

A later round of testing found a group of bugs that all had the same shape, where an index said "absent" when it really meant "not indexed." The token index drops tokens shorter than two characters at build time, so a query for a one-character token found nothing and the part got skipped. A zone map with no entry for a column returned an empty range list, and the caller read that as "proved zero matches." Each of those cases now returns "can't narrow," and the part gets read and rechecked.

What it costs in bytes

Sidecars are only worth having if they stay small compared to the data, and a local transcript import showed me they weren't. A partial run wrote 1.13 GB: 449 MB of Lance data, 329 MB of .idx, 300 MB of .idxh and 54 MB of stats. So the sidecars were 1.52× the size of the data they indexed. For some parts the "slim" header was byte-for-byte the same size as the full index, 15,399,902 bytes each.

The causes turned out to be pretty mundane. Datasets with explicit index annotations were still getting every heuristic index family on top, and at 5,000 rows per part even unique IDs and hashes fell under the low-cardinality threshold and got full postings. The prune header only dropped the text indexes, so it was carrying the inverted index and everything else along with it. I made index selection explicit (annotated datasets get what they ask for, plus the mandatory ownership and time structures) and took the inverted index out of the header. There's now a byte-attribution helper that reports per-part Lance, .idx, .idxh, stats and vector bytes, and a regression test on a synthetic 10,000-row conversation corpus that asserts sidecars stay at or below 1.0× the Lance bytes and that the header is at most 10% of the full index. I still haven't done the encoding and part-size benchmarks.

The 250-row parts

Per-part indexes assume the parts are reasonably large. When every part only holds a few hundred rows, the fixed cost of opening each part and fetching its header ends up dominating.

The exporter that moves rows from the hot database into Lance turns one database page into one part. The page size was a single global setting, and it had been set to 250 rows because the fattest table, which stores raw model request and response payloads, averages about 130 KB per row and had run out of memory at 2,000. A conversation event table averaging about 2.2 KB per row inherited the same 250. An hour of its traffic, 2,515 rows, became 11 parts, and the dataset got up to 743 parts. One cold read logged 743 parts kept and zero opened before its 8-second deadline ran out. Zone maps didn't help either, since a read for one conversation spans every time-sorted part.

I fixed it with a per-dataset page size. The thin event table went to 2,000 rows per page, about 4.4 MB, which is well under the part byte bound and cuts new part creation by 8×. The payload table stayed at 250.

That only slows down the creation of new small parts. The existing ones still have to be compacted separately. What I took from it for this design is that part size needs to be treated as a real tuning parameter, because without a global index every extra part costs a header fetch on every read.

Where it stands

Things still missing: pruning on IS NULL, scale probes for Date, Float32 and boolean columns, and filtered HNSW traversal instead of overfetch-then-recheck. The vector index has only been tested on synthetic embeddings so far. I'd also like the structural counts from the scale test recorded per commit, so that if a change suddenly decodes millions of rows where it used to decode one chunk, it fails loudly. The basic shape should stay the same through all of that: immutable parts, indexes next to them, and an exact recheck behind every index.