Index deliberately

What you will be able to do

Make each slow query fast with one index that fits it, and measure what the index costs. Do not add an index because someone might search a column one day.

Before you startWhat to know and to have readyAbout 55 minutes

What you need to know

• How to read a plan: Seq Scan, Index Scan, estimated and actual rows, from Read a query plan.
• CREATE INDEX CONCURRENTLY and the -- migrate: no-transaction line, from Migrations.
• Foreign keys and what a delete does to the child rows, from Integrity constraints.

What you need on your computer

• The project after the last lesson, with scripts/explain.py and bench-before.json. python -m pytest prints 79 passed.
• PostgreSQL running, with the large data loaded.

This lesson adds one migration, migrations/008_ticket_list_indexes.sql.

A phone book

A printed phone book is sorted by family name, then by first name. To find “Garcia, Hugo”, you open it near G, then look for Hugo among the Garcias. It takes seconds. Now find every person called Hugo. The book cannot help: the Hugos are spread over every letter, so you read the whole book.

The order of the sort decides which questions are fast. A second book, sorted by first name, would make the Hugos fast. But it costs paper, and when a person moves, both books need a change.

The problem: three full scans, and a guess

The last lesson found the slow parts of the ticket list. Three queries read whole tables to find a few rows. The list itself took 11.0 ms. The latest AI run of a ticket took 8.3 ms, 20 times per page. Its messages took 9.4 ms. Tomás still wants an index on every column. “Indexes make reads fast. More indexes, more speed.”

Mei has two questions. Which index makes each query fast? And what does each index cost? She answers both with measurements.

The idea: an index is a sorted copy

An index is a separate, sorted copy of one or more columns of a table. Each entry points to its row. PostgreSQL’s usual kind is the B-tree, a tree of pages that finds any value in a few steps. Because the entries are sorted, the database can jump to the first match and read on in order. That is the phone book.

An index on one column is a single-column index. An index on several columns is a composite index. It is sorted by the first column, then by the second inside each value of the first, and so on. So, like the phone book, it helps a query that fixes its first columns. An index on (status, team) finds “open, billing” at once. It cannot find “every billing ticket” quickly, because billing tickets sit under every status.

Here is a tiny worked example: the 8 open billing tickets of the small data, and the newest 3 of them (LIMIT 3). Compare two indexes:

The same 8 open billing tickets in two indexes. Both find the group at once; only the second also has it in the order the list needs.

Text description of the diagram

The left index is on (status, team). The 8 entries for open, billing sit together. Inside the group, they keep the order of the table: T-30002 first and T-30197 last. To return the newest 3, the database reads all 8, sorts them by time and keeps 3. The right index is on (status, team, created_at DESC, ticket_id DESC). The same 8 entries sit together, newest first. T-30197 (8 October, 14:47), T-30179 (6 October, 12:43) and T-30177 (6 October, 12:24) come first, then the other 5. The database reads the first 3 entries and stops. There is nothing to sort.

With 8 tickets, the difference is 8 reads against 3. With 76,160 closed shipping tickets on the large data, it is 76,160 rows fetched and sorted against 20 entries read. So the rule for a composite index is this. First come the columns that the query compares with =. Then come the columns of its ORDER BY, in the same order and direction. For the ticket list, that is (status, team, created_at DESC, ticket_id DESC).

Larkfield’s candidates, measured

Mei does not trust the rule alone. She measures six candidate indexes for the ticket list on the large data, one at a time, with two pages. “Open billing” has 1,659 matching tickets; “closed shipping” has 76,160. The explorer shows four of the candidates, next to no index. Predict first, then try them:

Explore

Five ways to index the ticket list

Time

11.0 ms

Pages read (8 kB each)

17,275

Rows looked at

300,000

Index size

no index

No index: three processes read every row of tickets, about 100,000 each. They keep the 1,659 open billing tickets, sort them, and the Limit returns the newest 20.

Open billing tickets (status=open&team=billing), no index: the steps in the order they run

#	Step	Rows expected	Rows found
1	Seq Scan Reads all 300,000 rows of tickets in 3 processes, and keeps the 1,659 that match the filter.	1,603	1,659
2	Sort Each process sorts its own rows by created_at DESC, ticket_id DESC. It must see every row before the first one can go out.	–	–
3	Gather Merge Merges the sorted rows of the 3 processes into one ordered list.	–	–
4	Limit Returns the first 20 rows and stops.	–	–

