Storage · 13 min

Database indexes

Find one user among a million by reading 4 pages instead of 12,500. Build the index by hand, then see what it costs and why column order matters.

Your sign-up page has one rule: one account per email. Each time someone presses Sign up, the server runs SELECT * FROM users WHERE email = 'mio@mail.jp' to check the address isn’t taken.

With 200 users the answer is instant. Now the users table has a million rows, and the same query takes about a second. Nothing is broken. The database is doing exactly what you asked, the slow way.

In this article you build the fix by hand, one step at a time. By the end, the same question costs 4 page reads instead of 12,500, and you will know what you pay for that.

Why one email means reading every row

A users row (id, email, city, sign-up date and a few more columns) is around 100 bytes, so an 8 KB page holds about 80 rows. A million users fill about 12,500 pages.

The rows sit in the order people signed up, not by email. So the database has no idea where mio is. It reads page 1 and checks 80 emails, then page 2, and keeps going to the very end, because a second mio could be further on. This is a full table scan.

Reading a page from an SSD takes around 0.1 ms when it isn’t already in memory. 12,500 pages × 0.1 ms is about 1.25 seconds, for one sign-up. A second sign-up at the same moment does it all again.

Step 1: keep a sorted copy of the emails

A dictionary solves “where is this word?” by keeping words in order. Do the same, without touching the table: build a second list next to it, with every email in alphabetical order and the row id: the number that tells the database where that row is stored.

Now you can binary search. Look at the middle entry. If mio comes before it, throw away the second half; if after, the first half. Each look halves what is left, and a million entries shrink to one in 20 looks, because 2²⁰ is about a million.

Two problems remain. First, the copy lives on disk in pages too. An email plus a row id is about 40 bytes, so a page holds about 200 entries and the copy fills 5,000 pages. Of the 20 looks, the first 13 each jump to a different page (2¹³ = 8,192 is the first power of 2 past 5,000). The last 7 happen inside one page. So a lookup still reads about 13 pages.

Second, sign-ups. A new email belongs somewhere in the middle. In a packed, sorted list, everything after it has to shift along by one. That rewrites half the copy on average: 2,500 pages for every new user.

Step 2: stack signposts on top of the pages

Fix the shifting first. Leave some free room in every page, and let each page store the address of the next one. The pages can now sit anywhere on disk and still read in order. A new email goes into the one page where it belongs, and no other page moves.

Then fix the lookup. Make one extra page that lists the first email of every bottom page, with that page’s address. It works like the letter tabs on a dictionary’s edge. To find mio, read the tabs, see that one page starts at kenji and the next at riku, and open the kenji page. The rule: anything smaller than a signpost lives to its left.

If the tabs don’t fit in one page, do it again: a level of tab pages, and one page above that pointing at them. Stop when the top level is a single page. That top page is the root. The bottom pages, which hold the real entries, are the leaves.

Count it for a million users. Step 1 packed 200 entries into a page. Now each page keeps free room for new arrivals, so say each holds about 100. That also keeps the sums easy.

1. 1,000,000 emails ÷ 100 per page = 10,000 leaf pages.
2. Each leaf needs one signpost (its first email): 10,000 signposts ÷ 100 per page = 100 signpost pages.
3. 100 signposts fit in 1 page: the root.

So the tree has 3 levels, and finding mio reads 3 index pages, then 1 table page for her row. Inside each page, a binary search over 100 entries takes about 7 looks (2⁷ = 128). So the cost is 4 page reads instead of 12,500, and about 21 comparisons inside the index instead of a million.

It gets better. The root and the 100 signpost pages are used by every lookup, so they stay in the database’s memory. In practice a lookup often costs one disk read for the leaf and one for the row.

Step 3: a new user signs up

nana@mail.jp signs up. Her email travels down the tree like a lookup: root, signpost page, then the leaf where nana belongs, between mio and ren. If that leaf has room, she slides into place and that’s all.

If the leaf is already full, it splits:

