db-derby-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Knut Anders Hatlen (JIRA)" <derby-...@db.apache.org>
Subject [jira] Created: (DERBY-642) SELECT MAX doesn't use indices optimally
Date Mon, 24 Oct 2005 14:54:55 GMT
SELECT MAX doesn't use indices optimally
----------------------------------------

         Key: DERBY-642
         URL: http://issues.apache.org/jira/browse/DERBY-642
     Project: Derby
        Type: Improvement
  Components: Store, Performance  
    Versions: 10.2.0.0    
    Reporter: Knut Anders Hatlen
    Priority: Minor
     Fix For: 10.2.0.0


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.

-- 
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
   http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see:
   http://www.atlassian.com/software/jira


Mime
View raw message