[CFReview] Red-Black Tree

Mark, do you need my data to reproduce results from
http://www.sai.msu.su/~megera/wiki/2009-07-27 ?

Oleg
On Fri, 29 Jan 2010, Mark Cave-Ayland wrote:

Hi Robert,

I've also spent some time reviewing this patch since it is a
pre-requisite to the KNNGiST patch. I did have a much more comprehensive
list of suggestions, but it seems you've managed to resolve most of
these with your latest re-write. Please find some more comments inline:

Here's an edited version, which I've now reviewed more fully. Some
more substantive review comments:

Firstly: the re-worked patch that you have posted seems to contain
remnants of at least 2 other patches. I have extracted the rbtree-only
sections and re-attached to this email.

The patch was tested against git head 124a3cc... and applied without any
fuzz or other issues.

1. I'm pretty satisfied that the rbtree code is generally sane,
although I wonder if we should think about putting it in access/common
rather than utils/misc. I'm not sure that I have a sufficiently
clearly defined notion of what each subdirectory is for to draw a
definitive conclusion on this point; hopefully someone else will weigh
in.

I'm happy that the code is a reasonable implementation of an RB-Tree, at
least with respect to the link to the related public domain source that
was posted. In terms of location, I think utils/misc is a reasonable
place for it to live since I see it as analogous to the hash table
implementation, i.e. it's a template RB-Tree implementation designed to
be used as required throughout the codebase. backend/access seems to be
the home of index AMs only.

Other code points:

- The new names for the iterator enum seem much better to me - or at
least it helped understand the meaning of the iterator code.

- You correctly picked up on the namespace issue, although I noticed
that you left RED and BLACK as they were. Maybe RBRED and RBBLACK would
be better, though not that there are any colour related defines around
in a database backend to make a name clash probable.

- I found the name of the "appendator" method misleading - perhaps
"updater" would make more sense?

2. I'm a little concerned about the performance implications of this
patch. Looking at http://www.sai.msu.su/~megera/wiki/2009-04-03, it's
clear that the patch is a huge win in some cases. But I'm also
surprised by how much performance is lost in some of the other cases
that you tested. I suspect, on balance, that it's probably still a
good idea to put this in, but I wonder if you've profiled this at all
to see where the extra time is going and/or explored possible ways of
squashing that overhead down a little more.

3. In ginInsertEntry(), the "else" branch of the if statement really
looks like magic when you first read it. I wonder if it would make
sense to pull the contents of EAAllocate() directly into this
function, since there's only one call site anyhow.

God yes. This is not a good example of maintainable code - even with your
comment I struggled for a while to try and figure it out :( I would suggest
that this is refactored appropriately before commit.

I still have not done any performance testing of my own on this code,
and it probably needs that. If anyone else has time to step up and
help with that, it would be much appreciated. It would be useful to
have some plain old benchmarks as well as some profiling data as
mentioned above.

As part of my testing, I attempted to duplicate some of the benchmarks
at http://www.sai.msu.su/~megera/wiki/2009-04-03. Unfortunately I was not
really able to reproduce the RND (teodor's) dataset, nor the random array
test as the SQL used to test the implementation was not present on the page
above.

For each test, I dropped and recreated the database to ensure that any
autovacuum impact would be the same.

1) Fixed length random & sequential string arrays

SELECT array_to_string(ARRAY(select '' || a || '.' || b from
generate_series(1,50) b), ' ')::tsvector AS i INTO seq FROM
generate_series(1,100000) a;

SELECT array_to_string(ARRAY(select '' || random() from
generate_series(1,50) b), ' ')::tsvector AS i INTO rnd FROM
generate_series(1,100000) a;

Before patch:

test=# create index seq_idx on seq using gin (i);
CREATE INDEX
Time: 103205.790 ms
test=# create index rnd_idx on rnd using gin (i);
CREATE INDEX
Time: 6770.131 ms

After patch:

test=# create index seq_idx on seq using gin (i);
CREATE INDEX
Time: 87724.953 ms
test=# create index rnd_idx on rnd using gin (i);
CREATE INDEX
Time: 5596.666 ms

2) Identical records, variable length test

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

Before patch:

i) len=3

select ARRAY(select generate_series(1,3)) as a3 into arr3 from
generate_series(1,100000) b;

