morrySnow commented on code in PR #62980:
URL: https://github.com/apache/doris/pull/62980#discussion_r3535235969
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/properties/DataTrait.java:
##########
@@ -404,81 +418,115 @@ public void replaceEqualSetBy(Map<Slot, Slot>
replaceMap) {
public void replaceFuncDepsBy(Map<Slot, Slot> replaceMap) {
fdDgBuilder.replace(replaceMap);
}
+
+ /** replace uniqueSet.slotSets slot to root in equalSets */
+ public void normalizeUniqueSetsToEqualSetRoot() {
+ ImmutableEqualSet<Slot> equalSet = equalSetBuilder.build();
+ Set<ImmutableSet<Slot>> newSlotSets = new HashSet<>();
+ for (ImmutableSet<Slot> uniqueSet :
uniqueSet.combinedUniqueSlotSet) {
+ ImmutableSet.Builder<Slot> roots = ImmutableSet.builder();
+ for (Slot slot : uniqueSet) {
+ Slot root = equalSet.getRoot(slot);
+ if (root != null) {
+ roots.add(root);
+ } else {
+ roots.add(slot);
+ }
+ }
+ newSlotSets.add(roots.build());
+ }
+ uniqueSet.combinedUniqueSlotSet = newSlotSets;
+ }
}
static class UniqueDescription {
- Set<Slot> slots;
- Set<ImmutableSet<Slot>> slotSets;
+ Set<Slot> uniqueSlots;
+ Set<ImmutableSet<Slot>> combinedUniqueSlotSet;
UniqueDescription() {
- slots = new HashSet<>();
- slotSets = new HashSet<>();
+ uniqueSlots = new HashSet<>();
+ combinedUniqueSlotSet = new HashSet<>();
}
UniqueDescription(UniqueDescription o) {
- this.slots = new HashSet<>(o.slots);
- this.slotSets = new HashSet<>(o.slotSets);
+ this.uniqueSlots = new HashSet<>(o.uniqueSlots);
+ this.combinedUniqueSlotSet = new
HashSet<>(o.combinedUniqueSlotSet);
}
UniqueDescription(Set<Slot> slots, Set<ImmutableSet<Slot>> slotSets) {
- this.slots = slots;
- this.slotSets = slotSets;
+ this.uniqueSlots = slots;
+ this.combinedUniqueSlotSet = slotSets;
}
public boolean contains(Slot slot) {
- return slots.contains(slot);
+ return uniqueSlots.contains(slot);
}
public boolean contains(Set<Slot> slotSet) {
if (slotSet.size() == 1) {
- return slots.contains(slotSet.iterator().next());
+ return uniqueSlots.contains(slotSet.iterator().next());
}
- return slotSets.contains(ImmutableSet.copyOf(slotSet));
+ return
combinedUniqueSlotSet.contains(ImmutableSet.copyOf(slotSet));
}
public boolean containsAnySub(Set<Slot> slotSet) {
- return slotSet.stream().anyMatch(s -> slots.contains(s))
- || slotSets.stream().anyMatch(slotSet::containsAll);
+ return slotSet.stream().anyMatch(s -> uniqueSlots.contains(s))
+ ||
combinedUniqueSlotSet.stream().anyMatch(slotSet::containsAll);
}
- public void removeNotContain(Set<Slot> slotSet) {
- if (!slotSet.isEmpty()) {
- Set<Slot> newSlots =
Sets.newLinkedHashSetWithExpectedSize(slots.size());
- for (Slot slot : slots) {
- if (slotSet.contains(slot)) {
+ public void removeNotContain(Set<Slot> outputSlots,
ImmutableEqualSet<Slot> equalSet) {
+ if (!outputSlots.isEmpty()) {
Review Comment:
```
if (outputSlots.isEmpty()) {
return;
}
```
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/properties/DataTrait.java:
##########
@@ -404,81 +418,115 @@ public void replaceEqualSetBy(Map<Slot, Slot>
replaceMap) {
public void replaceFuncDepsBy(Map<Slot, Slot> replaceMap) {
fdDgBuilder.replace(replaceMap);
}
+
+ /** replace uniqueSet.slotSets slot to root in equalSets */
+ public void normalizeUniqueSetsToEqualSetRoot() {
+ ImmutableEqualSet<Slot> equalSet = equalSetBuilder.build();
+ Set<ImmutableSet<Slot>> newSlotSets = new HashSet<>();
+ for (ImmutableSet<Slot> uniqueSet :
uniqueSet.combinedUniqueSlotSet) {
+ ImmutableSet.Builder<Slot> roots = ImmutableSet.builder();
+ for (Slot slot : uniqueSet) {
+ Slot root = equalSet.getRoot(slot);
+ if (root != null) {
+ roots.add(root);
+ } else {
+ roots.add(slot);
+ }
+ }
+ newSlotSets.add(roots.build());
+ }
+ uniqueSet.combinedUniqueSlotSet = newSlotSets;
+ }
}
static class UniqueDescription {
- Set<Slot> slots;
- Set<ImmutableSet<Slot>> slotSets;
+ Set<Slot> uniqueSlots;
+ Set<ImmutableSet<Slot>> combinedUniqueSlotSet;
UniqueDescription() {
- slots = new HashSet<>();
- slotSets = new HashSet<>();
+ uniqueSlots = new HashSet<>();
+ combinedUniqueSlotSet = new HashSet<>();
}
UniqueDescription(UniqueDescription o) {
- this.slots = new HashSet<>(o.slots);
- this.slotSets = new HashSet<>(o.slotSets);
+ this.uniqueSlots = new HashSet<>(o.uniqueSlots);
+ this.combinedUniqueSlotSet = new
HashSet<>(o.combinedUniqueSlotSet);
}
UniqueDescription(Set<Slot> slots, Set<ImmutableSet<Slot>> slotSets) {
- this.slots = slots;
- this.slotSets = slotSets;
+ this.uniqueSlots = slots;
+ this.combinedUniqueSlotSet = slotSets;
}
public boolean contains(Slot slot) {
- return slots.contains(slot);
+ return uniqueSlots.contains(slot);
}
public boolean contains(Set<Slot> slotSet) {
if (slotSet.size() == 1) {
- return slots.contains(slotSet.iterator().next());
+ return uniqueSlots.contains(slotSet.iterator().next());
}
- return slotSets.contains(ImmutableSet.copyOf(slotSet));
+ return
combinedUniqueSlotSet.contains(ImmutableSet.copyOf(slotSet));
}
public boolean containsAnySub(Set<Slot> slotSet) {
- return slotSet.stream().anyMatch(s -> slots.contains(s))
- || slotSets.stream().anyMatch(slotSet::containsAll);
+ return slotSet.stream().anyMatch(s -> uniqueSlots.contains(s))
+ ||
combinedUniqueSlotSet.stream().anyMatch(slotSet::containsAll);
}
- public void removeNotContain(Set<Slot> slotSet) {
- if (!slotSet.isEmpty()) {
- Set<Slot> newSlots =
Sets.newLinkedHashSetWithExpectedSize(slots.size());
- for (Slot slot : slots) {
- if (slotSet.contains(slot)) {
+ public void removeNotContain(Set<Slot> outputSlots,
ImmutableEqualSet<Slot> equalSet) {
+ if (!outputSlots.isEmpty()) {
+ Set<Slot> newSlots =
Sets.newLinkedHashSetWithExpectedSize(uniqueSlots.size());
+ for (Slot slot : uniqueSlots) {
+ if (outputSlots.contains(slot)) {
newSlots.add(slot);
}
}
- this.slots = newSlots;
-
- Set<ImmutableSet<Slot>> newSlotSets =
Sets.newLinkedHashSetWithExpectedSize(slots.size());
- for (ImmutableSet<Slot> set : slotSets) {
- if (slotSet.containsAll(set)) {
- newSlotSets.add(set);
+ this.uniqueSlots = newSlots;
+
+ Set<ImmutableSet<Slot>> newCombinedUniqueSlotSet =
Sets.newHashSetWithExpectedSize(uniqueSlots.size());
+ for (ImmutableSet<Slot> combinedUniqueSlots :
combinedUniqueSlotSet) {
+ ImmutableSet.Builder<Slot> builder =
ImmutableSet.builder();
+ boolean allCanFindReplacement = true;
+ for (Slot slot : combinedUniqueSlots) {
+ if (outputSlots.contains(slot)) {
+ builder.add(slot);
+ } else {
+ Set<Slot> equalSlots = equalSet.calEqualSet(slot);
+ Set<Slot> replaceSlots =
Sets.intersection(outputSlots, equalSlots);
+ if (!replaceSlots.isEmpty()) {
+ builder.add(replaceSlots.iterator().next());
+ } else {
+ allCanFindReplacement = false;
Review Comment:
break here
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalJoin.java:
##########
@@ -612,6 +613,37 @@ public void computeUnique(Builder builder) {
} else if (joinType.isRightSemiOrAntiJoin() ||
joinType.isAsofRightJoin()) {
builder.addUniqueSlot(right().getLogicalProperties().getTrait());
}
+
+ // Union propagation:
+ // For INNER / CROSS / LEFT_OUTER / RIGHT_OUTER / FULL_OUTER joins, if
the left side
+ // is unique on U_L and the right side is unique on U_R, then the join
output is unique
+ // on U_L ∪ U_R.
+ // Proof sketch (INNER): two output rows (l_a, r_a) and (l_b, r_b)
agreeing on U_L ∪ U_R
+ // must agree on U_L (so l_a = l_b by L's uniqueness on U_L) and on
U_R (so r_a = r_b),
+ // hence the two rows are identical.
+ if (joinType.isInnerJoin() || joinType.isCrossJoin()
+ || joinType.isLeftOuterJoin() || joinType.isRightOuterJoin()
+ || joinType.isFullOuterJoin()) {
+ List<Set<Slot>> leftUniqueSets =
+
left().getLogicalProperties().getTrait().getAllUniqueSets();
+ List<Set<Slot>> rightUniqueSets =
+
right().getLogicalProperties().getTrait().getAllUniqueSets();
+ if (!leftUniqueSets.isEmpty() && !rightUniqueSets.isEmpty()) {
+ int count = 0;
+ outer:
+ for (Set<Slot> leftUnique : leftUniqueSets) {
+ for (Set<Slot> rightUnique : rightUniqueSets) {
+ if (count >= DataTrait.UNIQUE_UNION_LIMIT) {
+ break outer;
+ }
+ builder.addUniqueSlot(ImmutableSet.<Slot>builder()
+
.addAll(leftUnique).addAll(rightUnique).build());
+ count++;
Review Comment:
move break here
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
