Query Processing Overview

Query processing is the sequence of activities involved in extracting data from a database: parsing and translating a query into an internal form, choosing an efficient execution strategy, and evaluating that strategy against the stored data. It is distinct from query optimization, which is specifically the sub-problem of choosing which plan to execute among the many algebraically equivalent options; query processing is the umbrella term for the whole pipeline that optimization lives inside. The central design idea is separation of concerns via an intermediate representation. SQL text is convenient for humans but ambiguous and verbose as a computational object — the same result can be phrased in countless syntactic ways. The engine instead translates SQL into relational algebra, a small, closed set of operators (selection σ, projection π, join ⋈, union ∪, set difference −, rename ρ, and grouping/aggregation extensions) with precise, composable semantics. Because relational algebra is a formal language with algebraic identities (e.g., selections commute, joins are associative and commutative up to renaming), the engine can rewrite one algebra expression into an equivalent but cheaper one — this rewriting is exactly what Query Optimization Fundamentals studies. Query processing supplies the representation that makes such rewriting possible in the first place. A second key idea is the distinction between a logical query plan (a relational algebra expression — what to compute) and a physical/evaluation query plan (an algebra tree annotated with specific algorithms and access paths — how to compute it). The same logical join can be realized physically as a nested-loop join, a sort-merge join, or a hash join; the same logical selection can be realized as a full table scan or an index lookup via Indexing Overview for Query Access. Query processing is precisely the machinery that produces, compares, and executes these physical plans.

The pipeline below is the standard architecture used by essentially every relational engine, from teaching systems to production servers.

Stage 1 — Lexing and parsing. The SQL text is tokenized (keywords, identifiers, literals, operators) and parsed against the SQL grammar into a parse tree (or abstract syntax tree). A recursive-descent or table-driven parser checks syntax: are the keywords in the right places, are parentheses balanced, is the `FROM` clause well-formed. Purely syntactic errors (a missing comma, an unmatched `SELECT`) are caught here.

Stage 2 — Semantic validation and translation to relational algebra. The parse tree is walked against the catalog (schema metadata): do the referenced relations and attributes exist, are the types compatible, is a `JOIN ... ON` predicate well-typed, is a view expandable in place. Once validated, the tree is translated into an initial relational algebra expression — this translation is mechanical and follows the syntactic structure of the query almost directly (a `WHERE` clause becomes a σ, a `SELECT` list becomes a π, a `JOIN` becomes a ⋈, `GROUP BY`/aggregate functions become a grouping operator, `ORDER BY` becomes a sort operator, and a nested subquery may become a further algebra sub-tree or be rewritten away entirely). Views referenced in the `FROM` clause are expanded into their defining queries at this point (view expansion), so downstream stages never need to know a view was involved — this is the connective tissue back to Views in SQL.

Stage 3 — Logical and physical plan generation. The initial algebra expression, usually built in a "canonical" but naive shape (e.g., selections and projections deferred to the very end, joins in `FROM`-clause order), is transformed using algebraic equivalence rules into alternative logical expressions. Each logical expression is then annotated with concrete algorithms and access paths to produce candidate physical plans. For example, a logical σ over relation R can become "scan R sequentially, filter in memory" or "use a B⁺-tree index on the filtered attribute." A logical join can become nested-loop, block nested-loop, sort-merge, or hash join. This enumeration-and-annotation process is where Query Optimization Fundamentals and Cost Estimation for Query Plans do their work — this article only describes that plans are enumerated, annotated, and one is chosen; the search strategy and cost model are separate topics.

Stage 4 — Plan selection. Among the candidate physical plans, the optimizer picks the one with the lowest estimated cost (I/O, CPU, sometimes network in distributed settings), using statistics maintained about relation sizes, value distributions, and index selectivity.

