Indexes from the inside
An index is the most powerful speed tool a database has, and also the most misused. This lesson opens one up, so you can see why one query drops from 34 ms to 2 ms while another ignores the index completely.
By the end you can
- Explain what an index is in one sentence, and why a lookup takes about 4 page reads even in a table of millions
- Read the four ways Postgres can scan a table, and know when each one wins
- Choose the column order of a composite index for a real query
- Pick the right special index: covering, partial, expression, unique, GIN or BRIN
- Write queries an index can serve, add an index without blocking writes, and find indexes nobody uses
The everyday picture
Think of a thick paper dictionary. To find "mango", you do not read from page 1. You open near the middle, see you are in "k", jump forward, land in "m", and narrow down in two or three moves. The words are sorted, so each look throws away most of the book.
Now think of the index at the back of a textbook. The chapters are written in their own order. The index is a separate list, sorted by topic, and each entry gives you a page number. You look up "photosynthesis", read "page 212", and go straight there.
A database index is the second kind. The table keeps its rows in the order they arrived. The index is a separate, sorted list of one column's values, and each entry points to where the row lives. It is sorted like the dictionary, so finding an entry takes a few jumps instead of a full read.
What an index actually is
Postgres stores a table as a file of pages, 8 KB each. New rows go wherever there is free space, usually at the end. This file is called the heap, because the rows are in no useful order. Every row has an address, the ctid, written as (page, slot), such as (36573,66).
Without an index, the only way to find "sale id 3,913,377" is to read every page and check every row. That is a sequential scan. For a year of sales from 300 stores (4.4 million rows, 40,935 pages, 320 MB) that means reading all 40,935 pages.
An index is a separate sorted structure that maps column values to row addresses. It is a second file, kept up to date on every insert, update and delete. Because it is sorted, Postgres can search it like the dictionary, find the ctid, and read exactly one heap page.