Repository navigation
Commit 49c78ee
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 apache#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. 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: ~13x (64-elem lists), ~1.9x at 1024-elem
i64, ~30% null elements: ~10x (8-elem) ... ~1x (512-elem); falls back beyond
string elements: ~1.45x
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 apache#18070 / apache#18161, which fixed the join's deep-copy but left the per-row
`array_has` cost) -- the overall speedup is single-digit percent.
Part of apache#18727.
Co-Authored-By: Claude Opus 4.8 <[email protected]>1 parent a0e9887 commit 49c78ee
2 files changed
Lines changed: 726 additions & 6 deletions
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
43 | 43 | | |
44 | 44 | | |
45 | 45 | | |
| 46 | + | |
46 | 47 | | |
47 | 48 | | |
48 | 49 | | |
49 | 50 | | |
50 | 51 | | |
51 | 52 | | |
| 53 | + | |
52 | 54 | | |
53 | 55 | | |
54 | 56 | | |
| |||
119 | 121 | | |
120 | 122 | | |
121 | 123 | | |
| 124 | + | |
| 125 | + | |
| 126 | + | |
| 127 | + | |
| 128 | + | |
| 129 | + | |
| 130 | + | |
| 131 | + | |
| 132 | + | |
| 133 | + | |
| 134 | + | |
| 135 | + | |
| 136 | + | |
| 137 | + | |
| 138 | + | |
| 139 | + | |
| 140 | + | |
| 141 | + | |
| 142 | + | |
| 143 | + | |
| 144 | + | |
| 145 | + | |
| 146 | + | |
| 147 | + | |
| 148 | + | |
| 149 | + | |
| 150 | + | |
| 151 | + | |
| 152 | + | |
| 153 | + | |
| 154 | + | |
| 155 | + | |
| 156 | + | |
| 157 | + | |
| 158 | + | |
| 159 | + | |
| 160 | + | |
| 161 | + | |
| 162 | + | |
| 163 | + | |
| 164 | + | |
| 165 | + | |
| 166 | + | |
| 167 | + | |
| 168 | + | |
| 169 | + | |
| 170 | + | |
| 171 | + | |
| 172 | + | |
| 173 | + | |
| 174 | + | |
| 175 | + | |
| 176 | + | |
| 177 | + | |
| 178 | + | |
| 179 | + | |
| 180 | + | |
| 181 | + | |
| 182 | + | |
| 183 | + | |
| 184 | + | |
| 185 | + | |
| 186 | + | |
| 187 | + | |
| 188 | + | |
| 189 | + | |
| 190 | + | |
| 191 | + | |
| 192 | + | |
| 193 | + | |
| 194 | + | |
| 195 | + | |
| 196 | + | |
| 197 | + | |
| 198 | + | |
| 199 | + | |
| 200 | + | |
| 201 | + | |
| 202 | + | |
| 203 | + | |
| 204 | + | |
| 205 | + | |
| 206 | + | |
| 207 | + | |
| 208 | + | |
| 209 | + | |
| 210 | + | |
| 211 | + | |
| 212 | + | |
| 213 | + | |
| 214 | + | |
| 215 | + | |
| 216 | + | |
| 217 | + | |
| 218 | + | |
| 219 | + | |
| 220 | + | |
| 221 | + | |
| 222 | + | |
| 223 | + | |
| 224 | + | |
| 225 | + | |
| 226 | + | |
| 227 | + | |
| 228 | + | |
| 229 | + | |
| 230 | + | |
| 231 | + | |
| 232 | + | |
| 233 | + | |
| 234 | + | |
| 235 | + | |
| 236 | + | |
| 237 | + | |
| 238 | + | |
| 239 | + | |
| 240 | + | |
| 241 | + | |
| 242 | + | |
| 243 | + | |
| 244 | + | |
| 245 | + | |
| 246 | + | |
| 247 | + | |
| 248 | + | |
| 249 | + | |
| 250 | + | |
| 251 | + | |
| 252 | + | |
| 253 | + | |
122 | 254 | | |
123 | 255 | | |
124 | 256 | | |
| |||
659 | 791 | | |
660 | 792 | | |
661 | 793 | | |
| 794 | + | |
| 795 | + | |
| 796 | + | |
| 797 | + | |
| 798 | + | |
| 799 | + | |
| 800 | + | |
| 801 | + | |
| 802 | + | |
| 803 | + | |
| 804 | + | |
| 805 | + | |
| 806 | + | |
| 807 | + | |
| 808 | + | |
| 809 | + | |
| 810 | + | |
| 811 | + | |
| 812 | + | |
| 813 | + | |
| 814 | + | |
| 815 | + | |
| 816 | + | |
| 817 | + | |
662 | 818 | | |
663 | 819 | | |
664 | 820 | | |
| |||
0 commit comments