Indexes, Statistics, and Cardinality Estimation

Indexes

An index is a B+ tree. You have seen the diagrams. Let's make sure we agree on what they mean.

Root page → intermediate pages → leaf pages. In a clustered index, leaf pages are the data pages — rows are stored in key order. The clustered index is not a separate structure; it is the table. In a non-clustered index, leaf pages contain index keys plus a row locator (the clustered key, or a physical row ID if no clustered index exists). To retrieve columns not in the non-clustered index, SQL Server must seek the clustered index again — that's the key lookup, the expensive extra hop that disappears when you cover the index with INCLUDE.

A covering index eliminates the key lookup entirely. TheINCLUDE clause on CREATE INDEX stores extra columns only at the leaf level — not in the B+ tree nodes above — so they don't affect sort order or index depth. When every column in the SELECT list,WHERE clause, and JOIN predicates is present in the index key or its INCLUDE list, SQL Server never touches the clustered index. A plan that was performing 2,000 key lookups — one per matched row — becomes a single seek with no follow-up I/O.

Seeking: traverse root → intermediate → leaf, one page read per level, O(log n). Scanning: follow the NextPage pointer chain across leaf pages sequentially, ignoring the upper levels entirely after the starting leaf is found.

The optimizer chooses between seek and scan based on estimated selectivity — how many rows does the predicate match? High selectivity → seek. Low selectivity → scan. The crossover is roughly where seeking would require more than a third of leaf-level pages, though the actual threshold depends on row size and the cost model constants.

Statistics and Cardinality Estimation

Selectivity estimates come from statistics. Statistics on a column are a histogram with up to 200 steps. Each step records five values: the upper boundary key (RANGE_HI_KEY), the rows with exactly that key value (EQ_ROWS), the rows in the range below the boundary (RANGE_ROWS), the distinct values in that range (DISTINCT_RANGE_ROWS), and the derived average rows per distinct value (AVG_RANGE_ROWS = RANGE_ROWS / DISTINCT_RANGE_ROWS). When the optimizer evaluates WHERE order_date = '2025-01-15', it looks up that date in the histogram and gets a row count estimate. That estimate drives every downstream decision: join order, join type, memory grant for hash operations, degree of parallelism.

When statistics are stale or misleading — the table was bulk-loaded, distribution shifted, or most rows cluster around values that fall between histogram steps — the estimate is wrong, and it propagates. A plan optimized for 100 rows that actually processes 10 million rows is one of SQL Server's most reliable methods for ruining your evening. Auto-update statistics helps; it triggers after roughly 20% of rows change (made adaptive for large tables in SQL Server 2016 — previously a 100-million-row table needed 20 million changes before anything updated). Don't rely on auto-update alone on tables with heavy writes or skewed distributions. ManualUPDATE STATISTICS WITH FULLSCAN after bulk loads is not optional maintenance. It is the price of having a cost-based optimizer.