WHERE as an Expression Tree

After this lesson WHERE understands OR, NOT, parentheses and IS [NOT] NULL, with the same answers a real SQL database gives. The flat list of ANDed comparisons from lesson 4 becomes a tree, and a new three-valued logic decides which rows survive.

From a list to a tree

(age > 20 AND age < 30) OR name = 'Bob' cannot be a list: two things are joined by AND, and the result is joined to a third by OR. Every operator has operands, and operands can be operators, so the natural shape is a tree whose leaves are comparisons:

OR
|-- AND
|   |-- age > 20
|   `-- age < 30
`-- name = 'Bob'

Evaluating a row is a recursive walk: a leaf evaluates its comparison, AND/OR evaluate their two children and combine them, NOT evaluates its one child and flips it.

Precedence is one function per level

In SQL, NOT binds tighter than AND, which binds tighter than OR. Without parentheses, a = 1 OR a = 2 AND b = 9 means a = 1 OR (a = 2 AND b = 9). A recursive-descent parser encodes this by giving each level its own function that calls the next tighter one for its operands:

or_expr  := and_expr { OR  and_expr }
and_expr := not_expr { AND not_expr }
not_expr := NOT not_expr | primary
primary  := "(" or_expr ")" | operand IS [NOT] NULL | comparison

A parenthesis jumps back to the top of the chain, which is how ((a)) and NOT (x AND y) nest to any depth. Loops ({ ... }) build left-leaning trees, so a OR b OR c is (a OR b) OR c. Parsing must also consume the whole clause: anything left over, such as an unmatched ), is ERR syntax error.

Three values, not two

A comparison with NULL is not false, it is unknown. If unknown were treated as false early, NOT would turn it into true and wrongly admit rows. Keep three values all the way up, and let only true keep a row.

NOT true is false, NOT false is true, NOT unknown is unknown. The rule of thumb: AND is false if either side is false and true only if both are true; OR is true if either side is true and false only if both are false; everything else is unknown.

The case that exposes a two-valued shortcut: take a row where x is NULL and y is 'a', and the filter NOT (x = 1 OR y = 'z').

x = 1          unknown
y = 'z'        false
unknown OR false   ->  unknown
NOT unknown        ->  unknown     the row is NOT kept

A version that turns unknown into false at the comparison would compute false OR false = false and NOT of that = true, and keep the row.

IS NULL: asking about NULL itself

x = NULL can never be true, so SQL has dedicated syntax: x IS NULL is true when the value is NULL and false otherwise, never unknown. x IS NOT NULL is its opposite. The operand can be a column, a literal or rowid.

Common mistakes

• Unknown as false. Fails NOT (x = 1 OR y = 'z') above.
• Flat precedence. a = 1 OR a = 2 AND b = 9 evaluated left to right gives different rows.
• NOT swallowing too much. NOT a = 1 AND b = 2 is (NOT a = 1) AND b = 2.
• Not binding all leaves. Unknown column names must be reported from anywhere in the tree.

Your exercise

The starter keeps the old AND-only chain. Replace parse_where, where_bind and where_eval with the tree versions; cond_eval already returns true, false or unknown for a single comparison. The one mistake to avoid: collapsing unknown to false before NOT sees it.