Horton

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

Tom Lane <tgl@sss.pgh.pa.us>

View thread View on postgr.es
From: Tom Lane <tgl@sss.pgh.pa.us>
To: Robert Haas <robertmhaas@gmail.com>
Cc: Ashutosh Bapat <ashutosh.bapat@enterprisedb.com>, Rajkumar Raghuwanshi <rajkumar.raghuwanshi@enterprisedb.com>, pgsql-hackers <pgsql-hackers@postgresql.org>
Date: 2016-11-14T14:57:37Z
Lists: pgsql-hackers 
Robert Haas <robertmhaas@gmail.com> writes:
> On Fri, Nov 4, 2016 at 6:52 AM, Ashutosh Bapat
> <ashutosh.bapat@enterprisedb.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

Commits

  1. Basic partition-wise join functionality.

  2. Assorted preparatory refactoring for partition-wise join.

  3. Teach adjust_appendrel_attrs(_multilevel) to do multiple translations.

  4. Stamp 10beta2.

  5. Eat XIDs more efficiently in recovery TAP test.

  6. Abstract logic to allow for multiple kinds of child rels.

  7. Implement SortSupport for macaddr data type

  8. Attempt to stabilize grouping sets regression test plans.

  9. Teach xlogreader to follow timeline switches

  10. Don't scan partitioned tables.

  11. Fix grammar.

  12. postgres_fdw: Push down FULL JOINs with restriction clauses.

  13. Some preliminary refactoring towards partitionwise join.

  14. contrib/amcheck needs RecentGlobalXmin to be PGDLLIMPORT'ified.

  15. Print test parameters like "foo: 123", and results like "foo = 123".