Composite index design

A composite index is one B-tree whose key is several columns, sorted by the first column, then by the second wherever the first ties, and so on. That single sort order decides which WHERE clauses can jump straight to their rows, whether ORDER BY … LIMIT needs a sort, and whether the query touches the table at all. Designing a composite index is mostly choosing the column order.

Picture it first: the reservation chart

Picture the master reservation chart for a long-distance train: one list of every passenger, sorted by coach (A1, B1, S1, S2 …) and, within each coach, by berth number. Now try some questions against it.

• “Who is in coach S4?” Find the first S4 line and read until S5 starts. One contiguous block.
• “Who has berths 1 to 8 in S4?” A shorter block inside the S4 block.
• “Who is on berth 23?” Berth 23 appears once inside every coach block. With 18 coaches you make 18 quick jumps: tedious, but fine, because there are few coaches.
• “Is Mr Iyer on board?” The chart is not sorted by name. You read every line. Map it back. The chart is the leaf level of the index; each line is an index entry (the key plus a pointer to the row); the coach is the leading column; the berth is the second column; the passenger’s name is a column that isn’t in the index. Only the sort order decides which questions are instant. A phone book sorted by surname, then first name, works the same way.

How a composite index is sorted

An index on (a, b, c) holds one entry per row. Entries are ordered by a; entries with the same a are ordered by b; entries with the same a and b are ordered by c. It is dictionary order applied to columns instead of letters. MySQL’s manual puts it well: a multiple-column index is a sorted array whose rows are the indexed values concatenated together.

Every example in this article uses one table from a UPI-style payments app, in PostgreSQL 18:

CREATE TABLE transactions (
  id               bigint GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
  user_id          bigint      NOT NULL,
  created_at       timestamptz NOT NULL,
  status           text        NOT NULL,  -- SUCCESS, PENDING, FAILED, REVERSED
  amount_paise     bigint      NOT NULL,
  counterparty_vpa text        NOT NULL,
  note             text
);
-- 500 million rows from about 50 million users;
-- user 42 has 4,812 transactions over three years.

A B-tree lookup does two things: it descends from the root to the first entry at or after a start key, then walks right along the leaf pages until it passes an end key. That is fast whenever the rows you want form one contiguous run in index order. Everything else in this article follows from that sentence. (How the tree itself is built, and why it is only three or four levels tall, is in database indexes.)

The leftmost-prefix rule

Because entries are grouped by the first column, a predicate can seek (jump to a start key) only if it pins down a leftmost prefix of the index. MySQL’s manual says it directly: an index on (col1, col2, col3) gives indexed search on (col1), (col1, col2) and (col1, col2, col3), and nothing else. PostgreSQL’s documentation gives the more exact rule:

1. Equality constraints on the leading columns, plus
2. a range constraint on the first column that has no equality constraint,

bound the part of the index that is read. Conditions on columns further right are still checked inside the index, which saves visits to the table, but they don’t shrink how much of the index is read.

Here is what that means for an index on (user_id, created_at, status):

“Can’t seek” is not quite “can’t use”. PostgreSQL may still read the entire index for a non-prefix predicate when it is much smaller than the table, and PostgreSQL 18 and MySQL 8.0.13+ can sometimes skip scan (below). But a full read of a 15 GB index is not what you built it for.

Order the columns: equality, sort, range

Most composite-index mistakes are column-order mistakes. A method that almost always works:

1. Take one query and label each column it uses. E if it is compared with = (or a short IN list), S if it is in ORDER BY, R if it is a range: <, >, BETWEEN, LIKE 'abc%', !=, a long IN list.
2. Build the index as all E columns (in any order among themselves), then the S columns in ORDER BY order and direction, then the R columns.

MongoDB documents this as the ESR guideline (Equality, Sort, Range). Nothing about it is specific to MongoDB: it falls straight out of how any B-tree is sorted.

Why the range goes last

Take “user 42’s large payments, newest first”:

