Query plans and indexes in practice

Why did more indexes make lunch slower?

On the last day of the month the accountant runs the kitchen report: every partner kitchen’s orders for the last 30 days, newest first. Since the orders moved into PostgreSQL, the report takes 40 seconds per kitchen. There are 200 kitchens.

The first fix was the one everyone has heard of: put an index on every column, because indexes make databases fast. Nine of them went in one night.

The next day the report was still slow. And at 12:30 the order page was slower than it had been in weeks. Placing an order used to be instant; now riders were waiting for the confirmation.

The old paper ledger on the shelf shows what an index is for. It is written day by day, page after page. Down the side are coloured tabs, one per customer. The tabs are by customer and not by date, because people ask what one customer ordered. Nobody asks what happened on the fourteenth, and the pages are already in date order anyway. Each tab exists to answer a question people actually ask. The database now has nine tabs, one per column, and every new order has to be written in nine places.

Count before reading on: if each of the nine indexes costs one extra write per insert, how many writes does one order now make?

There are two problems here, and both come from the same missing knowledge. Nobody knows which index the database uses for the report, or why. And nobody knows what each index costs every time an order is written.

The database does not pick an index at random. Before it runs a query it makes a plan, and it will show you that plan if you ask.

Pause and predict The report asks for one kitchen’s orders from the last 30 days, newest first. Which single index serves it?

The planner decides

A SQL query says what you want, not how to find it. The query planner considers several ways to run it, estimates what each will cost, and picks the cheapest. Adding an index does not force its use. It only adds another option to the list.

The estimates come from statistics the database keeps about each column: how many distinct values there are, the most common values and how often they occur, and a histogram of the rest. PostgreSQL collects them with ANALYZE, which autovacuum runs for you as a table changes.

Selectivity

The share of rows a condition keeps. A selective condition keeps few rows; an unselective one keeps most of them.

For example: kitchen_id = 42 keeps 1 in 200 orders: selectivity 0.005. status = 'delivered' keeps 90% of them: selectivity 0.9.

For a single table there are four plans worth knowing. Lesson 2.1 showed the pieces: a table is a heap of 8 KB pages, and a B+tree index points from key values to row locations.

• Seq Scan. Read every page of the table in order and test each row. This plan is always possible, and it is the cheapest way to read a large share of a table.
• Index Scan. Walk the B+tree to the first matching key, read entries in key order, and fetch each row from the table. With few matches this is fast. With many matches it costs one random page read per row.
• Bitmap Heap Scan. Read the matching entries from the index first, build a map of which table pages hold matches, then read those pages once each, in physical order. It suits queries that match quite a few rows, but the rows come out in page order, not in key order.
• Index Only Scan. If the index holds every column the query needs, answer from the index and skip the table.

Pause and predict The report asks for every delivered order. status = 'delivered' keeps 90% of the rows, and there is an index on status. Which plan is cheaper?

A mental model

Reading the numbers

The report, five ways

The report for one kitchen keeps 730,000 × 1/200 × 30/365 = 300 rows. The table is 730,000 / 60 rows per page = 12,167 pages. Estimated costs are in PostgreSQL’s units, not milliseconds; what matters is the ratio.

The covering index costs about a thousandth of the sequential scan. The column-by-column indexes help, but each answers only part of the question.

Column order: equality first, then the range

PostgreSQL’s documentation gives the exact rule for a multicolumn B-tree: equality conditions on the leading columns, plus a range condition on the first column without an equality, limit the part of the index that is read. Conditions on columns further right are still checked inside the index, so they save visits to the table, but they do not shrink the scan.

• (kitchen_id, created_at): the equality on kitchen jumps to kitchen 42, and the range on created_at reads only its last 30 days. That is 300 entries, about 5 index pages. The entries are also in created_at order, so no sort is needed.
• (created_at, kitchen_id): the range on created_at comes first, so the scan reads every kitchen’s last 30 days, 60,000 entries and about 243 index pages, checking kitchen_id inside the index as it goes. The answer is correct, but the scan does about twenty times more index work.
• A query without a kitchen condition cannot use (kitchen_id, created_at) to narrow anything in our simulator. PostgreSQL 18 added skip scan, which can sometimes use such an index by trying each leading value in turn; it helps when the leading column has few distinct values.

Reading EXPLAIN ANALYZE

EXPLAIN prints the plan the planner chose, with its estimates. EXPLAIN ANALYZE also runs the query and prints what really happened. This is the shape of the output for the report with the covering index (the timings are illustrative):

Index Only Scan Backward using orders_kitchen_created_cov on orders (cost=0.42..21.50 rows=300 width=14) (actual time=0.028..0.214 rows=287 loops=1) Index Cond: ((kitchen_id = 42) AND (created_at >= (CURRENT_DATE - 30))) Heap Fetches: 0 Planning Time: 0.120 ms Execution Time: 0.251 ms

• cost=0.42..21.50: the estimated cost to the first row and to the last, in the planner’s units.
• rows=300 estimated against rows=287 actual: close, so the statistics are healthy.
• Backward: the index is read from the end, because the query wants newest first.
• Heap Fetches: 0: every page was marked all-visible, so the table was never touched.

What each index costs on the write path

Every insert writes the row once, and then one entry into every index on the table, each in its own B+tree page, each recorded in the write-ahead log (lesson 2.2). The nine indexes turned one write per order into ten. An update to an indexed column also has to update that index. This is why the order page slowed down while the report did not speed up.

One index for the question, or one per column?

The nine indexes have to go. What replaces them is a choice between two goals: flexibility for queries nobody has written yet, and the cheapest possible answer to the one query that runs.

The first path has a point: a status-only query, if it ever becomes common, gets nothing from the covering index. But nobody runs one today, and every index is paid for on every order. Index the queries that run today, and add an index later if a real, frequent query shows up in the slow-query log.

What to remember

1. The planner picks the cheapest estimated plan from statistics. An index gives the planner one more option; it does not force the planner to use it.
2. An index wins for selective conditions. When a condition keeps most rows, a sequential scan is cheaper, because in-order page reads are cheap and random ones are not.
3. Order composite index columns as equality first, then the range, then the sort. Columns after the range are checked in the index but do not narrow the scan.
4. A covering index holds every column a query needs, so an Index Only Scan can skip the table.
5. Every index costs extra work on every write. Read EXPLAIN ANALYZE, compare estimated and actual rows, and run ANALYZE when they disagree.

Index for the queries you actually run, and remember that every index is one more write per row.

In the real world

Our planner handles one table and one query. A real planner also chooses join orders and join methods, parallel scans, and when to use statistics gathered across several columns at once (CREATE STATISTICS), and it models caching with more care than our formulas. Other engines differ in detail: in MySQL’s InnoDB the table itself is stored in primary-key order and secondary indexes point at primary keys, so “covering” matters even more there.

The same habits work in every database: ask the database for its plan, compare estimates with reality, and index for the queries you actually run.

A vector index in an LLM retrieval system is the same idea for a different question: it answers “nearest” instead of “equal”, and an IVF index partitions the space of vectors the way a B+tree partitions keys.