Amit Langote is working on supporting declarative partitioning in PostgreSQL [1]. I have started working on supporting partition-wise join. This mail describes very high level design and some insight into the performance improvements.
An equi-join between two partitioned tables can be broken down into pair-wise join between their partitions. This technique is called partition-wise join. Partition-wise joins between similarly partitioned tables with equi-join condition can be efficient because [2]
1. Each provably non-empty partition-wise join smaller. All such joins collectively might be more efficient than the join between their parent.
2. Such joins are able to exploit properties of partitions like indexes, their storage etc.
3. An N-way partition-wise join may have different efficient join orders compared to the efficient join order between the parent tables.
A partition-wise join is processed in following stages [2], [3].
1. Applicability testing: This phase checks if the join conditions match the partitioning scheme. A partition-wise join is efficient if there is an equi-join on the partition keys. E.g. join between tables R and S partitioned by columns a and b resp. can be broken down into partition-wise joins if there exists a join condition is R.a = S.b. Or in other words the number of provably non-empty partition-wise joins is O(N) where N is the number of partitions.
2. Matching: This phase determines which joins between the partitions of R and S can potentially produce tuples in the join and prunes empty joins between partitions.
3. Clustering: This phase aims at reducing the number of partition-wise joins by clubbing together partitions from joining relations. E.g. clubbing multiple partitions from either of the partitioned relations which can join to a single partition from the other partitioned relation.
4. Path/plan creation: This phase creates multiple paths for each partition-wise join. It also creates Append path/s representing the union of partition-wise joins.
The work here focuses on a subset of use-cases discussed in [2]. It only considers partition-wise join for join between similarly partitioned tables with same number of partitions with same properties, thus producing at most as many partition-wise joins as there are partitions. It should be possible to apply partition-wise join technique (with some special handling for OUTER joins) if both relations have some extra partitions with non-overlapping partition conditions, apart from the matching partitions. But I am not planning to implement this optimization in the first cut.
The attached patch is a POC implementation of partition-wise join. It is is based on the set of patches posted on 23rd May 2016 by Amit Langote for declarative partitioning. The patch gives an idea about the approach used. It has several TODOs, which I am working on.
Attached is a script with output which measures potential performance improvement because of partition-wise join. The script uses a GUC enable_partition_wise_join to disable/enable this feature for performance measurement. The scripts measures performance improvement of a join between two tables partitioned by range on integer column. Each table contains 50K rows. Each table has an integer and a varchar column. It shows around 10-15% reduction in execution time when partition-wise join is used. Accompanied with parallel query and FDWs, it opens up avenues for further improvements for joins between partitioned tables.
[1].
https://www.postgresql.org/message-id/55D3093C.5010800@lab.ntt.co.jp[2].
https://users.cs.duke.edu/~shivnath/papers/sigmod295-herodotou.pdf[3].
https://users.cs.duke.edu/~shivnath/tmp/paqo_draft.pdf--
Best Wishes,
Ashutosh Bapat
EnterpriseDB Corporation
The Postgres Database Company