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
usingti2 on t3  ->  Zipper  (cost .., sort by public.t.i)        -> Index Scan using ti4 on t4        -> Index Scan
usingti5 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