Visual walkthrough — Composite indexes, covering indexes
Step 1 — A table is just an unsorted heap
WHAT. Imagine a small orders table. Each row has two columns we care about: a = customer_id and b = status_code (say 1 = open, 2 = paid). Rows land on disk in insertion order — no order at all. In database jargon this raw, unordered storage is called a heap.
WHY. Before we can appreciate an index, we must feel the pain it removes. Let (the number of rows in the table) stand for how big that pile is. To answer WHERE a = 5 on an unsorted heap, the database must look at every single one of those rows. That is a full table scan: cost grows linearly with , written — "the work scales like ".
PICTURE. The red arrows below show the scan touching every box, most of them useless (grey), just to find the two matching rows (green).
Step 2 — Sort by one column: the seek is born
WHAT. Now copy the values of column a into a separate structure and keep them sorted: 1, 2, 3, 5, 5, 7, 9. Next to each value we store a pointer — a little arrow back to the full row in the heap.
WHY. Sorted data unlocks binary search: to find a = 5, jump to the middle, ask "too big or too small?", throw away half, repeat. Each question halves what remains, so instead of steps you need about steps.
PICTURE. The green pointer arrows show the two a = 5 rows sitting next to each other in the sorted column — that contiguity is the whole trick.
Step 3 — Two columns, one order: lexicographic sorting
WHAT. A composite index on (a, b) sorts by a first, and within each equal a sorts by b. This is lexicographic (dictionary) order — exactly how words sort by first letter, then second letter.
WHY. A query often filters on both columns: WHERE a = 5 AND b = 2. With one combined sorted order, both conditions land you in one contiguous block, not two scattered sets you have to intersect.
PICTURE. Watch how b (yellow) restarts its little climb inside every new a-block (blue).
Step 4 — WHY the leftmost prefix works: a = 5 AND b = 2
WHAT. We seek a = 5 AND b = 2. Binary-search on a to reach the a = 5 block; because that block is itself sorted by b, binary-search again inside it for b = 2. Two fast seeks, no scan.
WHY. Knowing a first collapses the search to a small contiguous block; knowing b second refines within it. This is the leftmost-prefix rule: you may seek on a, or on (a, b), but the columns must be filled left to right with no gaps.
PICTURE. Two nested green brackets: the outer one seeks a = 5, the inner one seeks b = 2 inside it.
Step 5 — WHY WHERE b = 3 alone fails (the degenerate case)
WHAT. Now ask for b = 3 with no constraint on a. The index on (a, b) cannot seek this. It must scan the whole index.
WHY. Because b was only a tie-breaker (Step 3). Across different a-blocks, b = 3 appears again and again — scattered, never contiguous. There is no single block to jump to.
PICTURE. The red b = 3 targets are sprinkled through every blue block — no contiguous slice exists.
(The natural "but the index still contains b — surely it helps?" worry is answered separately in the FAQ box at the end of the page, so it does not interrupt the derivation here.)
Step 6 — WHY equality-before-range: the range "spends" the sort
WHAT. Query: WHERE a = 5 AND b > 2. Index (a, b): seek a = 5, then because the block is sorted by b, a b > 2 range is one clean contiguous sweep from the first b > 2 to the block's end.
WHY. After a range, the next column loses its usable order. Once you fan out across many b values, whatever comes after b is re-sorted inside each b — scattered again from the range's point of view.
PICTURE. Compare two indexes for status = 'paid' AND created_at > T: (status, created_at) gives one green sweep; (created_at, status) scatters status across a huge red range.
Step 7 — The mirror-image edge case: a range FIRST (a > 5 AND b = 2)
WHAT. Flip the previous query around: WHERE a > 5 AND b = 2 on the same index (a, b). Now the range is on the leading column a, and the equality b = 2 comes after it. The index seeks the start of a > 5 — but it can not also seek b = 2. It must sweep every a > 5 row and filter b = 2 one row at a time.
WHY. This is the precise moment the "range last" rule pays off — or bites. After the range on a opens up many a-values (6, 7, 9, ...), each of those a-blocks has its own independent run of b values (Step 3). So b = 2 is scattered once per block: (6, 2), (7, 2), (9, 2) — never contiguous across the whole a > 5 region. The moment you take a range, every column to its right degrades from seekable to merely filterable. And a query with two ranges (a > 5 AND b < 4) is even worse — only the first range (a) can seek; the second (b) can only filter within the swept rows.
PICTURE. Green marks the seekable start of a > 5; the red b = 2 targets show up scattered, one per swept block — filter, not seek.
Step 8 — WHY covering kills the last cost: no table trip
WHAT. Even a perfect seek returns pointers. To read the SELECTed columns not in the index, the DB follows each pointer back to the heap — a possible random I/O per row. A covering index stores those output columns in the leaf, so the answer comes straight from the index: an index-only scan.
WHY. Index leaves are packed and often cached; heap rows are scattered across pages. Ten thousand pointer-follows can mean ten thousand random reads. Putting the payload in the leaf deletes that step.
Before the formula, we need two more named quantities — how many rows matched and how expensive one heap trip is:
PICTURE. Left: pointers arc out to scattered heap pages (red). Right: the same query, answer read entirely inside the green index leaf.
The one-picture summary
Everything above, compressed: an unsorted heap → sort by a → sort b within a (lexicographic) → seek the leftmost prefix → range last → payload in the leaf. Each arrow removes one cost term.
Recall Feynman retelling — the whole walkthrough in plain words
Start with a messy box of order slips. To find one, you'd flip through every slip — slow. So make a sorted list of customer numbers with a little arrow to each slip; now you can "guess halfway, throw away half" and find any customer in a handful of steps. To also filter by status, sort the list by customer, then by status inside each customer — like a phone book by last-then-first name. Now customer = 42 AND status = open lands in one neat clump. But if you only know the status and not the customer, the statuses are sprinkled everywhere — no single page to open, so you're stuck scanning. That's the leftmost-prefix rule: you must know the columns left to right. If you use a range (customer > 42), it fans you out, so nothing after it can be searched neatly — even an exact status has to be checked slip-by-slip. That's why ranges go last. Finally, even after finding the slips, walking back to the box for extra details is slow; so print those details right on the sorted list — that's a covering index, and it deletes the last trip entirely.
See also: Index selectivity & cardinality (how "narrow" each block is), Query planner / EXPLAIN (how to confirm a seek happened), Write amplification (why wide covering indexes cost on writes).