Skip to content

Commit 1271f00

Browse files
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/UnionDataTraitUtils.java‎

Lines changed: 576 additions & 0 deletions
Large diffs are not rendered by default.

‎fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalUnion.java‎

Lines changed: 2 additions & 72 deletions
Original file line numberDiff line numberDiff line change
@@ -23,6 +23,7 @@
2323
import org.apache.doris.nereids.properties.DataTrait;
2424
import org.apache.doris.nereids.properties.LogicalProperties;
2525
import org.apache.doris.nereids.properties.PhysicalProperties;
26+
import org.apache.doris.nereids.properties.UnionDataTraitUtils;
2627
import org.apache.doris.nereids.rules.expression.ExpressionRewriteContext;
2728
import org.apache.doris.nereids.trees.expressions.Expression;
2829
import org.apache.doris.nereids.trees.expressions.NamedExpression;
@@ -45,14 +46,9 @@
4546
import com.google.common.collect.ImmutableSet;
4647
import com.google.common.collect.Lists;
4748

48-
import java.util.ArrayList;
49-
import java.util.BitSet;
50-
import java.util.HashMap;
5149
import java.util.List;
52-
import java.util.Map;
5350
import java.util.Objects;
5451
import java.util.Optional;
55-
import java.util.Set;
5652