The steps and rows are from EXPLAIN (ANALYZE, BUFFERS) on the large data (300,000 tickets). The time is the median of 5 runs on the course's computer, with nothing else busy; your times will differ. "Rows expected" is the planner's estimate before the query runs; it moves a little from run to run.

The ticket list query (SELECT * … LIMIT 20) on 300,000 tickets, with one index at a time. Steps and rows from EXPLAIN (ANALYZE, BUFFERS); times are medians of 5 runs on the course's computer.

Text description of the explorer

The explorer has two controls. The first picks the index on tickets: no index, (status), (status, team), (created_at) or (status, team, created_at, ticket_id). The second picks the page: open billing tickets or closed shipping tickets. A table shows the steps in the order they run, with the rows expected and found. A readout shows the time, the pages read, the rows looked at and the index size.

Open billing. No index: 11.0 ms, a full scan of 300,000 rows. (status): 1.39 ms; it finds 7,216 open tickets, removes 5,557 and sorts 1,659. (status, team): 0.515 ms; it finds 1,659 and sorts them. (created_at): 0.028 ms; it walks newest first, looks at 126 tickets and stops at 21. The composite index: 0.013 ms; it reads 20 entries.

Closed shipping. No index: 16.1 ms. (status): 15.5 ms; the planner ignores the index and reads the whole table. (status, team): 10.4 ms; it finds 76,160 tickets, then fetches and sorts all of them. (created_at): 0.275 ms; it looks at 2,080 tickets. The composite index: 0.012 ms; it reads 20 entries.

Index sizes: (status) 2.0 MB, (status, team) 2.1 MB, (created_at) 6.4 MB, the composite index 17.1 MB.

What the measurements say:

• (status) helps the open page, 1.39 ms. For the closed page, the planner does not use it at all. 85% of the tickets are closed, and jumping to 254,364 rows one by one costs more than reading the table in order.
• (status, team) finds exactly the right group. But the group is not in date order, so the database fetches all 76,160 closed shipping tickets and sorts them, to keep 20. That page goes from 16.1 to only 10.4 ms.
• (created_at) is a surprise: 0.028 and 0.275 ms. It walks the tickets newest first, and open tickets are recent, so it finds 20 quickly. That speed depends on the data. For a page whose tickets are old or rare, the walk gets long.
• The composite index reads 20 entries for any page: 0.013 and 0.012 ms, the same for 1,659 or 76,160 matches. It is also the largest: 17.1 MB.

The course also measured the right columns in the wrong order, (created_at DESC, status, team): 0.026 and 0.042 ms, 11.8 MB. It behaves like (created_at) alone. The first column sets the order, so the database still walks by time and checks each ticket. The chart puts each candidate’s size next to its time on the harder page:

• No index
• Composite index
• Other candidates

Size of each candidate index against the time of the closed shipping page (76,160 matching tickets), on the large data. Medians of 5 warm runs; index sizes from pg_relation_size.

Text description of the chart

A scatter chart. Each point is one index candidate. The horizontal axis is the index size in MB, the vertical axis the time of the closed shipping page in ms. No index: 0 MB, 16.111 ms. (status): 2.01 MB, 15.515 ms. (status, team): 2.05 MB, 10.441 ms. (created_at): 6.44 MB, 0.275 ms. The composite index (status, team, created_at, ticket_id): 17.06 MB, 0.012 ms.

The small indexes, near 2 MB, save little on this page. The time falls to almost zero only for the indexes that give the rows in date order. The composite index is the largest and the fastest, and it does not depend on luck in the data. Mei keeps it.

Migration 008: one index per measured query

The other two slow queries need simpler indexes, by the same rule. “The latest AI run of a ticket” compares ticket_id and orders by created_at DESC. “The messages of a ticket” compares ticket_id. So migration 008 has three indexes:

migrations/008_ticket_list_indexes.sql (from line 7)

-- CONCURRENTLY builds an index without blocking writes; it cannot run in a transaction.
CREATE INDEX CONCURRENTLY IF NOT EXISTS tickets_queue_idx
    ON tickets (status, team, created_at DESC, ticket_id DESC);
CREATE INDEX CONCURRENTLY IF NOT EXISTS ai_runs_ticket_idx
    ON ai_runs (ticket_id, created_at DESC);
