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 |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
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
From | Date | Subject | |
---|---|---|---|
Next Message | Tom Lane | 2010-01-29 19:04:17 | Re: [COMMITTERS] pgsql: Augment WAL records for btree delete with GetOldestXmin() to |
Previous Message | Greg Stark | 2010-01-29 18:56:23 | Re: Faster CREATE DATABASE by delaying fsync (was 8.4.1 ubuntu karmic slow createdb) |