WHERE Evaluation — Complex Conditions

So far our WHERE clause supports single conditions with AND. Now we add OR, parentheses, and NULL handling — making our query engine much more powerful.

Operator Precedence

SQL has a defined precedence order for logical operators:

Highest: NOT
Middle:  AND
Lowest:  OR

This means a OR b AND c is parsed as a OR (b AND c), not (a OR b) AND c. Just like 2 + 3 * 4 is 2 + (3 * 4) in arithmetic.

Parsing with Precedence

Use a recursive descent parser that mirrors the precedence:

parse_or():
    left = parse_and()
    while current_token == "OR":
        consume("OR")
        right = parse_and()
        left = OrExpr(left, right)
    return left

parse_and():
    left = parse_comparison()
    while current_token == "AND":
        consume("AND")
        right = parse_comparison()
        left = AndExpr(left, right)
    return left

parse_comparison():
    if current_token == "(":
        consume("(")
        expr = parse_or()     # recursion handles nesting!
        consume(")")
        return expr
    ...parse col op value...

The Expression Tree

A complex WHERE clause becomes a tree:

WHERE (age > 20 AND age < 30) OR name = 'Alice'

        OR
       /  \
     AND   =
    /   \   \
   >     <   name='Alice'
   |     |
 age>20 age<30

Evaluation walks this tree bottom-up: evaluate leaves, combine with AND/OR.

NULL Handling

NULL represents "unknown" and requires special operators:

WHERE name IS NULL
WHERE age IS NOT NULL

Key rule: NULL compared with anything is NULL (which is falsy):

• NULL = NULL is NULL, not true
• NULL > 5 is NULL, not false
• NULL AND true is NULL
• NULL OR true is true (short-circuit)

This follows SQL's three-valued logic (true, false, unknown).

How PostgreSQL Handles NULL

PostgreSQL's executor treats NULL as a third truth value throughout. The IS NULL and IS NOT NULL operators are special nodes in the expression tree — they don't go through the normal comparison path. This is why WHERE x = NULL never matches anything (use IS NULL instead).

Your Task

Extend WHERE to support OR, parentheses for grouping, correct AND/OR precedence, and IS NULL / IS NOT NULL checks.