Composite indexes, covering indexes: Exercises — Coding deep dive

Before we start, one picture to keep in your head for every problem below — the leftmost-prefix staircase: an index sorts rows the way a dictionary sorts words, one column at a time, left to right.

Figure — Composite indexes, covering indexes

Level 1 — Recognition

Goal: can you read an index definition and a query and say "match / no match"?

Recall Solution L1.1

The index is sorted first by a, then by b, then by c — like a dictionary sorted first by first letter. To seek, you must know the columns from the left with no gaps.

a = 1 → ✅ seek. a is the leftmost column; all a=1 entries sit contiguously.
b = 2 → ❌ no seek (full scan). You skipped a, so b=2 values are scattered everywhere — like looking for every word whose second letter is "e".
a = 1 AND b = 2 → ✅ seek on the prefix (a,b). Contiguous block.
c = 3 → ❌ no seek. c is the deepest level; without a and b its values are scattered.

Recall Solution L1.2

A query is covered when every column it touches — both in WHERE and in SELECT — lives inside the index. The index holds {status, user_id, total}.

Needs {status, user_id} ⊆ index → ✅ covered.
Needs note, which is not in the index → ❌ must fetch the row. Not covered.
Needs {status, user_id, total} = exactly the index → ✅ covered.

Level 2 — Application

Goal: apply the equality-before-range rule to design a working index.

Worked example L2.1 — Order two columns

Query:

SELECT id FROM events
WHERE type = 'click' AND ts > '2024-01-01';

You may build one index on type and ts. Which order — (type, ts) or (ts, type) — and why?

Recall Solution L2.1

Recipe: equality column first, range column last.

type = 'click' is an equality (one exact value). ts > '2024-01-01' is a range (many values).

(type, ts) → seek straight to the type='click' block; within it, rows are already sorted by ts, so ts > '2024-01-01' is a clean contiguous range-scan. ✅
(ts, type) → the index is sorted by ts first, so ts > '2024-01-01' grabs a wide band of all types, then must filter out non-click rows one by one. ❌

Answer: (type, ts).

Recall Solution L2.2

Keep the search key (type, ts) (equality then range), and add the output columns as non-key payload:

CREATE INDEX ON events (type, ts) INCLUDE (id, user_id);

Now the leaf pages carry id and user_id, so the DB never visits the table. INCLUDE keeps them out of the searchable key, so the tree stays narrow and cheap to seek. (See parent's note on INCLUDE.)

Level 3 — Analysis

Goal: reason about partial use, gaps, and cost.

Recall Solution L3.1

The usable prefix stops at the first missing column.

a = 5 → ✅ seek narrows to the a=5 block.
b is not constrained → this is a gap. Beyond it, the index can no longer seek.
c = 9 → cannot be used for seeking (there's a gap at b). It becomes a filter applied while scanning the a=5 block.

Net: the index seeks on a only, then scans every a=5 entry checking c=9. Useful, but not as tight as if b were also constrained.

Recall Solution L3.2

Index (status): seeks to status='paid' → $1, 000, 000 \times 0.10 = 100, 000$ index entries examined; each surviving region filter passes $5%$ , leaving $100, 000 \times 0.05 = 5, 000$ result rows. Index entries examined = $100, 000$ .

Index (status, region): seeks the prefix (status='paid', region='EU') directly → jumps straight to that contiguous block. Index entries examined $\approx 5, 000$ (only the matches).

The composite index examines $20 \times$ fewer index entries ( $100, 000/5, 000 = 20$ ). This is exactly why matching the index to both predicates wins — see Index selectivity & cardinality.

Level 4 — Synthesis

Goal: design one index that satisfies filter + sort + output together.

Worked example L4.1 — Filter + ORDER BY + LIMIT

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

Design one index that (a) seeks the filter, (b) needs no sort step, (c) is covering.

Recall Solution L4.1

Apply the E-R-C recipe: Equality → Range/sort → Cover.

Equality columns first: customer_id = 42 and status = 'open' → (customer_id, status).
Sort column next: created_at DESC → append it so rows emerge pre-sorted; LIMIT 20 just grabs the top 20 with no separate sort.
Cover the output: order_id, amount → INCLUDE them.

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

Now: seek (42, 'open'), walk created_at descending, stop after 20, return columns from the leaf. One index, zero table fetches, zero sort.

Recall Solution L4.2

No. Once status becomes a range (<> 'closed' spans many values), the index is sorted by status before created_at, so within the matching band the created_at values are not globally ordered — they restart for each status. The DB must still sort by created_at.

Fix options:

Rewrite the predicate to equalities if the domain is small: status IN ('open','pending') per-value seeks that the planner can merge-sort.
Or accept the sort step for this shape, and let the index only handle customer_id + covering.

Level 5 — Mastery

Goal: weigh trade-offs — writes, width, and choosing among competing designs.

Recall Solution L5.1

Design for the query with the longer prefix, because a longer index also serves shorter leftmost-prefix queries.

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

Q1 uses the full prefix (customer_id, status) then created_at order, covered by INCLUDE (amount). ✅
Q2 constrains only customer_id — the leftmost prefix — and the index seeks that block; but note the sort is not free for Q2, because after customer_id the next column is status, not created_at, so within a customer the rows are ordered by status first. Q2 gets a fast seek + covering read, but pays a sort. That's an acceptable single-index compromise; a second index (customer_id, created_at) INCLUDE (amount) would make Q2's sort free at the cost of more write overhead. Note the honest trade-off — do not claim Q2's sort is free.

Recall Solution L5.2

Against. Reasons rooted in first principles:

Write amplification: every INSERT/UPDATE touching an indexed row must also update the index leaf. Adding a 4 KB payload multiplies the bytes written per row. Across $50, 000$ writes/day that's up to $50, 000 \times 4 KB \approx 200 MB/day$ of extra index churn. See Write amplification.
Cache pressure: fat leaves mean fewer entries per page, so more pages, so less of the index fits in RAM — slower seeks even for queries that don't read big_note.
Low payoff: big_note is rarely selected, so it seldom saves a fetch.

Rule: cover only hot, narrow columns (the 80/20). Leave big_note in the heap.