--- title: "PostgreSQL Internals - Module 5: Query pipeline " description: "Trace a SQL query through PostgreSQL's full pipeline - from raw text through the parser, rewriter, planner, and executor with internals at each stage." author: "Samba Siva" published: 2026-04-21T04:38:01.149Z updated: 2026-11-04T02:23:51.085Z tags: - "PostgreSQL" - "Technical" - "PGInternals" url: "https://sambasivareddy.in/blog/postgresql-internals-module-5-query-pipeline-parser-planner-executor" --- # PostgreSQL Internals - Module 5: Query pipeline In the previous blog, we have explored about the WAL and how it will helpful for Checkpoints, Crash Recovery and Replications. Every SQL statement you send to PostgreSQL travels through a precise pipeline before a single row is returned. This post traces that journey end-to-end, from raw text bytes arriving over the wire to result rows going back to the client. * * * ## Part 1: The Big Picture Consider a client sending the query: `SELECT * FROM orders WHERE status = 'pending' ORDER BY created_at`. Here's how it travels through the pipeline: ``` "SELECT * FROM orders WHERE status = 'pending' ORDER BY created_at" SQL Statement → Parser (returns Parse Tree) → Analyzer (returns Query Tree) → Rewriter applies Rules, Views (returns a list of Query Tree) → Planner (return Plan Tree) → Executor → Result Rows ``` _In the above flow, the output of the previous stage will act as input to the next stage._ * * * ## Part 2: The Parser **Input**: Raw SQL statement **Output**: a `RawStmt` parse tree **Checks**: Checks for syntax purely, no semantic meaning This parser lives in `src/backend/parser/gram.y` - a yacc/bison grammar file. It performs only **"syntactic validation"** i.e., it checks that the SQL is grammatically correct but has no idea whether the tables or columns actually exist. **It uses a LALR(1) parsing algorithm, tokens are read left-to-right, with decisions made using a single token of lookahead.** ### What the parser produces **Input:** ``` SELECT id, name FROM orders o WHERE o.status = 'pending'; ``` **Parser Pipeline** ``` SQL text: "SELECT id,name FROM orders o WHERE o.status = 'pending'" │ V Lexer (scan.l) │ tokenizes into: │ SELECT id,name FROM orders WHERE status = $1 │ (keyword)(ident)(sep)(ident)(keyword)(ident)(keyword)(ident)(op)(param) │ V Parser (gram.y) │ builds parse nodes: │ SelectStmt │ targetList: [ResTarget(ColumnRef("id"))] │ targetList: [ResTarget(ColumnRef("name"))] │ fromClause: [RangeVar("orders")] │ whereClause: A_Expr("=", ColumnRef("status"), ParamRef(1)) │ V RawStmt (List of raw parse nodes) ``` **Output:** Parse Tree of C structs ``` SelectStmt | |--- targetList | |- ResTarget → ColumnRef("id") | |- ResTarget → ColumnRef("name") |--- fromClause | |- RangeVar (relname="orders", inh=true) |--- whereClause | |- A_Expr (op="=") | |- ColumnRef("status") | |- A_Const(str="pending") ``` > At this point "orders" is just a string, not a table. "status" is just a name, not a column. The parser doesn't know or care. ### Parse Node Types - the Full Taxonomy ``` /* Statement nodes */ SelectStmt, InsertStmt, UpdateStmt, DeleteStmt CreateStmt, AlterTableStmt, DropStmt TransactionStmt, ExplainStmt, CopyStmt VacuumStmt, AnalyzeStmt, IndexStmt /* Expression nodes */ A_Expr — binary/unary operator expression ColumnRef — reference to a column (just a name at this stage) A_Const — a literal constant (integer, float, string, bool, null) ParamRef — a query parameter ($1, $2, ...) FuncCall — function call (name + args, no OID yet) TypeCast — explicit cast: expr::type SubLink — subquery in expression context (IN, EXISTS, ANY, ALL) CaseExpr — CASE WHEN ... THEN ... ELSE ... END CoalesceExpr — COALESCE(...) BoolExpr — AND, OR, NOT A_ArrayExpr — ARRAY[...] RowExpr — ROW(...) ``` ### What the parser catches ``` -- Syntax error caught by parser SELECT * FORM orders; -- ERROR: syntax error at "FORM" SELECT * FROM; -- ERROR: syntax error at ";" -- Not caught by parser (semantic errors) SELECT * FROM nonexistent_table; -- passes the parser phase SELECT fake_col FROM orders; -- passes the parser phase ``` * * * ## Part 3: The Analyzer (Semantic Analysis) **Input:** `RawStmt` parse tree **Output:** `Query` tree (fully resolved, typed) The analyzer lives in `src/backend/parser/analyze.c`. This is where PostgreSQL looks up system catalogs like `pg_class`, `pg_attribute`, `pg_type`, `pg_operator`, and others - to resolve every name to an **OID (Object Identifier)** and every expression to a type. ### What the analyzer does Note: The walkthrough below follows directly from the parse tree produced in **Part 2**, and the same resolution process applies to more complex queries. **RangeVar("orders")** 1. Lookup **pg\_class** for the relname = 'orders' 2. Resolves to OID 24601 (example value) and relkind = 'r' (regular table) 3. Replace with **RangeTblEntry** struct like below: ``` rtable[1]: RTE_RELATION relid=24601 (orders) alias="o" ``` **ColumnRef("id")** 1. Lookup **pg\_attribute** WHERE attrelid=24601(orders) AND attname='status' 2. Resolve to atttypid=22 (integer type OID), attnum=1 (position of this column in table) 3. Replace with **Var** struct like below ``` o.id → Var(varno=1, varattno=1, vartype=INT4OID) o.name → Var(varno=1, varattno=2, vartype=TEXTOID) o.status → Var(varno=1, varattno=3, vartype=TEXTOID) ``` **A\_Const(str="pending")** 1. type = text which will be inferred from the context 2. Replace with Const struct like below: ``` Const(consttype=25, constvalue="pending") ``` **A\_Expr(op="=", left=ColumnRef, right=A\_Const)** 1. Lookup pg\_operator WHERE oprname = '=' AND oprleft = 25 AND oprright = 25 2. Resolve to operator OID 98 (for =). 3. Replaces with OpExpr struct like below: ``` OpExpr(opno=98, args=[ Var(varno=1, varattno=3, vartype=TEXTOID), Const(consttype=25, constvalue="pending") ] ) ``` After analysis, every node in the tree is fully typed and resolved to their identifiers (OIDs). Unknown tables or columns fails here with the errors we used to seeing: ``` SELECT * FROM nonexistent_table; -- ERROR: relation "nonexistent_table" does not exist SELECT fake_col FROM orders; -- ERROR: column "fake_col" does not exist ``` ### The Query Struct ``` typedef struct Query { CmdType commandType; /* SELECT, INSERT, UPDATE, DELETE */ bool hasAggs; /* has aggregate functions? */ bool hasSubLinks; /* has subqueries? */ bool hasWindowFuncs; /* has window functions? */ List *rtable; /* range table: list of all tables used */ FromExpr *jointree; /* FROM and WHERE clauses */ List *targetList; /* SELECT columns / SET clauses */ Node *havingQual; /* HAVING clause */ List *groupClause; /* GROUP BY */ List *sortClause; /* ORDER BY */ Node *limitOffset; /* OFFSET */ Node *limitCount; /* LIMIT */ } Query; ``` * * * ## Part 4: The Rewriter **Input:** `Query` tree **Output:** List of `Query` trees (may expand one query into multiple) The rewriter lives in `src/backend/rewrite/rewriteHandler.c` and applies **rewrite rules** stored in `pg_rewrite`. One such important use case being **view expansion**. ### View expansion ``` CREATE VIEW active_orders AS SELECT * FROM orders WHERE status != 'cancelled'; -- Now suppose we ran the following query SELECT id FROM active_orders WHERE created_at > '2026-04-21'; ``` The rewriter: 1. Detects `active_orders` is a view (from `pg_class.relkind = 'v'` ) 2. Fetches the view definition from `pg_rewrite` . 3. Substitutes the view's `SELECT` in place of the `RangeTblEntry` 4. Merges `WHERE created_at > '2026-04-21'` with the view's quals. Result after rewriting: ``` -- After rewriting SELECT id FROM orders WHERE status != 'cancelled' AND created_at > '2026-04-21'; ``` The planner never sees the view name, it sees the fully expanded query and it's query tree. Views have zero runtime overhead - they are purely a rewrite-time substitution. ### Row Security Policies ``` CREATE POLICY user_isolation ON orders USING (user_id = current_user_id()); ``` The rewriter appends the policy's `USING` expression to the `WHERE` clause of every query touching that table. The planner receives a query that already has the security filter added. * * * ## Part 5: The Planner **Input**: `Query` tree **Output**: `PlannedStmt` containing a tree of `Plan` nodes The planner is the most intellectually complex part of PostgreSQL (`src/backend/optimizer/`). **Its job: enumerate every possible execution strategy and pick the cheapest one.** It's organized into three main phases: 1. **Preprocessing**: Simplify quals, pull up subqueries, reduce ops 2. **Path Generation**: Enumerate all access paths for each relation and join 3. **Plan Building**: Convert the cheapest path tree into a Plan tree ### Step 1: Preprocessing ``` SELECT * FROM orders WHERE status = 'pending' AND (1 = 1) -- constant true --> removed AND amount > 0 AND amount > 50 -- simplified to amount > 50 AND id IN (SELECT order_id FROM order_items WHERE qty > 10); ``` The preprocessor: - Folds constants: 1=1 which will true always and it won't effect the results anyway, so will be removed from quals. - Simplifies redundant predicates: amount > 0 and amount > 50 simply means amount > 50. - Attempts to pull up the subquery as a join (if safe to do so) - Flattens nested AND/OR into flat clause lists. ### Step 2: Generate RelOptInfo for each relation For every table in the query, the planner creates a `RelOptInfo` struct and gathers statistics from `pg_statistic` (populated by `ANALYZE`): ``` -- What ANALYZE collects, readable via pg_stats: SELECT attname, n_distinct, -- estimated distinct values correlation, -- physical sort order correlation most_common_vals, -- MCV list most_common_freqs, -- frequency of each MCV histogram_bounds -- bucket boundaries for non-MCV values FROM pg_stats WHERE tablename = 'orders' AND attname = 'status'; ``` ### Step 3: Estimate selectivity and row counts For each `WHERE` predicate, the planner estimates its selectivity i.e. what fraction of rows expected to pass the filter: ``` WHERE status = 'pending' -- Look up 'pending' in most_common_vals → freq = 0.15 -- Estimated rows = 1,000,000 * 0.15 = 150,000 WHERE created_at > '2026-01-01' -- Use histogram_bounds to find fraction above threshold -- Estimated rows = 1,000,000 * 0.35 = 350,000 WHERE status = 'pending' AND created_at > '2026-01-01' -- Assume independence (unless extended stats created): -- 1,000,000 * 0.15 * 0.35 = 52,500 rows ``` ### Step 4: Generate access paths for each relation For a single table `orders`, the planner generates all the possible paths to access that table by various modes of scanning like seqscan (read page by page sequentially), index scan (scan the index) etc. To decide what best among these, planner estimates the cost of each possible path/scan and picks the best one. ``` SeqScan(orders) cost = seq_page_cost × pages + cpu_tuple_cost × rows = 1.0 × 10000 + 0.01 × 1000000 = 20,000 IndexScan(orders_status_idx) cost = random_page_cost × index_pages + cpu_index_tuple_cost × index_rows + random_page_cost × heap_pages_fetched = 4.0 × 500 + 0.005 × 150000 + 4.0 × 15000 = 2000 + 750 + 60000 = 62,750 ← more expensive than seqscan here! BitmapIndexScan + BitmapHeapScan cost = index_cost + 0.1 × heap_pages (sequential after sort) = 750 + 0.1 × 15000 = 2,250 ← much cheaper ``` This is why a low-selectivity index is often skipped - the planner does real cost math, not guesswork. **The cost parameters** ``` SHOW seq_page_cost; -- 1.0 (baseline: cost of one sequential page read) SHOW random_page_cost; -- 4.0 (default: random I/O is 4× slower) -- set to 1.1 for SSDs! SHOW cpu_tuple_cost; -- 0.01 SHOW cpu_index_tuple_cost; -- 0.005 SHOW cpu_operator_cost; -- 0.0025 SHOW effective_cache_size; -- 4GB (planner's estimate of OS + PG cache) ``` ### Step 5: Join ordering generation For multi-table queries, the planner must find the optimal join order. **_With N tables there are N! possible orderings_**. For small N (<= join\_collapse\_limt (default 8)), the planner uses dynamic programming to find the true optimum. For large N, it switches to a Genetic Algorithm (GEQO) ``` -- Three-table join: orders, customers, products -- Possible orderings: 3! = 6 -- (orders ⋈ customers) ⋈ products -- (orders ⋈ products) ⋈ customers -- (customers ⋈ products) ⋈ orders -- (customers ⋈ orders) ⋈ products -- (products ⋈ customers) ⋈ orders -- (products ⋈ orders) ⋈ customers ``` The Planner tries all possible 6 combinations, estimates the cost of each and picks the cheapest in all of them. ### Step 6: Choose Join Algorithms For each join, planner has three algorithms, from which it picks the best possible one. The three algorithms are: 1. Nested Loop Join 2. Hash Join 3. Merge Join **Nested Loop Join** ``` Sample Algorithm for each outer row: scan inner for matching rows ``` - Cost would be = outer\_rows x inner\_scan\_cost - Good for small outer table and indexed inner table. **Hash Join** ``` Sample Algorithm build has table from smaller relation probe with larger relation ``` - Cost would be = build\_cost (for hash) + probe\_cost - Good for large equijoins, no useful indexes **Merge Join** ``` Sample Algorithm sort both inputs on join key and merge them ``` - Cost would be = sort\_cost\_outer\_table + sort\_cost\_inner\_table + merge\_cost - Good for inputs that are already sorted (index scan) or ORDER BY on join key ### Step 7: Build the final plan tree Once the cheapest path is choosen, at this phase it generates the `PlannedStmt` containing the tree of `PlannedStmt` nodes which will be passed to the Executor phase. Here I am showing that plan using EXPLAIN. ``` EXPLAIN SELECT o.id, c.name FROM orders o JOIN customers c ON o.customer_id = c.id WHERE o.status = 'pending' ORDER BY o.created_at; --------------------------------------------------------------- EXPLAIN PLAN generated on cheapest final plan tree --------------------------------------------------------------- Sort (cost=12500..12600 rows=50000) Sort Key: o.created_at → Hash Join (cost=2500..10000 rows=50000) Hash Cond: (o.customer_id = c.id) → Seq Scan on orders o (cost=0..8000 rows=50000) Filter: (status = 'pending') → Hash (cost=1500..1500 rows=100000) → Seq Scan on customers c (cost=0..1500 rows=100000) ``` * * * ## Part 6: The Executor **Input**: `PlannedStmt` **Output**: Tuple stream (rows returned to client) The executor uses the Volcano/Iterator model, where every plan node implements three operations: ``` ExecInitNode(node) /* open: allocate state, initialize children */ ExecProcNode(node) /* next: return one tuple at a time (or NULL if done) */ ExecEndNode(node) /* close: free resources */ ``` > The top node is called with ExecProcNode(). It calls its children, which call their children, pulling tuples up through the tree one at a time. This is the pull model i.e., the data flows upward on demand. A plan tree is a collection of nodes each with their own responsibilities. One node's responsibility is to read the data from the page, while other is to order the data fetched by other node etc. Let's see some of those such nodes. ### Scan nodes (leaves of the plan tree) Like 1. SeqScan 2. IndexScan 3. BitmapIndexScan 4. IndexOnlyScan ``` SeqScan reads pages from the buffer pool sequentially applies filter quals to each tuple calls heap_getnext() in a loop IndexScan calls index_getnext() to get TIDs from index for each TID: calls heap_fetch() to get the tuple applies any remaining filter quals BitmapIndexScan + BitmapHeapScan BitmapIndexScan: scans index, builds a bitmap of matching page+offset BitmapHeapScan: reads pages in physical order using the bitmap (avoids random I/O by sorting TIDs first) IndexOnlyScan calls index_getnext() checks visibility map — if all_visible: return tuple from index leaf if NOT all_visible: fetch from heap to check visibility never reads heap at all for fully-visible pages ``` ### Join Nodes Like 1. NestLoop 2. HashJoin 3. MergeJoin ``` NestLoop outer_slot = ExecProcNode(outer_child) while outer_slot not NULL: inner_slot = ExecProcNode(inner_child) ← rescanned for each outer while inner_slot not NULL: if qual matches: emit joined tuple inner_slot = ExecProcNode(inner_child) outer_slot = ExecProcNode(outer_child) HashJoin ExecInitNode: build hash table from inner child ExecProcNode: outer_slot = ExecProcNode(outer_child) hash outer_slot on join key probe hash table → emit matching tuples MergeJoin assumes both inputs sorted on join key merge using two pointers advancing through sorted streams ``` ### Other nodes ``` Sort reads all tuples from child, sorts in work_mem if > work_mem: spills to temp files (external merge sort) HashAgg GROUP BY using a hash table (one entry per group) if > work_mem: spills to disk Limit counts tuples, stops after N Append union of multiple children (used for partitioned tables) Result evaluates a constant expression (no child scan) Materialize buffers child output (lets inner of NestLoop re-read) ``` * * * ## Part 7: EXPLAIN ANALYZE ``` EXPLAIN (ANALYZE, BUFFERS, FORMAT TEXT) SELECT o.id, c.name FROM orders o JOIN customers c ON o.customer_id = c.id WHERE o.status = 'pending' ORDER BY o.created_at LIMIT 100; ``` Sample output: ``` Limit (cost=14234..14234 rows=100 width=36) (actual time=234.5..234.6 rows=100 loops=1) -> Sort (cost=14234..14359 rows=50000 width=36) (actual time=234.5..234.5 rows=100 loops=1) Sort Key: o.created_at Sort Method: top-N heapsort Memory: 36kB ← LIMIT lets planner use heapsort -> Hash Join (cost=2500..10000 rows=50000 width=36) (actual time=45.2..198.3 rows=50000 loops=1) Hash Cond: (o.customer_id = c.id) Buffers: shared hit=8420 read=1580 ← 8420 from cache, 1580 from disk -> Seq Scan on orders o (cost=0..8000 rows=50000 width=28) (actual time=0.1..120.4 rows=50000 loops=1) Filter: (status = 'pending') Rows Removed by Filter: 950000 ← 950k rows scanned but discarded Buffers: shared hit=5420 read=1580 -> Hash (cost=1500..1500 rows=100000 width=16) (actual time=44.8..44.8 rows=100000 loops=1) Buckets: 131072 Batches: 1 Memory Usage: 5452kB -> Seq Scan on customers c (cost=0..1500 rows=100000 width=16) (actual time=0.1..22.1 rows=100000 loops=1) Buffers: shared hit=3000 Planning Time: 2.3 ms Execution Time: 234.8 ms ``` ### How to read Every node shows **estimated (cost=X..Y rows=N)** and **actual (actual time=A..B rows=N loops=L)** - cost=0..1500 - 0 - cost to return fist row/tuple - 1500 - cost to return all the tuples - actual time=0.1..22.1 - 0.1 - time taken for first row to return (ms) - 22.1 - total time taken for all rows to return - rows=50000 - actual rows returned - loops=1 - how many times this node was executed. - Buffers: shared hit=5420 read=1580 - hit = pages served from shared\_buffers (no disk I/O) - read = pages read from disk - From we can calculate cache hit ratio = (5420 / (5420 + 1580))x100% = 77% of data read from the cache itself ### Key things to look for Consider you have table with 1M rows ``` Rows Removed by Filter: 950000 → index would help here — you're scanning 1M rows to get 50K Sort Method: external merge Disk: 128000kB → increase work_mem Hash Batches: 8 (instead of 1) → hash table spilled to disk — increase work_mem actual rows >> estimated rows → stale statistics — run ANALYZE loops=50000 on an inner node → nested loop with 50K outer rows — consider hash join set enable_nestloop = off to test ``` * * * ## Part 8: Advanced Executions ### Parallel Query Since PostgreSQL 9.6, the executor can parallelize sequential scans and joins. ``` SET max_parallel_workers_per_gather = 4; -- Execute EXPLAIN SELECT count(*) FROM large_orders WHERE amount > 100; ``` Output: ``` Finalize Aggregate (cost=284000..284001 rows=1) → Gather (cost=283999..284000 rows=1 workers=4) → Partial Aggregate → Parallel Seq Scan on large_orders Filter: (amount > 100) ``` How it works: ``` Leader process │ │── fork → Worker 1 ── scans blocks 0..249999 │── fork → Worker 2 ── scans blocks 250000..499999 │── fork → Worker 3 ── scans blocks 500000..749999 │── fork → Worker 4 ── scans blocks 750000..999999 │ │ Each worker computes Partial Aggregate (partial count) │ Sends result through a DSM (dynamic shared memory) queue │ Gather node collects partial results Finalize Aggregate combines partial counts → final count ``` Block assignment uses a **parallel block scan**, workers atomically increment a shared block counter, so each block is scanned by exactly one worker. ### Query Caching - The Plan Cache PostgreSQL caches plans for **prepared statements**: ``` PREPARE get_orders(text) AS SELECT * FROM orders WHERE status = $1 ORDER BY created_at; EXECUTE get_orders('pending'); EXECUTE get_orders('cancelled'); ``` **Generic vs Custom Plans** For the first 5 executions, PostgreSQL builds a custom plan - it substitues the actual parameter value and plans with full statistics knowledge. After 5 executions, it compares the average custom plan cost versus a generic plan (one built without knowing the parameter value). If the generic plan is cheaper (e.g., always a seq scan regardless of parameter), PostgreSQL switches to the generic plan. ``` -- See what plan is being used: EXPLAIN (ANALYZE) EXECUTE get_orders('pending'); -- Look for "Generic Plan" or "Custom Plan" in output (PG 16+) -- Force generic plan: SET plan_cache_mode = force_generic_plan; -- Force custom plan (re-plan every execution): SET plan_cache_mode = force_custom_plan; ``` This matters for **skewed data** — if `status='pending'` has 80% of rows but `status='archived'` has 0.001%, a generic plan can be catastrophically wrong for one of them. * * * ## Conclusion Every query you write travels farther than it looks. A single `SELECT` passes through a lexer, a grammar parser, a semantic analyzer resolving names to OIDs, a rewriter substituting views and policies, a cost-based planner enumerating thousands of execution strategies, and finally an executor pulling tuples through a tree of nodes — one row at a time. Understanding this pipeline changes how you think about performance. Slow query? Now you know whether to look at statistics staleness (Analyzer/Planner), missing indexes (Path Generation), skewed plan caching (Generic vs Custom), or work\_mem pressure (Sort/HashAgg). `EXPLAIN ANALYZE` stops being a black box and becomes a direct window into the decisions PostgreSQL made at each stage. In the next module, we'll go deeper into Indexing Internals. * * * ## What's Next → Module 6: Indexing Internals In Module 6, we'll go deep into how PostgreSQL builds and traverses B-Tree indexes, how the page layout looks on disk, what happens during index splits, and why an index scan can sometimes hurt more than it helps. We'll also cover GIN, GiST, and BRIN — when each one exists and what problem it was designed to solve.