Skip to content
Tutorials Center
My learning

Topics

Lesson 58 of 79 ยท Query Processing and Optimization

The Query Processing Pipeline

Follow a SQL query through parsing, algebra trees, logical and physical plans, the optimizer and the executor, with the Volcano iterator model and live EXPLAIN output.

SQL tells the database what you want, never how to get it. Between the moment you press Run and the moment the first row appears, the DBMS turns your text into an internal tree, picks one of many equivalent ways to evaluate it, and then runs that choice. This is the query processing pipeline, and every optimization topic in the rest of this chapter is a zoom into one of its boxes.

Understanding the pipeline explains many things that look odd from the outside: why a typo is reported before any data is read, why two equivalent queries can have very different speeds, why LIMIT 1 can be nearly free and why EXPLAIN exists at all. This lesson walks through the stages, introduces the iterator ("Volcano") execution model with a live Python version, and uses SQLite's EXPLAIN QUERY PLAN and EXPLAIN to look at real plans. For a practical guide to reading plans in several engines, see Reading Query Plans.

From text to rows

Parse Check the syntax and names.
Algebra tree Express the query as operators.
Optimize Pick the cheapest plan.
Execute Run it and stream the rows out.

Only the last step touches the data.

1 / 2

The stages

flowchart LR
    A["SQL text"] --> B["Parser<br/>and validator"]
    B --> C["Logical plan<br/>(algebra tree)"]
    C --> D["Optimizer<br/>(uses catalog statistics)"]
    D --> E["Physical plan"]
    E --> F["Executor"]
    F --> G["Result rows"]

The query is rewritten twice, once into a logical tree and once into a physical plan, before any row is read.

  1. Parsing. The lexer and parser check the text against the SQL grammar and build a parse tree. A syntax error stops here.
  2. Validation (binding). The system looks up every table, column and function in the catalog, checks the types, expands *, resolves views to their definitions and checks your privileges. A misspelled column is reported at this stage, before any data is touched.
  3. Logical plan. The query is translated into a tree of relational algebra operators: scans at the leaves, then selections (ฯƒ), projections (ฯ€) and joins (โ‹ˆ) towards the root. The tree says what to compute, not how.
  4. Optimization. The optimizer rewrites the tree into cheaper equivalent forms (heuristic rules), enumerates alternatives for access paths, join order and join algorithms, estimates each plan's cost using statistics from the catalog (cost-based optimization), and keeps the cheapest.
  5. Physical plan. The chosen tree, whose nodes are concrete algorithms: index scan on idx_grade, hash join, sort, stream aggregate.
  6. Execution. The executor runs the physical plan and returns rows to the client, usually one at a time.

Many systems also cache the result of steps 1 to 5 as a prepared statement or plan cache, so repeated queries skip them.

Logical versus physical plans

Take this query on a school database:

SQL
SELECT s.first_name, c.title, e.grade
FROM enrollments e
JOIN students s ON s.id = e.student_id
JOIN courses c ON c.id = e.course_id
WHERE e.grade >= 90;

The logical plan can be written as an algebra expression:

TEXT
ฯ€ first_name, title, grade
  ฯƒ grade >= 90
    ( (enrollments โ‹ˆ students) โ‹ˆ courses )

It says nothing about indexes, loops or order of evaluation. The physical plan commits to them: for example "scan enrollments; for each row filtered by grade >= 90, look up the student by primary key, then the course by primary key". The same logical tree can lead to many physical plans: the join could start from students instead, use a hash join, or read enrollments through an index on grade. The optimizer's job is to choose among them.

The first TryIt asks SQLite for the physical plan of a similar query on the school sample database, adds an index and asks again. The plan changes, the answer does not. (The notused column is internal; read detail.)

SQL The plan before and after an index ยท database: school

Press Run (or Ctrl + Enter) to see the result here.

The first plan reads SCAN e, then SEARCH c USING INTEGER PRIMARY KEY (rowid=?) for each matching enrollment, and finally USE TEMP B-TREE FOR GROUP BY. The second starts with SEARCH e USING INDEX idx_enr_grade (grade>?). In both, the course table is accessed through its primary key: that is a nested-loop join with enrollments as the outer table. SQLite's optimizer also decided that grouping needs a temporary tree, which you will see again as a physical operator when we cover external sorting and aggregation.

