vault

The Query Processing Pipeline

13 min read

The Query Processing Pipeline

Between the SQL text a client sends and the bytes a storage engine reads sits a small compiler. A SELECT string is not executed directly — it is parsed into a syntax tree, analyzed against the catalog so that names become concrete tables, columns, functions and types, rewritten to expand views and apply rules, planned/optimized from that logical query into a concrete tree of physical operators, and finally handed to an executor that turns the tree into work. PostgreSQL’s own internals chapter frames the job as tracing “how a query is processed … from the point at which a query is received, to the point at which the results are returned to the client” (PostgreSQL, Overview of PostgreSQL Internals). Each stage consumes one intermediate representation and produces the next — raw parse tree → query tree → rewritten query tree(s) → plan tree — and the whole reason EXPLAIN exists is to let you inspect the last of these before it runs. This is the CMU 15-445 course spine “SQL → parse → bind → optimize → execute,” the frame every relational engine shares even when the internal names differ (CMU 15-445/645).

Mental Model

Think of the database front end as a language compiler and the storage engine as the CPU. Just as a C compiler lexes, parses, type-checks, optimizes, and emits machine code, the query processor lexes SQL keywords, parses to a grammar tree, resolves names against the schema (its “symbol table” is the system catalog), applies rewrite rules, chooses an optimized physical plan, and emits an operator tree the executor interprets. The key insight is that each arrow in the pipeline is a total function from one well-defined data structure to another, and the pipeline is staged deliberately: raw parsing is kept free of catalog lookups so it can run before a transaction even opens, and semantic meaning is layered on only afterward.

flowchart TB
  SQL["SQL text<br/>(SELECT ... FROM ... WHERE ...)"]
  SQL -->|"lex + grammar<br/>(scan.l, gram.y)"| PT["Raw parse tree<br/>syntax only, no catalog"]
  PT -->|"parse analysis / bind<br/>catalog lookup, type &amp; semantic checks"| QT["Query tree<br/>(names → OIDs, types resolved)"]
  QT -->|"rewrite / rule system<br/>view expansion, RLS, ON-SELECT rules"| QT2["Rewritten query tree(s)"]
  QT2 -->|"planner / optimizer<br/>enumerate paths, cost, pick cheapest"| PLAN["Plan tree<br/>physical operators (Seq Scan, Hash Join, Sort...)"]
  PLAN -->|"executor<br/>pull tuples through the tree"| RES["Result rows to client"]
  EXPL["EXPLAIN shows this"] -.-> PLAN
  EXPLA["EXPLAIN ANALYZE runs &amp; measures"] -.-> RES

The five-stage query pipeline as PostgreSQL implements it. What it shows: each stage transforms one intermediate representation into the next — the raw parse tree captures only syntax, the query tree adds semantics (resolved names, types), the rewriter rewrites query-tree-to-query-tree, the planner turns the logical query into a physical plan tree, and the executor runs that tree. The insight to take: parsing and planning are separated on purpose — the parser deliberately does no catalog lookups so it can run outside a transaction, and everything “smart” (which index, which join order) is concentrated in the planner. When you run EXPLAIN, you are printing the plan tree; when you run EXPLAIN ANALYZE, you additionally execute it and annotate each node with real row counts and timings.

Mechanical Walk-through

Stage 1 — Parse: SQL text to a raw parse tree

The first stage “has to check the query string (which arrives as plain text) for valid syntax. If the syntax is correct a parse tree is built up and handed back; otherwise an error is returned” (PostgreSQL, The Parser Stage). PostgreSQL builds this parser with the classic Unix tools: a lexer (scan.l, compiled by flex) that recognizes “identifiers, the SQL key words etc. For every key word or identifier that is found, a token is generated,” and a grammar (gram.y, compiled by bison) of “grammar rules and actions … used to build up the parse tree.” The crucial property of this stage is that “it does not make any lookups in the system catalogs, so there is no possibility to understand the detailed semantics of the requested operations.” A query like SELECT foo FROM bar parses successfully into a well-formed tree even if neither bar nor foo exists — syntax is all that has been checked. The reason for this strict separation is stated plainly: “system catalog lookups can only be done within a transaction, and we do not wish to start a transaction immediately upon receiving a query string.”

Stage 2 — Analyze / bind: raw parse tree to query tree

