Indexes

A few months after launch, Tiffin's kitchen tablets start to lag. A new order used to appear within a few seconds; now it sometimes takes fifteen. Nothing in the code has changed. The orders table has just grown from a few thousand rows to two million.

The culprit is one query, run 160 times a second by tablets asking for new orders. On launch day it took 2 milliseconds. Now it takes 2 seconds. In this lesson we'll see why, and how one line of SQL brings it back to 2 milliseconds.

Without an index, the database reads everything

Here's the query:

SELECT id, total_paise, created_at
FROM orders
WHERE restaurant_id = 42 AND status = 'placed'
ORDER BY created_at;

The database stores the orders table as rows packed into pages (8 KB blocks in PostgreSQL), in roughly the order they were inserted. Nothing about that layout groups restaurant 42's orders together.

So to find them, the database has only one option: read every page, look at every row, and keep the ones that match. This is called a sequential scan or full table scan.

Let's put numbers on it. Say an orders row is about 250 bytes. Then:

• 2,000,000 rows x 250 bytes = 500 MB to read.
• At around 32 rows per 8 KB page, that's about 62,000 pages.
• Checking 2 million rows takes real CPU time even when everything is cached in memory, and much longer if the pages have to come from disk.

All of that work to return perhaps 3 rows. That's roughly where 2 seconds comes from. Worse, at 160 of these a second, the scans pile on top of each other, and every other query on the server slows down too.

And it gets worse every day, because the table keeps growing. A full scan's cost is proportional to the size of the table.

An index is a sorted lookup

The fix is an index: a separate structure, kept up to date by the database, that stores some columns in sorted order with a pointer to each row.

Think of the index at the back of a cookbook. To find every recipe with paneer, you don't read all 400 pages. You flip to "P" in the index, find "paneer", and get a list of page numbers. The index is sorted, so finding "paneer" is fast, and it tells you exactly where to go.

CREATE INDEX orders_restaurant_status_created
  ON orders (restaurant_id, status, created_at);

Under the hood, PostgreSQL (like almost every relational database) stores this as a B-tree: a wide, shallow tree of sorted pages. Each page holds hundreds of keys, so even a table of billions of rows is only 3 or 4 levels deep. We'll look inside B-trees in Module 19. For now, what matters is the cost.

That's the whole magic: the cost stops depending on how big the table is, and depends on how many rows you actually want.

The order of columns matters

Our index has three columns: (restaurant_id, status, created_at). The database sorts by the first column, then by the second within that, then the third. Like a phone book sorted by surname, then first name.

restaurant_id | status    | created_at
42            | accepted  | 20:01:10
42            | accepted  | 20:03:44
42            | placed    | 20:05:13   <- start here
42            | placed    | 20:06:02
42            | placed    | 20:07:30   <- stop here
42            | ready     | 19:58:21
43            | accepted  | 20:00:05

For our query, the database jumps straight to (42, 'placed'), reads the matching entries, which are already in created_at order, and stops. No sorting needed.

This gives you the leftmost prefix rule: a multi-column index can be used for any query that filters on its first column, or its first two, or all three. But not for one that skips the first.

A good rule for ordering columns: columns you filter with = first, then the one you sort or filter by range last.

Ask the database what it's doing

You never have to guess whether an index is used. Put EXPLAIN ANALYZE in front of the query and the database shows its plan and real timings.

Before the index:

Sort  (actual time=2104.3..2104.3 rows=3)
  ->  Seq Scan on orders  (actual time=0.02..2104.1 rows=3)
        Filter: ((restaurant_id = 42) AND (status = 'placed'))
        Rows Removed by Filter: 1999997
Execution Time: 2104.6 ms

After:

Index Scan using orders_restaurant_status_created on orders
      (actual time=0.03..0.05 rows=3)
  Index Cond: ((restaurant_id = 42) AND (status = 'placed'))
Execution Time: 0.08 ms

"Seq Scan" with "Rows Removed by Filter: 1999997" is the giveaway. Two million rows read, three kept. Most slow query investigations end with spotting a line like that.

Indexes aren't free

If indexes are so good, why not index every column? Because each one has costs.

• Writes have to update the indexes. Inserting one order with five indexes on orders means one table write plus five index writes, and an update that changes an indexed column touches those indexes too. On a table with heavy writes, too many indexes slow everything down.
• They take space. An index can be 20% to 100% of the size of the table, and to be fast it needs to fit in memory alongside your hot data.
• Unused ones still cost. An index nobody queries still pays the write and space cost forever.

So index for the queries you actually run. A good default for Tiffin:

PostgreSQL automatically indexes primary keys and unique constraints. It does not automatically index foreign keys. orders.customer_id referencing customers gives you no index unless you create one. That surprises a lot of people, especially those coming from MySQL, whose InnoDB engine does create one.

SELECT * FROM orders
WHERE customer_id = 881
  AND restaurant_id = 42
  AND created_at > now() - interval '30 days'
ORDER BY created_at DESC;