Anatomy of a SQL Engine

Summary

May marks five years since Dolt adopted go-mysql-server. Today we summarize the current state of GMS by walking through a query's journey from parsing to result spooling. Overview SQL engines are the logical layer of a database that sit between client and storage. To mutate the database state on behalf of a client, a SQL engine performs the following steps: Parsing Binding Plan Simplification Join Exploration Plan Costing Execution Spooling Results Most systems also have a variety of execution strategies (row vs vector based) and infrastructure layers (run locally vs distributed). At the moment Dolt's engine by default uses row-based execution within the local server. Parsing The first thing a SQL Engine does when receiving a query is try to form a structured abstract syntax tree (AST). The AST is a rough cut of whether the query is well formed. The entrypoint of the parser is here. A client driver initializes a query by passing bytes over the network through a server listener into a handler command ComHandler. The handler accumulates data until reaching a delimiter token (usually ;). The string is then split into space-delimited tokens and fed into parsing. The diagram below shows the movement from bytes to tokens and finally AST nodes: Right recursive parsing is easy to understand and debug because the program is a decision tree that chooses the next path based on the lookahead token. So a right-recursive parser might initially expect a SELECT, and then accumulate select expressions until a FROM token, and so on. This is "right recursive" because when we hit something like a join, we greedily accumulate table tokens and keep moving the parse state deeper. But right-recursive parsers are top-down, which unfortunately uses stack memory proportional to the number of tokens. Left-recursive parsers are instead bottom-up and collapse the accumulated stack eagerly when they find a happy pattern. So when we see a join, we'll fold the join so far before checking for more t...