SELECT * FROM transactions
WHERE user_id = 42 AND amount_paise >= 500000      -- ₹5,000 or more
ORDER BY created_at DESC
LIMIT 20;

Here user_id is E, created_at is S and amount_paise is R. Compare the two plausible orders:

• E, R, S: (user_id, amount_paise, created_at). The matching entries are contiguous, but inside that run they are sorted by amount. created_at is ordered only among payments with the exact same amount, so for practical purposes the dates come out shuffled. The database must fetch every matching row, sort them all, and only then return the first 20.
• E, S, R: (user_id, created_at, amount_paise). User 42’s entries come out newest first. The amount test is checked inside the index as each entry passes, failing entries are skipped without touching the table, and the scan stops after the 20th match.

Put numbers on it. User 42 has 4,812 transactions, of which 300 are ₹5,000 or more: 300 ÷ 4,812 ≈ 6.2%. With E, S, R, reading newest first you expect a match about every 16 entries, so 20 matches cost about 20 ÷ 0.062 ≈ 320 index entries (two or three leaf pages) plus 20 table fetches. With E, R, S you read only the 300 matching entries, but you must fetch all 300 rows from the table and sort them before the first one is returned. Fifteen times the table reads, to throw 280 rows away.

The exception, which MongoDB’s guide also calls out: if the range is very selective, put it before the sort. If the filter were “₹1 lakh or more” and matched three of user 42’s payments, E, R, S reads 3 entries and sorts 3 rows, while E, S, R walks back through the entire history to find them. Equality, sort, range is the default; a tiny range is the reason to break it.

“Most selective column first” is a myth

A popular rule says to lead with the column that has the most distinct values. For equality lookups it makes no difference: with WHERE user_id = 42 AND status = 'FAILED', indexes on (user_id, status) and (status, user_id) both descend straight to the same run of entries, of the same length. What matters is how selective the combination is. What actually decides the order among equality columns:

• Which other queries can reuse the prefix. (user_id, status) also serves “all of user 42”. (status, user_id) also serves “all PENDING payments”. Pick the prefix your other queries need.
• Ranges and sorts. They are positioned by the E, S, R method, whatever their cardinality.
• Skip scan. If anything, it favours a low-cardinality leading column, the opposite of the myth (see below).

The myth holds only for queries that filter on the leading column alone.

ORDER BY and LIMIT without a sort

An index can hand rows back already sorted, which removes the Sort step from the plan. It works when three conditions hold:

1. Every index column before the sort columns is fixed by an equality.
2. The ORDER BY columns appear in the index in the same order.
3. Their directions either all match the index or all are flipped.

B-tree leaves are linked in both directions, so a backward scan is cheap: (user_id, created_at) serves WHERE user_id = 42 ORDER BY created_at DESC with no DESC in the index definition at all. The direction of an equality column never matters, because it holds one value.

Mixed directions are where you need DESC in the definition. A fantasy-cricket contest leaderboard sorts by points, highest first, and breaks ties in favour of whoever joined earlier:

SELECT team_name, points
FROM contest_entries
WHERE contest_id = 9001
ORDER BY points DESC, joined_at ASC
LIMIT 50;

-- A plain (contest_id, points, joined_at) index can't produce DESC, ASC.
CREATE INDEX contest_leaderboard ON contest_entries (contest_id, points DESC, joined_at);

Scanning a plain index forward gives ASC, ASC and backward gives DESC, DESC; neither is DESC, ASC. Two engine details: PostgreSQL also orders NULLs (default ASC NULLS LAST, so a backward scan yields DESC NULLS FIRST), and a query asking for DESC NULLS LAST on a nullable column needs an index declared that way. MySQL accepted DESC in index definitions for years but ignored it; only since 8.0 does it store descending key parts, which is what makes mixed-direction indexes work there.

