Query predicate evaluator

The idea

When you write WHERE age > 30 AND (country = 'US' OR country = 'CA'), the database doesn't read that as a sentence. It builds a small tree: AND and OR are the branches, and each comparison — age > 30, country = 'US' — is a leaf.

To filter a table, the engine walks that tree once per row. Each leaf compares one column to one value and answers true or false. The branches combine those answers: AND needs every child true, OR needs any child true. A row survives the filter only if the whole tree evaluates to true.

The trick that makes it fast is short-circuiting: the moment an AND meets a false child, the answer is already false, so it stops — and the moment an OR meets a true child, it's already true, so it stops too.

How it works

The evaluator is a plain recursion over the tree. A leaf compares a column from the current row; an AND returns false as soon as a child is false; an OR returns true as soon as a child is true. That early return is the short-circuit.

def evaluate(node, row):
    if node["op"] == "leaf":
        col, cmp, val = node["col"], node["cmp"], node["val"]
        left = row.get(col)
        if left is None:                  # NULL: comparison is UNKNOWN, treat as not-true
            return False
        if cmp == ">":  return left > val
        if cmp == "=":  return left == val
        # ... other comparators

    if node["op"] == "AND":
        for child in node["children"]:
            if not evaluate(child, row):  # first false settles it
                return False              #   -> skip the rest
        return True

    if node["op"] == "OR":
        for child in node["children"]:
            if evaluate(child, row):      # first true settles it
                return True               #   -> skip the rest
        return False


def where(rows, predicate):
    return [row for row in rows if evaluate(predicate, row)]

Filtering the table is then one line: keep each row for which evaluate(predicate, row) is true.

Cost

Ordering is a real lever: put the cheap and selective predicate first so short-circuiting fires early. Checking status = 'closed' (knocks out 95% of rows for free) before an expensive LOWER(name) LIKE '%a%' can save most of the work — same result, far fewer comparisons.

Watch out for

• NULL is three-valued logic, not false. NULL > 30 is UNKNOWN, and a row only survives a WHERE when the predicate is exactly true — so unknown rows drop, and NOT (NULL > 30) is also unknown, so they drop there too. Reason about it explicitly with IS NULL.
• Short-circuit means side effects may not run. If a child calls a function with side effects, a settled AND/OR can skip it entirely. Don't rely on every predicate being evaluated.
• Type coercion. Comparing age > '30' (string against number) can silently coerce or compare lexicographically — '9' > '30' is true as strings. Compare like types.
• Precedence without parentheses. AND binds tighter than OR, so a OR b AND c means a OR (b AND c). If you meant (a OR b) AND c, the tree you got is not the tree you wanted.
• Ordering for cost. The result is the same whatever order the children sit in, but the work isn't. Put the cheapest, most selective predicate first.

Worked example

Take the query SELECT * FROM users WHERE age > 30 AND (country = 'US' OR country = 'CA') over four rows. The root is an AND with two children: the leaf age > 30, and an OR over country = 'US' and country = 'CA'.

Walk Mara, 41, FR: the leaf 41 > 30 is true, so the AND moves on. Inside the OR, FR = 'US' is false, then FR = 'CA' is false — the OR is false, so the AND is false and Mara is dropped. Now Dev, 24, US: the leaf 24 > 30 is false, so the AND short-circuits immediately — the whole OR branch is never even touched, and Dev drops. Ana, 52, CA passes the leaf, and the OR returns true on its second child, so Ana survives. Step through the visual above to watch each row's path and see who is left after the filter.

Check yourself