Part 4 — Fast at scale › Chapter 25

How an index actually works

A B-tree drawn out, clustered vs non-clustered, the heap, and the lookup that costs more than a scan.

From the advert

“Ottimizzazione e tuning delle query” — and you cannot tune what you cannot picture. This chapter is the picture.

A B-tree, drawn

🧒 Simple

A phone book, but with a contents page at the front: “A–F on page 1, G–M on page 200, N–Z on page 400”. To find Rossi you read one page, jump to page 400, read one more page, and jump again. Three pages instead of eight hundred. Add ten times more people and you read four pages instead of three — that is why an index still works when the table gets huge.

Three page reads to find one row. The dotted links between leaves are what make a range scan cheap.

🎓 Two properties, and everything follows from them

It is sorted. So it answers equality, ranges, prefix LIKE, MIN/MAX, and can supply an ORDER BY without a sort. It cannot answer anything about a value it does not store — which is the whole of sargability.
It is shallow. With ~8 KB pages and a narrow key, a level holds hundreds of entries, so three or four levels covers hundreds of millions of rows. A seek is three or four page reads whether the table has a thousand rows or a billion — which is why "add an index" scales and "the table got bigger" usually does not explain a slowdown on indexed access.

Clustered, non-clustered, heap

Structure	What the leaf holds	Notes
Clustered index	The whole row	The table is the index. One per table. It decides physical order
Non-clustered index	The key + a pointer to the row	Many per table. The pointer is the clustering key, or a RID on a heap
Heap	—	No clustered index: rows in insertion order. Fine for a staging table, bad for almost anything else

The engines disagree, and it matters

SQL Server and InnoDB cluster by the primary key by default. So the primary key choice is a physical storage decision.
PostgreSQL has no clustered index at all: the table is always a heap, and every index is secondary, storing a tuple id. CLUSTER reorders a table once and does not maintain it.
Oracle heaps by default, with index-organised tables as an option.

The key lookup, and why a scan can beat a seek

🎓 The tipping point

A non-clustered index seek finds the key, but the row is elsewhere. To fetch a column the index does not contain, the engine follows the pointer — a key lookup (SQL Server) or bookmark lookup — which is a random read per row.

Random reads are far more expensive than sequential ones, so past roughly 1–5% of the table the optimiser correctly decides that scanning everything sequentially is cheaper than seeking and looking up each row. That is why "it has an index but it's doing a scan" is very often the optimiser being right — and why the real fix is usually to make the index cover the query so there is no lookup at all.

The lookup, and the INCLUDE that removes it.

-- ix_orders_status is (status, placed_at). This query also needs customer_id:
SELECT customer_id FROM orders WHERE status = 'shipped';  -- seek, then fetch the column
--  seek the index to find the rows, then ONE LOOKUP per matching row to fetch
--  customer_id from the table itself. A thousand matches, a thousand lookups.

-- Covered, so zero lookups:
CREATE INDEX ix_orders_status_cov ON orders (status, placed_at)  -- the key, for seeking
  INCLUDE (customer_id);                                         -- the payload, for reading

What “covering” means, precisely

An index is a narrow, sorted copy. If every column the query mentions is in that copy, the engine never touches the table — the index covers the query. If one column is missing, it must go back to the table once per row.
INCLUDE columns live only in the leaf level. They cannot be searched or sorted by, they do not bloat the upper levels of the tree, and they are exactly what a lookup would have fetched.
The lookup is called a key lookup (SQL Server), a bookmark lookup (older names) or a heap fetch (PostgreSQL). Seeing thousands of them in a plan is one of the most reliable performance diagnoses there is.
The cost is disk and write time: every UPDATE to customer_id now maintains this index too. Covering is a trade, not a free win.

Fill factor and fragmentation

Pages fill up. An insert or a widening update into a full page causes a page split: the page becomes two half-empty pages, and the index now occupies more space and takes more reads forever. Fill factor leaves free space in each page at rebuild time to absorb that.

