On 10 Jun 2003 at 17:43, Alexander Klenin wrote:

> PROBLEM 1:
> Linear search for a key in the index page is slow when
> there are many repeated lookups in the small index (often
> the case with current optimizer ;). At least, that is what
> Arno said (and I assume that this is true). The binary
> search would help this, but it is precluded by the key
> compression.
> SOLUTION 1:
> As proposed by Arno: disable key compression altogether
> for small keys. (For some definition of "small"). This
> (apparently) solves problem 1, but leads to

This proposed solution actually allows random access to all nodes (all
nodes have the same size), while current ODS structure of B-tree page
allows only sequential scan, as there isn't any bucket pointer array like
on Data pages. Any solution will be always a trade off between dense B-
tree pages (the current one is as most dense as possible) that in turn
will result in shallow tree and thus less disk I/O, against more complex
B-tree page structure that would allow us to use a better page scan
algorithm.

Well, because db engine is always disk-bound, it may seem
straightforward, but it's not because many factors come to play here. The
main ones are:

1) The actual fruitfulness of key compression. This is affected by key
complexity (number of key segments, segment types, data mangling) and
data distribution. While some indices may have a great benefit from
prefix compression (especially with a lot of duplicates), others may not
and compression may turn in an obstacle. Actually, I'd like collect and
see some real-world gstat data for indices and try to find out if there
are some identifiable non-trivial conditions when pf. compression would
(not) help.

2) Page lookup complexity and overhead. Current one is very simple but
linear. Solution proposed by Arno is not complex either, and will have
better characteristic.

3) B-Tree maintenance overhead. Current design has very small maintenance
overhead in comparison to other mentioned / possible structures and
algorithms, at the expense of sub-optimal lookup at page level. Solution
proposed by Arno has the advantage of smallest maintenance overhead
(actually equal to current one as the maintenance code doesn't change
much) from any other proposed / possible solution.

So, I can imagine situations, where fixed-size nodes will really have
better performance than compressed ones (especially for small unique
keys), but I can't figure out any possible decision-making algorithm to
choose the best one automatically without actual full index
creation/computation of both and their comparison. Making such decision-
making to work behind the scene would be hard or at least will end in
weird and confusing server functionality.

So, I guess that we *could* implement Arno's design as an additional
mechanism for indices, and left the decision on the user/admin. At the
same time, we *should* provide tools/mechanism to compute (try-build)
characteristics for both methods for given key on current data (probably
as part of gstat ?).

> PROBLEM 2:
> Uncompressed indexes take more space, thereby slowing
> lookup when indexes are large and do not fit in the cache.
> This slowdown is the reason why Jim Starkey opposes
> solution 1, and so I thought that it may be amended by
> SOLUTION 2:
> Force insertion of uncompressed index (in the form "0abcd"
> as per your example) after every N records even if actual
> key values allow compression.
> The search algorithm then can work as following:
> 1) do a binary search on uncompressed values until the key
> is found or interval length is less then N
> 2) scan search interval with currect (compression-aware)
> method
> Given a reasonable (or, perhaps, tunable) value of N it is
> possible to avoid index inflation while still keeping page
> search time essentially logarithmic.
> However, there is a

The problem with this approach is two-fold:

1) We must change current b-tree page layout to allow direct random
access while nodes have various size, i.e. introduce a pointer array. It
may or may not be better than equal-sized nodes without such array, but
I'd oppose this even if it would be better as it impose more overhead and
complexity.

2) B-tree maintenance (insert/update/delete) including page split/merge
would be a nightmare.

Best regards
Pavel Cisar
http://www.ibphoenix.com
For all your upto date Firebird and
InterBase information