Point reads from Lance files, and the approximate algebra that picks which files to read

Ryle · Jun 28, 2026

Most of the reads against my cold data are "give me these few rows, with all their columns", by a key or a content hash, out of a pile of immutable Lance files in object storage. There's no global index, so that read splits into two problems. Inside a file, I need to pull out a few rows without decoding everything around them. Across files, I need to decide which files are worth opening at all.

Lance turned out to be good at the first problem. Once that worked, nearly all the time went into the second. My answer to the second is an old idea I first used at Radius with Twitter's Algebird: small mergeable sketches per file, combined with a bit of algebra. The rule I ended up writing down for this storage layer was "approximate sets pick the files, exact per-file indexes find the rows."

The per-part sidecar files these indexes live in, and how much they cut rows decoded, have their own post. This one covers the read underneath them and the sketch math above them, including the places where the math didn't actually hold.

Why Lance for point reads

I've spent a lot of time with Parquet, and it's a very good scan format. Its layout is built for scans, though. A file is split into row groups, often hundreds of thousands to a million rows each. Each row group stores a column chunk per column, and each chunk is a run of compressed, encoded pages. To read one row you find its row group, then for every column you want you find the page holding that row, decompress it and decode it (plus the dictionary page if the column is dictionary-encoded). The optional page index lets a reader skip pages it doesn't need, but every page it does need gets decoded whole. If your rows are scattered across row groups, you pay that per row group.

My data has a shape that makes this hurt. Several tables keep small key columns (ids, hashes, timestamps) next to fat payload columns. One table stores raw model request and response payloads, averaging about 130 KB a row. The common query is "find the two rows for this conversation, return everything", and what I want is to touch the key column for the whole file but the payload column only for those two rows.

Lance's file format (I use the file format directly, with no dataset layer) has no row groups. Each column is paged on its own, and the reader takes a sorted list of row positions and schedules only the reads it needs for those rows. The 2.1 version of the format went further on this: according to Lance's docs, small values are packed into small chunks so a point read decodes one small chunk instead of a whole page, and large values are laid out so one value can be found and fetched without its neighbors. I haven't run a head-to-head take benchmark against Parquet on my own data, so take the comparison as format design rather than something I measured. What I can say is that my read path depends on it and it has held up.

The read is two phases on one open reader:

let reader = open_part(key).await?;                    // one open, one footer read

// Phase A: only the columns the predicate needs, over every row
// (or only the candidate rows a sidecar index handed us).
let small = reader.read(&["data_hash"], candidates).await?;
let positions: Vec<u32> = matching_rows(&small, &wanted); // ascending, no dups

// Phase B: every column, but only those rows, on the same reader.
let rows = reader.take(&positions, all_columns, byte_budget).await?;

A few details mattered more than I expected. The positions have to be strictly ascending and deduplicated, because the decoder asserts it. Phase B has a byte budget, because parts roll at about 1 GiB and a few selected payload rows can still be large. Phase B can also be projected, so a caller that only needs the key and two small columns never materializes the payload at all. And it really is a single open: what used to be three reader opens (metadata, projected scan, row fetch) became one.

The take was never the slow part

What changed my mind about where to spend effort was profiling the live read. At one point about a quarter of the reads for a busy conversation table were hitting their 8-second deadline (3,121 of 12,681 over 12 hours). Listing files and pruning were cheap by then. The read budget went roughly like this:

That's about 7.8 seconds of an 8-second deadline, and the random-access step was the cheapest of the three. All of the cost came from opening and filtering files that turned out to hold nothing. The log line for one cancelled read said it plainly: every part in the dataset kept by pruning (287 of 287), 83 of them opened, zero with a matching row.

The cause was that nothing could rule a file out for that predicate. The query filtered on a conversation id and on the owner. The conversation id only had an exact inverted index, which lives in the full sidecar and is stripped from the slim header the pruner reads. The owner had a bloom filter, but with a single user every file contains that user's rows, so it has no selectivity at all. The reads that did prune were the ones that also carried a time range, because per-part min/max survives into the slim header (one of those kept 17 parts instead of 287). So the fix wasn't anything about Lance. It was about the per-file sketches.

Approximate algebra