The payoff is biggest with LIMIT. An explicit sort must process all matching rows to find the first n, while an index in the right order returns the first n and stops: for user 42’s passbook, 4,812 rows sorted versus 20 read. The same property makes keyset pagination work; add a unique tie-breaker such as id as the last sort column. InnoDB already appends the primary key to every secondary index, so there (user_id, created_at) is really (user_id, created_at, id).

When an index provides only a prefix of the requested order, PostgreSQL can use an Incremental Sort, sorting each group of equal prefix values separately: cheaper than a full sort, and a LIMIT can still stop early.

Covering indexes and index-only scans

An ordinary index scan has two halves: find the entry, then follow its pointer to the table for the rest of the row (a heap page in PostgreSQL, a second descent into the clustered index in InnoDB). Matching rows are usually spread all over the table, so the second half costs about one random page read per row, and it usually dominates.

If every column the query needs is in the index, the second half disappears. PostgreSQL calls this an index-only scan; MySQL’s EXPLAIN shows “Using index”. An index built to make that possible is a covering index.

• PostgreSQL added the INCLUDE clause in version 11: CREATE INDEX … ON transactions (user_id, created_at, status) INCLUDE (amount_paise). Included columns are payload: stored in leaf entries only, not part of the search key or of a UNIQUE constraint, and they need not be a type the B-tree can compare.
• InnoDB has no INCLUDE, but every secondary index entry already carries the primary-key columns. So SELECT id, created_at FROM transactions WHERE user_id = 42 is covered by (user_id, created_at) with nothing extra. To cover more, append columns to the key itself, at the end, where they don’t disturb the prefix.

PostgreSQL has one more hurdle. Index entries don’t record which transactions can see them, so before returning an entry the scan checks the table’s visibility map, one bit per heap page meaning “every row on this page is visible to everyone”. If the bit is set, no heap visit is needed. If not, the scan reads the heap page after all, and EXPLAIN ANALYZE counts it under Heap Fetches. VACUUM sets those bits, so index-only scans shine on data that changes slowly; index scan vs full table scan looks at what happens on busy tables.

Covering has a price. Every included column makes every entry wider, so fewer fit on a page and more memory is needed to keep the index cached. And in PostgreSQL, a column that appears anywhere in an index, payload included, disqualifies updates to it from the cheap HOT path (indexes in practice explains why). Include small, rarely updated columns that a hot query needs; never a free-text note.

Worked example: five queries, two indexes

Here are the five hottest queries on transactions:

-- Q1 Passbook: the screen every app open shows
SELECT * FROM transactions WHERE user_id = $1
ORDER BY created_at DESC LIMIT 20;

-- Q2 "Failed payments" tab
SELECT * FROM transactions WHERE user_id = $1 AND status = 'FAILED'
ORDER BY created_at DESC LIMIT 20;

-- Q3 Monthly statement
SELECT * FROM transactions
WHERE user_id = $1 AND created_at >= $2 AND created_at < $3
ORDER BY created_at;

-- Q4 Spend summary for a month, by status
SELECT status, sum(amount_paise) FROM transactions
WHERE user_id = $1 AND created_at >= $2 AND created_at < $3
GROUP BY status;

-- Q5 Reconciliation job: payments stuck in PENDING
SELECT id FROM transactions
WHERE status = 'PENDING' AND created_at < now() - interval '10 minutes'
ORDER BY created_at LIMIT 500;

Step 1: the ideal index for each query, by equality, sort, range.

Step 2: merge shared prefixes. Q1, Q3 and Q4 all start (user_id, created_at). Append status as a third key column and amount_paise as payload, and that one index serves Q4 as an index-only scan as well.

