Re: [CFReview] Red-Black Tree

Teodor Sigaev wrote:

>> I would like to see point #2 of the following email addressed before
>> commit. As things stand, it is not clear (at least to me) whether
>> this is a win.
>
> Reimplementation of ginInsertRecordBA reduces difference of HEAD and
> HEAD+rbtree in regular case.
> Test suite is taken from http://www.sai.msu.su/~megera/wiki/2009-04-03:
>
> SEQ: SELECT array_to_string(ARRAY(select '' || a || '.' || b from
> generate_series(1,50) b), ' ')::tsvector AS i INTO foo FROM
> generate_series(1,100000) a;
> RND: SELECT array_to_string(ARRAY(select '' || random() from
> generate_series(1,50) b), ' ')::tsvector AS i INTO foo FROM
> generate_series(1,100000) a;
>
> Times in seconds:
> HEAD 0.9 0.11
> SEQ 130 113 111
> RND 11.4 12.6 11.5
>
> The ides was to change order of insertion - now insertion order
> decreases number of rebalancing.
>
> Oleg's test (http://www.sai.msu.su/~megera/wiki/rbtree_test) are made
> with v0.10 which is differ from 0.11 only by comments around
> ginInsertRecordBA()

Here is a quick comparison between the current 0.11 patch against my
original 0.7 patch when building Oleg's simple data. (Note: due to time
constraints, this is just a single run to get a feel for performance)

0.7 patch
=========

rbtest=# CREATE INDEX idin_rbtree_idx ON links2 USING gin (idin);
CREATE INDEX
Time: 1910741.352 ms

rbtest=# CREATE INDEX idout_rbtree_idx ON links2 USING gin (idout);
CREATE INDEX
Time: 1647609.300 ms

0.11 patch
==========

rbtest=# CREATE INDEX idin_rbtree_idx ON links2 USING gin (idin);
CREATE INDEX
Time: 1864013.526 ms

rbtest=# CREATE INDEX idout_rbtree_idx ON links2 USING gin (idout);
CREATE INDEX
Time: 1661200.454 ms

HTH,

Mark.

--
Mark Cave-Ayland - Senior Technical Architect
PostgreSQL - PostGIS
Sirius Corporation plc - control through freedom
http://www.siriusit.co.uk
t: +44 870 608 0063

Sirius Labs: http://www.siriusit.co.uk/labs