Query Processing & Execution Internals

When you submit a SQL query, the database does not simply "run" it. Instead, a sophisticated pipeline of components parses, validates, rewrites, optimizes, and then executes your query. The difference between a naive execution and an optimized one can be the difference between milliseconds and hours on the same data.

Query processing matters across the full spectrum of database applications: in OLTP systems, efficient single-row lookups with index scans keep transaction latency low; in OLAP systems, vectorized hash joins and aggregate operators enable analytical queries over billions of rows in seconds. For database administrators, engineers, and architects alike, a working knowledge of these internals is indispensable for performance tuning.

Three Main Phases

Precise terminology is essential before diving into the mechanics of query processing.

A SQL query passes through nine distinct stages before results are returned. Each stage transforms the query representation, progressively moving from high-level intent to low-level, executable operations.

3.1 Lexical Analysis & Parsing

The lexer reads the SQL string character by character and groups characters into tokens: keywords (SELECT, FROM, WHERE), identifiers (table and column names), operators (=, >), and literals (numbers, strings). If an unrecognized character sequence is encountered, a lexical error is reported immediately.

The parser takes the token stream and checks it against the formal SQL grammar. If the token sequence is syntactically valid, the parser constructs a parse tree (syntax tree), a hierarchical structure mirroring the grammar rules. For example, a SELECT statement produces child nodes for the select list, from clause, and where clause. A syntax error terminates processing here.

3.2 Semantic Analysis

Even a syntactically valid parse tree can be meaningless. The semantic analyzer performs deeper validation against the database schema:

• Name resolution: All referenced tables, columns, and functions must exist and be in scope.
• Type checking: Operations must be applied to compatible types (e.g., comparing a string to an integer is an error).
• Authorization: The user must hold sufficient privileges (SELECT, UPDATE, etc.) on the referenced objects.
• View expansion: References to views are replaced with their underlying definitions.

3.3 Intermediate Representation (Logical Plan)

After successful semantic analysis, the parse tree is translated into a logical query plan— an operator tree expressed in relational algebra. Relational algebra operators include:

This logical plan captures what to compute without specifying how. It is the input to the query optimizer.

Query optimization is the most challenging phase of query processing. The optimizer's goal is to find the physical execution plan with the lowest estimated resource cost among potentially billions of candidates.

4.1 Logical Rewrites

Before selecting physical operators, the optimizer applies algebraic equivalence rules to rewrite the logical plan into an equivalent but cheaper form:

4.2 Cost-Based Optimization

Modern optimizers are cost-based: they assign an estimated cost to each candidate physical plan and select the lowest-cost plan. The cost model accounts for:

The System R optimizer (IBM, 1979) pioneered cost-based optimization with dynamic programming over left-deep join trees. It remains the conceptual template for most modern optimizers. The optimizer enumerates sub-expressions bottom-up, storing the cheapest plan for each sub-expression, then combines them.

4.3 Cardinality Estimation & Statistics

Cardinality estimation — predicting how many rows each operator will produce — is critical because operator costs are proportional to input/output sizes. The optimizer uses:

• N_R: number of tuples in relation R
• V(A, R): number of distinct values of attribute A in R
• Histograms: frequency distributions of attribute values
• Selectivity formulas: for σ_A=v(R), estimated rows = N_R / V(A, R); for σ_A>v(R), estimate uses histogram buckets
• Join cardinality: for R ⋈ S on A=B, estimated = N_R × N_S / max(V(A, R), V(B, S))

4.4 Rule-Based vs. Cost-Based Optimization

Joins are typically the most expensive operations in relational queries. Choosing the right join algorithm for each join in a query is one of the optimizer's most consequential decisions. Let B_R and B_S denote the number of disk blocks in relations R and S, |R| the number of tuples, and M available memory blocks.

5.1 Nested Loop Join (NLJ)

The simplest join: for every tuple in R, scan all of S.

I/O Cost: B_R + |R| × B_S (naive); improved to B_R + ⌈B_R / (M−1)⌉ × B_S with Block NLJ (reads M−1 blocks of R at a time). Use when: outer relation is very small, or no suitable index exists.

5.2 Index Nested Loop Join (INLJ)

A variant of NLJ where an index exists on the inner relation's join attribute. Instead of scanning all of S for each tuple in R, the optimizer uses the index to fetch only matching tuples. I/O Cost: B_R + |R| × C_index, where C_index is the index lookup cost (typically 2–4 I/Os for a non-clustered B-tree). Use when: the outer relation is small and the join is highly selective.

