Query Planner and Volcano Executor

Why this stage exists

SELECT works. It checks the statement, walks the table with a cursor, tests each row against the WHERE clause, and prints what matches. All of that probably lives in one function, and it will not stay small. index-scan wants a second way to read rows. The Querying part adds sorting, limits, grouping, and expressions. Each of them, added to that one function, makes every other harder to change.

Every relational database solves this the same way. First decide what to do, as a tree of small operators, each with one job. Then run the tree. This stage makes that split. It adds no feature: every result stays exactly as it was, and the tests of the earlier stages keep passing. What it adds is a way to see the tree, explain.

What changes: a statement becomes a plan

select name from users where name = 'bob' becomes two operators. A SeqScan reads every row of the table, in id order, and knows nothing about the WHERE clause. A Filter sits above it, holds the condition name = 'bob', and lets only the rows that satisfy it through. The select list is not an operator here: the executor prints the columns it asks for from each row the top node hands it.

This is the Volcano model, named after the research system that described it. Every operator has the same three operations: open, next, close. Asking the top node for its next row makes it ask its child, and so on down to the node that reads the table:

Rows travel up one at a time. The Filter never holds the table, and neither does the executor: each row is printed before the next is read. That is what lets a plan answer a query over a table far bigger than memory, and what lets a node above stop early, as a LIMIT will in a later part.

The planner builds the tree before any row is read, so everything that can be wrong with the statement is found first. A statement with an unknown column, or a value of the wrong type, has no plan: its error is the only line, exactly as in the previous stages.

What about WHERE id = 2?

In this stage, nothing special. id is the key the tree is sorted by, so a search could go straight to row 2 and read one row. The planner here does not: where id = 2 is a Filter over a SeqScan, exactly like where name = 'bob', and reads every row to keep one.

That is deliberate. One scan and one Filter are all the machinery this stage needs, and the tree of operators is the idea it teaches. index-scan adds a second scan, one that uses the key, and teaches the planner when to choose it. It replaces the plans of where id = ..., and it says which cases of this stage it retires.

explain

explain <statement> builds the plan, prints it, and stops. It reads no row and changes nothing: an explained INSERT inserts nothing, and an explained INSERT of an id that already exists still prints its plan, because only running it would find the duplicate.

The first line is the statement as you typed it after explain. Keywords keep their case, and spaces inside stay as they were. Only the spaces around it and the final ; go. Then comes one line per node, top first, each level four spaces deeper than the one above:

>explain select name from users where name = 'bob';
[PLAN] select name from users where name = 'bob'
[PLAN]   └── Filter (name = 'bob')
[PLAN]       └── SeqScan (table=users)

The node that reads the table is always the deepest line. The Filter shows its condition the way ast shows a WHERE: the column, the operator, and the value, strings in single quotes and numbers bare.

Output contract for this stage

These are the exact lines the tests check. The full definition is on the output contract page, section 12.

<statement> is the statement after explain, without the spaces around it and its final ;. The connector is └──, the box-drawing characters U+2514 and U+2500 twice, followed by a space.

What you should see when done

$droid --db users.db
Welcome to droid!
>insert into users (id, name, email) values (1, 'alice', 'alice@example.com');
Insert statement executed successfully
>insert into users (id, name, email) values (2, 'bob', 'bob@example.com');
Insert statement executed successfully
>explain select * from users;
[PLAN] select * from users
[PLAN]   └── SeqScan (table=users)
>explain select name from users where name = 'bob';
[PLAN] select name from users where name = 'bob'
[PLAN]   └── Filter (name = 'bob')
[PLAN]       └── SeqScan (table=users)
>select name from users where name = 'bob';
name
bob
(1 rows)
>explain select * from users where id = 2;
[PLAN] select * from users where id = 2
[PLAN]   └── Filter (id = 2)
[PLAN]       └── SeqScan (table=users)
>explain insert into users (id, name, email) values (3, 'cy', 'cy@example.com');
[PLAN] insert into users (id, name, email) values (3, 'cy', 'cy@example.com')
[PLAN]   └── Insert (table=users)
>select id from users;
id
1
2
(2 rows)
>explain select * from users where email = 7;
[ERROR:00403] Column email expects a string
>explain
[ERROR:00901] explain needs a statement
>.exit
exiting.. good bye!

The explained INSERT of row 3 added nothing: the SELECT after it still finds rows 1 and 2.

Common bugs in this stage

• Results change. The refactor drops the last row, repeats one, or loses the order. Run the suites of the earlier stages: they must all still pass.
• The Filter returns after one try. Asked for its next row, it asks its child once and returns nothing if that row does not match, so the scan stops at the first row that fails. A Filter keeps asking until a row matches or its child has none left.
• The scan starts over. A SeqScan that does not keep its cursor between calls returns the first row forever. The cursor is the node's state, kept from open to close.
• explain runs the statement. The plan is printed and the INSERT happens anyway. explain builds the plan and stops.
• explain prints the plan of a broken statement. Check first: a statement with an error has no plan, and the error is the only line.
• The statement is reprinted from the AST. SELECT * FROM users typed in capitals comes back in small letters, or the spaces change. Print the text as typed.
• The wrong connector or indent. └── is three characters, and each level adds exactly four spaces. |--, tabs, or two spaces per level fail the tests.
• The Filter in the scan. Testing the condition inside the SeqScan works today, and leaves index-scan nowhere to put a Filter above a different scan. Keep the jobs apart.

Language notes

The page above is the same for every language. These are the only language-specific hints.

• C: a node can be a struct holding three function pointers, open, next and close, plus a pointer to its own state and to its child. next returns whether it produced a row, and fills in a row the caller passed.
• C++: an abstract base class with virtual open, next and close, and each node owning its child through a std::unique_ptr.
• Rust: a trait with fn next(&mut self) -> Option<Row>, and nodes holding their child as Box<dyn Trait>. It is the same shape as Rust's own Iterator.
• Zig: a struct holding a pointer to its state and a table of function pointers, the pattern std.mem.Allocator uses, or a tagged union of node kinds with a switch in next.
• All languages: └ and ─ are three bytes each in UTF-8. Write them as a string, not as single characters.