B-tree Internals and Multi-Column Indexes

A query filters on (status, created_at). There is already an index on (created_at, status). It is not being used. Prove why, then fix it.

A B-tree index is not a set of columns; it is a sorted structure built in a specific column order, and that order determines everything about what the index can actually be used for. An index on (created_at, status) is physically sorted first by created_at, with status only sorted within each identical created_at value. Searching it for a specific status with no constraint on created_at is like trying to look up a phone book by first name when it is alphabetized by last name — the information is technically in there, but there is no way to jump directly to it.\n\nThis is the left-prefix rule: a composite index on (a, b, c) directly supports queries filtering on a alone, on (a, b) together, or on (a, b, c) together — but not on b alone, and not on c alone, without a value for a to anchor the search. Column order in CREATE INDEX is a design decision, not a formality, and this lab proves it two ways: the same query against an index in the wrong order, genuinely unused, and then against an index in the right order, genuinely used for three different real query shapes.

The Wrong Column Order, Proven Unused

CREATE INDEX idx_wrong_order ON idx_orders(created_at, status);
EXPLAIN SELECT * FROM idx_orders WHERE status = 'shipped';

Seq Scan on idx_orders  (cost=0.00..1965.00 rows=25103 width=25)
  Filter: (status = 'shipped'::text)

The index exists, it contains the status column, and the planner still chooses a full sequential scan — because created_at leads the index, and this query does not filter on created_at at all. There is no way to enter the index's sorted structure at the right point without it.

The Right Column Order, Proven Used

CREATE INDEX idx_status_created ON idx_orders(status, created_at);
EXPLAIN SELECT * FROM idx_orders WHERE status = 'shipped';

Bitmap Heap Scan on idx_orders  (cost=614.97..1643.75 rows=25103 width=25)
  Recheck Cond: (status = 'shipped'::text)
  ->  Bitmap Index Scan on idx_status_created  (cost=0.00..608.69 rows=25103 width=0)
        Index Cond: (status = 'shipped'::text)

Same query, same table, only the column order flipped — and now the index is used. It comes back as a Bitmap Heap Scan, not a plain Index Scan, because status = 'shipped' matches roughly a quarter of the table: with that many matching rows scattered across many heap pages, PostgreSQL builds an in-memory bitmap of matching pages first, then visits each qualifying heap page once, rather than bouncing around the heap once per matching row the way a plain Index Scan would.

The Same Index, Two More Query Shapes

EXPLAIN SELECT * FROM idx_orders WHERE status = 'shipped' AND created_at > '2025-01-02';
-- Bitmap Heap Scan, Index Cond uses BOTH columns together

EXPLAIN SELECT * FROM idx_orders WHERE status = 'shipped' ORDER BY created_at LIMIT 5;
-- Limit -> Index Scan using idx_status_created — no separate Sort node at all

One index, three query shapes it genuinely supports: status alone, status plus a created_at range, and status plus an ORDER BY on created_at that needs no separate sort step because the index is already sorted that way within each status value.

The Query It Structurally Cannot Support

EXPLAIN SELECT * FROM idx_orders WHERE amount > 250;

Seq Scan on idx_orders  (cost=0.00..1965.00 rows=50108 width=25)
  Filter: (amount > '250'::numeric)

amount is not part of idx_status_created at all — not the leading column, not a trailing one, simply absent. No column reordering could fix this; a different index would be needed entirely.

Left-prefix rule

A composite B-tree index on columns (a, b, c) is physically sorted first by a, then by b within each a, then by c within each (a, b). It can be searched efficiently starting from any leftmost contiguous prefix of its columns — a, or (a, b), or (a, b, c) — but not from b or c alone, since without a value for a (and b, for c) there is no way to know where in the sorted structure to start looking.

Bitmap Heap Scan

A two-phase scan strategy: first build an in-memory bitmap of which heap pages contain matching rows by scanning the index (the Bitmap Index Scan step), then visit each flagged heap page once, in physical order, checking every row on it against the original condition (the Recheck Cond). It is the planner's middle ground between a plain Index Scan (efficient for a few matching rows, wasteful for many) and a Seq Scan (efficient for most of the table, wasteful for a small fraction) — chosen when a meaningful fraction of the table matches.

🚫 Prove the Wrong Column Order Is Unusable

Build an index with created_at leading, then run a query that filters only on status — the second column — and confirm the index is genuinely ignored.

psql -U postgres -d beer_db -c "CREATE INDEX idx_wrong_order ON idx_orders(created_at, status);"

psql -U postgres -d beer_db -c "EXPLAIN SELECT * FROM idx_orders WHERE status = 'shipped';"

