[CALCITE-4663] And predicate in one subtree of Join causes JoinPushTransitivePredicatesRule pulls up predicates infinitely and StackOverflowError

• Type: Bug
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Affects Version/s: 1.26.0, 1.27.0
• Fix Version/s: 1.31.0
• Component/s: core

Environment

jdk8

calcite1.27.0

• Assignee: Unassigned
• Reporter: yanjing.wang
• Created: 23/Jun/21 03:48
• Updated: 18/Aug/22 12:18
• Resolved: 18/Aug/22 12:17

Description

the query is select empid from hr.emps where deptno in (select deptno from hr.depts where deptno between 1000 and 2000) and the logical plan tree after decorrelated optimization is 

LogicalProject(empid=[$0])
    LogicalJoin(condition=[=($1, $5)], joinType=[inner])
        LogicalTableScan(table=[[hr, emps]])
        LogicalAggregate(group=[\{0}])
            LogicalProject(deptno=[$0])
                LogicalFilter(condition=[*AND(>=($0, 1000), <=($0, 2000))*])
                     LogicalTableScan(table=[[hr, depts]])

the AND predicate behaves different with Search In JoinConditionBasedPredicateInference.

We can reproduce this problem through adding a test case like SortRemoveRuleTest.

public final class JoinPushTransitivePredicatesRuleTest {
  @Test
  void conjunctionTransitive() throws Exception {

    SchemaPlus rootSchema = Frameworks.createRootSchema(true);
    SchemaPlus defSchema = rootSchema.add("hr", new HrClusteredSchema());
    FrameworkConfig config = Frameworks.newConfigBuilder()
        .parserConfig(SqlParser.Config.DEFAULT)
        .defaultSchema(defSchema)
        .traitDefs(ConventionTraitDef.INSTANCE, RelCollationTraitDef.INSTANCE)
        .build();

    String sql = "select \"empid\" from \"hr\".\"emps\" where \"deptno\" in (select \"deptno\" from \"hr\".\"depts\" where \"deptno\" between 1000 and 2000)";
    Planner planner = Frameworks.getPlanner(config);
    SqlNode parse = planner.parse(sql);
    SqlNode validate = planner.validate(parse);
    RelRoot planRoot = planner.rel(validate);
    RelNode planBefore = planRoot.rel;
    HepProgram hepProgram = HepProgram.builder()
//        .addRuleInstance(CoreRules.FILTER_REDUCE_EXPRESSIONS)
        .addRuleInstance(CoreRules.JOIN_PUSH_TRANSITIVE_PREDICATES)
        .build();

    HepPlanner hepPlanner = new HepPlanner(hepProgram);
    hepPlanner.setRoot(planBefore);
    hepPlanner.findBestExp();
  }
}

Exception in thread "main" java.lang.StackOverflowError

The culprit is that the JoinPushTransitivePredicatesRule simplify pulledUpPredicates, otherwise JoinConditionBasedPredicateInference not, so that the JoinConditionBasedPredicateInference can infer predicates indefinitely.

Though we can add a CoreRules.FILTER_REDUCE_EXPRESSIONS before CoreRules.JOIN_PUSH_TRANSITIVE_PREDICATES as a workaround, but I think we can simplify left and right child predicates in JoinConditionBasedPredicateInference constructor and seems better.

 

I add simplification for child predicates and StackOverflowError disappears.

leftChildPredicates = simplify.simplify(leftPredicates.accept(
    new RexPermuteInputsShuttle(leftMapping, joinRel.getInput(0))));

rightChildPredicates = simplify.simplify(rightPredicates.accept(
    new RexPermuteInputsShuttle(rightMapping, joinRel.getInput(1))));

  

Issue Links

• is fixed by: CALCITE-5036 `RelMetadataQuery#getPulledUpPredicates` support to analyze constant key for the operator of IS_NOT_DISTINCT_FROM
• relates to: HIVE-25275 OOM during query planning due to HiveJoinPushTransitivePredicatesRule matching infinitely