Re: [PATCH] binary heap implementation

On 2012-11-15 11:37:16 -0500, Robert Haas wrote:
> On Thu, Nov 15, 2012 at 11:22 AM, Andres Freund <andres(at)2ndquadrant(dot)com> wrote:
> > On 2012-11-14 18:41:12 +0530, Abhijit Menon-Sen wrote:
> >> There are two or three places in the Postgres source that implement heap
> >> sort (e.g. tuplesort.c, nodeMergeAppend.c), and it's also needed by the
> >> BDR code. It seemed reasonable to factor out the functionality.
> >
> > pg_dump also contains a binary heap implementation if memory serves
> > right which makes me wonder whether we should try binaryheap.[ch]
> > backend clean... It currently uses palloc/pfree.
> >
> > Too bad we don't have a memory allocation routine which easily works in
> > the backend and frontend... palloc references MemoryContextAlloc and
> > CurrentMemoryContext so thats not that easy to emulate.

> I think there's a clear need for a library of code that can be shared
> by frontend and backend code. I don't necessarily want to punt
> everything into libpq, though.

Aggreed.

> What I wonder if we might do is create
> something like src/lib/pgguts that contains routines for memory
> allocation, error handling, stringinfos (so that you don't have to use
> PQexpBuffer in the frontend and StringInfo in the backend), etc. and
> make that usable by both front-end and back-end code. I think that
> would be a tremendously nice thing to have.

Yes. But it also sounds like quite a bit of work :(

> I don't think we should make it this patch's problem to do that

Me neither. I was thinking about letting the "user" allocate enough
memory like:

binaryheap *heap = palloc(binaryheap_size(/*capacity*/ 10));
binaryheap_init(heap, 10, comparator);

But thats pretty ugly.

> but
> I'd be strongly in favor of such a thing if someone wants to put it
> together. It's been a huge nuisance for me in the past and all
> indicates are that the work you're doing on LR is just going to
> exacerbate that problem.

I actually hope I won't have to fight with that all that much, but we
will see :/

Greetings,

Andres Freund

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services