What an index is and how it speeds up queries

A team’s “filter by status” dashboard takes 50ms on 100k rows in staging. In production with 50M rows it takes 8 seconds. The schema is correct. The query is correct. One DDL line — CREATE INDEX CONCURRENTLY ON orders(status) — brings it back to 20ms. That line is the entirety of this lesson.

What an index is

An index is a separate data structure — usually a B-tree — that stores a sorted copy of one or more column values plus pointers to the actual rows. When a query filters by an indexed column, Postgres navigates the tree in O(log n) steps instead of scanning every row.

The book-index metaphor holds precisely: a book’s back-matter index is a sorted list of terms with page numbers. To find “MVCC”, you open the index (one O(log n) lookup), read the page number, and jump there. Without the index you scan every page. A database index is identical — a copy of column values, organized for fast lookup by one specific question.

The cost: indexes tax every write

Every index is a separate on-disk structure that must stay synchronized with the table. Every INSERT, UPDATE, or DELETE that touches an indexed column must also update the index — costing CPU and I/O. A table with ten unused indexes on a write-heavy workload spends 10× more on writes than necessary.

Typical per-index write overhead: 5–50 µs per write. At 10,000 inserts/second with ten indexes, that is an extra 0.5–5ms of overhead per second of clock time — measurable, and often the bottleneck when teams over-index.

Index storage on disk: roughly bytes_per_key × row_count × 1.3. For a BIGINT key (8 bytes), a 100M-row table produces a ~1 GB index. Each index beyond the first multiplies this.

A concrete scenario

Consider: SELECT * FROM orders WHERE user_id = 42 on a table with 10M rows. Without an index: sequential scan, ~2 seconds. After CREATE INDEX ON orders(user_id): index lookup plus heap fetch, ~3 milliseconds. Same query, 600× speedup, one DDL line.

Postgres ships six index types. B-tree is the default and handles 95% of production use — equality, range, ORDER BY, LIKE 'abc%'. The other five (GIN, GiST, BRIN, Hash, Bloom) serve specific data shapes and are covered in lesson 04.

Production rule: always use CONCURRENTLY

CREATE INDEX takes an ACCESS EXCLUSIVE lock — all reads and writes are blocked for the duration. On a table with active traffic, even a 5-minute lock is an incident.

CREATE INDEX CONCURRENTLY uses a multi-phase build that does not take the exclusive lock. It scans the table twice and waits for in-flight transactions between phases. It is 2–3× slower and cannot be wrapped in a transaction, but it produces no visible impact on application traffic.

If a CONCURRENTLY build fails (e.g., a unique-index encounters a duplicate, or the process is killed), the index is left in an INVALID state (indisvalid = false in pg_indexes). The planner treats it as non-existent. Fix: DROP INDEX CONCURRENTLY and retry.