Repository navigation
Commit ab0504c
perf: Optimize array_has() for array needle
`array_has(array, element)` returns, for each row, whether the array contains
the element. When the `element` (needle) is an array rather than a scalar -- the
needle argument is a column with one value per row, e.g. `array_has(t1.tags,
t2.key)` in a join filter -- execution goes through `array_has_dispatch_for_array`
(the `ColumnarValue::Array` needle branch), which compared each row by invoking
the Arrow `eq` kernel once per row. That kernel allocates a `BooleanArray` and
pays downcast and dispatch overhead on every row. (The scalar-needle branch was
optimized separately in #20374.)
Add a fast path for primitive and string element types, preserving the Arrow
`eq` kernel semantics (total-order float equality; null elements never match).
With all-valid elements each row is a single branchless OR-reduction over the
native values. When primitive elements contain nulls -- whose backing values
are arbitrary -- the per-element equality bitmap is ANDed with the validity
bitmap (one word-parallel op, no per-element branch) before the per-row
reduction, so null slots never match regardless of their value. Past a moderate
average list length (`NULL_FAST_PATH_MAX_LEN`) this bitmap's extra passes lose to
the per-row kernel, so the element-null branch bails to it there; that length is
measured over the visible (sliced) region, so a sliced array's hidden child
elements don't route a small window to the slow path. The all-valid fold has no
such crossover.
For string elements each row is a single pass over the row's values; for
`Utf8View` this is view-aware -- the byte length and 4-byte prefix packed in the
128-bit view reject non-matches before touching the data buffer (what the `eq`
kernel does, but without its per-row allocation), and an inline needle (<= 12
bytes) is matched by full-view equality with no materialization at all. Nested
and other element types keep using the per-row `eq` kernel.
What this removes is the fixed per-row kernel overhead, not the element
comparison itself, so the gain is largest for short lists and shrinks as lists
grow. Criterion microbenchmark, array needle on a 100k-row batch vs the per-row
`eq` kernel (NOT end-to-end query time):
i64, all-valid elements: ~15x (64-elem lists), ~1.9x at 1024-elem
i64, ~30% null elements: ~9x (8-elem) ... ~1x (512-elem); falls back beyond
Utf8 / LargeUtf8: ~2.5x
Utf8View (view-aware): ~5x on short/inline strings
Every shape improves with no regression.
End-to-end impact depends on how much of a query `array_has` accounts for. For a
query dominated by an array-needle `array_has` join filter (a `NestedLoopJoinExec`
with `filter=array_has(tags, key)` over 3000x3000 rows of 8-element lists) total
time drops from 0.95s to 0.059s (~16x, identical results). For a workload where
`array_has` is a smaller fraction -- e.g. the ~6% of profile that motivated this
(see #18070 / #18161, which fixed the join's deep-copy but left the per-row
`array_has` cost) -- the overall speedup is single-digit percent.
The array-needle criterion benchmark used for these numbers is added separately
(so it can be run against `main` to capture the before baseline).
Part of #18727.
Co-Authored-By: Claude Opus 4.8 <[email protected]>1 parent a0e9887 commit ab0504c
1 file changed
Lines changed: 691 additions & 6 deletions
0 commit comments