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

Avoid LIMIT with trivial ORDER BY being pushed through JOIN endlessly

    Details

    • Type: Bug
    • Status: Closed
    • Priority: Minor
    • Resolution: Fixed
    • Affects Version/s: 1.10.0
    • Fix Version/s: 1.11.0
    • Component/s: core
    • Labels:
      None

      Description

      Currently LIMIT with trivial ORDER BY will be pushed through a JOIN endlessly by SortJoinTransposeRule, because the method RelMdUtil.checkInputForCollationAndLimit used to prevent endless matching does not know that an sort on zero keys is trivially satisfied (without requiring a Sort) by any relational expression:

          // Check if the input is already sorted
          boolean alreadySorted = false;
          if (!alreadySorted) {
            for (RelCollation inputCollation : mq.collations(input)) {
              if (inputCollation.satisfies(collation)) {
                alreadySorted = true;
                break;
              }
            }
          }
      

      if mq.collations(input) returns an empty array, alreadySorted will always be false even if the required collation is an empty collation (which indicates there's no need to sort). As a result, the check method RelMdUtil.checkInputForCollationAndLimit will always return false and the SortJoinTransposeRule will keep being fired endlessly.

        Activity

        Hide
        maryannxue Maryann Xue added a comment -

        Julian Hyde, could you please kindly review this PR for me? Thanks in advance! https://github.com/apache/calcite/pull/327

        Show
        maryannxue Maryann Xue added a comment - Julian Hyde , could you please kindly review this PR for me? Thanks in advance! https://github.com/apache/calcite/pull/327
        Hide
        julianhyde Julian Hyde added a comment -

        Can you fix a typo: s/filed/fired. Also I clarified the abstract (to my eyes, anyway). With that, +1.

        Show
        julianhyde Julian Hyde added a comment - Can you fix a typo: s/filed/fired. Also I clarified the abstract (to my eyes, anyway). With that, +1.
        Hide
        maryannxue Maryann Xue added a comment -

        Sorry, Julian Hyde, I didn't make myself very clear. The problem was that the rule would keep being fired endlessly if the Sort was a LIMIT with trivial ORDER BY.

        Show
        maryannxue Maryann Xue added a comment - Sorry, Julian Hyde , I didn't make myself very clear. The problem was that the rule would keep being fired endlessly if the Sort was a LIMIT with trivial ORDER BY.
        Hide
        maryannxue Maryann Xue added a comment -

        And there is actually another small bug with SortJoinTransposeRule. When offset is not null, the rule should not be fired. Right now it does not apply this check.

        Show
        maryannxue Maryann Xue added a comment - And there is actually another small bug with SortJoinTransposeRule. When offset is not null, the rule should not be fired. Right now it does not apply this check.
        Hide
        julianhyde Julian Hyde added a comment -

        I guessed it was something like that. Anyway, I wanted to change the abstract to something that would be meaningful in the release notes. Feel free to change it again.

        If they've written OFFSET 10 LIMIT 20 I don't see why you shouldn't push that offset + limit to the input of the join. Sure, the query results will be non-deterministic, but ORDER BY sal OFFSET 10 LIMIT 20 is non-deterministic too, because sal is not unique.

        Show
        julianhyde Julian Hyde added a comment - I guessed it was something like that. Anyway, I wanted to change the abstract to something that would be meaningful in the release notes. Feel free to change it again. If they've written OFFSET 10 LIMIT 20 I don't see why you shouldn't push that offset + limit to the input of the join. Sure, the query results will be non-deterministic, but ORDER BY sal OFFSET 10 LIMIT 20 is non-deterministic too, because sal is not unique.
        Hide
        maryannxue Maryann Xue added a comment -

        Yes, neither the original subject nor the description was very clear. I will change them according based on your version.
        Right, they are not deterministic. But let's say OFFSET is actually the number of rows we should skip before outputting the result. In those cases where the result is not deterministic before applying OFFSET, it does not matter which rows we skip but it does matter how many rows we will skip. Especially when the number of rows before applying LIMIT is smaller than LIMIT itself, we could end up returning less rows than we should. A left or right join can return one or more rows for each row from the "outer" side, so if we push down OFFSET, it's likely that we can skip more rows than we should.

        Show
        maryannxue Maryann Xue added a comment - Yes, neither the original subject nor the description was very clear. I will change them according based on your version. Right, they are not deterministic. But let's say OFFSET is actually the number of rows we should skip before outputting the result. In those cases where the result is not deterministic before applying OFFSET, it does not matter which rows we skip but it does matter how many rows we will skip. Especially when the number of rows before applying LIMIT is smaller than LIMIT itself, we could end up returning less rows than we should. A left or right join can return one or more rows for each row from the "outer" side, so if we push down OFFSET, it's likely that we can skip more rows than we should.
        Hide
        julianhyde Julian Hyde added a comment -

        Agreed, we can only push down LIMIT or OFFSET to the "count-preserving" side. I think we already do that properly. We just shouldn't worry about whether the order of the rows is deterministic; that's the user's problem.

        Show
        julianhyde Julian Hyde added a comment - Agreed, we can only push down LIMIT or OFFSET to the "count-preserving" side. I think we already do that properly. We just shouldn't worry about whether the order of the rows is deterministic; that's the user's problem.
        Hide
        maryannxue Maryann Xue added a comment -

        Take this query as an example:

        select d.deptno, empno
            from sales.dept d
            left join sales.emp e using (deptno)
            order by d.deptno offset 1
        

        And rows from "dept" and "emp" tables are like:

        "dept"
          deptno
          10
          20
          30
        
        "emp"
          empno    deptno
          101      10
          102      10
          105      30
        

        The expected output is:

        d.deptno    e.empno
        10          102
        20          null
        30          105
        

        While after applying SortJoinTransposeRule, the rel becomes:

        LogicalProject(DEPTNO=[$0], EMPNO=[$2])
          LogicalSort(sort0=[$0], dir0=[ASC], offset=[1])
            LogicalJoin(condition=[=($0, $9)], joinType=[left])
              LogicalSort(sort0=[$0], dir0=[ASC], offset=[1])
                LogicalTableScan(table=[[CATALOG, SALES, DEPT]])
              LogicalTableScan(table=[[CATALOG, SALES, EMP]])
        

        And the output will now be:

        d.deptno    e.empno
        20          null
        30          105
        

        because deptno "10" has been skipped from the left relation by the pushed through Sort node.

        Show
        maryannxue Maryann Xue added a comment - Take this query as an example: select d.deptno, empno from sales.dept d left join sales.emp e using (deptno) order by d.deptno offset 1 And rows from "dept" and "emp" tables are like: "dept" deptno 10 20 30 "emp" empno deptno 101 10 102 10 105 30 The expected output is: d.deptno e.empno 10 102 20 null 30 105 While after applying SortJoinTransposeRule, the rel becomes: LogicalProject(DEPTNO=[$0], EMPNO=[$2]) LogicalSort(sort0=[$0], dir0=[ASC], offset=[1]) LogicalJoin(condition=[=($0, $9)], joinType=[left]) LogicalSort(sort0=[$0], dir0=[ASC], offset=[1]) LogicalTableScan(table=[[CATALOG, SALES, DEPT]]) LogicalTableScan(table=[[CATALOG, SALES, EMP]]) And the output will now be: d.deptno e.empno 20 null 30 105 because deptno "10" has been skipped from the left relation by the pushed through Sort node.
        Hide
        julianhyde Julian Hyde added a comment -

        In that query, neither side is count-preserving. So I don't think it's valid to push either LIMIT or OFFSET.

        In the following query, the dept side is count-preserving:

        select d.deptno, empno
            from sales.dept d
            right join sales.emp e using (deptno)
            order by d.deptno offset 1
        

        For a given emp record, there is no more than one matching dept row (because dept.deptno is unique) and now fewer than one row (because right join).

        Show
        julianhyde Julian Hyde added a comment - In that query, neither side is count-preserving. So I don't think it's valid to push either LIMIT or OFFSET. In the following query, the dept side is count-preserving: select d.deptno, empno from sales.dept d right join sales.emp e using (deptno) order by d.deptno offset 1 For a given emp record, there is no more than one matching dept row (because dept.deptno is unique) and now fewer than one row (because right join ).
        Hide
        maryannxue Maryann Xue added a comment -

        In that query, neither side is count-preserving. So I don't think it's valid to push either LIMIT or OFFSET.

        The rule works like this right now, which I'm point out is wrong.

        The SortJoinTransposeRule does not really consider the "count-preserving" attribute. What it is trying to do is mainly to reduce the row count from the "outer" side relation, and it's definitely invalid to push the Sort node to the other child relation. Because whether a LIMIT or an OFFSET is pushed through onto the other side (dept side in the above RIGHT JOIN query), the join output row which is supposed to be eliminated will generate a null field instead.

        Show
        maryannxue Maryann Xue added a comment - In that query, neither side is count-preserving. So I don't think it's valid to push either LIMIT or OFFSET. The rule works like this right now, which I'm point out is wrong. The SortJoinTransposeRule does not really consider the "count-preserving" attribute. What it is trying to do is mainly to reduce the row count from the "outer" side relation, and it's definitely invalid to push the Sort node to the other child relation. Because whether a LIMIT or an OFFSET is pushed through onto the other side (dept side in the above RIGHT JOIN query), the join output row which is supposed to be eliminated will generate a null field instead.
        Hide
        julianhyde Julian Hyde added a comment -

        OK, I understand now. The "count-preserving" thing could be a future enhancement. In the case that an input is count-preserving (which does not happen often) we can push the limit and offset through, and remove them from above the join.

        Show
        julianhyde Julian Hyde added a comment - OK, I understand now. The "count-preserving" thing could be a future enhancement. In the case that an input is count-preserving (which does not happen often) we can push the limit and offset through, and remove them from above the join.
        Hide
        maryannxue Maryann Xue added a comment -

        Yes, agree. In the query you pointed out plus one little change:

        select d.deptno, empno
            from sales.dept d
            right join sales.emp e using (deptno)
            order by e.deptno offset 1
        

        We can actually push down the Sort node to "emp" side and remove the one above the Join.
        I will open another two JIRAs addressing the OFFSET bug and this potential optimization.

        Show
        maryannxue Maryann Xue added a comment - Yes, agree. In the query you pointed out plus one little change: select d.deptno, empno from sales.dept d right join sales.emp e using (deptno) order by e.deptno offset 1 We can actually push down the Sort node to "emp" side and remove the one above the Join. I will open another two JIRAs addressing the OFFSET bug and this potential optimization.
        Show
        maryannxue Maryann Xue added a comment - Fixed in https://git1-us-west.apache.org/repos/asf?p=calcite.git;a=commit;h=6a2d9e0 .
        Hide
        maryannxue Maryann Xue added a comment -

        Sorry, I was wrong about the above statement, the above Sort node can only be removed if it is a trivial ORDER BY coz we can't have any assumption over the join output collation.

        Show
        maryannxue Maryann Xue added a comment - Sorry, I was wrong about the above statement, the above Sort node can only be removed if it is a trivial ORDER BY coz we can't have any assumption over the join output collation.
        Hide
        julianhyde Julian Hyde added a comment -

        Resolved in release 1.11.0 (2017-01-11).

        Show
        julianhyde Julian Hyde added a comment - Resolved in release 1.11.0 (2017-01-11).

          People

          • Assignee:
            maryannxue Maryann Xue
            Reporter:
            maryannxue Maryann Xue
          • Votes:
            0 Vote for this issue
            Watchers:
            2 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development