Re: Ordered Append Node

Hello Gregory,

Gregory Stark wrote:
> It is kind of like a merge join but not quite. It's interleaving rows rather
> than matching them up. It's more like the final merge of a sort which also
> uses a heap to efficiently find the next value from the source tapes.

Well, maybe my point here is: why do you need the heap to sort? The
inputs you've got are already sorted, you only need to merge them. To me
this sounds very much like the final stage of a merge sort, which would
not require much memory.

IMO, a merge sort could easier be implemented by a binary tree zipper
node, as I had in mind. Leading to a plan like that (well, hey, this is
all made up):

Zipper (cost..., sort by public.t.i)
-> Zipper (cost .., sort by public.t.i)
-> Zipper (cost .., sort by public.t.i)
-> Index Scan using ti1 on t1
-> Index Scan using t12 on t2
-> Index Scan using ti2 on t3
-> Zipper (cost .., sort by public.t.i)
-> Index Scan using ti4 on t4
-> Index Scan using ti5 on t5

Every zipper node would simply have to keep the two top tuples from its
inputs in memory, compare them and return the best.

But maybe that's exactly how Knuth's polyphase merge sort internally
also merge their inputs (or runs). And perhaps it makes sense to show
the user just one simple append node instead of throwing a tree of
Zipper nodes at her. ;-)

> Not necessarily but it is something Postgres supports and I don't think we
> want to break it. Actually it's useful for partitioned tables if you build the
> new partition in a separate table and then add it to the partitioned table. In
> that case you may have gone through several steps of adding columns and
> dropping them to get the structure to line up.

Agreed, especially because lining up the columns isn't that hard after all.

OTOH I think Postgres is way too flexible in how it allows partitioning
to be done and thus it often can't optimize it properly. I'd very much
like to teach it a stricter and simpler to use partitioning scheme than
what we have with constraint exclusion.

But that's pipe dreaming, and your improvement to the append node is
certainly a good step towards the right direction, keep up the good work!

Regards

Markus