Skip site navigation (1) Skip section navigation (2)

Re: [CFReview] Red-Black Tree

From: Teodor Sigaev <teodor(at)sigaev(dot)ru>
To: Robert Haas <robertmhaas(at)gmail(dot)com>
Cc: Mark Cave-Ayland <mark(dot)cave-ayland(at)siriusit(dot)co(dot)uk>, Pgsql Hackers <pgsql-hackers(at)postgresql(dot)org>
Subject: Re: [CFReview] Red-Black Tree
Date: 2010-02-04 15:53:52
Message-ID: 4B6AED90.9040703@sigaev.ru (view raw or flat)
Thread:
Lists: pgsql-hackers
> 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()
-- 
Teodor Sigaev                                   E-mail: teodor(at)sigaev(dot)ru
                                                    WWW: http://www.sigaev.ru/

Attachment: rbtree-0.11.gz
Description: application/x-tar (8.7 KB)

In response to

Responses

pgsql-hackers by date

Next:From: Marko TiikkajaDate: 2010-02-04 16:04:51
Subject: Writeable CTEs documentation patch
Previous:From: Heikki LinnakangasDate: 2010-02-04 15:30:29
Subject: Re: Shared catalogs vs pg_global tablespace

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group