Expression Trees and Precedence

Why this stage exists

Since the where-filter stage a WHERE clause has been one column, one of =, < or >, and one value. Real queries need more: where dept = 'eng' and salary > 100, where not done, where price * qty > 1000. Every later stage of this part leans on the same machinery: ORDER BY can sort by an expression, aggregates sum one, HAVING filters with one. So this stage replaces the single comparison with something general: an expression tree.

The tree is the important word. A line of text has no structure, and a = 1 or b = 2 and c = 3 can be read two ways. Read left to right, it keeps a row where a = 1 only if c = 3 as well. Read the way SQL means it, AND binds tighter, so a row with a = 1 is kept whatever c is. The two readings are two different trees, and they give different rows:

From text to tree

The lexer learns the new pieces: and, or and not become keywords, and <=, >=, !=, <>, +, -, / and % become symbols. A two-character symbol is one token only when its characters touch, so < = is two tokens and a syntax error. A - is always a token of its own: -1 is unary minus applied to the number 1, not a negative number. That keeps the lexer simple, and it means a-1 and a - 1 are the same thing.

The parser then reads tokens by precedence, from the loosest operator to the tightest:

The idea behind the parser is in that table. Each level only ever builds operators of its own level, and reads its operands from the level just below it. So the loosest operator ends up at the root, and the tightest ones sit just above the leaves. This is often called precedence climbing or recursive descent by levels. Parentheses work by sending the parser back to the loosest level for what is inside them; they are gone from the tree once it is built.

Comparisons do not chain. a = 1 = 2 has a second comparison where an operand belongs, and is 00302. A comparison gives a truth value, and the next section says why (a = 1) = (b = 2) would not get far either.

Values have types

The old WHERE check answered yes or no. An evaluator for expressions cannot: a + b is not yes or no, it is a number. So evaluation gives a value, and a value has a type: an INT, a VARCHAR, or a truth value, the result of a comparison, AND, OR or NOT. The next stage adds a third truth value, unknown, and is much easier if the evaluator already returns values rather than booleans.

The types of a tree do not depend on any row: a column's type is in the catalog, a literal's is written in the query. So they are checked once, before the first row is read, and a mistake is 00403 with nothing else printed. where name > 5 compares a VARCHAR with an INT; where a is an INT where a condition belongs. Both are caught even on an empty table.

What cannot be checked in advance is a value. a / b is fine until a row has b = 0, and then the statement stops with 01501. Arithmetic runs in signed 64-bit integers: a column holds 0 to 4294967295, but a - 5 may be negative and a * 2 may pass 4294967295 on the way to a comparison. A result outside 64 bits is 01502. Division drops the fraction towards zero, so -7 / 2 is -3, and the remainder takes the sign of the left side, so -7 % 2 is -1.

Evaluating, row by row

The scan hands up one row at a time, and the tree is evaluated from its root for each of them. A row is kept when the root gives true.

AND and OR evaluate their left operand first. When it already decides the answer, false for AND and true for OR, the right operand is not evaluated at all. That is what makes the guard in b != 0 and a / b = 2 work: on a row with b = 0, the division never happens.

A statement that stops with 01501 or 01502 prints its error line and nothing else, even if it had already found rows to print. Collect the rows, and print them only when the statement has finished. An UPDATE or DELETE that stops is undone by the statement rollback you built in Transactions and Recovery.

What the planner can still use

The planner of the index-scan stage turned where id > 25 into an IndexScan. It should keep doing that inside larger expressions, and it can, for one shape of tree: the parts of a WHERE joined by AND at the top. Each of those parts is a conjunct, and a row is kept only when every conjunct holds. So a conjunct that bounds the key can be answered by the B+Tree, and the rest checked by a Filter on the rows the tree finds:

An OR at the top is a single conjunct, so id = 4 or id = 5 is still a Filter over a SeqScan. That is correct, just slower; the Indexes and the Optimizer part comes back to it.

Output contract for this stage

These are the exact lines the tests check. The full definition is on the output contract page, sections 3, 39 and 40.

How an expression is printed, in ast and in a Filter: a column as typed, a number as its digits, a string in single quotes; AND, OR and NOT in capitals; other operators as typed, with a space on each side; unary minus with no space. Every operand that is not a column or a literal goes between parentheses, and nothing else does. So a + b * 2 = 7 prints as (a + (b * 2)) = 7, and a single comparison prints as it always did: id = 5.

