HLL approximate distinct counts are not currently reproducible across identical runs
OPEN
- Discovered
- 24 August 2026
- Dependency
- datasketches 5.2.0 (Python binding)
- Affected path
- columna-core sketch-witness merges — the distinct-count family (hll_count → hll_merge → hll_estimate)
- Affected surface
- Any approximate distinct count served through that path, including the buyers-by-month exhibit
- Reproduction
- Reproduced outside Columna, in a program using only DataSketches
- Upstream
- apache/datasketches-python#68 — API-parity request
- Resolution
- — open
A distinct count on this path is not counted exactly. It is estimated from a HyperLogLog sketch, and the estimate travels with its relative error, which is stated on the answer itself. That much is by design and is unchanged.
What we did not know until now is that the estimate is also sensitive to the order in which the underlying sketches are merged. Apache DataSketches offers two estimators for the same sketch. The HIP estimator is more accurate but order-dependent. The composite estimator is order-independent, at a modest cost in accuracy. Which one a caller gets is decided by the library: the default returns the best available, which is HIP where HIP is valid. The maintainers describe this as a deliberate trade-off between accuracy and order-independence, and the choice between the two estimators is exposed in the C++ and Java APIs.
The Python binding we use does not currently expose that choice. It offers the default estimator only, so a Python caller cannot select the order-independent one. Because the merge order of the underlying sketches is not fixed, the practical consequence is that two runs over identical logical input can return different distinct-count estimates.
Both estimates remain approximate results within their disclosed error bounds, and we have no finding that either is wrong. What is affected is reproducibility: an approximate distinct count served through this path should not currently be assumed to be byte-for-byte reproducible for identical logical input.
Columna has not changed its semantics to accommodate this. We have not imposed a canonical merge order to hold the order-dependent estimator steady, and we have not used the self-union trick that forces the library onto its order-independent estimator. Either would make our recording look more deterministic than the computation underneath it. We have asked upstream for the estimator controls that already exist in the other bindings, and until a supported way to make that choice explicitly is available in Python, the limitation is disclosed here rather than concealed in the code.