Repository navigation
Commit 6357574
perf: dedupe collapsed hash join IN lists and add combined bounds
The per-partition InList arrays hold one entry per build row, and the
collapsed union concatenated them. On TPC-DS SF1 with 12 partitions, Q65
pushed 54,000 entries for 6 distinct keys, and Q18 pushed 10,848 entries
for 1,178 distinct keys. The pruning code uses an IN list only up to
`max_in_list_size` (20) entries, so these filters gave no pruning term,
and the long lists made the statistics evaluation for each file range
slow.
The union is now deduplicated and sorted with the arrow row format before
the IN list is built. This works for single and struct (multi-column)
keys and dictionaries, keeps one NULL, and makes the list order
deterministic. The 1 MiB cap now applies to the deduplicated union.
The collapsed filter also gets one range per key column,
`col >= min AND col <= max`, from the combined bounds of all non-empty
partitions, before the IN list. Every key in the union is inside this
range, so the filter stays exact, and the pruning code can use the range
when the list has more than `max_in_list_size` entries.
Co-Authored-By: Claude Opus 5.5 <[email protected]>1 parent 3eb7cf7 commit 6357574
4 files changed
Lines changed: 349 additions & 29 deletions
File tree
- datafusion
- core/tests/physical_optimizer
- physical-plan/src/joins/hash_join
- sqllogictest/test_files
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
1165 | 1165 | | |
1166 | 1166 | | |
1167 | 1167 | | |
1168 | | - | |
| 1168 | + | |
1169 | 1169 | | |
1170 | 1170 | | |
1171 | 1171 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
17 | 17 | | |
18 | 18 | | |
19 | 19 | | |
| 20 | + | |
20 | 21 | | |
21 | 22 | | |
22 | | - | |
| 23 | + | |
| 24 | + | |
23 | 25 | | |
| 26 | + | |
24 | 27 | | |
25 | 28 | | |
26 | 29 | | |
| |||
77 | 80 | | |
78 | 81 | | |
79 | 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 | + | |
80 | 125 | | |
81 | 126 | | |
82 | 127 | | |
| |||
155 | 200 | | |
156 | 201 | | |
157 | 202 | | |
| 203 | + | |
| 204 | + | |
| 205 | + | |
| 206 | + | |
| 207 | + | |
| 208 | + | |
| 209 | + | |
| 210 | + | |
| 211 | + | |
| 212 | + | |
| 213 | + | |
| 214 | + | |
| 215 | + | |
| 216 | + | |
| 217 | + | |
| 218 | + | |
| 219 | + | |
| 220 | + | |
| 221 | + | |
| 222 | + | |
| 223 | + | |
158 | 224 | | |
0 commit comments