The plan of a WHERE: with no key bound, a Filter holding the whole WHERE over a SeqScan. Otherwise an IndexScan whose key is the first = bound, or whose range is the first lower and the first upper bound, lower first (range: id >= 3 AND id <= 5), with a Filter above it for whatever is left. rows_examined counts the rows the IndexScan hands up, as before.

What you should see when done

$droid --db shop.db
Welcome to droid!
>create table t (id int, a int, b int, c int, name varchar(20));
Create table statement executed successfully
>insert into t (id, a, b, c, name) values (1, 1, 0, 0, 'ada');
Insert statement executed successfully (1 rows)
>insert into t (id, a, b, c, name) values (2, 0, 2, 3, 'bob');
Insert statement executed successfully (1 rows)
>insert into t (id, a, b, c, name) values (3, 0, 2, 0, 'cy');
Insert statement executed successfully (1 rows)
>select id from t where a = 1 or b = 2 and c = 3;
id
1
2
(2 rows)
[EXEC] rows_examined=3
>select id from t where (a = 1 or b = 2) and c = 3;
id
2
(1 rows)
[EXEC] rows_examined=3
>select name from t where a - 1 < 0 and id >= 2;
name
bob
cy
(2 rows)
[EXEC] rows_examined=2
>explain select name from t where a - 1 < 0 and id >= 2;
[PLAN] select name from t where a - 1 < 0 and id >= 2
[PLAN]   └── Filter ((a - 1) < 0)
[PLAN]       └── IndexScan (table=t, range: id >= 2)
>select id from t where b != 0 and c / b = 1;
id
2
(1 rows)
[EXEC] rows_examined=3
>select id from t where c / b = 1;
[ERROR:01501] Division by zero
>select id from t where name > 5;
[ERROR:00403] Cannot compare VARCHAR with INT
>.exit
exiting.. good bye!

Things to notice. Moving the parentheses changed which rows came back. a - 1 went below zero for rows 2 and 3, and that was fine. id >= 2 became the range of the scan, so only two rows were examined, while the rest of the WHERE became a Filter. The guarded division ran on every row without an error; the unguarded one stopped on row 1, where b is 0, and printed nothing but its error. The messages are yours to word; the tests check only the codes.

Common bugs in this stage

• Every binary operator at one level. The parser reads left to right and builds ((a = 1) or (b = 2)) and (c = 3). Write one level per row of the precedence table.
• Right-grouping subtraction. A level written as "operand, then operator, then the whole level again" builds a - (b - 1). Loop at each level, joining as you go.
• NOT bound too tightly. If NOT reads only the next operand, not a = 1 becomes (not a) = 1, which is a type error. NOT takes a whole comparison.
• The evaluator returns a boolean. It works today and breaks in the next stage. Return a value with a type.
• Unsigned arithmetic. a - 5 on a row with a = 3 wraps to a huge number and a - 5 < 0 keeps nothing. Work in signed 64 bits.
• Division that rounds down. -7 / 2 is -3 here. If your language's operator floors, or its remainder is always positive, fix the sign yourself.
• Types checked per row. where name > 5 on an empty table must still be 00403. Check types before the first row.
• Printing rows before an error. A division by zero on the fifth row must not leave four rows and a header on the screen.
• No short-circuit. b != 0 and a / b = 2 fails with 01501. AND must not evaluate its right side when the left is false.
• Parentheses kept in the tree. A "group" node makes ast print extra parentheses and the planner miss conjuncts written as (id >= 3) and a = 1. Parentheses only shape the tree.
• A conjunct used twice. Taking id >= 3 as the range and leaving it in the Filter gives the right rows and the wrong plan line.

Language notes

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

• C and C++: an expression node is a tagged struct: a kind, an operator, a value, and pointers to its operands. int64_t from <stdint.h> for arithmetic; __builtin_mul_overflow and its siblings (GCC and Clang) detect a result that does not fit. C's / and % already round towards zero.
• Rust: an enum Expr with a Box<Expr> per operand is the natural tree. i64::checked_mul, checked_add, checked_sub and checked_div return None on overflow, and checked_div also on division by zero. / and % round towards zero.
• Zig: a tagged union for the node, with pointers to operands allocated from an arena freed after each statement. @mulWithOverflow and friends detect overflow; @divTrunc and @rem are the rounding this page asks for.