What an index costs and buys
How an index turns a search through millions of rows into a few steps, and what every write pays for it.
5 minute lesson
Finding one row among ten million
Without help a database finds a row the hard way: it reads every row and checks it. That is a full table scan. An index is a second structure, sorted by one column, that leads straight to the matching rows, like the index at the back of a book.
- Full scan10,000,000 rowsread and checked
- IndexA few stepsdown a sorted tree
- index
- A separate structure, kept in order, that lets the database find rows by a column without reading the whole table.
- full table scan
- Reading every row of a table to find the ones that match.
Key terms
A users table has 20 million rows and no index on the email column. A login looks a user up by email.
What does the database have to do?
- Read rows until it has checked the whole table
- Jump to the row, as the emails are unique
- Reject the query, as an index is missing
- Sort the table first and search it after
Show the answer
- Read rows until it has checked the whole table
Nothing tells the database where an email is, so it reads rows and compares, in the worst case all 20 million, on every login. An index on email keeps the addresses sorted with a pointer to each row, and the same lookup takes a handful of steps.
Without an index a lookup is a scan of the table. With one it is a few steps.
Every write pays for every index
An index is a copy of a column, kept sorted. The database has to keep it in step with the table. So each insert, and each update of an indexed column, writes to the table and to every index on it.
- No index1 write per insert
- 5 indexes6 writes per insert
A table receives 5,000 inserts a second. Over the years twelve indexes have been added to it.
What does that mean for each insert?
- It writes to the table and to twelve indexes
- It writes to the table, and the indexes follow later
- It gets faster, as the indexes find the free space
- It writes to the one index that the query names
Show the answer
- It writes to the table and to twelve indexes
Every index has to contain the new row at once, or queries using it would miss the row. So one insert becomes thirteen writes, 5,000 times a second. Each index made some read faster and every write slower. On a table that is written far more than it is read, that trade can turn against you.
An insert updates every index on the table. Indexes are paid for by writes.
Which columns deserve one
- Columns that queries filter by: the email at login, the customer of an order.
- Columns that tables are joined on, usually the foreign keys.
- Columns that results are sorted by, when the list is long.
Indexes make reads faster. Why not put one on every column?
Show the answer
Because every index is a sorted copy that the database must update with each write to the table. Ten indexes turn one insert into eleven writes. They also take disk and memory. An index earns its place only if queries really use it and it narrows the search to few rows, so indexes are added for real queries and unused ones are removed.
Recap
- An index is a sorted structure that finds rows in a few steps where a scan reads them all.
- Each index is updated on every write, and takes space. Reads get faster, writes slower.
- Index what queries filter, join and sort by. Remove indexes that nothing uses.