On Wed, 2009-05-20 at 07:17 -0400, Robert Haas wrote:
> On Wed, May 20, 2009 at 4:11 AM, Simon Riggs <simon@2ndquadrant.com> wrote:
> > The Hash node is fully executed before we start pulling rows through the
> > Hash Join node. So the Hash Join node will know at execution time
> > whether or not it will continue to maintain sorted order. So we put the
> > Sort node into the plan, then the Sort node can just ask the Hash Join
> > at execution time whether it should perform a sort or just pass rows
> > through (act as a no-op).
>
> It's not actually a full sort. For example if the join has two
> batches, you don't need to dump all of the tuples from both batches
> into a sort. Each of the two tapes produced by the hash join is
> sorted, but if you read tape one and then tape two, of course then it
> won't be. What you want to do is read the first tuple from each tape
> and return whichever one is smaller, and put the other one back; then
> lather, rinse, and repeat. Because it's such a special-case
> computation, I think you're going to want to implement it within the
> HashJoin node rather than inserting a Sort node (or any other kind).
That has wider applicability and seems sound. It will also be easier to
assess a cost for that aspect in the optimizer. I like that approach.
Code wise, you'll need to refactor things quite a lot to make the
tuplesort code accessible to the HJ node. The sorting code is going to
get pretty hectic if we add in all the ideas for this, partial sort,
improved sorting (at least 3 other ideas). Perhaps it will be easier to
write a specific final merge routine just for HJs.
--
Simon Riggs www.2ndQuadrant.com
PostgreSQL Training, Services and Support
