db-derby-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Mike Matrigali (JIRA)" <j...@apache.org>
Subject [jira] Updated: (DERBY-884) allow and use backward scans on indexes.
Date Thu, 02 Dec 2010 18:42:12 GMT

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

Mike Matrigali updated DERBY-884:

To avoid latch/latch deadlocking you should maintain the current latching ordering scheme.
 So only wait on latches while holding latches when moving top to down and left to right.
 As you have laid out when moving right to left and you always request the latch
NOWAIT and then if you have to wait you need to save your position somehow and give up the
current latch and wait for the held
latch.  Once you have the new latch you need to give it up and reposition on the old row,
get that latch and continue the left to 
right scan.  Positioning by key should always work, but I think you need to handle the case
where the key disappears (at least for
some isolation levels).   I think there is existing code that does this to handle the similar
case where we can't hold a latch while 
waiting for a lock on a row, but the code probably is not exactly right for right to left
vs left to right.   

In right to left you probably want to position on >= ; where left to right we probably
position on <=.  

I think the cleanest implementation would be to add new backward scan interfaces to store
and implement the scan as separate
classes, following the BTreeMaxScan.java pattern.  (actually once a real backward scan exists
BTreeMaxScan should be changed
to use it and will be much more efficient).    I would suggest looking at the TransactionController.openScan()
interface defiition and
figure out what the start and stop parameters mean for a reverse scan.  I believe there should
be no interface change to the qualifiers
(but coding for them might be different (ie. opposite) for the backward scan - not sure).
 The backward vs. forward stuff seems obvious for single key indexes but gets complicated
for multiple column key indexes.  

> allow and use backward scans on indexes.
> ----------------------------------------
>                 Key: DERBY-884
>                 URL: https://issues.apache.org/jira/browse/DERBY-884
>             Project: Derby
>          Issue Type: Improvement
>          Components: SQL, Store
>    Affects Versions:
>            Reporter: Mike Matrigali
>            Priority: Minor
> Improve the access interface to support backward scans, currently only forward scans
are supported.
> Improve the btree implementation to support backward scans.  The structure could support
this, the work just has not been done.  With
> row level locking, concurrent tree splitting, and current assumptions
> throughout the access method that scans go top/down, left to right the
> work to do a backward scan is harder than doing a forward scan.  Also
> once the store portion is done, there would be necessary changes to:
> optimizer, execution engine, and scan interface to allow the backward
> scan.  This would be a hard first project. 
> Improve the optimizer to understand derby indexes now support backward scans.
> Improve the execution engine to use the new backward scan interfaces to execute backward

This message is automatically generated by JIRA.
You can reply to this email to add a comment to the issue online.

View raw message