Engineering Atlas › System Design Fundamentals

Speeding up queries with database indexes

15 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

How it works

Why scanning stops working

Without an index, WHERE email = 'ana@x.io' over 50 million 200-byte rows reads about 1.2 million 8 KB pages, roughly 10 GB. A B+ tree on email needs three or four page reads. This is the "finding things fast" problem shape, and it recurs as a search engine's inverted index, a vector database's neighbour graph and a code-search trigram index: pay at write time so reads touch a small fraction of the data.

What an index entry holds

An index entry is the indexed value plus a way to find the row. In Postgres the table is an unordered heap and each entry stores a ctid, the row's physical (block, offset) address. In InnoDB the table is a B+ tree ordered by primary key (a clustered index), and secondary entries store the primary key (MySQL docs). An InnoDB lookup by email descends two trees; Postgres descends one and reads a heap page. In exchange, InnoDB secondary indexes ignore rows moving within the clustered tree, while Postgres adds index entries whenever an update puts a new row version on another page.

Composite, covering, partial and expression indexes

A composite index on (tenant_id, created_at) sorts by tenant, then by time within a tenant. It serves "tenant 7's orders this week" as one contiguous range, but not "all orders this week" (the Database Design lesson covers the prefix rule in detail). Postgres 18 softened that rule with B-tree skip scan: when the leading column has few distinct values, the planner can probe once per value instead of giving up on the index (Postgres docs). With thousands of tenants it still loses to an index that leads with created_at. A covering index holds every column a query needs, either as key columns or as INCLUDE payload, so the database can answer from the index alone. A partial index (WHERE status = 'open') indexes only the rows a hot query cares about, often a few percent of the table. An expression index on lower(email) serves queries that filter on that expression, which a plain index on email cannot.

Choosing what to index

Indexes pay off when the query is selective. If a filter matches 30% of rows, following the pointers costs more than one sequential pass, and the planner rightly ignores the index (see Query Optimization). Index join keys, high-QPS lookups and the sort order of paginated lists; skip low-cardinality flags on their own, write-mostly columns, and indexes that duplicate another index's prefix.

Indexes in distributed stores

When data is partitioned, an index is local (each partition indexes its own rows: local writes, but a lookup asks every partition) or global (partitioned by the indexed value: one-partition lookups, but writes cross machines). DynamoDB's global secondary indexes are updated asynchronously, normally within a fraction of a second, and serve only eventually consistent reads; its local ones share the table's partition key and allow strong reads. The global index also pushes back: if it lacks write capacity, writes to the base table are throttled (DynamoDB docs). Cassandra's secondary indexes are local. Storage-attached indexes (SAI) index each node's memtables and SSTables as they are written, so a query without the partition key still asks replicas range by range (Cassandra docs); they suit filtering, not high-QPS lookups by a non-key column.

Down the stack

Layer 1The contract

An index is invisible to results: a query returns the same rows with or without it, and the index reflects every committed change in the same transaction (single-node relational) or within a stated lag (DynamoDB global indexes). A unique index also promises no two visible rows share a key, so it is a constraint as much as a speed-up. Nothing promises the planner will use it; that is a per-query cost decision. Building an index normally blocks writes for its duration; CREATE INDEX CONCURRENTLY in Postgres and online DDL in InnoDB avoid the block at the cost of a slower build (Postgres scans the table twice and waits for older transactions) and, for Postgres, an index left INVALID if the build fails. An invalid index is ignored by queries but still updated on every write until you drop it (Postgres docs).

Layer 2The mechanism

A Postgres B-tree index is a Lehman-Yao B+ tree of 8 KB pages: leaf pages hold (key, ctid) tuples in key order and are linked to their siblings for range scans and for detecting concurrent splits, and inner pages hold separator keys (nbtree README). Since Postgres 13, repeated keys in a non-unique index are stored once with a posting list of ctids, which keeps low-cardinality indexes much smaller. An index-only scan still has to know whether each row is visible to the current transaction, and Postgres keeps visibility in the heap, so it consults the visibility map (two bits per heap page). If the page is marked all-visible, the heap visit is skipped; if not, the scan fetches the heap tuple anyway (Postgres docs). After a bulk load, an index-only scan is only fast once VACUUM has set those bits.

Updates are where indexes cost the most. Postgres writes a new row version for every update. If no indexed column changed and the new version fits on the same heap page, a heap-only tuple (HOT) update chains it from the old version and adds no index entries; otherwise every index on the table gets a new entry. Leaving free space on each page (fillfactor below 100) raises the HOT rate (Postgres docs). InnoDB can buffer changes to non-unique secondary indexes in its change buffer and merge them when the page is next read, turning random index writes into batched ones; unique indexes cannot be buffered because the uniqueness check needs the page now. MySQL 8.4 turned this off by default (innodb_change_buffering went from all to none), so on current versions every secondary index write goes straight to its page (MySQL 8.4 changes).

GIN indexes store a posting list of row pointers per element, for arrays, jsonb keys and full-text tokens. BRIN stores only the min and max of each block range (128 heap pages by default), tiny even for a terabyte table and precise only when the column follows insertion order, like a timestamp (Postgres docs).

Layer 3The machine