test=# create index arr3_idx on arr3 using gin (a3);
CREATE INDEX
Time: 324.251 ms

ii) len=30

select ARRAY(select generate_series(1,30)) as a30 into arr30 from
generate_series(1,100000) b;

test=# create index arr30_idx on arr30 using gin (a30);
CREATE INDEX
Time: 2163.786 ms

iii) len=50

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

test=# create index arr50_idx on arr50 using gin (a50);
CREATE INDEX
Time: 3306.074 ms

iv) len=random

select ARRAY(select generate_series(1, (random() * 100)::int)) as arand into
arrrand from generate_series(1,100000) b;

test=# create index arrrand_idx on arrrand using gin (arand);
CREATE INDEX
Time: 4725.556 ms

After patch:

i) len=3

select ARRAY(select generate_series(1,3)) as a3 into arr3 from
generate_series(1,100000) b;

test=# create index arr3_idx on arr3 using gin (a3);
CREATE INDEX
Time: 299.090 ms

ii) len=30

select ARRAY(select generate_series(1,30)) as a30 into arr30 from
generate_series(1,100000) b;

test=# create index arr30_idx on arr30 using gin (a30);
CREATE INDEX
Time: 2828.424 ms

iii) len=50

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

test=# create index arr50_idx on arr50 using gin (a50);
CREATE INDEX
Time: 3984.456 ms

iv) len=random

select ARRAY(select generate_series(1, (random() * 100)::int)) as arand into
arrrand from generate_series(1,100000) b;

test=# create index arrrand_idx on arrrand using gin (arand);
CREATE INDEX
Time: 3514.972 ms

Summary
=======

I believe Robert has done a good deal of the groundwork required to get this
patch ready for inclusion. With the current version, I was able to see a
measurable performance improvement in some test cases with no significant
performance regression. It would have been nice to be able to reproduce the
whole set of test cases but this was not possible from the information
specified.

With perhaps some minor tweaks to some of the names and a rework of the else
clause in ginInsertEntry(), I feel this patch is reasonably close to commit.

I shall now continue my review of the associated KNNGiST patch.

ATB,

Mark.

Regards,
Oleg
_____________________________________________________________
Oleg Bartunov, Research Scientist, Head of AstroNet (www.astronet.ru),
Sternberg Astronomical Institute, Moscow University, Russia
Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
phone: +007(495)939-16-83, +007(495)939-23-83

On Fri, Jan 29, 2010 at 9:00 AM, Mark Cave-Ayland
<mark.cave-ayland@siriusit.co.uk> wrote:

I'm happy that the code is a reasonable implementation of an RB-Tree, at
least with respect to the link to the related public domain source that
was posted. In terms of location, I think utils/misc is a reasonable
place for it to live since I see it as analogous to the hash table
implementation, i.e. it's a template RB-Tree implementation designed to
be used as required throughout the codebase. backend/access seems to be
the home of index AMs only.

Not really. access/common has things in it like reloptions.c and
printtup.c, which are clearly not index AMs.

I suppose another option is to put it in lib. The only things there
right now are dllinfo.c and stringinfo.c, but in some ways generic
in-memory red-black trees seem analagous to generic string buffers.

- You correctly picked up on the namespace issue, although I noticed
that you left RED and BLACK as they were. Maybe RBRED and RBBLACK would
be better, though not that there are any colour related defines around
in a database backend to make a name clash probable.

Yeah, I thought about that. Since you came up with it independently,
that's enough to make me think it's a good idea.

- I found the name of the "appendator" method misleading - perhaps
"updater" would make more sense?

I like the existing name better. It's a little weird but I find it descriptive.

2. I'm a little concerned about the performance implications of this
patch.  Looking at http://www.sai.msu.su/~megera/wiki/2009-04-03, it's
clear that the patch is a huge win in some cases.  But I'm also
surprised by how much performance is lost in some of the other cases
that you tested.  I suspect, on balance, that it's probably still a
good idea to put this in, but I wonder if you've profiled this at all
to see where the extra time is going and/or explored possible ways of
squashing that overhead down a little more.

3. In ginInsertEntry(), the "else" branch of the if statement really
looks like magic when you first read it.  I wonder if it would make
sense to pull the contents of EAAllocate() directly into this
function, since there's only one call site anyhow.