student@lab:~$ psql -U postgres -d beer_db -c "CREATE INDEX idx_wrong_order ON idx_orders(created_at, status);" SET CREATE INDEX student@lab:~$ psql -U postgres -d beer_db -c "EXPLAIN SELECT * FROM idx_orders WHERE status = 'shipped';" SET QUERY PLAN ------------------------------------------------------------------ Seq Scan on idx_orders (cost=0.00..1965.00 rows=25103 width=25) Filter: (status = 'shipped'::text) (2 rows)

✅ Fix the Column Order and Prove It Now Works

Drop the wrongly-ordered index, build one with status leading, and rerun the identical query.

psql -U postgres -d beer_db -c "DROP INDEX idx_wrong_order;" -c "CREATE INDEX idx_status_created ON idx_orders(status, created_at);"

psql -U postgres -d beer_db -c "EXPLAIN SELECT * FROM idx_orders WHERE status = 'shipped';"

student@lab:~$ psql -U postgres -d beer_db -c "DROP INDEX idx_wrong_order;" -c "CREATE INDEX idx_status_created ON idx_orders(status, created_at);" SET DROP INDEX CREATE INDEX student@lab:~$ psql -U postgres -d beer_db -c "EXPLAIN SELECT * FROM idx_orders WHERE status = 'shipped';" SET QUERY PLAN ----------------------------------------------------------------------------------------- Bitmap Heap Scan on idx_orders (cost=614.97..1643.75 rows=25103 width=25) Recheck Cond: (status = 'shipped'::text) -> Bitmap Index Scan on idx_status_created (cost=0.00..608.69 rows=25103 width=0) Index Cond: (status = 'shipped'::text) (4 rows)

🎯 Confirm the Same Index Supports Two More Query Shapes

Run a range-filtered query and an ORDER BY + LIMIT query against the same index, confirming both are supported without rebuilding anything.

psql -U postgres -d beer_db -c "EXPLAIN SELECT * FROM idx_orders WHERE status = 'shipped' AND created_at > '2025-01-02';"

psql -U postgres -d beer_db -c "EXPLAIN SELECT * FROM idx_orders WHERE status = 'shipped' ORDER BY created_at LIMIT 5;"

student@lab:~$ psql -U postgres -d beer_db -c "EXPLAIN SELECT * FROM idx_orders WHERE status = 'shipped' AND created_at > '2025-01-02';" SET QUERY PLAN -------------------------------------------------------------------------------------------------------------------------- Bitmap Heap Scan on idx_orders (cost=95.90..862.83 rows=3462 width=25) Recheck Cond: ((status = 'shipped'::text) AND (created_at > '2025-01-02 00:00:00'::timestamp without time zone)) -> Bitmap Index Scan on idx_status_created (cost=0.00..95.04 rows=3462 width=0) Index Cond: ((status = 'shipped'::text) AND (created_at > '2025-01-02 00:00:00'::timestamp without time zone)) (4 rows) student@lab:~$ psql -U postgres -d beer_db -c "EXPLAIN SELECT * FROM idx_orders WHERE status = 'shipped' ORDER BY created_at LIMIT 5;" SET QUERY PLAN ----------------------------------------------------------------------------------------------- Limit (cost=0.42..1.14 rows=5 width=25) -> Index Scan using idx_status_created on idx_orders (cost=0.42..3628.25 rows=25103 width=25) Index Cond: (status = 'shipped'::text) (3 rows)

🧱 Write the Query This Index Structurally Cannot Support

Filter on a column that is not part of the index at all, and confirm no reordering could have fixed this one.

psql -U postgres -d beer_db -c "EXPLAIN SELECT * FROM idx_orders WHERE amount > 250;"

student@lab:~$ psql -U postgres -d beer_db -c "EXPLAIN SELECT * FROM idx_orders WHERE amount > 250;" SET QUERY PLAN ------------------------------------------------------------------ Seq Scan on idx_orders (cost=0.00..1965.00 rows=50108 width=25) Filter: (amount > '250'::numeric) (2 rows)

Lab 3.2.1 complete. The left-prefix rule, proven directly rather than just explained:\n\n\n Wrong column order (created_at, status) : ✅ Seq Scan — index genuinely unused\n Right column order (status, created_at) : ✅ Bitmap Heap Scan — index genuinely used\n Range + equality on the same index : ✅ both columns in Index Cond together\n ORDER BY + LIMIT on the same index : ✅ no separate Sort node needed\n Column not in the index at all (amount) : ✅ Seq Scan — structurally unfixable by reordering\n

Enable JavaScript to run the live terminal and track your progress.