SQL → index design → fast queries
A free online book by Markus Winand that teaches indexing from the developer's side: why the leftmost-prefix rule exists, how ORDER BY uses an index, and the traps that make an index useless.
Caching & Databases · lesson 2 of 8 · about 25 min
Indexes
What an index really is, why a lookup takes four page reads in a table of a billion rows, when the database ignores your index, and why every extra index slows your writes. Tap any for a plain-language card.
0 / 10 sections done
- 1The pain: scanning every row2 min
- 2The idea: the index at the back of a book3 min
- 3Sorted + halving = fast search3 min
- 4How an index is built (B-tree)3 min
- 5Will the planner use it?4 min
- 6What an index costs on writes3 min
- 7The index family2 min
- 8Who lives by this1 min
- 9Interview angle2 min
- 10Break It: index everything1 min
The pain
“Find user with this email.”
A table is stored as a long run of pages on disk, each holding about 100 rows. With no , the database has no idea where one email lives, so it reads every page and checks each row. That is a .
Each square below is a slice of the table. Choose a table size, run the scan, then run the same lookup using an index.
The table grows 10,000 times. The scan does 10,000 times more work. The index barely notices.
Each square ≈ 5 pages (500 rows).
Pages read0
Time0 ns
Rows checked0
Pick a size and a method, then press Find the row.
The idea, before any database
The index at the back of a book.
A database is exactly this: a second, sorted list that says “value → where it lives”. It costs extra paper (space), and every time a page of the book changes, the index must be updated too. That is the whole bargain: faster searching, slower and costlier changing.
This book has 30 pages. Pick a word and find it both ways.
The book never changed. We only added a sorted list at the back, and the work dropped.
1redis · disk · index
2ram · lsm · lsm
3wal · kafka · index
4index · cache · lsm
5ssd · btree · index
6btree · ssd · lsm
7cache · index · index
8kafka · wal · lsm
9lsm · ram · index
10disk · redis · lsm
11redis · disk · index
12ram · lsm · lsm
13wal · kafka · index
14index · cache · lsm
15ssd · btree · index
16btree · ssd · lsm
17cache · index · index
18kafka · wal · lsm
19lsm · ram · index
20disk · redis · lsm
21redis · disk · index
22ram · lsm · lsm
23wal · kafka · index
24index · cache · lsm
25ssd · btree · index
26btree · ssd · lsm
27cache · index · index
28kafka · wal · lsm
29lsm · ram · index
30disk · redis · lsm
Index (back of the book)
- btree5, 6, 15, 16, 25, 26
- cache4, 7, 14, 17, 24, 27
- disk1, 10, 11, 20, 21, 30
- index1, 3, 4, 5, 7, 9…
- kafka3, 8, 13, 18, 23, 28
- lsm2, 4, 6, 8, 9, 10…
- ram2, 9, 12, 19, 22, 29
- redis1, 10, 11, 20, 21, 30
- ssd5, 6, 15, 16, 25, 26
- wal3, 8, 13, 18, 23, 28
Pages read0
Pages that mention it6
Methodfull scan
Press the button. Watch how many pages get read.
Why sorted order matters
Search by halving. But inserting hurts.
16 items need at most 4 checks. A billion items need only about 30. Try finding a number both ways, and also try a number that is not in the list.
The catch: to keep the list sorted, a new number has to be squeezed into its place, and everything after it must shift along. Press Insert and count the moves. In a table of millions of rows that would be disastrous, which is why databases store the sorted data as a tree (next scenes) with gaps for new entries.
Sorted = fast to search, slow to change. Trees try to give you both.
381217212631374248535964707783
Items16
Checks made0
Worst case by halving5
Pick a method and press Search. Cells shaded gold are still possible; grey have been ruled out.
| Sorted items | One by one (worst) | Halving (worst) |
|---|---|---|
| 1,000 | 1,000 checks | 10 checks |
| 1,000,000 | 1,000,000 checks | 20 checks |
| 1,000,000,000 | 1,000,000,000 checks | 30 checks |
How an index is built
A short, wide tree of sorted pages.
Most databases build the index as a . Every page holds keys in sorted order plus signposts to the pages below. To search, start at the root and follow the signposts, one page per level.
Pick a key and search. This toy tree has 3 levels, so every search reads 3 pages, whether it holds 27 keys or, as you will see below, billions.
It is the index at the back of a book: jump to the right letter, then the right page, then the word.
Choose a key and press Search.
How tall is a real tree? A page holds hundreds of keys, so the tree stays very short.
root1 pages
level 2400 pages
leaves200,000 pages
Levels3
Pages per lookup4
Top levels hold200,401 pages
The top 3 levels are only 200,401 pages (about 1566 MB at 8 KB each), so they sit permanently in RAM. A lookup usually costs one real disk read. Index total: 200,401 pages.
Will it use my index?
Having an index isn't the same as using it.
The picks the cheapest plan it can find. Whether an index qualifies depends on the columns, their order, how many rows match (), and whether your SQL leaves the column bare.
The table has 5 million orders. Switch indexes on and off, and pick queries. Look for the surprises: an index that exists but is ignored, and a query that gets .
Remember : an index on (customer_id, created_at) helps customer_id alone, never created_at alone.
Try query 5, then press the rewrite button. Same question, 100× different cost.
SELECT * FROM orders WHERE customer_id = 42;
Seq Scan on orders
using none (reads all 62,500 pages)
No index starts with customer_id.
Rows examined5,000,000
Estimated time1 s
vs no indexessame
Indexes on this table: 0. Each one is also updated on every insert (next scene).
The bill for an index
Reads get a shortcut. Writes pay for it.
An index is a second copy of some columns, kept sorted. Inserting into a sorted structure is not free. If the right page is full, it must in two and update its parent: three page writes instead of one.
Try inserting keys in order (like an auto-increment id) and at random (like a UUID). Compare splits and how full the pages are.
Then see the bigger bill: every index on a table is its own tree, updated on every write.
Appending in order fills pages neatly. Random keys land everywhere, split pages half-empty, and scatter writes across the disk.
102030
405060
Inserts0
Page splits0
Page writes0
Pages 75% full2
Insert some keys. Gold keys are the newest.
Every index is another tree. One inserted row must be written into the table and into each index.
table
idx 1
idx 2
idx 3
Page writes for this one insert: 4 (1 table + 3 indexes), more if any page splits.
The index family
B-tree is the default. Know the others.
Interviewers love “which index would you use?” Tap a card for an example and the catch. Open at least four.
If you can say “composite, with the equality column first and the range column second”, you have answered half of every indexing question.
Who lives by this
Indexing is daily work.
Index design is one of the highest-leverage skills in backend engineering. A few real references and practices.
build a shadow table → copy rows → swap
On very large MySQL tables, adding an index with a plain ALTER can block writes for hours. GitHub built gh-ost, an online schema-change tool that builds the new structure on the side and swaps it in.
partial and functional indexes in Postgres
In an early engineering post about scaling on Postgres, Instagram described partial and functional indexes, indexing only the rows a query cares about, to keep indexes small and fast.
CREATE INDEX CONCURRENTLY → slower build, no write lock
Postgres can build an index while the table keeps taking writes, at the cost of extra scans and time. It is the safe default for production tables.
Interview angle
What interviewers actually ask.
Six questions, each worth 20 XP. Expect “why is this query slow?” and “what would you index?”.
Answer index questions in three parts: what the query filters and sorts on, which index fits, and what it costs on writes.
Question 1 / 6
A table holds 100 million rows and has a B-tree index on user_id. Roughly how many index pages must be read to find one user?
Tip: press 1 to 3 to answer, Enter for the next one.
Break It
“Just index every column.”
An events table ingests data all day. Someone adds an index “in case we query it”, then another. Each insert must now update the table and every .
The disk can do about 40,000 random page writes per second. Every index adds one more per insert. Choose how many indexes and how many inserts per second arrive, then run 20 seconds of traffic. (Illustrative model.)
Index what you actually query. Each index you do not use is pure write tax.
Inserts arriving6,000/s
Table can absorb4,444/s
Page writes needed54,000/s
Write backlog: 0 rows waiting · each new write waits ~0 ms · time 0 s
Press Run. A growing backlog means writes are arriving faster than the table can absorb them.