Parsing SQL into trees

Text is too flat

SQL enters the database as text, which is easy for people to write but unusable for an executor. The string contains spaces, keywords, identifiers, operators, literals, comments, and punctuation. Some characters belong together. Some words are reserved in one position and ordinary names in another. Parentheses can turn a small expression into a nested language. Parsing is the act of turning that flat stream into a tree where structure is explicit enough for later stages to reason about.

The first pass is lexical. The lexer groups characters into tokens: keywords, identifiers, numbers, string literals, operators, commas, parentheses, and terminators. This step sounds mechanical, but it already carries design choices. Is `select` different from `SELECT`? When is a quoted name case-sensitive? How are escaped string characters handled? Which operator spellings are legal? Tokenization is where the database stops seeing raw characters and starts seeing vocabulary.

Grammar gives shape

The parser then checks whether the token sequence fits the grammar. A grammar describes valid arrangements: a select statement may have a target list, a from clause, a where clause, grouping, ordering, and so on. Expressions have precedence and associativity. Function calls have argument lists. Subqueries contain statements inside expressions or relations. The parser's output is commonly an abstract syntax tree, or AST, that represents the grammatical shape without preserving every surface detail.

An AST for a query is not yet a plan. It does not know whether a table exists, whether a column name is ambiguous, or whether an operator can accept the supplied types. It only captures what the text said. That distinction matters. Parsing answers, "Is this a syntactically valid statement, and how is it nested?" Later analysis answers, "What does it mean in this database?"

Two kinds of wrong

Two invalid queries can fail for entirely different reasons. One says `select from where`. The words are recognizable, but the grammar has no valid structure for them. This is a parse error. Another says `select missing_column from accounts`. The grammar is fine: a select list names something and a from clause names a relation. The problem is semantic. The parser should not need the catalog to reject the first query, and it should not pretend it can reject the second without later context.

A tempting design is to parse directly into executable operations. For a small language, that can work. For SQL, it creates trouble quickly. Syntax contains too much ambiguity that only later context can resolve, and execution contains too many decisions that should remain flexible. If parsing chooses a scan method or join order, the system has collapsed language understanding into physical planning too early.

Another tempting design is to keep the AST very close to the original text. That helps with error messages and formatting tools, but it burdens later stages with surface clutter. A database AST should preserve meaning-bearing structure: statement kind, target expressions, relation references, predicates, function calls, sort keys, and nested scopes. Comments and whitespace matter to humans, not to query planning.

Expression trees hold the meaning

Expression parsing needs care. The text `a + b * c` should not become the same tree as `(a + b) * c`. Operator precedence changes meaning. So does associativity, especially for operators that are not mathematically interchangeable. SQL also has special forms such as `between`, `in`, `is null`, `like`, row constructors, casts, and case expressions. A parser must normalize enough to simplify later analysis without rewriting meaning prematurely.

Subqueries introduce scopes. In `where exists (select 1 from orders where orders.customer_id = customers.id)`, the inner query can refer to its own relations and sometimes outer ones. The parser can represent nesting, but it cannot fully decide binding. It must leave enough structure for the analyzer to work out which names belong to which scope.

Good parse errors are part of the architecture. If the parser reports only "invalid syntax," users have to debug by guessing. A serious database tracks token positions and expected forms so it can point near the mistake. This requires the lexer and parser to carry location information through the tree. Later semantic errors benefit from the same discipline because they can point back to the expression or name that failed.