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)