Part 4 — Fast at scale › Chapter 26

Index design: order, covering, selectivity

Why (a, b) is not (b, a), what INCLUDE is for, and the real cost of the index nobody uses.

From the advert

“Ottimizzazione e tuning delle query” — adding an index is easy. Knowing which one, in which column order, and which existing three to delete, is the job.

Column order is the whole game

The rule is mechanical: read the index columns left to right and stop at the first one your query does not filter on.

🧒 Simple

A phone book is sorted by surname, then first name. Finding “Rossi, Marco” is easy. Finding everyone called Marco is not — you have to read the whole book, because first names are scattered all through it. The order you sorted by decides which questions are cheap.

🎓 The leftmost-prefix rule

An index on (a, b, c) can seek on a, on (a, b), and on (a, b, c). It cannot seek on b alone, or on (b, c), because those values are not sorted independently — they are only sorted within a value of a.

So an index on (customer_id, placed_at) serves “this customer's orders” and “this customer's recent orders”. An index on (placed_at, customer_id) serves “orders in March” — and serves “this customer's orders” not at all.

Query	Index (a, b, c) can…
`WHERE a = 1`	✅ seek
`WHERE a = 1 AND b = 2`	✅ seek on both
`WHERE a = 1 AND c = 3`	✅ seek on a, then filter c inside the range
`WHERE b = 2`	❌ scan
`WHERE a > 1 AND b = 2`	⚠ seek the range on a; b cannot narrow it further
`ORDER BY a, b`	✅ no sort needed
`ORDER BY b`	❌ sort required

⚠ Trap — a range column stops the index dead

In row 5 above, once you use an inequality on a the entries are no longer grouped by b, so b can only filter rows already read, not narrow the seek. Hence the ordering rule: equality columns first, then the range column, then anything only needed for sorting or covering. This one sentence is the answer to most “design an index for this query” questions.

Column order: equality first, then the range or the sort. One sentence answers most index-design questions.

-- For: SELECT ... WHERE status = 'shipped' AND placed_at >= ? ORDER BY placed_at
CREATE INDEX ix ON orders (status, placed_at);   -- equality column first, range column second
--                          ^equality  ^range and sort. This order, not the other one.

-- Reverse it and the seek becomes a scan of every row in the date range, shipped or not.

Why equality has to come first

An index is sorted by its first column, then within that by its second. With (status, placed_at) all the shipped rows sit together and are ordered by date, so the engine seeks once and reads a contiguous run — which also satisfies the ORDER BY for free.
With (placed_at, status) the rows in the date range are contiguous, but shipped and unshipped are interleaved throughout it. The engine must read all of them and discard most.
The rule generalises: equality predicates first, then one range or sort column. Columns after a range column cannot narrow the seek — they only avoid a lookup.

Covering indexes

🎓 An index that answers the query by itself

If every column a query touches — in SELECT, WHERE, JOIN, ORDER BY — is in the index, the engine never reads the table at all. No key lookup, no random reads. In a plan this shows as an index-only scan (PostgreSQL) or an index seek with no key lookup beside it (SQL Server), and it is often a 10–100× improvement on a wide table.

INCLUDE: payload columns that remove the lookup without widening the key.

-- SQL Server: INCLUDE puts columns in the LEAF level only, not in the key.
CREATE INDEX ix_orders_status_cov        -- name it after what it serves
  ON orders (status, placed_at)          -- KEY: used for seeking, ordering, and the tree
  INCLUDE (customer_id, total_cents);    -- PAYLOAD: available without going to the table

-- PostgreSQL 11+ has the same thing:
CREATE INDEX ix ON orders (status, placed_at)  -- the same key…
  INCLUDE (customer_id, total_cents);    -- identical meaning, identical trade

-- MySQL has no INCLUDE: extra columns must go in the key, and pay for it there.

Key versus payload, and why the distinction earns its keep

Key columns are stored at every level of the B-tree and define the ordering. Adding a wide column to the key makes the whole tree taller and every seek slower.
INCLUDE columns exist only in the leaf pages, so they cost leaf space and nothing else. They cannot be seeked on or sorted by — that is the trade.
Making an index covering is often a 10–100× improvement on a wide table, because it removes one random read per matching row.
In MySQL/InnoDB every secondary index already carries the primary key, and a covering index is built by putting the extra columns in the key. Same idea, more cost.

⚠ Trap — the covering index that covers everything

It is tempting to INCLUDE every column so all queries are covered. That reproduces the table inside the index: every insert writes twice, every update of an included column updates two structures, and your buffer pool now holds two copies of the same data. Cover the columns your hot queries need, not all of them.

Selectivity: which column is worth indexing

Selectivity is the fraction of rows a predicate eliminates. An index on a column with two distinct values across a million rows cannot help a lookup — reading half the table through an index is worse than scanning it.

✔ Except when it is skewed, which is the interesting case

A status column that is 99% 'delivered' and 1% 'failed' is useless for finding delivered orders and excellent for finding failed ones. Which is exactly what a partial (filtered) index expresses:

Partial indexes: index the 1% of rows anybody actually queries for.

