Geoff Worboys wrote:

>
> ... 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
> transactions.)

Everything's easy if it's read only. Most things are easy if they're
single user. Multi-user updates with transactional stability make this
job interesting and challenging.

>
> Index maintenance becomes the significant issue on tables that
> have a high volume of changes.

If the data is generated in random order, index compaction doesn't
matter. Compaction is important when old data has low values and no new
low values are stored. (Or vice versa - when old data has high values
an no new high values are stored.) A generator is worst case - when you
delete an index entry, you know you're never going to store another one
there.

> 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 "need" to walk indexes backward isn't related to the volatility of
the key, but I do take your point that that index compression was
introduced for a reason (the reason being Jim's departure from
InterBase) and probably serves a purpose.

> 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"

Sorry, I thought that was a general term of art. No single request in
Firebird can hold a lock on more than one page. Requests often have
more than one lock, but they have to be prepared to release all but one
active page if requested to do so. That's how we avoid internal
deadlocks. When you're walking a structure, that rule is inconvenient -
the pointer from one page to the next is an essential bridge, and you'd
like to think that neither end of the bridge will disappear before you
get across. The mechanism is a handoff - a special lock request that
says, I've got a lock on this page and will give it up if you give me a
lock on that page. Handoffs don't produce deadlocks as long as they go
in the same direction.


- 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?

Right, and if I find a way to repeal gravity, apples will stay on trees.

>

Regards,


Ann