This is an automated email from the ASF dual-hosted git repository.
mbudiu pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/calcite.git
The following commit(s) were added to refs/heads/main by this push:
new c0cc8daee6 [CALCITE-6432] Infinite loop for
JoinPushTransitivePredicatesRule
c0cc8daee6 is described below
commit c0cc8daee6cc74338ee5acc20d0c7d891d6ef0a4
Author: Zhen Chen <[email protected]>
AuthorDate: Wed Apr 30 07:11:52 2025 +0800
[CALCITE-6432] Infinite loop for JoinPushTransitivePredicatesRule
---
.../calcite/rel/metadata/RelMdPredicates.java | 44 ++++++++++++------
.../org/apache/calcite/test/RelOptRulesTest.java | 18 +++++++-
.../org/apache/calcite/test/RelOptRulesTest.xml | 52 +++++++++++++---------
3 files changed, 78 insertions(+), 36 deletions(-)
diff --git
a/core/src/main/java/org/apache/calcite/rel/metadata/RelMdPredicates.java
b/core/src/main/java/org/apache/calcite/rel/metadata/RelMdPredicates.java
index f7d7692c10..cfdc372392 100644
--- a/core/src/main/java/org/apache/calcite/rel/metadata/RelMdPredicates.java
+++ b/core/src/main/java/org/apache/calcite/rel/metadata/RelMdPredicates.java
@@ -194,15 +194,13 @@ public RelOptPredicateList getPredicates(Project project,
final List<RexNode> projectPullUpPredicates = new ArrayList<>();
ImmutableBitSet.Builder columnsMappedBuilder = ImmutableBitSet.builder();
- Mapping m =
- Mappings.create(MappingType.PARTIAL_FUNCTION,
- input.getRowType().getFieldCount(),
- project.getRowType().getFieldCount());
-
+ // The keys are field indexes (RexInputRef) that appear in the input of
project,
+ // values are sets of field indexes (RexInputRef) that appear in project.
+ Map<Integer, BitSet> equivalence = new HashMap<>();
for (Ord<RexNode> expr : Ord.zip(project.getProjects())) {
if (expr.e instanceof RexInputRef) {
int sIdx = ((RexInputRef) expr.e).getIndex();
- m.set(sIdx, expr.i);
+ equivalence.computeIfAbsent(sIdx, k -> new BitSet()).set(expr.i);
columnsMappedBuilder.set(sIdx);
} else if (RexUtil.isConstant(expr.e)) {
// Project can also generate constants (including NULL). We need to
@@ -218,8 +216,21 @@ public RelOptPredicateList getPredicates(Project project,
for (RexNode r : inputInfo.pulledUpPredicates) {
RexNode r2 = projectPredicate(rexBuilder, input, r, columnsMapped);
if (!r2.isAlwaysTrue()) {
- r2 = r2.accept(new RexPermuteInputsShuttle(m, input));
- projectPullUpPredicates.add(r2);
+ ImmutableBitSet fields = RelOptUtil.InputFinder.bits(r2);
+ // If r2 cannot find input (such as SubQuery),
+ // it will directly return without adjusting mapping.
+ if (fields.isEmpty()) {
+ projectPullUpPredicates.add(r2);
+ continue;
+ }
+ JoinConditionBasedPredicateInference.ExprsItr exprsItr =
+ new JoinConditionBasedPredicateInference.ExprsItr(fields,
+ equivalence, input.getRowType().getFieldCount(),
+ project.getRowType().getFieldCount());
+ while (exprsItr.hasNext()) {
+ RexNode r3 = r2.accept(new RexPermuteInputsShuttle(exprsItr.next(),
input));
+ projectPullUpPredicates.add(r3);
+ }
}
}
return RelOptPredicateList.of(rexBuilder, projectPullUpPredicates);
@@ -888,7 +899,9 @@ Iterable<Mapping> mappings(final RexNode predicate) {
if (fields.cardinality() == 0) {
return Collections.emptyList();
}
- return () -> new ExprsItr(fields);
+ return () -> new ExprsItr(fields, equivalence,
+ nSysFields + nFieldsLeft + nFieldsRight,
+ nSysFields + nFieldsLeft + nFieldsRight);
}
private static boolean checkTarget(ImmutableBitSet inferringFields,
@@ -966,15 +979,17 @@ protected EquivalenceFinder() {
* b + b + e
* </pre>
*/
- class ExprsItr implements Iterator<Mapping> {
+ static class ExprsItr implements Iterator<Mapping> {
final int[] columns;
final BitSet[] columnSets;
final int[] iterationIdx;
@Nullable Mapping nextMapping;
boolean firstCall;
+ int sourceCount;
+ int targetCount;
- @SuppressWarnings("JdkObsolete")
- ExprsItr(ImmutableBitSet fields) {
+ ExprsItr(ImmutableBitSet fields, Map<Integer, BitSet> equivalence,
+ int sourceCount, int targetCount) {
nextMapping = null;
columns = new int[fields.cardinality()];
columnSets = new BitSet[fields.cardinality()];
@@ -990,6 +1005,8 @@ class ExprsItr implements Iterator<Mapping> {
iterationIdx[j] = 0;
}
firstCall = true;
+ this.sourceCount = sourceCount;
+ this.targetCount = targetCount;
}
@Override public boolean hasNext() {
@@ -1033,8 +1050,7 @@ private void computeNextMapping(int level) {
private void initializeMapping() {
nextMapping =
Mappings.create(MappingType.PARTIAL_FUNCTION,
- nSysFields + nFieldsLeft + nFieldsRight,
- nSysFields + nFieldsLeft + nFieldsRight);
+ sourceCount, targetCount);
for (int i = 0; i < columnSets.length; i++) {
BitSet c = columnSets[i];
int t = c.nextSetBit(iterationIdx[i]);
diff --git a/core/src/test/java/org/apache/calcite/test/RelOptRulesTest.java
b/core/src/test/java/org/apache/calcite/test/RelOptRulesTest.java
index 17d762ee15..c63aa979a7 100644
--- a/core/src/test/java/org/apache/calcite/test/RelOptRulesTest.java
+++ b/core/src/test/java/org/apache/calcite/test/RelOptRulesTest.java
@@ -6893,7 +6893,23 @@ private HepProgram getTransitiveProgram() {
.withRule(CoreRules.FILTER_INTO_JOIN,
CoreRules.JOIN_CONDITION_PUSH,
CoreRules.JOIN_PUSH_TRANSITIVE_PREDICATES)
- .check();
+ .checkUnchanged();
+ }
+
+ /** Test case of
+ * <a
href="https://issues.apache.org/jira/browse/CALCITE-6432";>[CALCITE-6432]
+ * Infinite loop for JoinPushTransitivePredicatesRule</a>. */
+ @Test void testProjectPredicatePull() {
+ final String sql = "select e.ename, d.dname\n"
+ + "from (select ename, deptno from emp where deptno = 10) e\n"
+ + "join (select name dname, deptno, * from dept) d\n"
+ + "on e.deptno = d.deptno";
+ final HepProgram program = new HepProgramBuilder()
+ .addRuleCollection(
+ ImmutableList.of(CoreRules.FILTER_PROJECT_TRANSPOSE,
+ CoreRules.JOIN_PUSH_TRANSITIVE_PREDICATES))
+ .build();
+ sql(sql).withProgram(program).check();
}
/** Test case for
diff --git
a/core/src/test/resources/org/apache/calcite/test/RelOptRulesTest.xml
b/core/src/test/resources/org/apache/calcite/test/RelOptRulesTest.xml
index fd946315d5..4e2946902c 100644
--- a/core/src/test/resources/org/apache/calcite/test/RelOptRulesTest.xml
+++ b/core/src/test/resources/org/apache/calcite/test/RelOptRulesTest.xml
@@ -7448,27 +7448,6 @@ LogicalProject(SAL=[$5])
LogicalProject(SAL=[$5], $f9=[=($5, 4)])
LogicalFilter(condition=[AND(=($7, 20), >($5, 1000))])
LogicalTableScan(table=[[CATALOG, SALES, EMPNULLABLES]])
-]]>
- </Resource>
- <Resource name="planAfter">
- <![CDATA[
-LogicalProject(SAL=[$5])
- LogicalJoin(condition=[AND(=($5, $11), =($9, $12))], joinType=[inner])
- LogicalFilter(condition=[>($5, 1000)])
- LogicalProject(EMPNO=[$0], ENAME=[$1], JOB=[$2], MGR=[$3],
HIREDATE=[$4], SAL=[$5], COMM=[$6], SLACKER=[$8], SAL0=[$5], $f9=[=($5, 4)])
- LogicalFilter(condition=[AND(=($7, 20), >($5, 1000))])
- LogicalTableScan(table=[[CATALOG, SALES, EMPNULLABLES]])
- LogicalFilter(condition=[=($1, $0)])
- LogicalAggregate(group=[{0, 1, 2}])
- LogicalProject(SAL=[$5], SAL0=[$8], $f9=[$9])
- LogicalJoin(condition=[OR(=($8, $5), $9)], joinType=[inner])
- LogicalProject(EMPNO=[$0], ENAME=[$1], JOB=[$2], MGR=[$3],
HIREDATE=[$4], SAL=[$5], COMM=[$6], SLACKER=[$8])
- LogicalFilter(condition=[AND(=($7, 20), >($5, 1000))])
- LogicalTableScan(table=[[CATALOG, SALES, EMPNULLABLES]])
- LogicalAggregate(group=[{0, 1}])
- LogicalProject(SAL=[$5], $f9=[=($5, 4)])
- LogicalFilter(condition=[AND(=($7, 20), >($5, 1000))])
- LogicalTableScan(table=[[CATALOG, SALES, EMPNULLABLES]])
]]>
</Resource>
</TestCase>
@@ -10034,6 +10013,37 @@ LogicalProject(EXPR$0=[CAST(/(CASE(>($2, 0), $3,
null:INTEGER), $2)):INTEGER])
LogicalWindow(window#0=[window(order by [0] rows between $2 PRECEDING and
CURRENT ROW aggs [COUNT($1), $SUM0($1)])], constants=[[3]])
LogicalProject(EMPNO=[$0], SAL=[$5])
LogicalTableScan(table=[[CATALOG, SALES, EMP]])
+]]>
+ </Resource>
+ </TestCase>
+ <TestCase name="testProjectPredicatePull">
+ <Resource name="sql">
+ <![CDATA[select e.ename, d.dname
+from (select ename, deptno from emp where deptno = 10) e
+join (select name dname, deptno, * from dept) d
+on e.deptno = d.deptno]]>
+ </Resource>
+ <Resource name="planBefore">
+ <![CDATA[
+LogicalProject(ENAME=[$0], DNAME=[$2])
+ LogicalJoin(condition=[=($1, $3)], joinType=[inner])
+ LogicalProject(ENAME=[$1], DEPTNO=[$7])
+ LogicalFilter(condition=[=($7, 10)])
+ LogicalTableScan(table=[[CATALOG, SALES, EMP]])
+ LogicalProject(DNAME=[$1], DEPTNO=[$0], DEPTNO0=[$0], NAME=[$1])
+ LogicalTableScan(table=[[CATALOG, SALES, DEPT]])
+]]>
+ </Resource>
+ <Resource name="planAfter">
+ <![CDATA[
+LogicalProject(ENAME=[$0], DNAME=[$2])
+ LogicalJoin(condition=[=($1, $3)], joinType=[inner])
+ LogicalProject(ENAME=[$1], DEPTNO=[$7])
+ LogicalFilter(condition=[=($7, 10)])
+ LogicalTableScan(table=[[CATALOG, SALES, EMP]])
+ LogicalProject(DNAME=[$1], DEPTNO=[$0], DEPTNO0=[$0], NAME=[$1])
+ LogicalFilter(condition=[=($0, 10)])
+ LogicalTableScan(table=[[CATALOG, SALES, DEPT]])
]]>
</Resource>
</TestCase>
