Indexing

Why does the thing that makes reading fast make writing slow?

A query takes four seconds. Someone adds an index. The query takes four milliseconds. It is a thousandfold improvement for one line of configuration, and the obvious next thought is: why not index everything?

Then the inserts get slower. Not dramatically at first, and not because anything is broken. Adding a lookup structure clearly should not affect writing a row — the row goes where it always went. So the slowdown must be coming from somewhere the question has not yet accounted for.

Start with why the read got fast, because the answer contains the whole trade.

Without an index, finding rows where the city is Bristol means examining every row — a full scan, work proportional to the size of the table. An index makes that fast by keeping a second structure in which the rows are already ordered by city, with each entry pointing back to the row itself. Now finding Bristol is a descent through a sorted structure: a handful of steps regardless of table size.

Hold on to the crucial word: ordered. The speed does not come from the index being small or clever. It comes from it being sorted, because sorting is what lets you discard most of the search space at every step. In practice this is a B-tree, a shallow, wide, balanced tree whose height grows only logarithmically — a few levels covering millions of rows.

Now ask what a new row does to that. The table itself does not care: append it wherever there is space. But the index cares intensely, because a sorted structure with a new value inserted at the end is no longer sorted. The entry must go in its correct position, which means locating that position and making room for it. If the page it belongs in is full, the page must be split, and the split may propagate upward through the tree.

So the write did not slow down because the index is large. It slowed down because order is a property that must be maintained, and every insertion is an obligation to maintain it. And the obligation is per index: one row into a table with five indexes is one table write plus five ordered insertions, each potentially touching several pages, each of which must itself be logged for durability. This is write amplification — the physical work done far exceeds the logical work requested.

Notice something the naive picture also misses. An update to an indexed column is not one write but a delete and an insert in that index, since the entry's position is determined by the value that changed. Update a rarely-indexed column and the indexes are untouched; update an indexed one and every index on it must be restructured.

There is a further cost that is easy to overlook and often the one that bites: memory. Indexes compete with data for cache. Ten indexes the query planner never chooses still occupy pages that could have held rows, so they degrade unrelated queries by evicting useful data. An unused index is not free; it is quietly negative.

Is the trade avoidable? Not eliminable, but it can be reshaped, and this is worth being accurate about rather than hand-waving. Log-structured merge trees — used by many modern stores — do not maintain global order on every write. They buffer writes in memory, flush them as sorted runs, and merge those runs in the background. That converts many small random writes into fewer large sequential ones, which suits solid-state storage well, but the merging work does not vanish; it is deferred and batched, and it can surface later as read amplification and compaction load. Different shape, same underlying obligation.

Two refinements sharpen the model.

First, an index is not automatically used. The query planner chooses it based on statistics, and if it estimates that a large fraction of the table matches, a full scan is genuinely cheaper — following thousands of pointers back to scattered rows costs more than reading everything in order. This surprises people: an index on a column with few distinct values, like a boolean flag, is often ignored, because it cannot discard enough of the search space to justify the indirection.

Second, order is directional and composite indexes inherit that. An index on (city, surname) accelerates a search on city, and on city with surname — but generally not on surname alone, because within the structure surnames are only sorted inside each city. The sorted prefix is what you can use. This is why the number of useful indexes is smaller than the number of columns, and why choosing them is a design act rather than a checklist.

So the answer to "why not index everything" is not merely that writes get slower. It is that most of those indexes would never be chosen, and would still cost every insert, every update, and every page of cache.

• How the query planner uses statistics to decide between an index and a scan, and when its estimates go wrong.
• Covering indexes, which answer a query from the index alone without visiting the row.
• LSM trees versus B-trees, and how deferring order changes the shape of the cost.

Every term the collection defines is gathered in the glossary.