Subject Re: [Firebird-Architect] Bi-directional indexes
Author Ann W. Harrison
OK, let me see if I understand where we currently are on the walking
backward issue. There may be a solution lurking that doesn't prevent
releasing index pages, at the expense of some repositioning logic for
right to left traversal.

There's no point in retrofitting this stuff to old indexes. New indexes
sort duplicates by record number, which turns out to be important.

I think it's pretty well established that when walking an index
backward, one must be prepared to release lock the current index page
before seizing a lock on its right hand neighbor. Certainly one can
attempt a no-wait handoff, but if that fails, the only remedy is to
release the current page.

(1) Before releasing that page, we should note the key value and record
number of the last index entry we read. In addition, we note the page
number and generation number of the index page we're about to release.

We acquire a read lock and read the left hand sibling page.

If its right sibling pointer is the old page(2), we do a right handoff
to the old page, and check the generation number(3). If it has not
changed, we try the instant handoff again. If that succeeds, fine, if
that fails we return to (1) and continue the loop until it succeeds or
exits at points (2) or (3).

If the sibling pointer is wrong at point (2) or if the generation number
has changed at point (3), we go back to the top of the index and
reestablish our location using the saved key and record number. As Arno
pointed out, if that particular value has been garbage collected, the
index lookup stops at the next record. Retrieval starts with the next
record to the left.

I think it may work.