Context: Velox's cuDF integration (velox/experimental/cudf) uses cudf::conditional_inner_join / cudf::conditional_left_semi_join to execute nested-loop joins whose condition isn't a simple equi-key match. These APIs require the join condition to be compiled into a cudf::ast::tree — a small closed set of arithmetic/comparison/logical operators that libcudf's AST evaluator can execute directly inside the join kernel, without ever materializing the full cross product.
The gap: SQL LIKE (wildcard pattern matching) is not one of those AST operators. When the pattern operand is itself a column that varies per build-side row — e.g. t.value LIKE u.pattern, where t is the probe/left table and u is the build/right table — there's no way to express this as a cudf::ast::tree at all.
Velox's normal workaround for AST-unsupported sub-expressions is to precompute them: evaluate the sub-expression once as an extra column on whichever single side supplies all its inputs, then reference that precomputed column via a plain AST column-reference in the rest of the tree. That only works when every input to the unsupported sub-expression comes from one side. Here it can't: value comes from the probe table, pattern comes from the build table, and no row pairing exists yet at precompute time (that pairing is what the join produces), so there is nothing to precompute against.
Velox's integration originally didn't handle this at all and crashed with:
Expression spans both join sides and cannot be precomputed: like
What a native libcudf feature would need to cover, to close this cleanly: one of —
Native LIKE/glob pattern-matching support as a first-class cudf::ast operator (taking two ast::column_references, one per table, analogous to how facebookincubator#8858 added basic string equality/comparison to AST — but pattern matching specifically is still missing), so conditional_inner_join/conditional_left_semi_join can evaluate it directly without any workaround; or
A join API variant that accepts an arbitrary row-wise callable (not restricted to the AST operator set) evaluated against the joined row pair on the fly — i.e. a "mixed" conditional join that mixes AST-representable predicates with a general/JIT expression for the parts AST can't express, without needing to materialize the full N × M cross product up front.
How we worked around it on the Velox side (facebookincubator/velox): rather than rejecting the query or falling back to CPU, we detect this "non-AST sub-expression spanning both sides" case up front, and — for that case only — replace conditional_inner_join with: (a) materializing explicit (probeIndex, buildIndex) pairs for the full cross product via arithmetic on a cudf::sequence (no cuDF join kernel involved), (b) gathering both sides' rows at those indices, (c) evaluating the whole condition generally (Velox's own JIT/functional expression evaluator, not cudf::ast) against the gathered rows, and (d) apply_boolean_mask-ing the index pairs down to matches — which are then fed into the same downstream gather/matched-flags logic that conditional_inner_join's output would have used. Correct, but it pays the full O(N × M) materialization cost that a native AST/join-kernel-level solution (option 1 or 2 above) would avoid, since conditional_inner_join never materializes the full cross product — it only returns the matching pairs.
Why this matters beyond just LIKE: the same gap applies to any non-AST-representable expression that references columns from both join sides — regex matching, UDFs, or anything else outside the AST operator set would hit the identical wall.
Context: Velox's cuDF integration (velox/experimental/cudf) uses cudf::conditional_inner_join / cudf::conditional_left_semi_join to execute nested-loop joins whose condition isn't a simple equi-key match. These APIs require the join condition to be compiled into a cudf::ast::tree — a small closed set of arithmetic/comparison/logical operators that libcudf's AST evaluator can execute directly inside the join kernel, without ever materializing the full cross product.
The gap: SQL LIKE (wildcard pattern matching) is not one of those AST operators. When the pattern operand is itself a column that varies per build-side row — e.g. t.value LIKE u.pattern, where t is the probe/left table and u is the build/right table — there's no way to express this as a cudf::ast::tree at all.
Velox's normal workaround for AST-unsupported sub-expressions is to precompute them: evaluate the sub-expression once as an extra column on whichever single side supplies all its inputs, then reference that precomputed column via a plain AST column-reference in the rest of the tree. That only works when every input to the unsupported sub-expression comes from one side. Here it can't: value comes from the probe table, pattern comes from the build table, and no row pairing exists yet at precompute time (that pairing is what the join produces), so there is nothing to precompute against.
Velox's integration originally didn't handle this at all and crashed with:
Expression spans both join sides and cannot be precomputed: like
What a native libcudf feature would need to cover, to close this cleanly: one of —
Native LIKE/glob pattern-matching support as a first-class cudf::ast operator (taking two ast::column_references, one per table, analogous to how facebookincubator#8858 added basic string equality/comparison to AST — but pattern matching specifically is still missing), so conditional_inner_join/conditional_left_semi_join can evaluate it directly without any workaround; or
A join API variant that accepts an arbitrary row-wise callable (not restricted to the AST operator set) evaluated against the joined row pair on the fly — i.e. a "mixed" conditional join that mixes AST-representable predicates with a general/JIT expression for the parts AST can't express, without needing to materialize the full N × M cross product up front.
How we worked around it on the Velox side (facebookincubator/velox): rather than rejecting the query or falling back to CPU, we detect this "non-AST sub-expression spanning both sides" case up front, and — for that case only — replace conditional_inner_join with: (a) materializing explicit (probeIndex, buildIndex) pairs for the full cross product via arithmetic on a cudf::sequence (no cuDF join kernel involved), (b) gathering both sides' rows at those indices, (c) evaluating the whole condition generally (Velox's own JIT/functional expression evaluator, not cudf::ast) against the gathered rows, and (d) apply_boolean_mask-ing the index pairs down to matches — which are then fed into the same downstream gather/matched-flags logic that conditional_inner_join's output would have used. Correct, but it pays the full O(N × M) materialization cost that a native AST/join-kernel-level solution (option 1 or 2 above) would avoid, since conditional_inner_join never materializes the full cross product — it only returns the matching pairs.
Why this matters beyond just LIKE: the same gap applies to any non-AST-representable expression that references columns from both join sides — regex matching, UDFs, or anything else outside the AST operator set would hit the identical wall.