7.3.2 — Indexes: What They Cost and Why Yours Is Not Being Used

A team adds an index on (status, created_at) to speed up a dashboard. The dashboard gets faster. Two weeks later the nightly import, which used to take 20 minutes, takes 70.

Both things are the same fact. An index is a second copy of some of your data, kept sorted, and every write has to maintain every copy. Reads get faster because the sorted copy can be searched; writes get slower because there is more to write. Almost every index question is that trade, applied carefully.

1. What an index physically is

An index is a B+ tree (Chapter 4.13.3 builds it from first principles) whose entries are (key value, row pointer), sorted by key. In PostgreSQL the pointer is the ctid from Chapter 7.3.1; in InnoDB a secondary index stores the primary key value instead.

The height is the number of page reads. With 8 KB pages and, say, 16-byte entries, one page holds hundreds of keys. A tree of fanout ~200 reaches:

• 1 level: 200 rows
• 2 levels: 40,000
• 3 levels: 8 million
• 4 levels: 1.6 billion

So finding one row among a billion is four page reads, and the top two or three levels are permanently in the buffer pool because every query touches them. In practice a primary-key lookup costs about one real read. That is the whole reason indexes work, and it is why the number of rows barely affects lookup time while it hugely affects a scan.

A B+ tree keeps all the data in the leaves and links the leaves together. That linkage is what makes range scans work: find the start, then walk sideways. This is why one structure serves =, <, >, BETWEEN, LIKE 'prefix%' and ORDER BY — all of them are "find a position and walk".

And it is why an index can remove a sort. If the query wants ORDER BY created_at DESC LIMIT 20 and an index on created_at exists, the engine walks the leaves backwards and stops after 20. No sort node, no reading the rest of the table. Chapter 7.2.3's plans call this out directly.

2. Composite indexes and the leftmost prefix rule

This is the single most misunderstood thing about indexes, and it has one clean mental model.

An index on (a, b, c) is a phone book sorted by surname, then first name, then middle name.

A composite index is sorted by the first column, then within that by the second. Anything that does not start at the left has no starting point to jump to.

The leftmost prefix rule: an index on (a, b, c) serves queries filtering on a, on (a, b), and on (a, b, c) — and not on b alone, or on (b, c).

Query	Index (a, b, c)
WHERE a = 1	Used
WHERE a = 1 AND b = 2	Used
WHERE a = 1 AND b = 2 AND c = 3	Fully used
WHERE a = 1 AND c = 3	Used for a only; c filtered after
WHERE b = 2	Not used (may still be scanned whole if that is cheaper)
ORDER BY a, b	Sort avoided
ORDER BY b	Sort not avoided

The order of conditions in your WHERE clause is irrelevant. WHERE b = 2 AND a = 1 uses the index perfectly; the planner is not reading left to right. Only the column order in the index definition matters.

How to choose the column order. There is a rule that gets it right nearly every time:

1. Equality columns first, in any order among themselves.
2. Then the column you want sorted, if there is an ORDER BY.
3. Range conditions last (<, >, BETWEEN, LIKE 'x%').

The reason range goes last is the important part: a range condition ends the usable prefix. Once the scan is walking a range of values in column b, column c is no longer in sorted order across those rows — it is only sorted within each value of b. So the engine can still read c and filter on it, but it cannot jump.

-- Query: recent orders for one customer, newest first
SELECT * FROM orders
WHERE customer_id = 42 AND placed_at >= '2026-01-01'
ORDER BY placed_at DESC LIMIT 20;

CREATE INDEX ON orders (customer_id, placed_at DESC);   -- (1)

(1) Equality on customer_id first, then placed_at which serves both the range and the sort. The plan becomes: jump to customer 42, walk backwards, stop after 20 rows. No sort, no filter, twenty rows touched. Reversing the columns to (placed_at, customer_id) would force a scan over every order since January, filtering for customer 42.

Is (a, b) plus (a) worth having? No — (a, b) already serves everything (a) does. A separate (a) index is a redundant index: pure write cost, no read benefit. Finding and dropping these is one of the easiest wins in an old schema. (b, a) on the other hand is a genuinely different index, and whether you need both depends on whether queries filter on b alone.

3. Covering indexes and index-only scans

If every column a query needs is in the index, the engine never touches the table. That is an index-only scan, and it is the fastest read shape available.

-- The query
SELECT customer_id, placed_at FROM orders WHERE customer_id = 42;
-- Covering index: both columns are present
CREATE INDEX ON orders (customer_id, placed_at);

INCLUDE adds payload columns without making them part of the key:

CREATE INDEX orders_cust_idx ON orders (customer_id) INCLUDE (total_minor, status);

The included columns are stored in the leaves only. They cannot be searched or sorted on, but they can be returned. That keeps the key small — so the tree stays shallow and comparisons stay cheap — while still avoiding the table fetch.

