A product page loads in 40 ms. A search for one seller's products takes four seconds, and while it runs the product pages slow down too. The table has two hundred thousand rows, and the database is reading every one of them to answer the search. An index is what lets it read a few.
What an index is
A table is stored on pages, each holding about a hundred rows, in the order the rows were added. (That's PostgreSQL's way; MySQL's InnoDB keeps rows sorted by primary key instead, but a search on any other column is no better off.) To find the rows with seller = 123, the only way without an index is to read every page and check each row: a scan, whose cost grows with the table. Two hundred thousand rows on two thousand pages means two thousand page reads, however few rows match. A scan also keeps the database's cores busy, which is why it slows every other query beside it.
An index is a second structure, kept sorted by a column, with one entry per row and a pointer to the row's page. Most databases build it as a B-tree: a shallow tree where a lookup walks two levels for a thousand rows and still only four for a billion. Index entries are small, so an index page holds hundreds of them.
| Without an index | With an index | |
|---|---|---|
| Find rows by a column | Read every table page | Walk the tree, then read the pages the matches are on |
| Cost grows with | The size of the table | Barely at all, plus one page per match |
| Cost of an insert | Write the row's page | Write the row's page and a page in every index |
So an index trades writes for reads. It's worth it when a column is searched far more than the table changes. The labs below use a real table, build real indexes over it and count the pages each search reads. They count pages, weighing a page reached at random as about four read in order (as PostgreSQL's random_page_cost does), and leave out the rest of what a real planner weighs.
Scan or look up
The table is 200 000 products on 2 000 pages, and a seller has about 40. Add an index on the seller column.
The right columns, in the right order
An index covers columns, and it only helps the searches that use them. Take products from one brand in a price range: about 40 rows.
Common values and rare ones
An index only wins when a search returns a small share of the table. Selectivity is the fraction of rows a condition matches, and a selective condition matches few of them. A status column where nine in ten rows have the same value has an index the planner won't use for that value, though it will use it for the rare ones.
Indexes that can't be used
Some searches can't use the index you have, and the lab says why. Most have a fix, usually a different index.
Everything in the index
An index that holds every column a query needs can answer it without reading the table at all: a covering index, shown as an index-only scan.
Searching text and places
A B-tree finds rows by how a value starts, so LIKE '%dragon%' scans the table. Text search uses an inverted index: for every word, the list of documents that contain it. A search for two words reads two lists and intersects them, and a ranking (how often a word appears in a document, how rare it is overall) orders the result. Most systems keep it in a separate search engine such as Elasticsearch, fed from the database by change data capture, which reads the database's log of committed changes and updates the index a second or so later. So search lags the database a little, a post just published may not be findable for a moment, and the database stays the record: a lost index is rebuilt from it.
Places need another trick, since "near this point" has two dimensions and an index sorts in one. A geohash turns a latitude and longitude into a string in which nearby points mostly share a prefix: each character narrows the cell, and 6 characters give a cell about 1.2 km by 0.6 km. Search the cell and its eight neighbours, since a point just across a cell's edge has a different prefix, then measure the exact distances. A quadtree splits busy areas into four, again and again, so a city gets small cells and an ocean one big one. Uber's H3 divides the globe into hexagons instead, at fixed sizes per level: a set grid rather than one that adapts to how busy an area is.
Two ways to store a table
Everything so far assumed a B-tree, which keeps rows sorted in pages and changes a page in place. Many write-heavy stores (Cassandra, RocksDB and the key-value stores built on it) use a log-structured merge tree (LSM tree) instead: a write goes to the write-ahead log (an append-only record on disk, so a crash can't lose it; Durability covers it) and an in-memory table, the in-memory table is written to disk as a sorted file when it fills, and background compaction merges the files and drops overwritten values.
| B-tree | LSM tree | |
|---|---|---|
| A write | changes a page in place, somewhere on disk | appends, so writes are cheap and sequential |
| A read | one path down the tree | may check the in-memory table and several files |
| Background work | little | compaction, which takes disk and CPU |
To keep a read from opening every file, each file has a Bloom filter: a small array of bits that answers "not in this file" or "maybe in this file". A no is right every time, so most files are skipped; with about 10 bits per key, about 1% of the keys a file doesn't hold still get a maybe, and each costs one wasted look. A filter tests one key at a time, so it can't help a range read, which still opens every file whose keys overlap the range.
The price of an index
Each index is another structure that every insert and update has to write to, and it takes space. Look at the line under the index builder in any lab above: every index you add makes every insert touch one more page. Index every column and writes pay for all of them.
That's the case for choosing indexes on purpose: the columns the slow queries use, in the order they use them, found by looking at which searches are slow, and not an index on every column in case.
Deep dives
| They ask | What to say |
|---|---|
| A query is slow | Look at its plan: is it scanning? Add an index on the columns it filters by |
| Which columns to index | The ones in frequent WHERE and ORDER BY clauses, where the condition is selective |
| A write-heavy table | Fewer indexes, since each is paid for on every write |
| Searching text | A full-text or inverted index, not LIKE; an index maps each word to its rows |
| Reads are heavy | Add read replicas, and still index: a replica doesn't make a scan fast |
| An index isn't used | Check selectivity, column order, a function on the column, and stale statistics |
In the wild
The ideas in this chapter, and where you'll meet them in real systems and interviews:
| Idea | Where you'll meet it |
|---|---|
| B-tree indexes | The default index in PostgreSQL and MySQL |
| Seeing a plan | EXPLAIN in both, which shows whether a query scans or uses an index |
| Composite and covering indexes | CREATE INDEX ... (a, b) and INCLUDE columns |
| Inverted indexes for text | Elasticsearch and Lucene, and PostgreSQL's GIN indexes |
| Searching by place | Redis's GEO commands (a geohash under the hood), Elasticsearch's geo queries, Uber's H3 |
| LSM trees and Bloom filters | RocksDB, Cassandra and LevelDB |
Your practice
Three searches matter on Inkwell Shop's catalog, and every index makes every insert touch another page. Find the fewest indexes that keep each search fast.