Torin is the new GPU execution engine we built at Starburst. It runs SQL query operators such as table scans, filters, projections, joins and aggregations on NVIDIA GPUs, using the cuDF library for the low-level work.
Building Torin, we met many challenges that are specific to GPU-based execution, or greatly amplified by the massively parallel nature of GPUs, and we learned many lessons on the way to an efficient GPU-based SQL engine. This post describes one of them as a case study: eager and lazy evaluation of expressions.
How a GPU evaluates an expression #
Take a typical filter:
WHERE l_discount BETWEEN 0.05 AND 0.07 AND l_quantity < 24
Torin processes rows in batches, and keeps each column of a batch in GPU memory as one contiguous array. BETWEEN is shorthand for two comparisons, so the filter is really three comparisons combined with AND: l_discount >= 0.05, l_discount <= 0.07 and l_quantity < 24. To evaluate the filter, Torin computes each comparison for every row of the batch at once, producing a column of booleans, and then combines the boolean columns with element-wise ANDs.
Figure 1: The filter as an expression tree. Each comparison is evaluated over the whole batch into a column of booleans, and each AND combines two such columns element by element.
This is the kind of work GPUs are built for. A GPU runs a computation as thousands of threads, scheduled in groups of 32 called warps, that all apply the same instruction to different values. In a single clock cycle, an NVIDIA L4 can process over 7,000 values, and an RTX PRO 6000 Blackwell over 24,000. For comparison, a 192-core CPU server using SIMD instructions processes a few thousand values per cycle.
Evaluating each side of the AND independently over whole columns is the natural way to use that parallelism. It works well for a filter consisting of comparisons only, where each side can safely be evaluated on every row. It doesn’t work in general.
Fallible expressions #
Consider this filter:
WHERE l_quantity > 0 AND l_extendedprice / l_quantity > 1000
The left side is there to protect the right side. SQL semantics are defined in a row-oriented manner. For any given row, the right side of an AND needs to be evaluated if and only if the left side is true, so the division never runs where l_quantity = 0. Queries written this way are common, and users rely on the guard.
A naive vectorized implementation of AND that evaluates both sides first divides on every row, including the ones where l_quantity is 0, and fails the query with a division by zero error. Obviously, Torin must always produce exactly the same results as execution without GPUs would, so failing the query is not an option.
We call an expression that can raise an error at runtime “fallible”. Division is fallible, and so are casts that can overflow, numeric or date/time arithmetic that can result in a value outside of the valid range, and many functions. On the other hand, expressions consisting of comparisons only are infallible: whatever the input, they return TRUE, FALSE or NULL and never fail.
The question is how to give the AND its lazy semantics without giving up the column-at-a-time vectorized evaluation that makes the GPU fast.
Three ways to evaluate the AND #
We’ll use six rows of data as the running example. Rows 2 and 6 have l_quantity = 0, so the division must not run on them.
Figure 2: Eager evaluation. Both sides are evaluated over all six rows, and the division fails on rows 2 and 6.
The first strategy is the one we started with: evaluate both sides over every row and combine. We call it eager evaluation. It is correct whenever the right side is infallible, because evaluating it on rows that don’t need it is harmless. Given how a GPU executes, it doesn’t even cost extra time: the whole column is processed at once either way. That is how a filter consisting of comparisons only runs, and since such filters are by far the most common, keeping them on this fastest path matters. For our filter with a division, however, it fails.
NULL masking
The solution is to evaluate the left side first and use its result to find the rows that still need the right side. For an AND, those are the rows where the left side is TRUE. On all other rows, the result is already decided.
On the decided rows, Torin replaces the inputs of the right side with NULL. Then it evaluates the right side over all rows, as before. Division by l_quantity being NULL yields NULL instead of failing, so nothing fails, and the NULL s land on rows where the AND result is FALSE anyway.
Figure 3: NULL masking. Inputs on decided rows 2 and 6 are replaced with NULL, the division returns NULL there, and the final AND is FALSE on those rows.
NULL masking costs one extra pass over each input column, and keeps everything else column-at-a-time over the full batch. It is correct for any expression that cannot fail when all of its inputs are NULL. Most arithmetic, comparisons and casts behave this way: a NULL input produces a NULL output without doing the computation that could fail.
Not every expression does.
Filter and scatter
Change the filter slightly:
WHERE l_quantity > 0 AND coalesce(l_extendedprice, 0) / coalesce(l_quantity, 0) > 1000
On the decided rows both inputs are now NULL, coalesce turns them into 0, and the division computes 0 / 0, on exactly the rows we tried to protect. Masking fails for an expression that turns a row of all-NULL inputs into values that make it fail.
Figure 4: Where NULL masking breaks. coalesce turns the masked NULLs on rows 2 and 6 into 0, and 0 / 0 fails.
The most general strategy doesn’t try to make the right side harmless on the decided rows. It removes those rows. Torin copies the rows that still need the right side into a smaller batch, evaluates the right side on that batch only, and scatters the results back to their original positions. Decided rows take FALSE.
Figure 5: Filter and scatter. Active rows 1, 3, 4 and 5 are copied into a 4-row batch, the right side is evaluated there, and the results are scattered back. Rows 2 and 6 never reach the division.
This works for any expression, because the right side is evaluated on exactly the rows where the original SQL expression needs it. The price is a copy of the input columns, plus the scatter at the end, so Torin uses it only when the cheaper strategies are not safe.
Choosing a strategy
To pick the cheapest safe strategy, every expression in Torin knows how it can fail:
- Never : comparisons, and arithmetic that cannot overflow, use eager evaluation;
- Only on rows where some input is not NULL :
l_extendedprice / l_quantityusesNULLmasking; - On any row :
coalesce(l_extendedprice, 0) / coalesce(l_quantity, 0)uses filter and scatter.
Each expression derives its class from its parts when the query is compiled. A division of two columns is in the middle class. A division moves to the last class only when both of its operands can be non-NULL with all inputs NULL, as when both are wrapped in coalesce.
Obviously, there is one more trick common to all the strategies. After evaluating the left side, Torin checks whether any row still needs the right side, or none does. In either case the masks and copies are skipped and only one path is evaluated.
One mechanism to rule them all #
AND is not the only lazy expression in SQL. OR needs its right side only where the left side isn’t TRUE. COALESCE needs an operand only where all the earlier ones are NULL. IF and CASE evaluate a branch only on the rows where it is selected. Each of them can guard a fallible expression in the same way, and implementing the three strategies separately for each would inflate the code and the potential for bugs.
Instead, the strategies live in one place: IF. For IF(condition, then, else), Torin evaluates the condition and then treats each branch the same way it treated the right side of the AND. A branch is evaluated eagerly, with NULL-masked inputs, or on a filtered batch, depending on how it can fail, and the two results are combined row by row or scattered into place.
The other lazy expressions are rewritten into IF. To do that we need one more construct, LET.
LET
SQL has no LET, but the idea is familiar from programming languages: give a value a name, compute it once, and use it several times. Go back to BETWEEN from the first example:
l_extendedprice * (1 - l_discount) BETWEEN 1000 AND 2000
This means the same as the following:
l_extendedprice * (1 - l_discount) >= 1000 AND
l_extendedprice * (1 - l_discount) <= 2000
But written out like this, the revenue expression would be computed twice. This would usually not be a problem, but it is inefficient when the compared expression is expensive to compute, and even incorrect when it is nondeterministic. With LET it is computed only once:
LET x = l_extendedprice * (1 - l_discount)
IN (x >= 1000 AND x <= 2000)
Note: the LET syntax used here is for illustration only. It can’t be used in a SQL query.
In Torin, LET evaluates the bound expression over the whole batch, keeps the resulting column, and lets the body refer to it as many times as needed.
Rewriting AND, OR and COALESCE
With IF and LET, the lazy expressions become:
a AND b => LET x = a IN IF(NOT x, FALSE, x AND b)
a OR b => LET x = a IN IF(x, TRUE, x OR b)
COALESCE(a, b) => LET x = a IN IF(x IS NULL, b, x)
LET makes sure the first operand is evaluated once, even though the rewritten form uses it twice. IF treats a NULL condition as false, so for AND the rows where x is NULL go to the second branch, where x AND b gives the SQL answer. In that branch, b is evaluated only on rows where it is needed, with whichever strategy its fallibility allows.
The rewrite is applied only where it is needed. Torin groups adjacent AND expressions into a single AND with many operands, then splits the operands into segments, starting a new one at every fallible operand, and keeps the operands within a segment as one eager AND. For example:
WHERE l_shipdate >= DATE '1994-01-01'
AND l_quantity > 0
AND l_extendedprice / l_quantity > 1000
AND l_discount < 0.05
This becomes two segments. The first two comparisons are evaluated eagerly, as before. The division and the comparison after it form the second segment, which is evaluated lazily, only on rows the first segment didn’t already reject. A filter consisting of comparisons only has a single segment, and compiles to exactly the eager AND it always did.
IF and LET get their fallibility from their parts, like every other expression. One rule is worth spelling out: a LET whose bound value can be non-NULL even when all its inputs are NULL makes its body fallible on any row. That is the coalesce case again, now hidden behind a name, and Torin has to see through it.
Closing #
Column-at-a-time vectorized evaluation is what makes a GPU fast, and short-circuit evaluation is what makes SQL guards work. Torin does both. Filters consisting of comparisons only keep running eagerly at full GPU speed. Guarded expressions get the cheapest strategy that is safe: NULL masking where a NULL input is enough to keep an expression from failing, and filter and scatter where it isn’t. All the lazy constructs in SQL go through a single implementation in IF, so the same strategies serve AND, OR, COALESCE and CASE, and the results are always the same as execution without GPUs would produce.
□□