Step 3: decide whether Q2 deserves its own index. With the merged index, Q2 seeks to user 42, walks newest first, and checks status inside the index. If about 2% of payments fail, finding 20 failures means reading about 20 ÷ 0.02 = 1,000 entries. Each entry is about 44 bytes (8 each for user_id, created_at, a short status and amount_paise, an 8-byte tuple header and a 4-byte line pointer), so a page holds 8,192 ÷ 44 ≈ 186, and about 167 at the default 90% fill. A thousand entries is six leaf pages plus the 20 table rows: well under a millisecond from cache. A dedicated (user_id, status, created_at) would read one leaf page instead, but it is another B-tree of about 20 GB (500 million entries of roughly 36 bytes, at 90% fill) to update on every insert. Fold Q2 in.

Step 4: Q5 needs a different leading column, so it gets its own index. (Because it only ever wants PENDING rows, a partial index is even smaller; see indexes in practice.)

CREATE INDEX tx_user_time ON transactions (user_id, created_at, status)
  INCLUDE (amount_paise);
CREATE INDEX tx_status_time ON transactions (status, created_at);

Two indexes plus the primary key, instead of five or six. Here is Q1 before, when the only helpful index was a single-column tx_user_idx (user_id):

-- PostgreSQL 18, EXPLAIN ANALYZE, before (some lines trimmed)
Limit  (cost=17862.40..17862.45 rows=20 width=118) (actual time=48.912..48.917 rows=20.00 loops=1)
  Buffers: shared hit=1245 read=3561
  ->  Sort  (cost=17862.40..17874.43 rows=4812 width=118) (actual time=48.910..48.913 rows=20.00 loops=1)
        Sort Key: created_at DESC
        Sort Method: top-N heapsort  Memory: 30kB
        ->  Bitmap Heap Scan on transactions  (cost=57.86..17734.36 rows=4812 width=118) (actual time=1.204..47.633 rows=4812.00 loops=1)
              Recheck Cond: (user_id = 42)
              Heap Blocks: exact=4789
              ->  Bitmap Index Scan on tx_user_idx  (cost=0.00..56.66 rows=4812 width=0) (actual time=0.611..0.611 rows=4812.00 loops=1)
                    Index Cond: (user_id = 42)
                    Index Searches: 1

To show 20 rows it read all 4,812 of user 42’s rows from 4,789 different heap pages (three years of payments, interleaved with everyone else’s), then sorted them. After:

-- after: tx_user_time
Limit  (cost=0.70..80.95 rows=20 width=118) (actual time=0.034..0.102 rows=20.00 loops=1)
  Buffers: shared hit=21 read=3
  ->  Index Scan Backward using tx_user_time on transactions  (cost=0.70..19310.62 rows=4812 width=118) (actual time=0.033..0.098 rows=20.00 loops=1)
        Index Cond: (user_id = 42)
        Index Searches: 1
        Buffers: shared hit=21 read=3

No Sort node, and 24 buffers: four index pages (three levels above the leaf for 500 million entries, plus one leaf) and one heap page per returned row. That is 4,806 ÷ 24 ≈ 200× fewer pages, and the cost no longer grows with the user’s history. Q2 runs as the same Index Scan Backward with Index Cond: ((user_id = 42) AND (status = 'FAILED'::text)): the status test sits in the index condition, checked entry by entry rather than bounding the scan. Q4 never touches the table:

HashAggregate  (cost=21.07..21.11 rows=4 width=40) (actual time=0.082..0.084 rows=3.00 loops=1)
  Group Key: status
  ->  Index Only Scan using tx_user_time on transactions  (cost=0.70..19.32 rows=233 width=16) (actual time=0.019..0.051 rows=241.00 loops=1)
        Index Cond: ((user_id = 42) AND (created_at >= '2026-09-01 00:00:00+05:30'::timestamp with time zone) AND (created_at < '2026-10-01 00:00:00+05:30'::timestamp with time zone))
        Heap Fetches: 0
        Index Searches: 1
        Buffers: shared hit=6

Skip scan: when the missing prefix is cheap

The ops team now wants a per-minute count of all payments, whatever their status:

SELECT count(*) FROM transactions
WHERE created_at >= '2026-10-26 09:00+05:30'
  AND created_at <  '2026-10-26 09:01+05:30';

