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

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