Dmitry,

Your analysis is correct, but I'm less wild about your
solution.

>The long story, the short question: what about including transaction id into
>BTN structure? Is it possible? Right now I see only the following cases to
>speed up with transaction id in a key:
>1. select count
>2. index garbage collection
>3. group by (when index is used).
>
>What do you think?

I think that making "select count" faster by making everything
else slower is a mistake. (I also think a lot of other things,
but that's the relevant one.)

First, adding the transaction id makes every node four bytes bigger,
and it must be propagated up the tree.

Second, if you have multiple versions of a record with a single
key value, there's currently only one index entry.

When updating, InterBase checks to see if the index entry already
exists, and if so, doesn't update the index. Your change would
require storing an index entry for every record version.

When garbage collecting, InterBase checks to see if there's another
version of the record with the key value from the version that's
going away. If so, it ignores that garbage collection pass.

A better solution, in my opinion, would be to propagate record numbers
up the tree. Same length, already in the leaf level, makes every
index entry unique.

Regards,

Ann