CREATE INDEX CONCURRENTLY IF NOT EXISTS messages_ticket_idx
    ON messages (ticket_id);

The first line of the file is -- migrate: no-transaction, and lines 2 to 6 explain each index. CONCURRENTLY builds an index while the API goes on writing, as Migrations explained. On the large data, the rehearsal took 0.97 s for all three, and no read waited.

After 008, the course measured the three queries again (medians of 5):

Query	Before 008	After 008	Plan after
The open billing page (Module 3 query)	11.0 ms	0.013 ms	Index Scan using tickets_queue_idx, 17 pages
The latest AI run of one ticket	8.3 ms	0.004 ms	Index Scan using ai_runs_ticket_idx, 4 pages
The messages of one ticket	9.4 ms	0.006 ms	Index Scan using messages_ticket_idx, then a sort of 3 rows

The ticket list endpoint, still with the 41 queries of Module 3, went from 375 ms to 13.3 ms median under the same workload. The next lesson takes it further.

Indexes also make deletes fast

Remember the delete rules of Integrity constraints. When a ticket is deleted, PostgreSQL must check every table that points to it: are there messages, AI runs, files? Each check is a query on the child table, by ticket_id. A foreign key does not create an index on the child’s column. So, without one, each check is a full scan.

The course deleted one ticket (in a transaction that it rolled back) before and after 008:

Foreign-key check	Before 008	After 008
messages_ticket_fk	21.48 ms	0.02 ms
ai_runs_ticket_fk	18.67 ms	0.1 ms
attachments_ticket_fk	3.91 ms	2.08 ms
The whole DELETE	46.52 ms	2.23 ms

Mei made the indexes of 008 for reads, and they made the delete 20 times faster as a side effect. attachments still has no index on ticket_id, and its check still scans. For one ticket, that is a few milliseconds. In Recovery and retention, the erasure of the business customer C-3835 deletes 4,322 tickets at once. It takes 7.7 s without that index, 0.39 s with it. So that lesson adds it. Index the referencing column of a foreign key when you delete parents, or when you look up children by their parent.

What an index costs

Every index is another sorted copy, so it costs disk space, and every write must update it. The course measured the write cost on a copy of tickets: 10,000 new tickets in one transaction, medians of 3 runs.

Inserting 10,000 tickets into a copy of tickets (300,000 rows) with the primary key only, with the queue index too, and with one more index on each of 11 columns. Medians of 3 runs.

Text description of the chart

A column chart of the seconds to insert 10,000 tickets. Primary key only: 0.026 s, with 9.3 MB of indexes. Plus the queue index: 0.047 s, 29.5 MB. Plus 11 more indexes, one on each column: 0.113 s, 92 MB of indexes for a table of 134.2 MB.

One well-chosen index almost doubled the insert time (0.026 to 0.047 s) and added 20 MB. For the help desk, that is a fair price: tickets are read far more often than they are written. Eleven more indexes made inserts 4.3 times slower than the keys alone, and the indexes grew to 92 MB. That is about two thirds of the table’s own 134 MB.

Common mistake

An index on every column

Symptom: Tomás adds an index on each of the 11 columns of tickets, next to the queue index. Inserts take 4.3 times as long as with the keys alone, and the indexes use 92 MB. The ticket list is no faster than with the queue index alone.

Cause: an index helps only a query whose conditions and order fit it. Nobody measured which queries the 11 indexes were for. One index per column also cannot replace one composite index. As the measurements showed, (status) and (team) alone barely help a page that filters on both and sorts by time.

Diagnose: PostgreSQL counts how often the planner uses each index. Run the workload, then ask:

SELECT indexrelname, idx_scan, pg_size_pretty(pg_relation_size(indexrelid)) AS size
FROM pg_stat_user_indexes WHERE relname = 'tickets' ORDER BY idx_scan;

The course ran the ticket-list workload and the customer list with Tomás’s 13 indexes. Then only 2 of the 13 had an idx_scan above zero: the queue index and the one on created_at. The other 11 cost space and write time for nothing.

Fix: drop the indexes that no measured query uses, with DROP INDEX CONCURRENTLY <name>; in a no-transaction migration. Then add an index only for a slow query that you measured, check its plan, and measure the query and the writes again. Look at idx_scan from time to time: a query can change and leave its index unused.

Guided practice: add the indexes and measure