tx_status_time (status, created_at) has the right column in second place, but status is not constrained, so there is no prefix to seek on. Before PostgreSQL 18 your choices were reading the whole index or the whole table. Do the arithmetic: an entry in this index is about 28 bytes (a short status padded to 8, an 8-byte timestamp, the 8-byte header and the 4-byte pointer), so about 263 fit on a page at 90% fill, and 500 million ÷ 263 ≈ 1.9 million leaf pages, about 15 GB.

But status has only four values. Skip scan treats the missing leading column as if the query had said status = 'FAILED' OR status = 'PENDING' OR … for every value present: descend once per distinct status, read that group’s 09:00–09:01 slice, then jump to the next group. PostgreSQL 18 added it for B-trees; EXPLAIN ANALYZE now reports how many descents a scan made:

-- PostgreSQL 18
Aggregate  (cost=3401.38..3401.39 rows=1 width=8) (actual time=17.903..17.904 rows=1.00 loops=1)
  ->  Index Only Scan using tx_status_time on transactions  (cost=0.57..3176.22 rows=90064 width=0) (actual time=0.038..12.716 rows=89412.00 loops=1)
        Index Cond: ((created_at >= '2026-10-26 09:00:00+05:30'::timestamp with time zone) AND (created_at < '2026-10-26 09:01:00+05:30'::timestamp with time zone))
        Heap Fetches: 0
        Index Searches: 4
        Buffers: shared hit=356

Four searches and 356 buffers: 89,412 ÷ 263 ≈ 340 leaf pages plus the upper levels on each descent. That is roughly 5,300× fewer pages than reading the whole index.

MySQL has had skip scan since 8.0.13, shown in EXPLAIN as “Using index for skip scan”, with tighter conditions: a single-table query, no GROUP BY or DISTINCT, only columns that are in the index, equality (if any) on the columns before the skipped ones, and a range on the column after them. The count above qualifies:

mysql> EXPLAIN SELECT COUNT(*) FROM transactions
    ->  WHERE created_at >= '2026-10-26 09:00:00' AND created_at < '2026-10-26 09:01:00'\G
           type: range
            key: tx_status_time
           rows: 88140
          Extra: Using where; Using index for skip scan

Now try it on the wrong index. The same query against tx_user_time would need one descent per distinct user_id, about 50 million of them, which is far worse than a sequential scan; the planner won’t choose it. Skip scan is a safety net that lets an existing index serve an occasional query. It is not a reason to put a low-cardinality column first, and not a substitute for the right index on a hot path.

Redundant indexes and the cost of width

Overlapping indexes creep in one migration at a time. The rules for spotting them follow from the prefix rule:

• (a) is redundant with (a, b). The composite serves every query the single-column index does. Keep the narrow one only if it backs a UNIQUE constraint, or a very hot query measurably benefits from its smaller size.
• (a, b) and (b, a) are not redundant. They offer different prefixes. Keep both only if both prefixes are queried.
• (a, b) is redundant with (a, b) INCLUDE (c) or (a, b, c), for lookups and ordering alike.
• In InnoDB, (a, id) is (a) when id is the primary key, because the key is appended anyway.
• Separate (a) and (b) are not a composite. PostgreSQL can combine them with a bitmap AND and MySQL with an index merge, but that is slower than one (a, b) and never returns rows in order.

The other side of the ledger is cost. Every index is another B-tree to update on every insert, and on every update that touches one of its columns; on a write-heavy table that is often what scaling writes starts with. Wider entries mean fewer per page, so the index is bigger and needs more memory to stay cached. On 500 million rows, every extra 8-byte column adds 500 million × 8 bytes ≈ 4 GB of leaf data before fill-factor slack. PostgreSQL’s documentation is blunt: indexes with more than three columns are unlikely to help unless the workload is extremely stylised. Finding and dropping unused and duplicate indexes safely is covered in indexes in practice.

