Re: [CFReview] Red-Black Tree

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(at)sai(dot)msu(dot)su, http://www.sai.msu.su/~megera/
phone: +007(495)939-16-83, +007(495)939-23-83