Re: Partition-wise join for join between (declaratively) partitioned tables

Robert Haas <robertmhaas(at)gmail(dot)com> writes:
> On Fri, Nov 4, 2016 at 6:52 AM, Ashutosh Bapat
> <ashutosh(dot)bapat(at)enterprisedb(dot)com> wrote:
>> Costing PartitionJoinPath needs more thought so that we don't end up
>> with bad overall plans. Here's an idea. Partition-wise joins are
>> better compared to the unpartitioned ones, because of the smaller
>> sizes of partitions. If we think of join as O(MN) operation where M
>> and N are sizes of unpartitioned tables being joined, partition-wise
>> join computes P joins each with average O(M/P * N/P) order where P is
>> the number of partitions, which is still O(MN) with constant factor
>> reduced by P times. I think, we need to apply similar logic to
>> costing. Let's say cost of a join is J(M, N) = S (M, N) + R (M, N)
>> where S and R are setup cost and joining cost (for M, N rows) resp.
>> Cost of partition-wise join would be P * J(M/P, N/P) = P * S(M/P, N/P)
>> + P * R(M/P, N/P). Each of the join methods will have different S and
>> R functions and may not be linear on the number of rows. So,
>> PartitionJoinPath costs are obtained from corresponding regular path
>> costs subjected to above transformation. This way, we will be
>> protected from choosing a PartitionJoinPath when it's not optimal.

> I'm not sure that I really understand the stuff with big-O notation
> and M, N, and P. But I think what you are saying is that we could
> cost a PartitionJoinPath by costing some of the partitions (it might
> be a good idea to choose the biggest ones) and assuming the cost for
> the remaining ones will be roughly proportional. That does seem like
> a reasonable strategy to me.

I'm not sure to what extent the above argument depends on the assumption
that join is O(MN), but I will point out that in no case of practical
interest for large tables is it actually O(MN). That would be true
only for the stupidest possible nested-loop join method. It would be
wise to convince ourselves that the argument holds for more realistic
big-O costs, eg hash join is more like O(M+N) if all goes well.

regards, tom lane