Repository navigation
Commit b33a1c0
committed
perf, chore: Consolidate and optimize
`map[key]` (aka `get_field`) and `map_extract(map, key)` collectively
had three ways to lookup keys in a map:
(1): `get_field` used a per-batch `eq` kernel for scalar keys. This is
efficient for maps with many entries where `key` is not found, but
slower for maps in which the key can be found quickly (because `eq`
does not allow early-stopping). On my local machine, `eq` only
beats a comparator-based approach if the latter required touching
more than 60% of the keys in a row.
(2): `get_field` used a comparator-based approach for nested keys.
(3): `map_extract` used a comparator-based approach for all keys.
Conceptually, these two functions only differ in how the result is
represented, so it makes sense to consolidate them. We can also adopt a
hybrid strategy that gets the best of the previous approaches for most
inputs:
* Start with a comparator-based approach.
* After the first row, remember the index at which the matching key was
found, and check that index first for subsequent rows. This takes
advantage of the observation that most map rows have their keys in
the same order.
* After 32 rows, check whether the comparator looked at more than 75% of
the entries in those rows. If it did, the early stopping that the
comparator approach allows is not useful and we switch to an `eq`
kernel for the remainder of the batch (as long as the map key is not a
nested type).
Add `datafusion_functions::utils::map_lookup`, which returns for each map
row the index of the first matching entry or null, and build both
functions on it with `take`. The lookup scans each row with a comparator,
which stops at the first match, and tries the position where the previous
row matched first, since rows in a batch usually share key order; a hit
then usually costs one comparison wherever the key sits. A miss has no
match to stop at, so every entry of the row is compared at the
comparator's higher per-comparison cost. After sampling 32 rows, if most
of them missed, the remaining entries are compared with one vectorized
`eq` instead, which does the same full comparison more cheaply. A lookup
key that differs from the map key type only in dictionary encoding is cast
rather than rejected.
`map_extract` now passes a scalar key through as a single row instead of
expanding it to the batch size. `map[key]` reports a mismatched key type
as an execution error instead of an Arrow comparison error, and a null map
row that still carries entries yields NULL, as it already did from
`map_extract`.
Closes apache#25083get_field and map_extract
1 parent d029ea1 commit b33a1c0
4 files changed
Lines changed: 469 additions & 212 deletions
File tree
- datafusion
- functions-nested/src
- functions/src
- core
- sqllogictest/test_files
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
17 | 17 | | |
18 | 18 | | |
19 | 19 | | |
20 | | - | |
21 | | - | |
22 | | - | |
23 | | - | |
| 20 | + | |
| 21 | + | |
24 | 22 | | |
25 | | - | |
| 23 | + | |
26 | 24 | | |
27 | | - | |
28 | 25 | | |
29 | 26 | | |
| 27 | + | |
30 | 28 | | |
31 | 29 | | |
32 | 30 | | |
33 | 31 | | |
| 32 | + | |
34 | 33 | | |
35 | 34 | | |
36 | 35 | | |
| |||
119 | 118 | | |
120 | 119 | | |
121 | 120 | | |
122 | | - | |
| 121 | + | |
| 122 | + | |
| 123 | + | |
| 124 | + | |
| 125 | + | |
123 | 126 | | |
124 | 127 | | |
125 | 128 | | |
| |||
149 | 152 | | |
150 | 153 | | |
151 | 154 | | |
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 | | - | |
| 155 | + | |
| 156 | + | |
| 157 | + | |
| 158 | + | |
| 159 | + | |
| 160 | + | |
| 161 | + | |
| 162 | + | |
| 163 | + | |
| 164 | + | |
| 165 | + | |
197 | 166 | | |
198 | | - | |
199 | | - | |
200 | | - | |
| 167 | + | |
| 168 | + | |
| 169 | + | |
201 | 170 | | |
202 | 171 | | |
203 | 172 | | |
204 | 173 | | |
205 | 174 | | |
206 | 175 | | |
207 | | - | |
208 | | - | |
209 | | - | |
210 | | - | |
211 | | - | |
212 | | - | |
213 | | - | |
214 | | - | |
215 | | - | |
216 | | - | |
217 | | - | |
218 | | - | |
219 | | - | |
220 | | - | |
221 | | - | |
| 176 | + | |
| 177 | + | |
| 178 | + | |
| 179 | + | |
| 180 | + | |
| 181 | + | |
222 | 182 | | |
223 | | - | |
224 | | - | |
225 | 183 | | |
226 | 184 | | |
227 | 185 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
17 | 17 | | |
18 | 18 | | |
19 | 19 | | |
20 | | - | |
21 | | - | |
22 | | - | |
23 | | - | |
24 | | - | |
| 20 | + | |
| 21 | + | |
25 | 22 | | |
26 | 23 | | |
27 | 24 | | |
| |||
38 | 35 | | |
39 | 36 | | |
40 | 37 | | |
| 38 | + | |
41 | 39 | | |
42 | 40 | | |
43 | 41 | | |
| |||
99 | 97 | | |
100 | 98 | | |
101 | 99 | | |
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 | | - | |
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 | 100 | | |
186 | 101 | | |
187 | 102 | | |
| |||
209 | 124 | | |
210 | 125 | | |
211 | 126 | | |
212 | | - | |
213 | | - | |
214 | | - | |
215 | | - | |
216 | | - | |
217 | | - | |
218 | | - | |
219 | | - | |
| 127 | + | |
| 128 | + | |
| 129 | + | |
| 130 | + | |
| 131 | + | |
220 | 132 | | |
221 | 133 | | |
222 | 134 | | |
| |||
656 | 568 | | |
657 | 569 | | |
658 | 570 | | |
659 | | - | |
660 | | - | |
661 | | - | |
662 | | - | |
663 | | - | |
| 571 | + | |
| 572 | + | |
664 | 573 | | |
665 | 574 | | |
666 | 575 | | |
| |||
698 | 607 | | |
699 | 608 | | |
700 | 609 | | |
701 | | - | |
702 | | - | |
703 | | - | |
704 | | - | |
705 | | - | |
706 | | - | |
707 | | - | |
708 | | - | |
709 | | - | |
710 | | - | |
711 | | - | |
712 | | - | |
713 | | - | |
714 | | - | |
715 | | - | |
716 | | - | |
717 | | - | |
718 | | - | |
719 | | - | |
720 | | - | |
721 | | - | |
722 | | - | |
723 | | - | |
724 | | - | |
725 | | - | |
726 | | - | |
727 | | - | |
728 | | - | |
729 | | - | |
730 | | - | |
731 | | - | |
732 | | - | |
733 | | - | |
734 | | - | |
735 | | - | |
736 | 610 | | |
737 | 611 | | |
738 | 612 | | |
| |||
0 commit comments