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