Skip to content

Commit 5c84f63

Browse files
924060929gnehil
authored andcommitted
[refactor](Nereids) refactor column pruning (apache#17579)
This pr refactor the column pruning by the visitor, the good sides 1. easy to provide ability of column pruning for new plan by implement the interface `OutputPrunable` if the plan contains output field or do nothing if not contains output field, don't need to add new rule like `PruneXxxChildColumns`, few scenarios need to override the visit function to write special logic, like prune the LogicalSetOperation and Aggregate 2. support shrink output field in some plans, this can skip some useless operations so improvement example: ```sql select id from ( select id, sum(age) from student group by id )a ``` we should prune the useless `sum (age)` in the aggregate. before refactor: ``` LogicalProject ( distinct=false, projects=[id#0], excepts=[], canEliminate=true ) +--LogicalSubQueryAlias ( qualifier=[a] ) +--LogicalAggregate ( groupByExpr=[id#0], outputExpr=[id#0, sum(age#2) AS `sum(age)`apache#4], hasRepeat=false ) +--LogicalProject ( distinct=false, projects=[id#0, age#2], excepts=[], canEliminate=true ) +--LogicalOlapScan ( qualified=default_cluster:test.student, indexName=<index_not_selected>, selectedIndexId=10007, preAgg=ON ) ``` after refactor: ``` LogicalProject ( distinct=false, projects=[id#0], excepts=[], canEliminate=true ) +--LogicalSubQueryAlias ( qualifier=[a] ) +--LogicalAggregate ( groupByExpr=[id#0], outputExpr=[id#0], hasRepeat=false ) +--LogicalProject ( distinct=false, projects=[id#0], excepts=[], canEliminate=true ) +--LogicalOlapScan ( qualified=default_cluster:test.student, indexName=<index_not_selected>, selectedIndexId=10007, preAgg=ON ) ```
1 parent 7a67c95 commit 5c84f63

44 files changed

Lines changed: 628 additions & 583 deletions

File tree

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

‎fe/fe-core/src/main/java/org/apache/doris/analysis/AggregateInfo.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -844,7 +844,7 @@ public void updateMaterializedSlots() {
844844
// why output and intermediate may have different materialized slots?
845845
// because some slot is materialized by materializeSrcExpr method directly
846846
// in that case, only output slots is materialized
847-
// assume output tuple has correct marterialized infomation
847+
// assume output tuple has correct materialized information
848848
// we update intermediate tuple and materializedSlots based on output tuple
849849
materializedSlots.clear();
850850
ArrayList<SlotDescriptor> outputSlots = outputTupleDesc.getSlots();

‎fe/fe-core/src/main/java/org/apache/doris/nereids/glue/translator/PhysicalPlanTranslator.java‎

Lines changed: 5 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1671,7 +1671,11 @@ public PlanFragment visitPhysicalGenerate(PhysicalGenerate<? extends Plan> gener
16711671
.map(e -> ExpressionTranslator.translate(e, context))
16721672
.collect(Collectors.toCollection(ArrayList::new));
16731673
TupleDescriptor tupleDescriptor = generateTupleDesc(generate.getGeneratorOutput(), null, context);
1674-
List<SlotId> outputSlotIds = Stream.concat(currentFragment.getPlanRoot().getTupleIds().stream(),
1674+
List<TupleId> childOutputTupleIds = currentFragment.getPlanRoot().getOutputTupleIds();
1675+
if (childOutputTupleIds == null || childOutputTupleIds.isEmpty()) {
1676+
childOutputTupleIds = currentFragment.getPlanRoot().getTupleIds();
1677+
}
1678+
List<SlotId> outputSlotIds = Stream.concat(childOutputTupleIds.stream(),
16751679
Stream.of(tupleDescriptor.getId()))
16761680
.map(id -> context.getTupleDesc(id).getSlots())
16771681
.flatMap(List::stream)

‎fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/batch/NereidsRewriter.java‎

Lines changed: 66 additions & 46 deletions
Original file line numberDiff line numberDiff line change
@@ -19,6 +19,7 @@
1919

2020
import org.apache.doris.nereids.CascadesContext;
2121
import org.apache.doris.nereids.jobs.RewriteJob;
22+
import org.apache.doris.nereids.rules.RuleFactory;
2223
import org.apache.doris.nereids.rules.RuleSet;
2324
import org.apache.doris.nereids.rules.RuleType;
2425
import org.apache.doris.nereids.rules.analysis.AdjustAggregateNullableForEmptySet;
@@ -56,13 +57,16 @@
5657
import org.apache.doris.nereids.rules.rewrite.logical.MergeProjects;
5758
import org.apache.doris.nereids.rules.rewrite.logical.MergeSetOperations;
5859
import org.apache.doris.nereids.rules.rewrite.logical.NormalizeAggregate;
60+
import org.apache.doris.nereids.rules.rewrite.logical.NormalizeSort;
5961
import org.apache.doris.nereids.rules.rewrite.logical.PruneOlapScanPartition;
6062
import org.apache.doris.nereids.rules.rewrite.logical.PruneOlapScanTablet;
6163
import org.apache.doris.nereids.rules.rewrite.logical.PushFilterInsideJoin;
6264
import org.apache.doris.nereids.rules.rewrite.logical.PushdownLimit;
6365
import org.apache.doris.nereids.rules.rewrite.logical.ReorderJoin;
6466
import org.apache.doris.nereids.rules.rewrite.logical.SplitLimit;
6567

68+
import com.google.common.collect.ImmutableList;
69+
6670
import java.util.List;
6771

6872
/**
@@ -89,7 +93,7 @@ public class NereidsRewriter extends BatchRewriteJob {
8993

9094
// ExtractSingleTableExpressionFromDisjunction conflict to InPredicateToEqualToRule
9195
// in the ExpressionNormalization, so must invoke in another job, or else run into
92-
// deep loop
96+
// dead loop
9397
topDown(
9498
new ExtractSingleTableExpressionFromDisjunction()
9599
)
@@ -117,10 +121,11 @@ public class NereidsRewriter extends BatchRewriteJob {
117121

118122
// The rule modification needs to be done after the subquery is unnested,
119123
// because for scalarSubQuery, the connection condition is stored in apply in the analyzer phase,
120-
// but when normalizeAggregate is performed, the members in apply cannot be obtained,
124+
// but when normalizeAggregate/normalizeSort is performed, the members in apply cannot be obtained,
121125
// resulting in inconsistent output results and results in apply
122126
topDown(
123-
new NormalizeAggregate()
127+
new NormalizeAggregate(),
128+
new NormalizeSort()
124129
),
125130

126131
topDown(
@@ -138,71 +143,86 @@ public class NereidsRewriter extends BatchRewriteJob {
138143
),
139144

140145
topic("Rewrite join",
141-
// infer not null filter, then push down filter, and then reorder join(cross join to inner join)
142-
topDown(
143-
new InferFilterNotNull(),
144-
new InferJoinNotNull()
145-
),
146-
// ReorderJoin depends PUSH_DOWN_FILTERS
147-
// the PUSH_DOWN_FILTERS depends on lots of rules, e.g. merge project, eliminate outer,
148-
// sometimes transform the bottom plan make some rules usable which can apply to the top plan,
149-
// but top-down traverse can not cover this case in one iteration, so bottom-up is more
150-
// efficient because it can find the new plans and apply transform wherever it is
151-
bottomUp(RuleSet.PUSH_DOWN_FILTERS),
152-
153-
topDown(
154-
new MergeFilters(),
155-
new ReorderJoin(),
156-
new PushFilterInsideJoin(),
157-
new FindHashConditionForJoin(),
158-
new ConvertInnerOrCrossJoin(),
159-
new EliminateNullAwareLeftAntiJoin()
160-
),
161-
topDown(
162-
new EliminateDedupJoinCondition()
163-
)
146+
// infer not null filter, then push down filter, and then reorder join(cross join to inner join)
147+
topDown(
148+
new InferFilterNotNull(),
149+
new InferJoinNotNull()
150+
),
151+
// ReorderJoin depends PUSH_DOWN_FILTERS
152+
// the PUSH_DOWN_FILTERS depends on lots of rules, e.g. merge project, eliminate outer,
153+
// sometimes transform the bottom plan make some rules usable which can apply to the top plan,
154+
// but top-down traverse can not cover this case in one iteration, so bottom-up is more
155+
// efficient because it can find the new plans and apply transform wherever it is
156+
bottomUp(RuleSet.PUSH_DOWN_FILTERS),
157+
158+
topDown(
159+
new MergeFilters(),
160+
new ReorderJoin(),
161+
new PushFilterInsideJoin(),
162+
new FindHashConditionForJoin(),
163+
new ConvertInnerOrCrossJoin(),
164+
new EliminateNullAwareLeftAntiJoin()
165+
),
166+
topDown(
167+
new EliminateDedupJoinCondition()
168+
)
164169
),
165170

166171
topic("Column pruning and infer predicate",
167-
topDown(new ColumnPruning()),
172+
custom(RuleType.COLUMN_PRUNING, () -> new ColumnPruning()),
168173

169-
custom(RuleType.INFER_PREDICATES, () -> new InferPredicates()),
174+
custom(RuleType.INFER_PREDICATES, () -> new InferPredicates()),
170175

171-
// column pruning create new project, so we should use PUSH_DOWN_FILTERS
172-
// to change filter-project to project-filter
173-
bottomUp(RuleSet.PUSH_DOWN_FILTERS),
176+
// column pruning create new project, so we should use PUSH_DOWN_FILTERS
177+
// to change filter-project to project-filter
178+
bottomUp(RuleSet.PUSH_DOWN_FILTERS),
174179

175-
// after eliminate outer join in the PUSH_DOWN_FILTERS, we can infer more predicate and push down
176-
custom(RuleType.INFER_PREDICATES, () -> new InferPredicates()),
180+
// after eliminate outer join in the PUSH_DOWN_FILTERS, we can infer more predicate and push down
181+
custom(RuleType.INFER_PREDICATES, () -> new InferPredicates()),
177182

178-
bottomUp(RuleSet.PUSH_DOWN_FILTERS),
183+
bottomUp(RuleSet.PUSH_DOWN_FILTERS),
179184

180-
// after eliminate outer join, we can move some filters to join.otherJoinConjuncts,
181-
// this can help to translate plan to backend
182-
topDown(
183-
new PushFilterInsideJoin()
184-
)
185+
// after eliminate outer join, we can move some filters to join.otherJoinConjuncts,
186+
// this can help to translate plan to backend
187+
topDown(
188+
new PushFilterInsideJoin()
189+
)
185190
),
186191

187192
// this rule should invoke after ColumnPruning
188193
custom(RuleType.ELIMINATE_UNNECESSARY_PROJECT, () -> new EliminateUnnecessaryProject()),
189194

190195
// we need to execute this rule at the end of rewrite
191196
// to avoid two consecutive same project appear when we do optimization.
192-
topic("Others optimization", topDown(
197+
topic("Others optimization",
198+
bottomUp(ImmutableList.<RuleFactory>builder().addAll(ImmutableList.of(
193199
new EliminateNotNull(),
194200
new EliminateLimit(),
195201
new EliminateFilter(),
196-
new PruneOlapScanPartition(),
197-
new SelectMaterializedIndexWithAggregate(),
198-
new SelectMaterializedIndexWithoutAggregate(),
199-
new PruneOlapScanTablet(),
200202
new EliminateAggregate(),
201203
new MergeSetOperations(),
202204
new PushdownLimit(),
203-
new SplitLimit(),
204205
new BuildAggForUnion()
205-
)),
206+
// after eliminate filter, the project maybe can push down again,
207+
// so we add push down rules
208+
)).addAll(RuleSet.PUSH_DOWN_FILTERS).build())
209+
),
210+
211+
// TODO: I think these rules should be implementation rules, and generate alternative physical plans.
212+
topic("Table/MV/Physical optimization",
213+
topDown(
214+
// TODO: the logical plan should not contains any phase information,
215+
// we should refactor like AggregateStrategies, e.g. LimitStrategies,
216+
// generate one PhysicalLimit if current distribution is gather or two
217+
// PhysicalLimits with gather exchange
218+
new SplitLimit(),
219+
220+
new SelectMaterializedIndexWithAggregate(),
221+
new SelectMaterializedIndexWithoutAggregate(),
222+
new PruneOlapScanTablet(),
223+
new PruneOlapScanPartition()
224+
)
225+
),
206226

207227
// this rule batch must keep at the end of rewrite to do some plan check
208228
topic("Final rewrite and check", bottomUp(

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

Lines changed: 2 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -88,6 +88,7 @@ public enum RuleType {
8888

8989
// rewrite rules
9090
NORMALIZE_AGGREGATE(RuleTypeClass.REWRITE),
91+
NORMALIZE_SORT(RuleTypeClass.REWRITE),
9192
NORMALIZE_REPEAT(RuleTypeClass.REWRITE),
9293
EXTRACT_AND_NORMALIZE_WINDOW_EXPRESSIONS(RuleTypeClass.REWRITE),
9394
CHECK_AND_STANDARDIZE_WINDOW_FUNCTION_AND_FRAME(RuleTypeClass.REWRITE),
@@ -128,14 +129,7 @@ public enum RuleType {
128129
PUSHDOWN_PROJECT_THROUGH_LIMIT(RuleTypeClass.REWRITE),
129130
PUSHDOWN_ALIAS_THROUGH_JOIN(RuleTypeClass.REWRITE),
130131
PUSHDOWN_FILTER_THROUGH_SET_OPERATION(RuleTypeClass.REWRITE),
131-
// column prune rules,
132-
COLUMN_PRUNE_AGGREGATION_CHILD(RuleTypeClass.REWRITE),
133-
COLUMN_PRUNE_FILTER_CHILD(RuleTypeClass.REWRITE),
134-
PRUNE_ONE_ROW_RELATION_COLUMN(RuleTypeClass.REWRITE),
135-
COLUMN_PRUNE_SORT_CHILD(RuleTypeClass.REWRITE),
136-
COLUMN_PRUNE_SORT(RuleTypeClass.REWRITE),
137-
COLUMN_PRUNE_JOIN_CHILD(RuleTypeClass.REWRITE),
138-
COLUMN_PRUNE_REPEAT_CHILD(RuleTypeClass.REWRITE),
132+
COLUMN_PRUNING(RuleTypeClass.REWRITE),
139133
// expression of plan rewrite
140134
REWRITE_ONE_ROW_RELATION_EXPRESSION(RuleTypeClass.REWRITE),
141135
REWRITE_PROJECT_EXPRESSION(RuleTypeClass.REWRITE),

0 commit comments

Comments
 (0)