This is an automated email from the ASF dual-hosted git repository.
caogaofei 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 9aac8228947 add ExtractCommonPredicatesExpressionRewriter
9aac8228947 is described below
commit 9aac82289474216ed4eb361d51e8cfb15964302c
Author: Beyyes <[email protected]>
AuthorDate: Thu Apr 11 15:56:38 2024 +0800
add ExtractCommonPredicatesExpressionRewriter
---
.../plan/planner/plan/node/PlanNode.java | 5 -
.../relational/planner/RelationalPlanVisitor.java | 1 +
.../planner/ir/DefaultTraversalVisitor.java | 173 ++++++++++++++++++
.../planner/ir/DeterminismEvaluator.java | 27 +++
.../planner/ir/ExpressionTreeRewriter.java | 12 ++
.../ExtractCommonPredicatesExpressionRewriter.java | 198 +++++++++++++++++++++
.../planner/ir/NormalizeOrExpressionRewriter.java | 2 +-
.../planner/optimizations/SimplifyExpressions.java | 6 +-
8 files changed, 416 insertions(+), 8 deletions(-)
diff --git
a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/planner/plan/node/PlanNode.java
b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/planner/plan/node/PlanNode.java
index d63c60e9c11..877db9bf543 100644
---
a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/planner/plan/node/PlanNode.java
+++
b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/planner/plan/node/PlanNode.java
@@ -22,7 +22,6 @@ package
org.apache.iotdb.db.queryengine.plan.planner.plan.node;
import
org.apache.iotdb.commons.exception.runtime.SerializationRunTimeException;
import org.apache.iotdb.consensus.common.request.IConsensusRequest;
import org.apache.iotdb.db.queryengine.plan.analyze.TypeProvider;
-import
org.apache.iotdb.db.queryengine.plan.relational.planner.RelationalPlanVisitor;
import org.apache.iotdb.tsfile.utils.PublicBAOS;
import org.apache.iotdb.tsfile.utils.ReadWriteIOUtils;
@@ -128,10 +127,6 @@ public abstract class PlanNode implements
IConsensusRequest {
return visitor.visitPlan(this, context);
}
- public <R, C> R accept(RelationalPlanVisitor<R, C> visitor, C context) {
- return visitor.visitPlan(this, context);
- }
-
public void serialize(ByteBuffer byteBuffer) {
serializeAttributes(byteBuffer);
id.serialize(byteBuffer);
diff --git
a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/RelationalPlanVisitor.java
b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/RelationalPlanVisitor.java
index e36dbddf0fa..e6c4ba583c8 100644
---
a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/RelationalPlanVisitor.java
+++
b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/RelationalPlanVisitor.java
@@ -31,6 +31,7 @@ import
org.apache.iotdb.db.queryengine.plan.relational.planner.node.SortNode;
import
org.apache.iotdb.db.queryengine.plan.relational.planner.node.TableScanNode;
import org.apache.iotdb.db.queryengine.plan.relational.planner.node.TopKNode;
+/** If it's needed to use RelationalPlanVisitor? */
public abstract class RelationalPlanVisitor<R, C> {
public abstract R visitPlan(PlanNode node, C context);
diff --git
a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/ir/DefaultTraversalVisitor.java
b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/ir/DefaultTraversalVisitor.java
new file mode 100644
index 00000000000..ee301b97a4d
--- /dev/null
+++
b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/ir/DefaultTraversalVisitor.java
@@ -0,0 +1,173 @@
+package org.apache.iotdb.db.queryengine.plan.relational.planner.ir;
+
+import org.apache.iotdb.db.relational.sql.tree.ArithmeticBinaryExpression;
+import org.apache.iotdb.db.relational.sql.tree.BetweenPredicate;
+import org.apache.iotdb.db.relational.sql.tree.Cast;
+import org.apache.iotdb.db.relational.sql.tree.CoalesceExpression;
+import org.apache.iotdb.db.relational.sql.tree.ComparisonExpression;
+import org.apache.iotdb.db.relational.sql.tree.Expression;
+import org.apache.iotdb.db.relational.sql.tree.FunctionCall;
+import org.apache.iotdb.db.relational.sql.tree.InPredicate;
+import org.apache.iotdb.db.relational.sql.tree.IsNullPredicate;
+import org.apache.iotdb.db.relational.sql.tree.LogicalExpression;
+import org.apache.iotdb.db.relational.sql.tree.NotExpression;
+import org.apache.iotdb.db.relational.sql.tree.NullIfExpression;
+import org.apache.iotdb.db.relational.sql.tree.Row;
+import org.apache.iotdb.db.relational.sql.tree.SearchedCaseExpression;
+import org.apache.iotdb.db.relational.sql.tree.SimpleCaseExpression;
+import org.apache.iotdb.db.relational.sql.tree.WhenClause;
+
+public abstract class DefaultTraversalVisitor<C> extends IrVisitor<Void, C> {
+ @Override
+ protected Void visitCast(Cast node, C context) {
+ process(node.getExpression(), context);
+ return null;
+ }
+
+ @Override
+ protected Void visitArithmeticBinary(ArithmeticBinaryExpression node, C
context) {
+ process(node.getLeft(), context);
+ process(node.getRight(), context);
+
+ return null;
+ }
+
+ @Override
+ protected Void visitBetweenPredicate(BetweenPredicate node, C context) {
+ process(node.getValue(), context);
+ process(node.getMin(), context);
+ process(node.getMax(), context);
+
+ return null;
+ }
+
+ @Override
+ protected Void visitCoalesceExpression(CoalesceExpression node, C context) {
+ for (Expression operand : node.getOperands()) {
+ process(operand, context);
+ }
+
+ return null;
+ }
+
+ // @Override
+ // protected Void visitSubscriptExpression(SubscriptExpression node, C
context)
+ // {
+ // process(node.getBase(), context);
+ // process(node.getIndex(), context);
+ //
+ // return null;
+ // }
+
+ @Override
+ protected Void visitComparisonExpression(ComparisonExpression node, C
context) {
+ process(node.getLeft(), context);
+ process(node.getRight(), context);
+
+ return null;
+ }
+
+ @Override
+ protected Void visitInPredicate(InPredicate node, C context) {
+ process(node.getValue(), context);
+ process(node.getValueList(), context);
+
+ return null;
+ }
+
+ @Override
+ protected Void visitFunctionCall(FunctionCall node, C context) {
+ for (Expression argument : node.getArguments()) {
+ process(argument, context);
+ }
+
+ return null;
+ }
+
+ @Override
+ protected Void visitSimpleCaseExpression(SimpleCaseExpression node, C
context) {
+ process(node.getOperand(), context);
+ for (WhenClause clause : node.getWhenClauses()) {
+ process(clause.getOperand(), context);
+ process(clause.getResult(), context);
+ }
+
+ node.getDefaultValue().ifPresent(value -> process(value, context));
+
+ return null;
+ }
+
+ @Override
+ protected Void visitNullIfExpression(NullIfExpression node, C context) {
+ process(node.getFirst(), context);
+ process(node.getSecond(), context);
+
+ return null;
+ }
+
+ // @Override
+ // protected Void visitBindExpression(BindExpression node, C context)
+ // {
+ // for (Expression value : node.getValues()) {
+ // process(value, context);
+ // }
+ // process(node.getFunction(), context);
+ //
+ // return null;
+ // }
+
+ // @Override
+ // protected Void visitArithmeticNegation(ArithmeticNegation node, C
context)
+ // {
+ // process(node.getValue(), context);
+ // return null;
+ // }
+
+ @Override
+ protected Void visitNotExpression(NotExpression node, C context) {
+ process(node.getValue(), context);
+ return null;
+ }
+
+ @Override
+ protected Void visitSearchedCaseExpression(SearchedCaseExpression node, C
context) {
+ for (WhenClause clause : node.getWhenClauses()) {
+ process(clause.getOperand(), context);
+ process(clause.getResult(), context);
+ }
+ node.getDefaultValue().ifPresent(value -> process(value, context));
+
+ return null;
+ }
+
+ @Override
+ protected Void visitIsNullPredicate(IsNullPredicate node, C context) {
+ process(node.getValue(), context);
+ return null;
+ }
+
+ @Override
+ protected Void visitLogicalExpression(LogicalExpression node, C context) {
+ for (Expression child : node.getTerms()) {
+ process(child, context);
+ }
+
+ return null;
+ }
+
+ @Override
+ protected Void visitRow(Row node, C context) {
+ for (Expression expression : node.getItems()) {
+ process(expression, context);
+ }
+ return null;
+ }
+
+ // @Override
+ // protected Void visitLambdaExpression(LambdaExpression node, C context)
+ // {
+ // process(node.getBody(), context);
+ //
+ // return null;
+ // }
+}
diff --git
a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/ir/DeterminismEvaluator.java
b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/ir/DeterminismEvaluator.java
new file mode 100644
index 00000000000..4b2f57507e9
--- /dev/null
+++
b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/ir/DeterminismEvaluator.java
@@ -0,0 +1,27 @@
+package org.apache.iotdb.db.queryengine.plan.relational.planner.ir;
+
+import org.apache.iotdb.db.relational.sql.tree.Expression;
+import org.apache.iotdb.db.relational.sql.tree.FunctionCall;
+
+import java.util.concurrent.atomic.AtomicBoolean;
+
+public final class DeterminismEvaluator {
+ private DeterminismEvaluator() {}
+
+ public static boolean isDeterministic(Expression expression) {
+ AtomicBoolean deterministic = new AtomicBoolean(true);
+ new Visitor().process(expression, deterministic);
+ return deterministic.get();
+ }
+
+ private static class Visitor extends DefaultTraversalVisitor<AtomicBoolean> {
+ @Override
+ protected Void visitFunctionCall(FunctionCall node, AtomicBoolean
deterministic) {
+ // if (!node.getFunction().isDeterministic()) {
+ // deterministic.set(false);
+ // return null;
+ // }
+ return super.visitFunctionCall(node, deterministic);
+ }
+ }
+}
diff --git
a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/ir/ExpressionTreeRewriter.java
b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/ir/ExpressionTreeRewriter.java
index b39bf4482ca..e2367eb8602 100644
---
a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/ir/ExpressionTreeRewriter.java
+++
b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/ir/ExpressionTreeRewriter.java
@@ -25,8 +25,10 @@ import
org.apache.iotdb.db.relational.sql.tree.CoalesceExpression;
import org.apache.iotdb.db.relational.sql.tree.ComparisonExpression;
import org.apache.iotdb.db.relational.sql.tree.Expression;
import org.apache.iotdb.db.relational.sql.tree.FunctionCall;
+import org.apache.iotdb.db.relational.sql.tree.Identifier;
import org.apache.iotdb.db.relational.sql.tree.InPredicate;
import org.apache.iotdb.db.relational.sql.tree.IsNullPredicate;
+import org.apache.iotdb.db.relational.sql.tree.Literal;
import org.apache.iotdb.db.relational.sql.tree.LogicalExpression;
import org.apache.iotdb.db.relational.sql.tree.NotExpression;
import org.apache.iotdb.db.relational.sql.tree.NullIfExpression;
@@ -512,6 +514,16 @@ public final class ExpressionTreeRewriter<C> {
return node;
}
+
+ @Override
+ protected Expression visitIdentifier(Identifier node, Context<C> context) {
+ return node;
+ }
+
+ @Override
+ protected Expression visitLiteral(Literal node, Context<C> context) {
+ return node;
+ }
}
public static class Context<C> {
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
new file mode 100644
index 00000000000..154eff8c547
--- /dev/null
+++
b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/ir/ExtractCommonPredicatesExpressionRewriter.java
@@ -0,0 +1,198 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you 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.ir;
+
+import org.apache.iotdb.db.relational.sql.tree.Expression;
+import org.apache.iotdb.db.relational.sql.tree.LogicalExpression;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Sets;
+
+import java.util.Collection;
+import java.util.List;
+import java.util.Set;
+
+import static com.google.common.collect.ImmutableList.toImmutableList;
+import static java.util.Collections.emptySet;
+import static java.util.stream.Collectors.toList;
+import static java.util.stream.Collectors.toSet;
+import static
org.apache.iotdb.db.queryengine.plan.relational.planner.ir.DeterminismEvaluator.isDeterministic;
+import static
org.apache.iotdb.db.queryengine.plan.relational.planner.ir.IrUtils.combinePredicates;
+import static
org.apache.iotdb.db.queryengine.plan.relational.planner.ir.IrUtils.extractPredicates;
+import static
org.apache.iotdb.db.relational.sql.tree.LogicalExpression.Operator.OR;
+
+public final class ExtractCommonPredicatesExpressionRewriter {
+
+ public static Expression extractCommonPredicates(Expression expression) {
+ return ExpressionTreeRewriter.rewriteWith(new Visitor(), expression,
NodeContext.ROOT_NODE);
+ }
+
+ private ExtractCommonPredicatesExpressionRewriter() {}
+
+ private static class Visitor extends ExpressionRewriter<NodeContext> {
+ @Override
+ protected Expression rewriteExpression(
+ Expression node, NodeContext context,
ExpressionTreeRewriter<NodeContext> treeRewriter) {
+ if (context.isRootNode()) {
+ return treeRewriter.rewrite(node, NodeContext.NOT_ROOT_NODE);
+ }
+
+ return null;
+ }
+
+ @Override
+ public Expression rewriteLogicalExpression(
+ LogicalExpression node,
+ NodeContext context,
+ ExpressionTreeRewriter<NodeContext> treeRewriter) {
+ Expression expression =
+ combinePredicates(
+ node.getOperator(),
+ extractPredicates(node.getOperator(), node).stream()
+ .map(
+ subExpression ->
+ treeRewriter.rewrite(subExpression,
NodeContext.NOT_ROOT_NODE))
+ .collect(toImmutableList()));
+
+ if (!(expression instanceof LogicalExpression)) {
+ return expression;
+ }
+
+ Expression simplified = extractCommonPredicates((LogicalExpression)
expression);
+
+ // Prefer AND LogicalBinaryExpression at the root if possible
+ if (context.isRootNode()
+ && simplified instanceof LogicalExpression
+ && ((LogicalExpression) simplified).getOperator() == OR) {
+ return distributeIfPossible((LogicalExpression) simplified);
+ }
+
+ return simplified;
+ }
+
+ private Expression extractCommonPredicates(LogicalExpression node) {
+ List<List<Expression>> subPredicates = getSubPredicates(node);
+
+ Set<Expression> commonPredicates =
+ ImmutableSet.copyOf(
+ subPredicates.stream()
+ .map(this::filterDeterministicPredicates)
+ .reduce(Sets::intersection)
+ .orElse(emptySet()));
+
+ List<List<Expression>> uncorrelatedSubPredicates =
+ subPredicates.stream()
+ .map(predicateList -> removeAll(predicateList, commonPredicates))
+ .collect(toImmutableList());
+
+ LogicalExpression.Operator flippedOperator = node.getOperator().flip();
+
+ List<Expression> uncorrelatedPredicates =
+ uncorrelatedSubPredicates.stream()
+ .map(predicate -> combinePredicates(flippedOperator, predicate))
+ .collect(toImmutableList());
+ Expression combinedUncorrelatedPredicates =
+ combinePredicates(node.getOperator(), uncorrelatedPredicates);
+
+ return combinePredicates(
+ flippedOperator,
+ ImmutableList.<Expression>builder()
+ .addAll(commonPredicates)
+ .add(combinedUncorrelatedPredicates)
+ .build());
+ }
+
+ private static List<List<Expression>> getSubPredicates(LogicalExpression
expression) {
+ return extractPredicates(expression.getOperator(), expression).stream()
+ .map(
+ predicate ->
+ predicate instanceof LogicalExpression
+ ? extractPredicates((LogicalExpression) predicate)
+ : ImmutableList.of(predicate))
+ .collect(toImmutableList());
+ }
+
+ /**
+ * Applies the boolean distributive property.
+ *
+ * <p>For example: ( A & B ) | ( C & D ) => ( A | C ) & ( A | D ) & ( B |
C ) & ( B | D)
+ *
+ * <p>Returns the original expression if the expression is
non-deterministic or if the
+ * distribution will expand the expression by too much.
+ */
+ private Expression distributeIfPossible(LogicalExpression expression) {
+ if (!isDeterministic(expression)) {
+ // Do not distribute boolean expressions if there are any
non-deterministic elements
+ // TODO: This can be optimized further if non-deterministic elements
are not repeated
+ return expression;
+ }
+ List<Set<Expression>> subPredicates =
+
getSubPredicates(expression).stream().map(ImmutableSet::copyOf).collect(toList());
+
+ int originalBaseExpressions =
subPredicates.stream().mapToInt(Set::size).sum();
+
+ int newBaseExpressions;
+ try {
+ newBaseExpressions =
+ Math.multiplyExact(
+
subPredicates.stream().mapToInt(Set::size).reduce(Math::multiplyExact).getAsInt(),
+ subPredicates.size());
+ } catch (ArithmeticException e) {
+ // Integer overflow from multiplication means there are too many
expressions
+ return expression;
+ }
+
+ if (newBaseExpressions > originalBaseExpressions * 2) {
+ // Do not distribute boolean expressions if it would create 2x more
base expressions
+ // (e.g. A, B, C, D from the above example). This is just an arbitrary
heuristic to
+ // avoid cross product expression explosion.
+ return expression;
+ }
+
+ Set<List<Expression>> crossProduct =
Sets.cartesianProduct(subPredicates);
+
+ return combinePredicates(
+ expression.getOperator().flip(),
+ crossProduct.stream()
+ .map(expressions -> combinePredicates(expression.getOperator(),
expressions))
+ .collect(toImmutableList()));
+ }
+
+ private Set<Expression> filterDeterministicPredicates(List<Expression>
predicates) {
+ return predicates.stream().filter(expression ->
isDeterministic(expression)).collect(toSet());
+ }
+
+ private static <T> List<T> removeAll(Collection<T> collection,
Collection<T> elementsToRemove) {
+ return collection.stream()
+ .filter(element -> !elementsToRemove.contains(element))
+ .collect(toImmutableList());
+ }
+ }
+
+ private enum NodeContext {
+ ROOT_NODE,
+ NOT_ROOT_NODE;
+
+ boolean isRootNode() {
+ return this == ROOT_NODE;
+ }
+ }
+}
diff --git
a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/ir/NormalizeOrExpressionRewriter.java
b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/ir/NormalizeOrExpressionRewriter.java
index 314da530323..6d00d1b72eb 100644
---
a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/ir/NormalizeOrExpressionRewriter.java
+++
b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/ir/NormalizeOrExpressionRewriter.java
@@ -40,8 +40,8 @@ import static
org.apache.iotdb.db.queryengine.plan.relational.planner.ir.IrUtils
import static
org.apache.iotdb.db.relational.sql.tree.ComparisonExpression.Operator.EQUAL;
import static
org.apache.iotdb.db.relational.sql.tree.LogicalExpression.Operator.AND;
-/** Transfer to conjunction normal form. */
public final class NormalizeOrExpressionRewriter {
+
public static Expression normalizeOrExpression(Expression expression) {
return ExpressionTreeRewriter.rewriteWith(new Visitor(), expression);
}
diff --git
a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/optimizations/SimplifyExpressions.java
b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/optimizations/SimplifyExpressions.java
index e9932be033f..aef419fa123 100644
---
a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/optimizations/SimplifyExpressions.java
+++
b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/optimizations/SimplifyExpressions.java
@@ -22,6 +22,7 @@ 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.relational.sql.tree.Expression;
+import static
org.apache.iotdb.db.queryengine.plan.relational.planner.ir.ExtractCommonPredicatesExpressionRewriter.extractCommonPredicates;
import static
org.apache.iotdb.db.queryengine.plan.relational.planner.ir.NormalizeOrExpressionRewriter.normalizeOrExpression;
public class SimplifyExpressions implements RelationalPlanOptimizer {
@@ -48,8 +49,9 @@ public class SimplifyExpressions implements
RelationalPlanOptimizer {
@Override
public PlanNode visitFilter(FilterNode node, RewriterContext context) {
- Expression newPredicate = normalizeOrExpression(node.getPredicate());
- node.setPredicate(newPredicate);
+ Expression predicate = normalizeOrExpression(node.getPredicate());
+ predicate = extractCommonPredicates(predicate);
+ node.setPredicate(predicate);
return node;
}
