System design · The method: framework, arithmetic, APIs, data, storage, caching

Indexes: what a query costs with and without one

An index turns a scan of every page into a walk of three or four, but only for the queries whose shape it matches, and every index you add is paid for on every write. This counts the page reads, shows why a planner ignores an index for unselective queries, and covers composite column order, covering indexes, the write cost, and how to read a query plan.

19 min read Free to read Patterns: btree-index, composite-index, covering-index

What you'll be able to do

Before this: data-modeling, picking-a-datastore

"Add an index" is the most common performance fix in a design round and the one most often offered without thought. It is usually right. But an interviewer who hears it will often ask the follow-up that separates the answers: which index, on which columns in which order, and what does it cost on the write path? A candidate who can count the pages a query reads can answer all three. A candidate who cannot will propose an index on every column and be asked why inserts got slow.

This lesson is the counting. It is short arithmetic, and it explains almost every indexing decision you will make in an interview.

Counting pages

Databases read and write in fixed-size pages, 8 KB in Postgres. Without an index, finding rows by a column the table is not sorted on means reading every page of the table. With a B-tree index, it means walking from the root of the tree to a leaf, then fetching the row.

The reason the walk is short is fanout. An index page holds hundreds of entries, each pointing to a page on the next level down, so each level multiplies the reach by hundreds. Three levels cover tens of millions of rows; four cover billions. The cell below sizes a 50 million row table and then asks a more interesting question: if a query matches a fraction of the rows, at what point does the index stop being worth it?

JavaScript
// How many 8 KB pages does a query read, with and without a B-tree index?
const ROWS = 50_000_000;
const PAGE = 8192;
const ROW_BYTES = 200;   // average heap row, including per-row overhead
const ENTRY_BYTES = 20;  // index entry: key + row pointer + overhead

const rowsPerPage = Math.floor(PAGE / ROW_BYTES);
const heapPages = Math.ceil(ROWS / rowsPerPage);
const fanout = Math.floor(PAGE / ENTRY_BYTES);

let levels = 1, reach = fanout;
while (reach < ROWS) { reach *= fanout; levels++; }

console.log("heap pages (full scan)    :", heapPages);
console.log("index fanout, levels      :", fanout, levels);
console.log("point lookup page reads   :", levels + 1);

// Postgres-style weights: a random page costs 4x a sequential one (random_page_cost = 4).
const SEQ = 1.0, RANDOM = 4.0;
const seqCost = heapPages * SEQ;
for (const pct of [0.001, 0.1, 0.5, 1, 10]) {
  const matching = ROWS * pct / 100;
  const indexCost = (levels + matching) * RANDOM;   // worst case: each match on its own page
  const winner = indexCost < seqCost ? "index" : "full scan";
  console.log(`select ${String(pct).padStart(5)}% of rows -> ${winner}`);
}

const crossover = (seqCost / RANDOM - levels) / ROWS;
console.log(`crossover selectivity     : ${(crossover * 100).toFixed(3)}%`);

Read the first three lines as the headline. A point lookup is 4 page reads against 1,250,000 for a scan: five orders of magnitude, and the reason an unindexed lookup on a big table is the most common cause of a slow endpoint. The upper levels of the tree are hot and stay in memory, so in practice the lookup often costs one or two real disk reads.

The rest is the part candidates miss. Each matching row may live on a different heap page, and random page reads cost more than sequential ones, so an index that matches more than a small fraction of the table loses to reading the table straight through. With these assumptions the crossover is well under 1%. That is why a planner ignores an index on status when 40% of orders are 'shipped', and why an index on a low-cardinality column alone is rarely useful. Real crossovers depend on how the table is physically ordered and on caching, so treat 0.6% as the shape of the answer, not a constant.

B-tree, hash, and why B-tree is the default

A B-tree keeps keys sorted, so it serves equality (= 42), ranges (BETWEEN, <), sorting (ORDER BY created_at) and prefix matches (LIKE 'abc%'). That breadth is why it is the default in every relational database and the right first answer in an interview.

A hash index serves equality only. It can be slightly smaller and faster for pure = lookups on long keys, but it cannot do ranges or sorting. In Postgres it is rarely worth choosing over a B-tree; in a key-value store, the whole store is effectively a hash index on the key, which is exactly why those stores are fast for lookups and useless for "everything between these two values" unless you design a sort key.

Composite indexes and column order

Most real queries filter on more than one column. A composite index on (a, b, c) is sorted by a, then by b within each a, then by c. That ordering gives the leftmost-prefix rule: the index can be used efficiently for conditions on a, on a and b, or on a, b and c, but not for b alone, because rows with a given b are scattered across every value of a.

The ordering rule that follows, and the one to say out loud: equality columns first, then the one range or sort column. For

SELECT * FROM orders
WHERE customer_id = $1 AND status = 'open'
ORDER BY created_at DESC
LIMIT 20;

the index is (customer_id, status, created_at). The planner jumps to the exact (customer_id, status) group, which is already sorted by created_at, and reads 20 entries. Put created_at first and the index is nearly useless for this query, because the matching rows are spread across the whole time range.