CREATE INDEX ix_orders_failed ON orders (placed_at)   -- the column queries sort and filter on…
  WHERE status = 'failed';                            -- …over only the rows that are failed
-- 1% of the size, seeks straight to the rows anyone queries for, and a row LEAVES
-- the index entirely when it stops being failed.

-- The reference database uses the same idea for the outbox worker:
CREATE INDEX ix_outbox_pending ON outbox (created_at) -- oldest-first claiming…
  WHERE published_at IS NULL;                         -- …over unpublished rows only
-- The index stays tiny however large the outbox table grows.

Why this is the right shape for a queue

A queue table is mostly finished work. A full index on created_at grows forever; a partial index contains only the rows still to do, so it stays the size of the backlog.
Rows are removed from the index when they no longer match the predicate. Publishing a message deletes an index entry rather than updating one — that is why the worker's claim query stays fast at ten million historical rows.
The query's WHERE must imply the index's predicate, or the index cannot be used. WHERE published_at IS NULL AND created_at < ? qualifies; a query without the IS NULL does not.
PostgreSQL calls it a partial index, SQL Server a filtered index. MySQL and SQLite have neither.

PostgreSQL calls them partial indexes, SQL Server calls them filtered indexes, Oracle achieves the same with a function-based index that returns NULL for uninteresting rows. MySQL has no equivalent.

What an index costs

🎓 The four costs, and the one people forget

Write amplification. An insert into a table with six indexes is seven writes. An update touching two indexed columns updates those two indexes as well.
Space, in the buffer pool as much as on disk — every unused index is evicting pages something else wanted.
Maintenance: statistics, rebuilds, backups all get bigger.
Optimiser choice. More indexes means a larger plan search space and more opportunities to pick a wrong one. This is the cost nobody mentions and it is real.

Finding the indexes you are paying for and not using.

-- SQL Server: indexes that are written to and never read.
SELECT OBJECT_NAME(s.object_id) AS tbl,           -- id → readable table name
       i.name,                                    -- the index name
       s.user_seeks, s.user_scans, s.user_lookups,-- the three ways it could be USED…
       s.user_updates                             -- …and how often writers maintained it
FROM sys.dm_db_index_usage_stats s                -- usage since the last restart
JOIN sys.indexes i ON i.object_id = s.object_id   -- join to get the name…
                  AND i.index_id  = s.index_id    -- …matching on both key columns
WHERE s.database_id = DB_ID()                     -- this database only
  AND s.user_seeks + s.user_scans + s.user_lookups = 0   -- never read…
ORDER BY s.user_updates DESC;                     -- …most expensively maintained first

-- PostgreSQL: the same question, one view.
SELECT relname, indexrelname, idx_scan,                        -- table, index, times used
       pg_size_pretty(pg_relation_size(indexrelid))            -- and how much disk it costs
FROM pg_stat_user_indexes WHERE idx_scan = 0                   -- never scanned…
ORDER BY pg_relation_size(indexrelid) DESC;                    -- …largest first

How to read the result, and one warning

An index with zero reads and many writes is pure cost: disk, write amplification, longer maintenance windows, and one more plan for the optimiser to get wrong.
The counters reset on restart (SQL Server) or on pg_stat_reset() (PostgreSQL). An index that only serves the quarterly report will look unused for eleven weeks — check the uptime before you drop anything.
Never drop the index behind a unique or primary key constraint: it is the constraint. The query above will happily list it if nobody queries that column.
Disable before dropping where the engine supports it, so restoring is one statement rather than a schema archaeology exercise.

⚠ Trap — the stats reset on restart

Those counters are cumulative since the last service restart (or since pg_stat_reset()). An index used only by the quarterly report looks unused in January. Check the uptime before you drop anything, and prefer disabling to dropping so you can put it back in one statement.

An index on (a, b, c) serves any leftmost prefix, and nothing else.
Equality columns first, then the range column, then columns needed only for sorting or covering.
Once you use an inequality on a column, later columns can only filter, not narrow the seek.
A covering index removes the lookup entirely and is often the single biggest win available.
INCLUDE adds leaf-level payload without affecting seekability or key width.
Do not cover everything — that is a second copy of the table, written on every insert.
Low selectivity kills an index, unless the distribution is skewed — then use a partial index.
Every index costs writes, space, buffer pool and optimiser search space.
Usage statistics reset on restart. Check uptime before dropping an index nobody appears to use.

Interview questions this chapter answers

Design an index for WHERE status = ? AND placed_at >= ? ORDER BY placed_at.

(status, placed_at): equality first so it can seek, then the range column — which also supplies the ORDER BY, so there is no sort. If the select list is small I would INCLUDE those columns to make it covering.

Why is (a, b) not the same as (b, a)?

An index is sorted left to right, so b is only ordered within a given a. A predicate on b alone therefore cannot seek. Only leftmost prefixes are seekable.

Can you have too many indexes?

Yes. Every one is written on insert and on updates to its columns, occupies buffer pool, enlarges backups, and adds to the optimiser's search space. I would look at the usage statistics for indexes with zero seeks and a high update count — checking server uptime first, because those counters reset.