The PostgreSQL caveat you must know. An index does not record whether a row version is visible to your transaction (Chapter 7.4.2). So an index-only scan consults the visibility map, a compact bitmap of pages known to be all-visible. If the page is not marked, the engine must fetch the row after all. The plan reports this as Heap Fetches: 41000, and the cause is almost always that autovacuum has not run since the last bulk change. An index-only scan on a heavily updated table is often not index-only, and VACUUM is the fix.

This matters more in InnoDB, where a secondary index lookup costs two tree traversals. A covering secondary index removes the second one entirely, which is a larger relative win than in PostgreSQL.

4. The index types, and when a B-tree is the wrong one

B-tree — the default, and correct for =, ranges, sorting and prefix matching, on anything with a natural order.

Hash — equality only, no ranges, no sorting. In PostgreSQL it is now crash-safe and marginally smaller than a B-tree for long keys, and there is rarely a strong reason to choose it.

GIN (generalised inverted index) — for values that contain multiple searchable items: array elements, jsonb keys and values, and full-text search lexemes. This is the inverted index of Chapter 7.7, built into PostgreSQL. Fast to search, slow to update, which is why it has a pending-insert list that defers work.

GiST — a framework for "is near / overlaps / contains" queries: geometric shapes, ranges, and geographic data through PostGIS. This is what answers "find restaurants within 2 km" (Chapter 11.17).

BRIN (block range index) — stores only the minimum and maximum value per group of pages. Tiny — kilobytes for a table of hundreds of gigabytes — and useful only when the physical row order correlates with the column, which in practice means an append-only table indexed on its timestamp. On such a table it replaces a multi-gigabyte B-tree. On a randomly ordered column it is useless, because every block range spans the whole value range.

Full-text — tsvector plus GIN. Chapter 7.7 covers ranking and why a real search engine may still be the right answer.

Then two modifiers that apply to any of them:

Partial index — indexes only rows matching a condition.

CREATE INDEX ON jobs (created_at) WHERE status = 'pending';

If 0.1% of jobs are pending, this index is a thousandth of the size, stays entirely in memory, and costs nothing on writes to rows that do not match. It is the highest-value index shape most schemas are missing, and it fits every queue table, every soft-delete table, and every "unprocessed" flag.

Expression index — indexes the result of a function, which is the fix for the non-sargable conditions in Chapter 7.2.3.

CREATE INDEX ON customers (LOWER(email));
-- now this uses it:
SELECT * FROM customers WHERE LOWER(email) = 'ana@x.com';

The query must contain the same expression the index was built on. WHERE email ILIKE 'ana@x.com' will not use it.

5. What an index costs

Write amplification. Every INSERT writes one row plus one entry per index. Every DELETE removes them. Every UPDATE to an indexed column rewrites that index entry — and in PostgreSQL, an update that cannot be a HOT update (Chapter 7.3.1) rewrites every index entry for that row, even for columns that did not change. A table with eight indexes costs roughly eight times as much per write as a table with none. That is the opening story's 20 minutes becoming 70.

Space. Indexes routinely exceed the table itself. It is normal for a 40 GB table to carry 60 GB of indexes, and that space competes for the buffer pool with the data.

Buffer pool competition. An index that is never read still gets loaded into memory when it is maintained, evicting pages that are read.

Planner effort and risk. More indexes means more plans to consider, and more chances of choosing a bad one from a bad estimate.

So the discipline is: index for the queries you actually run, and delete the ones nothing uses.

-- Indexes nobody has read since the last statistics reset
SELECT relname, indexrelname, idx_scan, pg_size_pretty(pg_relation_size(indexrelid))
FROM pg_stat_user_indexes
WHERE idx_scan = 0 AND indexrelid NOT IN (SELECT conindid FROM pg_constraint)
ORDER BY pg_relation_size(indexrelid) DESC;

Read the result carefully before dropping: an index with zero scans might serve a quarterly report, or enforce a unique constraint, or exist on a replica that gets different traffic. Check uptime since the statistics were reset, and drop with a plan to recreate.

Missing indexes show up as sequential scans with large Rows Removed by Filter in pg_stat_statements plus EXPLAIN. There is no reliable automatic list — advisers over-suggest, because they see each query alone and cannot see the write cost.

6. The N+1 problem, properly

This is the highest-value item in this chapter for most applications, and it is not an index problem at all — it is a round-trip problem that indexes cannot fix.

const orders = await db.query('SELECT id, customer_id FROM orders LIMIT 100'); // 1
for (const o of orders) {
  const c = await db.query('SELECT name FROM customers WHERE id = $1',
                           [o.customer_id]);                                   // ×100
}

101 queries. Each takes 0.3 ms in the database and 1 ms of network round trip, so the loop costs about 130 ms of which 100 ms is waiting. Add an index and each query goes from 0.3 ms to 0.1 ms — saving 20 ms out of 130. The problem is the count, not the speed.

Three fixes, in order of preference:

-- 1. Join: one query
SELECT o.id, c.name FROM orders o JOIN customers c ON c.id = o.customer_id LIMIT 100;

