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

Re: [CFReview] Red-Black Tree

From: Robert Haas <robertmhaas(at)gmail(dot)com>
To: Mark Cave-Ayland <mark(dot)cave-ayland(at)siriusit(dot)co(dot)uk>
Cc: Teodor Sigaev <teodor(at)sigaev(dot)ru>, Pgsql Hackers <pgsql-hackers(at)postgresql(dot)org>
Subject: Re: [CFReview] Red-Black Tree
Date: 2010-01-29 19:04:01
Message-ID: 603c8f071001291104n5f41f188ra43a2ad89e6bb1a6@mail.gmail.com (view raw or flat)
Thread:
Lists: pgsql-hackers
On Fri, Jan 29, 2010 at 9:00 AM, Mark Cave-Ayland
<mark(dot)cave-ayland(at)siriusit(dot)co(dot)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

In response to

Responses

pgsql-hackers by date

Next:From: Tom LaneDate: 2010-01-29 19:04:17
Subject: Re: [COMMITTERS] pgsql: Augment WAL records for btree delete with GetOldestXmin() to
Previous:From: Greg StarkDate: 2010-01-29 18:56:23
Subject: Re: Faster CREATE DATABASE by delaying fsync (was 8.4.1 ubuntu karmic slow createdb)

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