2009-04-03

Red-Black Tree experiments

Red-Black tree will eventually replaces BTree in GIN code. BTree suffers from the curse of sorted data (tree became very nonbalanced, so tree degenerates to the list with O(N^2) processing time, see thread http://archives.postgresql.org/pgsql-performance/2009-03/msg00340.php) ). Create index for such data will be amazingly slow, so we decided to replace BTree in GIN by RB-tree, which is self-balanced binary tree, to defense from such bad behaviour. This will affect bulk insert, i.e. create index and pending list cleanup. Tom Lane recently submitted quick defence against such behaviour into 8.3 and HEAD.

Teodor did quick test of rb-tree:

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;

Time of create index command in seconds.

                SEQ         RND
HEAD          140.131     119.160
rbtree        115.567      12.393

Update: Second query actually produces identical records, so it illustrates degenerated case of very unbalanced data, where rbtree has a huge advantage (as it follows from the result).

Test with random arrays with maxlen=1000, total 100,000 rows and 500,000 unique values shows rbtree slightly slower than HEAD code (with defense).

             RND (fu=on)   RND (fu=off)
HEAD (s)     175.762       180.061
rbtree       185.567       184.012       

Repeat test with 100,000 identical records varying array length (len).

select ARRAY(select generate_series(1,len)) as a50  into arr50 from generate_series(1,100000) b;

             len=3         len=30      len=50        RND (teodor's)
HEAD (ms)    835.792       3673.383    7498.342      9990.729
Mark         324.251       2163.786    3306.074      4725.556
rbtree       797.571       3771.747    7304.004      13440.959
Mark         299.090       2828.424    3984.456      3514.972 

Update: I added results from Mark Cave-Ayland

Results from experiment with real data (electronic papers archive) isn't very optimistic about rb-tree, but show almost the same performance as for BTree (plus recent defense by Tom Lane).

Btree:

arxiv=# create index gin_x_idx on papers using gin(fts);
CREATE INDEX
Time: 81714.308 ms
arxiv=# select pg_total_relation_size('gin_x_idx');
 pg_total_relation_size
------------------------
              319225856

RB-tree
arxiv=# create index gin_x_idx on papers using gin(fts);
CREATE INDEX
Time: 86312.517 ms
arxiv=# select pg_total_relation_size('gin_x_idx');
 pg_total_relation_size
------------------------
              319799296
(1 row)