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