God yes. This is not a good example of maintainable code - even with your
comment I struggled for a while to try and figure it out :(  I would suggest
that this is refactored appropriately before commit.

Yeah it took me a while.

I think we need Teodor and Oleg to prepare a new version of this patch
based on these suggestions. This part, in particular, I feel like
they need to rework rather than us. I don't know the GIN code well
enough to be confident of what I'm doing. I have to say that it would
be easier to understand what's going on here if there were a few more
comments...

With perhaps some minor tweaks to some of the names and a rework of the else
clause in ginInsertEntry(), I feel this patch is reasonably close to commit.

Yeah, I think it can get there, but only if Oleg and Teodor provide an
updated version pretty soon...

I shall now continue my review of the associated KNNGiST patch.

...especially if there is to be any thought of getting ANOTHER patch
after this one committed, too.

...Robert

Robert Haas <robertmhaas@gmail.com> writes:

On Fri, Jan 29, 2010 at 9:00 AM, Mark Cave-Ayland
<mark.cave-ayland@siriusit.co.uk> wrote:

... In terms of location, I think utils/misc is a reasonable
place for it to live since I see it as analogous to the hash table
implementation, i.e. it's a template RB-Tree implementation designed to
be used as required throughout the codebase. backend/access seems to be
the home of index AMs only.

Not really. access/common has things in it like reloptions.c and
printtup.c, which are clearly not index AMs.

That may be, but it's not a place for random generic data structures,
at least not ones that might be useful outside access/.

I suppose another option is to put it in lib. The only things there
right now are dllinfo.c and stringinfo.c, but in some ways generic
in-memory red-black trees seem analagous to generic string buffers.

I could live with either lib or utils/misc/.

regards, tom lane

With perhaps some minor tweaks to some of the names and a rework of the else
clause in ginInsertEntry(), I feel this patch is reasonably close to commit.

Yeah, I think it can get there, but only if Oleg and Teodor provide an
updated version pretty soon...

Updated version of patch based on version 0.7 from Mark (thank you for review!)
I removed EAAollocate() function and improved comments in ginInsertEntry().

--
Teodor Sigaev E-mail: teodor@sigaev.ru
WWW: http://www.sigaev.ru/

2010/2/2 Teodor Sigaev <teodor@sigaev.ru>:

 With perhaps some minor tweaks to some of the names and a rework of
the else
 clause in ginInsertEntry(), I feel this patch is reasonably close to
commit.

Yeah, I think it can get there, but only if Oleg and Teodor provide an
updated version pretty soon...

Updated version of patch based on version 0.7 from Mark (thank you for
review!)
I removed EAAollocate() function and improved comments in ginInsertEntry().

Can you rename RED and BLACK to RBRED and RBBLACK?

...Robert

Can you rename RED and BLACK to RBRED and RBBLACK?

Yes, of course, done.

Any objections to commit?

--
Teodor Sigaev E-mail: teodor@sigaev.ru
WWW: http://www.sigaev.ru/

2010/2/3 Teodor Sigaev <teodor@sigaev.ru>:

Can you rename RED and BLACK to RBRED and RBBLACK?

Yes, of course, done.

Any objections to commit?

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.

http://archives.postgresql.org/pgsql-hackers/2010-01/msg02552.php

...Robert

On Wed, Feb 3, 2010 at 8:48 AM, Robert Haas <robertmhaas@gmail.com> wrote:

2010/2/3 Teodor Sigaev <teodor@sigaev.ru>:

Can you rename RED and BLACK to RBRED and RBBLACK?

Yes, of course, done.

Any objections to commit?

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.

http://archives.postgresql.org/pgsql-hackers/2010-01/msg02552.php

Specifically, on this web page:

http://www.sai.msu.su/~megera/wiki/2009-04-03

There is a section that begins with this line of text:

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

That test shows rbtree being a third slower than HEAD. But there's
not enough information on that web page to replicate that test, so
it's hard to speculate on what may be going wrong. I don't think we
should commit this until we understand that.

...Robert

On Wed, 3 Feb 2010, Robert Haas wrote:

On Wed, Feb 3, 2010 at 8:48 AM, Robert Haas <robertmhaas@gmail.com> wrote:

2010/2/3 Teodor Sigaev <teodor@sigaev.ru>:

Can you rename RED and BLACK to RBRED and RBBLACK?

Yes, of course, done.

Any objections to commit?

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.

http://archives.postgresql.org/pgsql-hackers/2010-01/msg02552.php

Specifically, on this web page:

http://www.sai.msu.su/~megera/wiki/2009-04-03

There is a section that begins with this line of text:

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

That test shows rbtree being a third slower than HEAD. But there's
not enough information on that web page to replicate that test, so
it's hard to speculate on what may be going wrong. I don't think we
should commit this until we understand that.

Robert, Mark described the test he did
http://archives.postgresql.org/pgsql-hackers/2010-01/msg02927.php

Regards,
Oleg
_____________________________________________________________
Oleg Bartunov, Research Scientist, Head of AstroNet (www.astronet.ru),
Sternberg Astronomical Institute, Moscow University, Russia
Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
phone: +007(495)939-16-83, +007(495)939-23-83

2010/2/3 Oleg Bartunov <oleg@sai.msu.su>:

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.

http://archives.postgresql.org/pgsql-hackers/2010-01/msg02552.php

Specifically, on this web page:

http://www.sai.msu.su/~megera/wiki/2009-04-03

There is a section that begins with this line of text:

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

That test shows rbtree being a third slower than HEAD.  But there's
not enough information on that web page to replicate that test, so
it's hard to speculate on what may be going wrong.  I don't think we
should commit this until we understand that.

Robert, Mark described the test he did
http://archives.postgresql.org/pgsql-hackers/2010-01/msg02927.php

So why did he get totally different answers than you?

It's not enough to say "somebody else did a test and got better
numbers than we did, so let's use theirs".

...Robert

On Wed, 3 Feb 2010, Robert Haas wrote:

Robert, Mark described the test he did
http://archives.postgresql.org/pgsql-hackers/2010-01/msg02927.php

So why did he get totally different answers than you?

Because I did tests with 8.3 and HEAD+rbtree, while Mark compared
HEAD and HEAD+rbtree. Also, my HEAD and his HEAD are very different :)
I will not mention, that we used totally different setup.