1. Cut the full leaf into two half-full leaves. The lower half stays; the upper half moves to a new page.
2. Copy the first key of the new page up into the signpost page above, so lookups can find it. It is a copy, because the leaves must keep every real entry.
3. If that signpost page is now too full, split it the same way. This time its middle key moves up instead of being copied. Leaves must keep every real email, so they keep a copy. A signpost is only a pointer, so it can leave its page.
4. If the root itself splits, make a new root above the two halves. This is the only way the tree gets taller.

A split adds a page beside the old one, on the same level, never below it. Only a new root adds a level, and it sits above every leaf at once. So every leaf is always the same number of steps from the root. No lookup is ever unlucky. And a split rewrites 2 or 3 pages, not 2,500.

Step 4: ranges walk along the bottom

The next-page links in the leaves make a second kind of question cheap. Marketing wants everyone who signed up in March, and there is an index on the signup date.

Go down the tree once to the first March date, exactly like finding mio. Then read leaves left to right, following the links, until you meet an April date. Every entry on the way is a match, and they are all side by side. This is a range scan.

Its cost is the trip down plus however many leaves the answer fills. 30,000 March sign-ups at 100 per leaf is 300 leaf pages. Then each match points to its row, and those rows are spread through the table, so fetching them can take up to 30,000 more page reads. For big ranges, the rows are the expensive part.

Step 5: two columns in one index

The dashboard asks for “users in Osaka who signed up from March to June”. An index can be sorted by more than one column: first by city, then, inside each city, by signup date. That is a composite index on (city, signup). Here are the demo’s 12 users in that order:

All the Osaka entries sit together, in date order. So “Osaka, March to June” is one range: go down to Osaka 2024-03-01, then walk right until you pass Osaka 2024-06-30. “Everyone in Osaka” works too. It is the range from the first Osaka entry to the last.

This is the leftmost-prefix rule. A composite index on (a, b) can serve a query on a, or on a and b together, but not on b alone. Put the column your queries always filter on first. If you also need fast lookups by date alone, that is a second index, on (signup). And once a column is used as a range, the columns after it can’t narrow the search: an index on (signup, city) would walk every city’s March to June entries and throw away the ones that aren’t Osaka.

What every index costs

An index is not free, and every one you add costs a little more.

• Slower writes. Each sign-up writes the row and a key into every index on the table. With 4 indexes, that is 5 places to update, and now and then a split.
• More space. A million emails at about 40 bytes each is about 40 MB, more with the free room in the pages. The busy parts also want a place in memory.
• Not always used. Say a third of your million users live in Tokyo. Fetching their 333,000 rows one at a time can mean 333,000 page reads, while a full scan reads all 12,500 pages in order, which disks do much faster than jumping around. The query planner, the part of the database that decides how to run a query, then picks the full scan.

So index the columns your frequent queries filter on, and stop there.

Asking the database what it did

You don’t have to guess which plan the database chose. Put EXPLAIN in front of a query and PostgreSQL prints its plan. Look for Seq Scan, its name for a full table scan, versus Index Scan.

EXPLAIN SELECT * FROM users WHERE email = 'mio@mail.jp';
--  Seq Scan on users
--    Filter: (email = 'mio@mail.jp')

-- UNIQUE: also refuse a second row with the same email
CREATE UNIQUE INDEX users_email ON users (email);

EXPLAIN SELECT * FROM users WHERE email = 'mio@mail.jp';
--  Index Scan using users_email on users
--    Index Cond: (email = 'mio@mail.jp')

CREATE INDEX users_city_signup ON users (city, signup);

Back to the sign-up page

Put it together for a million users. Without an index, every “is this email taken?” reads 12,500 pages, about a second. With an index on email, it reads 3 index pages, two of them already in memory, plus one row: around 0.2 ms.

UNIQUE does the check for you, too. The database refuses a second row with the same email, using that same lookup. You pay with a little extra work on every sign-up and about 40 MB of disk.

For the dashboard, one (city, signup) index answers “everyone in Osaka” and “Osaka, March to June”. It can’t answer “everyone on 14 March”. That question needs its own index, or a full scan.