Derby
  1. Derby
  2. DERBY-642

SELECT MAX doesn't use indices optimally

    Details

    • Type: Improvement Improvement
    • Status: Closed
    • Priority: Minor Minor
    • Resolution: Fixed
    • Affects Version/s: 10.2.1.6
    • Fix Version/s: 10.8.1.2
    • Component/s: Store
    • Labels:
      None
    • Urgency:
      Low
    • Bug behavior facts:
      Performance

      Description

      I tried running SELECT MAX on an indexed column in a big (8 GB)
      table. It took 12 minutes, which is about 12 minutes more than I
      expected.

      After a bit of investigation, I found out that a full index scan was
      performed because all the rows referenced from the rightmost B-tree
      node were actually deleted.

      Possible improvements:

      1. Implement backwards scan in the B-trees (this is also suggested
      in the comments in BTreeMaxScan).

      2. Go up to the parent node and down to the next leaf node on the
      left side, and continue until a valid max value is found. In
      Derby, traversing up in a B-tree is not allowed, but would it be
      ok to go up if the latches were kept on the higher-level nodes in
      the tree? Of course, this would have negative impact on
      concurrency.

      3. Right-to-left traversal on the leaf level is possible (using
      ControlRow.getLeftSibling()), but will throw an exception if the
      page cannot be latched without waiting. It is therefore possible
      to try a right-to-left search for the max value, and only fall
      back to the left-to-right approach if a conflict arises.

      1. derby-642-1a.diff
        21 kB
        Knut Anders Hatlen
      2. derby-642-1b-withTests.diff
        42 kB
        Knut Anders Hatlen
      3. derby-642-2a-test-serializable.diff
        4 kB
        Knut Anders Hatlen
      4. derby-642-3a-waitBeforeRetry.diff
        2 kB
        Knut Anders Hatlen
      5. max.sql
        2 kB
        Rick Hillegas
      6. max2.sql
        0.2 kB
        Rick Hillegas
      7. Timestamper.java
        0.4 kB
        Rick Hillegas

        Issue Links

          Activity

          Gavin made changes -
          Workflow jira [ 12343065 ] Default workflow, editable Closed status [ 12801352 ]
          Knut Anders Hatlen made changes -
          Status Resolved [ 5 ] Closed [ 6 ]
          Rick Hillegas made changes -
          Fix Version/s 10.8.1.2 [ 12316362 ]
          Fix Version/s 10.8.1.1 [ 12316356 ]
          Rick Hillegas made changes -
          Fix Version/s 10.8.1.1 [ 12316356 ]
          Fix Version/s 10.8.1.0 [ 12315561 ]
          Rick Hillegas made changes -
          Attachment Timestamper.java [ 12473043 ]
          Attachment max.sql [ 12473044 ]
          Attachment max2.sql [ 12473045 ]
          Knut Anders Hatlen made changes -
          Status In Progress [ 3 ] Resolved [ 5 ]
          Fix Version/s 10.8.0.0 [ 12315561 ]
          Resolution Fixed [ 1 ]
          Knut Anders Hatlen made changes -
          Attachment derby-642-3a-waitBeforeRetry.diff [ 12471926 ]
          Knut Anders Hatlen made changes -
          Attachment derby-642-2a-test-serializable.diff [ 12471846 ]
          Knut Anders Hatlen made changes -
          Attachment derby-642-1b-withTests.diff [ 12471088 ]
          Knut Anders Hatlen made changes -
          Attachment derby-642-1a.diff [ 12470692 ]
          Knut Anders Hatlen made changes -
          Status Open [ 1 ] In Progress [ 3 ]
          Knut Anders Hatlen made changes -
          Assignee Knut Anders Hatlen [ knutanders ]
          Dag H. Wanvik made changes -
          Derby Categories [Performance]
          Dag H. Wanvik made changes -
          Component/s Performance [ 11709 ]
          Kathey Marsden made changes -
          Fix Version/s 10.2.0.0 [ 11187 ]
          Rick Hillegas made changes -
          Urgency Low
          Knut Anders Hatlen made changes -
          Field Original Value New Value
          Link This issue is related to DERBY-884 [ DERBY-884 ]
          Knut Anders Hatlen created issue -

            People

            • Assignee:
              Knut Anders Hatlen
              Reporter:
              Knut Anders Hatlen
            • Votes:
              3 Vote for this issue
              Watchers:
              2 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:

                Development