Design to Scale
Database Indexing
Why the same query gets slower every day as a table grows, how a B-tree index turns a full scan into a few page reads — and why every extra index makes writes pay.
What you will learn
- Explain the difference between a sequential scan and an index lookup.
- Predict how query time grows with table size with and without an index.
- Weigh the write cost of every index against the reads it speeds up.
- Use EXPLAIN to check what the database actually does.
Overview
Finding a topic in a 1,000-page book by reading every page takes forever; the index at the back sends you to page 412 in seconds. A database index is the same idea: a sorted structure that points to the rows you want, so the database does not have to read them all.
Without an index, WHERE customer_id = ? makes the database read every row (a sequential scan), so the cost grows linearly with the table. A B-tree index keeps the column sorted in a shallow tree; a lookup walks a handful of levels, so the cost grows with log₂(rows) — 20 levels for a million rows, 30 for a billion.
Run it
In A the table grows with every order and each lookup scans it: watch Average read climb until the database saturates — with the same code and the same traffic. B adds one index. C has twelve: reads are fast, but look at Average write.
What an index costs
| No index | One index | Many indexes | |
|---|---|---|---|
| Lookup by column | Scan every row | Walk ~20 tree levels | Walk ~20 tree levels |
| Insert / update | Write the row | Row + 1 index entry | Row + N index entries |
| Disk and memory | Table only | + index size | Indexes can outgrow the table |
| Grows with table | Linearly | Logarithmically | Logarithmically (reads), linearly in N (writes) |
In practice
EXPLAIN ANALYZE SELECT id, total FROM orders WHERE customer_id = 42 ORDER BY created_at DESC LIMIT 20;
-- Seq Scan on orders (rows=1,800,000) Filter: customer_id = 42 ← reads everything
-- One composite index serves the filter AND the sort; CONCURRENTLY avoids locking writes.
CREATE INDEX CONCURRENTLY idx_orders_customer_created ON orders (customer_id, created_at DESC);
EXPLAIN ANALYZE SELECT id, total FROM orders WHERE customer_id = 42 ORDER BY created_at DESC LIMIT 20;
-- Index Scan using idx_orders_customer_created (rows=20) ← reads 20 rows
-- Find indexes nobody uses (they still slow every write):
SELECT relname, indexrelname, idx_scan FROM pg_stat_user_indexes WHERE idx_scan = 0;- Composite indexes: column order matters — equality columns first, then range or sort columns.
(customer_id, created_at)servesWHERE customer_id = ? ORDER BY created_at, notWHERE created_at > ?alone. - Covering indexes (
INCLUDE (total)) answer the query from the index without touching the table. - Selectivity: an index on a column with two values (
is_active) rarely helps; the planner will scan anyway.
Trade-offs
| Benefits | Costs | |
|---|---|---|
| Reads | Lookups stay fast as the table grows by orders of magnitude. | Only queries that match the index's leading columns benefit. |
| Writes | One well-chosen index costs little. | Every index is updated on every insert and update — write-heavy tables suffer. |
| Resources | Hot index pages stay in memory. | Indexes use disk and buffer cache; bloated indexes need maintenance. |
Production considerations
- Index for your top queries by total time (
pg_stat_statements), not for every column. - Create indexes concurrently on live tables, and drop unused ones.
- Re-check plans after big data changes: a plan that was fine at 10k rows may scan at 10M.
- Load-test with production-sized data — small test tables hide missing indexes.