It's not enough to say "somebody else did a test and got better
numbers than we did, so let's use theirs".

I'll repeat my tests with current CVS HEAD.

Regards,
Oleg
_____________________________________________________________
Oleg Bartunov, Research Scientist, Head of AstroNet (www.astronet.ru),
Sternberg Astronomical Institute, Moscow University, Russia
Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
phone: +007(495)939-16-83, +007(495)939-23-83

On Wed, Feb 3, 2010 at 4:17 PM, Oleg Bartunov <oleg@sai.msu.su> wrote:

On Wed, 3 Feb 2010, Robert Haas wrote:

Robert, Mark described the test he did
http://archives.postgresql.org/pgsql-hackers/2010-01/msg02927.php

So why did he get totally different answers than you?

Because I did tests with 8.3 and HEAD+rbtree, while Mark compared
HEAD and HEAD+rbtree. Also, my HEAD and his HEAD are very different :)
I will not mention, that we used totally different setup.

It's not enough to say "somebody else did a test and got better
numbers than we did, so let's use theirs".

I'll repeat my tests with current CVS HEAD.

OK... can you post the exact queries that you are used for the
previous round of testing?

...Robert

On Wed, 3 Feb 2010, Robert Haas wrote:

I'll repeat my tests with current CVS HEAD.

OK... can you post the exact queries that you are used for the
previous round of testing?

Robert, Mark posted all queries in his post ! See
http://archives.postgresql.org/pgsql-hackers/2010-01/msg02927.php

Regards,
Oleg
_____________________________________________________________
Oleg Bartunov, Research Scientist, Head of AstroNet (www.astronet.ru),
Sternberg Astronomical Institute, Moscow University, Russia
Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
phone: +007(495)939-16-83, +007(495)939-23-83

On Wed, Feb 3, 2010 at 4:51 PM, Oleg Bartunov <oleg@sai.msu.su> wrote:

On Wed, 3 Feb 2010, Robert Haas wrote:

I'll repeat my tests with current CVS HEAD.

OK... can you post the exact queries that you are used for the
previous round of testing?

Robert, Mark posted all queries in his post ! See
http://archives.postgresql.org/pgsql-hackers/2010-01/msg02927.php

