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 Thu, 24 Feb 2011 16:14:38 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-2a-test-serializable.diff

Attaching a patch (2a) which adds a test for the repositioning logic after waiting for a lock
in serializable transactions. The test doesn't reveal any problems, but that's because the
B-tree max scans are currently always performed with table locks in serializable transactions.

The test case does expose the phantom read problem discussed above if we switch to record
locking for those scans. That can be achieved by disabling the following code in FromBaseTable:

			** Figure out whether to do row locking or table locking.
			** If there are no start/stop predicates, we're doing full
			** conglomerate scans, so do table locking.
			if (! startStopFound)

							    0, 0, 0.0, null);

I'm not planning to switch to record locking for max scans as part of this issue, but I'd
like to have a test case for it in any case.

Committed revision 1074196.

> 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, derby-642-2a-test-serializable.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