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

Inefficient plan for correlated sub-queries

    Details

    • Type: Improvement
    • Status: Closed
    • Priority: Major
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 1.12.0
    • Component/s: core
    • Labels:

      Description

      For co-related queries such as

       select sal from emp where empno IN (select deptno from dept where emp.job = dept.name) 

      Calcite generates following plan (SubqueryRemove Rule + Decorrelation)

      LogicalProject(SAL=[$5])
        LogicalProject(EMPNO=[$0], ENAME=[$1], JOB=[$2], MGR=[$3], HIREDATE=[$4], SAL=[$5], COMM=[$6], DEPTNO=[$7], SLACKER=[$8])
          LogicalJoin(condition=[AND(=($2, $10), =($0, $9))], joinType=[inner])
            LogicalTableScan(table=[[CATALOG, SALES, EMP]])
            LogicalAggregate(group=[{0, 1}])
              LogicalProject(DEPTNO=[$0], JOB=[$1])
                LogicalProject(DEPTNO=[$0], JOB=[$2])
                  LogicalJoin(condition=[=($2, $1)], joinType=[inner])
                    LogicalTableScan(table=[[CATALOG, SALES, DEPT]])
                    LogicalAggregate(group=[{0}])
                      LogicalProject(JOB=[$2])
                        LogicalTableScan(table=[[CATALOG, SALES, EMP]])
      

      As you can notice there is a outer table scan (EMP in this case) to retrieve all distinct values for co-related column (EMP.JOB here), which is then joined with inner table (DEPT).
      I am not sure why is this step required. After this join Calcite is anyway doing group by to generate all distinct values for correlated and result column (DEPTNO, JOB) which is then joined with outer table.
      I think the scan + join of outer table with inner table to generate co-rrelated values is un-necessary and is not required.

        Issue Links

          Activity

          Hide
          vgarg Vineet Garg added a comment -

          Note that Calcite seems to generate similar plan for EXISTS/NOT EXISTS correlated queries as well

          Show
          vgarg Vineet Garg added a comment - Note that Calcite seems to generate similar plan for EXISTS/NOT EXISTS correlated queries as well
          Hide
          julianhyde Julian Hyde added a comment -

          Calcite's general algorithm to de-correlate creates a "value generator" query to generate all possible values of a correlating variable. In some cases, such as this, the value generator is not necessary because the variable appears in an equi-join. But it's not currently smart enough to skip the value generator query.

          Show
          julianhyde Julian Hyde added a comment - Calcite's general algorithm to de-correlate creates a "value generator" query to generate all possible values of a correlating variable. In some cases, such as this, the value generator is not necessary because the variable appears in an equi-join. But it's not currently smart enough to skip the value generator query.
          Hide
          julianhyde Julian Hyde added a comment -

          I've made progress (see dev branch) and several plans are showing improvement but there are 7 test failures, so this is not going to make the cut for release 1.11.

          Show
          julianhyde Julian Hyde added a comment - I've made progress (see dev branch) and several plans are showing improvement but there are 7 test failures, so this is not going to make the cut for release 1.11.
          Hide
          vgarg Vineet Garg added a comment - - edited

          Hi Julian Hyde,

          I have a commit at https://github.com/vineetgarg02/calcite/commit/f3bb8941ac258b49ce88dbe48110ee0bd1c8fb91 which fixes following test failures

          • SqlToRelConverterTest.testNestedCorrelationsDecorrelated
          • SqlToRelConverterTest.testNestedCorrelationsDecorrelated2
          • RelOptRulesTest.testWhereNotInCorrelated
          • RelOptRulesTest.testWhereNotInCorrelated2

          I am not sure about blank.iq as I wasn't able to run it.
          Also I see org.apache.calcite.test.MaterializationTest.testSubQuery is still failing but from what I have looked this is expected and needs a test output update.

          Can you take a look at this commit and incorporate into your branch and re-run calcite tests? Let me know if you would like me to upload the patch here.

          Note that my fix is on top of your 1494-val-gen changes.

          Show
          vgarg Vineet Garg added a comment - - edited Hi Julian Hyde , I have a commit at https://github.com/vineetgarg02/calcite/commit/f3bb8941ac258b49ce88dbe48110ee0bd1c8fb91 which fixes following test failures SqlToRelConverterTest.testNestedCorrelationsDecorrelated SqlToRelConverterTest.testNestedCorrelationsDecorrelated2 RelOptRulesTest.testWhereNotInCorrelated RelOptRulesTest.testWhereNotInCorrelated2 I am not sure about blank.iq as I wasn't able to run it. Also I see org.apache.calcite.test.MaterializationTest.testSubQuery is still failing but from what I have looked this is expected and needs a test output update. Can you take a look at this commit and incorporate into your branch and re-run calcite tests? Let me know if you would like me to upload the patch here. Note that my fix is on top of your 1494-val-gen changes.
          Hide
          julianhyde Julian Hyde added a comment -

          Fixed in http://git-wip-us.apache.org/repos/asf/calcite/commit/73e437fe. Many thanks to Vineet Garg for his contributions to the fix!

          Show
          julianhyde Julian Hyde added a comment - Fixed in http://git-wip-us.apache.org/repos/asf/calcite/commit/73e437fe . Many thanks to Vineet Garg for his contributions to the fix!
          Hide
          julianhyde Julian Hyde added a comment -

          Resolved in release 1.12.0 (2017-03-24).

          Show
          julianhyde Julian Hyde added a comment - Resolved in release 1.12.0 (2017-03-24).

            People

            • Assignee:
              julianhyde Julian Hyde
              Reporter:
              vgarg Vineet Garg
            • Votes:
              0 Vote for this issue
              Watchers:
              4 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:

                Development