Statistics

pkg/statistics/ provides the cardinality and selectivity estimates the planner uses to choose plans. It implements histograms, count-min sketches, top-N sketches, and the cluster-wide refresh machinery that keeps them current.

Purpose

The package is split into two halves:

• Algorithms (top of the directory) — the data structures themselves: histograms, CMS sketches, FM sketches, top-N, sample reservoirs, scalar conversions, cardinality estimation formulas.
• Handle (pkg/statistics/handle/) — the runtime: persists stats to the mysql.stats_* system tables, refreshes them on schema/version change, runs ANALYZE jobs, and serves the rest of TiDB via a thread-safe handle.

Directory layout

pkg/statistics/
├── analyze.go            # ANALYZE job descriptors
├── analyze_jobs.go       # ANALYZE job tracking
├── builder.go            # Build a statistics table from samples
├── histogram.go          # Histogram type and ops (≈73 KB)
├── cmsketch.go           # Count-Min Sketch + TopN sketch
├── cmsketch_util.go
├── fmsketch.go           # Flajolet-Martin sketch (NDV estimation)
├── column.go, index.go, table.go  # Column / index / table stats
├── scalar.go             # Scalar conversions for histogram bounds
├── estimate.go           # Selectivity formulas
├── row_sampler.go        # Sampling executors used by analyze
├── sample.go             # Sample reservoir
├── handle/               # Runtime handle (see below)
├── asyncload/            # Async background loader
└── util/                 # Helpers

The handle (pkg/statistics/handle/) has many sub-packages: autoanalyze/, cache/, globalstats/, historical/, lockstats/, lock/, bootstrap/, storage/, usage/, internal/, etc. The entry type is handle.Handle.

Key abstractions

Type	File	Purpose
statistics.Table	pkg/statistics/table.go	All stats for a single physical table (columns, indexes).
statistics.Column / statistics.Index	column.go / index.go	Per-column and per-index stats.
statistics.Histogram	histogram.go	Equi-depth histogram with optional TopN frontload.
statistics.CMSketch	cmsketch.go	Count-Min Sketch for cardinality estimates.
statistics.FMSketch	fmsketch.go	NDV estimator.
statistics.TopN	cmsketch.go	Top-N values per histogram.
statistics.SampleCollector	sample.go	Reservoir sampler used by analyze.
handle.Handle	pkg/statistics/handle/handle.go	Public façade: stats lookups, updates, GC, autoanalyze coordination.
handle.StatsCache	pkg/statistics/handle/cache/	LRU-ish cache keyed by (physicalID, schemaVersion).
handle.AutoAnalyze	pkg/statistics/handle/autoanalyze/	Owner-only periodic auto-analyze.

How stats flow

graph TD
  analyze[ANALYZE TABLE statement] --> exec[pkg/executor/analyze*.go]
  exec --> sampler[row_sampler.go]
  sampler --> builder[builder.go]
  builder --> hist[Histogram + CMS + TopN + FM]
  hist --> store[Persist to mysql.stats_*]
  store --> handle[handle.Handle reload]
  handle --> planner[pkg/planner/cardinality estimates]
  planner --> plan[Optimizer choices]

Two paths populate stats:

1. Explicit ANALYZE TABLE: pkg/executor/analyze*.go runs the sampling executors (analyze_col_sampling.go, analyze_idx.go), feeds them into pkg/statistics/builder.go, and persists the result.
2. Auto-analyze: pkg/statistics/handle/autoanalyze/ runs on the elected owner. It scans mysql.stats_meta for tables exceeding tidb_auto_analyze_ratio modified-rows threshold, then schedules analyses (often via DXF for very large tables).

After persistence, the handle on every TiDB instance refreshes its in-memory cache. The planner queries stats via pkg/planner/cardinality/ which delegates to handle.Handle.

Histograms

histogram.go is the largest file. Highlights:

• Equi-depth histograms with bucket ranges, repeats, and lower/upper bounds encoded per type.
• Selectivity estimation for ranges: lookup using bucket boundaries plus TopN adjustment for hot values.
• "Bucket" extension to support index histograms over multi-column prefixes.

TopN

A TopN sketch records the most frequent values explicitly. It is critical for highly skewed columns (e.g., status flags) where a histogram alone underestimates frequency. cmsketch.go builds the TopN alongside the CM sketch during analyze.

Asynchronous loading

pkg/statistics/asyncload/ lets the planner request stats lazily. If a query touches a column whose stats aren't loaded, the planner kicks off an async load and falls back to default selectivity until it lands. The mechanism is gated by tidb_stats_load_sync_wait.

Persistence layout

Stats live in:

• mysql.stats_meta — counters, last-update timestamp.
• mysql.stats_histograms — per-column/index histograms.
• mysql.stats_buckets — histogram buckets.
• mysql.stats_top_n — TopN entries.
• mysql.stats_fm_sketch — FM sketches.
• mysql.stats_extended — multi-column stats and stats extensions.
• mysql.stats_table_locked — locked tables (LOCK STATS).

pkg/statistics/handle/storage/ is the IO layer for these tables.

DXF and distributed analyze

For very large tables, ANALYZE TABLE can run distributedly across multiple TiDB nodes via the DXF framework. The DXF side is in pkg/dxf/; the analyze hooks are in pkg/statistics/handle/autoanalyze/ and pkg/executor/analyze_col_sampling.go.

Locked stats

LOCK STATS and UNLOCK STATS (handled via pkg/executor/lockstats/) prevent auto-analyze from re-running on a table whose stats a user has manually pinned. The lock state lives in mysql.stats_table_locked and is consulted by the autoanalyze loop.

Historical stats

pkg/domain/historical_stats.go and pkg/statistics/handle/historical/ periodically snapshot mysql.stats_* so users can inspect or restore prior versions (tidb_enable_historical_stats). This powers TiDB's "stats time travel" feature.

Integration points

• Executor runs the analyze pipeline and writes stats back through the handle.
• Planner queries the handle via pkg/planner/cardinality/ and pkg/planner/core/stats.go.
• Domain owns the handle and runs auto-analyze.
• DXF (pkg/dxf/) carries distributed analyze tasks across TiDB nodes.
• Bootstrap initialises the mysql.stats_* tables (pkg/session/bootstrap.go).

Entry points for modification

• New histogram type / sketch → add to pkg/statistics/, register encoding in histogram.go, update persistence in handle/storage/, and bump the version field in mysql.stats_histograms if the layout changes.
• New selectivity formula → estimate.go plus pkg/planner/cardinality/.
• New auto-analyze trigger → pkg/statistics/handle/autoanalyze/.
• New stats system table → bootstrap (pkg/session/bootstrap.go and pkg/session/upgrade_def.go), persistence (pkg/statistics/handle/storage/), domain reload.

The validation matrix in AGENTS.md requires statistics work to be covered by targeted unit tests with edge cases plus, for behaviour that depends on real TiKV semantics, a realtikv test.