Re: expanding inheritance in partition bound order

On Wed, Aug 30, 2017 at 8:33 AM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
> On Tue, Aug 29, 2017 at 10:36 PM, Amit Langote
> <Langote_Amit_f8(at)lab(dot)ntt(dot)co(dot)jp> wrote:
>>> I keep having the feeling that this is a big patch with a small patch
>>> struggling to get out. Is it really necessary to change
>>> RelationGetPartitionDispatchInfo so much or could you just do a really
>>> minimal surgery to remove the code that sets the stuff we don't need?
>>> Like this:
>>
>> Sure, done in the attached updated patch.
>
> On first glance, that looks pretty good. I'll have a deeper look
> tomorrow.
>

In one of your earlier mails on this thread, you had described how
expand_inherited_rtentry() would look like as

-- quote --
1. Calling find_all_inheritors with a new only-lock-the-partitions
flag. This should result in locking all partitioned tables in the
inheritance hierarchy in breadth-first, low-OID-first order. (When
the only-lock-the-partitions isn't specified, all partitioned tables
should still be locked before any unpartitioned tables, so that the
locking order in that case is consistent with what we do here.)

2. Iterate over the partitioned tables identified in step 1 in the
order in which they were returned. For each one:
- Decide which children can be pruned.
- Lock the unpruned, non-partitioned children in low-OID-first order.

3. Make another pass over the inheritance hierarchy, starting at the
root. Traverse the whole hierarchy in breadth-first in *bound* order.
Add RTEs and AppendRelInfos as we go -- these will have rte->inh =
true for partitioned tables and rte->inh = false for leaf partitions.

-- quote ends --

Amit's patches seem to be addressing the third point here. But the
expansion is not happening in breadth-first manner. We are expanding
all the partitioned partitions first and then leaf partitions. So
that's not exactly "breadth-first".

I tried to rebase first patch from partition-wise join patchset [1] on
top of these two patches. I am having hard time applying those
changes. The goal of the my patch is to expand the partitioned table
into an inheritance hierarchy which retains the partition hierarchy.
For that to happen, we need to know which partition belongs to which
partitioned table in the partition hierarchy. PartitionDispatch array
provided by RelationGetPartitionDispatchInfo() provides me the parent
OIDs of partitioned parents but it doesn't do so for the leaf
partitions. So, I changed the signature of that function to return the
list of parent OIDs of leaf partitions. But for building
AppendRelInfos, child RTEs and child row marks, I need parent's RTI,
RTE and row marks, which are not available directly. Given parent's
OID, I need to search root->parse->rtable to find its RTE, RTI and
then using RTI I can find rowmarks. But that seems to defeat the
purpose why partition-wise join needs EIBO i.e. to avoid O(n ^2) loop
in build_simple_rel(). For eliminating that loop we are introducing
another O(n^2) loop in expand_inherited_rtentry(). Even without
considering O(n^2) complexity this looks ugly.

A better way for translating partition hierarchy into inheritance
hierarchy may be to expand all partitions (partitioned or leaf) of a
given parent at a time in breadth-first manner. This allows us to
create child RTE, AppendRelInfo, rowmarks while we have corresponding
parent structures at hand, rather than searching for those. This would
still satisfy Amit Khandekar's requirement to expand leaf partitions
in the same order as their OIDs would be returned by
RelationGetPartitionDispatchInfo(). I have a feeling that, if we go
that route, we will replace almost all the changes that Amit Langote's
patches do to expand_inherited_rtentry().

--
Best Wishes,
Ashutosh Bapat
EnterpriseDB Corporation
The Postgres Database Company