1. Measure a delete before the indexes. In psql (docker compose exec db psql -U tickets -d tickets), delete ticket T-399001 inside a transaction, and undo it:

   BEGIN;
   EXPLAIN (ANALYZE, COSTS OFF) DELETE FROM tickets WHERE ticket_id = 'T-399001';
   ROLLBACK;

   Note the Trigger for constraint lines and the Execution Time. Quit with \q.

2. Copy migration 008 from the snapshot end-of-m04:

   macOS / Linux

   S=../nextia-learning-labs/C20/snapshots/end-of-m04
   cp "$S/migrations/008_ticket_list_indexes.sql" migrations/

   Windows (PowerShell)

   $S = "..\nextia-learning-labs\C20\snapshots\end-of-m04"
   Copy-Item "$S\migrations\008_ticket_list_indexes.sql" migrations\

3. Apply it: python -m ticket_api.migrate.

4. Explain the three queries again: python -m scripts.explain queue, then latest-run --ticket T-399000, then messages --ticket T-399000. Each plan now starts with an Index Scan.

5. Explain the hard page: python -m scripts.explain queue --status closed --team shipping.

6. Repeat the delete of step 1, and compare the trigger times.

7. In psql, look at the sizes of the new indexes: SELECT indexrelname, pg_size_pretty(pg_relation_size(indexrelid)) FROM pg_stat_user_indexes WHERE indexrelname LIKE '%_idx';.

8. Measure the endpoint with the same workload as before: python -m scripts.bench. Then run the tests: python -m pytest.

Show the expected result

Step 1, the end of the author’s run (your times differ):

 Trigger for constraint messages_ticket_fk: time=20.313 calls=1
 Trigger for constraint attachments_ticket_fk: time=8.107 calls=1
 Trigger for constraint ai_runs_ticket_fk: time=25.373 calls=1
 Trigger for constraint ticket_embeddings_ticket_fk: time=0.196 calls=1
 Execution Time: 54.197 ms

Step 3 prints applied 008_ticket_list_indexes and Database is up to date (8 migrations). It takes a second or two on the large data. Step 4, the first plan:

Limit  (cost=0.42..57.24 rows=20 width=201) (actual time=0.025..0.038 rows=20.00 loops=1)
  Buffers: shared hit=18
  ->  Index Scan using tickets_queue_idx on tickets t  (cost=0.42..4736.50 rows=1667 width=201) (actual time=0.025..0.035 rows=20.00 loops=1)
        Index Cond: ((status = 'open'::text) AND (team = 'billing'::text))
        Index Searches: 1
        Buffers: shared hit=18

No Sort and no Filter: the index gives the 20 rows in order. Step 5 shows the same two steps, with Buffers: shared hit=24 in the author’s run. Step 6:

 Trigger for constraint messages_ticket_fk: time=0.124 calls=1
 Trigger for constraint attachments_ticket_fk: time=3.653 calls=1
 Trigger for constraint ai_runs_ticket_fk: time=0.282 calls=1
 Trigger for constraint ticket_embeddings_ticket_fk: time=0.053 calls=1
 Execution Time: 4.212 ms

Step 7: tickets_queue_idx 17 MB, ai_runs_ticket_idx 17 MB, messages_ticket_idx 14 MB. Step 8: database queries per request: 41 still, with a median of about ten to twenty milliseconds; the course measured 13.3 ms. The tests print 79 passed: the indexes change no result, only the speed.

Your turn: the customer’s ticket list

Grace’s team opens one customer’s tickets many times a day: GET /v1/tickets?customer_id=C-3835. Its query is the same list query, with customer_id = … instead of status and team. python -m scripts.explain customer --customer C-3835 shows that it still reads the whole table: a Parallel Seq Scan. The course measured about 12 ms for a similar query.

Design one index for it with the rule of this lesson. Test it without a migration: in psql, create it between BEGIN; and ROLLBACK;, and run EXPLAIN (ANALYZE, BUFFERS) on the query in the same transaction. Then answer: what does it cost, and is the query used often enough to pay for it?

Show an example answer

The query compares customer_id and orders by created_at DESC, ticket_id DESC. So the index is (customer_id, created_at DESC, ticket_id DESC):

BEGIN;
CREATE INDEX tickets_customer_idx ON tickets (customer_id, created_at DESC, ticket_id DESC);
EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM tickets t WHERE t.customer_id = 'C-3835' ORDER BY t.created_at DESC, t.ticket_id DESC LIMIT 20;
SELECT pg_size_pretty(pg_relation_size('tickets_customer_idx'));
ROLLBACK;

