Indexing

A sorted copy of one column, so a lookup reads a handful of pages instead of the whole table. Every index makes one read cheaper and every write dearer.

Each index you add speeds up the queries that use it and slows down every insert and update that has to maintain it.

B-treecovering indexwrite amplificationselectivity

Try it

Move the dials — the sentence under the picture changes.

Indexes on the table1

Rows a query matches1,000 of 1M

Reads in the mix90%

A read is 1,003 pages instead of 10,000; a write is 4 instead of 1. At 90% reads the blended cost is 903 pages per operation.

The trade

A table is stored in whatever order rows arrived. To find every order for one customer, the database reads every row and keeps the ones that match — a full scan, proportional to the table, and the reason a query that took a millisecond in development takes a minute in production.

An index is a second structure, kept sorted by one or more columns, with a pointer from each entry back to its row. Finding a customer's orders in a B-tree index (a wide, shallow sorted tree, one disk page per level) over customer_id is a walk down a tree a few levels deep: three or four page reads, whatever the table's size. That is the whole trick, and it is enormous.

The price is paid on every write. Inserting a row means inserting into every index on the table too; updating an indexed column means deleting and re-inserting its entry. Five indexes make a write roughly six times the I/O of an unindexed one, and the B-tree pages they touch are scattered, not sequential. The widget shows the two curves crossing: reads fall to nothing, writes climb, and where you sit on it depends on your read-to-write ratio.

Which column

An index earns its keep when it is selective: the query's condition matches a small fraction of rows. WHERE customer_id = 42 matches a few dozen rows out of millions — a superb index. WHERE status = 'active' matches half the table — the database will ignore the index and scan, because reading half the rows through pointer chasing is slower than reading all of them in order.

Composite indexes follow the leftmost-prefix rule. An index on (customer_id, created_at) serves WHERE customer_id = ? and WHERE customer_id = ? AND created_at > ?, but not WHERE created_at > ? alone: the tree is sorted by customer first, so dates from every customer are interleaved.

Index the columns in your WHERE and JOIN clauses, in the order of most selective first — and then look at the query plan — the database's own description of how it will run the query — because the planner's opinion is the one that counts.

Covering indexes

A lookup through an index is two steps: find the entry, then follow its pointer to the row for the columns you actually wanted. If the index itself contains every column the query needs — (customer_id, created_at, total) for a query that selects only those — the second step vanishes. The query is served from the index alone, which is why it is called covering, and why wide indexes are sometimes worth their write cost.

Where it goes wrong

Indexes nobody uses. They cost every write and speed up nothing. Most databases can report index usage; drop what is not read.
Low-cardinality indexes (few distinct values). An index on a boolean is two enormous lists; the planner will not touch it.
Functions on the column. WHERE lower(email) = ? cannot use an index on email. Index the expression, or store it lowercased.
Write-heavy tables. An event log with six indexes is an event log that cannot keep up. Fewer indexes, or a separate read replica that carries them.

Take this with you

The one idea: an index trades a little on every write for a lot on the reads it matches. Where that trade pays depends on your read-to-write ratio.
In an interview, say which columns you would index and why (selective, in the WHERE/JOIN), and mention the leftmost-prefix rule.
At work, run EXPLAIN on your slowest query before adding anything, and drop the indexes your database reports as never used.