Composite indexes — the leftmost prefix rule

Day 1 taught you what a single-column index is. Day 3 taught you how to read EXPLAIN output. Today: what happens when you index two columns together — and why the column order you choose determines which queries can use the index.

What is a composite index?

A composite index (also called a multicolumn index) is an index on more than one column:

CREATE INDEX idx_users_name ON users(last_name, first_name);

This creates a single B-tree index sorted by last_name first, then first_name within each last_name group. Think of a phone book: sorted by last name, then by first name within each last name.

One index, two columns. But here’s the catch: the order of columns in the index definition determines which queries can use it efficiently.

The leftmost prefix rule

An index on (last_name, first_name) can be used efficiently for:

• WHERE last_name = ‘Smith’ ✅ — seeks directly into the first column
• WHERE last_name = ‘Smith’ AND first_name = ‘John’ ✅ — seeks into both columns

But cannot be used efficiently for:

• WHERE first_name = ‘John’ ❌ — the index is sorted by last_name first, so Johns are scattered across all last-name groups

This is the leftmost prefix rule: a composite index can only seek efficiently when the query filters on a leftmost prefix of the indexed columns. An index on (a, b, c) serves queries on a, (a, b), or (a, b, c) — but not (b, c) or c alone.

The real benchmark

I created a users table with 1,000,000 rows and a composite index on (last_name, first_name). Then I ran three query patterns (30 iterations each, median):

Three key observations from the benchmark:

• Both columns = 5.3ms. The index seeks directly to (Smith, John) — 1 search, 2,500 rows. Narrowest result set, fastest lookup.
• Leftmost only = 44.8ms. The index still seeks efficiently (1 search) on last_name, but returns 50,000 rows (all Smiths). Slower because more rows to fetch from the table.
• Non-leftmost = 55.6ms. PostgreSQL CAN use the composite index for first_name only, but it must do 41 index searches instead of 1 — scanning through the entire index to find Johns scattered across every last-name section. Far less efficient.

(Full results: benchmark/composite-index-results.md)

Why does order matter? (the B-tree explanation)

A B-tree index on (last_name, first_name) is sorted by last_name first, then first_name within each last_name. It looks like this:

Anderson, David
Anderson, Jessica
Anderson, Michael
Brown, Elizabeth
Brown, Karen
Brown, William
...
Smith, John     ← both columns: direct seek
Smith, Karen
Smith, Thomas
...

When you query WHERE last_name = ‘Smith’, the database jumps to the Smith section — one seek. When you also filter AND first_name = ‘John’, it narrows within Smith — still one seek, fewer rows.

But when you query WHERE first_name = ‘John’, Johns are scattered across every last-name group. The database can’t jump to “John” — it must check every section. That’s why it does 41 searches instead of 1.

When to use a composite index

• When you frequently query multiple columns together. If your app often does WHERE last_name = ? AND first_name = ?, a composite index on (last_name, first_name) is ideal.
• Put the most-queried column first, then the most selective among those. The first column must be one you actually filter on frequently — otherwise the leftmost prefix never activates. Among the columns you query together, put the most selective one first (most distinct values) — it narrows the search fastest.
• Don’t create redundant single-column indexes. An index on (last_name, first_name) already serves WHERE last_name = ?. A separate index on last_name alone is redundant — it wastes write speed and storage (Day 1’s tradeoff).

The tradeoff (name it in interviews)

“I’d use a composite index on the columns I query together most often, ordered by selectivity — most selective first. This serves the leftmost prefix for the most common query patterns. If I also need to query the second column alone, I’d add a separate single-column index for that — accepting the extra write cost.”

The transfer question

From Day 1 → Day 6: Day 1 said “don’t index everything — indexes cost writes.” How does the composite index change (or not change) that advice?

Answer (click to reveal)

The advice still holds — but a composite index is smarter than multiple single-column indexes. Instead of creating separate indexes on last_name AND first_name (two indexes = double the write cost), one composite index on (last_name, first_name) serves both WHERE last_name = ? AND WHERE last_name = ? AND first_name = ? — with only one index’s write cost.

The composite index reduces the total number of indexes needed. But it doesn’t eliminate the tradeoff: each composite index still costs one index’s worth of write maintenance. And if you need to query first_name alone (non-leftmost), you still need a separate index for that — so you can’t always replace N single-column indexes with one composite.

Check your understanding