🗄 SQL & Databases · Chapter 7

Indexes: when they help, when they cost

An index is a second copy of your data, sorted differently. That sentence explains both why reads get faster and why writes get slower.

Study this lesson free in the app →

The basics

An index is a separate, sorted copy of one or more columns, with a pointer from each entry back to the full row, so the database can jump straight to matching rows instead of reading the whole table.

The problem it solves: finding one ride in a 40-million-row table without help means reading all 40 million rows. With an index on ride_id, the database walks a shallow tree — 3 or 4 steps — and lands on the row in milliseconds. That's the difference between a payments API that answers in 5 ms and one that times out.

The mental model: the index at the back of a textbook. Sorted alphabetically, so you jump to "Kafka" instead of reading 900 pages. But somebody had to build it, it takes extra pages, and every time a chapter is added it must be updated. Databases pay exactly those costs: every insert also writes into every index.

Explained

SELECT * FROM rides WHERE ride_id = 'ride_9001';

Without an index: read 40 million rows, keep one. Seconds. With an index on ride_id: three or four jumps down a tree. Milliseconds.

So index everything?

No — because every index must be updated on every insert, update and delete, and it occupies disk. Ten indexes on a hot table can halve your write throughput. Indexes are a trade, and the whole skill is knowing which side you're on.

The index at the back of a book

To find every mention of Kafka in a 900-page book, you can read all 900 pages, or turn to the index and find "Kafka — 210, 344, 501".

The index works because it's sorted alphabetically — you don't read it either, you jump.

But notice what it cost. Somebody built it. It takes up 30 extra pages. And if the author inserts a new chapter, every page number in the index is wrong and it must be rebuilt.

That's a database index exactly. A separate, sorted structure that makes lookups fast, costs storage, and must be maintained on every change to the underlying book.

How a B-tree actually answers a query

The default index type nearly everywhere is a B-tree — a shallow, sorted tree.

                [ M ]                     ← root
           /            \
      [ D  H ]        [ R  W ]            ← internal nodes
      /   |   \       /   |   \
   [A-C][E-G][I-L] [N-Q][S-V][X-Z]        ← leaves → row pointers

Finding a value means comparing at each level and descending. A tree over 100 million rows is about 4 levels deep, so a lookup is roughly 4 page reads instead of 100 million.

Because the leaves are sorted and linked, a B-tree serves more than equality:

WHERE ride_id = 'ride_9001'              -- ✅ point lookup
WHERE fare BETWEEN 100 AND 500           -- ✅ range: find the start, walk
WHERE ride_date >= '2026-07-01'          -- ✅ range
ORDER BY ride_date                       -- ✅ already sorted, no sort step
WHERE city LIKE 'Shil%'                  -- ✅ prefix match
WHERE city LIKE '%long'                  -- ❌ can't — no known starting point

That last pair is the key intuition: an index is sorted, so anything that gives it a starting point works, and anything that doesn't requires reading everything anyway.

Step through a lookup

The order of columns in a composite index is not cosmetic — it's the order the tree is sorted in.

Why does only one of these use the index?

There is one index: CREATE INDEX ON rides (city, ride_date);

-- A
WHERE city = 'Shillong' AND ride_date = '2026-07-15'
-- B
WHERE city = 'Shillong'
-- C
WHERE ride_date = '2026-07-15'
-- D
WHERE lower(city) = 'shillong'
-- E
WHERE city = 'Shillong' AND fare > 100

The costs, stated plainly

Write amplification. Every INSERT writes the row plus one entry per index. A table with 8 indexes does 9 writes per insert. On a high-throughput ingestion table this is often the actual bottleneck.

Storage. An index on a wide column can approach the size of the table. Ten indexes can exceed it.

Maintenance. Updates fragment the tree; it needs periodic rebuilding. Statistics go stale and the planner starts choosing badly.

When an index doesn't help at all:

• Low selectivity. An index on status where 90% of rows are 'completed' — the engine reads most of the table anyway, and doing it via the index (jump, fetch, jump, fetch) is slower than scanning sequentially. Rule of thumb: below roughly 10–20% selectivity, a scan wins
• Small tables. A few thousand rows fit in memory; the scan is already instant
• Bulk loads. Dropping indexes, loading, then rebuilding is often several times faster
• Columnar warehouses — Snowflake, BigQuery, Databricks. These generally have no B-tree indexes at all. Their equivalents are partitioning, clustering keys and micro-partition pruning. Proposing "add an index" in a Snowflake interview signals you've conflated two different worlds

The index that made everything slower

An ingestion table takes 40,000 inserts a second. Analysts complain their ad-hoc queries are slow, so eleven indexes get added over six months — one per column somebody filtered on.

Three months later, ingestion starts falling behind and consumer lag climbs every evening.

Each insert now performs 12 writes: the row plus eleven index entries. The table has become write-bound, and the cause is invisible in application code — nothing changed there.

Worse, most of those indexes are barely used. Two serve real queries; nine were added for a question asked once.

What should have happened: the analysts' queries didn't belong on the operational table at all. That's the OLTP/OLAP split — ad-hoc analysis belongs in the warehouse, where columnar storage answers those questions without indexes and without touching the write path.

Diagnosing this on a real system:

-- Postgres: which indexes are actually used?
SELECT relname, indexrelname, idx_scan
FROM pg_stat_user_indexes
WHERE idx_scan = 0;      -- never used since stats were reset

Unused indexes are pure cost. Auditing them is one of the highest-return, least-glamorous performance tasks there is.

An index is a sorted copy. Reads jump; writes pay for every index.

Leftmost prefix: an index on (a, b) serves a and a AND b, never b alone.

A function on the column kills the index. year(date) = 2026 ❌ → date >= … AND date < … ✅

Words to know

In two minutes

• An index is a sorted copy of some columns with pointers to rows; lookups jump instead of scanning.
• B-trees stay shallow — about 4 levels for 100M rows — so a point lookup is a handful of page reads.
• Composite indexes are sorted by the first column, then the next: the leftmost-prefix rule decides which queries they serve.
• Wrapping the indexed column in a function or cast (year(d), lower(x)) disables a plain index — rewrite as a range or build a functional index.
• Indexes help selective filters; for filters matching a large share of rows a sequential scan is faster.
• Every index taxes every insert, update and delete, plus storage and maintenance — index for real query patterns only.
• Warehouses like Snowflake and BigQuery have no B-trees; they rely on partitioning, clustering and pruning.

Test yourself

There are 9 questions, 3 puzzles and 7 recall cards for this lesson in the app — the recall cards come back on later days, just before you would forget.