This is an automated email from the ASF dual-hosted git repository.
alexpl pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/ignite.git
The following commit(s) were added to refs/heads/master by this push:
new ab3645496b6 IGNITE-24756 SQL Calcite: Add extraction of common part
from disjunction in conditions - Fixes #11972.
ab3645496b6 is described below
commit ab3645496b6f08189974b275e88fca8e1ad03a55
Author: Aleksey Plekhanov <[email protected]>
AuthorDate: Tue Apr 8 09:45:51 2025 +0300
IGNITE-24756 SQL Calcite: Add extraction of common part from disjunction in
conditions - Fixes #11972.
Signed-off-by: Aleksey Plekhanov <[email protected]>
---
.../query/calcite/prepare/IgnitePlanner.java | 116 ++++++++++++
.../query/calcite/prepare/PlannerHelper.java | 2 +
.../query/calcite/integration/tpch/TpchTest.java | 2 +-
.../planner/RexSimplificationPlannerTest.java | 196 +++++++++++++++++++++
.../apache/ignite/testsuites/PlannerTestSuite.java | 2 +
5 files changed, 317 insertions(+), 1 deletion(-)
diff --git
a/modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/prepare/IgnitePlanner.java
b/modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/prepare/IgnitePlanner.java
index 376220ae426..f7d8b584b81 100644
---
a/modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/prepare/IgnitePlanner.java
+++
b/modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/prepare/IgnitePlanner.java
@@ -50,14 +50,18 @@ import org.apache.calcite.rel.RelRoot;
import org.apache.calcite.rel.RelShuttle;
import org.apache.calcite.rel.core.CorrelationId;
import org.apache.calcite.rel.logical.LogicalCorrelate;
+import org.apache.calcite.rel.logical.LogicalFilter;
import org.apache.calcite.rel.logical.LogicalJoin;
import org.apache.calcite.rel.metadata.CachingRelMetadataProvider;
import org.apache.calcite.rel.metadata.RelMetadataQuery;
import org.apache.calcite.rel.type.RelDataType;
+import org.apache.calcite.rex.RexBuilder;
+import org.apache.calcite.rex.RexCall;
import org.apache.calcite.rex.RexCorrelVariable;
import org.apache.calcite.rex.RexExecutor;
import org.apache.calcite.rex.RexNode;
import org.apache.calcite.rex.RexShuttle;
+import org.apache.calcite.rex.RexUtil;
import org.apache.calcite.sql.SqlBasicCall;
import org.apache.calcite.sql.SqlDataTypeSpec;
import org.apache.calcite.sql.SqlIdentifier;
@@ -592,6 +596,118 @@ public class IgnitePlanner implements Planner,
RelOptTable.ViewExpander {
return relShuttle.visit(rel);
}
+ /**
+ * Due to distributive property of conjunction over disjunction we can
extract common part of conjunctions.
+ * This can help us to simplify and push down filters.
+ * For example, condition:
+ * (a = 0 and x = 1) or (a = 0 and y = 2) or (a = 0 and z = 3)
+ * can be translated to:
+ * a = 0 and (x = 1 or y = 2 or z = 3)
+ * after such a transformation condition "a = 0" can be used as index
access predicate.
+ */
+ public RelNode extractConjunctionOverDisjunctionCommonPart(RelNode rel) {
+ return new RelHomogeneousShuttle() {
+ /** {@inheritDoc} */
+ @Override public RelNode visit(LogicalFilter filter) {
+ RexNode condition =
transform(filter.getCluster().getRexBuilder(), filter.getCondition());
+
+ if (condition != filter.getCondition())
+ filter = filter.copy(filter.getTraitSet(),
filter.getInput(), condition);
+
+ return super.visit(filter);
+ }
+
+ /** {@inheritDoc} */
+ @Override public RelNode visit(LogicalJoin join) {
+ RexNode condition =
transform(join.getCluster().getRexBuilder(), join.getCondition());
+
+ if (condition != join.getCondition()) {
+ join = join.copy(join.getTraitSet(), condition,
join.getLeft(), join.getRight(),
+ join.getJoinType(), join.isSemiJoinDone());
+ }
+
+ return super.visit(join);
+ }
+
+ /** */
+ private RexNode transform(RexBuilder rexBuilder, RexNode
condition) {
+ // It makes sence to extract only top level disjunction common
part.
+ if (!condition.isA(SqlKind.OR))
+ return condition;
+
+ Set<RexNode> commonPart = new HashSet<>();
+
+ List<RexNode> orOps = ((RexCall)condition).getOperands();
+
+ RexNode firstOp = orOps.get(0);
+
+ for (RexNode andOpFirst : conjunctionOperands(firstOp)) {
+ boolean found = false;
+
+ for (int i = 1; i < orOps.size(); i++) {
+ found = false;
+
+ for (RexNode andOpOther :
conjunctionOperands(orOps.get(i))) {
+ if (andOpFirst.equals(andOpOther)) {
+ found = true;
+
+ break;
+ }
+ }
+
+ if (!found)
+ break;
+ }
+
+ if (found)
+ commonPart.add(andOpFirst);
+ }
+
+ if (commonPart.isEmpty())
+ return condition;
+
+ List<RexNode> newOrOps = new ArrayList<>(orOps.size());
+
+ for (RexNode orOp : orOps) {
+ List<RexNode> newAndOps = new ArrayList<>();
+
+ for (RexNode andOp : conjunctionOperands(orOp)) {
+ if (!commonPart.contains(andOp))
+ newAndOps.add(andOp);
+ }
+
+ if (!newAndOps.isEmpty()) {
+ RexNode newAnd =
RexUtil.composeConjunction(rexBuilder, newAndOps);
+
+ newOrOps.add(newAnd);
+ }
+ }
+
+ if (newOrOps.isEmpty())
+ condition = RexUtil.composeConjunction(rexBuilder,
commonPart);
+ else {
+ RexNode newOr = RexUtil.composeDisjunction(rexBuilder,
newOrOps);
+
+ List<RexNode> newConditions = new
ArrayList<>(commonPart.size() + 1);
+ newConditions.addAll(commonPart);
+ newConditions.add(newOr);
+
+ condition = RexUtil.composeConjunction(rexBuilder,
newConditions);
+ }
+
+ return condition;
+ }
+
+ /** */
+ private List<RexNode> conjunctionOperands(RexNode call) {
+ if (call.isA(SqlKind.AND))
+ return ((RexCall)call).getOperands();
+ else
+ return Collections.singletonList(call);
+ }
+ }.visit(rel);
+ }
+
/** */
private SqlToRelConverter sqlToRelConverter(SqlValidator validator,
CalciteCatalogReader reader,
SqlToRelConverter.Config config) {
diff --git
a/modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/prepare/PlannerHelper.java
b/modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/prepare/PlannerHelper.java
index 2f3cde82aee..12b9deed6e9 100644
---
a/modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/prepare/PlannerHelper.java
+++
b/modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/prepare/PlannerHelper.java
@@ -127,6 +127,8 @@ public class PlannerHelper {
rel = planner.replaceCorrelatesCollisions(rel);
+ rel = planner.extractConjunctionOverDisjunctionCommonPart(rel);
+
rel = planner.trimUnusedFields(root.withRel(rel)).rel;
rel = planner.transform(PlannerPhase.HEP_FILTER_PUSH_DOWN,
rel.getTraitSet(), rel);
diff --git
a/modules/calcite/src/test/java/org/apache/ignite/internal/processors/query/calcite/integration/tpch/TpchTest.java
b/modules/calcite/src/test/java/org/apache/ignite/internal/processors/query/calcite/integration/tpch/TpchTest.java
index 54251de8783..df59a9b2387 100644
---
a/modules/calcite/src/test/java/org/apache/ignite/internal/processors/query/calcite/integration/tpch/TpchTest.java
+++
b/modules/calcite/src/test/java/org/apache/ignite/internal/processors/query/calcite/integration/tpch/TpchTest.java
@@ -34,7 +34,7 @@ public class TpchTest extends AbstractBasicIntegrationTest {
/** */
@Parameterized.Parameters(name = "queryId={0}")
public static Collection<Object> params() {
- return F.asList(16, 20);
+ return F.asList(16, 19, 20);
}
/** {@inheritDoc} */
diff --git
a/modules/calcite/src/test/java/org/apache/ignite/internal/processors/query/calcite/planner/RexSimplificationPlannerTest.java
b/modules/calcite/src/test/java/org/apache/ignite/internal/processors/query/calcite/planner/RexSimplificationPlannerTest.java
new file mode 100644
index 00000000000..db7ec8238c6
--- /dev/null
+++
b/modules/calcite/src/test/java/org/apache/ignite/internal/processors/query/calcite/planner/RexSimplificationPlannerTest.java
@@ -0,0 +1,196 @@
+/*
+ * 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.ignite.internal.processors.query.calcite.planner;
+
+import org.apache.calcite.rel.core.Join;
+import org.apache.calcite.util.Util;
+import
org.apache.ignite.internal.processors.query.calcite.rel.ProjectableFilterableTableScan;
+import org.apache.ignite.internal.processors.query.calcite.schema.IgniteSchema;
+import
org.apache.ignite.internal.processors.query.calcite.trait.IgniteDistributions;
+import org.junit.Test;
+
+import static org.apache.calcite.sql.type.SqlTypeName.INTEGER;
+
+/**
+ * Tests for Rex simplification.
+ */
+public class RexSimplificationPlannerTest extends AbstractPlannerTest {
+ /**
+ * @throws Exception If failed.
+ */
+ @Test
+ public void testExtractCommonDisjunctionPart() throws Exception {
+ IgniteSchema schema = createSchema(
+ createTable("T1", IgniteDistributions.single(), "C1", INTEGER,
"C2", INTEGER, "C3", INTEGER)
+ .addIndex("IDX1", 0),
+ createTable("T2", IgniteDistributions.single(), "C1", INTEGER,
"C2", INTEGER, "C3", INTEGER)
+ .addIndex("IDX2", 0)
+ );
+
+ // Simple equality predicate.
+ assertPlan("SELECT * FROM t1 WHERE " +
+ "(c1 = 0 and c2 = 1) or " +
+ "(c1 = 0 and c3 = 2)", schema,
+ isIndexScan("T1", "IDX1")
+ .and(s -> "AND(=($t0, 0), OR(=($t1, 1), =($t2,
2)))".equals(s.condition().toString())));
+
+ // Reversed equality predicate.
+ assertPlan("SELECT * FROM t1 WHERE " +
+ "(c1 = 0 and c2 = 1) or " +
+ "(0 = c1 and c3 = 2)", schema,
+ isIndexScan("T1", "IDX1")
+ .and(s -> "AND(=($t0, 0), OR(=($t1, 1), =($t2,
2)))".equals(s.condition().toString())));
+
+ // Simple more-than predicate.
+ assertPlan("SELECT * FROM t1 WHERE " +
+ "(c1 > 0 and c2 = 1) or " +
+ "(c1 > 0 and c3 = 2)", schema,
+ isIndexScan("T1", "IDX1")
+ .and(s -> "AND(>($t0, 0), OR(=($t1, 1), =($t2,
2)))".equals(s.condition().toString())));
+
+ // Reversed more-than predicate.
+ assertPlan("SELECT * FROM t1 WHERE " +
+ "(c1 > 0 and c2 = 1) or " +
+ "(0 < c1 and c3 = 2)", schema,
+ isIndexScan("T1", "IDX1")
+ .and(s -> "AND(>($t0, 0), OR(=($t1, 1), =($t2,
2)))".equals(s.condition().toString())));
+
+ // Conjunction left inside disjunction.
+ assertPlan("SELECT * FROM t1 WHERE " +
+ "(c1 = 0 and c2 = 1 and c3 = 0) or " +
+ "(c1 = 0 and c2 = c3)", schema,
+ isIndexScan("T1", "IDX1")
+ .and(s -> "AND(=($t0, 0), OR(AND(=($t1, 1), =($t2, 0)), =($t1,
$t2)))".equals(s.condition().toString())));
+
+ // Three operands disjunction.
+ assertPlan("SELECT * FROM t1 WHERE " +
+ "(c1 = 0 and c2 = 1) or " +
+ "(c1 = 0 and c3 = 2) or " +
+ "(c1 = 0 and c2 = c3)", schema,
+ isIndexScan("T1", "IDX1")
+ .and(s -> "AND(=($t0, 0), OR(=($t1, 1), =($t2, 2), =($t1,
$t2)))".equals(s.condition().toString())));
+
+ // Two operands extraction.
+ assertPlan("SELECT * FROM t1 WHERE " +
+ "(c1 = 0 and c2 = 0 and c3 = 0) or " +
+ "(c1 = 0 and c2 = 0 and c3 = 1) or " +
+ "(c1 = 0 and c2 = 0 and c3 = 2)", schema,
+ isIndexScan("T1", "IDX1")
+ .and(s -> "AND(=($t0, 0), =($t1, 0), SEARCH($t2, Sarg[0, 1,
2]))".equals(s.condition().toString())));
+
+ // Disjunction equality first operand removal.
+ assertPlan("SELECT * FROM t1 WHERE " +
+ "(c1 = 0) or " +
+ "(c1 = 0 and c2 = 0) or " +
+ "(c1 = 0 and c2 = 1)", schema,
+ isIndexScan("T1", "IDX1")
+ .and(s -> "AND(=($t0, 0), SEARCH($t1, Sarg[0,
1]))".equals(s.condition().toString())));
+
+ // Disjunction equality last operand removal.
+ assertPlan("SELECT * FROM t1 WHERE " +
+ "(c1 = 0 and c2 = 0) or " +
+ "(c1 = 0 and c2 = 1) or " +
+ "(c1 = 0)", schema,
+ isIndexScan("T1", "IDX1")
+ .and(s -> "AND(=($t0, 0), SEARCH($t1, Sarg[0,
1]))".equals(s.condition().toString())));
+
+ // Disjunction conjunction operand removal.
+ assertPlan("SELECT * FROM t1 WHERE " +
+ "(c1 = 0 and c2 = 0 and c3 = 0) or " +
+ "(c1 = 0 and c2 = 0 and c3 = 1) or " +
+ "(c1 = 0 and c2 = 0)", schema,
+ isIndexScan("T1", "IDX1")
+ .and(s -> "AND(=($t0, 0), =($t1, 0), SEARCH($t2, Sarg[0,
1]))".equals(s.condition().toString())));
+
+ // Disjunction removal.
+ assertPlan("SELECT * FROM t1 WHERE " +
+ "(c1 = 0) or " +
+ "(c1 = 0)", schema,
+ isIndexScan("T1", "IDX1")
+ .and(s -> "=($t0, 0)".equals(s.condition().toString())));
+
+ // Disjunction removal.
+ assertPlan("SELECT * FROM t1 WHERE " +
+ "(c1 = 0) or " +
+ "(c1 = 0 and c2 = 0)", schema,
+ isIndexScan("T1", "IDX1")
+ .and(s -> "AND(=($t0, 0), =($t1,
0))".equals(s.condition().toString())));
+
+ // Disjunction removal.
+ assertPlan("SELECT * FROM t1 WHERE " +
+ "(c1 = 0 and c2 = 0) or " +
+ "(c1 = 0)", schema,
+ isIndexScan("T1", "IDX1")
+ .and(s -> "AND(=($t0, 0), =($t1,
0))".equals(s.condition().toString())));
+
+ // Disjunction removal.
+ assertPlan("SELECT * FROM t1 WHERE " +
+ "(c1 = 0 and c2 = 0) or " +
+ "(c2 = 0 and c1 = 0)", schema,
+ isIndexScan("T1", "IDX1")
+ .and(s -> "AND(=($t0, 0), =($t1,
0))".equals(s.condition().toString())));
+
+ // Commutes and duplicates.
+ assertPlan("SELECT * FROM t1 WHERE " +
+ "(c1 = 0 and c2 = 0 and c3 = 0) or " +
+ "(0 = c2 and c3 = 1 and c1 = 0 and c2 = 0) or " +
+ "(c2 = 0 and c3 = 2 and c1 = 0 and c2 = 0)", schema,
+ isIndexScan("T1", "IDX1")
+ .and(s -> "AND(=($t0, 0), =($t1, 0), SEARCH($t2, Sarg[0, 1,
2]))".equals(s.condition().toString())));
+
+ // Simple join.
+ assertPlan("SELECT * FROM t1 JOIN t2 ON (" +
+ "(t1.c1 = t2.c1 and t1.c2 = 0) or " +
+ "(t1.c1 = t2.c1 and t2.c2 = 0))", schema,
+ isInstanceOf(Join.class)
+ .and(s -> "AND(=($0, $3), OR(=($1, 0), =($4,
0)))".equals(s.getCondition().toString())));
+
+ // Simple join reversed equality predicate.
+ assertPlan("SELECT * FROM t1 JOIN t2 ON (" +
+ "(t1.c1 = t2.c1 and t1.c2 = 0) or " +
+ "(t2.c1 = t1.c1 and t2.c2 = 0))", schema,
+ isInstanceOf(Join.class)
+ .and(s -> "AND(=($0, $3), OR(=($1, 0), =($4,
0)))".equals(s.getCondition().toString())));
+
+ // Join with filter push-down.
+ assertPlan("SELECT * FROM t1 JOIN t2 ON (" +
+ "(t1.c1 = t2.c1 and t1.c2 = 0 and t2.c2 = 0 and t1.c3 = 0) or
" +
+ "(t1.c1 = t2.c1 and t1.c2 = 0 and t2.c2 = 0 and t2.c3 = 0))",
schema,
+ isInstanceOf(Join.class)
+ .and(s -> "AND(=($0, $3), OR(=($2, 0), =($5,
0)))".equals(s.getCondition().toString()))
+
.and(hasChildThat(isInstanceOf(ProjectableFilterableTableScan.class)
+ .and(s ->
"T1".equals(Util.last(s.getTable().getQualifiedName())))
+ .and(s -> "=($t1, 0)".equals(s.condition().toString()))
+ ))
+
.and(hasChildThat(isInstanceOf(ProjectableFilterableTableScan.class)
+ .and(s ->
"T2".equals(Util.last(s.getTable().getQualifiedName())))
+ .and(s -> "=($t1, 0)".equals(s.condition().toString()))
+ ))
+ );
+
+ // Can't simplify.
+ assertPlan("SELECT * FROM t1 WHERE " +
+ "(c1 = 0 and c2 = 1) or " +
+ "(c1 = 0 and c3 = 2) or " +
+ "(c1 = 1 and c2 = c3)", schema,
+ isInstanceOf(ProjectableFilterableTableScan.class)
+ .and(s -> "OR(AND(=($t0, 0), =($t1, 1)), AND(=($t0, 0), =($t2,
2)), AND(=($t0, 1), =($t1, $t2)))"
+ .equals(s.condition().toString()))
+ );
+ }
+}
diff --git
a/modules/calcite/src/test/java/org/apache/ignite/testsuites/PlannerTestSuite.java
b/modules/calcite/src/test/java/org/apache/ignite/testsuites/PlannerTestSuite.java
index 53ff68e605e..c4e4b259deb 100644
---
a/modules/calcite/src/test/java/org/apache/ignite/testsuites/PlannerTestSuite.java
+++
b/modules/calcite/src/test/java/org/apache/ignite/testsuites/PlannerTestSuite.java
@@ -35,6 +35,7 @@ import
org.apache.ignite.internal.processors.query.calcite.planner.MergeJoinPlan
import org.apache.ignite.internal.processors.query.calcite.planner.PlannerTest;
import
org.apache.ignite.internal.processors.query.calcite.planner.PlannerTimeoutTest;
import
org.apache.ignite.internal.processors.query.calcite.planner.ProjectFilterScanMergePlannerTest;
+import
org.apache.ignite.internal.processors.query.calcite.planner.RexSimplificationPlannerTest;
import
org.apache.ignite.internal.processors.query.calcite.planner.SerializationPlannerTest;
import
org.apache.ignite.internal.processors.query.calcite.planner.SetOpPlannerTest;
import
org.apache.ignite.internal.processors.query.calcite.planner.SortAggregatePlannerTest;
@@ -81,6 +82,7 @@ import org.junit.runners.Suite;
IndexSearchBoundsPlannerTest.class,
InlineIndexScanPlannerTest.class,
UserDefinedViewsPlannerTest.class,
+ RexSimplificationPlannerTest.class,
HintsTestSuite.class,
SerializationPlannerTest.class,
