Composite indexes, covering indexes: Worked examples

Throughout, imagine one table:

orders(customer_id, status, created_at, amount, order_id)

and one index we keep coming back to:

IX = (customer_id, status, created_at)

Read that as: entries are sorted first by customer_id, then by status within equal customer_id, then by created_at within equal (customer_id, status). That nested "within" is the whole story — the figure below draws it.

Figure — Composite indexes, covering indexes

The scenario matrix

Every query this topic can throw at you falls into one of these cells. The examples afterwards are labelled with the cell they cover.

#	Cell (case class)	What's special about it	Example
C1	Full prefix, all equalities	Ideal case: tight seek to one block	Ex 1
C2	Partial prefix (gap in middle)	Column skipped → seek stops early, rest is filter	Ex 2
C3	Equality then range (right order)	Range on the LAST used column — still one block	Ex 3
C4	Range then equality (wrong order)	Range too early → later column can't seek	Ex 4
C5	Wrong leftmost column	Query filters only a non-leading column	Ex 5
C6	Covering vs non-covering	Same filter, extra table fetch removed	Ex 6
C7	Sort/ORDER BY + LIMIT + ties	Index supplies pre-sorted rows; tie-break by later key	Ex 7
C8	Degenerate / empty inputs	Zero rows, `NULL`, `=` a value that doesn't exist	Ex 8
C9	Real-world word problem	Design the index from a feature request	Ex 9
C10	Exam twist	`OR`, function on column, wrong-direction sort	Ex 10

Ex 1 — Full prefix, all equalities (C1)

Worked example Statement

Index is $(customer_id, status, created_at)$ . Query:

WHERE customer_id = 42 AND status = 'open' AND created_at = '2024-05-01';

Forecast: Will the index seek on all three columns, some, or none?

Steps

Check the leftmost column: customer_id is constrained (= 42). ✅ Why this step? The index is sorted by customer_id first; without it we'd have no anchor.
Next column status is an equality (= 'open'), and it's the next in the index. ✅ Why? Within customer_id = 42, entries are sorted by status, so we can narrow again.
Next column created_at is an equality too. ✅ Why? Within (42, 'open'), entries are sorted by created_at; one more narrowing lands us on a single contiguous block.

Answer: seeks on all 3 columns — a full-prefix equality match, the tightest possible.

Verify: $L = 3$ and $n = 3$ , so $L = n$ → full-prefix. ✔

Ex 2 — Partial prefix with a gap (C2)

Steps

customer_id = 42 → seek works. $L$ so far $= 1$ . ✅
The next index column is status, but the query says nothing about status. ❌ Why does this stop us? Within customer_id=42, entries are ordered by status first. Since we don't fix status, our created_at values are scattered across every status — not one contiguous block.
created_at therefore can't be used to seek; it can only filter the rows already found by customer_id. Why? Seeking requires an unbroken sorted prefix; the gap at status breaks it.

Answer: $L = 1$ . Index seeks on customer_id, then filters created_at while scanning that customer's entries.

Verify: $L = 1$ (only the leading contiguous constrained column). ✔

Ex 3 — Equality then range, right order (C3)

Steps

customer_id = 42 equality → seek. $L = 1$ . ✅
status = 'open' equality, next column → seek. $L = 2$ . ✅
created_at > '2024-01-01' is a range, and it's on the last used column. ✅ Why is a range OK here? Within (42, 'open'), entries are sorted by created_at. A range like > X maps to one contiguous tail of that block — seek to X, then read forward. That's still a single block.

Answer: $L = 3$ ; all three participate — two equalities plus a range that reads a contiguous slice.

Verify: equalities $= 2$ , one range on the next column counted in $L$ , so $L = 2 + 1 = 3$ . ✔

Ex 4 — Range then equality, wrong order (C4)

Worked example Statement

Same index, but now the query ranges on a middle column:

WHERE customer_id = 42 AND status > 'a' AND created_at = '2024-05-01';

Forecast: Can created_at seek after the status range?

Steps

