Uploaded image for project: 'Derby'
  1. Derby
  2. DERBY-642

SELECT MAX doesn't use indices optimally


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


      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

      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

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

          Issue Links



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


                • Created: