Follow the Query
One real statement — best-selling products in a category — followed from text to result through every layer: parser, AST, candidate plans, cost, chosen plan, buffer pool, scans, joins, aggregate, sort, limit. At each step: what happens, why, the algorithm, the memory, the storage, the DSA concept underneath.
Why this exists
The mechanism as the answer to a problem — read this before the name.
- Problem
A product manager asks for the ten best-selling products in the Audio category. That is one SQL statement and, inside the engine, about fourteen distinct steps across four subsystems.
↓ - Naive solution
Read the whole of order_items, look up each product, look up each category, keep the Audio ones, add up quantities per product, sort, take ten.
↓ - Why it breaks
That reads 9,580 order items and does 9,580 product lookups and 9,580 category lookups to keep the 1,938 that matter. The order of operations is everything — and nothing in the SQL says what order to use.
↓ - Better idea
Filter first (one category out of eight), join the small result outward (30 products), then join the big table once, aggregate, sort only the 30 groups, cut to ten. Let the planner discover this order from statistics.
↓ - Internal mechanism
Parser → binder → planner: Seq Scan on categories with the filter pushed down → Hash Join to products → Hash Join to order_items (built on order_items in this engine) → HashAggregate by product name → Sort by units → Limit 10. Executor pulls rows through this tree; the buffer pool serves ~130 pages.
↓ - Trade-offs
This engine keeps the join order as written and hashes the right-hand input; PostgreSQL would reorder and hash the smaller side. The result is the same; the memory profile is not.
↓ - Real database
Run the same statement in PostgreSQL with
EXPLAIN (ANALYZE, BUFFERS)and you will see the same operators, the same estimated-vs-actual columns, and shared-hit/read counts where this platform shows pages.
Choose your depth
The same mechanism at four altitudes. Start where you are; come back deeper.
The statement names a result. The engine parses it, checks it, plans it, and runs the plan as a tree of operators that pull rows from the tables through a memory cache. Every one of those steps has a name in EXPLAIN and a reason for existing.
Following one query end to end is the fastest way to make the previous five lessons concrete.
The statement
The spec’s query asks for the ten best-selling products in one category. The ecommerce sample database keeps categories in their own table (products.category_id → categories.id), so the category predicate becomes a join to categories with c.name = 'Audio' — same question, one more table, and a better illustration of predicate pushdown.
1SELECT p.name, sum(oi.quantity) AS units2FROM categories c3JOIN products p ON p.category_id = c.id4JOIN order_items oi ON oi.product_id = p.id5WHERE c.name = 'Audio'6GROUP BY p.name7ORDER BY units DESC8LIMIT 10;Front end: text → AST → bound tree
Parser. 48 tokens; the recursive-descent parser produces a select node whose core holds three projection expressions (a column, an aggregate call with an alias), a from that is a join node nested inside another join node, a where that is a bin = over a column and a literal, one groupBy expression, and one orderBy term referring to the alias units, plus limit: 10. About 20 AST nodes. Nothing here has been checked against the database.
Binder. c → categories (8 rows, 3 columns), p → products (240 rows, 7 columns), oi → order_items (9,580 rows, 5 columns). p.category_id = c.id is int = int; c.name = 'Audio' is text = text; sum(oi.quantity) is sum(int) → bigint; units in ORDER BY resolves to the output column. Every name now has an object, a column number and a type. Memory so far: a few kilobytes. Storage: none — the catalog is cached.
join (inner) ON oi.product_id = p.id ├── join (inner) ON p.category_id = c.id │ ├── table categories AS c → oid 16384, 8 rows, 1 page │ └── table products AS p → oid 16391, 240 rows, 4 pages, index products_category_id_idx └── table order_items AS oi → oid 16402, 9,580 rows, 125 pages, index order_items_order_id_idx where: c.name = 'Audio' pushable to the scan of c group: p.name order: units DESC (alias of sum(oi.quantity)) limit: 10
Planner and optimizer: candidates → cost → chosen plan
Candidates. For each table, the access paths: categories has no index on name, so only a Seq Scan with the pushed-down filter. products has products_category_id_idx, but the predicate arrives through a join, not a constant, and the table is 4 pages — a Seq Scan is costed cheaper than any index path. order_items has an index on order_id, which the query does not constrain; Seq Scan. For each of the two joins, the condition is an equality, so a Hash Join is available; this engine builds the hash on the right-hand input. Join order is kept as written: (c ⋈ p) ⋈ oi, which is also the order PostgreSQL would find, because it starts from the most selective table.
Cost. Seq Scan categories: 1 page + 8 rows ≈ 1.1, estimated 2 rows out (the engine assumes 30% for a filter it cannot look up). Seq Scan products: 4 pages + 240 rows = 6.4. Hash Join: ≈ 8.5, estimated 2 rows. Seq Scan order_items: 125 pages + 9,580 rows ≈ 220.8. Hash Join: ≈ 253, estimated 2 rows — the join-selectivity model in this engine is simple and this estimate will be badly wrong. HashAggregate: +20. Sort: +1. Limit: free. Total ≈ 274 cost units, of which 80% is reading and hashing order_items.
Chosen plan. The one plan the engine builds, which EXPLAIN prints. In PostgreSQL there would have been several dozen candidates and the survivor would look the same except that the hash would be built on the 30-row side, not the 9,580-row side.
Limit (cost=0.00..273.91 rows=30) (actual rows=10 loops=1)
-> Sort (quicksort) (cost=0.00..273.91 rows=30) (actual rows=30)
Sort Key: units DESC
-> HashAggregate (cost=0.00..273.18 rows=30) (actual rows=30)
Group Key: p.name
-> Hash Join (cost=0.00..253.49 rows=2) (actual rows=1938) ← estimate 2, actual 1,938
Hash Cond: oi.product_id = p.id
-> Hash Join (cost=0.00..8.50 rows=2) (actual rows=30)
Hash Cond: p.category_id = c.id
-> Seq Scan on categories c (cost=0.00..1.08 rows=2) (actual rows=1)
Filter: c.name = 'Audio'
Rows Removed by Filter: 7
-> Hash (rows=240)
-> Seq Scan on products p (cost=0.00..4.40 rows=240) (actual rows=240)
-> Hash (rows=9580)
-> Seq Scan on order_items oi (cost=0.00..124.80 rows=9580) (actual rows=9580)Executor and storage: buffer pool → scan → join → aggregate → sort → limit
Buffer pool. The executor opens the plan; the leaves will request 1 + 4 + 125 = 130 pages. On a cold cache each is a read from the heap file into a free frame; on a warm cache each is a hash lookup in the page table and a pin. Either way the operators above never see a disk — they see pages.
Scan (categories). Linear search over 8 rows on one page, filter name = 'Audio' evaluated per row: 1 row kept, Rows Removed by Filter: 7. DSA: Linear Search. Join (categories ⋈ products). Build: 240 product rows into a hash table keyed on category_id (memory: 240 entries). Probe: the single category row hashes to its bucket; 30 products match. DSA: Hash Table. Scan (order_items). 125 pages, 9,580 rows, no filter. Join (⋈ order_items). Build: 9,580 rows hashed on product_id — the expensive part of the whole query, and the one PostgreSQL would do the other way round. Probe: 30 rows, each finding on average 65 line items: 1,938 output rows. The estimate said 2; every operator above was planned for 2 rows and got 1,938 — harmless here because the operators above are cheap, dangerous in general.
Aggregate. HashAggregate keyed on p.name: one hash entry per product accumulating sum(quantity); 1,938 rows in, 30 groups out; memory proportional to groups, not rows. A pipeline breaker — nothing is emitted until all 1,938 rows have been consumed. DSA: Hash Map. Sort. 30 rows by units DESC, quicksort in memory; another pipeline breaker, but a 30-row one. DSA: Quick Sort (a real engine with a LIMIT uses a bounded heap — top-N heapsort — so it never holds more than 10 rows: Min-Heap). Limit. A counter: after 10 rows from the Sort, stop. Result. 10 rows serialised to the client — Orbit Ember 949 first, with 1,508 units.
| Stage | What happens | Algorithm | Memory | Storage | DSA |
|---|---|---|---|---|---|
| Parser | 48 tokens → ~20-node AST | recursive descent | KB | — | stack, tree |
| Binder | names → oids, columns, types | tree walk + scope chain | KB | catalog cache | tree traversal |
| Planner | access paths, join methods | enumerate + cost | plan trees | statistics only | DAG |
| Optimizer | one plan, cost ≈ 274 | argmin over candidates | — | — | — |
| Buffer pool | 130 page requests | page-table lookup, Clock | shared_buffers | heap files | LRU cache |
| Seq Scan categories | 8 rows → 1 | linear scan + filter | 1 page | 1 page | linear search |
| Hash Join #1 | 1 × 240 → 30 | build (240) + probe (1) | 240 entries | 4 pages via scan | hash table |
| Seq Scan order_items | 9,580 rows | linear scan | 1 page at a time | 125 pages | linear search |
| Hash Join #2 | 30 × 9,580 → 1,938 | build (9,580) + probe (30) | 9,580 entries | — | hash table |
| HashAggregate | 1,938 → 30 groups | hash by key, accumulate sum | 30 entries | — | hash map |
| Sort | 30 rows by units DESC | quicksort (top-N heap in real engines) | 30 rows | — | quicksort / heap |
| Limit | 30 → 10 | counter | — | — | — |
| Result | 10 rows to the client | wire encoding | send buffer | — | queue |
What PostgreSQL would do differently
The shape is the same; three details differ. Hash build side: PostgreSQL builds on the smaller input, so the second join would hash the 30 products and probe with 9,580 order items — same output, 300× less memory. Join selectivity: it would estimate the join at ~1,200 rows from the foreign-key relationship and n_distinct of product_id, not 2. Sort with LIMIT: Sort Method: top-N heapsort keeps only ten rows in a bounded heap instead of sorting all thirty — trivial here, decisive when the aggregate produces a million groups.
It would also report Buffers: shared hit=130 (or read=130 on a cold cache), which is the buffer-pool line this platform shows as pages, and if order_items had an index on product_id it would consider an Index Nested Loop from the 30 products into it — 30 descents instead of a 125-page scan — and probably choose it.
Key points
- Text → tokens → AST → bound tree → candidates → cost → one plan → operators pulling rows through the buffer pool → result. Every EXPLAIN line is one of these steps.
- Rows shrink early (8 → 1 → 30) and grow once (30 → 1,938); the planner’s job is to keep the growth as late as possible, and predicate pushdown is how it starts.
- The expensive step is the scan and hash of the largest table; the aggregate, sort and limit are cheap because they see 30 rows.
- HashAggregate and Sort are pipeline breakers; Limit above them trims output but does not shorten work — unless the engine uses a top-N heap.
- Estimated 2 rows vs actual 1,938 on the join is the signature of a weak selectivity model; in a bigger plan it would have chosen the wrong join above it.
- A read-only query touches the parser, planner, executor and buffer pool — never the WAL or the lock manager under MVCC.
Follow the query — internals view
- ↓
- ↓
- ↓
- ↓
- ↓
- ↓
- ↓
- ↓
- ↓
- ↓
- ↓
- ↓
- ↓
- ↓
- ↓
The statement arrives as text over the connection.
SELECT p.name, sum(oi.quantity) AS units FROM categories c JOIN products p ON p.category_id = c.id JOIN order_items oi ON oi.product_id = p.id WHERE c.name = 'Audio' GROUP BY p.name ORDER BY units DESC LIMIT 10;
- Estimated rows
- 10
- Actual rows
- 10
- Estimated cost
- 273.91
- Time
- 0.000 ms
Try it in the playground
EXPLAIN ANALYZE SELECT p.name, sum(oi.quantity) AS units FROM categories c JOIN products p ON p.category_id = c.id JOIN order_items oi ON oi.product_id = p.id WHERE c.name = 'Audio' GROUP BY p.name ORDER BY units DESC LIMIT 10;
SELECT p.name, sum(oi.quantity) AS units FROM categories c JOIN products p ON p.category_id = c.id JOIN order_items oi ON oi.product_id = p.id WHERE c.name = 'Audio' GROUP BY p.name ORDER BY units DESC LIMIT 10;
CREATE INDEX order_items_product_id_idx ON order_items (product_id); EXPLAIN ANALYZE SELECT p.name, sum(oi.quantity) AS units FROM categories c JOIN products p ON p.category_id = c.id JOIN order_items oi ON oi.product_id = p.id WHERE c.name = 'Audio' GROUP BY p.name ORDER BY units DESC LIMIT 10;
When to use — and when not
- Following a query end to end fits whenever a plan is confusing: name the stage, then the operator, then the estimate that went wrong.
- The same walk applies to any statement you paste into the playground — the interactive accepts
?sql=from it.
- For a one-row primary-key lookup the walk is Index Scan → Result and the interesting part is the buffer pool, covered by Follow a Read Through the Engine.
- For writes the storage half is different — WAL, dirty pages, locks — and belongs to Follow a Write Through the Engine.
Failure modes
- Hashing the large side: memory proportional to the biggest table instead of the smallest — this engine does it, and so does any planner that misestimates which side is smaller.
- Join estimate off by three orders of magnitude; a nested loop chosen above it would run 1,938 times instead of twice.
- Aggregating above a fan-out join: sum(o.total) counted once per line item — a correctness bug the plan will not flag.
- Reading the plan top-down and blaming Limit or Sort; the cost is in the leaves and the join just above them.
Where you meet this
Back up to the practical layer, and across to the rest of Engineer Atlas.