With 8 KB pages and 16-byte entries plus per-tuple overhead, a B-tree leaf holds a few hundred entries, so 100 million keys need three or four levels. The root and inner levels are a few megabytes and stay in memory; a lookup costs one or two leaf and heap reads that may miss the cache, about 0.1 ms each on NVMe and 5 to 10 ms on a spinning disk. A range scan reads leaves sequentially, but each matching row in a heap table can be on a different page: fetching 10,000 rows scattered across the heap can cost 10,000 random reads, which is why Postgres switches to a bitmap heap scan that sorts pointers by page first, and why clustering by the scan order matters.

Each index also costs buffer pool memory and WAL bandwidth. One insert into a table with six indexes dirties at least seven pages and writes seven WAL records, and the first change to a page after a checkpoint logs the full 8 KB page image. Random UUID keys send each insert to a different leaf, so the whole index is the working set; time-ordered keys (UUIDv7, sequences) keep inserts on a few hot rightmost leaves. Postgres 18 added a built-in uuidv7() for exactly this reason (Postgres 18 release notes).

Why it's built this way

  1. Storage rewards reading a few nearby pages and punishes scattered ones, so an index keeps keys sorted in large pages of hundreds of entries.
  2. A sorted copy must stay correct under writes, so every index is updated in the writing transaction, and cost scales with the index count.
  3. Rewriting every index on every update is ruinous, so engines add escape hatches: HOT updates, change buffers, pointing by primary key.
  4. One ordering cannot serve every query, so engines offer several structures and the planner chooses per query by estimated cost.

Diagram

flowchart TB
  Q["WHERE tenant_id = 7 AND created_at >= '2026-10-01'"] --> R["Root page"]
  R --> I["Inner page"]
  I --> L1["Leaf: (7, 10-01) ctid (412,3)"]
  L1 --> L2["Leaf: (7, 10-09) ctid (88,5)"]
  L2 --> VM{"Visibility map: page all-visible?"}
  VM -->|"yes"| OUT["Return from index"]
  VM -->|"no"| H["Fetch heap page, check row version"]
  H --> OUT

Worked example

A multi-tenant billing table has 400 million invoices of 300 bytes, about 120 GB, taking 3,000 inserts and 1,500 updates a second. The hot query lists one tenant's unpaid invoices by due date, 50 per page, at 2,000 QPS.

Without a suitable index, each query scans the tenant's rows: 2 million invoices, about 600 MB, impossible at 2,000 QPS.

An index on (tenant_id, status, due_date) turns each query into one descent plus a 50-entry range, followed by up to 50 heap fetches: around 55 page reads, most cached. Since only 3% of invoices are unpaid, a partial index on (tenant_id, due_date) WHERE status = 'unpaid' holds 12 million entries instead of 400 million: at about 40 bytes each, roughly 0.5 GB instead of 16 GB, small enough to stay in memory. Adding INCLUDE (amount, customer_name) makes it covering, so pages whose heap blocks are all-visible need no heap fetch at all.

Now the write side. The table already had five indexes. Each insert touches six B-trees, 18,000 index insertions a second. Updates mostly change status and paid_at; because status is in the old composite index, every payment update was non-HOT and wrote all five indexes. Moving to the partial index and dropping two unused indexes (found with pg_stat_user_indexes.idx_scan = 0 over 30 days) cut the indexes a payment update touches from five to two, with a matching drop in WAL volume.

In the wild

Trade-offs

OptionStrengthsWeaknessesChoose when
B+ tree on one columnEquality, range and order, general purposeWrite cost, random I/O for unclustered rowsSelective lookups and sorted pagination
Composite or covering B+ treeOne range scan, no sort, no heap visitsLarger entries, only serves its prefixHigh-QPS queries with a fixed shape
Partial indexSmall, cache-resident, cheap to maintainOnly queries matching the predicate can use itHot queries over a small subset of rows
GIN or inverted indexArray, jsonb and full-text membershipSlow, large updates; no orderingTags, documents, search
BRINTiny, near-free to maintainUseful only when values follow physical orderAppend-only time-series tables
Global secondary index (distributed)Single-partition reads by the indexed valueCross-node writes, often eventually consistentLookups by a non-partition key at scale

Pitfalls in production

Leadership lens

Check yourself

  1. Why does an update to a non-indexed column in Postgres sometimes still write to every index?

    Show answer

    If the new row version does not fit on the same heap page, it is not a HOT update, so every index needs an entry pointing to the new ctid. Lowering fillfactor leaves room and raises the HOT rate.

  2. Why does an InnoDB secondary index lookup touch two B-trees?

    Show answer

    Secondary entries store the primary key, not a physical address, so the engine finds the primary key in the secondary index and then descends the clustered index to read the row.

  3. A query filters on a status that 40% of rows have. Why might the planner ignore an index on status?

    Show answer

    Following 40% of the pointers costs more random reads than scanning the table sequentially, so the cost model picks the scan. A partial or composite index that makes the query selective helps.

  4. What is the cost of a global secondary index in a partitioned store?

    Show answer

    A write to one partition must also update the index partition that owns the new value, often on another node, so writes cost more and the index usually lags the base table.

Sources and further study

Primary

Systems docs

Books

Other curricula

Watch

Free resources

Open in the interactive app: practice, quiz, mock interview →