Append nodes and orderings

The topic was recently mentioned again on -performance of Append nodes from
inherited tables destroying available orderings. Luke posted a patch a while
back which enabled using indexes for the sub plans and preserved the orderings
though a lot of the meat of the code to do this was missing from the patch.

One way to do this is to figure out when the subplans are in the right order
or can be re-ordered to maintain the ordering. But that seems computationally
hard. And it would only work in cases were you have precisely the right
constraints on each partition, which given our current problems with the
parent table would be never.

There's another approach though. We could make a new kind of Append node which
maintains a heap to do a merge much like the tape merges of tuplesort. Ie,
keep one record from each subplan in the heap at all times. So the output
would be sorted if the inputs from each subplan were sorted by the same key as
the heap.

Actually I think it would likely just be a regular Append node with some
additional fields set. If those fields aren't set then it just behaves like
the current Append node. If they are then it does this merge-append behaviour.

The executor changes actually look pretty straightforward. The hard part is in
planning it. Since we really want to be able to handle having an index on some
partitions and not others (such as an empty parent table) we need to consider
adding a sort node for partitions which have fewer indexes.

So I think we should generate the union of available paths from the subrels.
Then generate an append path for each path in the union using the best subpath
for each subrel with a matching pathkey list (actually two, one based on
startup and one based on total cost). If any given subrel can't generate a
matching subpath then pick the best subpath and generate a sort path.

This requires treating columns of subrels as equivalent to the columns of the
parent. Offhand I think that's theoretically ok since they'll never be
available except where they are in fact equivalent, but I'm not too familiar
with equivalence classes. There are a few comments indicating we don't
currently fully track columns of subrels of append rels in equivalence
classes. I'm not sure what the consequences of adding those columns as full
members of the equivalence classes would be.

--
Gregory Stark
EnterpriseDB http://www.enterprisedb.com