Query optimization series: 1. How SQL runs and reading execution plans · 2. PostgreSQL index lab on an airline dataset · 3. Join algorithms and partitioning
This lab measures what the textbooks’ “it depends” actually amounts to in milliseconds and pages. Seven steps on an airline dataset, each with the same rhythm: ask, predict, run EXPLAIN (ANALYZE, BUFFERS), explain. Afterwards you can pick an index type and a column order, and tell when an index is useless, with numbers to back it up.
Read first: Indexes, EXPLAIN, N+1 and pagination (B+tree, composite and covering basics) and part 1 to read a plan (cost, rows, loops, buffers, scan types). The theory underneath (heaps and TIDs, HOT updates, bloat, GIN/GiST) lives in the Indexes in depth series.
At a glance:
flowchart TD
Q{What kind of query?} -->|"= one row"| BT["B-tree: ~4 pages"]
Q -->|"LIKE 'abc%'"| CC["COLLATE C / text_pattern_ops"]
Q -->|"LIKE '%abc'"| TR[pg_trgm]
Q -->|"~94% of table"| SS[Seq Scan]
CP[Composite index] --> ORD["Equality first, range last"]
CP --> INC["INCLUDE: Index Only Scan"]
W[Each extra index] --> WR[One more write]
0. Setup
Key idea: run PostgreSQL 16 in Docker, generate data shaped like the airline demo database (2.1 million bookings, 3.1 million tickets), and in each step compare an index-free copy with an indexed one.
docker run -d --name pg-lab -e POSTGRES_USER=lab -e POSTGRES_PASSWORD=lab -e POSTGRES_DB=demo \
postgres:16 -c shared_preload_libraries=pg_stat_statements
docker exec -it pg-lab psql -U lab -d demo
- Index-free copy:
CREATE TABLE tickets0 AS TABLE ticketscopies no indexes or constraints. - Timings are first runs on a laptop: trust page counts (
Buffers, the number of 8 KB blocks read) over milliseconds.
Two ways to get data, and the generator script
Option one: the Postgres Pro Airlines demo database (the “big” edition, a year of data, about 2.1 million bookings). Download the .sql file from their demodb page, docker cp it into the container and run psql -U lab -f demo-big-en.sql.
Option two, which produced the numbers in this post: generate data with the same shape yourself (a few tens of seconds).
CREATE TABLE bookings (
book_ref char(6) PRIMARY KEY,
book_date timestamptz NOT NULL,
total_amount numeric(10,2) NOT NULL
);
INSERT INTO bookings
SELECT upper(lpad(to_hex(g::bigint * 7919 % 16777216), 6, '0')), -- unique 6-char hex code
timestamptz '2016-07-20 00:00+00' + random() * interval '390 days',
3000 + floor(power(random(), 2) * 5667) * 100 -- 5,667 price levels, skewed low
FROM generate_series(1, 2100000) g;
CREATE TABLE tickets (
ticket_no char(13) PRIMARY KEY,
book_ref char(6) NOT NULL REFERENCES bookings,
passenger_id varchar(20) NOT NULL, -- looks like '6074 127932'
passenger_name text NOT NULL
);
INSERT INTO tickets
SELECT lpad((5432000000 + b.rn * 3 + s)::text, 13, '0'), b.book_ref,
lpad(floor(random() * 10000)::text, 4, '0') || ' ' || lpad(floor(random() * 1000000)::text, 6, '0'),
(array['IVAN','OLGA','ANNA','PETR'])[1 + floor(random() * 4)] || ' ' || (array['IVANOV','POPOV'])[1 + floor(random() * 2)]
FROM (SELECT book_ref, row_number() OVER () AS rn FROM bookings) b
CROSS JOIN LATERAL generate_series(1, 1 + (b.rn % 3 = 0)::int + (b.rn % 7 = 0)::int) s; -- 1-3 tickets per booking
CREATE TABLE seats (
aircraft_code char(3) NOT NULL,
seat_no varchar(4) NOT NULL,
fare_conditions varchar(10) NOT NULL,
PRIMARY KEY (aircraft_code, seat_no)
);
INSERT INTO seats
SELECT a, r || l, CASE WHEN r <= 3 THEN 'Business' WHEN r <= 8 THEN 'Comfort' ELSE 'Economy' END
FROM unnest(array['319','320','321','733','763','773','CN1','CR2','SU9']) a,
generate_series(1, 40) r, unnest(array['A','B','C','D','E','F']) l;
VACUUM ANALYZE; -- 2,100,000 bookings, 3,100,000 tickets, 2,160 seats
Step 1: No index vs a B-tree
Key idea: with a B-tree, looking up one ticket reads 4 pages and takes ~0.5 ms instead of ~98 ms. More importantly, the page count barely changes as the table grows.
Question: look up one ticket by ticket_no in a 3.1-million-row table, with and without an index.
CREATE TABLE tickets0 AS TABLE tickets;
VACUUM ANALYZE tickets0;
EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM tickets0 WHERE ticket_no = '0005434508964';
CREATE INDEX tickets0_ticket_no_idx ON tickets0 (ticket_no); -- 1.1 seconds
EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM tickets0 WHERE ticket_no = '0005434508964';
| Plan | Buffers | Time | |
|---|---|---|---|
| No index | Parallel Seq Scan, 2 workers, 1,033,333 rows discarded per process | ~29,600 pages | ~98 ms |
| B-tree | Index Scan, cost=0.43..8.45 |
4 pages | ~0.5 ms |
About 200 times faster. Make the table ten times bigger and the B-tree gets roughly one level taller.
Step 2: B-tree vs hash index
Key idea: for =, hash saves just one page over a B-tree; for a range (>=), hash can’t be used and the query falls back to a Seq Scan. Almost always pick B-tree.
Question: for equality, is a hash index faster than a B-tree? What about a range?
CREATE TABLE tickets1 AS TABLE tickets;
CREATE INDEX tickets1_ticket_no_hash ON tickets1 USING hash (ticket_no);
VACUUM ANALYZE tickets1;
EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM tickets1 WHERE ticket_no = '0005434508964';
EXPLAIN ANALYZE SELECT * FROM tickets1 WHERE ticket_no >= '0005438299000';
EXPLAIN ANALYZE SELECT * FROM tickets0 WHERE ticket_no >= '0005438299000';
| Query | B-tree (tickets0) |
Hash (tickets1) |
|---|---|---|
= |
Index Scan, cost 8.45, 4 pages | Index Scan, cost 8.02, 3 pages |
>= (494 rows) |
Index Scan, 0.4 ms | unusable, Parallel Seq Scan 164 ms |
| Index size | 93 MB | 97 MB |
Hash vs B-tree: size, limits and when hash is worth it
Step 3: LIKE, collations and pg_trgm
Key idea: a linguistic collation (the rules for comparing and sorting strings) such as en_US.utf8 stops a plain B-tree from serving LIKE 'abc%'. You need an index in byte order; LIKE '%abc' needs a trigram index.
Question: does a plain index on passenger_id serve LIKE '6074 12%'? What about LIKE '%53 429919'?
CREATE INDEX tickets0_pid_idx ON tickets0 (passenger_id);
EXPLAIN SELECT * FROM tickets0 WHERE passenger_id = '3453 429919'; -- Index Scan
EXPLAIN SELECT * FROM tickets0 WHERE passenger_id LIKE '6074 12%'; -- Parallel Seq Scan!
en_US.utf8 (the Docker image default) doesn’t sort in byte order, so PostgreSQL can’t turn a prefix LIKE into a range on a plain index. You need an index in byte order:
CREATE INDEX tickets0_pid_c_idx ON tickets0 (passenger_id COLLATE "C");
-- or: CREATE INDEX ... ON tickets0 (passenger_id text_pattern_ops);
EXPLAIN ANALYZE SELECT * FROM tickets0 WHERE passenger_id LIKE '6074 12%';
Index Scan using tickets0_pid_c_idx on tickets0 (actual time=0.273..0.465 rows=5 loops=1)
Index Cond: (((passenger_id)::text >= '6074 12'::text) AND ((passenger_id)::text < '6074 13'::text))
Filter: ((passenger_id)::text ~~ '6074 12%'::text)
The planner rewrote the prefix as a range. A leading wildcard ('%53 429919') gives the tree no starting point, so it stays a Parallel Seq Scan at 105 ms. For suffix or substring search, use a trigram index (an index over every run of three consecutive characters):
CREATE EXTENSION IF NOT EXISTS pg_trgm;
CREATE INDEX tickets0_pid_trgm ON tickets0 USING gin (passenger_id gin_trgm_ops); -- 4.2 seconds, 74 MB
EXPLAIN ANALYZE SELECT * FROM tickets0 WHERE passenger_id LIKE '%53 429919';
-- Bitmap Index Scan on tickets0_pid_trgm → Bitmap Heap Scan, 5.8 ms
pg_trgm doesn’t score relevance, has no analyzer for accented Vietnamese and no search-as-you-type. When you need those, or search load starts to hurt the transactional database, see Elasticsearch: analyzers, the inverted index and mappings (it opens with the “PostgreSQL or add Elasticsearch” trade-off).
Step 4: When the planner skips the index
Key idea: an index only pays off when you fetch a small fraction of the table. At 94% of the table, a Seq Scan reads each page once, while a forced index re-reads the same pages hundreds of times and is 7.5 times slower.
Question: there’s an index on book_date. Which plan will a one-day, one-month and one-year query use? Guess first.
CREATE TABLE bookings0 AS TABLE bookings;
CREATE INDEX bookings0_book_date_idx ON bookings0 (book_date);
VACUUM ANALYZE bookings0;
EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM bookings0
WHERE book_date >= '2017-03-01' AND book_date < '2017-03-02'; -- vary the range: 1 day / 1 month / 1 year
| Range | Rows (share of table) | Plan | Buffers | Time |
|---|---|---|---|---|
| 1 day | 5,404 (0.26%) | Bitmap Heap Scan, 4,458 heap blocks | ~4,500 | 17 ms |
| 1 month | 167,029 (8%) | Bitmap Heap Scan, 13,376 heap blocks | ~13,800 | 51 ms |
| 1 year | 1,965,143 (94%) | Seq Scan | 13,376 | 122 ms |
1 year, index forced (enable_seqscan, enable_bitmapscan = off) |
1,965,143 | Index Scan | 1,970,356 | 922 ms |
correlation measures how closely the on-disk row order follows the column’s order (1 = matches, 0 = random). For book_date it’s near 0, so one day’s 5,404 rows are spread over 4,458 pages. For a year, the Index Scan touches heap pages almost 2 million times (each page re-read hundreds of times), while the Seq Scan reads 13,376 pages exactly once. The planner is right.
BRIN: a tiny index for data written in time order
Step 5: Column order in a composite index
Key idea: a B-tree can only use a range on the first column to bound the part it reads. So equality columns go first and the range column last; the kind of predicate decides, not cardinality (the number of distinct values in a column).
Question: the query is total_amount >= 400000 AND book_date within one day. Is (book_date, total_amount) or (total_amount, book_date) better? The popular “rule”: high-cardinality column first.
SELECT count(DISTINCT book_date), count(DISTINCT total_amount) FROM bookings; -- 2,100,000 and 5,667
SELECT count(*) FROM bookings WHERE total_amount >= 400000; -- 341,131 (16%)
CREATE INDEX bookings0_date_amount ON bookings0 (book_date, total_amount);
CREATE TABLE bookings1 AS TABLE bookings;
CREATE INDEX bookings1_amount_date ON bookings1 (total_amount, book_date);
-- the same query against both tables:
-- WHERE total_amount >= 400000 AND book_date >= '2017-03-01' AND book_date < '2017-03-02'
| Index | Plan | Index pages read | Time |
|---|---|---|---|
(book_date, total_amount) |
Bitmap Index Scan | 24 | 0.8 ms |
(total_amount, book_date) |
Bitmap Index Scan | 1,309 | 17 ms (8.7 ms warm) |
Both plans print both conditions in Index Cond; the difference is in the pages:
(total_amount, book_date): the bounded region is every entry withtotal_amount >= 400000(16% of the index), andbook_dateis filtered inside it.(book_date, total_amount): the region is just one day (0.26%).
Now make total_amount an equality: total_amount = 450000 with book_date over one month.
| Index | Pages read | Time |
|---|---|---|
(total_amount, book_date) |
4 index pages + 10 heap pages | 0.05 ms |
(book_date, total_amount) |
653 pages | 5.1 ms |
The ranking flips, although each column’s cardinality is unchanged.
The good news: the second column’s condition is still checked inside the index, before any heap access (MySQL calls this index condition pushdown, Using index condition; PostgreSQL does the equivalent). That’s how one composite index can serve several queries.
Step 6: ORDER BY together with a range
Key idea: an (a, b) index returns rows in b order only when a is an equality. With a range on a you still need a Sort, even if the index holds every column.
Question: add ORDER BY book_ref to the step 5 query. Which index gets rid of the Sort?
-- With (book_date, total_amount): Sort (quicksort 66kB) of 881 rows above a Bitmap Heap Scan, 11.4 ms
DROP INDEX bookings0_date_amount;
CREATE INDEX bookings0_date_ref_amount ON bookings0 (book_date, book_ref, total_amount);
VACUUM ANALYZE bookings0;
EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM bookings0
WHERE book_date >= '2017-03-01' AND book_date < '2017-03-02' AND total_amount >= 400000
ORDER BY book_ref;
Sort (actual time=0.561..0.578 rows=881 loops=1)
Sort Key: book_ref
Sort Method: quicksort Memory: 66kB
-> Index Only Scan using bookings0_date_ref_amount on bookings0 (actual time=0.014..0.263 rows=881 loops=1)
Heap Fetches: 0
Buffers: shared hit=1 read=30
About 20 times faster thanks to an Index Only Scan (the index holds all three columns), but the Sort is still there: the index orders book_ref within each book_date value, and one day holds thousands of timestamps. To confirm: ORDER BY book_date LIMIT 20 on the same index has no Sort and stops after 5 pages.
Two separate indexes plus LIMIT 20: a different plan and its limits
With two separate indexes, (book_date) and (book_ref), plus LIMIT 20, the planner walks the book_ref index in order and filters on book_date: 6,777 rows discarded, ~6,800 pages, 3.8 ms. That plan only works while matching rows are evenly spread; for a day with little data it can walk most of the index.
Step 7: A covering index with INCLUDE
Key idea: a covering index contains every column the query needs, so PostgreSQL can skip reading the table (Index Only Scan). INCLUDE adds columns to the index leaves without changing the key.
Question: SELECT seat_no, fare_conditions FROM seats0 WHERE aircraft_code = '733' with a unique index on (aircraft_code, seat_no). How do you avoid reading the table?
CREATE TABLE seats0 AS TABLE seats;
CREATE UNIQUE INDEX seats0_pk ON seats0 (aircraft_code, seat_no);
VACUUM ANALYZE seats0;
EXPLAIN (ANALYZE, BUFFERS) SELECT seat_no, fare_conditions FROM seats0 WHERE aircraft_code = '733';
-- Bitmap Heap Scan: 3 index pages + 12 heap pages (needs fare_conditions)
DROP INDEX seats0_pk;
CREATE UNIQUE INDEX seats0_pk ON seats0 (aircraft_code, seat_no) INCLUDE (fare_conditions);
VACUUM ANALYZE seats0;
EXPLAIN (ANALYZE, BUFFERS) SELECT seat_no, fare_conditions FROM seats0 WHERE aircraft_code = '733';
-- Index Only Scan using seats0_pk, Heap Fetches: 0, 4 pages
A note: the course’s sample script ends with an EXPLAIN on seats instead of seats0, so its plan doesn’t reflect the index just created. Always check the table name in the plan (on seats0).
INCLUDE vs adding to the key: the detailed comparison
Case study: designing indexes for a flight booking schema
Key idea: start from the main queries and tie each index to a real one. A report that scans most of the data doesn’t get a B-tree.
Task (the course homework, paraphrased): design the indexes for a flight booking schema modeled on the demo database. Constraints: about 20 reads per write; booking must stay fast when sales open; revenue reports run overnight; no “just in case” indexes.
| # | Query | Index |
|---|---|---|
| Q1 | Flight search: departure_airport = ? AND arrival_airport = ? AND scheduled_departure within a day, ordered by time |
flights (departure_airport, arrival_airport, scheduled_departure): two equalities first, the range and sort last |
| Q2 | Tickets of a booking | tickets (book_ref): PostgreSQL does not create indexes for foreign keys |
| Q3 | Passengers on a flight (check-in, seat assignment) | ticket_flights (flight_id): the PK starts with ticket_no and can’t help |
| Q4 | Seats already assigned on a flight, preventing double assignment | UNIQUE boarding_passes (flight_id, seat_no): a business rule and an index in one |
| Q5 | Lookup by passenger document | tickets (passenger_id); add pg_trgm only if partial matching is really needed |
| Q6 | Revenue by booking date | No B-tree just for the nightly report; use a daily summary table, or BRIN if data is written in time order |
Decision. Five indexes for Q1–Q5; Q6 goes the indirect way because it scans most of the data (step 4). A pull request that adds an index must include the query it serves and the before/after plans.
This is a demo dataset for measuring. Designing an airline booking database designs a booking schema from scratch (flights, seat maps, seat inventory per seat or as a counter, overbooking) and picks indexes for it, including a partial index over free seats.
Full schema, foreign key indexes and the cost of each index
bookings(book_ref PK, book_date, total_amount), tickets(ticket_no PK, book_ref FK, passenger_id, passenger_name), flights(flight_id PK, flight_no, scheduled_departure, departure_airport, arrival_airport, status, aircraft_code), ticket_flights(ticket_no, flight_id, fare_conditions, amount, PK (ticket_no, flight_id)), boarding_passes(ticket_no, flight_id, seat_no, boarding_no).
Exercises
Exercise 1: Repeat step 5 on MySQL
Task: create a similar bookings table on MySQL 8 and compare the two index orders. How does the plan differ from PostgreSQL?
Solution to exercise 1: measurements on MySQL 8.4
I ran it on MySQL 8.4 with 1 million rows. EXPLAIN ANALYZE shows that MySQL has no bitmap scans; both indexes give a Covering index range scan.
(book_date, total_amount): the range scan reads 2,532 entries to produce 402 rows (0.36 ms).(total_amount, book_date): it reads 162,557 entries for the same 402 rows (21 ms).
The ranking matches PostgreSQL because both are B+trees bounded by the leading column. One notable difference: the plan says “Covering index” even for SELECT *, because the table has only three columns and InnoDB secondary indexes always contain the PK (book_ref). When the index doesn’t cover the query, the Extra column of EXPLAIN shows Using index condition for the second column’s predicate (ICP).
Exercise 2: An index for the “departures today” screen
Task: SELECT flight_no, scheduled_departure, status FROM flights WHERE departure_airport = 'SGN' AND scheduled_departure >= current_date AND scheduled_departure < current_date + 1 ORDER BY scheduled_departure. Design the index and describe the expected plan.
Solution to exercise 2
CREATE INDEX ON flights (departure_airport, scheduled_departure) INCLUDE (flight_no, status).
- The equality column
departure_airportcomes first, the range/sort columnscheduled_departuresecond. Since the leading column is an equality, thescheduled_departureorder is preserved and no Sort is needed. INCLUDEenables an Index Only Scan if the table is vacuumed regularly.- If
statuschanges constantly during the day (DELAYED, BOARDING…), consider dropping it fromINCLUDEto keep HOT updates, and accept a few dozen heap reads.
Remember
- Explain why you trust
Buffersover milliseconds, and why a B-tree’s page count barely grows with the table. - Know when a hash index is worth it, and why
LIKE 'abc%'may not use a plain index in PostgreSQL. - Explain why the planner picks a Seq Scan when fetching most of the table, and how
correlationaffects that. - Order composite columns by predicate kind (equality, range, sort), and say why “high cardinality first” is wrong.
- Know when a composite index can remove a Sort, and choose between
INCLUDEand adding a column to the key.
Interview questions
Junior
Why does a query still do a Seq Scan when there’s an index?
Usually because it fetches most of the table, so reading sequentially is cheaper.
Other reasons: the predicate can’t use the index (column wrapped in a function, an implicit cast, LIKE '%x', a mismatched collation); stale statistics led to a bad estimate; or the table is tiny.
How does a hash index differ from a B-tree?
A hash index only serves equality, and is only slightly cheaper than a B-tree there.
A B-tree serves equality, ranges, ordering, prefix LIKE, uniqueness and multiple columns. Default to B-tree.
Mid
How should you order the columns of a composite index?
Equality columns first, the range or sort column last.
After a range, the remaining columns only filter inside the region already read; they don’t bound it. With several ranges, put the narrowest one on real data first. “High cardinality first” isn’t the right rule; measure with Buffers.
How do you make an index serve LIKE ‘abc%’ and LIKE ‘%abc’ in PostgreSQL?
Prefix: a B-tree with COLLATE "C" or text_pattern_ops. Leading wildcard: a pg_trgm trigram index.
For a prefix, the planner turns LIKE into a range when the index is in byte order (needed when the database uses a linguistic collation). For a leading wildcard, use pg_trgm with GIN or GiST; for suffix-only search, an expression index on reverse(col).
What is a covering index, and how is INCLUDE different from adding the column to the key?
A covering index contains every column the query needs, enabling an Index Only Scan.
INCLUDE keeps the column in the leaves only, outside the ordering and without changing uniqueness. Adding it to the key lets you filter and sort on it, but changes uniqueness and makes the tree bigger.
Senior
Does an index on (a, b) remove the Sort from WHERE a BETWEEN x AND y ORDER BY b?
No. Across a range of many a values, the output is ordered by a first and only then by b.
The order of b is preserved only when a is an equality. The options: sort a small result, or use an index on b and filter when there’s a small LIMIT.
How do you decide to add an index in production?
Tie it to a specific query with numbers, measure the plan before and after, then create it with CREATE INDEX CONCURRENTLY.
- Get frequency and total time from
pg_stat_statements. - Check whether an existing index could be extended instead.
- Measure the plan before and after on production-sized data; estimate the write and storage cost.
- After creating it, watch
idx_scanand write latency.
Useful phrases for interviews
- “Let me guess the plan first and then check it with EXPLAIN ANALYZE and BUFFERS.”
- “Both plans list the two conditions in Index Cond, but the buffer counts show that only the leading column bounds the scan.”
- “I’d put the equality columns first and the range column last, and among ranges the one that’s narrowest on real data.”
- “For ninety-four percent of the table, a sequential scan is the right call; forcing the index made it seven times slower.”
- “The database uses a linguistic collation, so I’d add a text_pattern_ops index for prefix searches.”
- “For a leading wildcard, a B-tree can’t help; I’d reach for a trigram GIN index.”
- “INCLUDE gives us an index-only scan without changing what the unique constraint means.”
- “Postgres doesn’t index foreign keys automatically, so that’s the first thing I check on a new schema.”
Notes based on the Advanced Backend course (Ronin Engineer), rewritten in my own words.