PostgreSQL vs MySQL

Cheat sheet

How to say it in the interview

“A composite index is sorted by its first column, then the second within ties, so it can only seek on a leftmost prefix. I order the columns equality first, then the ORDER BY column, then ranges, because a range on a middle column scrambles everything after it. For the payments table, the passbook, statement and spend-summary queries all start with user_id and created_at, so one index on user_id, created_at, status, with the amount included, serves all of them: the passbook reads 20 entries with no sort, and the summary is index-only. The reconciliation job leads with status, so it gets a second index. Two indexes, because every index costs us on every insert.”

Does (a, b) help a query on b alone? It can’t seek, because b is sorted only within each value of a. It may still be scanned in full if it is much smaller than the table, and on PostgreSQL 18 or MySQL 8.0.13+ a skip scan works if a has few distinct values. For a hot query on b, add an index that leads with b.

Should the most selective column go first? Not as a rule. For equality lookups both orders reach the same run of entries. Order equality columns so other queries can reuse the prefix, then follow equality, sort, range.

When would you break equality, sort, range? When the range is very selective. If it matches a handful of rows, putting it before the sort column reads only those rows, and sorting a handful is free.

What makes an index-only scan fall back to reading the table? In PostgreSQL, heap pages that aren’t marked all-visible: recently inserted or updated rows, or a table VACUUM hasn’t processed. Heap Fetches in EXPLAIN ANALYZE shows how often it happened.

Where to go next

• Database indexes: B+tree structure, clustered vs heap tables, and the write cost of every index.
• Index scan vs full table scan: why the planner sometimes ignores a perfectly good index.
• Indexes in practice: partial and expression indexes, building indexes on live tables, pruning unused ones.
• Query execution plans: reading every line of the plans shown above.
• Offset vs keyset pagination: the seek method that depends on an index matching your ORDER BY.
• MVCC and vacuum and bloat: where the visibility map and heap fetches come from.
• PostgreSQL vs MySQL: the storage-engine differences behind the comparison table.

References and further reading

1. PostgreSQL documentation: Multicolumn Indexespostgresql.orgThe exact rule for which constraints bound a B-tree scan, how skip scan repositions the scan, and the advice that more than three columns rarely helps.
2. PostgreSQL documentation: Indexes and ORDER BYpostgresql.orgBackward scans, ASC/DESC and NULLS options, why mixed-direction sorts need a matching index, and why LIMIT makes an ordered index so valuable.
3. PostgreSQL documentation: Index-Only Scans and Covering Indexespostgresql.orgThe two requirements for index-only scans, the visibility-map check, INCLUDE payload columns and suffix truncation.
4. PostgreSQL 11 release notespostgresql.orgThe release that added the INCLUDE clause for covering B-tree indexes.
5. PostgreSQL 18 release notespostgresql.orgB-tree skip scan, and the per-node count of index searches in EXPLAIN ANALYZE.
6. MySQL 8.0 Reference Manual: Multiple-Column Indexesdev.mysql.comThe leftmost-prefix rule with examples, the 16-column limit and the “sorted array of concatenated values” model.
7. MySQL 8.0 Reference Manual: Range Optimization (Skip Scan Range Access Method)dev.mysql.comSkip scan since 8.0.13, the conditions it needs, and the “Using index for skip scan” EXPLAIN marker.
8. MySQL 8.0 Reference Manual: Descending Indexesdev.mysql.comDESC key parts stored in descending order, and mixed ASC/DESC indexes for mixed-direction ORDER BY.
9. MySQL 8.0 Reference Manual: Use of Index Extensionsdev.mysql.comInnoDB appends the primary-key columns to every secondary index, and the optimizer uses them for lookups and sorting.
10. MongoDB Manual: The ESR (Equality, Sort, Range) Guidelinemongodb.comEquality fields first, sort before range to avoid an in-memory sort, and the exception for very selective ranges.