Repository navigation
Commit d2d9b12
authored
IN LIST: clean up generic static filtering (#21927)
## Which issue does this PR close?
- Part of #19241.
- This PR was originally proposed as the first commit in the broader `IN
LIST` optimization series in #19390.
- This PR builds on the refactor extracted in #21649.
## Rationale for this change
After #21649, non-primitive constant `IN LIST` evaluation still uses the
extracted `ArrayStaticFilter` fallback path. That path relies on
comparator checks for each input row. This PR replaces that fallback
lookup with a precomputed hash table and shared result construction so
generic constant-list evaluation is cheaper before the later specialized
primitive and string optimizations from #19390.
## What changes are included in this PR?
The PR is split so reviewers can separate mechanical cleanup from the
behavior/performance changes:
1. `Refactor generic InList static filter helpers`
Pure refactoring. This moves the existing generic static-filter
construction and probe loop into helper methods inside
`ArrayStaticFilter`, without changing the lookup data structure or
result semantics.
2. `Build InList results from bitmaps`
Changes how the generic path materializes `BooleanArray` results after
membership has been computed. Instead of mixing membership checks and
SQL three-valued null handling in the row loop, this builds a contains
bitmap first and applies the null/negation rules with bitmap operations.
This keeps the same `IN` / `NOT IN` semantics, including the `NULL`
cases.
3. `Optimize generic InList static filtering`
Replaces the fallback lookup storage from a unit-valued raw-entry
`HashMap` to `hashbrown::HashTable<usize>`. The table still stores
indices into the constant list and still uses Arrow hashing plus
`make_comparator` for equality, but avoids the extra map value
bookkeeping.
The existing specialized primitive filters and dictionary handling are
intentionally left out of scope.
## Are these changes tested?
Yes.
## Are there any user-facing changes?
No. This is an internal performance optimization only.
<!-- codex-benchmark-start -->
## Local benchmark snapshot
Benchmark command:
```bash
cargo bench -p datafusion-physical-expr --profile release-nonlto --bench in_list_strategy -- --save-baseline <name>
```
Method: compare adjacent saved baselines using raw Criterion sample
minima (`min(time / iters)`). Lower is better; changes within +/-5% are
treated as noise.
Compared baselines: merge-base ->
[#21927](#21927)
Relevant scope: generic fallback string/view/binary rows.
Summary: 62 relevant rows, 61 faster, 0 slower, 1 within +/-5%.
Largest relevant deltas:
| Benchmark | Before | After | Change |
|---|---:|---:|---:|
| `utf8view/short_8b/list=64/match=0%` | 45.55 us | 21.85 us | -52.0%
(2.08x faster) |
| `utf8view/short_8b/list=256/match=0%` | 44.34 us | 21.71 us | -51.0%
(2.04x faster) |
| `utf8view/short_8b/list=16/match=0%` | 44.03 us | 21.60 us | -50.9%
(2.04x faster) |
| `utf8view/short_8b/list=4/match=0%` | 41.54 us | 20.52 us | -50.6%
(2.02x faster) |
| `utf8view/len_12b/list=16/match=0%` | 41.43 us | 20.55 us | -50.4%
(2.02x faster) |
| `utf8view/len_12b/list=64/match=0%` | 41.59 us | 21.00 us | -49.5%
(1.98x faster) |
| `fixed_size_binary/fsb16/list=10000/match=0%` | 58.11 us | 29.36 us |
-49.5% (1.98x faster) |
| `fixed_size_binary/fsb16/list=256/match=0%` | 55.49 us | 28.57 us |
-48.5% (1.94x faster) |
| `utf8view/shared_prefix/pfx=8/list=16/match=0%` | 57.54 us | 32.07 us
| -44.3% (1.79x faster) |
| `utf8view/mixed_len/list=16/match=0%` | 62.86 us | 35.25 us | -43.9%
(1.78x faster) |
| `fixed_size_binary/fsb16/list=4/match=0%` | 47.62 us | 27.20 us |
-42.9% (1.75x faster) |
| `fixed_size_binary/fsb16/list=64/match=0%` | 47.85 us | 27.45 us |
-42.6% (1.74x faster) |
| `utf8view/mixed_len/list=64/match=0%` | 66.09 us | 38.00 us | -42.5%
(1.74x faster) |
| `utf8/short_8b/list=256/match=0%` | 52.09 us | 30.49 us | -41.5%
(1.71x faster) |
| `utf8view/shared_prefix/pfx=12/list=32/match=0%` | 70.61 us | 42.33 us
| -40.1% (1.67x faster) |
<details>
<summary>Full relevant table (62 rows)</summary>
| Benchmark | Before | After | Change |
|---|---:|---:|---:|
| `fixed_size_binary/fsb16/list=10000/match=0%` | 58.11 us | 29.36 us |
-49.5% (1.98x faster) |
| `fixed_size_binary/fsb16/list=10000/match=50%` | 98.77 us | 81.20 us |
-17.8% (1.22x faster) |
| `fixed_size_binary/fsb16/list=256/match=0%` | 55.49 us | 28.57 us |
-48.5% (1.94x faster) |
| `fixed_size_binary/fsb16/list=256/match=50%` | 96.40 us | 79.32 us |
-17.7% (1.22x faster) |
| `fixed_size_binary/fsb16/list=4/match=0%` | 47.62 us | 27.20 us |
-42.9% (1.75x faster) |
| `fixed_size_binary/fsb16/list=4/match=50%` | 93.08 us | 75.58 us |
-18.8% (1.23x faster) |
| `fixed_size_binary/fsb16/list=64/match=0%` | 47.85 us | 27.45 us |
-42.6% (1.74x faster) |
| `fixed_size_binary/fsb16/list=64/match=50%` | 95.20 us | 74.96 us |
-21.3% (1.27x faster) |
| `nulls/utf8/long_24b/list=16/match=50%/nulls=20%` | 85.74 us | 74.79
us | -12.8% (1.15x faster) |
| `nulls/utf8/short_8b/list=16/match=50%/nulls=20%` | 80.01 us | 77.30
us | -3.4% (within +/-5%) |
| `nulls/utf8view/long_24b/list=16/match=50%/nulls=20%` | 110.19 us |
96.52 us | -12.4% (1.14x faster) |
| `nulls/utf8view/short_8b/list=16/match=50%/nulls=20%` | 74.78 us |
62.92 us | -15.9% (1.19x faster) |
| `nulls/utf8view/short_8b/list=16/match=50%/nulls=20%/NOT_IN` | 71.24
us | 63.51 us | -10.9% (1.12x faster) |
| `nulls/utf8view/short_8b/list=16/match=50%/nulls=50%` | 83.84 us |
62.11 us | -25.9% (1.35x faster) |
| `utf8/long_24b/list=256/match=0%` | 58.79 us | 37.57 us | -36.1%
(1.56x faster) |
| `utf8/long_24b/list=256/match=50%` | 107.85 us | 74.62 us | -30.8%
(1.45x faster) |
| `utf8/long_24b/list=4/match=0%` | 56.68 us | 37.64 us | -33.6% (1.51x
faster) |
| `utf8/long_24b/list=4/match=50%` | 100.40 us | 79.11 us | -21.2%
(1.27x faster) |
| `utf8/long_24b/list=64/match=0%` | 59.39 us | 35.95 us | -39.5% (1.65x
faster) |
| `utf8/long_24b/list=64/match=50%` | 101.26 us | 79.59 us | -21.4%
(1.27x faster) |
| `utf8/mixed_len/list=16/match=0%` | 60.51 us | 49.06 us | -18.9%
(1.23x faster) |
| `utf8/mixed_len/list=16/match=50%` | 154.00 us | 139.13 us | -9.7%
(1.11x faster) |
| `utf8/mixed_len/list=64/match=0%` | 63.46 us | 49.87 us | -21.4%
(1.27x faster) |
| `utf8/mixed_len/list=64/match=50%` | 154.01 us | 134.01 us | -13.0%
(1.15x faster) |
| `utf8/shared_prefix/pfx=12/list=32/match=50%` | 98.73 us | 76.64 us |
-22.4% (1.29x faster) |
| `utf8/short_8b/list=16/match=50%/NOT_IN` | 96.18 us | 72.15 us |
-25.0% (1.33x faster) |
| `utf8/short_8b/list=256/match=0%` | 52.09 us | 30.49 us | -41.5%
(1.71x faster) |
| `utf8/short_8b/list=256/match=50%` | 94.56 us | 74.39 us | -21.3%
(1.27x faster) |
| `utf8/short_8b/list=4/match=0%` | 51.95 us | 32.27 us | -37.9% (1.61x
faster) |
| `utf8/short_8b/list=4/match=50%` | 95.05 us | 78.47 us | -17.4% (1.21x
faster) |
| `utf8/short_8b/list=64/match=0%` | 53.60 us | 33.34 us | -37.8% (1.61x
faster) |
| `utf8/short_8b/list=64/match=50%` | 96.35 us | 80.95 us | -16.0%
(1.19x faster) |
| `utf8view/len_12b/list=16/match=0%` | 41.43 us | 20.55 us | -50.4%
(2.02x faster) |
| `utf8view/len_12b/list=16/match=50%` | 73.07 us | 50.49 us | -30.9%
(1.45x faster) |
| `utf8view/len_12b/list=64/match=0%` | 41.59 us | 21.00 us | -49.5%
(1.98x faster) |
| `utf8view/len_12b/list=64/match=50%` | 75.23 us | 50.25 us | -33.2%
(1.50x faster) |
| `utf8view/long_24b/list=16/match=0%` | 58.48 us | 38.22 us | -34.7%
(1.53x faster) |
| `utf8view/long_24b/list=16/match=50%` | 109.63 us | 87.32 us | -20.4%
(1.26x faster) |
| `utf8view/long_24b/list=256/match=0%` | 61.12 us | 38.40 us | -37.2%
(1.59x faster) |
| `utf8view/long_24b/list=256/match=50%` | 113.25 us | 91.61 us | -19.1%
(1.24x faster) |
| `utf8view/long_24b/list=4/match=0%` | 58.43 us | 39.48 us | -32.4%
(1.48x faster) |
| `utf8view/long_24b/list=4/match=50%` | 112.73 us | 90.14 us | -20.0%
(1.25x faster) |
| `utf8view/long_24b/list=64/match=0%` | 62.17 us | 38.48 us | -38.1%
(1.62x faster) |
| `utf8view/long_24b/list=64/match=50%` | 109.35 us | 87.64 us | -19.8%
(1.25x faster) |
| `utf8view/mixed_len/list=16/match=0%` | 62.86 us | 35.25 us | -43.9%
(1.78x faster) |
| `utf8view/mixed_len/list=16/match=50%` | 126.60 us | 103.97 us |
-17.9% (1.22x faster) |
| `utf8view/mixed_len/list=64/match=0%` | 66.09 us | 38.00 us | -42.5%
(1.74x faster) |
| `utf8view/mixed_len/list=64/match=50%` | 137.76 us | 112.23 us |
-18.5% (1.23x faster) |
| `utf8view/shared_prefix/pfx=12/list=32/match=0%` | 70.61 us | 42.33 us
| -40.1% (1.67x faster) |
| `utf8view/shared_prefix/pfx=12/list=32/match=50%` | 115.15 us | 94.27
us | -18.1% (1.22x faster) |
| `utf8view/shared_prefix/pfx=16/list=64/match=0%` | 63.47 us | 40.67 us
| -35.9% (1.56x faster) |
| `utf8view/shared_prefix/pfx=16/list=64/match=50%` | 112.27 us | 91.32
us | -18.7% (1.23x faster) |
| `utf8view/shared_prefix/pfx=8/list=16/match=0%` | 57.54 us | 32.07 us
| -44.3% (1.79x faster) |
| `utf8view/shared_prefix/pfx=8/list=16/match=50%` | 100.47 us | 82.69
us | -17.7% (1.21x faster) |
| `utf8view/short_8b/list=16/match=0%` | 44.03 us | 21.60 us | -50.9%
(2.04x faster) |
| `utf8view/short_8b/list=16/match=50%` | 72.92 us | 49.10 us | -32.7%
(1.49x faster) |
| `utf8view/short_8b/list=256/match=0%` | 44.34 us | 21.71 us | -51.0%
(2.04x faster) |
| `utf8view/short_8b/list=256/match=50%` | 72.43 us | 51.58 us | -28.8%
(1.40x faster) |
| `utf8view/short_8b/list=4/match=0%` | 41.54 us | 20.52 us | -50.6%
(2.02x faster) |
| `utf8view/short_8b/list=4/match=50%` | 72.50 us | 48.46 us | -33.2%
(1.50x faster) |
| `utf8view/short_8b/list=64/match=0%` | 45.55 us | 21.85 us | -52.0%
(2.08x faster) |
| `utf8view/short_8b/list=64/match=50%` | 73.14 us | 50.92 us | -30.4%
(1.44x faster) |
</details>
<!-- codex-benchmark-end -->1 parent 421890e commit d2d9b12
3 files changed
Lines changed: 194 additions & 86 deletions
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
38 | 38 | | |
39 | 39 | | |
40 | 40 | | |
| 41 | + | |
41 | 42 | | |
42 | 43 | | |
43 | 44 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
23 | 23 | | |
24 | 24 | | |
25 | 25 | | |
26 | | - | |
27 | 26 | | |
28 | 27 | | |
29 | | - | |
| 28 | + | |
30 | 29 | | |
| 30 | + | |
31 | 31 | | |
32 | 32 | | |
33 | 33 | | |
34 | 34 | | |
35 | 35 | | |
36 | 36 | | |
37 | 37 | | |
38 | | - | |
| 38 | + | |
| 39 | + | |
| 40 | + | |
| 41 | + | |
| 42 | + | |
| 43 | + | |
| 44 | + | |
| 45 | + | |
39 | 46 | | |
40 | | - | |
41 | | - | |
42 | | - | |
| 47 | + | |
| 48 | + | |
| 49 | + | |
| 50 | + | |
| 51 | + | |
| 52 | + | |
| 53 | + | |
| 54 | + | |
| 55 | + | |
| 56 | + | |
| 57 | + | |
| 58 | + | |
| 59 | + | |
| 60 | + | |
| 61 | + | |
| 62 | + | |
| 63 | + | |
| 64 | + | |
| 65 | + | |
| 66 | + | |
| 67 | + | |
| 68 | + | |
| 69 | + | |
| 70 | + | |
| 71 | + | |
| 72 | + | |
| 73 | + | |
| 74 | + | |
| 75 | + | |
| 76 | + | |
| 77 | + | |
| 78 | + | |
| 79 | + | |
| 80 | + | |
| 81 | + | |
| 82 | + | |
| 83 | + | |
| 84 | + | |
| 85 | + | |
| 86 | + | |
| 87 | + | |
| 88 | + | |
| 89 | + | |
| 90 | + | |
| 91 | + | |
| 92 | + | |
| 93 | + | |
| 94 | + | |
| 95 | + | |
| 96 | + | |
| 97 | + | |
| 98 | + | |
| 99 | + | |
| 100 | + | |
| 101 | + | |
| 102 | + | |
| 103 | + | |
| 104 | + | |
| 105 | + | |
| 106 | + | |
| 107 | + | |
| 108 | + | |
| 109 | + | |
| 110 | + | |
| 111 | + | |
| 112 | + | |
| 113 | + | |
| 114 | + | |
| 115 | + | |
| 116 | + | |
| 117 | + | |
| 118 | + | |
| 119 | + | |
| 120 | + | |
| 121 | + | |
| 122 | + | |
| 123 | + | |
43 | 124 | | |
44 | 125 | | |
45 | 126 | | |
| |||
76 | 157 | | |
77 | 158 | | |
78 | 159 | | |
79 | | - | |
80 | | - | |
81 | | - | |
82 | | - | |
83 | | - | |
84 | | - | |
85 | | - | |
86 | | - | |
87 | | - | |
88 | | - | |
89 | | - | |
90 | | - | |
91 | | - | |
92 | | - | |
93 | | - | |
94 | | - | |
95 | | - | |
96 | | - | |
97 | | - | |
98 | | - | |
99 | | - | |
100 | | - | |
101 | | - | |
102 | | - | |
103 | | - | |
104 | | - | |
105 | | - | |
106 | | - | |
107 | | - | |
108 | | - | |
109 | | - | |
110 | | - | |
111 | | - | |
112 | | - | |
113 | | - | |
114 | | - | |
115 | | - | |
116 | | - | |
117 | | - | |
118 | | - | |
119 | | - | |
120 | | - | |
121 | | - | |
122 | | - | |
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 | | - | |
| 160 | + | |
159 | 161 | | |
160 | 162 | | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
| 1 | + | |
| 2 | + | |
| 3 | + | |
| 4 | + | |
| 5 | + | |
| 6 | + | |
| 7 | + | |
| 8 | + | |
| 9 | + | |
| 10 | + | |
| 11 | + | |
| 12 | + | |
| 13 | + | |
| 14 | + | |
| 15 | + | |
| 16 | + | |
| 17 | + | |
| 18 | + | |
| 19 | + | |
| 20 | + | |
| 21 | + | |
| 22 | + | |
| 23 | + | |
| 24 | + | |
| 25 | + | |
| 26 | + | |
| 27 | + | |
| 28 | + | |
| 29 | + | |
| 30 | + | |
| 31 | + | |
| 32 | + | |
| 33 | + | |
| 34 | + | |
| 35 | + | |
| 36 | + | |
| 37 | + | |
| 38 | + | |
| 39 | + | |
| 40 | + | |
| 41 | + | |
| 42 | + | |
| 43 | + | |
| 44 | + | |
| 45 | + | |
| 46 | + | |
| 47 | + | |
| 48 | + | |
| 49 | + | |
| 50 | + | |
| 51 | + | |
| 52 | + | |
| 53 | + | |
| 54 | + | |
| 55 | + | |
| 56 | + | |
| 57 | + | |
| 58 | + | |
| 59 | + | |
| 60 | + | |
| 61 | + | |
| 62 | + | |
| 63 | + | |
| 64 | + | |
| 65 | + | |
| 66 | + | |
| 67 | + | |
| 68 | + | |
| 69 | + | |
| 70 | + | |
| 71 | + | |
| 72 | + | |
| 73 | + | |
| 74 | + | |
| 75 | + | |
| 76 | + | |
| 77 | + | |
| 78 | + | |
| 79 | + | |
| 80 | + | |
| 81 | + | |
| 82 | + | |
| 83 | + | |
| 84 | + | |
| 85 | + | |
| 86 | + | |
| 87 | + | |
| 88 | + | |
| 89 | + | |
| 90 | + | |
| 91 | + | |
| 92 | + | |
| 93 | + | |
| 94 | + | |
| 95 | + | |
| 96 | + | |
| 97 | + | |
| 98 | + | |
| 99 | + | |
| 100 | + | |
| 101 | + | |
| 102 | + | |
| 103 | + | |
| 104 | + | |
| 105 | + | |
0 commit comments