The transformation process (parse analysis, the “binder” in other systems’ vocabulary) “takes the tree handed back by the parser as input and does the semantic interpretation needed to understand which tables, functions, and operators are referenced by the query. The data structure that is built to represent this information is called the query tree” (PostgreSQL, The Parser Stage). This is where meaning is attached: table and column names are resolved against pg_class/pg_attribute and replaced with object identifiers (OIDs) and range-table entries; ambiguous syntactic nodes are disambiguated — “a FuncCall node in the parse tree … might be transformed to either a FuncExpr or Aggref node depending on whether the referenced name turns out to be an ordinary function or an aggregate function”; and “information about the actual data types of columns and expression results is added to the query tree.” This stage is also where most semantic errors surface: column "x" does not exist, operator does not exist: integer = text, aggregate functions are not allowed in WHERE. The output is a fully-typed, catalog-resolved query tree.

Stage 3 — Rewrite: applying the rule system

The query tree next passes through the rule system, which “modifies queries to take rules into consideration, and then hands back the modified query” (PostgreSQL, The PostgreSQL Rule System). The most important consumer is views: a PostgreSQL view is literally implemented as an ON SELECT rewrite rule, so SELECT * FROM my_view is rewritten by substituting the view’s underlying query tree in place of the view reference — “view inlining.” Row-level security policies and user-defined CREATE RULE rules are applied here too, and a single input query tree can fan out into several rewritten trees (e.g. a rule that also logs). The important conceptual point: rewriting is query-tree-in, query-tree-out — it is still working at the logical level, not yet choosing any access method.

Uncertain

Verify: the exact division of labor between the rewriter and the planner’s preprocessing for constant folding and subquery flattening. In PostgreSQL these two transformations happen in the planner’s preprocessing phase (eval_const_expressions, pull_up_subqueries in the prep stage), not in the rule-system rewriter — the rewriter proper handles views, rules, and RLS. Many textbooks and course slides lump “constant folding, subquery flattening, predicate pushdown” under a single “rewrite” stage, which is true conceptually (they are logical rewrites) but conflates PostgreSQL’s specific module boundaries. Reason: the brief and secondary sources group these together; PostgreSQL’s source organizes them differently. To resolve: read src/backend/optimizer/prep/ and the planner README. uncertain

Stage 4 — Plan / optimize: query tree to plan tree

“The task of the planner/optimizer is to create an optimal execution plan. A given SQL query (and hence, a query tree) can be actually executed in a wide variety of different ways, each of which will produce the same set of results” (PostgreSQL, Planner/Optimizer). This is the stage where cost matters. Before enumerating join orders the planner does its preprocessing (constant folding, subquery pull-up, join-tree flattening), then for each base relation it generates candidate access paths — always a sequential scan, plus any usable index scans and bitmap scans — and for each pair of relations it considers the three physical join methods (nested loop, merge join, hash join). It “works with data structures called paths, which are simply cut-down representations of plans containing only as much information as the planner needs to make its decisions”; the winning paths are then expanded into a full plan tree of executable nodes. Because the number of join orderings explodes, PostgreSQL does a near-exhaustive dynamic-programming search only up to geqo_threshold (default 12) relations and switches to a genetic heuristic beyond that — the mechanics of that search live in Cost-Based Query Optimization, and the estimates that drive the cost model live in Database Statistics and Cardinality Estimation. The scan-vs-index arm of this decision is The Index versus Sequential Scan Decision.

Stage 5 — Execute: running the plan tree

The plan tree is a tree of physical operators — Seq Scan, Index Scan, Hash, Hash Join, Sort, Aggregate, Limit. The executor “recursively steps through the plan tree and retrieves rows in the way represented by the plan” (PostgreSQL, Executor). PostgreSQL’s executor is a classic pull-based iterator (Volcano model): each node exposes a “give me the next tuple” call, and a parent repeatedly pulls from its children — the top node pulls from the join, which pulls from its two scan children, and so on down to the leaves that read pages through The Buffer Pool. The competing execution strategies (materialization, vectorized batches, JIT-compiled code) are the subject of Query Execution Models. Reads are guarded by the concurrency-control layer — under Multiversion Concurrency Control each scan sees the row versions visible to its snapshot.

EXPLAIN — reading the plan tree

EXPLAIN prints the plan tree the planner produced, without executing it; EXPLAIN ANALYZE executes it and annotates each node with actual timings and row counts (PostgreSQL, Using EXPLAIN). A worked example against a two-table join:

EXPLAIN ANALYZE
SELECT o.id, c.name
FROM   orders o JOIN customers c ON c.id = o.customer_id
WHERE  o.total > 1000;
Hash Join  (cost=30.50..118.75 rows=210 width=40)
           (actual time=0.412..1.983 rows=198 loops=1)
  Hash Cond: (o.customer_id = c.id)
  ->  Seq Scan on orders o  (cost=0.00..85.00 rows=210 width=12)
                            (actual time=0.011..1.203 rows=198 loops=1)
        Filter: (total > 1000)
        Rows Removed by Filter: 4802
  ->  Hash  (cost=18.00..18.00 rows=1000 width=36)
        ->  Seq Scan on customers c  (cost=0.00..18.00 rows=1000 width=36)
