Skip to content

Commit dfe888e

Browse files
authored
[opt](mtmv) Support window function rewrite when materialized view contains window function (#55066)
### What problem does this PR solve? Support window function rewrite when materialized view contains window function Such as mv def is as following: CREATE MATERIALIZED VIEW mv1 BUILD IMMEDIATE REFRESH COMPLETE ON MANUAL DISTRIBUTED BY RANDOM BUCKETS 2 PROPERTIES ('replication_num' = '1') AS select * from ( select o_orderkey, FIRST_VALUE(o_custkey) OVER ( PARTITION BY o_orderdate ORDER BY o_totalprice NULLS LAST RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW ) AS first_value, RANK() OVER ( PARTITION BY o_orderdate, o_orderstatus ORDER BY o_totalprice NULLS LAST RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW ) AS rank_value, LAG(l_extendedprice, 1, 0) over (partition by o_orderdate, l_shipdate order by l_quantity) AS lag_value from lineitem2 left join orders2 on l_orderkey = o_orderkey and l_shipdate = o_orderdate ) t where o_orderkey > 1; if query as following, this can use mv to represent query select * from ( select o_orderkey, FIRST_VALUE(o_custkey) OVER ( PARTITION BY o_orderdate ORDER BY o_totalprice NULLS LAST RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW ) AS first_value, RANK() OVER ( PARTITION BY o_orderdate, o_orderstatus ORDER BY o_totalprice NULLS LAST RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW ) AS rank_value, LAG(l_extendedprice, 1, 0) over (partition by o_orderdate, l_shipdate order by l_quantity) AS lag_value from lineitem2 left join orders2 on l_orderkey = o_orderkey and l_shipdate = o_orderdate ) t where o_orderkey > 2; explain result is as follwing: +----------------------------------------------------------------------------------------+ | Explain String(Nereids Planner) | +----------------------------------------------------------------------------------------+ | PLAN FRAGMENT 0 | | OUTPUT EXPRS: | | o_orderkey[#4] | | first_value[#5] | | rank_value[#6] | | lag_value[#7] | | PARTITION: RANDOM | | | | HAS_COLO_PLAN_NODE: false | | | | VRESULT SINK | | MYSQL_PROTOCAL | | | | 0:VOlapScanNode(445) | | TABLE: regression_test_nereids_rules_p0_mv_window.mv1(mv1), PREAGGREGATION: ON | | PREDICATES: (o_orderkey[#0] > 2) | | partitions=1/1 (mv1) | | tablets=2/2, tabletList=1755678381149,1755678381151 | | cardinality=1, avgRowSize=0.0, numNodes=1 | | pushAggOp=NONE | | final projections: o_orderkey[#0], first_value[#1], rank_value[#2], lag_value[#3] | | final project output tuple id: 1 | | | | | | ========== MATERIALIZATIONS ========== | | | | MaterializedView | | MaterializedViewRewriteSuccessAndChose: | | internal.regression_test_nereids_rules_p0_mv_window.mv1 chose | | | | MaterializedViewRewriteSuccessButNotChose: | | | | MaterializedViewRewriteFail: | | | | | | ========== STATISTICS ========== | | planed with unknown column statistics | +----------------------------------------------------------------------------------------+
1 parent a32376d commit dfe888e

28 files changed

Lines changed: 7064 additions & 68 deletions

‎fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/node/StructInfoNode.java‎

Lines changed: 64 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -19,6 +19,9 @@
1919

2020
import org.apache.doris.common.Pair;
2121
import org.apache.doris.nereids.jobs.joinorder.hypergraph.edge.Edge;
22+
import org.apache.doris.nereids.rules.exploration.mv.StructInfo;
23+
import org.apache.doris.nereids.rules.exploration.mv.StructInfo.PlanCheckContext;
24+
import org.apache.doris.nereids.rules.exploration.mv.StructInfo.PredicateCollectorContext;
2225
import org.apache.doris.nereids.trees.expressions.Expression;
2326
import org.apache.doris.nereids.trees.plans.GroupPlan;
2427
import org.apache.doris.nereids.trees.plans.Plan;
@@ -27,6 +30,7 @@
2730
import org.apache.doris.nereids.trees.plans.logical.LogicalCatalogRelation;
2831
import org.apache.doris.nereids.trees.plans.logical.LogicalFilter;
2932
import org.apache.doris.nereids.trees.plans.logical.LogicalProject;
33+
import org.apache.doris.nereids.trees.plans.logical.LogicalWindow;
3034
import org.apache.doris.nereids.trees.plans.visitor.DefaultPlanVisitor;
3135
import org.apache.doris.nereids.util.Utils;
3236

@@ -39,26 +43,42 @@
3943
import java.util.List;
4044
import java.util.Set;
4145
import java.util.stream.Collectors;
46+
import java.util.stream.Stream;
4247
import javax.annotation.Nullable;
4348

4449
/**
4550
* HyperGraph Node.
4651
*/
4752
public class StructInfoNode extends AbstractNode {
48-
private final List<Set<Expression>> expressions;
53+
private final Pair<List<Set<Expression>>, List<Set<Expression>>> expressions;
4954
private final Set<CatalogRelation> relationSet;
5055

56+
/**
57+
* the constructor of StructInfoNode
58+
*/
5159
public StructInfoNode(int index, Plan plan, List<Edge> edges) {
5260
super(extractPlan(plan), index, edges);
5361
relationSet = plan.collect(CatalogRelation.class::isInstance);
54-
expressions = collectExpressions(plan);
62+
// check the node pattern is valid
63+
PlanCheckContext checkContext = PlanCheckContext.of(ImmutableSet.of());
64+
Boolean checkResult = plan.accept(StructInfo.PLAN_PATTERN_CHECKER, checkContext);
65+
if (checkResult && !checkContext.isWindowUnderAggregate() && checkContext.getTopAggregateNum() <= 1
66+
&& checkContext.getTopWindowNum() <= 1) {
67+
expressions = collectExpressions(plan);
68+
} else {
69+
expressions = null;
70+
}
5571
}
5672

5773
public StructInfoNode(int index, Plan plan) {
5874
this(index, plan, new ArrayList<>());
5975
}
6076

61-
private @Nullable List<Set<Expression>> collectExpressions(Plan plan) {
77+
/**
78+
* The key of pair is the expression which could be moved around anywhere,
79+
* the value of pair is the expression which could not be moved around anywhere.
80+
* */
81+
private @Nullable Pair<List<Set<Expression>>, List<Set<Expression>>> collectExpressions(Plan plan) {
6282

6383
Pair<Boolean, Builder<Set<Expression>>> collector = Pair.of(true, ImmutableList.builder());
6484
plan.accept(new DefaultPlanVisitor<Void, Pair<Boolean, ImmutableList.Builder<Set<Expression>>>>() {
@@ -69,7 +89,6 @@ public Void visitLogicalAggregate(LogicalAggregate<? extends Plan> aggregate,
6989
return null;
7090
}
7191
collector.value().add(ImmutableSet.copyOf(aggregate.getExpressions()));
72-
collector.value().add(ImmutableSet.copyOf(((LogicalAggregate<?>) plan).getGroupByExpressions()));
7392
return super.visit(aggregate, collector);
7493
}
7594

@@ -93,6 +112,13 @@ public Void visitGroupPlan(GroupPlan groupPlan,
93112
return groupActualPlan.accept(this, collector);
94113
}
95114

115+
@Override
116+
public Void visitLogicalWindow(LogicalWindow<? extends Plan> window,
117+
Pair<Boolean, Builder<Set<Expression>>> context) {
118+
collector.value().add(ImmutableSet.copyOf(window.getActualWindowExpressions()));
119+
return super.visit(window, context);
120+
}
121+
96122
@Override
97123
public Void visit(Plan plan, Pair<Boolean, ImmutableList.Builder<Set<Expression>>> context) {
98124
if (!isValidNodePlan(plan)) {
@@ -102,24 +128,52 @@ public Void visit(Plan plan, Pair<Boolean, ImmutableList.Builder<Set<Expression>
102128
return super.visit(plan, context);
103129
}
104130
}, collector);
105-
return collector.key() ? collector.value().build() : null;
131+
132+
if (!collector.key()) {
133+
return null;
134+
}
135+
PredicateCollectorContext predicateCollectorContext = new PredicateCollectorContext();
136+
plan.accept(StructInfo.PREDICATE_COLLECTOR, predicateCollectorContext);
137+
collector.value().add(ImmutableSet.copyOf(predicateCollectorContext.getCouldPullUpPredicates()));
138+
if (predicateCollectorContext.getCouldNotPullUpPredicates().isEmpty()) {
139+
return Pair.of(collector.value().build(), ImmutableList.of());
140+
}
141+
return Pair.of(collector.value().build(),
142+
ImmutableList.of(predicateCollectorContext.getCouldNotPullUpPredicates()));
106143
}
107144

108145
private boolean isValidNodePlan(Plan plan) {
109146
return plan instanceof LogicalProject || plan instanceof LogicalAggregate
110-
|| plan instanceof LogicalFilter || plan instanceof LogicalCatalogRelation;
147+
|| plan instanceof LogicalFilter || plan instanceof LogicalCatalogRelation
148+
|| plan instanceof LogicalWindow;
111149
}
112150

113151
/**
114152
* get all expressions of nodes
115153
*/
116154
public @Nullable List<Expression> getExpressions() {
117-
return expressions == null ? null : expressions.stream()
118-
.flatMap(Collection::stream)
119-
.collect(Collectors.toList());
155+
if (expressions == null) {
156+
return null;
157+
}
158+
return Stream.concat(expressions.key().stream().flatMap(Collection::stream),
159+
expressions.value().stream().flatMap(Collection::stream)).collect(Collectors.toList());
160+
}
161+
162+
public @Nullable List<Expression> getCouldMoveExpressions() {
163+
if (expressions == null) {
164+
return null;
165+
}
166+
return expressions.key().stream().flatMap(Collection::stream).collect(Collectors.toList());
167+
}
168+
169+
public @Nullable List<Expression> getCouldNotMoveExpressions() {
170+
if (expressions == null) {
171+
return null;
172+
}
173+
return expressions.value().stream().flatMap(Collection::stream).collect(Collectors.toList());
120174
}
121175

122-
public @Nullable List<Set<Expression>> getExprSetList() {
176+
public @Nullable Pair<List<Set<Expression>>, List<Set<Expression>>> getExprSetList() {
123177
return expressions;
124178
}
125179

‎fe/fe-core/src/main/java/org/apache/doris/nereids/rules/RuleSet.java‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -47,6 +47,9 @@
4747
import org.apache.doris.nereids.rules.exploration.mv.MaterializedViewProjectFilterScanRule;
4848
import org.apache.doris.nereids.rules.exploration.mv.MaterializedViewProjectJoinRule;
4949
import org.apache.doris.nereids.rules.exploration.mv.MaterializedViewProjectScanRule;
50+
import org.apache.doris.nereids.rules.exploration.mv.MaterializedViewWindowAggregateRule;
51+
import org.apache.doris.nereids.rules.exploration.mv.MaterializedViewWindowJoinRule;
52+
import org.apache.doris.nereids.rules.exploration.mv.MaterializedViewWindowScanRule;
5053
import org.apache.doris.nereids.rules.expression.ExpressionNormalizationAndOptimization;
5154
import org.apache.doris.nereids.rules.implementation.AggregateStrategies;
5255
import org.apache.doris.nereids.rules.implementation.LogicalAssertNumRowsToPhysicalAssertNumRows;
@@ -270,6 +273,9 @@ public class RuleSet {
270273
.add(MaterializedViewProjectFilterScanRule.INSTANCE)
271274
.add(MaterializedViewAggregateOnNoneAggregateRule.INSTANCE)
272275
.add(MaterializedViewOnlyScanRule.INSTANCE)
276+
.add(MaterializedViewWindowScanRule.INSTANCE)
277+
.add(MaterializedViewWindowJoinRule.INSTANCE)
278+
.add(MaterializedViewWindowAggregateRule.INSTANCE)
273279
.build();
274280

275281
public static final List<Rule> MATERIALIZED_VIEW_IN_RBO_RULES = planRuleFactories()

‎fe/fe-core/src/main/java/org/apache/doris/nereids/rules/RuleType.java‎

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -455,6 +455,27 @@ public enum RuleType {
455455
MATERIALIZED_VIEW_FILTER_PROJECT_JOIN(RuleTypeClass.MATERIALIZE_VIEW),
456456
MATERIALIZED_VIEW_ONLY_JOIN(RuleTypeClass.MATERIALIZE_VIEW),
457457

458+
// window above join without aggregate
459+
MATERIALIZED_VIEW_PROJECT_WINDOW_JOIN(RuleTypeClass.MATERIALIZE_VIEW),
460+
MATERIALIZED_VIEW_FILTER_WINDOW_JOIN(RuleTypeClass.MATERIALIZE_VIEW),
461+
MATERIALIZED_VIEW_PROJECT_FILTER_WINDOW_JOIN(RuleTypeClass.MATERIALIZE_VIEW),
462+
MATERIALIZED_VIEW_FILTER_PROJECT_WINDOW_JOIN(RuleTypeClass.MATERIALIZE_VIEW),
463+
MATERIALIZED_VIEW_ONLY_WINDOW_JOIN(RuleTypeClass.MATERIALIZE_VIEW),
464+
465+
// window above scan without aggregate
466+
MATERIALIZED_VIEW_FILTER_WINDOW_SCAN(RuleTypeClass.MATERIALIZE_VIEW),
467+
MATERIALIZED_VIEW_PROJECT_WINDOW_SCAN(RuleTypeClass.MATERIALIZE_VIEW),
468+
MATERIALIZED_VIEW_FILTER_PROJECT_WINDOW_SCAN(RuleTypeClass.MATERIALIZE_VIEW),
469+
MATERIALIZED_VIEW_PROJECT_FILTER_WINDOW_SCAN(RuleTypeClass.MATERIALIZE_VIEW),
470+
MATERIALIZED_VIEW_ONLY_WINDOW_SCAN(RuleTypeClass.MATERIALIZE_VIEW),
471+
472+
// window with aggregate
473+
MATERIALIZED_VIEW_PROJECT_WINDOW_AGGREGATE(RuleTypeClass.MATERIALIZE_VIEW),
474+
MATERIALIZED_VIEW_FILTER_WINDOW_AGGREGATE(RuleTypeClass.MATERIALIZE_VIEW),
475+
MATERIALIZED_VIEW_PROJECT_FILTER_WINDOW_AGGREGATE(RuleTypeClass.MATERIALIZE_VIEW),
476+
MATERIALIZED_VIEW_FILTER_PROJECT_WINDOW_AGGREGATE(RuleTypeClass.MATERIALIZE_VIEW),
477+
MATERIALIZED_VIEW_ONLY_WINDOW_AGGREGATE(RuleTypeClass.MATERIALIZE_VIEW),
478+
458479
MATERIALIZED_VIEW_PROJECT_AGGREGATE(RuleTypeClass.MATERIALIZE_VIEW),
459480
MATERIALIZED_VIEW_FILTER_AGGREGATE(RuleTypeClass.MATERIALIZE_VIEW),
460481
MATERIALIZED_VIEW_PROJECT_FILTER_AGGREGATE(RuleTypeClass.MATERIALIZE_VIEW),

‎fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/mv/AbstractMaterializedViewAggregateRule.java‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -688,7 +688,8 @@ protected boolean checkQueryPattern(StructInfo structInfo, CascadesContext casca
688688
PlanCheckContext checkContext = PlanCheckContext.of(SUPPORTED_JOIN_TYPE_SET);
689689
// if query or mv contains more then one top aggregate, should fail
690690
return structInfo.getTopPlan().accept(StructInfo.PLAN_PATTERN_CHECKER, checkContext)
691-
&& checkContext.isContainsTopAggregate() && checkContext.getTopAggregateNum() <= 1;
691+
&& checkContext.isContainsTopAggregate() && checkContext.getTopAggregateNum() <= 1
692+
&& !checkContext.isContainsTopWindow();
692693
}
693694

694695
/**

‎fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/mv/AbstractMaterializedViewJoinRule.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -81,6 +81,6 @@ protected Plan rewriteQueryByView(MatchMode matchMode,
8181
protected boolean checkQueryPattern(StructInfo structInfo, CascadesContext cascadesContext) {
8282
PlanCheckContext checkContext = PlanCheckContext.of(SUPPORTED_JOIN_TYPE_SET);
8383
return structInfo.getTopPlan().accept(StructInfo.PLAN_PATTERN_CHECKER, checkContext)
84-
&& !checkContext.isContainsTopAggregate();
84+
&& !checkContext.isContainsTopAggregate() && !checkContext.isContainsTopWindow();
8585
}
8686
}

‎fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/mv/AbstractMaterializedViewRule.java‎

Lines changed: 14 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -284,7 +284,8 @@ protected List<Plan> doRewrite(StructInfo queryStructInfo, CascadesContext casca
284284
rewrittenPlan = new LogicalFilter<>(Sets.newLinkedHashSet(rewriteCompensatePredicates), mvScan);
285285
}
286286
boolean checkResult = rewriteQueryByViewPreCheck(matchMode, queryStructInfo,
287-
viewStructInfo, viewToQuerySlotMapping, rewrittenPlan, materializationContext);
287+
viewStructInfo, viewToQuerySlotMapping, rewrittenPlan, materializationContext,
288+
comparisonResult);
288289
if (!checkResult) {
289290
continue;
290291
}
@@ -519,7 +520,7 @@ protected Pair<Map<BaseTableInfo, Set<String>>, Map<BaseColInfo, Set<String>>> c
519520
*/
520521
protected boolean rewriteQueryByViewPreCheck(MatchMode matchMode, StructInfo queryStructInfo,
521522
StructInfo viewStructInfo, SlotMapping viewToQuerySlotMapping, Plan tempRewritedPlan,
522-
MaterializationContext materializationContext) {
523+
MaterializationContext materializationContext, ComparisonResult comparisonResult) {
523524
if (materializationContext instanceof SyncMaterializationContext
524525
&& queryStructInfo.getBottomPlan() instanceof LogicalOlapScan) {
525526
LogicalOlapScan olapScan = (LogicalOlapScan) queryStructInfo.getBottomPlan();
@@ -743,13 +744,13 @@ protected SplitPredicate predicatesCompensate(
743744
// set pulled up expression to queryStructInfo predicates and update related predicates
744745
if (!queryPulledUpExpressions.isEmpty()) {
745746
queryStructInfo = queryStructInfo.withPredicates(
746-
queryStructInfo.getPredicates().merge(queryPulledUpExpressions));
747+
queryStructInfo.getPredicates().mergePulledUpPredicates(queryPulledUpExpressions));
747748
}
748749
List<Expression> viewPulledUpExpressions = ImmutableList.copyOf(comparisonResult.getViewExpressions());
749750
// set pulled up expression to viewStructInfo predicates and update related predicates
750751
if (!viewPulledUpExpressions.isEmpty()) {
751752
viewStructInfo = viewStructInfo.withPredicates(
752-
viewStructInfo.getPredicates().merge(viewPulledUpExpressions));
753+
viewStructInfo.getPredicates().mergePulledUpPredicates(viewPulledUpExpressions));
753754
}
754755
// if the join type in query and mv plan is different, we should check query is have the
755756
// filters which rejects null
@@ -762,8 +763,8 @@ protected SplitPredicate predicatesCompensate(
762763
queryStructInfo.getPredicates().getPulledUpPredicates(), queryToViewMapping, queryStructInfo,
763764
viewStructInfo, cascadesContext);
764765
if (!valid) {
765-
queryStructInfo = queryStructInfo.withPredicates(
766-
queryStructInfo.getPredicates().merge(comparisonResult.getQueryAllPulledUpExpressions()));
766+
queryStructInfo = queryStructInfo.withPredicates(queryStructInfo.getPredicates()
767+
.mergePulledUpPredicates(comparisonResult.getQueryAllPulledUpExpressions()));
767768
valid = containsNullRejectSlot(requireNoNullableViewSlot,
768769
queryStructInfo.getPredicates().getPulledUpPredicates(), queryToViewMapping,
769770
queryStructInfo, viewStructInfo, cascadesContext);
@@ -772,6 +773,13 @@ protected SplitPredicate predicatesCompensate(
772773
return SplitPredicate.INVALID_INSTANCE;
773774
}
774775
}
776+
// compensate couldNot PulledUp Conjunctions
777+
Map<Expression, ExpressionInfo> couldNotPulledUpCompensateConjunctions =
778+
Predicates.compensateCouldNotPullUpPredicates(queryStructInfo, viewStructInfo,
779+
viewToQuerySlotMapping, comparisonResult);
780+
if (couldNotPulledUpCompensateConjunctions == null) {
781+
return SplitPredicate.INVALID_INSTANCE;
782+
}
775783
// viewEquivalenceClass to query based
776784
// equal predicate compensate
777785
final Map<Expression, ExpressionInfo> equalCompensateConjunctions = Predicates.compensateEquivalence(

‎fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/mv/AbstractMaterializedViewScanRule.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -81,6 +81,6 @@ protected Plan rewriteQueryByView(MatchMode matchMode,
8181
protected boolean checkQueryPattern(StructInfo structInfo, CascadesContext cascadesContext) {
8282
PlanCheckContext checkContext = PlanCheckContext.of(ImmutableSet.of());
8383
return structInfo.getTopPlan().accept(StructInfo.SCAN_PLAN_PATTERN_CHECKER, checkContext)
84-
&& !checkContext.isContainsTopAggregate();
84+
&& !checkContext.isContainsTopAggregate() && !checkContext.isContainsTopWindow();
8585
}
8686
}

0 commit comments

Comments
 (0)