[DERBY-642] SELECT MAX doesn't use indices optimally

• Type: Improvement
• Status: Closed
• Priority: Minor
• Resolution: Fixed
• Affects Version/s: 10.2.1.6
• Fix Version/s: 10.8.1.2
• Component/s: Store
• Urgency: Low
• Bug behavior facts: Performance
• Assignee: Knut Anders Hatlen
• Reporter: Knut Anders Hatlen
• Created: 24/Oct/05 23:54
• Updated: 30/Jun/11 09:21
• Resolved: 07/Mar/11 13:27

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.

Issue Links

• is related to: DERBY-884 allow and use backward scans on indexes.