db-derby-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Knut Anders Hatlen (JIRA)" <j...@apache.org>
Subject [jira] Updated: (DERBY-642) SELECT MAX doesn't use indices optimally
Date Tue, 15 Feb 2011 16:54:57 GMT

     [ https://issues.apache.org/jira/browse/DERBY-642?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel

Knut Anders Hatlen updated DERBY-642:

    Attachment: derby-642-1b-withTests.diff

Attaching an updated patch (1b) with the following changes from 1a:

- Changed class javadoc for BTreeMaxScan to describe the new approach
  instead of the old one.

- Added a debug flag to allow tracing latch conflicts in sane builds.

- Added a new test (BTreeMaxScanTest) with test cases that exercise
  the code that handles some of the latch conflict scenarios.

If the test is run with derby.tests.trace=true, and a sane build is
used, a message will be printed to derby.log each time a latch
conflict that results in the need for repositioning is experienced by
a BTreeMaxScan. This can be used to verify that the test actually
exercised the code path we're interested in. For example, the test
that verifies that backward scans don't deadlock with backward scans,
will print something like this to derby.log:

DEBUG BTreeMaxScan.latchConflict OUTPUT: Enable tracing for testOppositeScanDirections
DEBUG BTreeMaxScan.latchConflict OUTPUT: Couldn't get latch nowait, will retry
DEBUG BTreeMaxScan.latchConflict OUTPUT: Couldn't get latch nowait, will retry
DEBUG BTreeMaxScan.latchConflict OUTPUT: Disable tracing for testOppositeScanDirections

And the test that verifies that the scan is restarted after a latch
conflict when moving from an empty page, will print something like

DEBUG BTreeMaxScan.latchConflict OUTPUT: Enable tracing for testEmptyRightmostLeaf
DEBUG BTreeMaxScan.latchConflict OUTPUT: Couldn't get latch nowait, will retry
DEBUG BTreeMaxScan.latchConflict OUTPUT: Restart scan from rightmost leaf
DEBUG BTreeMaxScan.latchConflict OUTPUT: Couldn't get latch nowait, will retry
DEBUG BTreeMaxScan.latchConflict OUTPUT: Restart scan from rightmost leaf
DEBUG BTreeMaxScan.latchConflict OUTPUT: Disable tracing for testEmptyRightmostLeaf

Since latch conflicts are hard to test reliably, the test runs many
iterations to increase the likelihood of a conflict, but there's no
guarantee that it actually has been tested. That's why the tracing is
added. Currently, the test takes almost a minute to run. This could be
reduced by cutting down on the number of iterations, and we should
probably do that when the feature has been stabilized, but I'll keep
the high number of iterations for now.

Although there still are some issues that need to be resolved, and
more tests need to be written, I intend to commit this patch soon so
that we can get as much testing as possible before the next release.
If we haven't gained enough confidence in it by then, we can always
back out the changes.

As to the issues I think need to be resolved, or at least investigated
further, I'm particularly thinking about what's the right way to do
the repositioning after waiting for a lock. The old code would give up
and start from the beginning of the B-tree in that case, whereas the
new code will reposition on the row we had to wait for and continue

I think that may be too simple, at least for serializable
transactions. Since we're moving backwards, the previous key locking
works a bit different. While we're waiting for the lock on the current
row, the range between the row we're waiting for and the (deleted)
record that we just saw is not protected. So when we get the lock, a
row with a higher value may have been inserted. We won't see this row
after the repositioning, and it will turn up as a phantom read
(thereby breaking the requirements for the serializable isolation
level) if we re-execute select max in the same transaction.

Now this doesn't seem to cause any problem in practise, because in all
the tests I've run, B-tree max scans in serializable transactions take
table locks, preventing any concurrent modification. However, it would
be good to get this right, especially so that the backward max scan
can be extended to a full-featured backward scan implementation in
DERBY-884, and also so that max scans at some point can safely be
performed without table locks in serializable transactions.

One possible solution may be to change BTreeScan.savePosition() to
save the position immediately to the right of the current position
when we scan backwards. That should prevent skipping rows that were
inserted while we waited for the lock on the current position, since
the range from the last visited row and up to infinity should be
protected by the locks already acquired. Moving one step to the left
from that saved position should get us back to the same position if no
rows were inserted, or to the newly inserted row with the highest
value otherwise.

> SELECT MAX doesn't use indices optimally
> ----------------------------------------
>                 Key: DERBY-642
>                 URL: https://issues.apache.org/jira/browse/DERBY-642
>             Project: Derby
>          Issue Type: Improvement
>          Components: Store
>    Affects Versions:
>            Reporter: Knut Anders Hatlen
>            Assignee: Knut Anders Hatlen
>            Priority: Minor
>         Attachments: derby-642-1a.diff, derby-642-1b-withTests.diff
> 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.
For more information on JIRA, see: http://www.atlassian.com/software/jira


View raw message