⚠ Trap — the nightly rebuild nobody questions

Rebuilding every index every night was reasonable advice in 2005. Today: on SSDs, logical fragmentation barely affects random reads; the rebuild generates enormous log and cache churn; and — the part people miss — a rebuild is often only helping because it updates the statistics as a side effect. Updating statistics directly is far cheaper. Rebuild for a measured reason; do not rebuild because a maintenance plan wizard offered to.

Watch a seek become a scan, in the playground.

-- There IS an index on (customer_id, placed_at):
EXPLAIN QUERY PLAN SELECT * FROM orders WHERE customer_id = 7;   -- ask for the plan
-- SEARCH orders USING INDEX ix_orders_cust_date (customer_id=?)  ← it jumped straight there

-- There is NO index on total_cents:
EXPLAIN QUERY PLAN SELECT * FROM orders WHERE total_cents > 500000;  -- the same shape of query
-- SCAN orders   ← every row read. And an index would not help much here anyway.

Why the second one would not improve much even with an index

SEARCH versus SCAN is the whole vocabulary you need from SQLite's plan output. Everything else is detail.
An index helps when it eliminates most of the table. A predicate matching a large fraction of rows is better served by a scan: reading the index and then most of the table is more work than reading the table once.
That threshold is why the optimiser needs statistics (chapter 28), and why the same query can get two different plans for two different parameter values.

Index types that are not B-trees

Type	For	Where
Hash	Equality only — no ranges, no ordering	PostgreSQL, memory-optimised tables in SQL Server
GIN / inverted	Arrays, JSONB containment, full text	PostgreSQL
GiST / SP-GiST	Geometry, ranges, nearest-neighbour	PostgreSQL, PostGIS
BRIN	Huge tables physically ordered by the column — stores min/max per block range, tiny	PostgreSQL
Columnstore	Analytical scans and aggregates over hundreds of millions of rows	SQL Server, and the model behind every column-oriented warehouse
Full-text	Word and phrase search, ranked	All of them, differently

BRIN is the one worth remembering for an interview: an index on a billion-row append-only log, a few hundred kilobytes in size, that works only because the physical order matches the column order. It is a lovely illustration that "index" does not mean one thing.

An index is sorted and shallow. Sorted is why it answers ranges; shallow is why it scales.
A seek costs three or four page reads whether the table has a thousand rows or a billion.
A clustered index leaf holds the whole row: the table is that index, and there is one per table.
Every non-clustered index carries the clustering key, so a wide primary key inflates all of them.
PostgreSQL has no clustered index; every index is secondary and the table is a heap.
A key lookup is a random read per row. Past ~1–5% of the table, a scan is genuinely cheaper.
“It has an index and still scans” is usually the optimiser being right. Make the index cover the query.
Page splits fragment an index. Fill factor buys headroom; nightly rebuilds are mostly cargo cult on SSDs.
Hash, GIN, GiST, BRIN, columnstore and full-text exist. Reaching for the right one is a real skill.

Interview questions this chapter answers

How does an index make a query faster?

It is a sorted structure with a shallow tree over it, so finding a key is three or four page reads instead of scanning the table. Being sorted also lets it answer ranges, prefix matches and ORDER BY without a sort. The cost is that every write has to maintain it.

Clustered versus non-clustered?

A clustered index's leaf level is the table, so it defines physical order and there is one per table. A non-clustered index stores the key plus a pointer, so reading other columns costs a lookup per row. In PostgreSQL the distinction does not exist — every index is secondary.

There is an index on the column and the plan still shows a scan. Why?

Either the predicate is not sargable, or the optimiser has decided the seek plus a lookup per row is more expensive than a sequential scan — which is usually correct once the query returns more than a few percent of the table. If the query genuinely needs to be fast, make the index cover it so there is no lookup.