5753
/**
5854
* Logical Union.
@@ -290,75 +286,9 @@ public boolean hasUnboundExpression() {
290286
return super.hasUnboundExpression();
291287
}
292288

293-
private List<BitSet> mapSlotToIndex(Plan plan, List<Set<Slot>> equalSlotsList) {
294-
Map<Slot, Integer> slotToIndex = new HashMap<>();
295-
for (int i = 0; i < plan.getOutput().size(); i++) {
296-
slotToIndex.put(plan.getOutput().get(i), i);
297-
}
298-
List<BitSet> equalSlotIndicesList = new ArrayList<>();
299-
for (Set<Slot> equalSlots : equalSlotsList) {
300-
BitSet equalSlotIndices = new BitSet();
301-
for (Slot slot : equalSlots) {
302-
if (slotToIndex.containsKey(slot)) {
303-
equalSlotIndices.set(slotToIndex.get(slot));
304-
}
305-
}
306-
if (equalSlotIndices.cardinality() > 1) {
307-
equalSlotIndicesList.add(equalSlotIndices);
308-
}
309-
}
310-
return equalSlotIndicesList;
311-
}
312-
313289
@Override
314290
public void computeEqualSet(DataTrait.Builder builder) {
315-
if (children.isEmpty()) {
316-
return;
317-
}
318-
319-
// Get the list of equal slot sets and their corresponding index mappings for the first child
320-
List<Set<Slot>> childEqualSlotsList = child(0).getLogicalProperties()
321-
.getTrait().calAllEqualSet();
322-
List<BitSet> childEqualSlotsIndicesList = mapSlotToIndex(child(0), childEqualSlotsList);
323-
List<BitSet> unionEqualSlotIndicesList = new ArrayList<>(childEqualSlotsIndicesList);
324-
325-
// Traverse all children and find the equal sets that exist in all children
326-
for (int i = 1; i < children.size(); i++) {
327-
Plan child = children.get(i);
328-
329-
// Get the equal slot sets for the current child
330-
childEqualSlotsList = child.getLogicalProperties().getTrait().calAllEqualSet();
331-
332-
// Map slots to indices for the current child
333-
childEqualSlotsIndicesList = mapSlotToIndex(child, childEqualSlotsList);
334-
335-
// Only keep the equal pairs that exist in all children of the union
336-
// This is done by calculating the intersection of all children's equal slot indices
337-
for (BitSet unionEqualSlotIndices : unionEqualSlotIndicesList) {
338-
BitSet intersect = new BitSet();
339-
for (BitSet childEqualSlotIndices : childEqualSlotsIndicesList) {
340-
if (unionEqualSlotIndices.intersects(childEqualSlotIndices)) {
341-
intersect = childEqualSlotIndices;
342-
break;
343-
}
344-
}
345-
unionEqualSlotIndices.and(intersect);
346-
}
347-
}
348-
349-
// Build the functional dependencies for the output slots
350-
List<Slot> outputList = getOutput();
351-
for (BitSet equalSlotIndices : unionEqualSlotIndicesList) {
352-
if (equalSlotIndices.cardinality() <= 1) {
353-
continue;
354-
}
355-
int first = equalSlotIndices.nextSetBit(0);
356-
int next = equalSlotIndices.nextSetBit(first + 1);
357-
while (next > 0) {
358-
builder.addEqualPair(outputList.get(first), outputList.get(next));
359-
next = equalSlotIndices.nextSetBit(next + 1);
360-
}
361-
}
291+
UnionDataTraitUtils.computeEqualSet(this, this, builder);
362292
}
363293

364294
@Override

‎fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/physical/PhysicalUnion.java‎

Lines changed: 2 additions & 73 deletions
Original file line numberDiff line numberDiff line change
@@ -21,9 +21,9 @@
2121
import org.apache.doris.nereids.properties.DataTrait;
2222
import org.apache.doris.nereids.properties.LogicalProperties;
2323
import org.apache.doris.nereids.properties.PhysicalProperties;
24+
import org.apache.doris.nereids.properties.UnionDataTraitUtils;
2425
import org.apache.doris.nereids.trees.expressions.Expression;
2526
import org.apache.doris.nereids.trees.expressions.NamedExpression;
26-
import org.apache.doris.nereids.trees.expressions.Slot;
2727
import org.apache.doris.nereids.trees.expressions.SlotReference;
2828
import org.apache.doris.nereids.trees.plans.AbstractPlan;
2929
import org.apache.doris.nereids.trees.plans.Plan;
@@ -38,14 +38,9 @@
3838
import com.google.common.collect.ImmutableList;
3939
import com.google.common.collect.ImmutableSet;
4040

41-
import java.util.ArrayList;
42-
import java.util.BitSet;
43-
import java.util.HashMap;
4441
import java.util.List;
45-
import java.util.Map;
4642
import java.util.Objects;
4743
import java.util.Optional;
48-
import java.util.Set;
4944
import java.util.stream.Collectors;
5045

5146
/**
@@ -189,75 +184,9 @@ public void computeUniform(DataTrait.Builder builder) {
189184
// don't propagate uniform slots
190185
}
191186

192-
private List<BitSet> mapSlotToIndex(Plan plan, List<Set<Slot>> equalSlotsList) {
193-
Map<Slot, Integer> slotToIndex = new HashMap<>();
194-
for (int i = 0; i < plan.getOutput().size(); i++) {
195-
slotToIndex.put(plan.getOutput().get(i), i);
196-
}
197-
List<BitSet> equalSlotIndicesList = new ArrayList<>();
198-
for (Set<Slot> equalSlots : equalSlotsList) {
199-
BitSet equalSlotIndices = new BitSet();
200-
for (Slot slot : equalSlots) {
201-
if (slotToIndex.containsKey(slot)) {
202-
equalSlotIndices.set(slotToIndex.get(slot));
203-
}
204-
}
205-
if (equalSlotIndices.cardinality() > 1) {
206-
equalSlotIndicesList.add(equalSlotIndices);
207-
}
208-
}
209-
return equalSlotIndicesList;
210-
}
211-
212187
@Override
213188
public void computeEqualSet(DataTrait.Builder builder) {
214-
if (children.isEmpty()) {
215-
return;
216-
}
217-
218-
// Get the list of equal slot sets and their corresponding index mappings for the first child
219-
List<Set<Slot>> childEqualSlotsList = child(0).getLogicalProperties()
220-
.getTrait().calAllEqualSet();
221-
List<BitSet> childEqualSlotsIndicesList = mapSlotToIndex(child(0), childEqualSlotsList);
222-
List<BitSet> unionEqualSlotIndicesList = new ArrayList<>(childEqualSlotsIndicesList);
223-
224-
// Traverse all children and find the equal sets that exist in all children
225-
for (int i = 1; i < children.size(); i++) {
226-
Plan child = children.get(i);
227-
228-
// Get the equal slot sets for the current child
229-
childEqualSlotsList = child.getLogicalProperties().getTrait().calAllEqualSet();
230-
231-
// Map slots to indices for the current child
232-
childEqualSlotsIndicesList = mapSlotToIndex(child, childEqualSlotsList);
233-
234-
// Only keep the equal pairs that exist in all children of the union
235-
// This is done by calculating the intersection of all children's equal slot indices
236-
for (BitSet unionEqualSlotIndices : unionEqualSlotIndicesList) {
237-
BitSet intersect = new BitSet();
238-
for (BitSet childEqualSlotIndices : childEqualSlotsIndicesList) {
239-
if (unionEqualSlotIndices.intersects(childEqualSlotIndices)) {
240-
intersect = childEqualSlotIndices;
241-
break;
242-
}
243-
}
244-
unionEqualSlotIndices.and(intersect);
245-
}
246-
}
247-
248-
// Build the functional dependencies for the output slots
249-
List<Slot> outputList = getOutput();
250-
for (BitSet equalSlotIndices : unionEqualSlotIndicesList) {
251-
if (equalSlotIndices.cardinality() <= 1) {
252-
continue;
253-
}
254-
int first = equalSlotIndices.nextSetBit(0);
255-
int next = equalSlotIndices.nextSetBit(first + 1);
256-
while (next > 0) {
257-
builder.addEqualPair(outputList.get(first), outputList.get(next));
258-
next = equalSlotIndices.nextSetBit(next + 1);
259-
}
260-
}
189+
UnionDataTraitUtils.computeEqualSet(this, this, builder);
261190
}
262191

263192
@Override

‎fe/fe-core/src/test/java/org/apache/doris/nereids/properties/EqualSetTest.java‎

Lines changed: 139 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -18,6 +18,8 @@
1818
package org.apache.doris.nereids.properties;
1919

2020
import org.apache.doris.nereids.trees.plans.Plan;
21+
import org.apache.doris.nereids.trees.plans.logical.LogicalUnion;
22+
import org.apache.doris.nereids.trees.plans.physical.PhysicalUnion;
2123
import org.apache.doris.nereids.util.PlanChecker;
2224
import org.apache.doris.utframe.TestWithFeService;
2325

@@ -98,6 +100,143 @@ void testSetOp() {
98100
.isEmpty());
99101
}
100102

103+
@Test
104+
void testUnionEqualSetUsesRegularChildOutputMapping() {
105+
String sql = "select name, id, id2 from agg where id = id2 "
106+
+ "union all select name, id, id2 from agg where id = id2";
107+
LogicalUnion union = analyzeLogicalUnion(sql);
108+
Assertions.assertNotEquals(union.child(0).getOutput(), union.getRegularChildOutput(0),
109+
"the test must exercise an ordinal mapping that differs from child.getOutput()");
110+
assertUnionEqualPair(sql, union, 1, 2, true);
111+
assertUnionEqualPair(sql, union, 0, 1, false);
112+
}
113+
114+
@Test
115+
void testUnionEqualSetChecksEveryConstantRow() {
116+
assertUnionEqualPair(
117+
"select id, id2 from agg where id = id2 "
118+
+ "union all select 1, 1 union all select 2, 2",
119+
0, 1, true);
120+
assertUnionEqualPair(
121+
"select id, id2 from agg where id = id2 "
122+
+ "union all select 1, 1 union all select 2, 3",
123+
0, 1, false);
124+
assertUnionEqualPair(
125+
"select id, id2 from agg where id = id2 "
126+
+ "union all select 1, 2 union all select 2, 1",
127+
0, 1, false);
128+
}
129+
130+
@Test
131+
void testConstantOnlyUnionEqualSetUsesNullSafeEquality() {
132+
assertUnionEqualPair(
133+
"select cast(1 as int), cast(1 as bigint) "
134+
+ "union all select cast(2 as int), cast(2 as bigint)",
135+
0, 1, true);
136+
assertUnionEqualPair(
137+
"select 1 + 1, cast(2 as bigint) "
138+
+ "union all select 2 * 2, cast(4 as bigint)",
139+
0, 1, true);
140+
assertUnionEqualPair(
141+
"select 1, 1 union all select 2, 3",
142+
0, 1, false);
143+
assertUnionEqualPair(
144+
"select cast(null as int), cast(null as bigint) union all select 1, 1",
145+
0, 1, true);
146+
assertUnionEqualPair(
147+
"select cast(null as int), cast(1 as bigint) union all select 1, 1",
148+
0, 1, false);
149+
}
150+
151+
@Test
152+
void testConstantOnlyUnionKeepsComparableSubsetOfMixedNullBucket() {
153+
String incompatibleNullFirst = "select cast(null as array<int>), cast(null as int), "
154+
+ "cast(null as bigint) union all select cast(null as array<int>), "
155+
+ "cast(1 as int), cast(1 as bigint)";
156+
assertUnionEqualPair(incompatibleNullFirst, 1, 2, true);
157+
assertUnionEqualPair(incompatibleNullFirst, 0, 1, false);
158+
159+
String compatibleValuesFirst = "select cast(null as array<int>), cast(1 as int), "
160+
+ "cast(1 as bigint) union all select cast(null as array<int>), "
161+
+ "cast(null as int), cast(null as bigint)";
162+
assertUnionEqualPair(compatibleValuesFirst, 1, 2, true);
163+
assertUnionEqualPair(compatibleValuesFirst, 0, 1, false);
164+
}
165+
166+
@Test
167+
void testWideConstantUnionReusesComparisonProofs() {
168+
int columnCount = 256;
169+
StringBuilder sql = new StringBuilder("select ");
170+
appendNullIntColumns(sql, columnCount);
171+
sql.append(" union all select ");
172+
appendNullIntColumns(sql, columnCount);
173+
174+
LogicalUnion union = analyzeLogicalUnion(sql.toString());
175+
Assertions.assertTrue(union.getLogicalProperties().getTrait().isNullSafeEqual(
176+
union.getOutput().get(0), union.getOutput().get(columnCount - 1)));
177+
}
178+
179+
private void appendNullIntColumns(StringBuilder sql, int columnCount) {
180+
for (int column = 0; column < columnCount; column++) {
181+
if (column > 0) {
182+
sql.append(", ");
183+
}
184+
sql.append("cast(null as int)");
185+
}
186+
}
187+
188+
private void assertUnionEqualPair(String sql, int leftIndex, int rightIndex, boolean expected) {
189+
assertUnionEqualPair(sql, analyzeLogicalUnion(sql), leftIndex, rightIndex, expected);
190+
}
191+
192+
private void assertUnionEqualPair(String sql, LogicalUnion logicalUnion,
193+
int leftIndex, int rightIndex, boolean expected) {
194+
Assertions.assertEquals(expected, logicalUnion.getLogicalProperties().getTrait().isNullSafeEqual(
195+
logicalUnion.getOutput().get(leftIndex), logicalUnion.getOutput().get(rightIndex)));
196+
197+
Plan physicalPlan = PlanChecker.from(connectContext).analyze(sql).rewrite().implement().getPhysicalPlan();
198+
PhysicalUnion physicalUnion = findPhysicalUnion(physicalPlan);
199+
Assertions.assertNotNull(physicalUnion, "expected a PhysicalUnion in: " + physicalPlan.treeString());
200+
DataTrait.Builder builder = new DataTrait.Builder();
201+
physicalUnion.computeEqualSet(builder);
202+
DataTrait physicalTrait = builder.build();
203+
Assertions.assertEquals(expected, physicalTrait.isNullSafeEqual(
204+
physicalUnion.getOutput().get(leftIndex), physicalUnion.getOutput().get(rightIndex)));
205+
}
206+
207+
private LogicalUnion analyzeLogicalUnion(String sql) {
208+
Plan rewritten = PlanChecker.from(connectContext).analyze(sql).rewrite().getPlan();
209+
LogicalUnion logicalUnion = findLogicalUnion(rewritten);
210+
Assertions.assertNotNull(logicalUnion, "expected a LogicalUnion in: " + rewritten.treeString());
211+
return logicalUnion;
212+
}
213+
214+
private LogicalUnion findLogicalUnion(Plan plan) {
215+
if (plan instanceof LogicalUnion) {
216+
return (LogicalUnion) plan;
217+
}
218+
for (Plan child : plan.children()) {
219+
LogicalUnion union = findLogicalUnion(child);
220+
if (union != null) {
221+
return union;
222+
}
223+
}
224+
return null;
225+
}
226+
227+
private PhysicalUnion findPhysicalUnion(Plan plan) {
228+
if (plan instanceof PhysicalUnion) {
229+
return (PhysicalUnion) plan;
230+
}
231+
for (Plan child : plan.children()) {
232+
PhysicalUnion union = findPhysicalUnion(child);
233+
if (union != null) {
234+
return union;
235+
}
236+
}
237+
return null;
238+
}
239+
101240
@Test
102241
void testFilterHaving() {
103242
Plan plan = PlanChecker.from(connectContext)

‎fe/fe-core/src/test/java/org/apache/doris/nereids/rules/rewrite/EliminateOrderByKeyTest.java‎

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -213,6 +213,42 @@ void testWindowUniform() {
213213
.getOrderKeys().isEmpty()));
214214
}
215215

216+
@Test
217+
void testWindowUnionNullSafeEquality() {
218+
PlanChecker.from(connectContext)
219+
.analyze("select rank() over(order by a, b) from ("
220+
+ "select cast(null as int) a, cast(null as bigint) b "
221+
+ "union all select cast(1 as int), cast(1 as bigint)) t")
222+
.rewrite()
223+
.printlnTree()
224+
.matches(logicalWindow()
225+
.when(window -> ((WindowExpression) window.getWindowExpressions().get(0).child(0))
226+
.getOrderKeys().size() == 1));
227+
}
228+
229+
@Test
230+
void testWindowUnionMixedNullTypesIndependentOfArmOrder() {
231+
PlanChecker.from(connectContext)
232+
.analyze("select a, rank() over(order by b, c) from ("
233+
+ "select cast(null as array<int>) a, cast(null as int) b, cast(null as bigint) c "
234+
+ "union all select cast(null as array<int>), cast(1 as int), cast(1 as bigint)) t")
235+
.rewrite()
236+
.printlnTree()
237+
.matches(logicalWindow()
238+
.when(window -> ((WindowExpression) window.getWindowExpressions().get(0).child(0))
239+
.getOrderKeys().size() == 1));
240+
241+
PlanChecker.from(connectContext)
242+
.analyze("select a, rank() over(order by b, c) from ("
243+
+ "select cast(null as array<int>) a, cast(1 as int) b, cast(1 as bigint) c "
244+
+ "union all select cast(null as array<int>), cast(null as int), cast(null as bigint)) t")
245+
.rewrite()
246+
.printlnTree()
247+
.matches(logicalWindow()
248+
.when(window -> ((WindowExpression) window.getWindowExpressions().get(0).child(0))
249+
.getOrderKeys().size() == 1));
250+
}
251+
216252
@Test
217253
void testWindowPartitionKey() {
218254
// an order key that repeats the window's own partition key is constant within each partition,

0 commit comments

Comments
 (0)