Skip to content
The Data EngineeringThe Data EngineeringBeta
About
Main content

Composite indexes: everything follows from lexicographic order

Which rules follow from lexicographic order, and what decides whether the index is chosen at all?

A B+tree imposes a total order on the key tuple, lexicographically (like a dictionary: compare the first column, and only if equal, compare the second, and so on). Every rule practitioners memorize about multi-column indexes is a consequence of that one sentence. Deriving them is faster than remembering them.

Leftmost prefix. Only a prefix of the tuple defines a contiguous range in . An index on (a, b, c) serves predicates on a, on (a, b) and on (a, b, c). A predicate on b alone selects entries scattered all over the index, which is the same problem as an unclustered lookup, one level up. It is not a rule. It is a consequence.

Equality first, then one range, then sort columns. Once you apply a range predicate to a column, everything after it stops being contiguous. For a = 1 AND b > 5 AND c = 3: the index can seek to (1, 5) and scan forward, but c = 3 is only a filter applied to every entry scanned, not a seek. So an index on (a, c, b) is strictly better than (a, b, c) here: it seeks to (1, 3, 5) and scans one contiguous run. This single derivation fixes more bad than any other piece of knowledge here. (It is Priya's fourth symptom.)

-- Query: WHERE a = 1 AND b > 5 AND c = 3
CREATE INDEX bad  ON t (a, b, c);  -- seek (1,5), then scan and filter on c
CREATE INDEX good ON t (a, c, b);  -- seek (1,3,5), one contiguous run

"Most selective column first" is wrong as usually stated. For a set of pure equality predicates, column order does not change the number of index entries scanned at all: the matching range has the same size whichever order you write the columns in. What column order actually determines is:

  • which other queries in the workload can use this index as a prefix;
  • how well the leading column compresses or deduplicates;
  • whether the index can supply a required sort order.

So Order your leading columns so that one index serves three query shapes instead of one.

The heuristic has a partial rescue: index (Oracle and MySQL have had it for years; PostgreSQL gained a form of it recently). The engine enumerates the distinct values of an unconstrained leading column and does one seek per value. That converts the leftmost rule from hard to soft, but only when the leading column's is low enough that the enumeration is cheap. It is a mitigation, not a reprieve.

Width is paid in fanout, permanently. Going from a 16-byte entry to a 64-byte entry takes from roughly 500 to roughly 125 (an 8 KB page ÷ 16 B = 512; ÷ 64 B = 128). For 10⁹ rows:

  • log₅₀₀(10⁹) = 9 / 2.70 ≈ 3.3 levels
  • log₁₂₅(10⁹) = 9 / 2.10 ≈ 4.3 levels

That is one extra on every single lookup, forever, in exchange for columns that may serve one query shape.

Whether the index is chosen: the estimation problem

An index that is not chosen is pure write tax, and whether it is chosen is decided by the 's row estimates. A composite index is exactly where those estimates fail: the planner estimates a AND b by multiplying the two selectivities, which is right only if the columns are independent, and columns indexed together rarely are (city and postcode, status and created_at). The estimate comes out orders of magnitude too low and the planner picks a plan built for a handful of rows. Why the errors multiply, and what can and cannot repair, is on why errors multiply instead of adding.