Summary and key takeaways
The reframe. Layout work gives data one arrangement. An index drops that limit by giving up on the data: it is a separate, derived, redundant structure that answers "where is it?" The price is write amplification, a consistency problem and an optimizer problem.
The crossover. An index beats a scan when k/N < s/r, the ratio of sequential to random access cost, counted in pages and affected by clustering and by the memory cliff. The "5% rule" is this ratio on old hardware.
The four dials of an index entry
| Dial | Choices | Key lesson |
|---|---|---|
| Key | column, tuple, expression | composite order follows lexicographic order; expression indexes are caches of unversioned functions |
| Reference | physical address, primary key | identity is stable, location is volatile; clustering is the only lever on pages touched |
| Rows | all, partial, sparse, zone map | skew is an asset when describable; zone maps need clustering |
| Payload | none, INCLUDE, covering | a covering index is a narrow sorted copy, and depends on visibility information |
The pruning criterion. An index is useful exactly when the qualifying entries form a small number of contiguous runs. Point: 1 run. Order: 1 run. Set membership: 1 run per term after inverting. Two dimensions: perimeter-many runs, and you pick what to break. High dimension: runs approach N and exactness is lost.
Key equations and rules
| Rule | Meaning |
|---|---|
| k/N < s/r | index beats scan |
| clustered ≈ k/f pages; unclustered ≈ min(k, N/f) | clustering gives up to an f-fold saving |
| fanout = page ÷ entry; height = log_fanout(N) | width is paid on every lookup |
| bitmap AND ≈ N/64 word operations | predicate combination independent of selectivity |
| runs ∝ perimeter of the query region | cost model for cell-based spatial indexes |
| nlist ≈ √(N · nprobe) | IVF balance point |
| 768 × 4 B = 3,072 B → 96 B (32×) | quantization crosses the memory cliff |
Patterns that repeat
- Coarse summaries matched to the read unit (sparse index, skip pointers, zone maps, IVF centroids).
- No in-place update (or relocation) ⇒ indirection + garbage collector (segments, tombstones, MVCC, row pointers).
- Independence is assumed and false, so estimates fail on correlated columns.
- Costs are conserved: every escape moves a cost.
- Derived state has a consistency boundary that can be placed, not removed.
- Memory cliffs make cost functions steps.
- Fewer indexes than you think: unused indexes are pure write tax.