This is an automated email from the ASF dual-hosted git repository. jackietien pushed a commit to branch ty/TableModelGrammar in repository https://gitbox.apache.org/repos/asf/iotdb.git
The following commit(s) were added to refs/heads/ty/TableModelGrammar by this push: new eea9de150eb Add FilterScanCombine optimize rule eea9de150eb is described below commit eea9de150eb46f13b0e8db590777b3e84d366565 Author: Beyyes <cgf1...@foxmail.com> AuthorDate: Tue Jun 11 12:05:40 2024 +0800 Add FilterScanCombine optimize rule --- .../db/queryengine/common/MPPQueryContext.java | 15 ++ .../relational/ColumnTransformerBuilder.java | 2 +- ...a => PredicateCombineIntoTableScanChecker.java} | 71 ++++--- ....java => PredicatePushIntoMetadataChecker.java} | 11 +- .../plan/relational/planner/LogicalPlanner.java | 4 +- .../plan/relational/planner/RelationPlanner.java | 12 +- .../ExtractCommonPredicatesExpressionRewriter.java | 2 +- .../relational/planner/node/TableScanNode.java | 22 +- .../planner/optimizations/FilterScanCombine.java | 227 +++++++++++++++++++++ .../planner/optimizations/IndexScan.java | 67 +++--- .../planner/optimizations/PredicatePushDown.java | 125 ------------ .../planner/optimizations/PruneUnUsedColumns.java | 14 ++ .../plan/relational/analyzer/AnalyzerTest.java | 53 ++++- 13 files changed, 408 insertions(+), 217 deletions(-) diff --git a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/common/MPPQueryContext.java b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/common/MPPQueryContext.java index 988224da729..1f9b24c713b 100644 --- a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/common/MPPQueryContext.java +++ b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/common/MPPQueryContext.java @@ -27,6 +27,7 @@ import org.apache.iotdb.db.queryengine.plan.analyze.QueryType; import org.apache.iotdb.db.queryengine.plan.analyze.TypeProvider; import org.apache.iotdb.db.queryengine.plan.analyze.lock.SchemaLockType; import org.apache.iotdb.db.queryengine.plan.planner.LocalExecutionPlanner; +import org.apache.iotdb.db.queryengine.plan.relational.sql.tree.Expression; import org.apache.iotdb.db.queryengine.statistics.QueryPlanStatistics; import org.apache.tsfile.read.filter.basic.Filter; @@ -89,6 +90,11 @@ public class MPPQueryContext { private final LocalExecutionPlanner LOCAL_EXECUTION_PLANNER = LocalExecutionPlanner.getInstance(); + // splits predicate expression in table model into three parts, + // index 0 represents metadataExpressions, index 1 represents expressionsCanPushDownToOperator, + // index 2 represents expressionsCannotPushDownToOperator + private List<List<Expression>> tableModelPredicateExpressions; + public MPPQueryContext(QueryId queryId) { this.queryId = queryId; this.endPointBlackList = new LinkedList<>(); @@ -312,6 +318,15 @@ public class MPPQueryContext { queryPlanStatistics.setLogicalOptimizationCost(logicalOptimizeCost); } + public List<List<Expression>> getTableModelPredicateExpressions() { + return tableModelPredicateExpressions; + } + + public void setTableModelPredicateExpressions( + List<List<Expression>> tableModelPredicateExpressions) { + this.tableModelPredicateExpressions = tableModelPredicateExpressions; + } + // region =========== FE memory related, make sure its not called concurrently =========== /** diff --git a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/execution/relational/ColumnTransformerBuilder.java b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/execution/relational/ColumnTransformerBuilder.java index fb405d1c62e..b911e2f0da4 100644 --- a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/execution/relational/ColumnTransformerBuilder.java +++ b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/execution/relational/ColumnTransformerBuilder.java @@ -113,7 +113,7 @@ import java.util.Optional; import java.util.stream.Collectors; import static com.google.common.base.Preconditions.checkArgument; -import static org.apache.iotdb.db.queryengine.plan.relational.analyzer.predicate.PredicatePushIntoIndexScanChecker.isStringLiteral; +import static org.apache.iotdb.db.queryengine.plan.relational.analyzer.predicate.PredicatePushIntoMetadataChecker.isStringLiteral; import static org.apache.iotdb.db.queryengine.plan.relational.type.InternalTypeManager.getTSDataType; import static org.apache.iotdb.db.queryengine.plan.relational.type.TypeSignatureTranslator.toTypeSignature; import static org.apache.tsfile.read.common.type.BinaryType.TEXT; diff --git a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/analyzer/predicate/PredicatePushIntoIndexScanChecker.java b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/analyzer/predicate/PredicateCombineIntoTableScanChecker.java similarity index 68% copy from iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/analyzer/predicate/PredicatePushIntoIndexScanChecker.java copy to iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/analyzer/predicate/PredicateCombineIntoTableScanChecker.java index f7d2c1764a3..03b717f3fe6 100644 --- a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/analyzer/predicate/PredicatePushIntoIndexScanChecker.java +++ b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/analyzer/predicate/PredicateCombineIntoTableScanChecker.java @@ -32,20 +32,24 @@ import org.apache.iotdb.db.queryengine.plan.relational.sql.tree.NotExpression; import org.apache.iotdb.db.queryengine.plan.relational.sql.tree.NullIfExpression; import org.apache.iotdb.db.queryengine.plan.relational.sql.tree.SearchedCaseExpression; import org.apache.iotdb.db.queryengine.plan.relational.sql.tree.SimpleCaseExpression; -import org.apache.iotdb.db.queryengine.plan.relational.sql.tree.StringLiteral; import org.apache.iotdb.db.queryengine.plan.relational.sql.tree.SymbolReference; import java.util.List; import java.util.Set; +import static org.apache.iotdb.db.queryengine.plan.relational.analyzer.predicate.PredicatePushIntoScanChecker.isLiteral; import static org.apache.iotdb.db.queryengine.plan.relational.analyzer.predicate.PredicatePushIntoScanChecker.isSymbolReference; -public class PredicatePushIntoIndexScanChecker extends PredicateVisitor<Boolean, Void> { +public class PredicateCombineIntoTableScanChecker extends PredicateVisitor<Boolean, Void> { - private final Set<String> idOrAttributeColumnNames; + private final Set<String> measurementColumns; - public PredicatePushIntoIndexScanChecker(Set<String> idOrAttributeColumnNames) { - this.idOrAttributeColumnNames = idOrAttributeColumnNames; + public static boolean check(Set<String> measurementColumns, Expression expression) { + return new PredicateCombineIntoTableScanChecker(measurementColumns).process(expression); + } + + public PredicateCombineIntoTableScanChecker(Set<String> measurementColumns) { + this.measurementColumns = measurementColumns; } @Override @@ -54,7 +58,7 @@ public class PredicatePushIntoIndexScanChecker extends PredicateVisitor<Boolean, } @Override - protected Boolean visitInPredicate(InPredicate node, Void context) { + protected Boolean visitNotExpression(NotExpression node, Void context) { return Boolean.FALSE; } @@ -64,53 +68,64 @@ public class PredicatePushIntoIndexScanChecker extends PredicateVisitor<Boolean, } @Override - protected Boolean visitIsNotNullPredicate(IsNotNullPredicate node, Void context) { - return Boolean.FALSE; + protected Boolean visitInPredicate(InPredicate node, Void context) { + return isMeasurementColumn(node.getValue()); } @Override protected Boolean visitLikePredicate(LikePredicate node, Void context) { - return Boolean.FALSE; + return isMeasurementColumn(node.getValue()) + && isLiteral(node.getPattern()) + && node.getEscape().map(PredicatePushIntoScanChecker::isLiteral).orElse(true); } @Override protected Boolean visitLogicalExpression(LogicalExpression node, Void context) { if (node.getOperator() == LogicalExpression.Operator.AND) { - throw new IllegalStateException("Shouldn't have AND operator in index scan expression."); + throw new IllegalStateException( + "Shouldn't have AND operator in PredicateCombineIntoTableScanChecker."); } + List<Expression> children = node.getTerms(); for (Expression child : children) { Boolean result = process(child, context); if (result == null) { - throw new IllegalStateException("Should never return null."); + throw new IllegalStateException( + "Should never return null in PredicateCombineIntoTableScanChecker."); } if (!result) { return Boolean.FALSE; } } + return Boolean.TRUE; } @Override - protected Boolean visitNotExpression(NotExpression node, Void context) { - return Boolean.FALSE; + protected Boolean visitComparisonExpression(ComparisonExpression node, Void context) { + return (isMeasurementColumn(node.getLeft()) && isLiteral(node.getRight())) + || (isMeasurementColumn(node.getRight()) && isLiteral(node.getLeft())); } @Override - protected Boolean visitComparisonExpression(ComparisonExpression node, Void context) { - if (node.getOperator() == ComparisonExpression.Operator.EQUAL) { - return (isIdOrAttributeColumn(node.getLeft()) && isStringLiteral(node.getRight())) - || (isIdOrAttributeColumn(node.getRight()) && isStringLiteral(node.getLeft())); - } else { - return Boolean.FALSE; - } + protected Boolean visitBetweenPredicate(BetweenPredicate node, Void context) { + return (isMeasurementColumn(node.getValue()) + && isLiteral(node.getMin()) + && isLiteral(node.getMax())) + || (isLiteral(node.getValue()) + && isMeasurementColumn(node.getMin()) + && isLiteral(node.getMax())) + || (isLiteral(node.getValue()) + && isLiteral(node.getMin()) + && isMeasurementColumn(node.getMax())); } - private boolean isIdOrAttributeColumn(Expression expression) { - return isSymbolReference(expression) - && idOrAttributeColumnNames.contains(((SymbolReference) expression).getName()); + @Override + protected Boolean visitIsNotNullPredicate(IsNotNullPredicate node, Void context) { + return isMeasurementColumn(node.getValue()); } + // expression below will be supported later @Override protected Boolean visitSimpleCaseExpression(SimpleCaseExpression node, Void context) { return Boolean.FALSE; @@ -131,12 +146,8 @@ public class PredicatePushIntoIndexScanChecker extends PredicateVisitor<Boolean, return Boolean.FALSE; } - @Override - protected Boolean visitBetweenPredicate(BetweenPredicate node, Void context) { - return Boolean.FALSE; - } - - public static boolean isStringLiteral(Expression expression) { - return expression instanceof StringLiteral; + private boolean isMeasurementColumn(Expression expression) { + return isSymbolReference(expression) + && measurementColumns.contains(((SymbolReference) expression).getName()); } } diff --git a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/analyzer/predicate/PredicatePushIntoIndexScanChecker.java b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/analyzer/predicate/PredicatePushIntoMetadataChecker.java similarity index 91% rename from iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/analyzer/predicate/PredicatePushIntoIndexScanChecker.java rename to iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/analyzer/predicate/PredicatePushIntoMetadataChecker.java index f7d2c1764a3..62551a24b84 100644 --- a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/analyzer/predicate/PredicatePushIntoIndexScanChecker.java +++ b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/analyzer/predicate/PredicatePushIntoMetadataChecker.java @@ -40,11 +40,15 @@ import java.util.Set; import static org.apache.iotdb.db.queryengine.plan.relational.analyzer.predicate.PredicatePushIntoScanChecker.isSymbolReference; -public class PredicatePushIntoIndexScanChecker extends PredicateVisitor<Boolean, Void> { +public class PredicatePushIntoMetadataChecker extends PredicateVisitor<Boolean, Void> { private final Set<String> idOrAttributeColumnNames; - public PredicatePushIntoIndexScanChecker(Set<String> idOrAttributeColumnNames) { + public static boolean check(Set<String> idOrAttributeColumnNames, Expression expression) { + return new PredicatePushIntoMetadataChecker(idOrAttributeColumnNames).process(expression); + } + + public PredicatePushIntoMetadataChecker(Set<String> idOrAttributeColumnNames) { this.idOrAttributeColumnNames = idOrAttributeColumnNames; } @@ -76,7 +80,8 @@ public class PredicatePushIntoIndexScanChecker extends PredicateVisitor<Boolean, @Override protected Boolean visitLogicalExpression(LogicalExpression node, Void context) { if (node.getOperator() == LogicalExpression.Operator.AND) { - throw new IllegalStateException("Shouldn't have AND operator in index scan expression."); + throw new IllegalStateException( + "Shouldn't have AND operator in PredicatePushIntoMetadataChecker."); } List<Expression> children = node.getTerms(); for (Expression child : children) { diff --git 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 index dfc2bfae5a2..f1ce49f1c14 100644 --- 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 @@ -28,8 +28,8 @@ 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.metadata.Metadata; import org.apache.iotdb.db.queryengine.plan.relational.planner.node.OutputNode; +import org.apache.iotdb.db.queryengine.plan.relational.planner.optimizations.FilterScanCombine; import org.apache.iotdb.db.queryengine.plan.relational.planner.optimizations.IndexScan; -import org.apache.iotdb.db.queryengine.plan.relational.planner.optimizations.PredicatePushDown; import org.apache.iotdb.db.queryengine.plan.relational.planner.optimizations.PruneUnUsedColumns; import org.apache.iotdb.db.queryengine.plan.relational.planner.optimizations.RelationalPlanOptimizer; import org.apache.iotdb.db.queryengine.plan.relational.planner.optimizations.RemoveRedundantIdentityProjections; @@ -79,7 +79,7 @@ public class LogicalPlanner { Arrays.asList( new SimplifyExpressions(), new PruneUnUsedColumns(), - new PredicatePushDown(), + new FilterScanCombine(), new RemoveRedundantIdentityProjections(), new IndexScan()); } diff --git a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/RelationPlanner.java b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/RelationPlanner.java index c09e5d67caa..d39b008a8ca 100644 --- a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/RelationPlanner.java +++ b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/RelationPlanner.java @@ -13,7 +13,6 @@ */ package org.apache.iotdb.db.queryengine.plan.relational.planner; -import org.apache.iotdb.commons.schema.table.column.TsTableColumnCategory; import org.apache.iotdb.db.queryengine.common.MPPQueryContext; import org.apache.iotdb.db.queryengine.common.QueryId; import org.apache.iotdb.db.queryengine.common.SessionInfo; @@ -41,7 +40,6 @@ import com.google.common.collect.ImmutableList; import com.google.common.collect.ImmutableMap; import java.util.Collection; -import java.util.HashMap; import java.util.List; import java.util.Map; @@ -94,12 +92,11 @@ public class RelationPlanner extends AstVisitor<RelationPlan, Void> { expansion.getRoot(), expansion.getScope(), expansion.getFieldMappings()); } - Map<Symbol, Integer> idAndAttributeIndexMap = new HashMap<>(); Scope scope = analysis.getScope(table); ImmutableList.Builder<Symbol> outputSymbolsBuilder = ImmutableList.builder(); ImmutableMap.Builder<Symbol, ColumnSchema> symbolToColumnSchema = ImmutableMap.builder(); Collection<Field> fields = scope.getRelationType().getAllFields(); - int IDIdx = 0, attributeIdx = 0; + for (Field field : fields) { Symbol symbol = symbolAllocator.newSymbol(field); outputSymbolsBuilder.add(symbol); @@ -107,12 +104,6 @@ public class RelationPlanner extends AstVisitor<RelationPlan, Void> { symbol, new ColumnSchema( field.getName().get(), field.getType(), field.isHidden(), field.getColumnCategory())); - - if (TsTableColumnCategory.ID.equals(field.getColumnCategory())) { - idAndAttributeIndexMap.put(symbol, IDIdx++); - } else if (TsTableColumnCategory.ATTRIBUTE.equals(field.getColumnCategory())) { - idAndAttributeIndexMap.put(symbol, attributeIdx++); - } } List<Symbol> outputSymbols = outputSymbolsBuilder.build(); @@ -123,7 +114,6 @@ public class RelationPlanner extends AstVisitor<RelationPlan, Void> { outputSymbols, symbolToColumnSchema.build()); - tableScanNode.setIdAndAttributeIndexMap(idAndAttributeIndexMap); return new RelationPlan(tableScanNode, scope, outputSymbols); // Collection<Field> fields = analysis.getMaterializedViewStorageTableFields(node); diff --git a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/ir/ExtractCommonPredicatesExpressionRewriter.java b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/ir/ExtractCommonPredicatesExpressionRewriter.java index 92a5f96e3e7..3789b793c29 100644 --- a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/ir/ExtractCommonPredicatesExpressionRewriter.java +++ b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/ir/ExtractCommonPredicatesExpressionRewriter.java @@ -163,7 +163,7 @@ public final class ExtractCommonPredicatesExpressionRewriter { } private Set<Expression> filterDeterministicPredicates(List<Expression> predicates) { - return predicates.stream().filter(expression -> isDeterministic(expression)).collect(toSet()); + return predicates.stream().filter(DeterminismEvaluator::isDeterministic).collect(toSet()); } private static <T> List<T> removeAll(Collection<T> collection, Collection<T> elementsToRemove) { diff --git a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/node/TableScanNode.java b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/node/TableScanNode.java index 6fd46d63678..846a64bcfdf 100644 --- a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/node/TableScanNode.java +++ b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/node/TableScanNode.java @@ -164,6 +164,13 @@ public class TableScanNode extends SourceNode { } ReadWriteIOUtils.write(scanOrder.ordinal(), byteBuffer); + + if (pushDownPredicate != null) { + ReadWriteIOUtils.write(true, byteBuffer); + Expression.serialize(pushDownPredicate, byteBuffer); + } else { + ReadWriteIOUtils.write(false, byteBuffer); + } } @Override @@ -194,6 +201,13 @@ public class TableScanNode extends SourceNode { } ReadWriteIOUtils.write(scanOrder.ordinal(), stream); + + if (pushDownPredicate != null) { + ReadWriteIOUtils.write(true, stream); + Expression.serialize(pushDownPredicate, stream); + } else { + ReadWriteIOUtils.write(false, stream); + } } public static TableScanNode deserialize(ByteBuffer byteBuffer) { @@ -226,6 +240,12 @@ public class TableScanNode extends SourceNode { Ordering scanOrder = Ordering.values()[ReadWriteIOUtils.readInt(byteBuffer)]; + Expression pushDownPredicate = null; + boolean hasPushDownPredicate = ReadWriteIOUtils.readBool(byteBuffer); + if (hasPushDownPredicate) { + pushDownPredicate = Expression.deserialize(byteBuffer); + } + PlanNodeId planNodeId = PlanNodeId.deserialize(byteBuffer); return new TableScanNode( @@ -236,7 +256,7 @@ public class TableScanNode extends SourceNode { deviceEntries, idAndAttributeIndexMap, scanOrder, - null); + pushDownPredicate); } @Override diff --git a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/optimizations/FilterScanCombine.java b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/optimizations/FilterScanCombine.java new file mode 100644 index 00000000000..e02fa012123 --- /dev/null +++ b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/optimizations/FilterScanCombine.java @@ -0,0 +1,227 @@ +/* + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.iotdb.db.queryengine.plan.relational.planner.optimizations; + +import org.apache.iotdb.db.queryengine.common.MPPQueryContext; +import org.apache.iotdb.db.queryengine.common.SessionInfo; +import org.apache.iotdb.db.queryengine.plan.analyze.IPartitionFetcher; +import org.apache.iotdb.db.queryengine.plan.planner.plan.node.PlanNode; +import org.apache.iotdb.db.queryengine.plan.planner.plan.node.PlanVisitor; +import org.apache.iotdb.db.queryengine.plan.planner.plan.node.process.MultiChildProcessNode; +import org.apache.iotdb.db.queryengine.plan.planner.plan.node.process.SingleChildProcessNode; +import org.apache.iotdb.db.queryengine.plan.relational.analyzer.Analysis; +import org.apache.iotdb.db.queryengine.plan.relational.analyzer.predicate.PredicateCombineIntoTableScanChecker; +import org.apache.iotdb.db.queryengine.plan.relational.analyzer.predicate.PredicatePushIntoMetadataChecker; +import org.apache.iotdb.db.queryengine.plan.relational.metadata.Metadata; +import org.apache.iotdb.db.queryengine.plan.relational.planner.Symbol; +import org.apache.iotdb.db.queryengine.plan.relational.planner.node.FilterNode; +import org.apache.iotdb.db.queryengine.plan.relational.planner.node.TableScanNode; +import org.apache.iotdb.db.queryengine.plan.relational.sql.tree.Expression; +import org.apache.iotdb.db.queryengine.plan.relational.sql.tree.FunctionCall; +import org.apache.iotdb.db.queryengine.plan.relational.sql.tree.LogicalExpression; +import org.apache.iotdb.db.queryengine.plan.relational.sql.tree.Node; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.List; +import java.util.Set; +import java.util.stream.Collectors; + +import static org.apache.iotdb.commons.schema.table.column.TsTableColumnCategory.MEASUREMENT; + +/** + * After the optimized rule {@link SimplifyExpressions} finished, predicate expression in FilterNode + * has been transformed to conjunctive normal forms(CNF). + * + * <p>In this class, we examine each expression in CNFs, determine how to use it, in metadata query, + * or pushed down into ScanOperators, or it can only be used in FilterNode above with TableScanNode. + * + * <p>Notice that, when aggregation, multi-table, join are introduced, this optimization rule need + * to be adapted. + */ +public class FilterScanCombine implements RelationalPlanOptimizer { + + @Override + public PlanNode optimize( + PlanNode planNode, + Analysis analysis, + Metadata metadata, + IPartitionFetcher partitionFetcher, + SessionInfo sessionInfo, + MPPQueryContext queryContext) { + + if (!analysis.hasValueFilter()) { + return planNode; + } + + return planNode.accept(new Rewriter(), new RewriterContext(queryContext)); + } + + private static class Rewriter extends PlanVisitor<PlanNode, RewriterContext> { + + @Override + public PlanNode visitPlan(PlanNode node, RewriterContext context) { + throw new IllegalArgumentException( + String.format("Unexpected plan node: %s in TableModel PredicatePushDown", node)); + } + + @Override + public PlanNode visitSingleChildProcess(SingleChildProcessNode node, RewriterContext context) { + PlanNode rewrittenChild = node.getChild().accept(this, context); + node.setChild(rewrittenChild); + return node; + } + + @Override + public PlanNode visitMultiChildProcess(MultiChildProcessNode node, RewriterContext context) { + List<PlanNode> rewrittenChildren = new ArrayList<>(); + for (PlanNode child : node.getChildren()) { + rewrittenChildren.add(child.accept(this, context)); + } + node.setChildren(rewrittenChildren); + return node; + } + + @Override + public PlanNode visitFilter(FilterNode node, RewriterContext context) { + context.filterNode = node; + + if (node.getPredicate() != null) { + // when exist diff function, predicate can not be pushed down + if (containsDiffFunction(node.getPredicate())) { + context.pushDownPredicate = null; + return node; + } + + context.pushDownPredicate = node.getPredicate(); + return node.getChild().accept(this, context); + } else { + throw new IllegalStateException( + "Filter node has no predicate, node: " + node.getPlanNodeId()); + } + } + + @Override + public PlanNode visitTableScan(TableScanNode node, RewriterContext context) { + // has diff in FilterNode + if (context.pushDownPredicate == null) { + node.setPushDownPredicate(null); + return node; + } + + context.queryContext.setTableModelPredicateExpressions( + splitConjunctionExpressions(context, node)); + + // exist expressions can push down to scan operator + if (!context.queryContext.getTableModelPredicateExpressions().get(1).isEmpty()) { + List<Expression> expressions = + context.queryContext.getTableModelPredicateExpressions().get(1); + node.setPushDownPredicate( + expressions.size() == 1 + ? expressions.get(0) + : new LogicalExpression(LogicalExpression.Operator.AND, expressions)); + } else { + node.setPushDownPredicate(null); + } + + // exist expressions can not push down to scan operator + if (!context.queryContext.getTableModelPredicateExpressions().get(2).isEmpty()) { + List<Expression> expressions = + context.queryContext.getTableModelPredicateExpressions().get(2); + return new FilterNode( + context.queryContext.getQueryId().genPlanNodeId(), + node, + expressions.size() == 1 + ? expressions.get(0) + : new LogicalExpression(LogicalExpression.Operator.AND, expressions)); + } + + return node; + } + } + + private static List<List<Expression>> splitConjunctionExpressions( + RewriterContext context, TableScanNode node) { + Expression predicate = context.pushDownPredicate; + + Set<String> idOrAttributeColumnNames = + node.getIdAndAttributeIndexMap().keySet().stream() + .map(Symbol::getName) + .collect(Collectors.toSet()); + + Set<String> measurementColumnNames = + node.getAssignments().entrySet().stream() + .filter(e -> MEASUREMENT.equals(e.getValue().getColumnCategory())) + .map(e -> e.getKey().getName()) + .collect(Collectors.toSet()); + + List<Expression> metadataExpressions = new ArrayList<>(); + List<Expression> expressionsCanPushDown = new ArrayList<>(); + List<Expression> expressionsCannotPushDown = new ArrayList<>(); + + if (predicate instanceof LogicalExpression + && ((LogicalExpression) predicate).getOperator() == LogicalExpression.Operator.AND) { + + for (Expression expression : ((LogicalExpression) predicate).getTerms()) { + if (PredicatePushIntoMetadataChecker.check(idOrAttributeColumnNames, expression)) { + metadataExpressions.add(expression); + } else if (PredicateCombineIntoTableScanChecker.check(measurementColumnNames, expression)) { + expressionsCanPushDown.add(expression); + } else { + expressionsCannotPushDown.add(expression); + } + } + + return Arrays.asList(metadataExpressions, expressionsCanPushDown, expressionsCannotPushDown); + } + + if (PredicatePushIntoMetadataChecker.check(idOrAttributeColumnNames, predicate)) { + metadataExpressions.add(predicate); + } else if (PredicateCombineIntoTableScanChecker.check(measurementColumnNames, predicate)) { + expressionsCanPushDown.add(predicate); + } else { + expressionsCannotPushDown.add(predicate); + } + + return Arrays.asList(metadataExpressions, expressionsCanPushDown, expressionsCannotPushDown); + } + + static boolean containsDiffFunction(Expression expression) { + if (expression instanceof FunctionCall + && "diff".equalsIgnoreCase(((FunctionCall) expression).getName().toString())) { + return true; + } + + if (!expression.getChildren().isEmpty()) { + for (Node node : expression.getChildren()) { + if (containsDiffFunction((Expression) node)) { + return true; + } + } + } + + return false; + } + + private static class RewriterContext { + Expression pushDownPredicate; + MPPQueryContext queryContext; + FilterNode filterNode; + + public RewriterContext(MPPQueryContext queryContext) { + this.queryContext = queryContext; + } + } +} diff --git a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/optimizations/IndexScan.java b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/optimizations/IndexScan.java index fd3fe00bd9f..e2f4a1f3be5 100644 --- a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/optimizations/IndexScan.java +++ b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/optimizations/IndexScan.java @@ -27,7 +27,6 @@ import org.apache.iotdb.db.queryengine.plan.analyze.IPartitionFetcher; import org.apache.iotdb.db.queryengine.plan.planner.plan.node.PlanNode; import org.apache.iotdb.db.queryengine.plan.planner.plan.node.PlanVisitor; import org.apache.iotdb.db.queryengine.plan.relational.analyzer.Analysis; -import org.apache.iotdb.db.queryengine.plan.relational.analyzer.predicate.PredicatePushIntoIndexScanChecker; import org.apache.iotdb.db.queryengine.plan.relational.metadata.DeviceEntry; import org.apache.iotdb.db.queryengine.plan.relational.metadata.Metadata; import org.apache.iotdb.db.queryengine.plan.relational.metadata.QualifiedObjectName; @@ -35,7 +34,6 @@ import org.apache.iotdb.db.queryengine.plan.relational.planner.Symbol; import org.apache.iotdb.db.queryengine.plan.relational.planner.node.FilterNode; import org.apache.iotdb.db.queryengine.plan.relational.planner.node.TableScanNode; import org.apache.iotdb.db.queryengine.plan.relational.sql.tree.Expression; -import org.apache.iotdb.db.queryengine.plan.relational.sql.tree.LogicalExpression; import org.apache.tsfile.file.metadata.StringArrayDeviceID; import org.apache.tsfile.read.filter.basic.Filter; @@ -85,26 +83,37 @@ public class IndexScan implements RelationalPlanOptimizer { @Override public PlanNode visitFilter(FilterNode node, RewriterContext context) { context.setPredicate(node.getPredicate()); + context.setFilterNode(node); node.getChild().accept(this, context); return node; } @Override public PlanNode visitTableScan(TableScanNode node, RewriterContext context) { - List<String> attributeColumns = - node.getAssignments().entrySet().stream() - .filter(e -> e.getValue().getColumnCategory().equals(ATTRIBUTE)) - .map(e -> e.getKey().getName()) - .collect(Collectors.toList()); - List<Expression> conjExpressions = getConjunctionExpressions(context.getPredicate(), node); + // only when exist diff predicate in FilterNode, context.predicate will not equal null + if (context.predicate == null) { + context.predicate = node.getPushDownPredicate(); + } + + List<Expression> metadataExpressions = + context.queryContext.getTableModelPredicateExpressions() == null + || context.queryContext.getTableModelPredicateExpressions().get(0).isEmpty() + ? Collections.emptyList() + : context.queryContext.getTableModelPredicateExpressions().get(0); String dbName = context.getSessionInfo().getDatabaseName().get(); + List<String> attributeColumns = + node.getOutputSymbols().stream() + .filter( + symbol -> ATTRIBUTE.equals(node.getAssignments().get(symbol).getColumnCategory())) + .map(Symbol::getName) + .collect(Collectors.toList()); List<DeviceEntry> deviceEntries = context .getMetadata() .indexScan( new QualifiedObjectName(dbName, node.getQualifiedTableName()), - conjExpressions, + metadataExpressions, attributeColumns); node.setDeviceEntries(deviceEntries); @@ -151,37 +160,6 @@ public class IndexScan implements RelationalPlanOptimizer { } } - private static List<Expression> getConjunctionExpressions( - Expression predicate, TableScanNode node) { - if (predicate == null) { - return Collections.emptyList(); - } - - Set<String> idOrAttributeColumnNames = - node.getIdAndAttributeIndexMap().keySet().stream() - .map(Symbol::getName) - .collect(Collectors.toSet()); - if (predicate instanceof LogicalExpression - && ((LogicalExpression) predicate).getOperator() == LogicalExpression.Operator.AND) { - List<Expression> resultExpressions = new ArrayList<>(); - for (Expression subExpression : ((LogicalExpression) predicate).getTerms()) { - if (Boolean.TRUE.equals( - new PredicatePushIntoIndexScanChecker(idOrAttributeColumnNames) - .process(subExpression))) { - resultExpressions.add(subExpression); - } - } - return resultExpressions; - } - - if (Boolean.FALSE.equals( - new PredicatePushIntoIndexScanChecker(idOrAttributeColumnNames).process(predicate))) { - return Collections.emptyList(); - } else { - return Collections.singletonList(predicate); - } - } - private static DataPartition fetchDataPartitionByDevices( Set<String> deviceSet, String database, @@ -219,6 +197,7 @@ public class IndexScan implements RelationalPlanOptimizer { private final Analysis analysis; private final IPartitionFetcher partitionFetcher; private final MPPQueryContext queryContext; + private FilterNode filterNode; RewriterContext( Expression predicate, @@ -266,5 +245,13 @@ public class IndexScan implements RelationalPlanOptimizer { public MPPQueryContext getQueryContext() { return queryContext; } + + public FilterNode getFilterNode() { + return filterNode; + } + + public void setFilterNode(FilterNode filterNode) { + this.filterNode = filterNode; + } } } diff --git a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/optimizations/PredicatePushDown.java b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/optimizations/PredicatePushDown.java deleted file mode 100644 index ae05611ce08..00000000000 --- a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/optimizations/PredicatePushDown.java +++ /dev/null @@ -1,125 +0,0 @@ -/* - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package org.apache.iotdb.db.queryengine.plan.relational.planner.optimizations; - -import org.apache.iotdb.db.queryengine.common.MPPQueryContext; -import org.apache.iotdb.db.queryengine.common.SessionInfo; -import org.apache.iotdb.db.queryengine.plan.analyze.IPartitionFetcher; -import org.apache.iotdb.db.queryengine.plan.planner.plan.node.PlanNode; -import org.apache.iotdb.db.queryengine.plan.planner.plan.node.PlanVisitor; -import org.apache.iotdb.db.queryengine.plan.planner.plan.node.process.MultiChildProcessNode; -import org.apache.iotdb.db.queryengine.plan.planner.plan.node.process.SingleChildProcessNode; -import org.apache.iotdb.db.queryengine.plan.relational.analyzer.Analysis; -import org.apache.iotdb.db.queryengine.plan.relational.metadata.Metadata; -import org.apache.iotdb.db.queryengine.plan.relational.planner.node.FilterNode; -import org.apache.iotdb.db.queryengine.plan.relational.planner.node.TableScanNode; -import org.apache.iotdb.db.queryengine.plan.relational.sql.tree.Expression; -import org.apache.iotdb.db.queryengine.plan.relational.sql.tree.FunctionCall; -import org.apache.iotdb.db.queryengine.plan.relational.sql.tree.Node; - -import java.util.ArrayList; -import java.util.List; - -/** Push down predicate to TableScanNode as possible. */ -public class PredicatePushDown implements RelationalPlanOptimizer { - - @Override - public PlanNode optimize( - PlanNode planNode, - Analysis analysis, - Metadata metadata, - IPartitionFetcher partitionFetcher, - SessionInfo sessionInfo, - MPPQueryContext context) { - - if (!analysis.hasValueFilter()) { - return planNode; - } - - return planNode.accept(new Rewriter(), new RewriterContext()); - } - - private static class Rewriter extends PlanVisitor<PlanNode, RewriterContext> { - - @Override - public PlanNode visitPlan(PlanNode node, RewriterContext context) { - throw new IllegalArgumentException( - String.format("Unexpected plan node: %s in TableModel PredicatePushDown", node)); - } - - @Override - public PlanNode visitSingleChildProcess(SingleChildProcessNode node, RewriterContext context) { - PlanNode rewrittenChild = node.getChild().accept(this, context); - node.setChild(rewrittenChild); - return node; - } - - @Override - public PlanNode visitMultiChildProcess(MultiChildProcessNode node, RewriterContext context) { - List<PlanNode> rewrittenChildren = new ArrayList<>(); - for (PlanNode child : node.getChildren()) { - rewrittenChildren.add(child.accept(this, context)); - } - node.setChildren(rewrittenChildren); - return node; - } - - @Override - public PlanNode visitFilter(FilterNode node, RewriterContext context) { - if (node.getPredicate() != null) { - // when exist diff function, predicate can not be pushed down - if (containsDiffFunction(node.getPredicate())) { - return node; - } - - context.pushDownPredicate = node.getPredicate(); - node.getChild().accept(this, context); - - // remove FilterNode after push down - return node.getChild(); - } - - node.getChild().accept(this, context); - return node; - } - - @Override - public PlanNode visitTableScan(TableScanNode node, RewriterContext context) { - node.setPushDownPredicate(context.pushDownPredicate); - return node; - } - } - - static boolean containsDiffFunction(Expression expression) { - if (expression instanceof FunctionCall - && "diff".equalsIgnoreCase(((FunctionCall) expression).getName().toString())) { - return true; - } - - if (!expression.getChildren().isEmpty()) { - for (Node node : expression.getChildren()) { - if (containsDiffFunction((Expression) node)) { - return true; - } - } - } - - return false; - } - - private static class RewriterContext { - Expression pushDownPredicate; - } -} diff --git a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/optimizations/PruneUnUsedColumns.java b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/optimizations/PruneUnUsedColumns.java index d6310c37dc0..c3b0a12c01b 100644 --- a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/optimizations/PruneUnUsedColumns.java +++ b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/optimizations/PruneUnUsedColumns.java @@ -14,6 +14,7 @@ package org.apache.iotdb.db.queryengine.plan.relational.planner.optimizations; +import org.apache.iotdb.commons.schema.table.column.TsTableColumnCategory; import org.apache.iotdb.db.queryengine.common.MPPQueryContext; import org.apache.iotdb.db.queryengine.common.SessionInfo; import org.apache.iotdb.db.queryengine.plan.analyze.IPartitionFetcher; @@ -119,6 +120,19 @@ public class PruneUnUsedColumns implements RelationalPlanOptimizer { } node.setOutputSymbols(newOutputSymbols); node.setAssignments(newAssignments); + + int IDIdx = 0, attributeIdx = 0; + Map<Symbol, Integer> idAndAttributeIndexMap = new HashMap<>(node.getAssignments().size()); + for (Symbol symbol : node.getOutputSymbols()) { + ColumnSchema columnSchema = node.getAssignments().get(symbol); + if (TsTableColumnCategory.ID.equals(columnSchema.getColumnCategory())) { + idAndAttributeIndexMap.put(symbol, IDIdx++); + } else if (TsTableColumnCategory.ATTRIBUTE.equals(columnSchema.getColumnCategory())) { + idAndAttributeIndexMap.put(symbol, attributeIdx++); + } + } + node.setIdAndAttributeIndexMap(idAndAttributeIndexMap); + return node; } } diff --git a/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/queryengine/plan/relational/analyzer/AnalyzerTest.java b/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/queryengine/plan/relational/analyzer/AnalyzerTest.java index a2a3b56fc8d..681205bb499 100644 --- a/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/queryengine/plan/relational/analyzer/AnalyzerTest.java +++ b/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/queryengine/plan/relational/analyzer/AnalyzerTest.java @@ -51,6 +51,7 @@ import org.apache.iotdb.db.queryengine.plan.relational.planner.node.ProjectNode; import org.apache.iotdb.db.queryengine.plan.relational.planner.node.TableScanNode; import org.apache.iotdb.db.queryengine.plan.relational.security.AccessControl; import org.apache.iotdb.db.queryengine.plan.relational.sql.parser.SqlParser; +import org.apache.iotdb.db.queryengine.plan.relational.sql.tree.LogicalExpression; import org.apache.iotdb.db.queryengine.plan.relational.sql.tree.Statement; import org.apache.iotdb.mpp.rpc.thrift.TRegionRouteReq; @@ -300,7 +301,7 @@ public class AnalyzerTest { context, metadata, sessionInfo, getFakePartitionFetcher(), WarningCollector.NOOP); logicalQueryPlan = logicalPlanner.plan(actualAnalysis); rootNode = logicalQueryPlan.getRootNode(); - PlanNode tableScanNode = rootNode.getChildren().get(0).getChildren().get(0); + tableScanNode = (TableScanNode) rootNode.getChildren().get(0).getChildren().get(0); assertEquals( Arrays.asList("time", "tag1", "attr1", "s1"), tableScanNode.getOutputColumnNames()); @@ -315,7 +316,7 @@ public class AnalyzerTest { context, metadata, sessionInfo, getFakePartitionFetcher(), WarningCollector.NOOP); logicalQueryPlan = logicalPlanner.plan(actualAnalysis); rootNode = logicalQueryPlan.getRootNode(); - tableScanNode = rootNode.getChildren().get(0).getChildren().get(0); + tableScanNode = (TableScanNode) rootNode.getChildren().get(0).getChildren().get(0); assertEquals( Arrays.asList("time", "tag1", "tag2", "attr1", "s1", "s2"), tableScanNode.getOutputColumnNames()); @@ -330,10 +331,26 @@ public class AnalyzerTest { context, metadata, sessionInfo, getFakePartitionFetcher(), WarningCollector.NOOP) .plan(actualAnalysis); rootNode = logicalQueryPlan.getRootNode(); - tableScanNode = rootNode.getChildren().get(0).getChildren().get(0); + assertTrue(rootNode.getChildren().get(0).getChildren().get(0) instanceof FilterNode); + tableScanNode = + (TableScanNode) rootNode.getChildren().get(0).getChildren().get(0).getChildren().get(0); assertEquals( Arrays.asList("time", "tag1", "attr2", "s1", "s2", "s3"), tableScanNode.getOutputColumnNames()); + + // 4. project with not all attributes, to test the rightness of PruneUnUsedColumns + sql = "SELECT tag2, attr2, s2 FROM table1"; + actualAnalysis = analyzeSQL(sql, metadata); + context = new MPPQueryContext(sql, queryId, sessionInfo, null, null); + logicalQueryPlan = + new LogicalPlanner( + context, metadata, sessionInfo, getFakePartitionFetcher(), WarningCollector.NOOP) + .plan(actualAnalysis); + rootNode = logicalQueryPlan.getRootNode(); + tableScanNode = (TableScanNode) rootNode.getChildren().get(0).getChildren().get(0); + assertEquals( + Arrays.asList("time", "tag2", "attr2", "s2"), tableScanNode.getOutputColumnNames()); + assertEquals(2, tableScanNode.getIdAndAttributeIndexMap().size()); } @Test @@ -434,6 +451,36 @@ public class AnalyzerTest { rootNode = logicalQueryPlan.getRootNode(); } + @Test + public void predicatePushDownTest() throws IoTDBException { + // `is null expression`, `not expression` cannot be pushed down into TableScanOperator + sql = + "SELECT *, s1/2, s2+1 FROM table1 WHERE tag1 in ('A', 'B') and tag2 = 'C' " + + "and s2 iS NUll and S1 = 6 and s3 < 8.0 and tAG1 LIKE '%m'"; + context = new MPPQueryContext(sql, queryId, sessionInfo, null, null); + actualAnalysis = analyzeSQL(sql, metadata); + logicalQueryPlan = + new LogicalPlanner( + context, metadata, sessionInfo, getFakePartitionFetcher(), WarningCollector.NOOP) + .plan(actualAnalysis); + rootNode = logicalQueryPlan.getRootNode(); + assertTrue(rootNode instanceof OutputNode); + assertTrue(rootNode.getChildren().get(0) instanceof ProjectNode); + assertTrue(rootNode.getChildren().get(0).getChildren().get(0) instanceof FilterNode); + FilterNode filterNode = (FilterNode) rootNode.getChildren().get(0).getChildren().get(0); + assertTrue(filterNode.getPredicate() instanceof LogicalExpression); + assertEquals(3, ((LogicalExpression) filterNode.getPredicate()).getTerms().size()); + assertTrue( + rootNode.getChildren().get(0).getChildren().get(0).getChildren().get(0) + instanceof TableScanNode); + tableScanNode = + (TableScanNode) rootNode.getChildren().get(0).getChildren().get(0).getChildren().get(0); + assertTrue( + tableScanNode.getPushDownPredicate() != null + && tableScanNode.getPushDownPredicate() instanceof LogicalExpression); + assertEquals(2, ((LogicalExpression) tableScanNode.getPushDownPredicate()).getTerms().size()); + } + public static Analysis analyzeSQL(String sql, Metadata metadata) { try { SqlParser sqlParser = new SqlParser();