Covering indexes

After finding entries in the index, the database normally fetches each row from the table to get the other columns. If the index already contains every column the query needs, it can skip that fetch entirely; this is an index-only scan, and the index is said to cover the query.

In Postgres you can add non-key columns to an index with INCLUDE:

CREATE INDEX orders_open_by_customer
  ON orders (customer_id, status, created_at DESC)
  INCLUDE (total_cents);

Now "the 20 newest open orders for this customer with their totals" touches only index pages. For a hot read endpoint that removes the random heap reads that dominated the cost in the cell above. Postgres adds one condition worth knowing: an index-only scan still checks whether each row is visible to the transaction, and it can skip the heap only for pages that vacuum has marked all-visible. A table with heavy churn gets less benefit.

The cost is size. Every included column is duplicated in the index, so cover the one or two queries that matter, not every query.

What each index costs on the write path

Every insert writes the row and one entry in every index on the table. Every update that changes an indexed column writes a new entry in that index. Every delete eventually has to remove entries from every index. So a table with eight indexes does roughly nine writes for each insert, and those index writes land on random pages unless the key is time-ordered (the data modeling lesson's point about ids applies to every index, not just the primary key).

Three consequences to bring into a design:

  • Write-heavy tables get few indexes. An events table taking 20,000 inserts a second should have its primary key and perhaps one more. Reads that need other orders belong in a copy built for them (a search index, an analytics store), fed asynchronously.
  • Unused indexes are pure cost. Databases track index usage; dropping indexes nobody reads is one of the cheapest write optimisations there is.
  • Index builds lock or slow the table. In Postgres, CREATE INDEX CONCURRENTLY avoids blocking writes at the cost of a slower build. Mentioning it when you add an index to a live table is a small, convincing senior detail.

Specialised indexes, named briefly

Two index families come up in interviews for queries a B-tree cannot answer well.

Geospatial indexes answer "what is within 2 km of this point?". A B-tree on latitude alone finds a band around the whole planet. Spatial indexes (R-trees, which is what PostGIS builds through Postgres's GiST, or grid encodings such as geohashes) group nearby points together. The proximity-search lesson in the patterns part covers the options and when each wins.

Inverted indexes answer "which documents contain these words?". They map each term to the list of documents containing it, which is the structure behind full-text search. Postgres has one (GIN) and it is good enough for modest search; a dedicated engine such as Elasticsearch adds relevance ranking, analysers and distributed scoring, covered in the key-technologies part.

Reading a query plan

In an interview you will not run EXPLAIN, but saying how you would check an index is a strong signal, and the vocabulary is small. EXPLAIN ANALYZE runs the query and reports the plan with real row counts and timings. The node types to recognise:

Plan nodeWhat it meansUsually
Seq ScanRead every page of the tableFine for small tables or unselective filters; a red flag on a big table with a selective filter
Index ScanWalk the index, fetch each matching rowThe normal selective lookup
Index Only ScanAnswer from the index aloneA covering index working
Bitmap Heap ScanCollect matching row locations, then read pages in orderMedium selectivity, or several indexes combined

The other thing to read is estimated rows against actual rows. If the planner expected 10 rows and got 400,000, its statistics are stale or the data is skewed, and it picked the plan for a query you are not running. Refreshing statistics (ANALYZE) fixes more slow queries than adding indexes does.

A worked indexing pass

1Map each read to an index▾

A table of 50 million orders. The interface has three reads: an order by id; a customer's recent orders, newest first, 20 at a time; and a support tool that finds orders by the last four digits of a phone number.

  • Order by id is served by the primary key. Four page reads, nothing to add.
  • Customer's recent orders needs (customer_id, created_at DESC). With a cursor on created_at and id, every page of results is one index descent plus 20 entries. Add INCLUDE for the two columns the list screen shows if it is the hottest read.
  • Phone suffix search is the interesting one. LIKE '%1234' cannot use a B-tree on the phone column, because the match is at the end. Either store the reversed phone number (or the last four digits) in its own indexed column, or accept a slow query for an internal tool used ten times an hour. Saying which and why is the answer; both are defensible.
2State the write cost▾

"That's the primary key and two secondary indexes on a table taking about 300 inserts a second. Three index writes per insert is nowhere near a problem at that rate, so I'm comfortable. If this were the events table at 20,000 a second, I'd keep it to the primary key and serve the other reads from a separate store."

The checklist

  1. For each read, the query shape: which columns are equalities, which is the range or sort.
  2. A B-tree on equality columns first, then the range or sort column, matching the leftmost prefix.
  3. A selectivity check: an index on a column where one value matches a large share of rows will not be used.
  4. A covering index (INCLUDE) only for the one or two hottest reads.
  5. The write cost counted: one entry per index per insert, and few indexes on write-heavy tables.
  6. Geospatial or inverted indexes named when the query is "nearby" or "contains these words".
  7. How you would verify it: EXPLAIN ANALYZE, the node type, and estimated against actual rows.