How the database finds things fast

Pick up a big textbook and try to find every page that mentions "photosynthesis". You could read all 500 pages from start to finish. That works, but it's slow. Or you could turn to the index at the back, find "photosynthesis: pages 42, 87, 233", and jump straight there.

Databases face the same choice. Reading every row in a table is called a full table scan. It's fine for 20 books, but painful for 20 million.

So a database can keep an index on a column. An index is a sorted list of that column's values, and each value points to where its rows live. If there's an index on genre, a search for Fantasy books jumps straight to the right rows.

Remember the planner from the last lesson? This is exactly the kind of choice it makes: "There's an index on genre, so I'll use it instead of reading every row."

Indexes aren't free, though. Just as a textbook's index has to be updated whenever pages change, the database has to update an index every time you add or change a row. So you add indexes to the columns people search on a lot, not to every column.