docs/architecture/sql-execution.md
Now that the planner and optimizer have done all the hard work of figuring out how to execute a query, it's time to actually execute it.
Plan execution is done by sql::execution::Executor in the
sql::execution
module, using a sql::engine::Transaction to access the SQL storage engine.
The executor takes a sql::planner::Plan as input, and will return an ExecutionResult depending
on the statement type.
When executing the plan, the executor will branch off depending on the statement type:
We'll focus on SELECT queries here, which are the most interesting.
toyDB uses the iterator model (also known as the volcano model) for query execution. In the case of
a SELECT query, the result is a row iterator, and pulling from this iterator by calling next()
will drive the entire execution pipeline by recursively calling next() on the child nodes' row
iterators. This maps very naturally onto Rust's iterators, and we leverage these to construct the
execution pipeline as nested iterators.
Execution itself is fairly straightforward, since we're just doing exactly what the planner tells us
to do in the plan. We call Executor::execute_node recursively on each sql::planner:Node,
starting with the root node. Each node returns a result row iterator that the parent node can pull
its input rows from, process them, and output the resulting rows via its own row iterator (with the
root node's iterator being returned to the caller):
Executor::execute_node() will simply look at the type of Node, recursively call
Executor::execute_node() on any child nodes, and then process the rows accordingly.
We won't discuss every plan node in detail, but let's consider the movie plan we've looked at previously:
Select
└─ Order: movies.released desc
└─ Projection: movies.title, movies.released, genres.name as genre
└─ HashJoin: inner on movies.genre_id = genres.id
├─ Scan: movies (released >= 2000)
└─ Scan: genres
We'll recursively call execute_node() until we end up in the two Scan nodes. These simply
call through to the SQL engine (either using Raft or local disk) via Transaction::scan(), passing
in the scan predicate if any, and return the resulting row iterator:
HashJoin will then join the output rows from the movies and genres iterators by using a
hash join. This builds an in-memory table for genres and then iterates over movies, joining
the rows:
The Projection node will simply evaluate the (trivial) column expressions using each joined
row as input:
And finally the Order node will sort the results (which requires buffering them all in memory):
The output row iterator of Order is returned via ExecutionResult::Select, and the caller can now
go ahead and pull the resulting rows from it.
The entry point to the SQL engine is the sql::execution::Session, which represents a single user
session. It is obtained via sql::engine::Engine::session().
The session takes a series of raw SQL statement strings as input and parses them:
For each statement, it returns a result depending on the kind of statement:
The session itself performs transaction control. It handles BEGIN, COMMIT, and ROLLBACK
statements, and modifies the transaction accordingly.
Any other statements are processed by the SQL planner, optimizer, and executor as we've seen in previous sections.
These statements are always executed using the session's current transaction. If there is no active transaction, the session will create a new, implicit transaction for each statement.
And with that, we have a fully functional SQL engine!