At Radius I scaled a marketing segmentation pipeline from single-machine Python to Scala on Spark, and Algebird did a lot of the heavy lifting. Its main idea is that many useful summaries are monoids (the same property I proved in Lean for the exact aggregates): there's an empty value and an associative plus, so you can summarize each partition independently and combine the results in any grouping. HyperLogLog for distinct counts, Bloom filters for membership, count-min for frequencies, min/max, top-k and quantile digests all fit. Algebird bills itself as abstract algebra for Scala, and the approximate structures were the part I used most, so in my head this has always been approximate algebra.

Immutable part files are a perfect fit for this. Each part is written once, so its sketches can be built once at write time and never touched again. A dataset is just the union of its parts, so a dataset-level summary is a fold over the per-part sketches. In the repo, the sketches live in a small sketch library with Bloom, cuckoo and xor filters, HyperLogLog, count-min, MinHash, t-digest and KLL. Every sketch has a canonical byte encoding (a fixed header, then little-endian fields, with no hash-map ordering or pointer values leaking in) so the same state always produces the same bytes and the same BLAKE3 hash.

The trait shape is about what you'd expect:

trait Sketch: Sized {
    /// Parameters that must match for a merge to mean anything:
    /// size, error rate, hash count, and the hash seed.
    type Params: PartialEq;
    fn params(&self) -> &Self::Params;
    fn empty(p: &Self::Params) -> Self;
    fn merge(&mut self, other: &Self) -> Result<(), Incompatible>;
}

The sketches end up doing three different jobs, and it took me a while to see that they're different.

Job 1: picking the files

For pruning, you don't actually need to merge anything. Membership in a union of parts is the OR of membership in each part, so the query probes every part's sketch and opens only the parts that might hold the value. A part's bloom filter can say "maybe" or "definitely not". A min/max range on the time column can say "outside my window". A missing or overflowed sketch has to say "can't tell", and the part gets read.

fn may_contain(part: &PartIndex, col: &str, v: &str) -> bool {
    match part.bloom(col) {
        Some(b) => b.probably_contains(v), // false means definitely absent
        None => true,                      // no sketch: can't rule it out
    }
}

A point lookup by content hash then has two steps. Bloom filters choose the candidate parts. Each candidate's exact hash → row postings give the row positions, or an empty set if the bloom was a false positive, and the two-phase read takes them. A lookup by full primary key goes the other way. The time part of the key is checked against each part's min/max, which normally leaves exactly one part. Inside that part the exact index finds the row, and the other key fields are checked on the materialized row so a hash collision can't return the wrong one. There's no global hash → location map anywhere, which matters to me because a global map would have to be rewritten every time a hash changed.

The fix for the slow conversation reads was a bloom filter on the conversation id column. It survives into the slim header the pruner reads, so a part that doesn't hold the conversation gets dropped without being opened. Existing parts only got it once their headers were rebuilt, which is a separate backfill job.

Job 2: deciding what to build

The second job happens at write time. Before building a part's indexes, the builder runs a HyperLogLog over each string column and uses the estimate to decide what that column gets. A column whose estimate is over half the row count gets no bloom or cuckoo filter by default, because unique ids and hashes make membership filters large and useless. The same check keeps n-gram and token text indexes off near-unique columns, and a composite index is only built for column pairs whose estimates multiply to 100,000 or less. Some decisions use an exact distinct count instead, since the builder has the values in memory anyway. Inverted postings, for example, stop at 100,000 distinct values.

The estimate also sizes the bloom filters, which turned out to be important. When I added the conversation id bloom through an explicit config, explicit mode didn't enroll that column for HLL, so the bloom was sized by row count. On a million-row part that's about a 1.2 MB filter, which pushed the slim header past its 2 MB cap and took the part out of the fast prune path the bloom was added for. Now asking for a bloom on a column also asks for its HLL.

Job 3: describing the whole dataset

The third job is the one Algebird is really about: fold every part's sketch into one dataset-level answer, like "about how many distinct users" or "the p99 latency". That's where my implementation fell short.

Where the algebra broke

t-digest and KLL merged fine. They store numeric centroids and levels, and no hashing is involved.

