On 10-6-2012 12:32, Dmitry Yemanov wrote:

> 10.06.2012 14:09, Mark Rotteveel wrote:
>>
>> * for each record (sequential read of all pages?)
>> * insert column value into index
>
> Inserting unsorted / random values into the b-tree is known to be much
> slower than sorting the values in advance and loading them into the
> b-tree "in order".

If the trade off is requiring a large part of memory or disk space extra
(and the additional time required to perform the sort), then I do wonder
if the advantage is really that big.

The build of a balanced b-tree(*) is O(n log n), and the 'good' case of
sorting is O(n log n) to O(n^2) (ideal is O(n)). Sorting before
insertion might only be worth the effort if the sort can fully occur in
memory. The additional overhead of writing to disk during the sort and
reading from disk for insertion might negate most of the advantages
against the overhead of inserting into the b-tree unsorted (ie balancing
etc).

It might be worth to investigate this tradeoff, or just to provide an
option to rebuild indices without using temporary sort spaces so others
can measure it for themselves (or to have a workaround if disk space is
not large enough to accommodate the rebuild).

*) I am assuming FB uses a balanced trees, because sorting first would
otherwise degenerate it into a linked list
--
Mark Rotteveel