How a Query Executes: Planner and Executor

After parsing and rewriting, the planner has a query tree: which tables, which predicates, which joins, which aggregates. For each table it considers every access path — sequential scan, each usable index. For each join it considers every order and every algorithm. For sorts and aggregates it considers whether an input is already ordered. Each candidate gets a cost: an abstract number built from page reads (sequential = 1.0, random = 4.0) and per-row CPU work (0.01 per tuple, 0.0025 per operator).

The row counts that feed those costs come from statistics gathered by ANALYZE: rows per table, distinct values per column, most-common values, histograms. The planner never looks at the data itself while planning. If the statistics are stale, the plan is optimised for a table that no longer exists. That is why "the query got slow and nothing changed" is so often answered by running ANALYZE.

Seq Scan reads every page in order. Right for small tables and unselective predicates. Index Scan walks the index for matching entries and fetches each row from the table by pointer. Right for selective predicates. Index Only Scan answers from the index alone when every needed column is in it. Bitmap Index Scan + Bitmap Heap Scan collects matching row pointers from one or more indexes into a bitmap, sorts them by page, then reads the pages in physical order — the middle ground for medium selectivity, and how the planner combines two indexes for an OR.

Nested Loop: for each outer row, run the inner plan. O(outer × inner) if the inner is a scan, O(outer × log inner) if it is an index lookup — the index makes all the difference. Chosen when the outer side is small or the inner has an index on the join key. Hash Join: build a hash table on the smaller input, probe with the larger. O(n + m), needs an equality condition and memory for the build side; spills to disk in batches if the build exceeds work_mem. The default for large joins. Merge Join: both inputs sorted on the key, walked together. O(n + m) after sorting; wins when indexes already provide the order or the output must be sorted anyway.

You do not pick the algorithm. You enable good ones: an equality join condition (hash and merge need it), an index on the inner join column (makes nested loop cheap), and accurate statistics (so the planner picks the right one).

Sort materialises its whole input before emitting the first row — it is a pipeline breaker. In memory up to work_mem, then an external merge on disk. Avoided entirely when an index provides the order. HashAggregate groups by hashing, memory proportional to group count. GroupAggregate groups a sorted input in a stream. Limit stops pulling rows from its child once it has enough — which is only useful if the child can produce rows incrementally; a Limit over a Sort still sorts everything.

The executor is a tree of iterators: each node asks its child for the next row. That pull model is why LIMIT over an index scan stops early, why a Sort under it does not, and why the top of the plan is the last thing to run.