The index adds a new access path (a range search instead of a full scan); the join algorithm stays the same. The exact range bounds (>?) are an implementation detail: SQLite searches above 89 and filters.

The iterator (Volcano) model

How does the executor run a plan? Most systems use the iterator model, also called the Volcano model after the research prototype that popularised it. Every operator implements the same tiny interface, usually open(), next() and close(). A call to next() returns the next output row, or "end". An operator gets its input by calling next() on its children:

  • A scan reads the next row from the table.
  • A selection keeps calling next() on its child until a row passes the predicate.
  • A projection takes one row from its child and returns only the requested columns.
  • A limit counts rows and stops after n, without asking its child for more.

The root keeps being asked for rows by the client, and the demand flows down the tree. No operator needs to know how its children work, so any plan can be built by plugging operators together. Rows flow up one at a time (pipelining), so a LIMIT can stop the whole tree early and intermediate results often never need to be materialized. Operators that must see all their input before they can produce a row, such as sort or hash build, are called blocking.

The TryIt implements Scan, Select, Project and Limit with exactly this interface, and counts how many table rows were read.

Python Volcano iterators with a row counter

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With LIMIT 2 the scan only reads three rows, because after the second matching student (Cleo, at position 3) the Limit stops asking. Without it, all six rows are read. Production engines refine the model with vectorized execution (next() returns a batch of about 1,000 rows) or compile the plan to machine code, to cut the per-row call overhead; the idea of operators passing rows between them stays the same.

Peeking at the executor in SQLite

SQLite does not interpret an operator tree. Its code generator compiles the plan into a small program of bytecode for its virtual machine. The statement EXPLAIN (without QUERY PLAN) lists that program. You can see the same loop as in the Python code: open the table, rewind to the first row, test the condition, emit a row, advance, repeat.

SQL The bytecode behind a simple query ยท database: school

Press Run (or Ctrl + Enter) to see the result here.

The listing contains the opcodes Init, Transaction (start a read transaction), OpenRead (open a cursor on students), Rewind (go to the first row), Column (read a column), Ne (jump if the homeroom does not equal 'A1'), ResultRow (hand a row to the client), Next (advance the cursor and loop) and Halt. Read it as Scan + Select + Project fused into one loop, which is how a compiled plan avoids function-call overhead for every row.

What runs live here: SQLite plans and bytecode, and a Python version of the iterator model. The optimizers of PostgreSQL, MySQL, Oracle and SQL Server print their plans in different formats (EXPLAIN trees with costs and row estimates); those are read-only topics shown in Reading Query Plans.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A query refers to a column that does not exist. At which stage is the error reported?

    Name resolution against the catalog happens during validation. The system never starts execution of a query it cannot bind.
  2. 2. What is the difference between a logical and a physical plan?

    The optimizer turns a logical tree into a physical one by choosing, for example, an index scan and a hash join.
  3. 3. In the Volcano model, what does a call to next() on the root operator do?

    Each operator produces one row per call by calling next() on its children, so rows are pipelined through the tree.
  4. 4. Why can LIMIT 2 make a query much cheaper in an iterator-based executor?

    Because rows are pulled on demand, nothing below the Limit has to produce more rows than are requested (unless a blocking operator such as a sort sits in between).
  5. 5. Which of these is a blocking operator?

    A sort cannot emit its first row until it has seen all of its input. Selection, projection and limit work row by row.

Summary

  • A query passes through parsing, validation, a logical plan (relational algebra tree), optimization, a physical plan and execution.
  • The logical plan says what to compute; the physical plan names the algorithms and access paths. The optimizer picks the cheapest physical plan using catalog statistics.
  • Most executors use the iterator (Volcano) model: every operator offers next(), rows are pipelined, and blocking operators like sort hold back until all input has arrived.
  • EXPLAIN QUERY PLAN shows SQLite's physical plan; EXPLAIN shows the bytecode that implements it.
  • Adding an index changes the access path but not the result.

Next: Join Algorithms.