Re: [HACKERS] expanding inheritance in partition bound order

On 2017/08/31 4:45, Robert Haas wrote:
> On Wed, Aug 30, 2017 at 12:47 PM, Ashutosh Bapat
> <ashutosh.bapat@enterprisedb.com> wrote:
>> +1. I think we should just pull out the OIDs from partition descriptor.
> 
> Like this?  The first patch refactors the expansion of a single child
> out into a separate function, and the second patch implements EIBO on
> top of it.
> 
> I realized while doing this that we really want to expand the
> partitioning hierarchy depth-first, not breadth-first.  For some
> things, like partition-wise join in the case where all bounds match
> exactly, we really only need a *predictable* ordering that will be the
> same for two equi-partitioned tables.  A breadth-first expansion will
> give us that.  But it's not actually in bound order.  For example:
> 
> create table foo (a int, b text) partition by list (a);
> create table foo1 partition of foo for values in (2);
> create table foo2 partition of foo for values in (1) partition by range (b);
> create table foo2a partition of foo2 for values from ('b') to ('c');
> create table foo2b partition of foo2 for values from ('a') to ('b');
> create table foo3 partition of foo for values in (3);
> 
> The correct bound-order expansion of this is foo2b - foo2a - foo1 -
> foo3, which is indeed what you get with the attached patch.  But if we
> did the expansion in breadth-first fashion, we'd get foo1 - foo3 -
> foo2a, foo2b, which is, well, not in bound order.  If the idea is that
> you see a > 2 and rule out all partitions that appear before the first
> one with an a-value >= 2, it's not going to work.

I think, overall, this might be a good idea.  Thanks for working on it.

The patches I posted in the "path toward faster partition pruning" achieve
the same end result as your patch that the leaf partitions appear in the
partition bound order in the Append path for a partitioned table.  It
achieves that result in a somewhat different way, but let's forget about
that for a moment.  One thing the patch on that thread didn't achieve
though is getting the leaf partitions in the same (partition bound) order
in the ModifyTable path for UPDATE/DELETE, because inheritance_planner()
path is not modified in a suitable way (in fact, I'm afraid that there
might be a deadlock bug lurking there, which I must address).

Your patch, OTOH, achieves the same order in both cases, which seems
desirable.

> Mind you, that idea has some problems anyway in the face of default
> partitions, null partitions, and list partitions which accept
> non-contiguous values (e.g. one partition for 1, 3, 5; another for 2,
> 4, 6).  We might need to mark the PartitionDesc to indicate whether
> PartitionDesc-order is in fact bound-order in a particular instance,
> or something like that.

ISTM, the primary motivation for the EIBO patch at this point is to get
the partitions ordered in a predictable manner so that the partition-wise
join patch and update partition key patches could implement certain logic
using O (n) algorithm rather than an O (n^2) one.  Neither of them depend
on the actual order in the sense of, say, sticking a PathKey to the
resulting Append.  Perhaps, the patch to"Make the optimiser aware of
partitions ordering" [1] will have to consider this somehow; maybe by
limiting its scope to only the cases where the root partitioned table is
range partitioned.

Thanks,
Amit

[1] https://commitfest.postgresql.org/14/1093/