This is an automated email from the ASF dual-hosted git repository.
jakevin pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/doris.git
The following commit(s) were added to refs/heads/master by this push:
new 051ab7a9c6 [refactor](Nereids): refactor Join-Dependent Predicate
Duplication. (#17653)
051ab7a9c6 is described below
commit 051ab7a9c665d3c05a3f3b6ef6e0d4921b2b4f43
Author: jakevin <[email protected]>
AuthorDate: Fri Mar 10 22:19:45 2023 +0800
[refactor](Nereids): refactor Join-Dependent Predicate Duplication. (#17653)
---
.../rules/rewrite/logical/AdjustNullable.java | 2 +-
...xtractSingleTableExpressionFromDisjunction.java | 149 +++++++++------------
.../nereids/trees/plans/logical/LogicalFilter.java | 55 +++-----
...ctSingleTableExpressionFromDisjunctionTest.java | 4 +-
4 files changed, 81 insertions(+), 129 deletions(-)
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/logical/AdjustNullable.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/logical/AdjustNullable.java
index 42ebe1e2da..83f096586d 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/logical/AdjustNullable.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/logical/AdjustNullable.java
@@ -63,7 +63,7 @@ public class AdjustNullable implements RewriteRuleFactory {
RuleType.ADJUST_NULLABLE_ON_FILTER.build(logicalFilter().then(filter -> {
Map<ExprId, Slot> exprIdSlotMap =
collectChildrenOutputMap(filter);
Set<Expression> conjuncts =
updateExpressions(filter.getConjuncts(), exprIdSlotMap);
- return new LogicalFilter<>(conjuncts,
filter.isSingleTableExpressionExtracted(), filter.child());
+ return new LogicalFilter<>(conjuncts, filter.child());
})),
RuleType.ADJUST_NULLABLE_ON_GENERATE.build(logicalGenerate().then(generate -> {
Map<ExprId, Slot> exprIdSlotMap =
collectChildrenOutputMap(generate);
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/logical/ExtractSingleTableExpressionFromDisjunction.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/logical/ExtractSingleTableExpressionFromDisjunction.java
index 5bb029e035..c72d7b00c5 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/logical/ExtractSingleTableExpressionFromDisjunction.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/logical/ExtractSingleTableExpressionFromDisjunction.java
@@ -22,7 +22,6 @@ import org.apache.doris.nereids.rules.RuleType;
import org.apache.doris.nereids.rules.rewrite.OneRewriteRuleFactory;
import org.apache.doris.nereids.trees.expressions.Expression;
import org.apache.doris.nereids.trees.expressions.Slot;
-import org.apache.doris.nereids.trees.expressions.SlotReference;
import org.apache.doris.nereids.trees.plans.logical.LogicalFilter;
import org.apache.doris.nereids.util.ExpressionUtils;
@@ -35,109 +34,87 @@ import java.util.Set;
import java.util.stream.Collectors;
/**
+ * Paper: Quantifying TPC-H Choke Points and Their Optimizations
+ * 4.4 Join-Dependent Predicate Duplication
* Example:
- * (n1.n_name = 'FRANCE' and n2.n_name = 'GERMANY') or (n1.n_name = 'GERMANY'
and n2.n_name = 'FRANCE')
+ * Two queries, Q7 and Q19, include predicates that operate
+ * on multiple tables without being a join predicate. In Q17,
+ * (n1.name = ’NATION1’ AND n2.name = ’NATION2’) OR (n1.name = ’NATION2’ AND
n2.name = ’NATION1’)
* =>
* (n1.n_name = 'FRANCE' and n2.n_name = 'GERMANY') or (n1.n_name = 'GERMANY'
and n2.n_name = 'FRANCE')
* and (n1.n_name = 'FRANCE' or n1.n_name='GERMANY') and (n2.n_name='GERMANY'
or n2.n_name='FRANCE')
- *
- * (n1.n_name = 'FRANCE' or n1.n_name='GERMANY') is a logical redundant, but
it could be pushed down to scan(n1) to
- * reduce the number of scan output tuples.
- * For complete sql example, refer to tpch q7.
- *
==================================================================================================
- * <br/>
- * There are 2 cases, in which the redundant expressions are useless:
- * 1. filter(expr)-->XXX out join.
- * For example, for left join, the redundant expression for right side is not
useful, because we cannot push expression
- * down to right child. Refer to PushDownJoinOtherCondition Rule for push-down
cases.
- * But it is hard to detect this case, if the outer join is a descendant but
not child of the filter.
- * 2. filter(expr)
- * |-->upper-join
- * |-->bottom-join
- * +-->child
- * In current version, we do not extract redundant expression for bottom-join.
This redundancy is good for
- * upper-join (reduce the number of input tuple from bottom join), but it
becomes unuseful if we rotate the join tree.
- *
==================================================================================================
- *<br/>
+ * <p>
+ * new generated expr is redundant, but they could be pushed down to reduce
the cardinality of children output tuples.
+ * <p>
* Implementation note:
* 1. This rule should only be applied ONCE to avoid generate same redundant
expression.
- * 2. This version only generates redundant expressions, but not push them.
- * 3. A redundant expression only contains slots from a single table.
- * 4. This rule is applied after rules converting sub-query to join.
- * 5. Add a flag 'isRedundant' in Expression. It is true, if it is generated
by this rule.
- * 6. The useless redundant expression should be removed, if it cannot be
pushed down. We need a new rule
- * `RemoveRedundantExpression` to fulfill this purpose.
- * 7. In old optimizer, there is `InferFilterRule` generates redundancy
expressions. Its Nereid counterpart also need
+ * 2. A redundant expression only contains slots from a single table.
+ * 3. In old optimizer, there is `InferFilterRule` generates redundancy
expressions. Its Nereid counterpart also need
* `RemoveRedundantExpression`.
+ * <p>
+ * TODO: This rule just match filter, but it could be applied to inner/cross
join condition.
*/
public class ExtractSingleTableExpressionFromDisjunction extends
OneRewriteRuleFactory {
@Override
public Rule build() {
- return
logicalFilter().whenNot(LogicalFilter::isSingleTableExpressionExtracted).then(filter
-> {
- //filter = [(n1.n_name = 'FRANCE' and n2.n_name = 'GERMANY')
- // or (n1.n_name = 'GERMANY' and n2.n_name = 'FRANCE')]
- // and ...
- Set<Expression> conjuncts = filter.getConjuncts();
-
- List<Expression> redundants = Lists.newArrayList();
- for (Expression conjunct : conjuncts) {
- //conjunct=(n1.n_name = 'FRANCE' and n2.n_name = 'GERMANY')
- // or (n1.n_name = 'GERMANY' and n2.n_name = 'FRANCE')
- List<Expression> disjuncts =
ExpressionUtils.extractDisjunction(conjunct);
- //disjuncts={ (n1.n_name = 'FRANCE' and n2.n_name = 'GERMANY'),
- // (n1.n_name = 'GERMANY' and n2.n_name = 'FRANCE')}
- if (disjuncts.size() == 1) {
- continue;
- }
- //only check table in first disjunct.
- //In our example, qualifiers = { n1, n2 }
- Expression first = disjuncts.get(0);
- Set<String> qualifiers = first.getInputSlots()
- .stream()
- .map(SlotReference.class::cast)
- .map(this::getSlotQualifierAsString)
- .collect(Collectors.toSet());
- //try to extract
- for (String qualifier : qualifiers) {
- List<Expression> extractForAll = Lists.newArrayList();
- boolean success = true;
- for (Expression expr :
ExpressionUtils.extractDisjunction(conjunct)) {
- Optional<Expression> extracted =
extractSingleTableExpression(expr, qualifier);
- if (!extracted.isPresent()) {
- //extract failed
- success = false;
- break;
- } else {
- extractForAll.add(extracted.get());
- }
- }
- if (success) {
- redundants.add(ExpressionUtils.or(extractForAll));
- }
- }
+ return logicalFilter().then(filter -> {
+ List<Expression> dependentPredicates =
extractDependentConjuncts(filter.getConjuncts());
+ if (dependentPredicates.isEmpty()) {
+ return null;
}
- if (redundants.isEmpty()) {
- return new LogicalFilter<>(filter.getConjuncts(), true,
filter.child());
- } else {
- return new LogicalFilter<>(ImmutableSet.<Expression>builder()
- .addAll(filter.getConjuncts())
- .addAll(redundants).build(),
- true, filter.child());
+ Set<Expression> newPredicates = ImmutableSet.<Expression>builder()
+ .addAll(filter.getConjuncts())
+ .addAll(dependentPredicates).build();
+ if (newPredicates.size() == filter.getConjuncts().size()) {
+ return null;
}
+ return new LogicalFilter<>(newPredicates, filter.child());
}).toRule(RuleType.EXTRACT_SINGLE_TABLE_EXPRESSION_FROM_DISJUNCTION);
}
- private String getSlotQualifierAsString(SlotReference slotReference) {
- StringBuilder builder = new StringBuilder();
- for (String q : slotReference.getQualifier()) {
- builder.append(q).append('.');
+ private List<Expression> extractDependentConjuncts(Set<Expression>
conjuncts) {
+ List<Expression> dependentPredicates = Lists.newArrayList();
+ for (Expression conjunct : conjuncts) {
+ // conjunct=(n1.n_name = 'FRANCE' and n2.n_name = 'GERMANY')
+ // or (n1.n_name = 'GERMANY' and n2.n_name = 'FRANCE')
+ List<Expression> disjuncts =
ExpressionUtils.extractDisjunction(conjunct);
+ // disjuncts={ (n1.n_name = 'FRANCE' and n2.n_name = 'GERMANY'),
+ // (n1.n_name = 'GERMANY' and n2.n_name = 'FRANCE')}
+ if (disjuncts.size() == 1) {
+ continue;
+ }
+ // only check table in first disjunct.
+ // In our example, qualifiers = { n1, n2 }
+ Expression first = disjuncts.get(0);
+ Set<String> qualifiers = first.getInputSlots()
+ .stream()
+ .map(slot -> String.join(".", slot.getQualifier()))
+ .collect(Collectors.toSet());
+ // try to extract
+ for (String qualifier : qualifiers) {
+ List<Expression> extractForAll = Lists.newArrayList();
+ boolean success = true;
+ for (Expression expr :
ExpressionUtils.extractDisjunction(conjunct)) {
+ Optional<Expression> extracted =
extractSingleTableExpression(expr, qualifier);
+ if (!extracted.isPresent()) {
+ // extract failed
+ success = false;
+ break;
+ } else {
+ extractForAll.add(extracted.get());
+ }
+ }
+ if (success) {
+ dependentPredicates.add(ExpressionUtils.or(extractForAll));
+ }
+ }
}
- return builder.toString();
+ return dependentPredicates;
}
- //extract some conjucts from expr, all slots of the extracted conjunct
comes from the table referred by qualifier.
- //example: expr=(n1.n_name = 'FRANCE' and n2.n_name = 'GERMANY'),
qualifier="n1."
- //output: n1.n_name = 'FRANCE'
+ // extract some conjucts from expr, all slots of the extracted conjunct
comes from the table referred by qualifier.
+ // example: expr=(n1.n_name = 'FRANCE' and n2.n_name = 'GERMANY'),
qualifier="n1."
+ // output: n1.n_name = 'FRANCE'
private Optional<Expression> extractSingleTableExpression(Expression expr,
String qualifier) {
List<Expression> output = Lists.newArrayList();
List<Expression> conjuncts = ExpressionUtils.extractConjunction(expr);
@@ -156,7 +133,7 @@ public class ExtractSingleTableExpressionFromDisjunction
extends OneRewriteRuleF
private boolean isSingleTableExpression(Expression expr, String qualifier)
{
//TODO: cache getSlotQualifierAsString() result.
for (Slot slot : expr.getInputSlots()) {
- String slotQualifier = getSlotQualifierAsString((SlotReference)
slot);
+ String slotQualifier = String.join(".", slot.getQualifier());
if (!slotQualifier.equals(qualifier)) {
return false;
}
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalFilter.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalFilter.java
index 20a80ba614..cd533f63a9 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalFilter.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalFilter.java
@@ -47,24 +47,14 @@ public class LogicalFilter<CHILD_TYPE extends Plan> extends
LogicalUnary<CHILD_T
private final Set<Expression> conjuncts;
- private final boolean singleTableExpressionExtracted;
-
public LogicalFilter(Set<Expression> conjuncts, CHILD_TYPE child) {
- this(conjuncts, Optional.empty(), false, Optional.empty(), child);
- }
-
- public LogicalFilter(Set<Expression> conjuncts, boolean
singleTableExpressionExtracted,
- CHILD_TYPE child) {
- this(conjuncts, Optional.empty(), singleTableExpressionExtracted,
- Optional.empty(), child);
+ this(conjuncts, Optional.empty(), Optional.empty(), child);
}
- public LogicalFilter(Set<Expression> conjuncts, Optional<GroupExpression>
groupExpression,
- boolean singleTableExpressionExtracted,
+ private LogicalFilter(Set<Expression> conjuncts, Optional<GroupExpression>
groupExpression,
Optional<LogicalProperties> logicalProperties, CHILD_TYPE child) {
super(PlanType.LOGICAL_FILTER, groupExpression, logicalProperties,
child);
this.conjuncts = ImmutableSet.copyOf(Objects.requireNonNull(conjuncts,
"conjuncts can not be null"));
- this.singleTableExpressionExtracted = singleTableExpressionExtracted;
}
@Override
@@ -78,18 +68,13 @@ public class LogicalFilter<CHILD_TYPE extends Plan> extends
LogicalUnary<CHILD_T
@Override
public List<Plan> extraPlans() {
- if (conjuncts != null) {
- return conjuncts.stream().map(Expression::children)
- .flatMap(Collection::stream)
- .flatMap(m -> {
- if (m instanceof SubqueryExpr) {
- return Stream.of(new
LogicalSubQueryAlias<>(m.toSql(), ((SubqueryExpr) m).getQueryPlan()));
- } else {
- return new LogicalFilter<Plan>(ImmutableSet.of(m),
child()).extraPlans().stream();
- }
- }).collect(Collectors.toList());
- }
- return ImmutableList.of();
+ return
conjuncts.stream().map(Expression::children).flatMap(Collection::stream).flatMap(m
-> {
+ if (m instanceof SubqueryExpr) {
+ return Stream.of(new LogicalSubQueryAlias<>(m.toSql(),
((SubqueryExpr) m).getQueryPlan()));
+ } else {
+ return new LogicalFilter<Plan>(ImmutableSet.of(m),
child()).extraPlans().stream();
+ }
+ }).collect(Collectors.toList());
}
@Override
@@ -99,9 +84,7 @@ public class LogicalFilter<CHILD_TYPE extends Plan> extends
LogicalUnary<CHILD_T
@Override
public String toString() {
- return Utils.toSqlString("LogicalFilter",
- "predicates", getPredicate()
- );
+ return Utils.toSqlString("LogicalFilter", "predicates",
getPredicate());
}
@Override
@@ -113,13 +96,12 @@ public class LogicalFilter<CHILD_TYPE extends Plan>
extends LogicalUnary<CHILD_T
return false;
}
LogicalFilter that = (LogicalFilter) o;
- return conjuncts.equals(that.conjuncts)
- && singleTableExpressionExtracted ==
that.singleTableExpressionExtracted;
+ return conjuncts.equals(that.conjuncts);
}
@Override
public int hashCode() {
- return Objects.hash(conjuncts, singleTableExpressionExtracted);
+ return Objects.hash(conjuncts);
}
@Override
@@ -130,23 +112,16 @@ public class LogicalFilter<CHILD_TYPE extends Plan>
extends LogicalUnary<CHILD_T
@Override
public LogicalUnary<Plan> withChildren(List<Plan> children) {
Preconditions.checkArgument(children.size() == 1);
- return new LogicalFilter<>(conjuncts, singleTableExpressionExtracted,
children.get(0));
+ return new LogicalFilter<>(conjuncts, children.get(0));
}
@Override
public Plan withGroupExpression(Optional<GroupExpression> groupExpression)
{
- return new LogicalFilter<>(conjuncts, groupExpression,
singleTableExpressionExtracted,
- Optional.of(getLogicalProperties()), child());
+ return new LogicalFilter<>(conjuncts, groupExpression,
Optional.of(getLogicalProperties()), child());
}
@Override
public Plan withLogicalProperties(Optional<LogicalProperties>
logicalProperties) {
- return new LogicalFilter<>(conjuncts, Optional.empty(),
- singleTableExpressionExtracted,
- logicalProperties, child());
- }
-
- public boolean isSingleTableExpressionExtracted() {
- return singleTableExpressionExtracted;
+ return new LogicalFilter<>(conjuncts, Optional.empty(),
logicalProperties, child());
}
}
diff --git
a/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/rewrite/logical/ExtractSingleTableExpressionFromDisjunctionTest.java
b/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/rewrite/logical/ExtractSingleTableExpressionFromDisjunctionTest.java
index bfc7e1aaa2..6e03afaa33 100644
---
a/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/rewrite/logical/ExtractSingleTableExpressionFromDisjunctionTest.java
+++
b/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/rewrite/logical/ExtractSingleTableExpressionFromDisjunctionTest.java
@@ -83,14 +83,14 @@ public class
ExtractSingleTableExpressionFromDisjunctionTest implements MemoPatt
)
);
Plan join = new LogicalJoin<>(JoinType.CROSS_JOIN, student, course);
- LogicalFilter root = new LogicalFilter(ImmutableSet.of(expr), join);
+ LogicalFilter root = new LogicalFilter<>(ImmutableSet.of(expr), join);
PlanChecker.from(MemoTestUtils.createConnectContext(), root)
.applyTopDown(new
ExtractSingleTableExpressionFromDisjunction())
.matchesFromRoot(
logicalFilter()
.when(filter ->
verifySingleTableExpression1(filter.getConjuncts()))
);
- Assertions.assertTrue(studentGender != null);
+ Assertions.assertNotNull(studentGender);
}
private boolean verifySingleTableExpression1(Set<Expression> conjuncts) {
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