-- 2. Two queries with an IN list — better when a join would multiply rows
SELECT id, name FROM customers WHERE id = ANY($1);

3. A dataloader: collect the ids requested during one tick of the event loop, issue a single batched query, and hand each caller its result. This is how GraphQL servers avoid N+1 without every resolver knowing about every other one, and Chapter 5.8 names N+1 as one of GraphQL's three real costs.

Detection is the part to get right. N+1 never appears in a slow-query log, because each query is fast. Count queries per request in development and log it. A number that jumps from 4 to 104 when you add a field to a response is unmissable in a log line and invisible in a profile.

7. A practical checklist

Index every foreign key. Databases index primary keys automatically and do not index the referencing side. So orders.customer_id is unindexed by default, which makes both the join and — critically — a DELETE on the parent slow, because the engine must scan the child table to check the constraint.

Index the columns you filter and sort on together, in one composite index, using the equality-then-sort-then-range order.

Add a partial index for any "hot subset" — pending, active, undeleted.

Do not index a low-cardinality column alone. A boolean with a 50/50 split will never be used. As the second column of a composite, or as the condition of a partial index, the same column is valuable.

Create on production with CONCURRENTLY (Chapter 7.2.4), and check afterwards that it is actually being used.

Review index size against table size once in a while. Indexes larger than the table are a signal to look for redundant and unused ones.

What the interviewer will push on

"You have an index on (a, b, c). Which queries use it?" Anything with a leftmost prefix: a, a+b, a+b+c. Not b alone. Then add the two things that separate a real answer: the order of conditions in the WHERE clause is irrelevant, and a range condition ends the usable prefix, which is why range columns go last.

"How would you order the columns for WHERE customer_id = ? AND placed_at > ? ORDER BY placed_at DESC?" (customer_id, placed_at DESC) — equality first, then the column that serves both range and sort. Say what it buys: no sort node, and only the twenty rows of the LIMIT are touched.

"What does an index cost?" Write amplification per index, space that competes for the buffer pool, and planner risk. Then the PostgreSQL specific: a non-HOT update rewrites every index entry for the row, not only the changed column's.

"What is a covering index?" One that contains every column the query needs, so the table is never read — an index-only scan. Then volunteer the PostgreSQL caveat: visibility is not stored in the index, so an unvacuumed table shows Heap Fetches and loses the benefit.

"When is a B-tree the wrong index type?" Containment and multi-value search wants GIN (jsonb, arrays, full text); nearness and overlap wants GiST; a huge append-only table ordered by time wants BRIN, which is kilobytes instead of gigabytes. Naming BRIN's precondition — physical order must correlate with the column — is the tell.

"How do you find and fix an N+1?" Count queries per request in development, because it never shows in a slow-query log. Fix with a join, an IN batch, or a dataloader. The strong version adds that indexing does not fix it: the cost is 101 round trips, not slow queries.

One thing to volunteer: point out that databases index the primary key automatically but not the foreign key column that references it, so an unindexed orders.customer_id makes deleting a customer scan the entire orders table. It is a one-line fix that almost every young schema is missing.

Recall

• An index is a sorted second copy of some columns. Reads get faster, writes get slower, and every index question is that trade.
• A B+ tree of fanout ~200 finds one row in a billion in four page reads, with the top levels always cached. Leaves are linked, which is why one structure serves =, ranges, prefixes and ORDER BY.
• Leftmost prefix rule: (a, b, c) serves a, (a, b), (a, b, c) — never b alone. The order of conditions in your WHERE is irrelevant; only the index definition's order matters.
• Column order: equality, then sort, then range — because a range condition ends the usable prefix. (a, b) makes a separate (a) index redundant.
• A covering index gives an index-only scan; INCLUDE adds payload without enlarging the key. In PostgreSQL, Heap Fetches above zero means the visibility map is stale — vacuum.
• Types beyond B-tree: GIN for jsonb/arrays/full text, GiST for nearness and overlap, BRIN for huge append-only tables where physical order correlates with the column. Plus partial indexes for hot subsets and expression indexes for LOWER(col).
• Costs: one extra write per index per row, space that often exceeds the table, and — in PostgreSQL — a non-HOT update rewriting every index entry for the row.
• N+1 is not an index problem. 101 round trips cost latency, not query time, so it never appears in a slow-query log. Detect by counting queries per request; fix with a join, an IN batch, or a dataloader.
• Foreign key columns are not indexed automatically. An unindexed orders.customer_id makes deleting a customer scan the whole child table.

Self-test: Why does WHERE b = 2 not use an index on (a, b)? · Why do range columns go last? · What is Heap Fetches telling you? · When is BRIN a thousand times smaller than a B-tree, and when is it useless? · Why does adding an index not fix N+1? · Which index does every schema forget to create?

Next: 7.3.3 covers the write side — the write-ahead log that makes a commit durable without a random disk write, checkpoints, replication built from the same log, and the LSM tree that makes the opposite trade.