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] Commented: (DERBY-884) allow and use backward scans on indexes.
Date Thu, 02 Dec 2010 13:18:11 GMT

    [ https://issues.apache.org/jira/browse/DERBY-884?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12966111#action_12966111
] 

Knut Anders Hatlen commented on DERBY-884:
------------------------------------------

Does anyone have any thoughts on how to avoid deadlocks between the
scans that move left to right and those that move right to left?
Here's what comes to my mind:

The scan that moves right to left could save the scan position (that
is, copy the key found on the current position, similar to what we did
in DERBY-2991) if it cannot obtain the latch on the left sibling
immediately. After saving the position, it could release the latch on
the current leaf page and wait for the left sibling to become
unlatched. Once it detects that the left sibling is unlatched, it can
reposition in the B-tree using the saved key and continue the scan
from the old position.

Since the latch on the current leaf is released before the scan waits
for the latch on the left sibling, the right-to-left scan shouldn't be
causing any deadlocks. And releasing the latch on the current leaf
page should also be safe, since we reposition using the key so we'll
find the correct position in the scan even if the key was moved while
the page was not protected by a latch.

> 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: 10.1.3.1
>            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
scans.

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


Mime
View raw message