The plan lines of the author’s run:

 Limit  (cost=0.42..72.70 rows=20 width=201) (actual time=0.036..0.053 rows=20.00 loops=1)
   Buffers: shared hit=18 read=3
   ->  Index Scan using tickets_customer_idx on tickets t  (cost=0.42..15467.18 rows=4280 width=201) (actual time=0.035..0.050 rows=20.00 loops=1)
         Index Cond: (customer_id = 'C-3835'::text)
         Index Searches: 1

21 pages instead of the whole table, and no sort. The index is 14 MB, and every new ticket must update it. The help desk opens customer pages many times a day, so it is worth it. In a real project, you would keep it as a migration with CONCURRENTLY, rehearsed on the large data. Without CONCURRENTLY, CREATE INDEX blocks writes to tickets while it builds; inside BEGIN … ROLLBACK on your own computer, that does not matter. In this course, do not keep it: the next modules continue without it.

When to add an index, and when not

Add an index when a query you measured is slow, its plan reads many more rows than it returns, and the query runs often. Build it for that query: the = columns first, then the ORDER BY columns. Then check the plan and measure again, reads and writes.

Do not add an index:

• for a small table. On the 200 small-data tickets, the planner prefers a full scan, and it is right.
• for a condition that matches most rows. As status = 'closed' showed, the planner ignores it.
• “in case”. Every index slows every insert and many updates, and it uses disk and memory. An unused index is pure cost.

Indexes on the referencing column of a foreign key are an exception that you should plan for. Deletes of parents and lookups of children both need them.

See it end to endDesign and tune storage for an open public datasetCase study

The Boston 311 case study tries ten index candidates one at a time. A partial index of 6 MB makes the work queue about 900 times faster.

Knowledge check

Check your understanding

The ticket list filters on status and team and sorts by created_at DESC, ticket_id DESC. Why is (status, team, created_at DESC, ticket_id DESC) better than two indexes, one on (status, team) and one on (created_at)?

Show the answer

Neither single index does both jobs, and PostgreSQL cannot merge them into one ordered list. (status, team) finds the group, but not in date order, so 76,160 closed shipping tickets must be fetched and sorted. (created_at) gives the order, but then the database checks ticket after ticket for the status and team. The composite index has the group together and newest first, so the first 20 entries are the answer: 0.012 ms for any page.

Check your understanding

With an index on (status), the open billing page took 1.39 ms, but the closed shipping page still took 15.5 ms and its plan had no index at all. Why did the planner ignore the index?

Show the answer

254,364 of the 300,000 tickets are closed. To use the index, the database would jump from entry to row for each of them, in a random order of pages. Reading the whole table in order is cheaper than that. An index pays off when it narrows the rows a lot; a value that most rows have does not narrow anything.

Check your understanding

Migration 008 was written for the ticket list, but deleting a ticket became 20 times faster. Explain why, and name the table whose check is still slow.

Show the answer

Deleting a ticket makes PostgreSQL check each table with a foreign key to tickets, by ticket_id. Without an index on that column, each check reads the whole child table. 008 indexed messages (ticket_id) and ai_runs (ticket_id, created_at DESC). Those two checks became index lookups, from 21.5 and 18.7 ms to 0.02 and 0.1 ms. But attachments has no index on ticket_id yet, so its check still scans the table.

Recap

• An index is a sorted copy of some columns that points to the rows. A composite index is sorted by its first column, then the next: it helps queries that fix its first columns.
• For a query, put the = columns first, then the ORDER BY columns in the same order and direction. For the ticket list: (status, team, created_at DESC, ticket_id DESC), 0.013 ms for any page.
• Measure each candidate. The planner ignored (status) on the closed page; (status, team) still sorted 76,160 rows; (created_at) was fast only because open tickets are recent.
• 008 adds three indexes. The list endpoint, still with 41 queries, went from 375 ms to 13.3 ms; deleting a ticket from 46.5 to 2.2 ms.
• Each index costs space and write time. An index on every column: 4.3 times slower inserts, 92 MB, and 2 of 13 indexes used. pg_stat_user_indexes shows which ones work.
• Next: send one query instead of 41, and return a page that stays fast however deep it is.

Next: Bound result sizes