This is an automated email from the ASF dual-hosted git repository. caogaofei pushed a commit to branch beyyes/sort_transform_elimate_topk in repository https://gitbox.apache.org/repos/asf/iotdb.git
commit 173d6eeb3e13e70f08bcd869ec7d429405829f9b Merge: 22e003e9c31 3145d189530 Author: Beyyes <[email protected]> AuthorDate: Tue Jul 16 14:19:22 2024 +0800 merge .../java/org/apache/iotdb/rpc/TSStatusCode.java | 2 +- .../confignode/persistence/schema/ConfigMTree.java | 17 +- .../persistence/schema/ConfigMTreeTest.java | 81 ++ .../plan/planner/plan/node/PlanNode.java | 4 + .../plan/planner/plan/node/PlanVisitor.java | 5 + .../querystats/PlanOptimizersStatsCollector.java | 75 ++ .../querystats/QueryPlanOptimizerStatistics.java | 57 ++ .../querystats/QueryPlanOptimizerStats.java | 84 ++ .../plan/relational/planner/Assignments.java | 20 + .../relational/planner/ExpressionExtractor.java | 117 +++ .../planner/ExpressionSymbolInliner.java | 65 ++ .../plan/relational/planner/LogicalPlanner.java | 79 +- .../plan/relational/planner/PlanBuilder.java | 4 +- .../plan/relational/planner/PlanNodeSearcher.java | 226 +++++ .../plan/relational/planner/QueryPlanner.java | 4 +- .../plan/relational/planner/SymbolsExtractor.java | 200 ++++ .../plan/relational/planner/ir/IrUtils.java | 5 + .../GroupReference.java} | 72 +- .../planner/iterative/IterativeOptimizer.java | 365 +++++++ .../plan/relational/planner/iterative/Lookup.java | 65 ++ .../plan/relational/planner/iterative/Memo.java | 225 +++++ .../plan/relational/planner/iterative/Plans.java | 54 ++ .../plan/relational/planner/iterative/Rule.java | 87 ++ .../relational/planner/iterative/RuleIndex.java | 76 ++ .../relational/planner/iterative/RuleStats.java | 53 + .../planner/iterative/RuleStatsRecorder.java | 45 + .../planner/iterative/rule/InlineProjections.java | 220 +++++ .../iterative/rule/ProjectOffPushDownRule.java | 67 ++ .../planner/iterative/rule/PruneFilterColumns.java | 46 + .../planner/iterative/rule/PruneLimitColumns.java | 36 + .../planner/iterative/rule/PruneOffsetColumns.java | 36 + .../iterative/rule/PruneOutputSourceColumns.java | 43 + .../iterative/rule/PruneProjectColumns.java | 39 + .../planner/iterative/rule/PruneSortColumns.java | 44 + .../iterative/rule/PruneTableScanColumns.java | 102 ++ .../rule/RemoveRedundantIdentityProjections.java | 48 + .../relational/planner/iterative/rule/Util.java | 137 +++ .../relational/planner/node/ChildReplacer.java | 32 + .../plan/relational/planner/node/CollectNode.java | 12 + .../plan/relational/planner/node/FilterNode.java | 6 + .../plan/relational/planner/node/LimitNode.java | 11 + .../relational/planner/node/MergeSortNode.java | 18 + .../plan/relational/planner/node/OffsetNode.java | 6 + .../plan/relational/planner/node/OutputNode.java | 6 + .../plan/relational/planner/node/Patterns.java | 429 +++++++++ .../plan/relational/planner/node/ProjectNode.java | 10 + .../plan/relational/planner/node/SortNode.java | 6 + .../relational/planner/node/TableScanNode.java | 12 + .../plan/relational/planner/node/TopKNode.java | 22 + .../optimizations/AdaptivePlanOptimizer.java | 56 ++ .../planner/optimizations/PlanOptimizer.java | 77 ++ .../planner/optimizations/PruneUnUsedColumns.java | 151 --- .../RemoveRedundantIdentityProjections.java | 97 -- .../plan/relational/utils/MoreLists.java | 53 + .../plan/relational/utils/matching/Capture.java | 43 + .../plan/relational/utils/matching/Captures.java | 86 ++ .../relational/utils/matching/DefaultPrinter.java | 77 ++ .../plan/relational/utils/matching/Match.java | 66 ++ .../plan/relational/utils/matching/Pattern.java | 120 +++ .../relational/utils/matching/PatternVisitor.java | 46 + .../plan/relational/utils/matching/Property.java | 89 ++ .../relational/utils/matching/PropertyPattern.java | 51 + .../utils/matching/pattern/CapturePattern.java | 53 + .../utils/matching/pattern/EqualsPattern.java | 53 + .../utils/matching/pattern/FilterPattern.java | 55 ++ .../utils/matching/pattern/TypeOfPattern.java | 59 ++ .../utils/matching/pattern/WithPattern.java | 65 ++ .../plan/relational/analyzer/AnalyzerTest.java | 82 +- .../analyzer/LimitOffsetPushDownTest.java | 42 +- .../plan/relational/analyzer/SortTest.java | 1015 +++++++------------- 70 files changed, 4868 insertions(+), 1043 deletions(-) diff --cc iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/LogicalPlanner.java index 6bd88486b48,8d34326e066..98d260e1ed9 --- a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/LogicalPlanner.java +++ b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/LogicalPlanner.java @@@ -30,13 -31,24 +31,25 @@@ import org.apache.iotdb.db.queryengine. import org.apache.iotdb.db.queryengine.plan.relational.analyzer.Analysis; import org.apache.iotdb.db.queryengine.plan.relational.analyzer.Field; import org.apache.iotdb.db.queryengine.plan.relational.analyzer.RelationType; + import org.apache.iotdb.db.queryengine.plan.relational.execution.querystats.PlanOptimizersStatsCollector; import org.apache.iotdb.db.queryengine.plan.relational.metadata.Metadata; + import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.IterativeOptimizer; + import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.Rule; + import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.RuleStatsRecorder; + import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.rule.InlineProjections; + import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.rule.PruneFilterColumns; + import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.rule.PruneLimitColumns; + import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.rule.PruneOffsetColumns; + import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.rule.PruneOutputSourceColumns; + import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.rule.PruneProjectColumns; + import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.rule.PruneSortColumns; + import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.rule.PruneTableScanColumns; + import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.rule.RemoveRedundantIdentityProjections; import org.apache.iotdb.db.queryengine.plan.relational.planner.node.CreateTableDeviceNode; import org.apache.iotdb.db.queryengine.plan.relational.planner.node.OutputNode; +import org.apache.iotdb.db.queryengine.plan.relational.planner.optimizations.AddStreamSort; - import org.apache.iotdb.db.queryengine.plan.relational.planner.optimizations.PruneUnUsedColumns; + import org.apache.iotdb.db.queryengine.plan.relational.planner.optimizations.PlanOptimizer; import org.apache.iotdb.db.queryengine.plan.relational.planner.optimizations.PushPredicateIntoTableScan; - import org.apache.iotdb.db.queryengine.plan.relational.planner.optimizations.RemoveRedundantIdentityProjections; import org.apache.iotdb.db.queryengine.plan.relational.planner.optimizations.SimplifyExpressions; import org.apache.iotdb.db.queryengine.plan.relational.planner.optimizations.TablePlanOptimizer; import org.apache.iotdb.db.queryengine.plan.relational.sql.ast.CreateDevice; @@@ -79,16 -96,29 +97,30 @@@ public class LogicalPlanner this.metadata = metadata; this.sessionInfo = requireNonNull(sessionInfo, "session is null"); this.warningCollector = requireNonNull(warningCollector, "warningCollector is null"); - + PlannerContext plannerContext = new PlannerContext(metadata, new InternalTypeManager()); this.tablePlanOptimizers = - Arrays.asList(new SimplifyExpressions(), new PushPredicateIntoTableScan()); + Arrays.asList( - new SimplifyExpressions(), - new PruneUnUsedColumns(), - new PushPredicateIntoTableScan(), - new RemoveRedundantIdentityProjections(), - new AddStreamSort()); ++ new SimplifyExpressions(), new PushPredicateIntoTableScan(), new AddStreamSort()); + + Set<Rule<?>> pruneRules = + ImmutableSet.of( + new PruneFilterColumns(), + new PruneLimitColumns(), + new PruneOffsetColumns(), + new PruneOutputSourceColumns(), + new PruneProjectColumns(), + new PruneSortColumns(), + new PruneTableScanColumns(metadata)); + Set<Rule<?>> inlineProjections = + ImmutableSet.of( + new InlineProjections(plannerContext), new RemoveRedundantIdentityProjections()); + this.planOptimizers = + ImmutableList.of( + new IterativeOptimizer(plannerContext, new RuleStatsRecorder(), pruneRules), + new IterativeOptimizer(plannerContext, new RuleStatsRecorder(), inlineProjections)); } + @TestOnly public LogicalPlanner( MPPQueryContext context, Metadata metadata, diff --cc iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/QueryPlanner.java index 8456c03a52f,ae7f47f3058..a9c094d7d9a --- a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/QueryPlanner.java +++ b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/QueryPlanner.java @@@ -152,6 -152,6 +152,7 @@@ public class QueryPlanner outputs.stream().map(builder::translate).forEach(newFields::add); builder = builder.withScope(analysis.getScope(node.getOrderBy().orElse(null)), newFields); ++ analysis.setSortNode(true); } List<Expression> orderBy = analysis.getOrderByExpressions(node); diff --cc iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/node/LimitNode.java index f5f4b93a6ff,a0862384d87..8e7b0292b0a --- a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/node/LimitNode.java +++ b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/node/LimitNode.java @@@ -46,9 -47,14 +47,14 @@@ public class LimitNode extends SingleCh this.tiesResolvingScheme = tiesResolvingScheme; } + public boolean requiresPreSortedInputs() { + // TODO + return false; + } + @Override public PlanNode clone() { - return new LimitNode(id, child, count, tiesResolvingScheme); + return new LimitNode(id, null, count, tiesResolvingScheme); } @Override diff --cc iotdb-core/datanode/src/test/java/org/apache/iotdb/db/queryengine/plan/relational/analyzer/LimitOffsetPushDownTest.java index 3cdaa96bb16,da2368a0ab3..31b33a772b4 --- a/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/queryengine/plan/relational/analyzer/LimitOffsetPushDownTest.java +++ b/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/queryengine/plan/relational/analyzer/LimitOffsetPushDownTest.java @@@ -263,7 -257,7 +257,7 @@@ public class LimitOffsetPushDownTest assertTrue(tableScanNode.getPushDownLimit() == 0 && tableScanNode.getPushDownOffset() == 0); } -- private PlanNode getChildrenNode(PlanNode root, int idx) { ++ static PlanNode getChildrenNode(PlanNode root, int idx) { PlanNode result = root; for (int i = 1; i <= idx; i++) { result = result.getChildren().get(0); diff --cc iotdb-core/datanode/src/test/java/org/apache/iotdb/db/queryengine/plan/relational/analyzer/SortTest.java index 4fe3ae62137,c36e40d2bb8..3286313881a --- a/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/queryengine/plan/relational/analyzer/SortTest.java +++ b/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/queryengine/plan/relational/analyzer/SortTest.java @@@ -41,12 -40,8 +40,10 @@@ import org.apache.iotdb.db.queryengine. import org.apache.iotdb.db.queryengine.plan.relational.planner.node.OutputNode; import org.apache.iotdb.db.queryengine.plan.relational.planner.node.ProjectNode; import org.apache.iotdb.db.queryengine.plan.relational.planner.node.SortNode; +import org.apache.iotdb.db.queryengine.plan.relational.planner.node.StreamSortNode; import org.apache.iotdb.db.queryengine.plan.relational.planner.node.TableScanNode; +import org.apache.iotdb.db.queryengine.plan.relational.planner.optimizations.AddStreamSort; - import org.apache.iotdb.db.queryengine.plan.relational.planner.optimizations.PruneUnUsedColumns; import org.apache.iotdb.db.queryengine.plan.relational.planner.optimizations.PushPredicateIntoTableScan; - import org.apache.iotdb.db.queryengine.plan.relational.planner.optimizations.RemoveRedundantIdentityProjections; import org.apache.iotdb.db.queryengine.plan.relational.planner.optimizations.SimplifyExpressions; import org.apache.iotdb.db.queryengine.plan.relational.planner.optimizations.TablePlanOptimizer; @@@ -58,6 -53,6 +55,7 @@@ import java.util.List import java.util.stream.Collectors; import static org.apache.iotdb.db.queryengine.plan.relational.analyzer.AnalyzerTest.analyzeSQL; ++import static org.apache.iotdb.db.queryengine.plan.relational.analyzer.LimitOffsetPushDownTest.getChildrenNode; import static org.apache.iotdb.db.queryengine.plan.statement.component.Ordering.ASC; import static org.apache.iotdb.db.queryengine.plan.statement.component.Ordering.DESC; import static org.junit.Assert.assertEquals; @@@ -85,12 -80,7 +83,8 @@@ public class SortTest DistributedQueryPlan distributedQueryPlan; TableScanNode tableScanNode; List<TablePlanOptimizer> planOptimizerList = - Arrays.asList(new SimplifyExpressions(), new PushPredicateIntoTableScan()); + Arrays.asList( - new SimplifyExpressions(), - new PruneUnUsedColumns(), - new PushPredicateIntoTableScan(), - new RemoveRedundantIdentityProjections(), - new AddStreamSort()); ++ new SimplifyExpressions(), new PushPredicateIntoTableScan(), new AddStreamSort()); /* * order by time, others, some_ids @@@ -847,27 -700,17 +704,15 @@@ .plan(actualAnalysis); rootNode = logicalQueryPlan.getRootNode(); - // OutputNode - LimitNode - OffsetNode - SortNode - ProjectNode - ProjectNode - FilterNode - - // OutputNode - LimitNode - OffsetNode - ProjectNode - SortNode - ProjectNode - FilterNode - -- // TableScanNode ++ // LogicalPlan: `Output - Limit - Offset - Project - StreamSort - Project - Filter - TableScan` assertTrue(rootNode instanceof OutputNode); -- assertTrue(rootNode.getChildren().get(0) instanceof LimitNode); -- assertTrue(rootNode.getChildren().get(0).getChildren().get(0) instanceof OffsetNode); -- assertTrue( -- rootNode.getChildren().get(0).getChildren().get(0).getChildren().get(0) - instanceof StreamSortNode); - StreamSortNode sortNode = - (StreamSortNode) rootNode.getChildren().get(0).getChildren().get(0).getChildren().get(0); - assertTrue(sortNode.getChildren().get(0) instanceof ProjectNode); - assertTrue(sortNode.getChildren().get(0).getChildren().get(0) instanceof ProjectNode); - assertTrue( - sortNode.getChildren().get(0).getChildren().get(0).getChildren().get(0) - instanceof FilterNode); - assertTrue( - sortNode.getChildren().get(0).getChildren().get(0).getChildren().get(0).getChildren().get(0) - instanceof TableScanNode); - tableScanNode = - (TableScanNode) - sortNode - instanceof ProjectNode); - SortNode sortNode = - (SortNode) ++ assertTrue(getChildrenNode(rootNode, 1) instanceof LimitNode); ++ assertTrue(getChildrenNode(rootNode, 2) instanceof OffsetNode); ++ assertTrue(getChildrenNode(rootNode, 3) instanceof ProjectNode); ++ assertTrue(getChildrenNode(rootNode, 4) instanceof StreamSortNode); ++ StreamSortNode streamSortNode = ++ (StreamSortNode) + rootNode .getChildren() .get(0) .getChildren() @@@ -876,14 -719,21 +721,21 @@@ .get(0) .getChildren() .get(0); - assertTrue(sortNode.getChildren().get(0) instanceof ProjectNode); - assertTrue(sortNode.getChildren().get(0).getChildren().get(0) instanceof FilterNode); ++ assertTrue(streamSortNode.getChildren().get(0) instanceof ProjectNode); ++ assertTrue(streamSortNode.getChildren().get(0).getChildren().get(0) instanceof FilterNode); + assertTrue( - sortNode.getChildren().get(0).getChildren().get(0).getChildren().get(0) ++ streamSortNode.getChildren().get(0).getChildren().get(0).getChildren().get(0) + instanceof TableScanNode); + tableScanNode = - (TableScanNode) sortNode.getChildren().get(0).getChildren().get(0).getChildren().get(0); ++ (TableScanNode) ++ streamSortNode.getChildren().get(0).getChildren().get(0).getChildren().get(0); assertEquals("testdb.table1", tableScanNode.getQualifiedObjectName().toString()); - assertEquals(9, tableScanNode.getAssignments().size()); + assertEquals(8, tableScanNode.getAssignments().size()); assertEquals(6, tableScanNode.getDeviceEntries().size()); assertEquals(5, tableScanNode.getIdAndAttributeIndexMap().size()); - // OutputNode - LimitNode - OffsetNode - MergeSortNode - SortNode - ProjectNode - ProjectNode - - // OutputNode - LimitNode - OffsetNode - ProjectNode - MergeSortNode - SortNode - ProjectNode - -- // FilterNode - -- // TableScanNode ++ // DistributePlan: `Output - Limit - Offset - Project - MergeSort - StreamSort - Project - ++ // Filter - TableScan` distributionPlanner = new TableDistributionPlanner(actualAnalysis, logicalQueryPlan, context); distributedQueryPlan = distributionPlanner.plan(); assertEquals(3, distributedQueryPlan.getFragments().size()); @@@ -928,6 -759,14 +761,15 @@@ .get(0) .getChildren() .get(0); + assertTrue(mergeSortNode.getChildren().get(0) instanceof ExchangeNode); - assertTrue(mergeSortNode.getChildren().get(1) instanceof SortNode); ++ assertTrue(mergeSortNode.getChildren().get(1) instanceof StreamSortNode); + assertTrue(mergeSortNode.getChildren().get(2) instanceof ExchangeNode); - sortNode = (SortNode) mergeSortNode.getChildren().get(1); - assertTrue(sortNode.getChildren().get(0) instanceof ProjectNode); - assertTrue(sortNode.getChildren().get(0).getChildren().get(0) instanceof FilterNode); ++ streamSortNode = (StreamSortNode) mergeSortNode.getChildren().get(1); ++ assertTrue(streamSortNode.getChildren().get(0) instanceof ProjectNode); ++ assertTrue(streamSortNode.getChildren().get(0).getChildren().get(0) instanceof FilterNode); + tableScanNode = - (TableScanNode) sortNode.getChildren().get(0).getChildren().get(0).getChildren().get(0); ++ (TableScanNode) ++ streamSortNode.getChildren().get(0).getChildren().get(0).getChildren().get(0); assertEquals(4, tableScanNode.getDeviceEntries().size()); assertEquals( Arrays.asList( @@@ -940,7 -779,7 +782,7 @@@ .collect(Collectors.toList())); assertEquals(DESC, tableScanNode.getScanOrder()); - // IdentitySinkNode - SortNode - ProjectNode - ProjectNode - FilterNode - TableScanNode - // IdentitySinkNode - SortNode - ProjectNode - FilterNode - TableScanNode ++ // DistributePlan: `IdentitySink - StreamSort - Project - Filter - TableScan` assertTrue( distributedQueryPlan.getFragments().get(1).getPlanNodeTree() instanceof IdentitySinkNode); assertTrue(
