Subject Re: [firebird-support] Today's performance question - index direction
Author Ann Harrison

On Thu, Sep 5, 2013 at 1:21 PM, Mark Rotteveel <mark@...> wrote:
On 5-9-2013 18:02, Ann Harrison wrote:

> A major goal for Firebird's indexes was to minimize index locking and
> allow pages to be added to and dropped from indexes without blocking
> index reads.  There's a long paper on the IBPhoenix web site that
> explains exactly how that works.  The summary is that during index
> modifications, the forward pointers between pages in an index are always
> correct, but the back pointers are not guaranteed. 

I wonder though, when you are following the back pointers couldn't this
be solved by checking the forward pointer from the 'current' page to see
if it points back to your 'previous' page? And when it doesn't, you
follow the forward pointers back to your 'previous' page adding those
pages to a stack, and when you reach the 'previous' page then you
process the page pages from the stack and start reading again from the
'current' page?

To avoid internal deadlocks, Firebird allows each connection only one 
hard page lock at a time. Other locks are just bookkeeping so the engine
can figure out who has a page in cache and whether the page is dirty.
When someone else wants a page that's in your cache, the engine
writes the page (if it's dirty and Classic) and releases the lock.  When 
you reference the page again, Firebird reads it in (in Classic) or gives 
you a reference to the new version of the page (in SS).  So there's
no guarantee that the page that was the prior is still the prior.

In a contentious environment, pages change amazingly quickly.  Vlad
Khorson solved a very mysterious problem that showed up as a wrong
page type when looking for an item in an index.  As it happens, there 
are actually three pointers to each page in the index, left, right, and
parent.  Sometimes a page would be removed from an index and reallocated
to some other use (generally a data page) between the time the parent 
pointer was read and the page it pointed to was read. 

Stacking page numbers really doesn't work.  You have to come down
from the top again.  And yes, if you do the "I went from C to A, does
A point forward to C?" check and start from the top again every time
it fails, you could read the index backward.  That's code that's never
been written.

Good luck,