Bloom filters only OR together if they were built with the same size, the same number of hashes and the same hash keys. The Bloom library I use draws its SipHash keys from the OS random number generator by default. So two builds of the same part produced different bytes, and worse, a different set of absent values that happened to false-positive. Reindexing a part could start keeping a conversation id it used to skip, and tests over small blooms failed a few percent of the time. I pinned the seed, so a part's index is now a pure function of its rows, and that's also what makes a bitwise OR across parts valid.

HyperLogLog didn't merge at all. The HLL library I wrapped seeds each instance's hasher randomly, and merging two instances with different hasher state panics. My wrapper catches the panic and returns an error. On top of that, the library keeps its registers private, so my canonical encoding only stores the final estimate, and a decoded HLL can't be merged with anything. The cross-part merge handles this by summing the per-part estimates and marking the column as an upper bound, since a disjoint sum over-counts every value that appears in more than one part. The unit test for this used two parts with no overlapping values, where the sum happens to be right, so it never showed the problem. It's a milder case of a test that can't fail.

The accuracy also wasn't what the constructor said. Asking for 1% error gives 1,024 registers, whose standard error is about 3.25%, and with the random seeds CI saw around 14% error at 5,000 distinct values. The opt-in APPROX_COUNT_DISTINCT now reports a 25% bound in its result metadata, because that's the bound its own test actually holds.

Count-min merge was a placeholder. It checked that the parameters matched and returned Ok(()) without adding any counters. The merge code keeps the first part's sketch and flags the column instead of calling it.

Tiny blooms didn't hit their rate. Sized at its true item count, a one-value part got a 16-bit bitmap, and the library's double hashing falls apart at that size. I measured 494 of 2,000 absent values reported present, about 25% against a 1% target. A floor of 1,024 items, about 1.2 KB per column, put it back under 1%.

The common thread is that a sketch is only a monoid if everything that affects its bits is part of its type, and that very much includes the hash seed. Algebird gets this right: its HLL hashes with one fixed function, and its count-min monoid takes the seed as a parameter. Rust crates I picked up for single-process use mostly didn't, and wrapping them didn't fix that. If I started over, I'd write the HLL myself (my guess is it's around a hundred lines with a fixed hash and serialized registers) and test every merge with overlapping inputs.

Keeping approximation out of the answers

None of this is allowed to change a query's results, and the rule that keeps it that way is that approximation has two separate jobs that never mix.

Acceleration is always on and never changes a returned row. Sketches pick files and size indexes, and every surviving row goes through an exact recheck. A sketch can say "maybe" or "can't help", but it can never claim zero matches when it doesn't actually know.

Approximate answers are opt-in. APPROX_COUNT_DISTINCT, APPROX_PERCENTILE and APPROX_TOP_K exist, and they only run when the query names them. Each puts its error bound and the sketch it used into the output column's Arrow field metadata. COUNT DISTINCT and MEDIAN stay exact. The merged dataset summary from the per-part sketches is currently only logged, behind a flag that's off by default, until the HLL problem is fixed.

The same structure works with exact merges too. Keyword search used to download each candidate part's full sidecar to learn whether it held a word. Now each part writes a small term → rows table, and groups of parts get a segment table mapping each term to a bitmap of the parts that contain it. That's just the union of the per-part term sets, the same fold as before but with roaring bitmaps instead of sketches, so there's no error to reason about.

What I'd tell someone doing the same thing

• If your reads are "a few whole rows by key" over big immutable files, Lance's take path is worth a look. Read the narrow columns first, then take the wide ones by position on the same reader.
• Measure where the time goes before tuning the read itself. For me, random access was solved early, and the remaining problem was opening files that held nothing.
• Per-file membership sketches don't need to be merged to prune. Probe each one and OR the answers.
• Before you rely on a sketch's merge, check that the hash seed is fixed, that the serialized form keeps enough state to merge, and that merge actually does something. Test it with overlapping inputs, not disjoint ones.
• Use cheap sketches to decide which expensive indexes to build, and size filters by estimated distinct count instead of row count.

Still missing: a deterministic, register-serializing HLL, a real count-min merge, feeding merged cardinalities to the query planner, and a proper take benchmark against Parquet on the same rows.

Related posts

• Indexing Lance files without the Dataset API
• Proving dataflow operators coordination-free in Lean 4
• Agents write tests that can't fail
• Taking protobuf out of a 1,000-crate Rust monorepo