customer_id = 42 equality → seek. $L = 1$ . ✅
status > 'a' is a range on status (the 2nd column). It seeks a contiguous slice of statuses, and being the one allowed range it counts in $L$ . $L = 2$ . ✅
created_at = '2024-05-01' — but we just did a range on status. ❌ Why blocked? Once status spans a range of values, the created_at ordering resets for each different status. So created_at values are scattered again — no single block to seek. created_at becomes a filter only.

Answer: $L = 2$ . The range on status "uses up" our one range and stops created_at from seeking.

Verify: equalities before the range $= 1$ , plus the one counted range $= 1$ , so $L = 2$ (not 3). ✔

Ex 5 — Wrong leftmost column (C5)

Steps

Leftmost index column is customer_id. The query does not constrain it. ❌ Why fatal? The entire index is sorted by customer_id first. Every customer has its own status='open' entries, scattered from the top of the index to the bottom. There is no contiguous block of status='open'.
Therefore no seek at all; the planner would either full-scan the index or the table.

Answer: $L = 0$ . This index is useless for this query — you'd want a separate index leading with status. See Index selectivity & cardinality to decide if that's worth it.

Verify: leading column unconstrained → $L = 0$ . ✔

Ex 6 — Covering vs non-covering (C6)

Worked example Statement

Two candidate indexes for:

SELECT amount FROM orders WHERE customer_id = 42 AND status = 'open';

IX-A = (customer_id, status)
IX-B = (customer_id, status) INCLUDE (amount)

Both find the same rows. Forecast: which avoids touching the table, and how many random fetches does the other do if 500 rows match?

Steps

Both seek on (customer_id, status) — identical filter performance ( $L = 2$ ). ✅ Why identical? INCLUDE columns are payload, not search keys; they don't change the seek.
IX-A leaf entries hold only the key + a row pointer. The query wants amount, which isn't there. So for each matching row the DB does a table fetch (random I/O). For 500 matches → up to 500 random page reads. Why so costly? Table rows are scattered across pages (see Clustered vs non-clustered indexes); each is a separate disk trip.
IX-B stores amount right in the leaf. amount is read straight from the index → 0 table fetches. This is an index-only scan.

Answer: IX-B is covering; table fetches drop from 500 to 0.

Verify: non-covering fetches $= 500$ ; covering fetches $= 0$ ; savings $= 500$ . ✔

Ex 7 — Sort + LIMIT served by the index, with a tie-break (C7)

Worked example Statement

SELECT order_id FROM orders
WHERE customer_id = 42 AND status = 'open'
ORDER BY created_at DESC
LIMIT 10;

Index: (customer_id, status, created_at DESC) INCLUDE (order_id). Extra wrinkle: three orders share the exact same created_at (a tie). Forecast: Does the DB perform a separate sort? In what order do the three tied rows come out, and is that order stable across runs?

Steps

Seek customer_id=42 AND status='open' → lands on the block for that pair. $L = 2$ . ✅
Within that block, entries are already sorted by created_at DESC (we built the index that way). Why does this matter? ORDER BY created_at DESC matches the stored order exactly → no sort step needed. The DB just reads entries in storage order.
The tie. Three rows have identical created_at. The ORDER BY alone doesn't say who wins. What breaks the tie? Since created_at is the last key column, the tied rows sit next to each other in the leaf but in an order the query never pinned down — the engine returns them in whatever physical order they happen to occupy (often insertion/row-id order). This is a non-deterministic tie: the set of 10 rows is correct, but the order among ties can shift between runs or after a rebuild. Why care? If the boundary of LIMIT 10 falls inside a tie group, which tied row makes the cut can change run to run. Fix: add a deterministic tie-breaker, e.g. ORDER BY created_at DESC, order_id DESC, and put order_id in the key so the index still supplies the full order.
order_id is in the INCLUDE payload → index-only, no table fetch.

Answer: 0 sort operations, exactly 10 index entries read (plus the seek descent). Tied rows come out in physical order — not guaranteed stable unless you add a tie-breaker column.

Verify: entries read $= 10$ , sorts $= 0$ , fetches $= 0$ ; tie group size $= 3$ . ✔

Ex 8 — Degenerate & empty inputs (C8)

