Composite indexes, covering indexes

WHAT is a composite index?

The key idea is the sort order is hierarchical, just like dictionary ordering of words: (A, 1) < (A, 2) < (A, 9) < (B, 1) < (B, 5).

WHY do these exist? (first principles)

A B-tree index lets you do binary-search-like lookups: instead of scanning $N$ rows ( $O(N)$ ), you descend a balanced tree in $O(\log N)$ .

But two problems remain:

Multi-condition filters. A query WHERE a=? AND b=? on two separate indexes can only efficiently use one of them, then filter the rest. A composite (a,b) index narrows both at once.
The extra fetch. Even after the index finds the matching row pointers, the DB must go to the table to read the other columns you asked for. That's a random I/O per row. A covering index removes that step.

HOW composite index ordering works — the leftmost-prefix rule

Why? Because the index is sorted lexicographically. Knowing only $c_2$ (without $c_1$ ) is like knowing only first names in a (last, first) phone book — the matching entries are scattered everywhere, so no fast seek is possible.

Worked example Index

(a, b, c) — which queries can seek?

Query predicate	Uses index?	Why this step?
`a = 5`	✅ (a)	leftmost prefix present
`a = 5 AND b = 3`	✅ (a,b)	full prefix to b
`a = 5 AND b = 3 AND c = 1`	✅ (a,b,c)	full prefix
`b = 3`	❌ (seek)	`a` missing → no leftmost prefix
`a = 5 AND c = 1`	⚠️ partial	seeks on `a`, then filters `c` (gap at b)
`a = 5 AND b > 3 AND c = 1`	⚠️	range on b stops seeking; `c` only filters

HOW a covering index works

Worked example Turning a query "index-only"

SELECT user_id, total
FROM orders
WHERE status = 'paid';

Index (status) → finds rows, then fetches user_id, total from the table. Extra I/O.
Index (status, user_id, total) → ✅ covering: status for filtering, user_id, total are present in the index leaf. Answer comes straight from the index. Why this works: every column the query touches lives in the index.

Postgres syntax to avoid bloating the search key: CREATE INDEX ON orders (status) INCLUDE (user_id, total); — status is the searchable key, the others are just payload stored in leaves.

Figure — Composite indexes, covering indexes

Worked example: designing one index for a query

Worked example Real query

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

Step 1 — equality columns first: customer_id, status are equalities → put them first. Why? They each narrow to an exact slice. Step 2 — sort column next: created_at for the ORDER BY → next, so rows come out pre-sorted and LIMIT 10 just grabs the top. Why? No separate sort step needed. Step 3 — cover the output: add order_id, amount as INCLUDE payload. Why? Then no table fetch.

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

Common mistakes

Flashcards

What is a composite index?

An index on multiple columns stored sorted lexicographically — first by col1, then col2 within equal col1, etc.

State the leftmost-prefix rule.

An index on (c1,…,cn) is usable only if the query constrains a leftmost prefix (c1, or c1+c2, …); equality on prefix columns, then one range on the next.

Why can't index (a,b) efficiently serve WHERE b = 5?

Entries are sorted by a first, so a given b value is scattered throughout — no contiguous range to seek.

What is a covering index?

An index containing all columns a query reads (filter + SELECT), so it's answered index-only with no table fetch.

Equality vs range columns — what's the ordering rule?

Put equality-predicate columns first, the range/ORDER BY column last, so you can seek then range-scan in order.

What does Postgres INCLUDE (cols) do?

Adds columns as non-key payload in leaf pages to make the index covering, without bloating the searchable key.

Main downside of covering/wide indexes?

More storage and slower writes (each modification must update the index); may not fit in cache.

Why is eliminating the table fetch so impactful?

Each fetch is a potential random I/O to scattered table pages; index-only scan avoids thousands of random reads.

Recall Feynman: explain to a 12-year-old

Imagine a giant phone book. If it's sorted by last name then first name, you can find "Smith, Anna" super fast. But if you only know "Anna" (no last name), you'd have to read the WHOLE book — that's why a multi-column index needs you to know the first column. Now imagine the phone book also prints each person's phone number right next to their name — then you never have to drive to their house to ask. That printed-number trick is a covering index: everything you need is right there.

Connections

B-tree indexes — the structure that makes ordered seeks possible
Clustered vs non-clustered indexes — why the "extra fetch" exists
Query planner / EXPLAIN — how to verify an index-only scan
Index selectivity & cardinality — choosing which column leads
Write amplification — the cost side of adding indexes
Database normalization — affects which columns you filter on

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, index ka pura funda yeh hai ki table ko poora scan na karna pade. Composite index matlab ek index jo do ya zyada columns par bana ho, jaise (a, b). Ye entries ko pehle a se sort karta hai, aur same a ke andar b se. Isiliye ek golden rule hai — leftmost prefix rule: aap index ko tabhi efficiently use kar sakte ho jab aap left wale columns ko constrain karo. Sirf b pata hone se kuch nahi hoga, kyunki b ki values poore index mein bikhri hui hain (jaise phone book mein sirf first name pata ho).

Design ka mantra yaad rakho: Equality columns pehle, Range ya ORDER BY wala column last. Agar aapki query WHERE customer_id=42 AND status='open' ORDER BY created_at hai, to index (customer_id, status, created_at) perfect hai — equality se exact slice mil jata hai, aur created_at already sorted aata hai to LIMIT 10 turant top rows utha leta hai, alag se sorting nahi karni padti.

Ab covering index ka jaadu: normally index sirf row ka pointer deta hai, phir database table tak jaata hai baaki columns lene ke liye — yeh random disk I/O slow hota hai. Agar index ke andar hi saare zaroori columns ho (jo SELECT mein chahiye), to query index-only ho jaati hai, table tak jaana hi nahi padta. Postgres mein INCLUDE (col1, col2) se aap ye payload columns add karte ho bina search key ko bhaari banaye.

Par dhyan rakho — har column ka index mat banao, aur cover karne ke chakkar mein index ko itna mota mat banao ki writes slow ho jaayein aur cache mein na fite. 80/20 lagao: sirf hot, baar-baar chalne wali queries ke liye smartly index banao. E-R-C yaad rakho: Equality, Range, Cover.