Evaluating one expression against one row

The smallest job a query engine has: given a row and an expression like age + 10 > 40 AND city = 'Austin', produce a value. Get this right, including NULL, and everything after it is about deciding which rows to feed it.

A query engine does a lot: it scans tables, joins them, groups, sorts, and picks among a combinatorial number of plans. Underneath all of that, though, the innermost loop keeps asking one question: what does this expression evaluate to for this row? A WHERE clause asks it once per row to decide whether to keep the row. A SELECT list asks it once per output column. Join conditions, sort keys, and group keys ask it too.

So that's where we start. By the end of this post we'll have a representation for values and rows, a tree for expressions, an evaluator that walks the tree, SQL's peculiar three-valued logic, and a second evaluator that's faster because it does its thinking once instead of once per row.

Values, rows, schemas

Our engine has five kinds of value: NULL, integers, floats, strings, and booleans. In Go a value is any holding nil, int64, float64, string, or bool. In Clojure it's nil, a long, a double, a String, or a Boolean. No dates, no decimals, no collations. Those are real work in a real engine and none of it teaches anything about execution.

A row is a positional list of values. A schema is the matching list of column names, qualified by table: customers.id, customers.name, and so on. Here is the toy table that appears all through this series:

Why positional rather than a map from column name to value? Because every operator downstream will touch every row, and "look up age in a hash map" is a cost you'd pay billions of times. "Read slot 3" is an array index. Names live in the schema, which you consult once, when you build the thing that will run. That split between work done once per query and work done once per row comes back again and again, and it is the main idea in this post.

Expressions are trees

A parser turns age + 10 > 40 AND city = 'Austin' into a tree. Operators are interior nodes and columns and literals are leaves:

AND
├── >
│   ├── +
│   │   ├── Col("age")
│   │   └── Lit(10)
│   └── Lit(40)
└── =
    ├── Col("city")
    └── Lit("Austin")

We don't need a parser yet. The integrated engine has one, but here we build trees by hand. In Go each node is a struct implementing an Expr interface: Col{Name}, Lit{V}, Bin{Op, L, R}, Not{E}, IsNull{E}, and Func{Name, Args}. In Clojure we use plain vectors:

[:and [:> [:+ [:col "customers.age"] [:lit 10]] [:lit 40]]
      [:= [:col "customers.city"] [:lit "Austin"]]]

That's the whole data model: an expression is data describing a computation. What remains is running it.

Walking the tree

The obvious evaluator is a recursive function with one case per node type. To evaluate a node, evaluate its children, then combine the results. That's a post-order traversal:

function eval(expr, row, schema)
  match expr
    case Col(name)    -> return row[indexOf(schema, name)]   -- name lookup, every time
    case Lit(v)       -> return v
    case Bin(op, l, r) ->
      a = eval(l, row, schema)
      b = eval(r, row, schema)
      return apply(op, a, b)
    case Not(e)       -> return not3(eval(e, row, schema))
    case IsNull(e)    -> return eval(e, row, schema) is null

Step through it below. Pick a row and an expression and watch values move up the tree. Then pick Bo and watch what his NULL age does.

Two things are worth noticing. First, with Ada the second and third expressions finish early. If the left side of an OR is TRUE, the right side can't change the answer, so a sensible evaluator doesn't compute it. Second, with Bo, the NULL doesn't stop at the age leaf: NULL + 10 is NULL, NULL > 40 is NULL, and then the AND has to decide what "unknown and true" means.

NULL, and why SQL has three truth values

NULL in SQL doesn't mean "nothing" or "zero." It means unknown. Bo has an age; we just don't know it. Once you read it that way, the rules all follow from one question: could the answer change depending on what the unknown value turns out to be?

• Arithmetic and comparison with NULL give NULL. Is Bo's age plus 10 greater than 40? It depends on his age. Unknown.
• FALSE AND NULL is FALSE. Whatever the unknown is, an AND with a false side is false. The answer doesn't depend on the unknown, so it isn't unknown.
• TRUE OR NULL is TRUE, for the same reason.
• TRUE AND NULL is NULL and NOT NULL is NULL. Both still depend on the unknown.
• IS NULL is the exception. It looks at the unknown-ness itself, so it only ever returns TRUE or FALSE.

