Horton

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

Robert Haas <robertmhaas@gmail.com>

View thread View on postgr.es
From: Robert Haas <robertmhaas@gmail.com>
To: Ashutosh Bapat <ashutosh.bapat@enterprisedb.com>
Cc: Rajkumar Raghuwanshi <rajkumar.raghuwanshi@enterprisedb.com>, pgsql-hackers <pgsql-hackers@postgresql.org>
Date: 2016-11-14T14:45:29Z
Lists: pgsql-hackers 
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.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

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".