Subject Re: [Firebird-Architect] Bi-directional indexes
Author Geoff Worboys
Hi Ann,

> I've read too many messages from users of other systems who
> can't believe how "primitive" Firebird is in not supporting
> what is "obviously" superior technology.

My own reaction was not so much that FB must be primitive, just
a total lack of understanding or expectation. I thought I had
studied index algorithms in some detail several years ago but
I did/do not remember coming across an algorithm that was
unidirectional. (Of course I realise now that I did not study
algorithms that tried to make sense of multiple generations and

So it was a considerable surprise to me to discover that I may
indeed have to implement two indexes if I had data that needed
optimisation for access in either direction. Considering the
potential cost of index maintenance this seemed like a waste.

I guess the truth is that need for bidirectional access is
comparitively rare, thus the trade-offs of a more efficient
unidirectional algorithm made (make?) sense.

But my point here is that I expect many people like myself tend
to just assume an index will be bidirectional. It is not one
of those things that I even thought to question when I started
using a new database system. I think this expectation leads to
the reactions you are seeing from other people.

A similar situation exists with a recent thread where a user
was incorrectly expecting that indexes contained actual data
that could be used to optimise SELECT DISTINCT on indexed
fields. (However this situation can be resolved by using a
more carefully normalised database design, I really do not
think it is a "problem" that needs resolving in FB itself.)

The bidirectional index issue is something that I suspect
really should be fixed but ONLY if that fix proves to be less
expensive than maintenance of two indexes instead of one.
Following from this...

Index maintenance becomes the significant issue on tables that
have a high volume of changes. And therein lies the problem
with your proposal. Your proposed solution needs to disable
self-compaction, and this feature is also most important on
tables with a high volume of changes. The trade-offs are not
likely to be good, potentially decreasing the performance on
an index until we get to a point where two indexes would have
been better than one.

That is; The place where most need the fix is also the place
where your proposed fix is most likely to run into problems.

It seems that the problem you are trying to resolve relates
to this part of your description:

> So, rather than doing a handoff, the backward walker must
> release the page it holds then get a read lock on the next
> page.

I am not familiar with what you mean by "handoff" - which is
probably why I do not understand why the backward reader cannot
try to get a lock on the next page before it releases the page
that it holds. If a way can be found to do this without
causing internal deadlocks then the rest of the problem goes
away - yes?

So where does the deadlock come from? If we understand this
in more detail perhaps we can find a way to prevent it without
all the other mucking around.

Geoff Worboys
Telesis Computing