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

Re: Red-black tree for GIN

From: Robert Haas <robertmhaas(at)gmail(dot)com>
To: Teodor Sigaev <teodor(at)sigaev(dot)ru>
Cc: Pgsql Hackers <pgsql-hackers(at)postgresql(dot)org>
Subject: Re: Red-black tree for GIN
Date: 2009-12-31 21:19:11
Message-ID: 603c8f070912311319q4fb1ffffrbfc0adef1d237db5@mail.gmail.com (view raw or flat)
Thread:
Lists: pgsql-hackers
2009/11/23 Teodor Sigaev <teodor(at)sigaev(dot)ru>:
> Hi there,
>
> attached is a patch, which contains implementation of a  red-black
> tree,  a self-balanced implementation of binary tree.  The main goal of
> this patch is to improve creation time of GIN index in the corner cases.
> While creation, GIN collects data in memory in binary tree until it
> reach some limit and then it flush tree to disk. Some data could
> produces unbalanced binary tree,  for example, sorted data, so the tree
> degenerates to the list with O(N^2) processing time (see thread
> http://archives.postgresql.org/pgsql-performance/2009-03/msg00340.php)
> ), which cause very slow index creation.  Tom has fixed that by limiting
> depth of tree  (committed to 8.3 and 8.4),  but we found it's not enough
> and propose to use red-black tree, which is very good for skewed data and
> has almost the same performance for unsorted data, see
> http://www.sai.msu.su/~megera/wiki/2009-07-27 and
> http://www.sai.msu.su/~megera/wiki/2009-04-03 for more information.
>
> Implementation of red-black tree has several currently unused  methods,
> but they will be used in next patches.

I did a quick read-through of this, and one question that immediately
occurred to me is that rbtree.c says that it is adopted from
http://algolist.manual.ru/ds/rbtree.php.  But I'm not sure what
license that code is under, so I'm not sure whether it's OK for us to
use it.

My other question is as related to performance.  Can you provide a
test case that shows the performance improvement with this patch?

...Robert

In response to

Responses

pgsql-hackers by date

Next:From: Robert HaasDate: 2009-12-31 21:28:41
Subject: Re: PATCH: Add hstore_to_json()
Previous:From: Jeff DavisDate: 2009-12-31 21:16:54
Subject: Re: Serializable Isolation without blocking

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