Composite indexes and column order: an interactive query planner

A database index is a sorted copy of some of a table’s columns that lets the database find matching rows without reading every one. A composite index covers several columns and is sorted by the first, then the second, and so on, so the order of its columns decides which queries it can serve. The rule of thumb: columns compared with = first, then the one used in a range or ORDER BY.

The playground runs five queries against a table of a million orders. Pick a query and an index, and see how many index entries are read, how many rows are fetched from the table, whether a sort is needed, and how every other index would have done.

SELECT * FROM orders
WHERE status = 'pending'
  AND created_at > now() - interval '1 day';

How a B-tree index finds rows

1. Seek: walk down the tree to the first entry that matches, a handful of page reads even for millions of rows.
2. Scan: read entries in order for as long as they still match.
3. Fetch: for each entry, read the full row from the table, a random read, unless the index already holds every column the query needs.

The work is the entries scanned plus the rows fetched, and both depend on how much of the query the index can narrow with its seek.

The leftmost prefix rule

An index on (a, b, c) is sorted by a first, so it can find rows by a, by a and b, or by all three, but not by b alone: rows with a given b are scattered through every value of a. In the last preset, a query on customer_id cannot use an index on (status, customer_id) at all, and reads all a million rows.

Equality first, range last

The seek can use any number of equality columns from the left, but only one range, and it stops there. Columns after the range can still be checked as entries are read, but not to skip any. For “pending orders from today”, (status, created_at) seeks straight to today’s pending orders and reads 110 entries, while (created_at, status) reads all 1,370 of today’s orders and checks each one’s status. For one customer’s orders this month the gap is wider: (customer_id, created_at) reads under one entry on average, and (created_at, customer_id) reads 41,096.

Indexes that sort for you

Within an equality match, an index returns rows already ordered by its next column, so an ORDER BY on that column needs no sort, and a LIMIT lets the scan stop early. For the latest 20 pending orders, (status, created_at) reads 20 entries and stops. An index on status alone finds all 80,000 pending orders, fetches every one and sorts them to keep 20.

Covering indexes and the cost of indexes

If the index holds every column the query reads, the table fetches disappear, an index-only scan. Adding columns with INCLUDE, or at the end of the key, buys that. But every index costs something: each insert, update and delete has to change it, it takes space, and it competes for memory. And an index on a column with few distinct values, like a status, matches a large share of the table; once a condition matches more than a few percent of rows, random fetches can cost more than reading the whole table in order, and the planner may choose a full scan anyway.

Composite indexes in SQL

-- equality columns first, then the range or ORDER BY column
CREATE INDEX orders_status_created ON orders (status, created_at);

-- serves all of these with a seek and no sort:
--   WHERE status = 'pending'
--   WHERE status = 'pending' AND created_at > now() - interval '1 day'
--   WHERE status = 'pending' ORDER BY created_at DESC LIMIT 20
-- but not this, which has no condition on status:
--   WHERE created_at > now() - interval '1 day'

-- a covering index answers from the index alone, with no table fetches (PostgreSQL)
CREATE INDEX orders_customer_created ON orders (customer_id, created_at) INCLUDE (total);

EXPLAIN ANALYZE SELECT * FROM orders
WHERE status = 'pending' ORDER BY created_at DESC LIMIT 20;

In a system design interview

When you write down a schema, name the queries and the index for each: “The order history page asks for one customer’s orders, newest first, 20 at a time, so the orders table has an index on (customer_id, created_at); the operations dashboard lists pending orders by age, so another on (status, created_at). Nothing else is indexed, because the table is write-heavy.” Expect the follow-ups: why that column order, what the writes cost, and what changes when the table is sharded.

Read the guide to database indexing, see choosing a shard key for the same thinking one level up, or watch a strong candidate design a ticketing system.

Questions people ask