Repository navigation
Commit 1271f00
authored
[fix](rbo) Guard union equal-set propagation (#67886)
## Problem
`UNION ALL` could publish output-column equality that does not hold for
every row. Downstream rules may then remove a required window ordering
key and change `RANK()` results.
Two forms reproduce the problem:
1. Regular children project columns in a different order from their
internal output. With child filters proving `a = b`, a union that
projects `(c, a, b)` can incorrectly map that equality to `(c, a)` and
remove `a` from `ORDER BY c, a`.
2. A regular child proves `a = b`, but constant rows such as `(1, 2)`
and `(2, 1)` do not. The union can still claim the output columns are
equal and remove `b` from `ORDER BY a, b`.
## Root cause
Logical and physical unions independently mapped child equality sets
through `child.getOutput()` positions. The authoritative union ordinal
mapping is `regularChildrenOutputs`, which can have a different order.
The derivation also considered only regular children and ignored every
constant row carried by the union.
## Reproduction
Create rows `(1, 1, 10)`, `(2, 2, 10)`, and `(1, 1, 20)`, duplicate a
filtered `(c, a, b)` child with `UNION ALL`, and compute `RANK() OVER
(ORDER BY c, a)`. The two rows with `(c, a) = (10, 2)` must have rank 3.
Separately, union filtered table rows satisfying `a = b` with constant
rows `(1, 2)` and `(2, 1)`, then compute `RANK() OVER (ORDER BY a, b)`.
The four ordered pairs must receive ranks 1, 2, 3, and 4.
## Fix
- Share one equal-set derivation between logical and physical unions.
- Validate and use each regular child's explicit union-output mapping.
- Intersect child equality classes by per-ordinal class signatures,
avoiding pairwise quadratic candidate generation.
- Refine candidates against every constant row after SQL comparison
coercion and constant folding.
- Accept only a folded `TRUE`; `NULL`, unsupported coercion,
non-foldable expressions, and malformed mappings conservatively provide
no equality proof.
- Build each surviving equivalence class with linear star edges.1 parent 249c1ba commit 1271f00
7 files changed
Lines changed: 904 additions & 145 deletions
File tree
- fe/fe-core/src
- main/java/org/apache/doris/nereids
- properties
- trees/plans
- logical
- physical
- test/java/org/apache/doris/nereids
- properties
- rules/rewrite
- regression-test
- data/nereids_rules_p0/union_equal_set
- suites/nereids_rules_p0/union_equal_set
Large diffs are not rendered by default.
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
23 | 23 | | |
24 | 24 | | |
25 | 25 | | |
| 26 | + | |
26 | 27 | | |
27 | 28 | | |
28 | 29 | | |
| |||
45 | 46 | | |
46 | 47 | | |
47 | 48 | | |
48 | | - | |
49 | | - | |
50 | | - | |
51 | 49 | | |
52 | | - | |
53 | 50 | | |
54 | 51 | | |
55 | | - | |
56 | 52 | | |
57 | 53 | | |
58 | 54 | | |
| |||
290 | 286 | | |
291 | 287 | | |
292 | 288 | | |
293 | | - | |
294 | | - | |
295 | | - | |
296 | | - | |
297 | | - | |
298 | | - | |
299 | | - | |
300 | | - | |
301 | | - | |
302 | | - | |
303 | | - | |
304 | | - | |
305 | | - | |
306 | | - | |
307 | | - | |
308 | | - | |
309 | | - | |
310 | | - | |
311 | | - | |
312 | | - | |
313 | 289 | | |
314 | 290 | | |
315 | | - | |
316 | | - | |
317 | | - | |
318 | | - | |
319 | | - | |
320 | | - | |
321 | | - | |
322 | | - | |
323 | | - | |
324 | | - | |
325 | | - | |
326 | | - | |
327 | | - | |
328 | | - | |
329 | | - | |
330 | | - | |
331 | | - | |
332 | | - | |
333 | | - | |
334 | | - | |
335 | | - | |
336 | | - | |
337 | | - | |
338 | | - | |
339 | | - | |
340 | | - | |
341 | | - | |
342 | | - | |
343 | | - | |
344 | | - | |
345 | | - | |
346 | | - | |
347 | | - | |
348 | | - | |
349 | | - | |
350 | | - | |
351 | | - | |
352 | | - | |
353 | | - | |
354 | | - | |
355 | | - | |
356 | | - | |
357 | | - | |
358 | | - | |
359 | | - | |
360 | | - | |
361 | | - | |
| 291 | + | |
362 | 292 | | |
363 | 293 | | |
364 | 294 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
21 | 21 | | |
22 | 22 | | |
23 | 23 | | |
| 24 | + | |
24 | 25 | | |
25 | 26 | | |
26 | | - | |
27 | 27 | | |
28 | 28 | | |
29 | 29 | | |
| |||
38 | 38 | | |
39 | 39 | | |
40 | 40 | | |
41 | | - | |
42 | | - | |
43 | | - | |
44 | 41 | | |
45 | | - | |
46 | 42 | | |
47 | 43 | | |
48 | | - | |
49 | 44 | | |
50 | 45 | | |
51 | 46 | | |
| |||
189 | 184 | | |
190 | 185 | | |
191 | 186 | | |
192 | | - | |
193 | | - | |
194 | | - | |
195 | | - | |
196 | | - | |
197 | | - | |
198 | | - | |
199 | | - | |
200 | | - | |
201 | | - | |
202 | | - | |
203 | | - | |
204 | | - | |
205 | | - | |
206 | | - | |
207 | | - | |
208 | | - | |
209 | | - | |
210 | | - | |
211 | | - | |
212 | 187 | | |
213 | 188 | | |
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 | | - | |
254 | | - | |
255 | | - | |
256 | | - | |
257 | | - | |
258 | | - | |
259 | | - | |
260 | | - | |
| 189 | + | |
261 | 190 | | |
262 | 191 | | |
263 | 192 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
18 | 18 | | |
19 | 19 | | |
20 | 20 | | |
| 21 | + | |
| 22 | + | |
21 | 23 | | |
22 | 24 | | |
23 | 25 | | |
| |||
98 | 100 | | |
99 | 101 | | |
100 | 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 | + | |
| 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 | + | |
101 | 240 | | |
102 | 241 | | |
103 | 242 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
213 | 213 | | |
214 | 214 | | |
215 | 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 | + | |
216 | 252 | | |
217 | 253 | | |
218 | 254 | | |
| |||
0 commit comments