Three queries hit the same table with different filters. What composite indexes do you build, and how do you order the columns?

The rule is about predicate shape

Take three queries against a shipment table:

-- (1)
SELECT * FROM shipment WHERE tenant_id = $1 AND status = 'IN_TRANSIT';
-- (2)
SELECT * FROM shipment WHERE tenant_id = $1 AND dispatched_at >= $2
ORDER BY dispatched_at DESC LIMIT 50;
-- (3)
SELECT * FROM shipment WHERE tenant_id = $1 AND status = 'IN_TRANSIT'
  AND dispatched_at >= $2;

A B-tree index is a sorted structure over the concatenation of its columns, and that single fact generates the whole rule. Entries are ordered by the first column, then within equal values of the first by the second, and so on. So a lookup can seek to a contiguous range of the index only while each column is pinned to a single value; the first column constrained by a range makes everything after it non-contiguous, because within the range the later columns run through their whole ordering repeatedly.

That gives the ordering: equality predicates first, then at most one range predicate, then columns needed only for ordering or for covering. For query (3) the index is (tenant_id, status, dispatched_at). Reversing the last two to (tenant_id, dispatched_at, status) still uses the index, which is why this mistake is hard to spot, but status can no longer bound the seek. It becomes a filter applied to every entry in the date range, so you read far more index entries than you return. In a PostgreSQL plan that shows as a large gap between Rows Removed by Filter and the returned row count, and in the Index Cond versus Filter lines — anything that appears under Filter is a column the index did not use to narrow the search.

What the leftmost prefix buys you

An index on (tenant_id, status, dispatched_at) also serves any query whose predicates cover a leftmost prefix: tenant_id alone, and tenant_id with status. It does not usefully serve status alone, because the entries for a given status are scattered across every tenant's section of the index. This is why you should not create one index per query. For the three queries above, (tenant_id, status, dispatched_at) handles (1) and (3) outright, and a second index (tenant_id, dispatched_at) handles (2) — which also gives you the sort for free, since the index already delivers rows in that order and the LIMIT 50 can stop after fifty entries instead of sorting the whole range.

Sorting is the part people forget the index can do. ORDER BY dispatched_at DESC is satisfiable from (tenant_id, dispatched_at) because PostgreSQL can walk a B-tree backwards, and an equality on the leading column means the scan is already within one contiguous ordered run. Mixed directions are where it breaks: ORDER BY status ASC, dispatched_at DESC needs an index declared with those directions, (status ASC, dispatched_at DESC), or the engine sorts. MySQL only gained genuine descending indexes in 8.0 — before that DESC in an index definition was parsed and ignored — so a claim about index-satisfied sorting there carries a version.

Covering, and what index-only actually requires

If the index contains every column the query touches, the engine can answer from the index without visiting the table at all. In PostgreSQL that is an Index Only Scan, and INCLUDE exists for exactly this: payload columns stored in the leaf pages, not part of the ordered key, so they add no seek capability and no ordering obligation.

-- reference is returned but never filtered or sorted on, so it belongs
-- in INCLUDE rather than as a fourth key column.
CREATE INDEX shipment_tenant_status_dispatched
  ON shipment (tenant_id, status, dispatched_at)
  INCLUDE (reference);

The caveat that separates a read answer from an operating one: PostgreSQL's index-only scan still consults the visibility map, because the index does not record which row versions are visible to your snapshot. Pages that are not marked all-visible force a heap fetch anyway, so an index-only scan on a heavily updated table degrades until autovacuum catches up. The plan tells you — Heap Fetches on the Index Only Scan node — and a non-zero value there is the number worth watching.

InnoDB works differently and the difference changes the advice. The table is the primary-key B-tree, and every secondary index implicitly stores the primary key as its row locator. So the primary key is always effectively included, INCLUDE does not exist, and a secondary-index lookup that needs other columns performs a second descent through the clustered index for each row. That makes covering indexes disproportionately valuable in InnoDB and it makes a wide primary key expensive twice over, since it is copied into every secondary index. A random UUID primary key in InnoDB is the classic version of this mistake: it inflates every index and randomises insert position in the clustered index.

The rule that gets recited instead

"Put the most selective column first" is the answer most candidates give, and it is not the rule. Selectivity does not decide order; predicate shape does. Where cardinality does matter is as a tiebreaker between two equality columns, and even there the stronger consideration is usually which prefix serves the most queries — putting tenant_id first in a multi-tenant schema is right even though it is the least selective column in the index, because every query has it and it makes the index prefix reusable.

The related myth is that a low-cardinality column is not worth indexing. It is worth indexing when the value you filter on is rare, which is a different property from cardinality: a boolean needs_review that is true for 2% of rows is highly selective for WHERE needs_review, and the right answer there is a partial index carrying only those rows.

-- Small, cheap to maintain, and only touched by the queries that want it.
CREATE INDEX shipment_review_queue ON shipment (tenant_id, dispatched_at)
  WHERE needs_review;

PostgreSQL calls these partial indexes; MySQL has no equivalent, and the nearest approach there is a generated column plus a functional index. A partial index also has to match the query's predicate for the planner to use it, so the WHERE clause in the index and in the query must be recognisably the same condition.

Pricing the index you are about to add

Every index is a second data structure that every INSERT maintains and every UPDATE to an indexed column maintains, plus space, plus a share of the buffer cache that is no longer holding table pages. On a write-heavy table this is the dominant cost and it is invisible in the query plan you were looking at.

So the discipline is to prune while you add. (tenant_id, status, dispatched_at) makes a separate index on (tenant_id) and one on (tenant_id, status) redundant, because both are prefixes of it — dropping those is free performance on the write path. Before dropping, check usage rather than reasoning about it: in PostgreSQL, idx_scan in pg_stat_user_indexes counts how often each index has actually been used since statistics were last reset, and a zero on a long-running production system is real evidence. Do check that the index is not enforcing a unique constraint first, which is the one case where a never-scanned index is still doing essential work.