Then comes the rule that bites in practice: a WHERE clause keeps a row only when the predicate is TRUE. NULL is not TRUE, so NULL rows are dropped, just as FALSE ones are. That makes WHERE p and WHERE NOT p not complements of each other: a row where p is NULL appears in neither result. Try it:

In code, three-valued AND and OR are small enough to read at a glance. Note the order of the checks: the decisive value wins over NULL.

function and3(a, b)
  if a == false or b == false then return false   -- decisive, even if the other is NULL
  if a == null or b == null then return null
  return true

function or3(a, b)
  if a == true or b == true then return true
  if a == null or b == null then return null
  return false

function passes(predicate, row)
  return eval(predicate, row) == true              -- not "truthy": exactly TRUE

Short-circuiting follows directly from these definitions. If the left side of an AND is FALSE, you can return FALSE without evaluating the right side. If the left side is NULL you can't stop, because a FALSE on the right would turn the result into FALSE. So evaluate the right side as well.

The rest of the semantics

Every engine has to pick answers for the edge cases. Here are ours, as written down in the project's design doc:

• int + int is an int; involve a float anywhere and you get a float. / always returns a float, so 7 / 2 is 3.50. Postgres would say 3; we're avoiding a whole category of surprise.
• Division by zero is NULL. Postgres raises an error and MySQL returns NULL; we follow MySQL because errors mid-stream complicate everything that comes later.
• Ints and floats compare numerically; strings compare by bytes; comparing a string to a number is an error.
• Functions (lower, upper, length, abs) return NULL for NULL input. coalesce exists precisely to not do that: it returns its first non-NULL argument.

Compiling the tree into closures

The tree walker works, but look at what it repeats for every row. For each node, it re-decides which kind of node this is (the match). For every column, it searches the schema for the column's name. Neither answer ever changes between rows. Both are decisions about the query, and we're making them over and over at row time.

The fix is to walk the tree once, make every decision that doesn't depend on the row, and return a function that only does the remaining per-row work. Each node becomes a closure that has already captured its children's closures and its resolved column index:

function compile(expr, schema) -> (row -> value)
  match expr
    case Col(name) ->
      i = indexOf(schema, name)            -- resolved once, here
      if i < 0 then error("unknown column " + name)
      return row -> row[i]
    case Lit(v) ->
      return row -> v
    case Bin("and", l, r) ->
      fl = compile(l, schema); fr = compile(r, schema)
      return row ->
        a = fl(row)
        if a == false then return false     -- short-circuit
        return and3(a, fr(row))
    case Bin(op, l, r) ->
      fl = compile(l, schema); fr = compile(r, schema)
      f  = lookupOperator(op)               -- also resolved once
      return row -> f(fl(row), fr(row))

A few things changed beyond speed. An unknown column is now an error at compile time, before any row is read. The per-row path doesn't mention the schema at all. And the structure of the work changed: the tree is still there, but it now exists as a tree of closures pointing at closures, and evaluation is a chain of plain function calls.

In Clojure this is especially natural, since compile returns fns:

(defn compile-expr [expr schema]
  (case (first expr)
    :col (let [i (.indexOf ^java.util.List schema (second expr))]
           (fn [row] (nth row i)))
    :lit (let [v (second expr)] (fn [_] v))
    :and (let [l (compile-expr (nth expr 1) schema)
               r (compile-expr (nth expr 2) schema)]
           (fn [row] (let [a (l row)]
                       (if (false? a) false (and3 a (r row))))))
    …))

How much faster is it? On the JVM, with the JIT inlining small closures, often several times for simple predicates. The exact number doesn't matter here. What matters is the habit of separating the work that depends only on the query from the work that depends on the row. Parts 6 and 7 push that habit much further: the planner makes even more decisions up front, and the final part compiles a whole query, not just one expression.

Where does the work in progress live?

Here's a question that looks pointless now but will matter by part 7: while an expression is halfway through evaluation, where is its state? In the tree walker, it's on the call stack: the left child's result sits in a local variable of the parent's stack frame while the right child is evaluated. The compiled version is the same; the nested closure calls hold intermediate values in their frames.

For expressions that's fine, since they run for nanoseconds. Nobody wants to pause halfway through age + 10. A whole query is another matter: it can run for minutes, and "paused partway through" becomes a feature you might want. In the next part, operators get their own state, and we'll start keeping track of which state lives in objects on the heap and which lives in stack frames.