Planning Time: 0.256 ms
Execution Time: 2.104 ms

Line-by-line, this is the plan tree, printed depth-first with indentation showing parent/child:

  • Hash Join is the root physical operator. cost=30.50..118.75 is the planner’s estimate of startup cost .. total cost in its abstract cost units (page-fetch-equivalents, where seq_page_cost = 1.0 anchors the scale, per PostgreSQL cost docs); rows=210 is the estimated output cardinality; actual … rows=198 is what really happened.
  • Hash Cond names the join predicate this operator evaluates.
  • The two -> children are the join’s inputs. The build side (customers) is scanned and loaded into a Hash; the probe side (orders) is scanned with the total > 1000 filter applied.
  • Rows Removed by Filter: 4802 exposes selectivity reality: the scan read 5000 rows and discarded 4802 — useful for spotting a missing index.
  • The gap between estimated rows=210 and actual rows=198 is small here (healthy stats). A large gap is the single most common cause of a bad plan — see Database Statistics and Cardinality Estimation.

The chosen physical join (Hash Join vs Nested Loop vs Merge Join) is decided in Stage 4 from these estimates; the algorithms themselves are covered in Join Algorithms.

Failure Modes and Common Misunderstandings

  • “The database ran my SQL as written.” It did not. The plan can differ radically from the SQL’s surface structure — a subquery may be flattened into a join, a join order may be swapped, a view is expanded inline. The SQL specifies what, the plan tree decides how.
  • Parse success ≠ query validity. A syntactically perfect query referencing a nonexistent column parses fine (Stage 1) and only fails at analysis (Stage 2). This is why column does not exist is a semantic error, not a syntax error.
  • Plan caching hides the pipeline. Prepared statements and PL/pgSQL cache plans, so Stages 1–4 may run once and be reused. A cached “generic plan” built without knowledge of specific parameter values can be worse than a re-planned “custom plan” — PostgreSQL’s plan_cache_mode exists precisely to manage this. A plan that was great last week can degrade as data grows and stats drift, without the SQL changing at all.
  • EXPLAIN vs EXPLAIN ANALYZE. Plain EXPLAIN only estimates and does not run the query (safe, instant). EXPLAIN ANALYZE actually executes it — including any INSERT/UPDATE/DELETE side effects unless you wrap it in a rolled-back transaction. The estimated-vs-actual row divergence it reveals is the primary diagnostic for optimizer misestimates.

Alternatives and Variations Across Engines

Every relational engine has this pipeline, but the module boundaries and names differ. SQLite compiles the parse tree straight into bytecode for a virtual machine (the VDBE) rather than an operator tree, so its “executor” is a bytecode interpreter. MySQL/InnoDB historically fused parsing and optimization more tightly and gained a cost-based optimizer with a visible logical/physical split later than PostgreSQL. SQL Server and systems descended from the Cascades framework (see Cost-Based Query Optimization) blur the rewrite/optimize boundary entirely, expressing even “rewrites” like predicate pushdown as cost-driven transformation rules inside the optimizer rather than as a separate deterministic rewrite phase. Analytical engines such as DuckDB keep the same logical pipeline but replace the pull-based iterator executor with a vectorized push engine (Query Execution Models). The staging concept — syntax, then semantics, then logical rewrite, then physical optimization, then execution — is universal; only the code organization varies.

Production Notes

The practical payoff of understanding the pipeline is knowing where a problem lives. A query that is slow to plan (visible as a high Planning Time) is usually a many-table join hitting the combinatorial search in Stage 4 — the fix is geqo, join_collapse_limit, or a hint/materialization, not an index. A query that is slow to execute with a plan whose estimated rows are wildly off actual rows is a Stage 4 problem rooted in Stage-2/statistics inputs — the fix is ANALYZE, extended statistics, or raising default_statistics_target. A query that fails to use an index you expected is Stage 4 correctly costing a sequential scan cheaper (The Index versus Sequential Scan Decision). And a query whose plan is correct but cached against stale assumptions is a plan-cache problem. Reading an EXPLAIN (ANALYZE, BUFFERS) output top-down and comparing estimated to actual rows at each node localizes almost every “why is this query slow?” to a single stage of this pipeline.

See Also

Graph View

Backlinks