Stage 5 — Execution. The chosen physical plan is a tree of physical operators. The iterator model (also called the Volcano or pull model) executes it: every operator implements three methods — ``` open() — initialize operator state, recursively open() children next() — produce (and return) the next output tuple, pulling from children's next() as needed; return end-of-stream when exhausted close() — release resources, recursively close() children ``` The root operator's `next()` is called repeatedly by the client (or by the code producing the final result set) until end-of-stream, and each call may cascade into calls on children, forming a demand-driven pipeline. This lets operators be composed uniformly regardless of their internal algorithm, and lets tuples flow through the whole tree without materializing every intermediate result on disk (pipelining), except where an operator is blocking (like sort or hash-build) and must consume all input before producing any output. ``` // Generic evaluation-plan execution driver function EXECUTE_PLAN(rootOperator): rootOperator.open() results = [] tuple = rootOperator.next() while tuple != END_OF_STREAM: results.append(tuple) tuple = rootOperator.next() rootOperator.close() return results // Example physical operator: file scan class FileScan implements Operator: function open(): this.cursor = storage.openScan(this.relationName) function next(): record = this.cursor.getNextRecord() if record == null: return END_OF_STREAM return record function close(): storage.closeScan(this.cursor) // Example physical operator: selection (filter), pipelined class Select implements Operator: // predicate: a function tuple -> boolean function open(): this.child.open() function next(): loop: t = this.child.next() if t == END_OF_STREAM: return END_OF_STREAM if predicate(t): return t // else loop and pull the next child tuple function close(): this.child.close() // Example physical operator: block nested-loop join (blocking on the outer's current block) class BlockNestedLoopJoin implements Operator: function open(): this.outer.open() this.inner.open() this.outerBlock = [] this.innerBuffered = [] // reloaded from scratch per outer block this.fillOuterBlock() function fillOuterBlock(): this.outerBlock = readUpTo(this.outer, BLOCK_SIZE_TUPLES) this.inner.close(); this.inner.open() // rescan inner this.matchQueue = [] function next(): loop: while this.matchQueue is empty: if this.outerBlock is empty: return END_OF_STREAM innerTuple = this.inner.next() if innerTuple == END_OF_STREAM: this.fillOuterBlock() if this.outerBlock is empty: return END_OF_STREAM continue for outerTuple in this.outerBlock: if joinCondition(outerTuple, innerTuple): this.matchQueue.push(combine(outerTuple, innerTuple)) return this.matchQueue.pop() function close(): this.outer.close() this.inner.close() ``` The `Select` operator above is a pipelined (non-blocking) operator: it produces output as soon as it sees a matching tuple. The join operator is partially blocking: it must buffer an entire block of the outer relation before it can start matching, but it does not need the whole relation. A full hash join build phase or an external merge sort is fully blocking: no output tuple can be produced until all input has been consumed. Recognizing which operators block matters directly for pipelining and for Cost Estimation for Query Plans, since blocking operators force materialization and add distinct I/O cost terms.

Parsing. Standard SQL grammars are context-free (with some context-sensitive checks like type resolution deferred to a separate semantic pass). A well-designed grammar can be parsed in O(n) time and space for a query of length n using a deterministic (LL/LALR) parser, since SQL's grammar is engineered to avoid the super-linear behavior of ambiguous grammars. Semantic validation against the catalog (resolving each identifier to a relation/attribute) costs O(n · log m) or O(n) amortized, where m is the number of catalog objects, assuming a hashed or tree-indexed catalog lookup — this is negligible next to actual data processing cost.

