Indexescomposite indexleftmost prefixcolumn ordercoveringsort avoidance

Composite Indexes and the Leftmost-Prefix Rule

A multi-column B-tree is sorted by its first column, then its second inside that, then its third; a query can use it from the left, through equalities, up to the first range — and not at all if it skips the first column.

▶ Interactive Try queries Interview question See how this works internally →

Progress

How a composite index is sorted

CREATE INDEX ON users (country, city, age) stores entries sorted by country; within one country, by city; within one city, by age. Like a phone book sorted by surname then first name. You can find every "Schmidt" (leading column), every "Schmidt, Anna" (two columns), but you cannot find every "Anna" without reading the whole book — first names are scattered across every surname.

That is the leftmost-prefix rule. A query can use the index for a prefix of its columns, starting from the first. WHERE country = ? uses one column; WHERE country = ? AND city = ? uses two; WHERE city = ? uses none. The index on (country, city, age) also serves (country, city) and (country) — so those single-column indexes would be redundant.

Equalities, then one range

Prefix matching continues through equality conditions and stops after the first range. WHERE country = ? AND city = ? AND age > 30 uses all three: two equalities narrow to one (country, city) run, and within that run ages are sorted, so > 30 is a range scan. WHERE country = ? AND age > 30 uses only country: with city unconstrained, the ages inside one country are not sorted, so age becomes a filter applied after the index fetched every row for the country.

This gives the column-ordering rule: equality columns first, then the range column, then columns needed for ordering or covering. Among equality columns, put the most selective first if the query always constrains all of them, or the one that appears in the most queries if it does not.

Free ordering, and the LIMIT payoff

Because the index is sorted, WHERE user_id = ? ORDER BY created_at DESC on an index (user_id, created_at) needs no Sort node: the executor walks the index backwards from the end of that user’s run. With LIMIT 20 it walks 20 entries and stops. The same query without the index sorts every one of the user’s rows to return 20. For "newest N for this parent" — the most common query shape in any application — this is the difference between constant and linear time.

The index for "my recent orders"

1CREATE INDEX orders_user_recent ON orders (user_id, created_at DESC);
2 
3-- Index Scan, no Sort, stops after 20 entries:
4SELECT id, total FROM orders
5WHERE user_id = 17
6ORDER BY created_at DESC
7LIMIT 20;

Covering: include what you select

If every column the query touches — in SELECT, WHERE, ORDER BY — is in the index, the executor never reads the table at all: an Index Only Scan. Adding total to (user_id, created_at) makes the recent-orders query index-only. PostgreSQL’s INCLUDE (total) adds the column to leaf entries without making it part of the sort key, which keeps the tree narrower.

The cost is a wider index to maintain and a strong coupling to one query’s column list. SELECT * defeats it permanently. Use it for the two or three hottest queries in the system, not everywhere.

Key points

A composite index is sorted by column 1, then 2, then 3. Queries use a leftmost prefix.
Equality columns first, then at most one range, then ordering/covering columns.
An index on (a, b, c) makes indexes on (a) and (a, b) redundant.
Matching ORDER BY to the index removes the Sort; with LIMIT the query becomes constant-time.
Include selected columns to get an Index Only Scan for the hottest queries.

Composite index: which queries can use it?

Which queries can use this index?

A composite B-tree is sorted by its columns in order — like a phone book sorted by (surname, first name). Guess how many columns each query can use before revealing it.

CREATE INDEX idx_users ON users (country, city, age);

index entries, in stored order:
  ('DE', 'Berlin',    24) -> row
  ('DE', 'Berlin',    31) -> row
  ('DE', 'Hamburg',   19) -> row      sorted by country,
  ('DE', 'Munich',    45) -> row      then city,
  ('FR', 'Lyon',      33) -> row      then age
  ('FR', 'Paris',     28) -> row
  ('NL', 'Amsterdam', 52) -> row

Query 1

SELECT * FROM users
WHERE country = ?

How many of the three index columns can this query use?

The rule in one sentence: an index can be used from the leftmost column inwards, with equalities as long as you like and then at most one range — and it stops at the first column your query does not constrain.

1/101 of 10

Try it in the playground

CREATE INDEX users_loc ON users (country, city, created_at);
EXPLAIN ANALYZE SELECT id FROM users WHERE country = 'DE' AND city = 'Berlin';

Two leading columns used. →

CREATE INDEX users_loc ON users (country, city, created_at);
EXPLAIN ANALYZE SELECT id FROM users WHERE city = 'Berlin';

Skipping the first column: unusable. →

When to use — and when not

Use it when

Queries that always constrain the same leading column and then filter or sort by another — tenant + time, user + time, status + priority.

Avoid it when

Queries that constrain the columns in unpredictable combinations — no single order serves them; consider separate indexes.

Failure modes

Index on (a, b) and the hot query filters on b alone.
Range column before an equality column.
Redundant single-column index next to a composite that already covers it.

See how this works internally →

Descend one layer: the same topic explained from the machinery up.

Why does column order matter? Keys inside a B+ tree page

↓ Database Internals → B+ Tree Internals: Pages, Splits, Merges

Why can a scan beat the index? Cost-based optimization

↓ Database Internals → Cost-Based Optimization

← Why Is This Query Slow? Indexes Index Types: B-tree, Hash, Partial, Expression, Covering, Full-Text →