Derby
  1. Derby
  2. DERBY-4372

Wrong result for simple join when index is created

    Details

    • Type: Bug Bug
    • Status: Closed
    • Priority: Critical Critical
    • Resolution: Fixed
    • Affects Version/s: 10.1.3.3, 10.2.2.1, 10.5.1.1
    • Fix Version/s: 10.5.3.1, 10.6.1.0
    • Component/s: SQL
    • Labels:
      None
    • Urgency:
      Urgent
    • Issue & fix info:
      Repro attached
    • Bug behavior facts:
      Wrong query result

      Description

      In the example below, the first SELECT has correct result. After the index is created, the second SELECT gives wrong result.

      ij> CREATE TABLE t1 (i1 INT, j1 INT);
      0 rows inserted/updated/deleted
      ij> CREATE TABLE t2 (i2 INT, j2 INT);
      0 rows inserted/updated/deleted
      ij> INSERT INTO t1 VALUES (8, 8),(NULL, 8);
      2 rows inserted/updated/deleted
      ij> INSERT INTO t2 VALUES (8, 8);
      1 row inserted/updated/deleted
      ij> SELECT * FROM t1 INNER JOIN t2 ON (t2.j2 = t1.i1) OR (t2.j2 = t1.j1);
      I1 |J1 |I2 |J2
      -----------------------------------------------
      8 |8 |8 |8
      NULL |8 |8 |8

      2 rows selected
      ij> CREATE INDEX ix2 ON t2(j2);
      0 rows inserted/updated/deleted
      ij> SELECT * FROM t1 INNER JOIN t2 ON (t2.j2 = t1.i1) OR (t2.j2 = t1.j1);
      I1 |J1 |I2 |J2
      -----------------------------------------------
      8 |8 |8 |8

      1 row selected

      1. experiment.diff
        2 kB
        Knut Anders Hatlen
      2. derby-4372-1a.stat
        0.2 kB
        Knut Anders Hatlen
      3. derby-4372-1a.diff
        5 kB
        Knut Anders Hatlen

        Activity

        Hide
        Knut Anders Hatlen added a comment -

        Other variants of the query also show this problem:

        ij> select * from t1,t2 where t2.j2 in (t1.i1, t1.j1);
        I1 |J1 |I2 |J2
        -----------------------------------------------
        8 |8 |8 |8

        1 row selected
        ij> drop index ix2;
        0 rows inserted/updated/deleted
        ij> select * from t1,t2 where t2.j2 in (t1.i1, t1.j1);
        I1 |J1 |I2 |J2
        -----------------------------------------------
        8 |8 |8 |8
        NULL |8 |8 |8

        2 rows selected

        Oddly enough, if the last condition (t2.j2=t1.j1) is changed into the equivalent form (t1.j1=t2.j2) the query returns correct results regardless of the index (the query plan says that the index is not used in this case).

        Show
        Knut Anders Hatlen added a comment - Other variants of the query also show this problem: ij> select * from t1,t2 where t2.j2 in (t1.i1, t1.j1); I1 |J1 |I2 |J2 ----------------------------------------------- 8 |8 |8 |8 1 row selected ij> drop index ix2; 0 rows inserted/updated/deleted ij> select * from t1,t2 where t2.j2 in (t1.i1, t1.j1); I1 |J1 |I2 |J2 ----------------------------------------------- 8 |8 |8 |8 NULL |8 |8 |8 2 rows selected Oddly enough, if the last condition (t2.j2=t1.j1) is changed into the equivalent form (t1.j1=t2.j2) the query returns correct results regardless of the index (the query plan says that the index is not used in this case).
        Hide
        Knut Anders Hatlen added a comment -

        It seems like the problem can be reproduced even without the join. However, because of DERBY-4376, it is only reproducible this way on 10.2.2.0 and earlier. On 10.3.1.4 and later, this will go into an infinite loop.

        ij> create table t(x int);
        0 rows inserted/updated/deleted
        ij> insert into t values (8);
        1 row inserted/updated/deleted
        ij> prepare ps as 'select * from t where x = ? or x = ?';
        ij> execute ps using 'values (cast(null as int), 8)';
        IJ WARNING: Autocommit may close using result set
        X
        -----------
        8

        1 row selected
        ij> create index idx on t;
        0 rows inserted/updated/deleted
        ij> execute ps using 'values (cast(null as int), 8)';
        IJ WARNING: Autocommit may close using result set
        X
        -----------

        0 rows selected

        Show
        Knut Anders Hatlen added a comment - It seems like the problem can be reproduced even without the join. However, because of DERBY-4376 , it is only reproducible this way on 10.2.2.0 and earlier. On 10.3.1.4 and later, this will go into an infinite loop. ij> create table t(x int); 0 rows inserted/updated/deleted ij> insert into t values (8); 1 row inserted/updated/deleted ij> prepare ps as 'select * from t where x = ? or x = ?'; ij> execute ps using 'values (cast(null as int), 8)'; IJ WARNING: Autocommit may close using result set X ----------- 8 1 row selected ij> create index idx on t ; 0 rows inserted/updated/deleted ij> execute ps using 'values (cast(null as int), 8)'; IJ WARNING: Autocommit may close using result set X ----------- 0 rows selected
        Hide
        Knut Anders Hatlen added a comment -

        I think this is what's causing the bug:

        • Internally, (t2.j2 = t1.i1) OR (t2.j2 = t1.j1) is rewritten to t2.j2 IN (t1.i1, t1.j1).
        • With an index on J2, we'll choose an index scan of T2, with min(t1.i1, t1.j1) as start key and max(t1.i1, t1.j1) as stop key.
        • The code to create start/stop keys is generated in InListOperatorNode.generateStartStopKey(), and it uses BaseExpressionActivation.minValue()/maxValue() to find min/max.
        • The methods minValue() and maxValue() are not prepared for SQL NULL. If SQL NULL is passed as the first argument, they will both return SQL NULL. If the first argument is not SQL NULL, the min or max of the non-NULL values will be returned.

        For the join that returns wrong results, the following happens:

        When the second row in T1 is read, the join attempts to find a match in T2 where j2 IN (NULL,8). It calls minValue() and maxValue() with NULL as first arg and 8 as second arg. Both of them return NULL, so the index scan looks for all rows in T2 where j2 >= NULL and j2 <= NULL. Comparison with NULL never returns TRUE, so no row is found.

        Both minValue() and maxValue() should have returned 8, in which case the index scan would have found a match.

        Show
        Knut Anders Hatlen added a comment - I think this is what's causing the bug: Internally, (t2.j2 = t1.i1) OR (t2.j2 = t1.j1) is rewritten to t2.j2 IN (t1.i1, t1.j1). With an index on J2, we'll choose an index scan of T2, with min(t1.i1, t1.j1) as start key and max(t1.i1, t1.j1) as stop key. The code to create start/stop keys is generated in InListOperatorNode.generateStartStopKey(), and it uses BaseExpressionActivation.minValue()/maxValue() to find min/max. The methods minValue() and maxValue() are not prepared for SQL NULL. If SQL NULL is passed as the first argument, they will both return SQL NULL. If the first argument is not SQL NULL, the min or max of the non-NULL values will be returned. For the join that returns wrong results, the following happens: When the second row in T1 is read, the join attempts to find a match in T2 where j2 IN (NULL,8). It calls minValue() and maxValue() with NULL as first arg and 8 as second arg. Both of them return NULL, so the index scan looks for all rows in T2 where j2 >= NULL and j2 <= NULL. Comparison with NULL never returns TRUE, so no row is found. Both minValue() and maxValue() should have returned 8, in which case the index scan would have found a match.
        Hide
        Knut Anders Hatlen added a comment -

        The attached patch adds a fix for the bug and a test case that exposes it.

        The javadoc for minValue() and maxValue() in BaseExpressionActivation is clarified with respect to how NULLs are handled. Also, the methods are changed so that they handle NULLs the same way regardless of their position in the IN list. Now, SQL NULL is only returned if and only if all the inputs are SQL NULL. Previously, SQL NULL was returned if and only if the first input was SQL NULL. This change made the start and stop keys come out right if the first input was SQL NULL and there was other non-NULL inputs.

        I have started the full regression test suite.

        Show
        Knut Anders Hatlen added a comment - The attached patch adds a fix for the bug and a test case that exposes it. The javadoc for minValue() and maxValue() in BaseExpressionActivation is clarified with respect to how NULLs are handled. Also, the methods are changed so that they handle NULLs the same way regardless of their position in the IN list. Now, SQL NULL is only returned if and only if all the inputs are SQL NULL. Previously, SQL NULL was returned if and only if the first input was SQL NULL. This change made the start and stop keys come out right if the first input was SQL NULL and there was other non-NULL inputs. I have started the full regression test suite.
        Hide
        Bryan Pendleton added a comment -

        Are BaseExpressionActivation's minValue and maxValue methods used widely?

        I'm irrationally nervous about changing the handling of NULL because the complex
        semantics of NULL have been implemented with exquisite care over the years.

        I suppose an alternative would be to make a change to InListOperatorNode.generateStartStopKey()
        so that it uses some new set of functions, rather than
        BaseExpressionActivation.minValue()/maxValue() to find min/max.

        We could call the new methods "minNonNullValue()" and "maxNonNullValue()", or
        something like that, to help clarify that they had different semantics.

        Show
        Bryan Pendleton added a comment - Are BaseExpressionActivation's minValue and maxValue methods used widely? I'm irrationally nervous about changing the handling of NULL because the complex semantics of NULL have been implemented with exquisite care over the years. I suppose an alternative would be to make a change to InListOperatorNode.generateStartStopKey() so that it uses some new set of functions, rather than BaseExpressionActivation.minValue()/maxValue() to find min/max. We could call the new methods "minNonNullValue()" and "maxNonNullValue()", or something like that, to help clarify that they had different semantics.
        Hide
        Knut Anders Hatlen added a comment -

        As far as I can tell, those two methods are only used by InListOperatorNode.generateStartStopKey(). There are no direct calls to any of them in the code, and the only occurrences of the strings "maxValue" and "minValue" (with the double-quotes) are the ones in generateStartStopKey().

        I can perform this experiment: Change the names of maxValue/minValue to something completely different, and replace them with dummy methods (called maxValue/minValue) that always throw an exception. Then I'll make InListOperatorNode.generateStartStopKey() use the renamed methods and run suites.All/derbyall to (hopefully) verify that they are never called elsewhere. Would that make you feel more comfortable?

        Show
        Knut Anders Hatlen added a comment - As far as I can tell, those two methods are only used by InListOperatorNode.generateStartStopKey(). There are no direct calls to any of them in the code, and the only occurrences of the strings "maxValue" and "minValue" (with the double-quotes) are the ones in generateStartStopKey(). I can perform this experiment: Change the names of maxValue/minValue to something completely different, and replace them with dummy methods (called maxValue/minValue) that always throw an exception. Then I'll make InListOperatorNode.generateStartStopKey() use the renamed methods and run suites.All/derbyall to (hopefully) verify that they are never called elsewhere. Would that make you feel more comfortable?
        Hide
        Knut Anders Hatlen added a comment -

        Um, well... Running the tests may not help that much. According to the test coverage report, the BaseExpressionActivation class isn't used at all by the JUnit tests: http://dbtg.foundry.sun.com/derby/test/coverage/jvm1.6/sol/suitesAll82289/_files/3b1.html. I guess the MultiProbeTableScanResultSet added in DERBY-47 makes it less likely that this code path is used.

        The lack of test coverage probably means the answer to your question ("Are [the] methods used widely?") is no...

        I'll run the experiment anyway, since there may be tests in derbyall that exercise the code path.

        Show
        Knut Anders Hatlen added a comment - Um, well... Running the tests may not help that much. According to the test coverage report, the BaseExpressionActivation class isn't used at all by the JUnit tests: http://dbtg.foundry.sun.com/derby/test/coverage/jvm1.6/sol/suitesAll82289/_files/3b1.html . I guess the MultiProbeTableScanResultSet added in DERBY-47 makes it less likely that this code path is used. The lack of test coverage probably means the answer to your question ("Are [the] methods used widely?") is no... I'll run the experiment anyway, since there may be tests in derbyall that exercise the code path.
        Hide
        Bryan Pendleton added a comment -

        Well, your static analysis seems pretty persuasive to me.

        And, like I said, it is an irrational fear.

        But that code in inListOperatorNode.generateStartStopKey has been
        present since since the original Derby contribution to Apache, if I'm
        reading the svn history correctly
        http://svn.apache.org/viewvc/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/InListOperatorNode.java?revision=37083&view=markup
        so that's very old code indeed.

        Of course, if I'm understanding your earlier comments here and in DERBY-4376
        correctly, this behavior has been around since the original Derby contribution to Apache, too.

        After re-reading your comments and reading the attached patch file, I can't see any reason
        not to proceed with your change.

        Thanks for letting me raise my concern, and thanks for taking the time to study this issue in detail!

        Show
        Bryan Pendleton added a comment - Well, your static analysis seems pretty persuasive to me. And, like I said, it is an irrational fear. But that code in inListOperatorNode.generateStartStopKey has been present since since the original Derby contribution to Apache, if I'm reading the svn history correctly http://svn.apache.org/viewvc/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/InListOperatorNode.java?revision=37083&view=markup so that's very old code indeed. Of course, if I'm understanding your earlier comments here and in DERBY-4376 correctly, this behavior has been around since the original Derby contribution to Apache, too. After re-reading your comments and reading the attached patch file, I can't see any reason not to proceed with your change. Thanks for letting me raise my concern, and thanks for taking the time to study this issue in detail!
        Hide
        Knut Anders Hatlen added a comment -

        Uploading experiment.diff which makes minValue() and maxValue() throw a RuntimeException and adds methods called minValueXYZ() and maxValueXYZ() that InListOperatorNode.generateStartStopKey() can use instead. Running suites.All and derbyall now to verify that minValue() and maxValue() aren't being called by other methods.

        Show
        Knut Anders Hatlen added a comment - Uploading experiment.diff which makes minValue() and maxValue() throw a RuntimeException and adds methods called minValueXYZ() and maxValueXYZ() that InListOperatorNode.generateStartStopKey() can use instead. Running suites.All and derbyall now to verify that minValue() and maxValue() aren't being called by other methods.
        Hide
        Knut Anders Hatlen added a comment -

        Thanks, Bryan!

        All the regression tests ran cleanly (both with the fix and with the experiment to smoke out any other callers of maxValue() and minValue()).

        Committed revision 816531.

        I plan to port the fix to 10.5, so I'll leave the issue open for now.

        Show
        Knut Anders Hatlen added a comment - Thanks, Bryan! All the regression tests ran cleanly (both with the fix and with the experiment to smoke out any other callers of maxValue() and minValue()). Committed revision 816531. I plan to port the fix to 10.5, so I'll leave the issue open for now.
        Hide
        Knut Anders Hatlen added a comment -

        Merged the fix to 10.5 and committed revision 818931.

        Show
        Knut Anders Hatlen added a comment - Merged the fix to 10.5 and committed revision 818931.
        Hide
        Mamta A. Satoor added a comment -

        Knut, does the fix need to be backported to earlier revisions too? Copying one of your earlier comment for reference. thanks
        *************
        It seems like the problem can be reproduced even without the join. However, because of DERBY-4376, it is only reproducible this way on 10.2.2.0 and earlier. On 10.3.1.4 and later, this will go into an infinite loop.
        *************

        Show
        Mamta A. Satoor added a comment - Knut, does the fix need to be backported to earlier revisions too? Copying one of your earlier comment for reference. thanks ************* It seems like the problem can be reproduced even without the join. However, because of DERBY-4376 , it is only reproducible this way on 10.2.2.0 and earlier. On 10.3.1.4 and later, this will go into an infinite loop. *************
        Hide
        Knut Anders Hatlen added a comment -

        This bug also affects older versions, so it certainly can be back-ported if someone wants the fix on those branches.

        Show
        Knut Anders Hatlen added a comment - This bug also affects older versions, so it certainly can be back-ported if someone wants the fix on those branches.
        Hide
        Mamta A. Satoor added a comment -

        I have backported DERBY-4376 into 10.4 codeline and when I run the test script for this jira entry on that 10.4 codeline, I see that it returns the correct results even after the index is created. the script I tried is as follows
        java -Dij.exceptionTrace=true org.apache.derby.tools.ij
        connect 'jdbc:derby:c:/dellater/db;create=true';
        create table t(x int);
        insert into t values (8);
        prepare ps as 'select * from t where x = ? or x = ?';
        execute ps using 'values (cast(null as int), 8)';
        create index idx on t;
        execute ps using 'values (cast(null as int), 8)';

        I didn't not running the above script before backporting DERBY-4376.

        I will try the script on 10.3 and earlier codelines and backport the fix as needed.

        Show
        Mamta A. Satoor added a comment - I have backported DERBY-4376 into 10.4 codeline and when I run the test script for this jira entry on that 10.4 codeline, I see that it returns the correct results even after the index is created. the script I tried is as follows java -Dij.exceptionTrace=true org.apache.derby.tools.ij connect 'jdbc:derby:c:/dellater/db;create=true'; create table t(x int); insert into t values (8); prepare ps as 'select * from t where x = ? or x = ?'; execute ps using 'values (cast(null as int), 8)'; create index idx on t ; execute ps using 'values (cast(null as int), 8)'; I didn't not running the above script before backporting DERBY-4376 . I will try the script on 10.3 and earlier codelines and backport the fix as needed.
        Hide
        Mamta A. Satoor added a comment -

        Doesn't repro on 10.3 either. I will check the other codelines and will update the jira with what I find for 10.2 and 10.1 releases.

        Show
        Mamta A. Satoor added a comment - Doesn't repro on 10.3 either. I will check the other codelines and will update the jira with what I find for 10.2 and 10.1 releases.
        Hide
        Mamta A. Satoor added a comment -

        The problem reproduces on 10.2 and 10.1 codeline. I am not planning on backporting into those codelines at this point.

        Show
        Mamta A. Satoor added a comment - The problem reproduces on 10.2 and 10.1 codeline. I am not planning on backporting into those codelines at this point.

          People

          • Assignee:
            Knut Anders Hatlen
            Reporter:
            Bernt M. Johnsen
          • Votes:
            0 Vote for this issue
            Watchers:
            0 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development