Skip to content
notes.vinhnq.com

Search

Database & ORMSenior23 min read

A PostgreSQL index lab on an airline dataset: B-tree, hash, LIKE, composite and covering indexes

Review 16 cards
On this page

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 tickets copies 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 with total_amount >= 400000 (16% of the index), and book_date is 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_airport comes first, the range/sort column scheduled_departure second. Since the leading column is an equality, the scheduled_departure order is preserved and no Sort is needed.
  • INCLUDE enables an Index Only Scan if the table is vacuumed regularly.
  • If status changes constantly during the day (DELAYED, BOARDING…), consider dropping it from INCLUDE to keep HOT updates, and accept a few dozen heap reads.

Remember

  • Explain why you trust Buffers over 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 correlation affects 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 INCLUDE and 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_scan and 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.