Translation to algebra. This is a single structural recursion over the parse tree, so it is O(n) in the size of the parse tree. Correctness here means semantic equivalence: the resulting algebra expression must denote exactly the same set (or bag, for SQL's multiset semantics) of result tuples as the original SQL query for every database instance. This is established by defining the translation compositionally — each SQL clause maps to an algebra operator whose formal semantics (given in terms of relations as sets/bags of tuples) is proven to match the SQL standard's clause semantics. For example, `SELECT DISTINCT A FROM R WHERE P` translates to π_A(σ_P(R)) with duplicate elimination, and one checks that both sides produce, for every instance of R, the identical distinct-tuple set.

Plan generation and rewriting. The number of syntactically distinct join orders for k relations is (2k−2)!/(k−1)! for left-deep trees alone (accounting for choice of join method separately), and grows even faster if bushy trees are allowed — this combinatorial explosion is precisely why Query Optimization Fundamentals needs dynamic programming or heuristics rather than brute force, and why this stage is described only structurally here. Correctness of plan generation means every candidate plan is algebraically equivalent to the original expression: rewriting rules (selection pushdown, join commutativity/associativity, projection pushdown) are each proven correct as algebra identities independent of the actual data, so any composition of valid rules preserves the final result.

Execution (iterator model). For an operator tree with k operators where operator i does O(f_i) work per `next()` call in the worst case, and the tree produces r output tuples total, the total work is bounded by the sum, over all operators, of (number of times `next()` is called on that operator) × (cost per call). For purely pipelined trees (scans, selections, projections, pipelined nested-loop-style joins) this yields time linear in the total number of tuples read across all base relations, i.e. O(N) where N is total input size, plus O(r) for output — but for blocking operators such as sort (O(N log N) time, O(N) extra I/O in the external case) or hash-join build phases (O(N) average time, quadratic worst case under adversarial hash collisions), the tree's overall complexity is the sum of each operator's own algorithmic cost, not simply linear in N. This is exactly why algorithm choice at the physical-plan stage matters so much, and why Cost Estimation for Query Plans must model I/O (page reads/writes) separately from CPU tuple-processing cost — disk I/O typically dominates for data sets larger than main memory.

Correctness invariant for the iterator protocol. Every operator must satisfy: (1) `open()` must be called exactly once before any `next()` call and establishes the operator's internal state as "ready, zero tuples emitted yet"; (2) each `next()` call either returns exactly one new output tuple consistent with the operator's semantics given its children's outputs so far, or returns end-of-stream, and once end-of-stream is returned the operator must continue to return end-of-stream on subsequent calls (no false restarts); (3) `close()` releases all resources and may not be followed by further `next()` calls. If every operator in a tree satisfies this contract, a simple induction over tree height shows the whole tree satisfies it too: the base case is a leaf scan operator (trivially satisfies the contract by construction over the stored file), and the inductive step holds because each interior operator's `next()` is defined purely in terms of calling its children's `next()` according to its own algebra semantics (e.g., `Select.next()` returns the first child tuple satisfying the predicate, which is exactly the set semantics of σ). This is why the iterator model composes safely: any tree built from contract-respecting operators is itself contract-respecting and computes the algebra expression it represents.

Tradeoffs. Pipelining minimizes memory and lets results start streaming to the client immediately, but it forces algorithm choices (e.g., you cannot use a plain in-memory hash join if the build side does not fit in memory) and complicates operators like sort that inherently need to see all their input. Materializing intermediate results (writing them to temporary storage) simplifies operator implementation and permits re-scans, but costs extra I/O. Real engines mix both: blocking operators materialize just enough (a hash table, a run of sorted tuples) while everything else stays pipelined.

Consider the query, over a schema `Orders(order_id, customer_id, amount, order_date)` and `Customers(customer_id, name, city)`: ```sql SELECT c.name, o.amount FROM Orders o JOIN Customers c ON o.customer_id = c.customer_id WHERE o.amount > 500 ORDER BY o.amount DESC; ```

Step 1 — Parse. The parser confirms the grammar (`SELECT-FROM-WHERE-ORDER BY` shape) is well-formed, that `o` and `c` are valid table aliases, and that `o.customer_id`, `c.customer_id`, `o.amount`, `c.name` all resolve to real columns in the catalog with compatible types for `=` and `>`.

Step 2 — Translate to relational algebra. The canonical (unoptimized) translation nests operators exactly following clause order: ``` τ_{amount DESC} ( π_{name, amount} ( σ_{amount > 500} ( Orders ⋈_{customer_id = customer_id} Customers ) ) ) ``` where τ denotes sort. Note this "obvious" translation joins the full Orders and Customers relations before filtering — correct, but potentially wasteful if Orders is large and the filter is selective.

Step 3 — Generate candidate plans. Using the selection-pushdown identity σ_P(R ⋈ S) ≡ σ_P(R) ⋈ S (valid because P only references attributes of R), the optimizer can produce an equivalent, cheaper logical plan: ``` τ_{amount DESC} ( π_{name, amount} ( σ_{amount > 500}(Orders) ⋈_{customer_id = customer_id} Customers ) ) ``` Two physical plans might then be considered for the σ over Orders — a full scan with an in-memory filter, or an index scan using a B⁺-tree on `amount` (see Indexing Overview for Query Access) — and two physical algorithms for the join, say hash join versus sort-merge join. Suppose the catalog statistics say Orders has 1,000,000 rows with roughly 8% satisfying `amount > 500`, and Customers has 10,000 rows (small enough to build an in-memory hash table).

A cost-based optimizer (mechanics covered in Cost Estimation for Query Plans) estimates I/O and CPU cost for each and picks the cheapest — here likely Plan B, since the selective filter combined with an index avoids touching 92% of Orders pages.

Step 4 — Execute. Suppose Plan B is chosen. The operator tree is: ``` Sort(amount DESC) └─ Project(name, amount) └─ HashJoin(Orders.customer_id = Customers.customer_id) ├─ IndexScan(Orders, amount > 500) └─ FileScan(Customers) ``` Execution trace (abridged, showing the hash join's two phases): 1. `HashJoin.open()` calls `FileScan(Customers).open()` and builds an in-memory hash table keyed on `customer_id` over all 10,000 Customers rows — this is the build phase, fully blocking. 2. `HashJoin.open()` calls `IndexScan(Orders, amount > 500).open()`, positioning a cursor at the first index entry satisfying the predicate. 3. The `Sort` operator, being blocking, must pull every tuple from `Project` before it can emit anything: it repeatedly calls `Project.next()`, which calls `HashJoin.next()`, which pulls one Orders tuple via `IndexScan.next()` and probes the Customers hash table for a match — the probe phase. 4. Each matched (Orders, Customers) pair flows up through `Project` (dropping unneeded columns down to `name, amount`) and is buffered by `Sort`. 5. Once `IndexScan.next()` signals end-of-stream (no more index entries satisfy the range predicate), `Sort` has all ~80,000 filtered/joined tuples buffered, sorts them by `amount` descending (external sort if they do not fit in memory — see the sort operator's own O(N log N) analysis above), and only then starts returning tuples one at a time via its own `next()`. The final answer streams out of the root `Sort.next()` calls in descending `amount` order, and by the compositional correctness argument above, this output is guaranteed to equal exactly π_{name,amount} applied to the σ-filtered ⋈ of Orders and Customers, sorted — i.e., exactly the semantics of the original SQL query.

Every relational database — PostgreSQL, MySQL, Oracle, SQL Server, SQLite — implements exactly this pipeline internally: a parser/validator, a translator to an internal algebra or plan-tree IR, a planner that enumerates and costs alternatives, and an executor built on iterator-style physical operators (sometimes replaced or augmented by vectorized/columnar "batch" execution for analytics, but the logical stages remain the same). Distributed SQL engines (Spark SQL, Presto/Trino, Google BigQuery, Snowflake) extend this same pipeline with an extra stage that also decides data placement and shuffling across machines, but still bottom out in the same parse → algebra → physical-plan → execute skeleton. Application-facing tools such as ORMs and query builders generate SQL that ultimately funnels through this exact pipeline, and understanding it is the prerequisite for reading `EXPLAIN`/`EXPLAIN ANALYZE` output, tuning slow queries, designing indexes intelligently using Indexing Overview for Query Access, and reasoning about when a view from Views in SQL will be expanded versus materialized. The topics that follow — Selection and Projection Evaluation, Cost Estimation for Query Plans, and Query Optimization Fundamentals — each drill into one stage of exactly this pipeline in depth.

Ask the tutor: How does the query optimizer decide which of several equivalent physical plans has the lowest cost?