[jira] Commented: (DERBY-642) SELECT MAX doesn't use indices optimally

["Mike Matrigali (JIRA)" <de...@db.apache.org>]

    [ http://issues.apache.org/jira/browse/DERBY-642?page=comments#action_12355642 ] 

Mike Matrigali commented on DERBY-642:
--------------------------------------

The current  implementation was done as  a way to get 90% for a very small amount of work - it was not a technical decision, simply a scheduling one.

Option 1 would be the best technical decision, but is the hardest. -- but the
store work is not extremely hard just some care needs to be taken to handle
the messy case of when latching going backward needs to wait.  Basically
when going right to left you must request the latch NOWAIT, and if you can't
get the latch you need to code a way to save your current position in the
tree, release all current latches, and wait for the desired latch.  Once you
have the latch then you have to refind your current position as it may have
moved (but I believe it can only have moved right of the page you are on in the
current btree implementation - implementer would need to verify that).

If a real backward scan were implemented, then the next obvious step would
be to teach the optimizer about it so that it could use it in plans.  Doing it 
first for max would be a reasonable 1st step in a phased implementation
approach.  The second step would be to change the store interfaces to allow for a backward scan, and then finally change the language layer to actually
use the backward scans.

Option 3 would be an interesting extension to the "do what is easy" approach, 
it would be significantly easier than option 1.  

Not sure about option 2, it sounds deadlock prone - but  could work if you 
paid the cost of more latches and less concurrency.  

> 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