5.3 Sort-Merge Join (SMJ)

Sort both R and S on their join attributes, then merge the two sorted streams in a single pass. I/O Cost: Sort(R) + Sort(S) + B_R + B_S, where Sort(X) ≈ 2·B_X·(1 + ⌈log_(M−1)(B_X/M)⌉). If both relations are already sorted, cost collapses to B_R + B_S. Use when: inputs are pre-sorted, or the query requires sorted output on the join key anyway.

5.4 Hash Join (HJ)

Build an in-memory hash table on the smaller relation (R), then probe it with every tuple from S. I/O Cost: B_R + B_S if R fits in memory. If R does not fit, a partitioning phase writes both relations to disk partitioned by hash key: total cost ≈ 3·(B_R + B_S). Use when: equijoin, large unsorted relations, and the build side fits in memory. Generally the fastest join algorithm in practice.

5.5 Join Algorithm Comparison

SELECT E.name, D.dept_name FROM Employees E
JOIN Departments D ON E.dept_id = D.dept_id WHERE E.salary > 50000

ORDER BY, GROUP BY, DISTINCT, and set operations (UNION, INTERSECT, EXCEPT) all require sorting or hashing. When data exceeds available memory, the DBMS must use disk-based algorithms.

6.1 External Merge-Sort

When data is too large to sort in memory (B_R > M blocks), external merge-sort proceeds in two phases:

6.2 Sort-Based vs. Hash-Based Aggregation

Once the physical query plan is selected, the execution engine takes over. There are three dominant execution paradigms, each with different performance characteristics.

7.1 Iterator / Volcano Model

The Volcano model (Graefe & McKenna, 1993) is the classical execution paradigm. Every physical operator implements three methods:

7.2 Pipelining vs. Materialization

7.3 Vectorized Execution

Traditional Volcano processes one tuple at a time. Vectorized execution processes data in batches (vectors) of 1,000–10,000 tuples. Each call to next() returns an entire vector instead of a single tuple:

7.4 JIT Compilation

Some advanced systems (Apache Impala with LLVM, HyPer, CockroachDB) use Just-in-Time (JIT) compilation to translate the physical query plan into native machine code at runtime. Unlike interpreted execution, JIT-compiled code contains no virtual dispatch overhead, enables loop unrolling, and generates specialized code for specific data types and predicates. The compilation overhead is amortized over long-running or repeated queries.

EXPLAIN ANALYZE is the primary tool for observing how a DBMS actually executes a query. It shows the physical plan, estimated vs. actual row counts, and buffer/I/O statistics.

EXPLAIN ANALYZE
SELECT emp_name, salary
FROM Employees
WHERE salary > 50000.00;

-- QUERY PLAN -----------------------------------------------
-- Project (emp_name, salary)
--   -> Index Scan using idx_employees_salary on Employees
--         Filter: (salary > 50000.00)
--         Rows Removed by Filter: 150000
--         Actual Rows: 100000
--         Buffers: shared hit=10000, read=5000

EXPLAIN ANALYZE
SELECT D.dept_name, SUM(E.salary) AS total_salary
FROM Employees AS E
JOIN Departments AS D ON E.dept_id = D.dept_id
WHERE D.location = 'New York'
GROUP BY D.dept_name
ORDER BY total_salary DESC;

-- QUERY PLAN -----------------------------------------------
-- Sort (total_salary DESC)
--   -> HashAggregate (SUM(E.salary), Group Key: D.dept_name)
--         -> Hash Join (E.dept_id = D.dept_id)
--               -> Seq Scan on Employees E     [probe side]
--               -> Hash (D.dept_id)            [build side]
--                     -> Index Scan on Departments D
--                           Filter: (location = 'New York')
--                           Rows Removed: 900  Actual Rows: 100

EXPLAIN ANALYZE
SELECT D.dept_name
FROM Departments D
WHERE EXISTS (
    SELECT 1 FROM Employees E
    WHERE E.dept_id = D.dept_id AND E.salary > 70000.00
);

-- QUERY PLAN -----------------------------------------------
-- HashAggregate (DISTINCT D.dept_name)  -- EXISTS → join + distinct
--   -> Hash Join (D.dept_id = E.dept_id)
--         -> Seq Scan on Departments D
--         -> Hash (E.dept_id)
--               -> Index Scan using idx_salary on Employees E
--                     Filter: (salary > 70000.00)
--                     Rows Removed: 200000  Actual Rows: 50000