HyperLogLog
A mergeable estimate of how many distinct values a path holds.
Cardinality is what turns a list of paths into a recommendation. A path whose every document carries a different value is a key, not an index; a path with two values is a flag and a bitmap over it saves nothing. The useful band is in between, and finding it needs a distinct count over millions of values held in a few hundred bytes and mergeable across segments — which is what HyperLogLog is for.
Mergeability is the property the whole design rests on. The catalog's model of a store is the fold of its live segments' sketches, so a merge that depended on order — or that lost accuracy each time — would make the model depend on the compaction history rather than on the data. Register-wise maximum has neither problem: it is associative, commutative, idempotent, and exact in the sense that merging two sketches gives byte-for-byte what sketching the union would have.
Two representations, and which one is in use is a function of the data alone.
Sparse, up to SPARSE_LIMIT distinct 64-bit hashes kept verbatim. The estimate is then the count, exactly. Most paths in a real document live here — a status field, a country code, a boolean — and these are exactly the paths worth indexing, so the estimator is exact precisely where the recommendation is being made.
Dense, REGISTER_COUNT one-byte registers, once the sparse set would overflow.
A merge whose result would exceed the sparse limit produces a dense sketch, and a merge involving a dense sketch is dense. Both conditions depend only on the union, never on the order the union was built in, so two different fold orders produce identical bytes. The property test asserts that equality rather than an approximate one.
The precision is a format constant, not a knob. Registers written at one precision cannot be merged with registers written at another, and a knob whose values do not interoperate is a trap. It lives in SketchFormat with the rest of the permanent constants.
Mutable, and deliberately: accumulation calls add once per value on the flush and compaction path, and a copy per value would dwarf the sketch. Merging into a new sketch is mergedWith; merge mutates. Not thread-safe — one observation belongs to one segment writer.