WHERE Evaluation — Filtering Rows

Your WHERE clause so far handles a single condition, or a flat chain of ANDs. Real predicates need more: OR, parentheses for grouping, NOT, and null checks. This lesson turns WHERE from a flat list of comparisons into a proper boolean expression tree that you evaluate recursively.

From flat conditions to an expression tree

A condition like

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

can't be represented as a simple list — it needs structure. Model it as a tree of nodes, where leaves are comparisons and internal nodes are boolean combinators:

OR
├── AND
│   ├── (age > 20)
│   └── (age < 30)
└── (name = 'Alice')

Evaluating this tree against a row is a straightforward recursive function: a comparison node evaluates directly (as in the previous lesson); an AND node evaluates both children and requires both True; an OR node evaluates both children and requires at least one True; a NOT node negates its single child's result.

def eval_expr(node, row, schema):
    if node.kind == "AND": return eval_expr(node.left, row, schema) and eval_expr(node.right, row, schema)
    if node.kind == "OR":  return eval_expr(node.left, row, schema) or  eval_expr(node.right, row, schema)
    if node.kind == "NOT": return not eval_expr(node.child, row, schema)
    if node.kind == "IS_NULL":     return get_value(row, schema, node.column) is None
    if node.kind == "IS_NOT_NULL": return get_value(row, schema, node.column) is not None
    return eval_comparison(node, row, schema)   # base case: col OP value

Parsing with correct precedence

Boolean expressions have a standard precedence order — NOT binds tighter than AND, which binds tighter than OR — mirroring arithmetic's "multiplication before addition." Without this, a OR b AND c would be ambiguous. The standard way to parse this correctly is recursive descent with one function per precedence level, from loosest to tightest:

parse_or()   -> parse_and() (OR parse_and())*
parse_and()  -> parse_not() (AND parse_not())*
parse_not()  -> NOT parse_not() | parse_primary()
parse_primary() -> '(' parse_or() ')' | comparison | IS_NULL_check

Each level calls the next-tighter level for its operands, and only combines results with its own operator. Parentheses are handled in parse_primary: when you see (, recursively call all the way back up to parse_or, then expect a matching ). This is the same technique used for parsing arithmetic expressions (+/- looser than *//), just applied to boolean operators — if you've built an expression parser earlier in this course, the structure will look familiar.

IS NULL / IS NOT NULL

Comparisons like = and > don't have well-defined behavior against a missing value in most SQL dialects — NULL = NULL is famously not true in real SQL, it's unknown. Rather than trying to make ordinary comparison operators handle nulls implicitly, SQL provides dedicated syntax:

WHERE age IS NULL
WHERE age IS NOT NULL

Implement these as their own leaf node kind that checks for a null marker directly, bypassing the ordinary comparison operators entirely.

Edge cases

• NOT (age > 20 AND age < 30) must correctly negate the entire parenthesized group, not just the first condition — this is exactly what recursive descent with explicit precedence levels gets right and a naive left-to-right scan gets wrong.
• Deeply nested parentheses, e.g. ((a AND b) OR (c AND (d OR e))), should parse correctly since each ( recursion handles its own nested structure independently.
• An empty predicate result (no rows satisfy a complex expression) is not an error — same as with simple WHERE, just print the header with zero data rows.