Re: [PATCH] binary heap implementation

On Wed, Nov 21, 2012 at 6:08 AM, Andres Freund <andres(at)2ndquadrant(dot)com> wrote:
> On 2012-11-20 22:55:52 -0500, Tom Lane wrote:
>> Abhijit Menon-Sen <ams(at)2ndQuadrant(dot)com> writes:
>> >> While I'm thinking about it, why are the fields of a binaryheap_node
>> >> called "key" and "value"? That implies a semantics not actually used
>> >> here. Maybe "value1" and "value2" instead?
>>
>> > Yes, I discussed this with Andres earlier (and considered ptr and value
>> > or p1 and p2), but decided to wait for others to comment on the naming.
>> > I have no problem with value1 and value2, though I'd very slightly
>> > prefer d1 and d2 (d for Datum) now.
>>
>> d1/d2 would be fine with me.
>>
>> BTW, I probably missed some context upthread, but why do we have two
>> fields at all? At least for the purposes of nodeMergeAppend, it
>> would make a lot more sense for the binaryheap elements to be just
>> single Datums, without all the redundant pointers to the MergeAppend
>> node. The need to get at the comparison support info could be handled
>> much more elegantly than that by providing a "void *" passthrough arg.
>> That is, the heap creation function becomes
>>
>> binaryheap *binaryheap_allocate(size_t capacity,
>> binaryheap_comparator compare,
>> void *passthrough);
>>
>> and the comparator signature becomes
>>
>> typedef int (*binaryheap_comparator) (Datum a, Datum b, void *passthrough);
>>
>> For nodeMergeAppend, the Datums would be the slot indexes and the
>> passthrough pointer could point to the MergeAppend node.
>>
>> This would make equal sense in a lot of other contexts, such as if you
>> wanted a heap composed of tuples -- the info to compare tuples could be
>> handled via the passthrough argument, rather than doubling the size of
>> the heap in order to put that pointer into each heap element. If you
>> have no use for the passthrough arg in a particular usage, just pass
>> NULL.
>
> The passthrough argument definitely makes sense, I am all for adding it.
>
> The reasons I originally wanted to have two values was that it made it
> easy/possible for the comparison function to work without any pointer
> dereferences which was somewhat beneficial to performance. Completely
> without dereferences only worked on 64bit systems anyway though...
> With just one value I need an extra struct, but thats not too bad.
>
> So if you all prefer just having one value, I am ok with that. Who is
> updating the patch?

I guess I'll take another whack at it.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company