Maybe we are now getting to the heart of the confusion. Mark wrote in
his email: "Unfortunately I was not really able to reproduce the RND
(teodor's) dataset, nor the random array test as the SQL used to test
the implementation was not present on the page above." The SQL for
the fixed-length tests is posted, but the SQL for the variable length
test is not - so Mark was just guessing on that one.

Or am I just totally confused?

...Robert

Robert Haas wrote:

Maybe we are now getting to the heart of the confusion. Mark wrote in
his email: "Unfortunately I was not really able to reproduce the RND
(teodor's) dataset, nor the random array test as the SQL used to test
the implementation was not present on the page above." The SQL for
the fixed-length tests is posted, but the SQL for the variable length
test is not - so Mark was just guessing on that one.

Or am I just totally confused?

...Robert

No, that's correct. In the "Repeat test with 100,000 identical records
varying array length (len)" section, it's fairly easy to substitute in
the varying values of len where len = 3, 30 and 50. As documented in my
review email I had a guess at generating the contents of RND (teodor's)
column with this query:

select ARRAY(select generate_series(1, (random() * 100)::int)) as arand
into arrrand from generate_series(1,100000) b;

However, unlike the other figures this is quite a bit different from
Oleg/Teodor's results which make me think this is the wrong query (3.5s
v 9s). Obviously Robert's concern here is that it is this column that
shows one of the largest performance decreases compared to head.

I've also finished benchmarking the index creation scripts yesterday on
Oleg's test dataset from
http://www.sai.msu.su/~megera/postgres/files/links2.sql.gz. With
maintenance_work_mem set to 256Mb, the times I got with the rbtree patch
applied were:

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

Without the patch applied, I ended up having to shutdown my laptop after
around 90 mins before the first index had even been created. So there is
a definite order of magnitude speed increase with this patch applied.

ATB,

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

I'm in progress of preparing this page
http://www.sai.msu.su/~megera/wiki/rbtree_test

Hope, tests are easy to reproduce.

This is slightly improved version of rbtree patch, Teodor didn't commit yet.
Random array test and real-life examples are ok, I still working on
test #1, which is quite artificial test, but still I want to understand if
the results are in accuracy of test.

Oleg

On Thu, 4 Feb 2010, Mark Cave-Ayland wrote:

Robert Haas wrote:

Maybe we are now getting to the heart of the confusion. Mark wrote in
his email: "Unfortunately I was not really able to reproduce the RND
(teodor's) dataset, nor the random array test as the SQL used to test
the implementation was not present on the page above." The SQL for
the fixed-length tests is posted, but the SQL for the variable length
test is not - so Mark was just guessing on that one.

Or am I just totally confused?

...Robert

No, that's correct. In the "Repeat test with 100,000 identical records
varying array length (len)" section, it's fairly easy to substitute in the
varying values of len where len = 3, 30 and 50. As documented in my review
email I had a guess at generating the contents of RND (teodor's) column with
this query:

select ARRAY(select generate_series(1, (random() * 100)::int)) as arand into
arrrand from generate_series(1,100000) b;

However, unlike the other figures this is quite a bit different from
Oleg/Teodor's results which make me think this is the wrong query (3.5s v
9s). Obviously Robert's concern here is that it is this column that shows one
of the largest performance decreases compared to head.

I've also finished benchmarking the index creation scripts yesterday on
Oleg's test dataset from
http://www.sai.msu.su/~megera/postgres/files/links2.sql.gz. With
maintenance_work_mem set to 256Mb, the times I got with the rbtree patch
applied were:

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

Without the patch applied, I ended up having to shutdown my laptop after
around 90 mins before the first index had even been created. So there is a
definite order of magnitude speed increase with this patch applied.

ATB,

Mark.

Regards,
Oleg
_____________________________________________________________
Oleg Bartunov, Research Scientist, Head of AstroNet (www.astronet.ru),
Sternberg Astronomical Institute, Moscow University, Russia
Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
phone: +007(495)939-16-83, +007(495)939-23-83

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@sigaev.ru
WWW: http://www.sigaev.ru/

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

That's all around 1%

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

--
Teodor Sigaev E-mail: teodor@sigaev.ru
WWW: http://www.sigaev.ru/