Steps

(a) Missing value. Seek descends the tree to where 999999 would be, finds the block empty, returns 0 rows immediately. Why still fast? A seek that lands on an empty range costs $O (lo g N)$ — same as a hit; it just reads 0 leaf entries.
(b) NULL on status. In most engines NULL is stored and sorted (typically as a distinct value at one end). status IS NULL seeks the NULL slot within customer_id=42. $L = 2$ , works. Why care? Beginners assume NULL breaks indexes — it doesn't for IS NULL; it does break for = NULL (which is never true, matches nothing).
(c) Empty table. Index has 0 entries; the root is empty. Any seek returns 0 rows in $O (1)$ . Why? Nothing to descend into — the degenerate limiting case of $N \to 0$ .

Answer: all three behave correctly; entries read = 0 for (a) and (c); (b) reads however many NULL-status rows customer 42 has.

Verify: (a) rows $= 0$ ; (c) rows $= 0$ ; = NULL matches $= 0$ (three-valued logic). ✔

Ex 9 — Real-world word problem (C9)

First, the recipe we'll apply, spelled out in full:

Steps (recipe: E → R → C)

E — Equality columns first. We always filter one customer and one status: customer_id = ?, status = 'paid'. Both equalities → they lead. Why? Each pins an exact slice (Ex 1 logic).
R — Range/sort column next. "20 most recent" = ORDER BY created_at DESC LIMIT 20. Put created_at DESC right after the equalities. Why? Then results emerge pre-sorted (Ex 7 logic), no sort step.
C — Cover the output last. The dashboard shows order_id, amount → add them as INCLUDE payload. Why? Eliminates the table fetch (Ex 6 logic).

Answer:

CREATE INDEX ON orders (customer_id, status, created_at DESC)
INCLUDE (order_id, amount);

Now the metric. Two equalities (customer_id, status) plus the sort column created_at used as the ordered read give a usable prefix of $L = 3$ — same rule as Ex 3: the sort/range column is counted in $L$ . From that block we read only the first 20 entries, and with the INCLUDE payload there are 0 table fetches.

Verify: usable prefix $L = 3$ (two equalities + the sort column), entries read $= 20$ , table fetches $= 0$ . ✔

Ex 10 — Exam twists (C10)

Steps

(a) OR. An OR between different columns is two separate conditions, not a single prefix. Why blocked? customer_id=42 matches one block; status='open' matches scattered entries (Ex 5). No single contiguous range covers both. The planner may do an index-merge (two seeks unioned) or a full scan — but not one clean seek. Rewrite with UNION of two indexable queries.
(b) Function on the column. The index stores raw status, not LOWER(status). Why blocked? Seeking needs the stored sort order; LOWER(...) scrambles it. Fix: an expression index on LOWER(status), or store the value already lowercased.
(c) Reverse sort direction. Query wants ASC, index is DESC. Why usually fine? B-trees are doubly linked, so the DB can read the block backwards — same block, reverse traversal, still no sort step. $L = 2$ seek + backward scan.

Answer: (a) no clean seek (needs rewrite), (b) no seek (needs expression index), (c) seeks fine by reading backward.

Verify: (a) single-seek possible = false; (b) single-seek possible = false; (c) single-seek possible = true. ✔

Recall

Recall Match each example to its rule in one sentence

Ex 1 :::: full equality prefix → deepest possible seek ( $L = n$ ). Ex 2 :::: gap in the middle → seek stops at the gap; rest is filter. Ex 3 :::: range on the last used column → still one contiguous block, range counted in $L$ . Ex 4 :::: range on a middle column → later columns can't seek. Ex 5 :::: leading column unconstrained → $L = 0$ , index unusable. Ex 6 :::: INCLUDE payload → same seek, zero table fetches. Ex 7 :::: matching sort order → no sort step; ties need an explicit tie-breaker. Ex 8 :::: empty/NULL/missing → seek still $O (lo g N)$ , returns 0 cleanly.

See also: Query planner / EXPLAIN to see which of these the optimizer actually chose, and Database normalization for why the column set exists in the first place.