Uploaded image for project: 'Calcite'
  1. Calcite
  2. CALCITE-457

Push condition of non-ansi join into join operator

    Details

    • Type: Bug
    • Status: Closed
    • Priority: Major
    • Resolution: Fixed
    • Affects Version/s: 0.9.1-incubating
    • Fix Version/s: 1.4.0-incubating
    • Component/s: None
    • Labels:
      None

      Description

      I've tested two plans and it turns out the query with non-ansi joins has extremely bad plan (note EnumerableJoinRel(condition=[true]):

      explain plan for select d."deptno", e."empid"
      from "hr"."emps" as e
        , "hr"."depts" as d
      where e."deptno" = d."deptno"+0
      
      PLAN=EnumerableCalcRel(expr#0..2=[{inputs}], expr#3=[CAST($t1):INTEGER NOT NULL], expr#4=[0], expr#5=[+($t2, $t4)], expr#6=[=($t3, $t5)], deptno=[$t2], empid=[$t0], $condition=[$t6])
        EnumerableJoinRel(condition=[true], joinType=[inner])
          EnumerableCalcRel(expr#0..4=[{inputs}], proj#0..1=[{exprs}])
            EnumerableTableAccessRel(table=[[hr, emps]])
          EnumerableCalcRel(expr#0..2=[{inputs}], deptno=[$t0])
            EnumerableTableAccessRel(table=[[hr, depts]])
      

      Same works fine with ANSI style:

      explain plan for select d."deptno", e."empid"
      from "hr"."emps" as e
        join "hr"."depts" as d
       on (e."deptno" = d."deptno"+0)
      
      PLAN=EnumerableCalcRel(expr#0..3=[{inputs}], deptno=[$t2], empid=[$t0])
        EnumerableJoinRel(condition=[=($1, $3)], joinType=[inner])
          EnumerableCalcRel(expr#0..4=[{inputs}], expr#5=[CAST($t1):INTEGER NOT NULL], empid=[$t0], $f5=[$t5])
            EnumerableTableAccessRel(table=[[hr, emps]])
          EnumerableCalcRel(expr#0..2=[{inputs}], expr#3=[0], expr#4=[+($t0, $t3)], deptno=[$t0], $f3=[$t4])
            EnumerableTableAccessRel(table=[[hr, depts]])
      

      The query that does not use calculations works fine even with non-ansi style:

      explain plan for select d."deptno", e."empid"
      from "hr"."emps" as e
        , "hr"."depts" as d
      where e."deptno" = d."deptno"
      
      PLAN=EnumerableCalcRel(expr#0..2=[{inputs}], deptno=[$t2], empid=[$t0])
        EnumerableJoinRel(condition=[=($1, $2)], joinType=[inner])
          EnumerableCalcRel(expr#0..4=[{inputs}], proj#0..1=[{exprs}])
            EnumerableTableAccessRel(table=[[hr, emps]])
          EnumerableCalcRel(expr#0..2=[{inputs}], deptno=[$t0])
            EnumerableTableAccessRel(table=[[hr, depts]])
      

        Issue Links

          Activity

          Hide
          jni Jinfeng Ni added a comment -

          Drill hits the same problem when there is a compound expression (not a single column) in non-ansi join condition, and we fixed this problem in Drill's forked version of Optiq. Basically, the cause of this problem is the the compound expression in FILTER is not pushed past join, leaving the JOIN operator with "true" condition.

          In contrast, if the compound expression is in "ON" clause (ansi-join), then the expression would be pushed past JOIN, and put it into a PROJECT below JOIN. And JOIN would simply refer the projected expression in the join condition. (Such logic is in SqlToRelConverter.java).

          The fix we did is simply to make the logic in SqlToRelConverter shared by both SqlToRelConverter and PushFilterPastJoinRule, so that the compound expression in either "ON" clause or "WHERE" clause would be handled properly.

          Show
          jni Jinfeng Ni added a comment - Drill hits the same problem when there is a compound expression (not a single column) in non-ansi join condition, and we fixed this problem in Drill's forked version of Optiq. Basically, the cause of this problem is the the compound expression in FILTER is not pushed past join, leaving the JOIN operator with "true" condition. In contrast, if the compound expression is in "ON" clause (ansi-join), then the expression would be pushed past JOIN, and put it into a PROJECT below JOIN. And JOIN would simply refer the projected expression in the join condition. (Such logic is in SqlToRelConverter.java). The fix we did is simply to make the logic in SqlToRelConverter shared by both SqlToRelConverter and PushFilterPastJoinRule, so that the compound expression in either "ON" clause or "WHERE" clause would be handled properly.
          Hide
          julianhyde Julian Hyde added a comment -

          If ProjectJoinTransposeRule (formerly PushProjectThroughJoinRule) and FilterJoinRule (formerly PushFilterPastJoinRule) are enabled it ought to work. We should end up with a project under the join, projecting deptno+0, just like 'ANSI style' above.

          Show
          julianhyde Julian Hyde added a comment - If ProjectJoinTransposeRule (formerly PushProjectThroughJoinRule) and FilterJoinRule (formerly PushFilterPastJoinRule) are enabled it ought to work. We should end up with a project under the join, projecting deptno+0, just like 'ANSI style' above.
          Hide
          vladimirsitnikov Vladimir Sitnikov added a comment - - edited

          I investigated the issue and my conclusion is as follows:
          1) PushProjectPastJoinRule.INSTANCE is not enabled by default
          2) if I just add the rule it does not make the plans better. The rule does fire, however its sanity checks fail right after the start of onMatch.

          I believe the bug is in the definition of the INSTANCE:

            public static final PushProjectPastJoinRule INSTANCE =
                new PushProjectPastJoinRule(PushProjector.ExprCondition.FALSE);
          

          If I change FALSE to TRUE, then the plans become good.
          I tried some variations and they work fine (from a plan perspective):
          e.deptno = d.deptno+0
          e.deptno = d.deptno+d.deptno
          e.deptno + e.empid = d.deptno
          e.deptno = d.deptno+d.deptno and e.deptno + e.empid = d.deptno
          e.deptno = d.deptno+d.deptno and e.deptno + e.empid = d.deptno and e.empid + d.deptno = 0 <-- here the latest condition is not pushed.

          I suggest the following:
          1) Enable the rule by default
          2) Rewrite if (pushProject.locateAllRefs()) return; part to PushProjectPastJoinRule.matches method
          3) Add some tests.

          Do you think it is the right approach here?

          Show
          vladimirsitnikov Vladimir Sitnikov added a comment - - edited I investigated the issue and my conclusion is as follows: 1) PushProjectPastJoinRule.INSTANCE is not enabled by default 2) if I just add the rule it does not make the plans better. The rule does fire, however its sanity checks fail right after the start of onMatch . I believe the bug is in the definition of the INSTANCE : public static final PushProjectPastJoinRule INSTANCE = new PushProjectPastJoinRule(PushProjector.ExprCondition.FALSE); If I change FALSE to TRUE , then the plans become good. I tried some variations and they work fine (from a plan perspective): e.deptno = d.deptno+0 e.deptno = d.deptno+d.deptno e.deptno + e.empid = d.deptno e.deptno = d.deptno+d.deptno and e.deptno + e.empid = d.deptno e.deptno = d.deptno+d.deptno and e.deptno + e.empid = d.deptno and e.empid + d.deptno = 0 <-- here the latest condition is not pushed. I suggest the following: 1) Enable the rule by default 2) Rewrite if (pushProject.locateAllRefs()) return; part to PushProjectPastJoinRule.matches method 3) Add some tests. Do you think it is the right approach here?
          Hide
          vladimirsitnikov Vladimir Sitnikov added a comment - - edited

          When ProjectJoinTransposeRule is enabled, certain tests take forever to plan.
          When ProjectFilterTransposeRule is enabled, certain tests take forever to plan.
          For instance, JdbcTest.testInnerJoinValues just does not finish in any reasonable time.

          Show
          vladimirsitnikov Vladimir Sitnikov added a comment - - edited When ProjectJoinTransposeRule is enabled, certain tests take forever to plan. When ProjectFilterTransposeRule is enabled, certain tests take forever to plan. For instance, JdbcTest.testInnerJoinValues just does not finish in any reasonable time.
          Hide
          julianhyde Julian Hyde added a comment -

          When ProjectFilterTransposeRule is enabled, certain tests take forever to plan. For instance, JdbcTest.testInnerJoinValues just does not finish in any reasonable time.

          I'm not surprised by this. ProjectFilterTransposeRule is the converse of FilterProjectTransposeRule, which is the normal, sensible, instant-reduction-in-cost rule to apply. Enabling both expands the search space. Ideally Calcite would use "importance" and stop before it got to those far-reaches of the search space. But it doesn't currently. So I'd advise only enabling ProjectFilterTransposeRule in a Hep plan.

          Show
          julianhyde Julian Hyde added a comment - When ProjectFilterTransposeRule is enabled, certain tests take forever to plan. For instance, JdbcTest.testInnerJoinValues just does not finish in any reasonable time. I'm not surprised by this. ProjectFilterTransposeRule is the converse of FilterProjectTransposeRule , which is the normal, sensible, instant-reduction-in-cost rule to apply. Enabling both expands the search space. Ideally Calcite would use "importance" and stop before it got to those far-reaches of the search space. But it doesn't currently. So I'd advise only enabling ProjectFilterTransposeRule in a Hep plan.
          Hide
          julianhyde Julian Hyde added a comment -

          Do you think it is the right approach here?

          Yes.

          Show
          julianhyde Julian Hyde added a comment - Do you think it is the right approach here? Yes.
          Hide
          jni Jinfeng Ni added a comment -

          Hi Julian,

          Submitted a new PR for CALCITE-457. See https://github.com/apache/incubator-calcite/pull/92

          It uses a different approach to fix the issue of non-ansi join case : try to leverage the existing code logic for ansi-join case, and call that logic in FilterJoinRule to handle non-ansi join case.

          Please review the patch and let me know if there is any problem.

          Thanks!

          Show
          jni Jinfeng Ni added a comment - Hi Julian, Submitted a new PR for CALCITE-457 . See https://github.com/apache/incubator-calcite/pull/92 It uses a different approach to fix the issue of non-ansi join case : try to leverage the existing code logic for ansi-join case, and call that logic in FilterJoinRule to handle non-ansi join case. Please review the patch and let me know if there is any problem. Thanks!
          Hide
          jni Jinfeng Ni added a comment -

          Hi Julian,

          I modified the code based on your comments. The PR is updated at https://github.com/apache/incubator-calcite/pull/92. Please take a look.

          Here are responses to your comments.

          Comment 1 . In misc.oq, a field that was called "DESC" is now called "EXPR$1". Can you restore the old name?

          [jni] I guess you are talking about the JdbcTest.testInnerJoinValues(), where "DESC" is changed to "EXPR$1" in EXPLAIN.

          Actually, the field name change happens only in EXPLAIN PLAN output; the query result is still using "DESC". I spent quite some time trying to figure out why the field name is changed in EXPLAIN. I do not have a completely clear idea why it happened. But seems the cause might be related to the fact that Calcite put two RelNodes with different rowType under the same RelSet.

          The following is from the calcite trace "before" my code change:

          Set#1, type: RecordType(INTEGER EXPR$0, CHAR(8) EXPR$1)
          rel#11:Subset#1.NONE.[], best=null, importance=0.5904900000000001
          rel#1:LogicalValues.NONE.[[0, 1], [1]](type=RecordType(INTEGER EXPR$0, CHAR(8) EXPR$1),tuples=[

          { 10, 'SameName' }

          ]), rowcount=1.0, cumulative cost=

          {inf}
          rel#12:LogicalProject.NONE.[[0, 1], [1]](input=rel#11:Subset#1.NONE.[],ID=$0,DESC=$1), rowcount=1.0, cumulative cost={inf}

          In the above, the LogicalValues has (EXPR$0, EXPR$1), LogicalProject has (ID, DESC). Yet Calcite still put them together under the same RelSet. My guess is CALCITE-457 patch will impact the order of some rules firing, and somehow the rowType of downstream RelNode is messed up.

          On the other hand, I think Calcite's API does not guarantee that the intermediate RelNode will keep the same field name; the output field name is ensured to be "DESC" via validator.getValidatedNodeType(). That's why the query result still has "DESC" in the output. Therefore, I feel it might be ok to have different field name in the EXPLAIN plan output.

          Another comment : this testcase does not have the join condition pushed, simply because f costing : Values() has one row only. I tried at least with two rows, and verified the condition will be pushed down.

          Comment 2: It's appropriate to always create a LogicalJoin when in SqlToRelConverter, less so in general-purpose planner rules. Can you use a join factory and not add method RelOptUtil.createJoin?

          [jni]
          I tried to add join factory to FilterJoinRule, that seems require more change. In stead, I chose to passing in originalJoin, and use join.copy() method. That way, in the general-purpose planner rule or SqlToRelConverter, the new created Join will be of the same class of original join node.

          Comment 3: re-format
          [jni] Now I pass in param originalJoin. No need for such format.

          Comment 4: join.oq should end with newline
          [jni] Done.

          Comment 5: Can you add a test for FilterJoinRule's new capability to RelOptRulesTest.
          [jni] testPushJoinCondDownToProject() is Added.

          Show
          jni Jinfeng Ni added a comment - Hi Julian, I modified the code based on your comments. The PR is updated at https://github.com/apache/incubator-calcite/pull/92 . Please take a look. Here are responses to your comments. Comment 1 . In misc.oq, a field that was called "DESC" is now called "EXPR$1". Can you restore the old name? [jni] I guess you are talking about the JdbcTest.testInnerJoinValues(), where "DESC" is changed to "EXPR$1" in EXPLAIN. Actually, the field name change happens only in EXPLAIN PLAN output; the query result is still using "DESC". I spent quite some time trying to figure out why the field name is changed in EXPLAIN. I do not have a completely clear idea why it happened. But seems the cause might be related to the fact that Calcite put two RelNodes with different rowType under the same RelSet. The following is from the calcite trace "before" my code change: Set#1, type: RecordType(INTEGER EXPR$0, CHAR(8) EXPR$1) rel#11:Subset#1.NONE.[], best=null, importance=0.5904900000000001 rel#1:LogicalValues.NONE.[ [0, 1] , [1] ](type=RecordType(INTEGER EXPR$0, CHAR(8) EXPR$1),tuples=[ { 10, 'SameName' } ]), rowcount=1.0, cumulative cost= {inf} rel#12:LogicalProject.NONE.[ [0, 1] , [1] ](input=rel#11:Subset#1.NONE.[],ID=$0,DESC=$1), rowcount=1.0, cumulative cost={inf} In the above, the LogicalValues has (EXPR$0, EXPR$1), LogicalProject has (ID, DESC). Yet Calcite still put them together under the same RelSet. My guess is CALCITE-457 patch will impact the order of some rules firing, and somehow the rowType of downstream RelNode is messed up. On the other hand, I think Calcite's API does not guarantee that the intermediate RelNode will keep the same field name; the output field name is ensured to be "DESC" via validator.getValidatedNodeType(). That's why the query result still has "DESC" in the output. Therefore, I feel it might be ok to have different field name in the EXPLAIN plan output. Another comment : this testcase does not have the join condition pushed, simply because f costing : Values() has one row only. I tried at least with two rows, and verified the condition will be pushed down. Comment 2: It's appropriate to always create a LogicalJoin when in SqlToRelConverter, less so in general-purpose planner rules. Can you use a join factory and not add method RelOptUtil.createJoin? [jni] I tried to add join factory to FilterJoinRule, that seems require more change. In stead, I chose to passing in originalJoin, and use join.copy() method. That way, in the general-purpose planner rule or SqlToRelConverter, the new created Join will be of the same class of original join node. Comment 3: re-format [jni] Now I pass in param originalJoin. No need for such format. Comment 4: join.oq should end with newline [jni] Done. Comment 5: Can you add a test for FilterJoinRule's new capability to RelOptRulesTest. [jni] testPushJoinCondDownToProject() is Added.
          Hide
          julianhyde Julian Hyde added a comment -

          Looks good. I removed the RelOptUtil.createJoin method – the factory method suffices – and did a bit of cleanup. I will push to master shortly.

          Show
          julianhyde Julian Hyde added a comment - Looks good. I removed the RelOptUtil.createJoin method – the factory method suffices – and did a bit of cleanup. I will push to master shortly.
          Show
          julianhyde Julian Hyde added a comment - Fixed in http://git-wip-us.apache.org/repos/asf/incubator-calcite/commit/f3cae130 .
          Hide
          jnadeau Jacques Nadeau added a comment -

          Resolved in release 1.4.0-incubating (2015-08-23)

          Show
          jnadeau Jacques Nadeau added a comment - Resolved in release 1.4.0-incubating (2015-08-23)

            People

            • Assignee:
              julianhyde Julian Hyde
              Reporter:
              vladimirsitnikov Vladimir Sitnikov
            • Votes:
              0 Vote for this issue
              Watchers:
              4 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:

                Development