Package org.eclipse.rdf4j.sail.lmdb.estimate

@InternalUseOnly package org.eclipse.rdf4j.sail.lmdb.estimate
Snapshot-consistent, bounded cardinality estimation over the LMDB B+tree stored in data.mdb.

Call flow

TripleStore chooses a statement index and creates an inclusive outer-key range. Bound statement fields at the front of that index become the range prefix; bound fields after the first gap become a residual GroupMatcher. LmdbPageCardinalityEstimator pins the request to the meta page for the active LMDB read transaction, resolves the named database descriptor, and delegates to LmdbBtreeRangeCounter.

The range counter descends to both boundary keys. It counts the selected portions of the two boundary leaves exactly, represents the interior as complete sibling subtrees, and counts the whole range exactly when that needs no more than the configured exact-leaf budget. Larger interiors receive a fixed number of deterministic probes. Each probe follows one path through a subtree and is weighted by the inverse probability of choosing that leaf. For a residual matcher, the estimator separately estimates physical range mass and the matched fraction. The resulting RangeCountResult carries hard bounds and quality signals as well as the point estimate.

Important invariants

  • All pages, named-database descriptors, and cached headers used by one estimate come from the same pinned LMDB snapshot. Never reuse a page-number cache across transaction IDs or native-map remaps.
  • Public range bounds are inclusive. Internal slices use the Java convention [fromInclusive, toExclusive); keep the conversion in the seek phase so the rest of the algorithm has one boundary convention.
  • Boundary leaves are exact. Sampling applies only to complete interior subtrees, which prevents a weighted probe from representing records outside the requested range.
  • Sampling seeds depend on logical database identity, key bounds, flags, and sampler version—not LMDB page numbers. This keeps decisions stable when copy-on-write commits merely renumber otherwise equivalent pages.
  • In DUPSORT databases, cardinality means duplicate values, not outer keys. Direct values, embedded duplicate pages, and promoted duplicate sub-databases must all report logical multiplicity.
  • Every approximate result is clamped to proven lower and upper bounds. Corrupt metadata, unsupported layouts, and non-finite arithmetic fail with IOException; TripleStore then uses its RDF4J 5.3.2 cursor sampler rather than publishing an unsafe estimate.

Changing the estimator

Keep structural work bounded before tuning statistical formulas. A new exact case must prove that it cannot traverse more than the exact-leaf budget. A new sampling stream needs its own stream identifier so it is deterministic but independent of existing evidence. Changes to weighting must update effective-sample and variance accounting; changes to page decoding must cover ordinary LMDB pages, integer/reverse comparators, and every DUPSORT container form. Add synthetic range-counter tests for structural invariants and a native LMDB test for any assumption about the actual on-disk layout. Dataset-scale accuracy measurements belong in the opt-in Theme accuracy test, not ordinary CI.