Day 89: How a B-tree serves a query; the query planner
How a B-tree actually serves a query
A B-tree is a balanced, sorted tree where each node holds multiple keys and pointers — designed so that finding any value takes only a handful of node reads (O(log n)) even across millions of rows, because the tree stays shallow (a node holds many keys, not just one or two, unlike a binary tree).
For a range query (WHERE created_at BETWEEN X AND Y), Postgres walks down to the starting leaf, then follows leaf-level sibling pointers rightward — this is why B-trees are excellent at range scans specifically, not just point lookups.
The query planner
Postgres doesn't just use an index because one exists — the planner estimates the cost of every viable strategy (sequential scan, index scan, bitmap index scan, different join orders) using table statistics (row counts, value distributions, gathered by ANALYZE), and picks the cheapest estimated plan. This is why stale statistics (after a huge bulk insert, before ANALYZE runs) can cause the planner to make surprisingly bad choices.
ANALYZE orders;
-- or, for a full maintenance pass:
VACUUM ANALYZE orders;Why a query "used to be fast" and suddenly isn't
This is one of the most common real production mysteries, and it's almost always one of: stale statistics (planner picks a bad plan), index bloat (tomorrow's vacuum topic), or a data distribution change that makes a previously-good plan no longer optimal.
Key terms
- B-tree
- A balanced, sorted tree with multi-key nodes, kept shallow for fast lookups even on huge tables.
- Query planner
- Estimates the cost of different execution strategies using table statistics and picks the cheapest.
A query that used to run in milliseconds suddenly takes seconds after a massive bulk data load, with no schema change. What's the most likely first thing to check?
