Derby
  1. Derby
  2. DERBY-4471

Left outer join reassociation rewrite gives wrong result

    Details

    • Type: Bug Bug
    • Status: Closed
    • Priority: Major Major
    • Resolution: Fixed
    • Affects Version/s: 10.0.2.0, 10.0.2.1, 10.1.1.0, 10.1.2.1, 10.1.3.1, 10.2.1.6, 10.2.2.0, 10.3.1.4, 10.3.2.1, 10.3.3.0, 10.4.1.3, 10.4.2.0, 10.5.1.1, 10.5.2.0, 10.5.3.0
    • Fix Version/s: 10.6.2.1, 10.7.1.1
    • Component/s: SQL
    • Bug behavior facts:
      Wrong query result

      Description

      The following script and output shows the problem:

      > create table r(c1 char(1));
      > create table s(c1 char(1), c2 char(1));
      > create table t(c1 char(1));

      > insert into r values 'a';
      > insert into s values ('b', default);
      > insert into t values ('c');

      > select * from s left outer join t on s.c2=t.c1 or s.c2 is null;

      C1 |C2 |C1
      --------------
      b |NULL|c

      > select * from r left outer join s on r.c1=s.c1;
      C1 |C1 |C2
      --------------
      a |NULL|NULL

      > select * from (r left outer join s on r.c1=s.c1) left outer join t on s.c2=t.c1 or s.c2 is null;

      C1 |C1 |C2 |C1
      -------------------
      a |NULL|NULL|c

      > select * from r left outer join (s left outer join t on s.c2=t.c1 or s.c2 is null) on r.c1=s.c1;

      C1 |C1 |C2 |C1
      -------------------
      a |NULL|NULL|c

      The last result is wrong. The correct answer should be:

      C1 |C1 |C2 |C1
      -------------------
      a |NULL|NULL|NULL

      since in the last form, the left table r has the value 'a', which does
      not match any row in result of the compound inner given the join
      predicate ("r.c1=s.c1"), so all nulls should be appended to the 'a'
      from the outer table r.

      This happens because internally the last form is rewritten to the
      second but the last form (left-deep), but this rewrite is not
      justified here unless the join predicate on s rejects null, which the
      present one explicitly does not ("or s.c2 is null"). Cf. for example
      [1], page 52, which describes this transform and its prerequisite
      condition as indentity #7.

      [1] Galindo-Legaria, C. & Rosenthal, A.: "Outerjoin simplification and
      reordering for query optimization", ACM Transactions on Database
      Systems, Vol 22, No 1, March 1997.

      1. derby-4471-1d.stat
        0.6 kB
        Dag H. Wanvik
      2. derby-4471-1d.diff
        2.06 MB
        Dag H. Wanvik
      3. derby-4471-1c.stat
        0.7 kB
        Dag H. Wanvik
      4. derby-4471-1c.diff
        2.06 MB
        Dag H. Wanvik
      5. derby-4471-1b.stat
        0.2 kB
        Dag H. Wanvik
      6. derby-4471-1b.diff
        103 kB
        Dag H. Wanvik
      7. derby-4471-1a.stat
        0.2 kB
        Dag H. Wanvik
      8. derby-4471-1a.diff
        96 kB
        Dag H. Wanvik
      9. query_plan_derby_4471.pdf
        77 kB
        Nirmal Fernando
      10. derby-4471-junit-repro.diff
        4 kB
        Dag H. Wanvik

        Issue Links

          Activity

          Hide
          Dag H. Wanvik added a comment -

          Closing again, the tag has been added.

          Show
          Dag H. Wanvik added a comment - Closing again, the tag has been added.
          Hide
          Kathey Marsden added a comment -

          reopen to add backport reject label

          Show
          Kathey Marsden added a comment - reopen to add backport reject label
          Hide
          Dag H. Wanvik added a comment -

          Merged back to 10.6 branch as svn 997924.

          Show
          Dag H. Wanvik added a comment - Merged back to 10.6 branch as svn 997924.
          Hide
          Dag H. Wanvik added a comment -

          Committed derby-4471-1d as svn 990292, resolving.

          Show
          Dag H. Wanvik added a comment - Committed derby-4471-1d as svn 990292, resolving.
          Hide
          Dag H. Wanvik added a comment - - edited

          Thanks for considering this, Lily. I agree, so I made a new variant of the assertFullResultSet method and
          used that in the relevant places in LojReorderTest. Uploading a new version of the patch containing this change + some minor code cleanups and Javacoc improvements. Re-running regressions.

          Note: Due to DERBY-159 (I think), the client doesn't consistently return the warnings, so the assertion method currently does its thing only when running with the embedded client. I made notes of this in the code and in DERBY-159, so we can change this if/when this bug is fixed.

          Show
          Dag H. Wanvik added a comment - - edited Thanks for considering this, Lily. I agree, so I made a new variant of the assertFullResultSet method and used that in the relevant places in LojReorderTest. Uploading a new version of the patch containing this change + some minor code cleanups and Javacoc improvements. Re-running regressions. Note: Due to DERBY-159 (I think), the client doesn't consistently return the warnings, so the assertion method currently does its thing only when running with the embedded client. I made notes of this in the code and in DERBY-159 , so we can change this if/when this bug is fixed.
          Hide
          Lily Wei added a comment -

          I will go for option c). It gives you the freedom to recognize the expected behavior with a warning. Also, it leaves room for lots of comments for further development down the road. And, we will have computer to do the filter work for us. However, the warning could be over look.

          Show
          Lily Wei added a comment - I will go for option c). It gives you the freedom to recognize the expected behavior with a warning. Also, it leaves room for lots of comments for further development down the road. And, we will have computer to do the filter work for us. However, the warning could be over look.
          Hide
          Dag H. Wanvik added a comment -

          One note about the conversion of lojreorder.sql to JUnit: The old test's master contains several occurence of this warning on the result sets:

          WARNING 01003: Null values were eliminated from the argument of a column function.

          Our JUnit idiom for asserting result sets, assertFullResultSet ignores such warnings. I could either

          a) go ahead and ignore these warnings in the JUnit test
          b) inspect those particar result sets "manually" (tedious, quite a lot)
          c) make a new variant of assertFullResultSet which allows one to specify expected warnings

          Opinions?

          Show
          Dag H. Wanvik added a comment - One note about the conversion of lojreorder.sql to JUnit: The old test's master contains several occurence of this warning on the result sets: WARNING 01003: Null values were eliminated from the argument of a column function. Our JUnit idiom for asserting result sets, assertFullResultSet ignores such warnings. I could either a) go ahead and ignore these warnings in the JUnit test b) inspect those particar result sets "manually" (tedious, quite a lot) c) make a new variant of assertFullResultSet which allows one to specify expected warnings Opinions?
          Hide
          Dag H. Wanvik added a comment -

          Thanks for looking at this, Rick.

          The thrust of this patch is not transformation of outer join to inner join, but rather reassociating one form of left outer join (right deep) to another form of left outer join (left deep). The new Javadoc for HalfOuterJoinNode#LOJ_reorderable and HalfOuterJoinNode#isNullRejecting
          is intended to explain how this now works. If you find this confusing, let me know and I'll try to improve it.

          As for the transformation of outer join to inner join (HalfOuterJoinNode#transformOuterJoins), this patch doesn't touch that, but the condition is related: The must exist a null intolerant predicate on the inner table.

          Show
          Dag H. Wanvik added a comment - Thanks for looking at this, Rick. The thrust of this patch is not transformation of outer join to inner join, but rather reassociating one form of left outer join (right deep) to another form of left outer join (left deep). The new Javadoc for HalfOuterJoinNode#LOJ_reorderable and HalfOuterJoinNode#isNullRejecting is intended to explain how this now works. If you find this confusing, let me know and I'll try to improve it. As for the transformation of outer join to inner join (HalfOuterJoinNode#transformOuterJoins), this patch doesn't touch that, but the condition is related: The must exist a null intolerant predicate on the inner table.
          Hide
          Rick Hillegas added a comment -

          Thanks for the patch, Dag. I think that this will be a big step forward in clarifying and cleaning up our implementation of outer joins. It would be helpful for me if HalfOuterJoinNode (or some other source file) contained a tidy, comprehensive explanation of the rules which determine when a nested outer join can be pre-processed into an inner join. I don't think we need all of the rules, just the rules which we apply. The references to Galindo-Legaria are helpful but it would be nice to be able to read this code without having to flip back and forth to an external text. Thanks.

          Show
          Rick Hillegas added a comment - Thanks for the patch, Dag. I think that this will be a big step forward in clarifying and cleaning up our implementation of outer joins. It would be helpful for me if HalfOuterJoinNode (or some other source file) contained a tidy, comprehensive explanation of the rules which determine when a nested outer join can be pre-processed into an inner join. I don't think we need all of the rules, just the rules which we apply. The references to Galindo-Legaria are helpful but it would be nice to be able to read this code without having to flip back and forth to an external text. Thanks.
          Hide
          Dag H. Wanvik added a comment -

          Actually, the my first patch was both too liberal (due to bug) and too
          restrictive (design). I instrumented the code to show when reorderings
          took place before and after.

          Uploading version 1c of this patch. It now allows all correct
          reorderings that the old implementation did, but still fixes the wrong
          ones seen in this issue. In addition, it opens up for reordering in a
          few cases where the old implementation did not, by improving the
          analysis for null rejecting join predicates, cf. the equation
          mentioned in the paper by Galindo-Legaria et al:

          Prs Pst Prs Pst
          R ---> (S ---> T) == (R ---> S) ---> T

          where ---> is (left) outer join, Pxy is a null rejecting join predicate.

          The old implementation, as well as my previous version of this patch,
          required equality operators, but the new implementation allows for the
          other relational operators as well that also deny nulls, of this form
          (the join predicate is in CNF at this time in processing):

          X relop Y [and .. and X-n relop Y-n]

          where at least one relop refers to columns from both R,S or S,T.

          Note that the predicate analysis could be liberalized even more at the
          cost of a more sophisticated analysis, e.g. "R.x1 = S.y1 OR R.x2 = S.y2"
          would be safe, but disjunction (OR) is currently not accepted.

          The major problem with the old implementation was that, although it
          did check that Prs did not reference T, it did not assert Pst.

          New test cases have been added to OuterJoinTest that pass with the new
          implementation, but gave wrong results with the old, cf. fixtures
          OuterJoinTest#testDerby_4471a and OuterJoinTest#testDerby_4471b().

          The old style test lojreorder.sql has been converted to the JUnit test
          LojReorderTest. The test cases that now reorder and did not before,
          are annotated in LojReorderTest, look for the string 4471, or cf the
          list below.

          I added a couple of new methods to be able to assert contents in the
          execution plan, to make it convenient to verify that the reorderings
          actually took place, cf. JDBC.checkPlan and
          RuntimeStatisticsParser#assertSequence.

          Since HalfOuterJoinNode#LOJ_reorderable has largely been rewritten, it
          would probably be best to review the changes by looking at the old and
          the new versions in full. The predicate checking has been factored
          out in the method isNullRejecting.

          [Appendix]
          New reorderings from lojreorder.sql. All compute correctly as before.

          After conversion to JUnit, I have added assertions on the query plans to
          show that these reordering now actually take place.

          • select * from t left outer join (s left outer join r on (f = i)) on (b = e and a > b)
          • select * from t left outer join (s left outer join r on (f = i)) on (b = e and a = b);
          • select * from t left outer join (s left outer join r on (f = i)) on (b = e and 1 = 1)
          • select * from t left outer join (s left outer join r on (f = i)) on (b > e)
          • Makes case 1.13 work: the test says its reordered, but actually it
            is not (the "and 1=1" threw old impl off).
          • Case 1.15 now reorders ("on b1>c1" is ok) - Note to self: update comment.
          • Makes case 1.31 work, now reorders twice, earlier none ("on a1=b1 and b2=2"
            threw old impl off).
          Show
          Dag H. Wanvik added a comment - Actually, the my first patch was both too liberal (due to bug) and too restrictive (design). I instrumented the code to show when reorderings took place before and after. Uploading version 1c of this patch. It now allows all correct reorderings that the old implementation did, but still fixes the wrong ones seen in this issue. In addition, it opens up for reordering in a few cases where the old implementation did not, by improving the analysis for null rejecting join predicates, cf. the equation mentioned in the paper by Galindo-Legaria et al: Prs Pst Prs Pst R ---> (S ---> T) == (R ---> S) ---> T where ---> is (left) outer join, Pxy is a null rejecting join predicate. The old implementation, as well as my previous version of this patch, required equality operators, but the new implementation allows for the other relational operators as well that also deny nulls, of this form (the join predicate is in CNF at this time in processing): X relop Y [and .. and X-n relop Y-n] where at least one relop refers to columns from both R,S or S,T. Note that the predicate analysis could be liberalized even more at the cost of a more sophisticated analysis, e.g. "R.x1 = S.y1 OR R.x2 = S.y2" would be safe, but disjunction (OR) is currently not accepted. The major problem with the old implementation was that, although it did check that Prs did not reference T, it did not assert Pst. New test cases have been added to OuterJoinTest that pass with the new implementation, but gave wrong results with the old, cf. fixtures OuterJoinTest#testDerby_4471a and OuterJoinTest#testDerby_4471b(). The old style test lojreorder.sql has been converted to the JUnit test LojReorderTest. The test cases that now reorder and did not before, are annotated in LojReorderTest, look for the string 4471, or cf the list below. I added a couple of new methods to be able to assert contents in the execution plan, to make it convenient to verify that the reorderings actually took place, cf. JDBC.checkPlan and RuntimeStatisticsParser#assertSequence. Since HalfOuterJoinNode#LOJ_reorderable has largely been rewritten, it would probably be best to review the changes by looking at the old and the new versions in full. The predicate checking has been factored out in the method isNullRejecting. [Appendix] New reorderings from lojreorder.sql. All compute correctly as before. After conversion to JUnit, I have added assertions on the query plans to show that these reordering now actually take place. select * from t left outer join (s left outer join r on (f = i)) on (b = e and a > b) select * from t left outer join (s left outer join r on (f = i)) on (b = e and a = b); select * from t left outer join (s left outer join r on (f = i)) on (b = e and 1 = 1) select * from t left outer join (s left outer join r on (f = i)) on (b > e) Makes case 1.13 work: the test says its reordered, but actually it is not (the "and 1=1" threw old impl off). Case 1.15 now reorders ("on b1>c1" is ok) - Note to self: update comment. Makes case 1.31 work, now reorders twice, earlier none ("on a1=b1 and b2=2" threw old impl off).
          Hide
          Dag H. Wanvik added a comment -

          The old style test lang/lojreorder.sql broke, so it seems my tightening up has removed some reorderings
          which were previously asserted to happen. Investigating.

          Show
          Dag H. Wanvik added a comment - The old style test lang/lojreorder.sql broke, so it seems my tightening up has removed some reorderings which were previously asserted to happen. Investigating.
          Hide
          Dag H. Wanvik added a comment - - edited

          Attaching a first patch for this issue. It tighens up the criterion
          used for determining whether outer join reordering is allowed. I have
          tocuhed most of HalfOuterJoinNode#LOJ_reorderable, so to review it may
          be best to have a full copy of before/after since the diff is a bit
          hard to read.

          The new criterion looks inside the null-producing child of the OJ
          (the LOJ's right side) and inspects its join predicate. Previously,
          something like 1=1 would pass muster, but as we have seen this gives
          wrong results.

          As before, we require that the top join predicate is of the form
          L.X=R.y and additionally that R.y not reference the child OJ's
          null-preserving side.

          Additionally, we now require that the child OJ's join predicate also
          have the form L.x = R.y, discarding for example 1=1. See the code
          comments for details,

          I also made a new Javadoc to clarify what the method does.

          I have factored out the check for join predicate of the form
          L.x = R.y to a new private method, isLeftRightEquiJoin.

          New tests have been added to OuterJoinTest that test for query
          correctness and that the expected reorderings occur when they should.

          Note also the current limitations I found in the code:

          • Only left outer joins are considered
          • Top left side must be a base table

          I have not removed these. I have filed DERBY-4742 for also
          considering right outer joins.

          Running regressions.

          Show
          Dag H. Wanvik added a comment - - edited Attaching a first patch for this issue. It tighens up the criterion used for determining whether outer join reordering is allowed. I have tocuhed most of HalfOuterJoinNode#LOJ_reorderable, so to review it may be best to have a full copy of before/after since the diff is a bit hard to read. The new criterion looks inside the null-producing child of the OJ (the LOJ's right side) and inspects its join predicate. Previously, something like 1=1 would pass muster, but as we have seen this gives wrong results. As before, we require that the top join predicate is of the form L.X=R.y and additionally that R.y not reference the child OJ's null-preserving side. Additionally, we now require that the child OJ's join predicate also have the form L.x = R.y, discarding for example 1=1. See the code comments for details, I also made a new Javadoc to clarify what the method does. I have factored out the check for join predicate of the form L.x = R.y to a new private method, isLeftRightEquiJoin. New tests have been added to OuterJoinTest that test for query correctness and that the expected reorderings occur when they should. Note also the current limitations I found in the code: Only left outer joins are considered Top left side must be a base table I have not removed these. I have filed DERBY-4742 for also considering right outer joins. Running regressions.
          Hide
          Dag H. Wanvik added a comment -

          Thanks, Nirmal!

          Show
          Dag H. Wanvik added a comment - Thanks, Nirmal!
          Hide
          Nirmal Fernando added a comment -

          Hi,

          I sincerely hope that this PDF (created using
          screen shots of the query plan imported
          by PlanExporter tool (Derby-4587))
          helps you to get an idea of what's happening.
          If you like any other data in Xplain tables appear in the
          plan, please suggest.

          Thanks.

          Show
          Nirmal Fernando added a comment - Hi, I sincerely hope that this PDF (created using screen shots of the query plan imported by PlanExporter tool (Derby-4587)) helps you to get an idea of what's happening. If you like any other data in Xplain tables appear in the plan, please suggest. Thanks.
          Hide
          Dag H. Wanvik added a comment -

          A query in DERBY-4436 shows another example of wrong outer join reordering.

          https://issues.apache.org/jira/browse/DERBY-4736?focusedCommentId=12886105&page=com.atlassian.jira.plugin.system.issuetabpanels%3Acomment-tabpanel#action_12886105

          select * from (t2 left join (t3 left outer join t4 on 1=1) on t2.x = t3.x)

          loj t2.x=t3.x
          / \
          / \
          t2 loj 1=1
          / \
          / \
          t3 t4

          is rewritten to:

          select * from ((t2 left join t3 on t2.x = t3.x) left join t4 on 1=1);

          loj 1=1
          / \
          / t4
          /
          loj t2.x=t3.x
          / \
          / \
          t2 t3

          which also gives a wrong result, cf. analysis in DERBY-4736.

          Show
          Dag H. Wanvik added a comment - A query in DERBY-4436 shows another example of wrong outer join reordering. https://issues.apache.org/jira/browse/DERBY-4736?focusedCommentId=12886105&page=com.atlassian.jira.plugin.system.issuetabpanels%3Acomment-tabpanel#action_12886105 select * from (t2 left join (t3 left outer join t4 on 1=1) on t2.x = t3.x) loj t2.x=t3.x / \ / \ t2 loj 1=1 / \ / \ t3 t4 is rewritten to: select * from ((t2 left join t3 on t2.x = t3.x) left join t4 on 1=1); loj 1=1 / \ / t4 / loj t2.x=t3.x / \ / \ t2 t3 which also gives a wrong result, cf. analysis in DERBY-4736 .
          Hide
          Dag H. Wanvik added a comment -

          Seen all the way back to 10.0; not a regression.

          Show
          Dag H. Wanvik added a comment - Seen all the way back to 10.0; not a regression.
          Hide
          Dag H. Wanvik added a comment -

          Thanks, Knut!
          Uploading a patch to JoinTest.java which shows the problem in JUnit form.

          Show
          Dag H. Wanvik added a comment - Thanks, Knut! Uploading a patch to JoinTest.java which shows the problem in JUnit form.
          Hide
          Knut Anders Hatlen added a comment -

          I haven't studied the details, but at least PostgreSQL agrees with Dag that (a,NULL,NULL,NULL) is the correct result.

          Show
          Knut Anders Hatlen added a comment - I haven't studied the details, but at least PostgreSQL agrees with Dag that (a,NULL,NULL,NULL) is the correct result.

            People

            • Assignee:
              Dag H. Wanvik
              Reporter:
              Dag H. Wanvik
            • Votes:
              0 Vote for this issue
              Watchers:
              0 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:

                Development