Documentation
¶
Overview ¶
Package stats holds the best-effort, approximate planner statistics that back the Cypher optimiser's cardinality estimates for single-column predicates (design docs/statistics-design.md, tasks #2097 / #2098). It complements the EXACT population counts of the sibling count-store (graph/index/count): every selectivity is S = C/N with an exact denominator N (N(label) / E(relType)), so only the numerator — an in-range row count, or a number of distinct values — is ever approximate, and that numerator is what this package estimates.
Structures ¶
- HLL — a HyperLogLog++ distinct-value (NDV) estimator over 64-bit hashes, m = 2^12 = 4096 registers, 6-bit packed, with a sparse low-cardinality representation and a linear-counting small-range correction. Relative standard error 1.04/√m ≈ 1.625%.
- Histogram — an equi-depth histogram (B = 256 buckets) whose worst-case absolute selectivity error is the distribution-free 1/B ≈ 0.39% bound (Piatetsky-Shapiro & Connell, SIGMOD'84), with heavy (most-common) values isolated into singleton buckets so the bound survives skew (the MaxDiff mechanism, Poosala et al. SIGMOD'96).
- MCVList — the EXACT top-k (k = 32) most-common values, selected by a bounded min-heap over the rebuild scan. Exact, not Count-Min: a Count-Min sketch over-estimates, which is the unsafe direction for a no-regression safety gate.
- Stats — the per-(label, property) bundle of the three estimators plus a generation stamp (g0, N0) and the atomic staleness counters.
- Collector — the lock-free-read registry mapping (labelID, propID) to Stats, published by an atomic snapshot swap.
Maintenance model ¶
The estimators are built by a caller-driven full scan (never a background goroutine); a fresh snapshot is published atomically with Collector.Publish. Absence or staleness is harmless: a consumer that finds no fresh statistic simply falls back to the exact-count plan. The only write-path cost the design permits is an O(1) atomic per-(label, property) dirty-write counter (Δ), bumped through Collector.RecordWrite; everything else is rebuilt off the write path. HLL cannot delete (a register maximum only rises), so deletes over-estimate NDV (the unsafe direction) and are tracked separately (Stats.RecordDelete) to force a rebuild once they exceed a small tolerance of N.
Value-domain neutrality ¶
The package is generic over the value type T and never imports the Cypher value model: callers inject an orderability comparator (for Histogram) and a hash / equivalence pair (for MCVList and HLL). The Cypher layer instantiates everything with expr.Value, expr.Compare (the CIP2016-06-14 orderability comparator, which routes cross-type Integer/Float boundaries through the exact cmpInt64Float64), and expr.EquivalentHash / expr.Equivalent, keeping the openCypher value semantics — NaN exclusion, −0.0 == +0.0, one histogram per comparable value-domain — where they belong.
Concurrency contract ¶
A Collector is safe for concurrent use: reads (Collector.Lookup, Collector.TrackedLabelsForProp, Collector.Tracking) are lock-free (an atomic snapshot-pointer load over an immutable map), the per-Stats staleness counters are atomics, and Collector.Publish swaps a freshly-built snapshot in one atomic store. A HLL, Histogram, or MCVList is immutable once built and is safe for concurrent reads; building one (Insert / BuildEquiDepth / BuildTopK) is single-threaded and must complete before the value is published. The package spawns no goroutines.
Index ¶
- type Collector
- func (c *Collector[T]) Lookup(label, prop uint32) (*Stats[T], bool)
- func (c *Collector[T]) Publish(byKey map[Key]*Stats[T])
- func (c *Collector[T]) RecordDelete(label, prop uint32)
- func (c *Collector[T]) RecordWrite(label, prop uint32)
- func (c *Collector[T]) Size() int
- func (c *Collector[T]) TrackedLabelsForProp(prop uint32) []uint32
- func (c *Collector[T]) Tracking() bool
- type Domain
- type HLL
- type Histogram
- type Input
- type Key
- type MCVEntry
- type MCVList
- type Op
- type Stats
- func (s *Stats[T]) Buckets() int
- func (s *Stats[T]) Deletes() int64
- func (s *Stats[T]) Delta() int64
- func (s *Stats[T]) Generation() uint64
- func (s *Stats[T]) Histogram(d Domain) (*Histogram[T], bool)
- func (s *Stats[T]) LabelCount() int64
- func (s *Stats[T]) NeedsRebuildForDeletes(tol float64) bool
- func (s *Stats[T]) RecordDelete()
- func (s *Stats[T]) RecordWrite()
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Collector ¶
type Collector[T any] struct { // contains filtered or unexported fields }
Collector is the lock-free-read registry of per-(label, property) Stats. A rebuild publishes a fresh immutable snapshot with Collector.Publish; every read loads the current snapshot pointer atomically and consults its immutable map, so readers never block writers or each other. The per-Stats staleness counters are mutated in place through the atomic Record* methods.
Collector is safe for concurrent use. The zero value is not usable; construct one with NewCollector.
func NewCollector ¶
NewCollector returns an empty Collector holding no statistics. Every lookup on an empty Collector misses, so a consumer falls back to its exact-count plan until the first Collector.Publish.
func (*Collector[T]) Lookup ¶
Lookup returns the Stats for (label, prop) and true when present. It is a lock-free read of the current snapshot.
func (*Collector[T]) Publish ¶
Publish atomically replaces the Collector's contents with byKey. It derives the property→labels index the write path consults for staleness attribution, then swaps in the new immutable snapshot in one atomic store. Concurrent readers see either the whole previous snapshot or the whole new one, never a mix.
func (*Collector[T]) RecordDelete ¶
RecordDelete bumps the delete counter for (label, prop) when a bundle exists.
func (*Collector[T]) RecordWrite ¶
RecordWrite bumps Δ for (label, prop) when a bundle exists (a no-op otherwise).
func (*Collector[T]) TrackedLabelsForProp ¶
TrackedLabelsForProp returns the labels for which prop currently has statistics, so the write path can attribute a property write to each affected (label, property) bundle. The returned slice belongs to the immutable snapshot and must not be mutated. It is a lock-free read.
type Domain ¶
type Domain uint8
Domain is a caller-assigned tag identifying one comparable value-domain of a property (for example numeric versus string). A Stats holds at most one Histogram per domain, because a single histogram is only meaningful over values a single orderability comparator totally orders.
type HLL ¶
type HLL struct {
// contains filtered or unexported fields
}
HLL is a HyperLogLog++ distinct-value (cardinality) estimator over 64-bit hashes. It starts in a sparse, exact-per-register representation for small cardinalities and promotes to a 6-bit-packed dense array of m = 4096 registers once enough distinct registers are touched. Small cardinalities are estimated by linear counting (guarded against a zero empty-register count); larger ones by Ertl's table-free improved register-histogram estimator, whose exact-dyadic fold uses no math.Pow. See HLL.Estimate for the full rationale.
The zero value is not usable; construct one with NewHLL. An HLL is NOT safe for concurrent Insert; once fully built it is immutable and safe for concurrent HLL.Estimate reads. Insert is called only off the write path, during a statistics rebuild scan.
func (*HLL) Bytes ¶
Bytes reports the estimator's current register footprint in bytes: the packed dense array once promoted, or an approximation of the sparse map's live entries beforehand. It surfaces the memory the estimator holds for observability.
func (*HLL) Estimate ¶
Estimate returns the estimated number of distinct values folded into the receiver.
Small cardinalities (the sparse representation) use linear counting m·ln(m/V) over the empty-register count V, which is near-exact in that regime; the m·ln(m/V) term is guarded against V = 0 (design docs/statistics-design.md §5.1). Larger cardinalities (the dense representation) use Ertl's table-free improved register-histogram estimator, which realises the HLL++ small-and-mid- range bias correction the spec requires WITHOUT any precision-specific empirical bias tables to transcribe: the classic harmonic-mean-plus-linear-counting estimator is measurably outside the ±2·(1.04/√m) accuracy band in the 2m–5m transition region (the very reason HLL++ adds a bias correction), whereas Ertl's closed form holds within one standard error across the entire range and is verifiable against a single published algorithm.
The estimator's core is the register-value histogram folded as z = 0.5·(z + c_k) down the ranks — the numerically-stable, exact-dyadic evaluation of the harmonic-mean sum Σ_k c_k·2^{−k} (each ×0.5 is exact in IEEE-754, so no math.Pow ever appears, per §5.1) — bracketed by the σ (empty-register) and τ (saturated-register) tail corrections that make it accurate at both extremes.
func (*HLL) Insert ¶
Insert folds a 64-bit hash into the estimator. Callers pass any hash that is consistent with their equality relation (the Cypher layer uses expr.EquivalentHash so numerically-equal Integer/Float values, ±0.0, and all NaN bit-patterns fold to one register); Insert finalises it internally ([hllMix]) so the register distribution is uniform regardless. Insert only ever raises a register, so it is monotonic and idempotent for a repeated hash.
type Histogram ¶
type Histogram[T any] struct { // contains filtered or unexported fields }
Histogram is an equi-depth histogram over an ordered value domain T. Its worst-case absolute selectivity error is the distribution-free 1/B bound: no non-singleton bucket holds more than ⌈total/B⌉ rows, and heavy values are isolated into singleton buckets so a boundary on a spike is exact. It is immutable once built (BuildEquiDepth) and safe for concurrent reads; the orderability comparator is supplied per call so the structure never captures a closure and stays copy-cheap.
func BuildEquiDepth ¶
BuildEquiDepth builds an equi-depth histogram over the sorted distinct values and their parallel frequencies. values must already be sorted strictly ascending in the caller's orderability order (one entry per distinct value); freqs[i] is the row count of values[i]. The build walks that order directly and never re-compares, so no comparator is needed here — Histogram.Selectivity takes it at query time. b is the target bucket count B (the 1/B error bound). isHeavy reports whether a value must be isolated into its own singleton bucket (the caller passes the exact most-common-values set); any value whose own frequency reaches the per-bucket target is isolated as well, so the 1/B bound survives skew even for a spike the caller did not flag.
Callers must exclude out-of-domain and NaN rows before calling (a range predicate yields null on NaN, so such rows belong to no bucket); their count is tracked separately by the caller for the estimate's denominator arithmetic.
func (*Histogram[T]) BucketError ¶
BucketError returns the histogram's certified absolute selectivity error 1/B, the distribution-free per-boundary bound. It is independent of the data distribution.
func (*Histogram[T]) Buckets ¶
Buckets reports the number of buckets, for observability and testing.
func (*Histogram[T]) Selectivity ¶
Selectivity returns the estimated fraction of in-domain rows that satisfy value <op> bound, clamped to [0,1]. The estimate is exact for a boundary that lands on a singleton (heavy) value; for a boundary inside a non-singleton bucket it takes the bucket midpoint, so the absolute error is at most half the bucket depth and therefore within the 1/B bound the histogram guarantees. cmp is the orderability comparator over T (the Cypher layer supplies expr.Compare, whose cross-type Integer/Float path is the exact cmpInt64Float64).
func (*Histogram[T]) Total ¶
Total reports the number of in-domain rows the histogram summarises — the denominator of the fraction Histogram.Selectivity returns.
type Input ¶
type Input[T any] struct { NDV *HLL MCV *MCVList[T] Histograms map[Domain]*Histogram[T] Generation uint64 LabelCount int64 // N0: the exact live count of the label at build time Buckets int // the histogram target bucket count B }
Input carries the freshly-built estimators and the generation stamp for a single (label, property) into NewStats.
type MCVEntry ¶
MCVEntry is one most-common-value: the value, its equality-consistent hash (the same hash folded into the HLL), and its EXACT row count.
type MCVList ¶
type MCVList[T any] struct { // contains filtered or unexported fields }
MCVList is the exact top-k most-common values of a column, ordered by descending count (ties broken by ascending hash for determinism). It is immutable once built and safe for concurrent reads.
func BuildTopK ¶
BuildTopK selects the k highest-count entries from all with a bounded min-heap (O(n log k) time, O(k) space) and returns them ordered by descending count. It is exact — the entries carry true per-value counts from the rebuild scan, not a sketch estimate — because a safety gate needs the true count, and a Count-Min sketch's over-estimate bias is the wrong direction for such a gate. A k ≤ 0 yields an empty list.
func (*MCVList[T]) Entries ¶
Entries returns the retained values in descending-count order. The slice is the list's own backing array; callers must not mutate it.
func (*MCVList[T]) Lookup ¶
Lookup returns the exact count of value in the most-common-values list and true when it is present. It matches on the hash first (cheap) and confirms with eq (the caller's equivalence relation) so a hash collision between two distinct values never returns a wrong count. eq is the equivalence relation consistent with the hashes the entries carry (the Cypher layer passes expr.Equivalent).
type Op ¶
type Op uint8
Op is a range-predicate operator the histogram can estimate the selectivity of.
type Stats ¶
Stats is the per-(label, property) bundle of approximate estimators plus the staleness bookkeeping. It is built off the write path by a rebuild scan and published through a Collector; once published its estimators are immutable and its counters are mutated only through the atomic Record* methods.
A Stats is safe for concurrent use: the estimator fields are read-only after construction and the dirty / delete counters are atomics.
func NewStats ¶
NewStats assembles a Stats from freshly-built estimators. The dirty and delete counters start at zero.
func (*Stats[T]) Buckets ¶
Buckets returns the histogram bucket count B, the source of the 1/B error term.
func (*Stats[T]) Generation ¶
Generation returns the g0 stamp: the graph generation at build time.
func (*Stats[T]) LabelCount ¶
LabelCount returns the N0 stamp: the exact live label count at build time.
func (*Stats[T]) NeedsRebuildForDeletes ¶
NeedsRebuildForDeletes reports whether the delete count has exceeded the given tolerance fraction of the build-time label count, the threshold past which the HLL's inability to delete makes its NDV estimate untrustworthy (an over- estimate). A non-positive n0 forces a rebuild (nothing was summarised, or the stamp is degenerate).
func (*Stats[T]) RecordDelete ¶
func (s *Stats[T]) RecordDelete()
RecordDelete bumps the delete counter by one (a value removed or overwritten).
func (*Stats[T]) RecordWrite ¶
func (s *Stats[T]) RecordWrite()
RecordWrite bumps Δ by one — the single O(1) atomic the write path may pay.
Source Files