From 25,000 pages to 4

The query

The kind of thing every dashboard has: show a customer their last 20 paid orders. The table has three million orders from 50,000 customers. About 90% are paid and 1% refunded, on purpose, because that skew matters later. Customer 4242 ended up with 45 orders, 40 of them paid.

SELECT id, created_at, total
  FROM orders
 WHERE customer_id = 4242 AND status = 'paid'
 ORDER BY created_at DESC
 LIMIT 20;

For every index I ran EXPLAIN (ANALYZE, BUFFERS) five times and kept the median. I started out looking at milliseconds and switched to pages read pretty quickly. Time jumps around depending on what my laptop is doing and what's already cached. The number of pages a plan has to touch stays put.

All five at once

For scale, the table itself is 195 MB. The rest of the page goes through the rows one at a time.

01 · No index: read everything

No surprises here. Postgres reads the whole table, keeps the 40 rows that match, sorts them and hands back 20. My favourite line in the plan is Rows Removed by Filter: 2,999,961: three million rows read to keep forty. 60 ms doesn't sound bad, until a hundred people open the dashboard at the same time.

02 · An index on customer_id, and a Sort that stays

The index I'd have added first, honestly. Pages read drop from 25,114 to 48, and it's tempting to stop there. Then you read the plan:

Limit
  ->  Sort  (Sort Key: created_at DESC)
        ->  Bitmap Heap Scan on orders
              Recheck Cond: (customer_id = 4242)
              Filter: (status = 'paid')
              Rows Removed by Filter: 5
              ->  Bitmap Index Scan on idx_customer_id
                    Index Cond: (customer_id = 4242)

Still a Sort, still rows thrown away. It took me a minute to see why. The index only holds the customer id and the address of each row in the table. So it knows where 4242's orders are, but not which ones are paid or when they were placed. For that it has to go to the table anyway.

The other part I had to look up was the word bitmap. Postgres doesn't follow the addresses one by one. It first marks which table pages it needs, then reads those pages in the order they sit on disk, each one once. Cheaper reads, but whatever order the index had is gone by the time the rows come out. This is the picture that made it click for me:

With 40 rows the Sort is free. With a customer who has 200,000 orders it isn't, and LIMIT 20 doesn't save you: you can't know which 20 are the newest until you've looked at all of them.

03a · An index shaped like the query

CREATE INDEX ON orders (customer_id, status, created_at);

The way I think about it is a phone book sorted by three columns. Inside customer 4242 the entries are grouped by status, and inside "paid" they're already in date order. All 40 paid orders sit next to each other, sorted. Postgres goes straight to the newest one, reads 20 entries and stops.

No Sort, nothing removed by a filter, and exactly 20 rows read, because this time LIMIT actually gets to stop the scan. The rule I took from it: the columns you filter with = go first, the column you sort by goes after them.

03b · Same columns, wrong order

Then I put created_at first. Now the phone book is sorted by date, and 4242's orders are scattered through the whole thing, between everyone else's. I guessed Postgres would still use it, and it did. What I didn't guess was the price, because the plan looked perfectly fine:

Limit  (actual rows=20)
  Buffers: shared hit=6555
  ->  Index Scan using idx_created_at_customer_id_status on orders
        Index Cond: ((customer_id = 4242) AND (status = 'paid'))
        Buffers: shared hit=6555

Index Cond on both columns, same as 03a. If I'd only skimmed the plan I'd have called it done. The difference is that in 03a the condition tells Postgres where to jump, and here there's nowhere to jump. It starts at the newest order in the whole table and checks every entry, walking back in time until it has found 20 of 4242's. 6,555 pages, 285 times more than 03a, and the plan uses the same words for both. The page count was the only thing that gave it away.

Out of curiosity I asked for a customer that doesn't exist. LIMIT 20 never fills up, so nothing stops the scan: 14,781 pages, the entire index. Same query, same plan, and the cost depends on which customer you ask for. Postgres assumed each customer's orders are spread evenly over time, which is roughly true for the average one. For the customers who don't fit that, this is the slow page nobody else can reproduce.

04 · Never touch the table

03a still read 23 pages for 20 rows. About three to get down the index, then one table page per row, because the query asks for id and total and the index doesn't have them. So I added them:

CREATE INDEX ON orders (customer_id, status, created_at)
  INCLUDE (id, total);

Index Only Scan, Heap Fetches: 0, four pages. I put them in INCLUDE rather than in the key: those columns aren't sorted and can't be searched on, they just ride along in the leaf pages. For values the query only returns, that's enough, and it keeps the upper levels of the index smaller.

What the indexes cost

This one I didn't see coming. The index on customer_id alone is 20 MB. The three-column one is 116 MB, almost six times bigger, even though each entry is only a few bytes wider. The reason is deduplication. Each customer id shows up about 60 times, and Postgres stores a repeated key once with a list of row addresses after it. Add a timestamp and almost every entry is unique, so there's nothing to squash: three million full entries. With the INCLUDE columns it's 168 MB, not far off the 195 MB table.

And every insert and update pays to keep all of that in order. I haven't measured how much yet.

What this isn't

It's one query, made-up data, my laptop, and everything already in memory. The small millisecond numbers are mostly noise, which is why I lean on page counts. Real tables are skewed in ways this seed isn't, and that moves 03b the most: a customer whose orders are all recent gets lucky, one whose orders are all old pays for nearly the whole index.

Part 2, when I get to it, is about where indexes don't help: a filter that matches 90% of the table, a function wrapped around a column, deep OFFSET pagination, and the cache people put in front of all of it.

Where this came from

"I'd check the execution plan and look for a missing index" is something I've said in interviews without ever having watched it happen on a big table. So I built this to see it for myself. The queries, the seed script and every measurement are in the repo if you want to run it.