Derby
  1. Derby
  2. DERBY-4240

An index cause SQL ORDER BY can't return correct result

    Details

    • Type: Bug Bug
    • Status: Closed
    • Priority: Major Major
    • Resolution: Duplicate
    • Affects Version/s: 10.4.2.0
    • Fix Version/s: None
    • Component/s: SQL
    • Labels:
      None
    • Urgency:
      Normal
    • Issue & fix info:
      Repro attached
    • Bug behavior facts:
      Wrong query result

      Description

      Following snippet is a SQL example program. It can reproduce a database issue.

      DROP TABLE test1;
      DROP TABLE test2;
      CREATE TABLE test1 (id BIGINT NOT NULL, name VARCHAR(255), PRIMARY KEY (id));
      CREATE TABLE test2 (entity_id BIGINT, rel_id BIGINT);
      CREATE INDEX idx_test2 ON test2 (entity_id);
      INSERT INTO test1 (id, name) VALUES (102, 'Tom');
      INSERT INTO test1 (id, name) VALUES (1, null);
      INSERT INTO test1 (id, name) VALUES (103, 'Jerry');
      INSERT INTO test1 (id, name) VALUES (101, 'Pupy');
      INSERT INTO test2 (entity_id, rel_id) VALUES (1, 102);
      INSERT INTO test2 (entity_id, rel_id) VALUES (1, 101);
      INSERT INTO test2 (entity_id, rel_id) VALUES (1, 103);
      SELECT t1.id, t1.name FROM test2 t2 INNER JOIN test1 t1 ON t2.rel_id = t1.id WHERE t2.entity_id = 1 ORDER BY t1.id ASC;

      The expected result should be
      ID NAME
      --------------------------
      101 Pupy
      102 Tom
      103 Jerry

      When running the program, I got below result.
      ID NAME
      --------------------------
      102 Tom
      101 Pupy
      103 Jerry

      The result is obviously wrong. Using ORDER BY ASC does not get expected result. I found ORDER BY DESC works fine.
      Note: there is an index (idx_test2). This index affects the SQL query. If the index is dropped, ORDER BY ASC can return correct result..

        Issue Links

          Activity

          Simon Meng created issue -
          Hide
          Mike Matrigali added a comment -

          This reproduces for me in trunk using the included script against both ibm16 and ibm15 jvms.
          Here is the query plan:
          2009-05-21 15:09:30.671 GMT Thread[main,5,main] (XID = 288), (SESSIONID = 1), SELECT t1.id, t1.name FROM test2 t2 INNER JOIN test1 t1 ON t2.rel_id = t
          1.id WHERE t2.entity_id = 1 ORDER BY t1.id ASC ******* Project-Restrict ResultSet (6):
          Number of opens = 1
          Rows seen = 3
          Rows filtered = 0
          restriction = false
          projection = true
          constructor time (milliseconds) = 0
          open time (milliseconds) = 0
          next time (milliseconds) = 0
          close time (milliseconds) = 0
          restriction time (milliseconds) = 0
          projection time (milliseconds) = 0
          optimizer estimated row count: 3.00
          optimizer estimated cost: 62.07

          Source result set:
          Nested Loop Exists Join ResultSet:
          Number of opens = 1
          Rows seen from the left = 3
          Rows seen from the right = 3
          Rows filtered = 0
          Rows returned = 3
          constructor time (milliseconds) = 0
          open time (milliseconds) = 0
          next time (milliseconds) = 0
          close time (milliseconds) = 0
          optimizer estimated row count: 3.00
          optimizer estimated cost: 62.07

          Left result set:
          Index Row to Base Row ResultSet for TEST2:
          Number of opens = 1
          Rows seen = 3
          Columns accessed from heap =

          {0, 1}

          constructor time (milliseconds) = 0
          open time (milliseconds) = 0
          next time (milliseconds) = 0
          close time (milliseconds) = 0
          optimizer estimated row count: 3.00
          optimizer estimated cost: 40.57

          Index Scan ResultSet for TEST2 using index IDX_TEST2 at read committed isolation level using share row locking chosen by the optimizer
          Number of opens = 1
          Rows seen = 3
          Rows filtered = 0
          Fetch Size = 1
          constructor time (milliseconds) = 0
          open time (milliseconds) = 0
          next time (milliseconds) = 0
          close time (milliseconds) = 0
          next time in milliseconds/row = 0

          scan information:
          Bit set of columns fetched=All
          Number of columns fetched=2
          Number of deleted rows visited=0
          Number of pages visited=1
          Number of rows qualified=3
          Number of rows visited=3
          Scan type=btree
          Tree height=-1
          start position:
          >= on first 1 column(s).
          Ordered null semantics on the following columns:

          stop position:
          > on first 1 column(s).
          Ordered null semantics on the following columns:

          qualifiers:
          None
          optimizer estimated row count: 3.00
          optimizer estimated cost: 40.57
          Right result set:
          Index Row to Base Row ResultSet for TEST1:
          Number of opens = 3
          Rows seen = 3
          Columns accessed from heap =

          {1}

          constructor time (milliseconds) = 0
          open time (milliseconds) = 0
          next time (milliseconds) = 0
          close time (milliseconds) = 0
          optimizer estimated row count: 3.00
          optimizer estimated cost: 21.50

          Index Scan ResultSet for TEST1 using constraint SQL090521080928600 at read committed isolation level using share row locking cho
          optimizer
          Number of opens = 3
          Rows seen = 3
          Rows filtered = 0
          Fetch Size = 1
          constructor time (milliseconds) = 0
          open time (milliseconds) = 0
          next time (milliseconds) = 0
          close time (milliseconds) = 0
          next time in milliseconds/row = 0

          scan information:
          Bit set of columns fetched=All
          Number of columns fetched=2
          Number of deleted rows visited=0
          Number of pages visited=3
          Number of rows qualified=3
          Number of rows visited=3
          Scan type=btree
          Tree height=1
          start position:
          >= on first 1 column(s).
          Ordered null semantics on the following columns:

          stop position:
          > on first 1 column(s).
          Ordered null semantics on the following columns:

          qualifiers:
          None
          optimizer estimated row count: 3.00
          optimizer estimated cost: 21.50

          Show
          Mike Matrigali added a comment - This reproduces for me in trunk using the included script against both ibm16 and ibm15 jvms. Here is the query plan: 2009-05-21 15:09:30.671 GMT Thread [main,5,main] (XID = 288), (SESSIONID = 1), SELECT t1.id, t1.name FROM test2 t2 INNER JOIN test1 t1 ON t2.rel_id = t 1.id WHERE t2.entity_id = 1 ORDER BY t1.id ASC ******* Project-Restrict ResultSet (6): Number of opens = 1 Rows seen = 3 Rows filtered = 0 restriction = false projection = true constructor time (milliseconds) = 0 open time (milliseconds) = 0 next time (milliseconds) = 0 close time (milliseconds) = 0 restriction time (milliseconds) = 0 projection time (milliseconds) = 0 optimizer estimated row count: 3.00 optimizer estimated cost: 62.07 Source result set: Nested Loop Exists Join ResultSet: Number of opens = 1 Rows seen from the left = 3 Rows seen from the right = 3 Rows filtered = 0 Rows returned = 3 constructor time (milliseconds) = 0 open time (milliseconds) = 0 next time (milliseconds) = 0 close time (milliseconds) = 0 optimizer estimated row count: 3.00 optimizer estimated cost: 62.07 Left result set: Index Row to Base Row ResultSet for TEST2: Number of opens = 1 Rows seen = 3 Columns accessed from heap = {0, 1} constructor time (milliseconds) = 0 open time (milliseconds) = 0 next time (milliseconds) = 0 close time (milliseconds) = 0 optimizer estimated row count: 3.00 optimizer estimated cost: 40.57 Index Scan ResultSet for TEST2 using index IDX_TEST2 at read committed isolation level using share row locking chosen by the optimizer Number of opens = 1 Rows seen = 3 Rows filtered = 0 Fetch Size = 1 constructor time (milliseconds) = 0 open time (milliseconds) = 0 next time (milliseconds) = 0 close time (milliseconds) = 0 next time in milliseconds/row = 0 scan information: Bit set of columns fetched=All Number of columns fetched=2 Number of deleted rows visited=0 Number of pages visited=1 Number of rows qualified=3 Number of rows visited=3 Scan type=btree Tree height=-1 start position: >= on first 1 column(s). Ordered null semantics on the following columns: stop position: > on first 1 column(s). Ordered null semantics on the following columns: qualifiers: None optimizer estimated row count: 3.00 optimizer estimated cost: 40.57 Right result set: Index Row to Base Row ResultSet for TEST1: Number of opens = 3 Rows seen = 3 Columns accessed from heap = {1} constructor time (milliseconds) = 0 open time (milliseconds) = 0 next time (milliseconds) = 0 close time (milliseconds) = 0 optimizer estimated row count: 3.00 optimizer estimated cost: 21.50 Index Scan ResultSet for TEST1 using constraint SQL090521080928600 at read committed isolation level using share row locking cho optimizer Number of opens = 3 Rows seen = 3 Rows filtered = 0 Fetch Size = 1 constructor time (milliseconds) = 0 open time (milliseconds) = 0 next time (milliseconds) = 0 close time (milliseconds) = 0 next time in milliseconds/row = 0 scan information: Bit set of columns fetched=All Number of columns fetched=2 Number of deleted rows visited=0 Number of pages visited=3 Number of rows qualified=3 Number of rows visited=3 Scan type=btree Tree height=1 start position: >= on first 1 column(s). Ordered null semantics on the following columns: stop position: > on first 1 column(s). Ordered null semantics on the following columns: qualifiers: None optimizer estimated row count: 3.00 optimizer estimated cost: 21.50
          Hide
          Mike Matrigali added a comment -

          Until the bug is fixed one workaround would be to add another term to the order by. The following query produces the correct sort order:
          SELECT t1.id, t1.name FROM test2 t2 INNER JOIN test1 t1 ON t2.rel_id = t1.id WHERE t2.entity_id = 1 ORDER BY t1.id, t1.name ASC;

          Show
          Mike Matrigali added a comment - Until the bug is fixed one workaround would be to add another term to the order by. The following query produces the correct sort order: SELECT t1.id, t1.name FROM test2 t2 INNER JOIN test1 t1 ON t2.rel_id = t1.id WHERE t2.entity_id = 1 ORDER BY t1.id, t1.name ASC;
          Mike Matrigali made changes -
          Field Original Value New Value
          Link This issue is related to DERBY-3926 [ DERBY-3926 ]
          Hide
          Mike Matrigali added a comment -

          I think this may be the same issue as DERBY-3926, but only marking relates to until someone can run the proposed patch on that issue against this test case. The inner join forces the join order, thus the outermost access path is:
          Index Scan ResultSet for TEST2 using index IDX_TEST2 at read com
          mitted isolation level using instantaneous share row locking chosen by the optim
          izer

          This uses the IDX_TEST2 index to find the 3 rows matching (t2.entity_id = 1), which
          as a constant expression the optimizer marks as always sorted.

          This then does 3 probes using the following access path:
          Index Scan ResultSet for TEST1 using constraint SQL0905210821211
          20 at read committed isolation level using share row locking chosen by the optim
          izer - which is an index sorted on t1.id

          The optimizer incorrectly assumes since the first access path is a constant expression that the query result will be properly sorted on the 2nd part of join
          and thus incorrectly does not do a sort.

          Show
          Mike Matrigali added a comment - I think this may be the same issue as DERBY-3926 , but only marking relates to until someone can run the proposed patch on that issue against this test case. The inner join forces the join order, thus the outermost access path is: Index Scan ResultSet for TEST2 using index IDX_TEST2 at read com mitted isolation level using instantaneous share row locking chosen by the optim izer This uses the IDX_TEST2 index to find the 3 rows matching (t2.entity_id = 1), which as a constant expression the optimizer marks as always sorted. This then does 3 probes using the following access path: Index Scan ResultSet for TEST1 using constraint SQL0905210821211 20 at read committed isolation level using share row locking chosen by the optim izer - which is an index sorted on t1.id The optimizer incorrectly assumes since the first access path is a constant expression that the query result will be properly sorted on the 2nd part of join and thus incorrectly does not do a sort.
          Hide
          Mamta A. Satoor added a comment -

          I tried the test case with and without my patch for DERBY-3926. The test passes when run with the patch.

          I see that this jira entry is already connected to DERBY-3926.

          Show
          Mamta A. Satoor added a comment - I tried the test case with and without my patch for DERBY-3926 . The test passes when run with the patch. I see that this jira entry is already connected to DERBY-3926 .
          Mamta A. Satoor made changes -
          Assignee Mamta A. Satoor [ mamtas ]
          Hide
          Dag H. Wanvik added a comment -

          Triaged for 10.5.2, checking "repro attached" and setting "normal" urgency.

          So, can this be closed as a duplicate of DERBY-3926?

          Show
          Dag H. Wanvik added a comment - Triaged for 10.5.2, checking "repro attached" and setting "normal" urgency. So, can this be closed as a duplicate of DERBY-3926 ?
          Dag H. Wanvik made changes -
          Urgency Normal
          Issue & fix info [Repro attached]
          Hide
          Mamta A. Satoor added a comment -

          duplicate of DERBY-3926.

          Show
          Mamta A. Satoor added a comment - duplicate of DERBY-3926 .
          Mamta A. Satoor made changes -
          Status Open [ 1 ] Resolved [ 5 ]
          Resolution Duplicate [ 3 ]
          Mamta A. Satoor made changes -
          Status Resolved [ 5 ] Closed [ 6 ]
          Gavin made changes -
          Workflow jira [ 12463983 ] Default workflow, editable Closed status [ 12800218 ]
          Transition Time In Source Status Execution Times Last Executer Last Execution Date
          Open Open Resolved Resolved
          49d 9h 31m 1 Mamta A. Satoor 09/Jul/09 14:03
          Resolved Resolved Closed Closed
          1m 30s 1 Mamta A. Satoor 09/Jul/09 14:05

            People

            • Assignee:
              Mamta A. Satoor
              Reporter:
              Simon Meng
            • Votes:
              0 Vote for this issue
              Watchers:
              0 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:

                Development