PFA the patches rebased on the latest sources. There are also fixes
for some of the crashes and bugs reported. I haven't yet included the
testcase patch in the main patchset.
On Mon, Aug 28, 2017 at 12:44 PM, Rajkumar Raghuwanshi
<rajkumar.raghuwan...@enterprisedb.com> wrote:
> On Mon, Aug 21, 2017 at 12:43 PM, Ashutosh Bapat
> <ashutosh.ba...@enterprisedb.com> wrote:
>>
>> TODOs
>> -----------
>> 1. Add tests for advanced partition matching algorithm
>
>
> Hi Ashutosh,
>
> I have applied all partition-wise-join patches (v26) and tested feature. I
> have modified partition_join.sql file and added extra test cases to test
> partition matching.
>
> Attaching WIP test case patch which as of now have some server crashes and a
> data corruptions issue which is commented in the file itself and need to be
> removed once issue got solved. Also some of queries is not picking or
> picking partition-wise-join as per expectation which may need some
> adjustment.
>
>
>
>
>
>
--
Best Wishes,
Ashutosh Bapat
EnterpriseDB Corporation
The Postgres Database Company
From 865242c79b56f021dc619bc028480097d11bb69a Mon Sep 17 00:00:00 2001
From: Ashutosh Bapat <ashutosh.ba...@enterprisedb.com>
Date: Thu, 6 Jul 2017 14:15:22 +0530
Subject: [PATCH 11/12] Modify bound comparision functions to accept members
of PartitionKey
Functions partition_bound_cmp(), partition_rbound_cmp() and
partition_rbound_datum_cmp() are required to merge partition bounds
from joining relations. While doing so, we do not have access to the
PartitionKey of either relations. So, modify these functions to accept
only required members of PartitionKey so that the functions can be
reused for merging bounds.
Ashutosh Bapat.
---
src/backend/catalog/partition.c | 76 ++++++++++++++++++++++-----------------
1 file changed, 44 insertions(+), 32 deletions(-)
diff --git a/src/backend/catalog/partition.c b/src/backend/catalog/partition.c
index 96a64ce..d42e1b5 100644
--- a/src/backend/catalog/partition.c
+++ b/src/backend/catalog/partition.c
@@ -126,15 +126,17 @@ static List *generate_partition_qual(Relation rel);
static PartitionRangeBound *make_one_range_bound(PartitionKey key, int index,
List *datums, bool lower);
-static int32 partition_rbound_cmp(PartitionKey key,
- Datum *datums1, PartitionRangeDatumKind *kind1,
- bool lower1, PartitionRangeBound *b2);
-static int32 partition_rbound_datum_cmp(PartitionKey key,
- Datum *rb_datums, PartitionRangeDatumKind *rb_kind,
+static int32 partition_rbound_cmp(int partnatts, FmgrInfo *partsupfunc,
+ Oid *partcollation, Datum *datums1,
+ PartitionRangeDatumKind *kind1, bool lower1,
+ PartitionRangeBound *b2);
+static int32 partition_rbound_datum_cmp(int partnatts, FmgrInfo *partsupfunc,
+ Oid *partcollation, Datum *rb_datums,
+ PartitionRangeDatumKind *rb_kind,
Datum *tuple_datums);
-static int32 partition_bound_cmp(PartitionKey key,
- PartitionBoundInfo boundinfo,
+static int32 partition_bound_cmp(int partnatts, FmgrInfo *partsupfunc,
+ Oid *partcollation, PartitionBoundInfo boundinfo,
int offset, void *probe, bool probe_is_bound);
static int partition_bound_bsearch(PartitionKey key,
PartitionBoundInfo boundinfo,
@@ -719,8 +721,9 @@ check_new_partition_bound(char *relname, Relation parent,
* First check if the resulting range would be empty with
* specified lower and upper bounds
*/
- if (partition_rbound_cmp(key, lower->datums, lower->kind, true,
- upper) >= 0)
+ if (partition_rbound_cmp(key->partnatts, key->partsupfunc,
+ key->partcollation, lower->datums,
+ lower->kind, true, upper) >= 0)
{
ereport(ERROR,
(errcode(ERRCODE_INVALID_OBJECT_DEFINITION),
@@ -771,9 +774,11 @@ check_new_partition_bound(char *relname, Relation parent,
{
int32 cmpval;
- cmpval = partition_bound_cmp(key, boundinfo,
- offset + 1, upper,
- true);
+ cmpval = partition_bound_cmp(key->partnatts,
+ key->partsupfunc,
+ key->partcollation,
+ boundinfo, offset + 1,
+ upper, true);
if (cmpval < 0)
{
/*
@@ -2138,7 +2143,9 @@ qsort_partition_rbound_cmp(const void *a, const void *b, void *arg)
PartitionRangeBound *b2 = (*(PartitionRangeBound *const *) b);
PartitionKey key = (PartitionKey) arg;
- return partition_rbound_cmp(key, b1->datums, b1->kind, b1->lower, b2);
+ return partition_rbound_cmp(key->partnatts, key->partsupfunc,
+ key->partcollation, b1->datums, b1->kind,
+ b1->lower, b2);
}
/*
@@ -2155,7 +2162,7 @@ qsort_partition_rbound_cmp(const void *a, const void *b, void *arg)
* two contiguous partitions.
*/
static int32
-partition_rbound_cmp(PartitionKey key,
+partition_rbound_cmp(int partnatts, FmgrInfo *partsupfunc, Oid *partcollation,
Datum *datums1, PartitionRangeDatumKind *kind1,
bool lower1, PartitionRangeBound *b2)
{
@@ -2165,7 +2172,7 @@ partition_rbound_cmp(PartitionKey key,
PartitionRangeDatumKind *kind2 = b2->kind;
bool lower2 = b2->lower;
- for (i = 0; i < key->partnatts; i++)
+ for (i = 0; i < partnatts; i++)
{
/*
* First, handle cases where the column is unbounded, which should not
@@ -2186,8 +2193,8 @@ partition_rbound_cmp(PartitionKey key,
*/
break;
- cmpval = DatumGetInt32(FunctionCall2Coll(&key->partsupfunc[i],
- key->partcollation[i],
+ cmpval = DatumGetInt32(FunctionCall2Coll(&partsupfunc[i],
+ partcollation[i],
datums1[i],
datums2[i]));
if (cmpval != 0)
@@ -2213,22 +2220,23 @@ partition_rbound_cmp(PartitionKey key,
* is <, =, or > partition key of tuple (tuple_datums)
*/
static int32
-partition_rbound_datum_cmp(PartitionKey key,
- Datum *rb_datums, PartitionRangeDatumKind *rb_kind,
+partition_rbound_datum_cmp(int partnatts, FmgrInfo *partsupfunc,
+ Oid *partcollation, Datum *rb_datums,
+ PartitionRangeDatumKind *rb_kind,
Datum *tuple_datums)
{
int i;
int32 cmpval = -1;
- for (i = 0; i < key->partnatts; i++)
+ for (i = 0; i < partnatts; i++)
{
if (rb_kind[i] == PARTITION_RANGE_DATUM_MINVALUE)
return -1;
else if (rb_kind[i] == PARTITION_RANGE_DATUM_MAXVALUE)
return 1;
- cmpval = DatumGetInt32(FunctionCall2Coll(&key->partsupfunc[i],
- key->partcollation[i],
+ cmpval = DatumGetInt32(FunctionCall2Coll(&partsupfunc[i],
+ partcollation[i],
rb_datums[i],
tuple_datums[i]));
if (cmpval != 0)
@@ -2245,17 +2253,18 @@ partition_rbound_datum_cmp(PartitionKey key,
* specified in *probe.
*/
static int32
-partition_bound_cmp(PartitionKey key, PartitionBoundInfo boundinfo,
- int offset, void *probe, bool probe_is_bound)
+partition_bound_cmp(int partnatts, FmgrInfo *partsupfunc, Oid *partcollation,
+ PartitionBoundInfo boundinfo, int offset, void *probe,
+ bool probe_is_bound)
{
Datum *bound_datums = boundinfo->datums[offset];
int32 cmpval = -1;
- switch (key->strategy)
+ switch (boundinfo->strategy)
{
case PARTITION_STRATEGY_LIST:
- cmpval = DatumGetInt32(FunctionCall2Coll(&key->partsupfunc[0],
- key->partcollation[0],
+ cmpval = DatumGetInt32(FunctionCall2Coll(&partsupfunc[0],
+ partcollation[0],
bound_datums[0],
*(Datum *) probe));
break;
@@ -2273,12 +2282,14 @@ partition_bound_cmp(PartitionKey key, PartitionBoundInfo boundinfo,
*/
bool lower = boundinfo->indexes[offset] < 0;
- cmpval = partition_rbound_cmp(key,
- bound_datums, kind, lower,
+ cmpval = partition_rbound_cmp(partnatts, partsupfunc,
+ partcollation, bound_datums,
+ kind, lower,
(PartitionRangeBound *) probe);
}
else
- cmpval = partition_rbound_datum_cmp(key,
+ cmpval = partition_rbound_datum_cmp(partnatts, partsupfunc,
+ partcollation,
bound_datums, kind,
(Datum *) probe);
break;
@@ -2286,7 +2297,7 @@ partition_bound_cmp(PartitionKey key, PartitionBoundInfo boundinfo,
default:
elog(ERROR, "unexpected partition strategy: %d",
- (int) key->strategy);
+ (int) boundinfo->strategy);
}
return cmpval;
@@ -2320,7 +2331,8 @@ partition_bound_bsearch(PartitionKey key, PartitionBoundInfo boundinfo,
int32 cmpval;
mid = (lo + hi + 1) / 2;
- cmpval = partition_bound_cmp(key, boundinfo, mid, probe,
+ cmpval = partition_bound_cmp(key->partnatts, key->partsupfunc,
+ key->partcollation, boundinfo, mid, probe,
probe_is_bound);
if (cmpval <= 0)
{
--
1.7.9.5
From 737299aa79cc5d8e9fbf825ef6396696c485031d Mon Sep 17 00:00:00 2001
From: Ashutosh Bapat <ashutosh.ba...@enterprisedb.com>
Date: Wed, 9 Aug 2017 12:30:34 +0530
Subject: [PATCH 12/12] WIP Partition-wise join for 1:1, 1:0, 0:1 partition
matching.
Earlier version of partition-wise join implementation allowed
partition-wise join between two relations with exactly same partition
bounds. This commit allows partition-wise join to be applied under
following conditions
1. the partition bounds of joining relations are such that rows from
given partition on one side join can join with rows from maximum one
partition on the other side i.e. bounds of a given partition on one
side match/overlap with those of maximum one partition on the other
side. If the mapping happens to be m:n where m > 1 or n > 1, we have
to gang multiple partition relations together into a single relation.
This means that we have to add simple relations during join
processing, something which is not supported right now. ALso, in such
a case, different pairs of joining relations can produce different
partition bounds for the same join relation, which again is not
supported right now.
2. For every partition on outer side that can contribute to the result
of an OUTER side, there exists at least one (taken along with item 1,
it means exactly one) matching partition on the inner side. To
support partition-wise join when the inner matching partition doesn't
exist, we have to add a dummy base relation corresponding to the
non-existent inner partition. We don't have support add base relations
during join processing.
This commit is not complete yet.
Ashutosh Bapat.
---
src/backend/catalog/partition.c | 1255 +++++++++++++++++++++++++++++++++
src/backend/optimizer/path/joinrels.c | 77 +-
src/backend/optimizer/util/relnode.c | 42 +-
src/include/catalog/partition.h | 6 +
4 files changed, 1349 insertions(+), 31 deletions(-)
diff --git a/src/backend/catalog/partition.c b/src/backend/catalog/partition.c
index d42e1b5..2d1a905 100644
--- a/src/backend/catalog/partition.c
+++ b/src/backend/catalog/partition.c
@@ -141,6 +141,38 @@ static int32 partition_bound_cmp(int partnatts, FmgrInfo *partsupfunc,
static int partition_bound_bsearch(PartitionKey key,
PartitionBoundInfo boundinfo,
void *probe, bool probe_is_bound, bool *is_equal);
+static PartitionBoundInfo partition_range_bounds_merge(int partnatts,
+ FmgrInfo *supfuncs, Oid *collations,
+ PartitionBoundInfo boundinfo1, int nparts1,
+ PartitionBoundInfo boundinfo2, int nparts2,
+ JoinType jointype, List **parts1, List **parts2);
+static PartitionBoundInfo partition_list_bounds_merge(int partnatts,
+ FmgrInfo *partsupfunc, Oid *collations,
+ PartitionBoundInfo boundinfo1, int nparts1,
+ PartitionBoundInfo boundinfo2, int nparts2,
+ JoinType jointype, List **parts1, List **parts2);
+static void generate_matching_part_pairs(int *mergemap1, int npart1,
+ int *mergemap2, int nparts2, JoinType jointype,
+ int nparts, List **parts1, List **parts2);
+static PartitionBoundInfo build_merged_partition_bounds(char strategy,
+ List *merged_datums, List *merged_indexes,
+ List *merged_contents, int null_index);
+static int map_and_merge_partitions(int *partmap1, int *mergemap1, int index1,
+ int *partmap2, int *mergemap2, int index2,
+ int *next_index);
+static int32 partition_range_bound_cmp(int partnatts, FmgrInfo *partsupfunc,
+ Oid *collations, PartitionRangeBound *bound1,
+ PartitionRangeBound *bound2);
+static int partition_range_cmp(int partnatts, FmgrInfo *supfuncs,
+ Oid *collations, PartitionRangeBound *lower_bound1,
+ PartitionRangeBound *upper_bound1,
+ PartitionRangeBound *lower_bound2,
+ PartitionRangeBound *upper_bound2, bool *overlap);
+static bool partition_range_merge_next_lb(int partnatts, FmgrInfo *supfuncs,
+ Oid *collations, Datum *next_lb_datums,
+ PartitionRangeDatumKind *next_lb_kind,
+ List **merged_datums, List **merged_kinds,
+ List **merged_indexes);
/*
* RelationBuildPartitionDesc
@@ -2348,3 +2380,1226 @@ partition_bound_bsearch(PartitionKey key, PartitionBoundInfo boundinfo,
return lo;
}
+
+/*
+ * Merge the given partition bounds.
+ *
+ * If given partition bounds can not be merged, return NULL.
+ *
+ * The function also returns two lists of partition indexes one for each of the
+ * joining relations. Both the lists contain the same number of elements. The
+ * partition indexes at the same positions in the list indicate partitions from
+ * each side to be joined and their position corresponds to the index of
+ * partition to which the results of the child-join belong in the partitioned
+ * join.
+ */
+extern PartitionBoundInfo
+partition_bounds_merge(int partnatts, FmgrInfo *partsupfunc, Oid *partcollation,
+ PartitionBoundInfo boundinfo1, int nparts1,
+ PartitionBoundInfo boundinfo2, int nparts2,
+ JoinType jointype, List **parts1, List **parts2)
+{
+ PartitionBoundInfo merged_bounds;
+ char strategy;
+
+ /* Bail out if partitioning strategies are different. */
+ if (boundinfo1->strategy != boundinfo2->strategy)
+ return NULL;
+
+ *parts1 = NIL;
+ *parts2 = NIL;
+ strategy = boundinfo1->strategy;
+ if (strategy == PARTITION_STRATEGY_LIST)
+ merged_bounds = partition_list_bounds_merge(partnatts, partsupfunc,
+ partcollation, boundinfo1,
+ nparts1, boundinfo2,
+ nparts2, jointype, parts1,
+ parts2);
+ else if (strategy == PARTITION_STRATEGY_RANGE)
+ merged_bounds = partition_range_bounds_merge(partnatts, partsupfunc,
+ partcollation, boundinfo1,
+ nparts1, boundinfo2,
+ nparts2, jointype, parts1,
+ parts2);
+ else
+ elog(ERROR, "unexpected partition strategy: %d", strategy);
+
+ Assert(merged_bounds || (*parts1 == NIL && *parts2 == NIL));
+ return merged_bounds;
+}
+
+/*
+ * partition_get_range_bounds
+ *
+ * Given the index of lower bound in datums array, return lower and upper
+ * bounds and the index of the partition with that lower bound.
+ */
+static int
+partition_get_range_bounds(PartitionBoundInfo bi, int lb_index,
+ PartitionRangeBound *lower,
+ PartitionRangeBound *upper)
+{
+ int part_index;
+
+ /* A lower bound should have at least one more bound after it. */
+ Assert(lb_index < bi->ndatums - 1);
+
+ /* The lower bound should correspond to a valid partition. */
+ part_index = bi->indexes[lb_index + 1];
+ Assert(part_index >= 0);
+
+ lower->kind = bi->kind[lb_index];
+ lower->datums = bi->datums[lb_index];
+ lower->lower = true;
+ upper->kind = bi->kind[lb_index + 1];
+ upper->datums = bi->datums[lb_index + 1];
+ upper->lower = false;
+
+ return part_index;
+}
+
+/*
+ * partition_range_get_next_lb_index
+ *
+ * Given the index of lower bound in datums array return the
+ * index of lower bound of the next partition. When the given index corresponds
+ * to the last partition, return number of datums (ndatums).
+ */
+static int
+partition_range_get_next_lb_index(PartitionBoundInfo bi, int lb_index)
+{
+ /* A lower bound should have at least one more bound after it. */
+ Assert(lb_index < bi->ndatums - 1);
+
+ /* The partition index corresponding to the upper bound should be valid. */
+ Assert(bi->indexes[lb_index + 1] >= 0);
+
+ /*
+ * If there are no bounds left beyond the upper bound, we have reached the
+ * last partition.
+ */
+ if (lb_index + 2 < bi->ndatums)
+ {
+ /*
+ * If the bound next to the upper bound corresponds to no partition,
+ * that's the next lower bound of the next partition. Otherwise, the
+ * current upper bound is the lower bound of the next partition.
+ */
+ if (bi->indexes[lb_index + 2] < 0)
+ return lb_index + 2;
+ else
+ return lb_index + 1;
+ }
+ else
+ return bi->ndatums;
+}
+
+static int32
+partition_range_bound_cmp(int partnatts, FmgrInfo *partsupfunc, Oid *collations,
+ PartitionRangeBound *bound1,
+ PartitionRangeBound *bound2)
+{
+ return partition_rbound_cmp(partnatts, partsupfunc, collations,
+ bound1->datums, bound1->kind, bound1->lower,
+ bound2);
+}
+
+/*
+ * partition_range_cmp
+ *
+ * Compare the bounds of two range partitions and return <, = or > 0, if the
+ * first partition's upper bound is lower than, equal to or higher than the
+ * second partition's upper bound resp.
+ *
+ * Also, set overlaps to true, if the ranges overlap, otherwise set it to
+ * false.
+ */
+static int
+partition_range_cmp(int partnatts, FmgrInfo *supfuncs, Oid *collations,
+ PartitionRangeBound *lower_bound1,
+ PartitionRangeBound *upper_bound1,
+ PartitionRangeBound *lower_bound2,
+ PartitionRangeBound *upper_bound2, bool *overlap)
+{
+ /*
+ * Compare upper bound of the first partition with the lower bound of the
+ * second and vice-versa. If lower bound is higher than the upper bound,
+ * the partitions are not overlapping. All other cases indicate overlapping
+ * partitions.
+ * TODO: Add a testcase which has lower and upper bound matching exactly.
+ * Lower bound is inclusive and upper bound is exclusive, so even if the
+ * datums match, the bounds do not match exactly.
+ */
+ if (partition_range_bound_cmp(partnatts, supfuncs, collations,
+ lower_bound1, upper_bound2) > 0)
+ {
+ *overlap = false;
+ return 1;
+ }
+ else if (partition_range_bound_cmp(partnatts, supfuncs, collations,
+ lower_bound2, upper_bound1) > 0)
+ {
+ *overlap = false;
+ return -1;
+ }
+ else
+ {
+ *overlap = true;
+ return partition_range_bound_cmp(partnatts, supfuncs, collations,
+ upper_bound1, upper_bound2);
+ }
+}
+
+/*
+ * partition_range_merge
+ *
+ * Merge the partition bounds of given two partitions such that the join
+ * between the given two partitions fits merged bounds.
+ *
+ * "merged_upper" will be set to one of the given upper bounds and
+ * "merged_lower" will be set to one of the given lower bounds.
+ */
+static void
+partition_range_merge(int partnatts, FmgrInfo *supfuncs,
+ Oid *collations, JoinType jointype,
+ PartitionRangeBound *left_lb,
+ PartitionRangeBound *left_ub,
+ PartitionRangeBound *right_lb,
+ PartitionRangeBound *right_ub,
+ PartitionRangeBound **merged_lb,
+ PartitionRangeBound **merged_ub)
+{
+ /*
+ * An outer join will have all the rows from the outer side, so merged
+ * bounds will be same as the outer bounds. An inner join will have rows
+ * that fit both the bounds, thus lower merged bound will be higher of two
+ * lower bounds and upper merged bound will be lower of the two upper
+ * bounds.
+ */
+ switch (jointype)
+ {
+ case JOIN_LEFT:
+ case JOIN_ANTI:
+ *merged_ub = left_ub;
+ *merged_lb = left_lb;
+ break;
+
+ case JOIN_RIGHT:
+ *merged_ub = right_ub;
+ *merged_lb = right_lb;
+ break;
+
+ case JOIN_INNER:
+ case JOIN_SEMI:
+ if (partition_range_bound_cmp(partnatts, supfuncs, collations,
+ left_ub, right_ub) < 0)
+ *merged_ub = left_ub;
+ else
+ *merged_ub = right_ub;
+
+ if (partition_range_bound_cmp(partnatts, supfuncs, collations,
+ left_lb, right_lb) > 0)
+ *merged_lb = left_lb;
+ else
+ *merged_lb = right_lb;
+ break;
+
+ case JOIN_FULL:
+ if (partition_range_bound_cmp(partnatts, supfuncs, collations,
+ left_ub, right_ub) > 0)
+ *merged_ub = left_ub;
+ else
+ *merged_ub = right_ub;
+
+ if (partition_range_bound_cmp(partnatts, supfuncs, collations,
+ left_lb, right_lb) < 0)
+ *merged_lb = left_lb;
+ else
+ *merged_lb = right_lb;
+ break;
+
+ default:
+ elog(ERROR, "Unexpected join type %d", jointype);
+ }
+
+ return;
+}
+
+/*
+ * Add the lower bound of the next range to the list of bounds, if the lower
+ * bound is higher or equal to the previous upper bound. If successful return
+ * true, otherwise false.
+ */
+static bool
+partition_range_merge_next_lb(int partnatts, FmgrInfo *supfuncs,
+ Oid *collations, Datum *next_lb_datums,
+ PartitionRangeDatumKind *next_lb_kind,
+ List **merged_datums, List **merged_kinds,
+ List **merged_indexes)
+{
+ int cmpval;
+
+ if (!*merged_datums)
+ {
+ Assert(!*merged_kinds && !*merged_indexes);
+ cmpval = 1;
+ }
+ else
+ {
+ PartitionRangeBound prev_ub;
+
+ prev_ub.datums = llast(*merged_datums);
+ prev_ub.kind = llast(*merged_kinds);
+ prev_ub.lower = false;
+
+ /*
+ * TODO: explain why do we pass lower to be false for the next lower
+ * bound.
+ */
+ cmpval = partition_rbound_cmp(partnatts, supfuncs, collations,
+ next_lb_datums, next_lb_kind, false,
+ &prev_ub);
+ }
+
+ /*
+ * The lower bound is lower than the last upper bound, thus does not fit
+ * the bounds created so far and hence can not be merged with the existing
+ * bounds.
+ */
+ if (cmpval < 0)
+ return false;
+
+ /*
+ * Add bounds of the new merged partition. If the next lower bound is
+ * higher than the last upper bound, add new range with index
+ * corresponding to the lower bound as -1. If the merged lower bound
+ * is same as the last merged upper bound, the last upper bound will be
+ * reused as the lower bound of the next range.
+ */
+ if (cmpval > 0)
+ {
+ *merged_datums = lappend(*merged_datums, next_lb_datums);
+ *merged_kinds = lappend(*merged_kinds, next_lb_kind);
+ *merged_indexes = lappend_int(*merged_indexes, -1);
+ }
+
+ return true;
+}
+
+/*
+ * Merge given two range partition bounds.
+ *
+ * Work horse function for partition_bounds_merge() for range partitioned
+ * tables.
+ *
+ * TODO: for an anti-join, the caller is supposed to send the outer relation as
+ * left relation. May be we should rename left and right as inner and outer. We
+ * don't need to handle RIGHT joins in this function, so renaming them as outer
+ * and inner is fine.
+ */
+static PartitionBoundInfo
+partition_range_bounds_merge(int partnatts, FmgrInfo *supfuncs, Oid *collations,
+ PartitionBoundInfo left_bi, int left_nparts,
+ PartitionBoundInfo right_bi, int right_nparts,
+ JoinType jointype, List **left_parts, List **right_parts)
+{
+ int *left_pmap;
+ int *left_mmap;
+ int *right_pmap;
+ int *right_mmap;
+ int cnt1;
+ int cnt2;
+ int left_part;
+ int right_part;
+ PartitionBoundInfo merged_bounds = NULL;
+ bool merged = true; /* By default we ranges are merge-able. */
+ int left_lb_index;
+ int right_lb_index;
+ int next_index;
+ int cmpval;
+ List *merged_datums = NIL;
+ List *merged_indexes = NIL;
+ List *merged_kinds = NIL;
+
+ Assert(left_bi->strategy == right_bi->strategy &&
+ left_bi->strategy == PARTITION_STRATEGY_RANGE);
+
+ *left_parts = NIL;
+ *right_parts = NIL;
+
+ /* Allocate and initialize partition maps. */
+ left_pmap = (int *) palloc(sizeof(int) * left_nparts);
+ left_mmap = (int *) palloc(sizeof(int) * left_nparts);
+ right_pmap = (int *) palloc(sizeof(int) * right_nparts);
+ right_mmap = (int *) palloc(sizeof(int) * right_nparts);
+
+ for (cnt1 = 0; cnt1 < left_nparts; cnt1++)
+ {
+ left_pmap[cnt1] = -1;
+ left_mmap[cnt1] = -1;
+ }
+ for (cnt2 = 0; cnt2 < right_nparts; cnt2++)
+ {
+ right_pmap[cnt2] = -1;
+ right_mmap[cnt2] = -1;
+ }
+
+ left_lb_index = 0;
+ right_lb_index = 0;
+ next_index = 0;
+ while (left_lb_index < left_bi->ndatums &&
+ right_lb_index < right_bi->ndatums)
+ {
+ PartitionRangeBound left_lb;
+ PartitionRangeBound left_ub;
+ PartitionRangeBound right_lb;
+ PartitionRangeBound right_ub;
+ PartitionRangeBound *merged_lb = NULL;
+ PartitionRangeBound *merged_ub = NULL;
+ int merged_index = -1;
+ bool overlap;
+
+ /* Get the range bounds of the next partition. */
+ left_part = partition_get_range_bounds(left_bi, left_lb_index,
+ &left_lb, &left_ub);
+ right_part = partition_get_range_bounds(right_bi, right_lb_index,
+ &right_lb, &right_ub);
+
+ cmpval = partition_range_cmp(partnatts, supfuncs, collations,
+ &left_lb, &left_ub, &right_lb, &right_ub,
+ &overlap);
+
+ if (overlap)
+ {
+ /* Overlapping ranges, try merging. */
+ partition_range_merge(partnatts, supfuncs, collations, jointype,
+ &left_lb, &left_ub, &right_lb, &right_ub,
+ &merged_lb, &merged_ub);
+ merged_index = map_and_merge_partitions(left_pmap, left_mmap,
+ left_part, right_pmap,
+ right_mmap, right_part,
+ &next_index);
+
+ if (merged_index < 0)
+ {
+ merged = false;
+ break;
+ }
+ }
+
+ if (cmpval == 0)
+ {
+ Assert(overlap);
+
+ /* Move to the next pair of partitions. */
+ left_lb_index = partition_range_get_next_lb_index(left_bi,
+ left_lb_index);
+ right_lb_index = partition_range_get_next_lb_index(right_bi,
+ right_lb_index);
+ }
+ else if (cmpval < 0)
+ {
+ /*
+ * If the partition on the left was not mapped to any partition on
+ * the right. Any row from that partition will not have a matching
+ * row from the other relation. So the partition will be part of
+ * the join if it's an anti-join or the left side is the outer
+ * side.
+ */
+ if (jointype == JOIN_INNER || jointype == JOIN_SEMI ||
+ jointype == JOIN_RIGHT)
+ {
+ /* Nothing to do. */
+ }
+ else if (jointype == JOIN_LEFT || jointype == JOIN_FULL ||
+ jointype == JOIN_ANTI)
+ {
+ if (left_mmap[left_part] < 0)
+ {
+ left_mmap[left_part] = next_index++;
+ merged_index = left_mmap[left_part];
+ merged_lb = &left_lb;
+ merged_ub = &left_ub;
+ }
+ }
+ else
+ {
+ /* Don't know what to do with other join types. Bail out. */
+ merged = false;
+ }
+
+ /* Move to the next partition on the left side. */
+ left_lb_index = partition_range_get_next_lb_index(left_bi,
+ left_lb_index);
+ }
+ else
+ {
+ Assert(cmpval > 0);
+
+ /*
+ * If the partition on the right was not mapped to any partition on
+ * the left. Any row from that partition will not have a matching
+ * row from the other relation. So the partition will be part of
+ * the join if the right side is the outer side.
+ */
+ if (jointype == JOIN_INNER || jointype == JOIN_SEMI ||
+ jointype == JOIN_LEFT || jointype == JOIN_ANTI)
+ {
+ /* Nothing to do. */
+ }
+ else if (jointype == JOIN_RIGHT || jointype == JOIN_FULL)
+ {
+ if (right_mmap[right_part] < 0)
+ {
+ right_mmap[right_part] = next_index++;
+ merged_index = right_mmap[right_part];
+ merged_lb = &right_lb;
+ merged_ub = &right_ub;
+ }
+ }
+ else
+ {
+ /* Don't know what to do with other join types. Bail out. */
+ merged = false;
+ }
+
+ /* Move to the next partition on the right side. */
+ right_lb_index = partition_range_get_next_lb_index(right_bi,
+ right_lb_index);
+ }
+
+ if (!merged)
+ break;
+
+ /* A skipped partition is not added to merged bounds. */
+ if (merged_index < 0)
+ continue;
+
+ /*
+ * We have a valid partition index for the next partition of join. The
+ * partition should have valid range.
+ */
+ Assert(merged_lb && merged_ub);
+
+ /* Try merging merged lower bound with the last upper bound. */
+ merged = partition_range_merge_next_lb(partnatts, supfuncs,
+ collations, merged_lb->datums,
+ merged_lb->kind, &merged_datums,
+ &merged_kinds, &merged_indexes);
+ if (merged)
+ {
+ /* Add upper bound with the merged partition index. */
+ merged_datums = lappend(merged_datums, merged_ub->datums);
+ merged_kinds = lappend(merged_kinds, merged_ub->kind);
+ merged_indexes = lappend_int(merged_indexes, merged_index);
+ }
+ else
+ break;
+ }
+
+ /*
+ * We will run the above loop till we exhaust ranges of at least one side
+ * unless we failed to merge the ranges.
+ */
+ Assert (!merged || (left_lb_index >= left_bi->ndatums ||
+ right_lb_index >= right_bi->ndatums));
+
+ /*
+ * Handle any remaining partition bounds. If remaining partitions fall on
+ * the inner side of the join, none of the rows in those partition are
+ * going to be joined with any row on the outer side and hence those
+ * partitions will not be part of the join result. Hence only consider the
+ * remaining partitions on the outer side of the join.
+ */
+ if (merged &&
+ ((left_lb_index < left_bi->ndatums &&
+ (jointype == JOIN_LEFT || jointype == JOIN_FULL ||
+ jointype == JOIN_ANTI)) ||
+ (right_lb_index < right_bi->ndatums &&
+ (jointype == JOIN_RIGHT || jointype == JOIN_FULL))))
+ {
+ int bound_index = -1;
+ PartitionBoundInfo rem_bi = NULL;
+ int *mmap = NULL;
+ int part_index;
+
+ if (left_lb_index < left_bi->ndatums)
+ {
+ Assert(jointype == JOIN_LEFT || jointype == JOIN_FULL ||
+ jointype == JOIN_ANTI);
+ bound_index = left_lb_index;
+ rem_bi = left_bi;
+ mmap = left_mmap;
+ part_index = left_part;
+ }
+ else if (right_lb_index < right_bi->ndatums)
+ {
+ Assert(jointype == JOIN_RIGHT || jointype == JOIN_FULL);
+ bound_index = right_lb_index;
+ rem_bi = right_bi;
+ mmap = right_mmap;
+ part_index = right_part;
+ }
+ Assert((bound_index >= 0 && bound_index < rem_bi->ndatums) &&
+ rem_bi && mmap && part_index >= 0);
+
+ /*
+ * If the partition corresponding to this lower bound has been already
+ * mapped to a merged partition, don't need to add it again. This may
+ * happen if the range of the last partition on the inner side overlaps
+ * with this partition's range and has upper bound lesser than upper
+ * bound of this partition's range.
+ */
+ if (mmap[part_index] >= 0)
+ bound_index = partition_range_get_next_lb_index(rem_bi, bound_index);
+
+ /*
+ * Merge lower bound of the next range with the upper bound of last
+ * range.
+ */
+ if (bound_index < rem_bi->ndatums)
+ merged = partition_range_merge_next_lb(partnatts, supfuncs,
+ collations,
+ rem_bi->datums[bound_index],
+ rem_bi->kind[bound_index],
+ &merged_datums,
+ &merged_kinds,
+ &merged_indexes);
+
+ /*
+ * Rest of the bounds correspond to valid ranges so add them after
+ * remapping their partitions as required.
+ */
+ for (bound_index++; merged && bound_index < rem_bi->ndatums;
+ bound_index++)
+ {
+ Datum *datums = rem_bi->datums[bound_index];
+ int index = rem_bi->indexes[bound_index];
+ int part_index;
+
+ /*
+ * Add lower bounds with partition index -1 and assign a new
+ * partition index to the upper bounds.
+ */
+ if (index < 0)
+ part_index = index;
+ else
+ {
+ if (mmap[index] < 0)
+ mmap[index] = next_index++;
+ part_index = mmap[index];
+ }
+
+ merged_indexes = lappend_int(merged_indexes, part_index);
+ merged_datums = lappend(merged_datums, datums);
+ merged_kinds = lappend(merged_kinds,
+ rem_bi->kind[bound_index]);
+ }
+ }
+
+ /* Create PartitionBoundInfo */
+ if (merged)
+ {
+ /* Use maps to match partition from the joining relations. */
+ generate_matching_part_pairs(left_mmap, left_nparts, right_mmap,
+ right_nparts, jointype, next_index,
+ left_parts, right_parts);
+
+ /* Craft a PartitionBoundInfo to return. */
+ if (*left_parts && *right_parts)
+ {
+ Assert(list_length(*left_parts) == list_length(*right_parts));
+ Assert(list_length(*left_parts) == next_index);
+ merged_bounds = build_merged_partition_bounds(left_bi->strategy,
+ merged_datums,
+ merged_indexes,
+ merged_kinds,
+ -1);
+ }
+ }
+
+ list_free(merged_datums);
+ list_free(merged_indexes);
+ pfree(left_pmap);
+ pfree(right_pmap);
+ pfree(left_mmap);
+ pfree(right_mmap);
+
+ /* Free any memory we used in this function. */
+ return merged_bounds;
+}
+
+/*
+ * partition_bounds_merge()'s arm for list partitioned tables.
+ *
+ * The function builds the maps of matching partitions from either relation. It
+ * builds the list of partition key values that may appear in the join result
+ * alongwith the list of indexes of partitions of join to which those values
+ * belong. It then crafts a PartitionBoundInfo structure representing the
+ * partition bounds of the join result.
+ */
+static PartitionBoundInfo
+partition_list_bounds_merge(int partnatts, FmgrInfo *partsupfunc,
+ Oid *partcollation, PartitionBoundInfo left_bi,
+ int left_nparts, PartitionBoundInfo right_bi,
+ int right_nparts, JoinType jointype, List **left_parts,
+ List **right_parts)
+{
+ int *left_pmap; /* left to right partition map */
+ int *left_mmap; /* left to merged partition map */
+ int *right_pmap; /* right to left partition map */
+ int *right_mmap; /* right to merged partition map */
+ int cntl;
+ int cntr;
+ bool merged = true;
+ List *merged_datums = NIL;
+ List *merged_indexes = NIL;
+ int next_index = 0;
+ int null_index;
+ PartitionBoundInfo merged_bounds = NULL;
+ int *left_indexes = left_bi->indexes;
+ int *right_indexes = right_bi->indexes;
+ int left_ni = left_bi->null_index;
+ int right_ni = right_bi->null_index;
+
+ Assert(left_bi->strategy == right_bi->strategy &&
+ left_bi->strategy == PARTITION_STRATEGY_LIST);
+
+ /* List partitions do not require unbounded ranges. */
+ Assert(!left_bi->kind && !right_bi->kind);
+
+ /* Allocate and initialize partition maps. */
+ left_pmap = (int *) palloc(sizeof(int) * left_nparts);
+ left_mmap = (int *) palloc(sizeof(int) * left_nparts);
+ right_pmap = (int *) palloc(sizeof(int) * right_nparts);
+ right_mmap = (int *) palloc(sizeof(int) * right_nparts);
+
+ /* Initialize partition maps. */
+ for (cntl = 0; cntl < left_nparts; cntl++)
+ {
+ left_pmap[cntl] = -1;
+ left_mmap[cntl] = -1;
+ }
+ for (cntr = 0; cntr < right_nparts; cntr++)
+ {
+ right_pmap[cntr] = -1;
+ right_mmap[cntr] = -1;
+ }
+
+ cntl = cntr = 0;
+ while (cntl < left_bi->ndatums && cntr < right_bi->ndatums)
+ {
+ Datum *ldatums = left_bi->datums[cntl];
+ Datum *rdatums = right_bi->datums[cntr];
+ int l_index = left_indexes[cntl];
+ int r_index = right_indexes[cntr];
+ int cmpval;
+ int merged_index;
+ Datum *merged_datum;
+
+ /* Every list datum should map to a valid partition index. */
+ Assert(l_index >= 0 && r_index >= 0);
+
+ cmpval = DatumGetInt32(FunctionCall2Coll(&partsupfunc[0],
+ partcollation[0], ldatums[0],
+ rdatums[0]));
+ if (cmpval == 0)
+ {
+ /*
+ * Try matching partitions containing the matching datums. If
+ * successful, add the datum to the merged bounds with index of
+ * merged partition containing it.
+ */
+ merged_datum = ldatums;
+ merged_index = map_and_merge_partitions(left_pmap, left_mmap, l_index,
+ right_pmap, right_mmap, r_index,
+ &next_index);
+
+ if (merged_index < 0)
+ {
+ merged = false;
+ break;
+ }
+
+ /* Move to the next pair of bounds. */
+ cntl++;
+ cntr++;
+ }
+ else if (cmpval < 0)
+ {
+ /*
+ * This list datum is present in the left side but not the right
+ * side. So it will appear in the join when the left side is outer
+ * side.
+ */
+ if (jointype == JOIN_INNER || jointype == JOIN_RIGHT ||
+ jointype == JOIN_SEMI)
+ merged_index = -1;
+ else if (jointype == JOIN_LEFT || jointype == JOIN_FULL ||
+ jointype == JOIN_ANTI)
+ {
+ if (left_mmap[l_index] < 0)
+ left_mmap[l_index] = next_index++;
+ merged_index = left_mmap[l_index];
+ merged_datum = ldatums;
+ }
+ else
+ {
+ /* Don't know what to do with other join types. */
+ merged = false;
+ break;
+ }
+
+ /* Move to the next datum on the left side. */
+ cntl++;
+ }
+ else
+ {
+ Assert(cmpval > 0);
+
+ /*
+ * This list datum is present in the right side but not the left
+ * side. So it will appear in the join when the right side is outer
+ * side.
+ */
+ if (jointype == JOIN_INNER || jointype == JOIN_LEFT ||
+ jointype == JOIN_SEMI || jointype == JOIN_ANTI)
+ merged_index = -1;
+ else if (jointype == JOIN_RIGHT || jointype == JOIN_FULL)
+ {
+ /*
+ * Every list value on the outer side will appear in the
+ * join. Find the merged partition to which this value
+ * belongs.
+ */
+ if (right_mmap[r_index] < 0)
+ right_mmap[r_index] = next_index++;
+ merged_index = right_mmap[r_index];
+ merged_datum = rdatums;
+ }
+ else
+ {
+ /* Don't know what to do with other join types. */
+ merged = false;
+ break;
+ }
+
+ /* Move to the next datum on the right side. */
+ cntr++;
+ }
+
+ /*
+ * Add the datum with appropriate index in the list of datums, if the
+ * rows containing that datum are deemed to be part of the join.
+ */
+ if (merged_index >= 0)
+ {
+ merged_indexes = lappend_int(merged_indexes, merged_index);
+ merged_datums = lappend(merged_datums, merged_datum);
+ }
+ }
+
+ /*
+ * If merge is unsuccessful, bail out without any further processing.
+ * That leaks the memory allocated in this function. So, try not to leak
+ * memory.
+ */
+ if (!merged)
+ goto merge_failed;
+
+ /* We should have exhausted datums on at least one side. */
+ Assert(cntr >= right_bi->ndatums || cntl >= left_bi->ndatums);
+
+ /*
+ * Add any remaining list values on the outer side, assigning partition
+ * indexes if required.
+ */
+ if (jointype == JOIN_LEFT || jointype == JOIN_FULL || jointype == JOIN_ANTI)
+ {
+ for (;cntl < left_bi->ndatums; cntl++)
+ {
+ Datum *ldatums = left_bi->datums[cntl];
+ int l_index = left_indexes[cntl];
+
+ if (left_mmap[l_index] < 0)
+ left_mmap[l_index] = next_index++;
+ merged_indexes = lappend_int(merged_indexes, left_mmap[l_index]);
+ merged_datums = lappend(merged_datums, ldatums);
+ }
+ }
+
+ if (jointype == JOIN_RIGHT || jointype == JOIN_FULL)
+ {
+ for (;cntr < right_bi->ndatums; cntr++)
+ {
+ Datum *rdatums = right_bi->datums[cntr];
+ int r_index = right_indexes[cntr];
+
+ if (right_mmap[r_index] < 0)
+ right_mmap[r_index] = next_index++;
+ merged_indexes = lappend_int(merged_indexes, right_mmap[r_index]);
+ merged_datums = lappend(merged_datums, rdatums);
+ }
+ }
+
+ /*
+ * Merge NULL partitions if any. Find the index of merged partition to
+ * which the NULL values belong in the join result. We can eliminate a NULL
+ * partition when it appears only in the inner relation.
+ */
+ if (!partition_bound_accepts_nulls(left_bi) &&
+ !partition_bound_accepts_nulls(right_bi))
+ null_index = -1;
+ else if (partition_bound_accepts_nulls(left_bi) &&
+ !partition_bound_accepts_nulls(right_bi))
+ {
+ if (jointype == JOIN_LEFT || jointype == JOIN_FULL ||
+ jointype == JOIN_ANTI)
+ {
+ if (left_mmap[left_ni] < 0)
+ left_mmap[left_ni] = next_index++;
+ null_index = left_mmap[left_ni];
+ }
+ else
+ null_index = -1;
+ }
+ else if (!partition_bound_accepts_nulls(left_bi) &&
+ partition_bound_accepts_nulls(right_bi))
+ {
+ if (jointype == JOIN_RIGHT || jointype == JOIN_FULL)
+ {
+ if (right_mmap[right_ni] < 0)
+ right_mmap[right_ni] = next_index++;
+ null_index = right_mmap[right_ni];
+ }
+ else
+ null_index = -1;
+ }
+ else
+ {
+ /* Both the relations have NULL partitions, try merging them. */
+ null_index = map_and_merge_partitions(left_pmap, left_mmap,
+ left_ni, right_pmap,
+ right_mmap, right_ni,
+ &next_index);
+ if (null_index < 0)
+ merged = false;
+ }
+
+ /* If successful build the output structures. */
+ if (merged)
+ {
+
+ /* Use maps to match partition from the joining relations. */
+ generate_matching_part_pairs(left_mmap, left_nparts, right_mmap,
+ right_nparts, jointype, next_index,
+ left_parts, right_parts);
+ /* Craft a PartitionBoundInfo to return. */
+ if (*left_parts && *right_parts)
+ {
+ Assert(list_length(*left_parts) == list_length(*right_parts));
+ Assert(list_length(*left_parts) == next_index);
+ merged_bounds = build_merged_partition_bounds(left_bi->strategy,
+ merged_datums,
+ merged_indexes, NIL,
+ null_index);
+ }
+ }
+
+merge_failed:
+ list_free(merged_datums);
+ list_free(merged_indexes);
+ pfree(left_pmap);
+ pfree(right_pmap);
+ pfree(left_mmap);
+ pfree(right_mmap);
+
+ return merged_bounds;
+}
+
+/*
+ * map_and_merge_partitions
+ *
+ * If the two given partitions (given by index1 and index2 resp.) are already
+ * mapped to each other return the index of corresponding partition in the
+ * merged set of partitions. If they do not have a merged partition associated
+ * with them, assign a new merged partition index. If the partitions are
+ * already mapped and their mapped partitions are different from each other,
+ * they can not be merged, so return -1.
+ *
+ * partmap1[i] gives the partition of relation 2 which matches ith partition of
+ * relation 1. Similarly for partmap2.
+ *
+ * mergemap1[i] gives the partition in the merged set to which ith partition of
+ * relation 1 maps to. Similarly for mergemap2.
+ *
+ * index1 and index2 are the indexes of matching partition from respective
+ * relations.
+ *
+ * *next_index is used and incremented when the given partitions require a new
+ * merged partition.
+ */
+static int
+map_and_merge_partitions(int *partmap1, int *mergemap1, int index1,
+ int *partmap2, int *mergemap2, int index2,
+ int *next_index)
+{
+ int merged_index;
+
+ /*
+ * If both the partitions are not mapped to each other, update the
+ * maps.
+ */
+ if (partmap1[index1] < 0 && partmap2[index2] < 0)
+ {
+ partmap1[index1] = index2;
+ partmap2[index2] = index1;
+ }
+
+ /*
+ * If the given to partitions map to each other, find the corresponding
+ * merged partition index .
+ */
+ if (partmap1[index1] == index2 && partmap2[index2] == index1)
+ {
+ /*
+ * If both the partitions are mapped to the same merged partition, get
+ * the index of merged partition.
+ */
+ if (mergemap1[index1] == mergemap2[index2])
+ {
+ merged_index = mergemap1[index1];
+
+ /*
+ * If the given two partitions do not have a merged partition
+ * associated with them, allocate a new merged partition.
+ */
+ if (merged_index < 0)
+ {
+ merged_index = *next_index;
+ *next_index = *next_index + 1;
+ mergemap1[index1] = merged_index;
+ mergemap2[index2] = merged_index;
+ }
+ }
+
+ /*
+ * If partition from one relation was mapped to a merged partition but
+ * not the partition from the other relation, map the same merged
+ * partition to the partition from other relation, since matching
+ * partitions map to the same merged partition.
+ */
+ else if (mergemap1[index1] >= 0 && mergemap2[index2] < 0)
+ {
+ mergemap2[index2] = mergemap1[index1];
+ merged_index = mergemap1[index1];
+ }
+ else if (mergemap1[index1] < 0 && mergemap2[index2] >= 0)
+ {
+ mergemap1[index1] = mergemap2[index2];
+ merged_index = mergemap2[index2];
+ }
+ else
+ {
+ Assert(mergemap1[index1] != mergemap2[index2] &&
+ mergemap1[index1] >= 0 && mergemap2[index2] >= 0);
+
+ /*
+ * Both the partitions map to different merged partitions. This
+ * means that multiple partitions from one relation matches to one
+ * partition from the other relation. Partition-wise join does not
+ * handle this case right now, since it requires ganging multiple
+ * partitions together (into one RelOptInfo).
+ */
+ merged_index = -1;
+ }
+ }
+ else
+ {
+ /*
+ * Multiple partitions from one relation map to one partition from the
+ * other relation. Partition-wise join does not handle this case right
+ * now, since it requires ganging multiple partitions together (into
+ * one RelOptInfo).
+ */
+ merged_index = -1;
+ }
+
+ return merged_index;
+}
+
+/*
+ * generate_matching_part_pairs
+ *
+ * Given the merged partition to which partition on either side of join map,
+ * produce the list pairs of partitions which when joined produce the merged
+ * partitions in the order of merged partition indexes.
+ *
+ * If successful, the pairs of partitions are returned as two separate lists
+ * one for each side. Otherwise, those lists will be set to NIL.
+ *
+ * TODO: rename the sides as outer and inner. You may not need to support
+ * JOIN_RIGHT, since we won't see that type here.
+ */
+static void
+generate_matching_part_pairs(int *mergemap1, int nparts1, int *mergemap2,
+ int nparts2, JoinType jointype, int nparts,
+ List **parts1, List **parts2)
+{
+ bool merged = true;
+ int **matching_parts;
+ int cnt1;
+ int cnt2;
+
+ matching_parts = (int **) palloc(sizeof(int *) * 2);
+ matching_parts[0] = (int *) palloc(sizeof(int) * nparts);
+ matching_parts[1] = (int *) palloc(sizeof(int) * nparts);
+
+ *parts1 = NIL;
+ *parts2 = NIL;
+
+ for (cnt1 = 0; cnt1 < nparts; cnt1++)
+ {
+ matching_parts[0][cnt1] = -1;
+ matching_parts[1][cnt1] = -1;
+ }
+
+ /* Set pairs of matching partitions. */
+ for (cnt1 = 0; cnt1 < nparts1; cnt1++)
+ {
+ if (mergemap1[cnt1] >= 0)
+ {
+ Assert(mergemap1[cnt1] < nparts);
+ matching_parts[0][mergemap1[cnt1]] = cnt1;
+ }
+ }
+ for (cnt2 = 0; cnt2 < nparts2; cnt2++)
+ {
+ if (mergemap2[cnt2] >= 0)
+ {
+ Assert(mergemap2[cnt2] < nparts);
+ matching_parts[1][mergemap2[cnt2]] = cnt2;
+ }
+ }
+
+ /*
+ * If we have a partition missing on an inner side, we need to add a dummy
+ * relation which joins with the outer partition. If the inner relation
+ * happens to be a base relation, it will require adding a dummy child
+ * base relation during join processing. Right now, we freeze the base
+ * relation arrays like PlannerInfo::simple_rte_array after planning for
+ * base relations. Adding a new (dummy) base relation would require some
+ * changes to that. So, right now, we do not implement partition-wise join
+ * in such cases.
+ */
+ for (cnt1 = 0; cnt1 < nparts; cnt1++)
+ {
+ int part1 = matching_parts[0][cnt1];
+ int part2 = matching_parts[1][cnt1];
+
+ /* At least one of the partitions should exist. */
+ Assert(part1 >= 0 || part2 >= 0);
+
+ switch (jointype)
+ {
+ case JOIN_INNER:
+ case JOIN_SEMI:
+
+ /*
+ * An inner or semi join can not return any row when the
+ * matching partition on either side is missing. We should
+ * have eliminated all such cases while merging the bounds.
+ */
+ Assert(part1 >= 0 && part2 >= 0);
+ break;
+
+ case JOIN_LEFT:
+ case JOIN_ANTI:
+ Assert(part1 >= 0);
+ if (part2 < 0)
+ merged = false;
+ break;
+
+ case JOIN_RIGHT:
+ Assert(part2 >= 0);
+ if (part1 < 0)
+ merged = false;
+ break;
+
+ case JOIN_FULL:
+ if (part1 < 0 || part2 < 0)
+ merged = false;
+ break;
+
+ default:
+ /* We do not know what to do in this case. Bail out. */
+ merged = false;
+ }
+
+ if (!merged)
+ break;
+
+ *parts1 = lappend_int(*parts1, part1);
+ *parts2 = lappend_int(*parts2, part2);
+ }
+
+ pfree(matching_parts[0]);
+ pfree(matching_parts[1]);
+ pfree(matching_parts);
+
+ if (!merged)
+ {
+ list_free(*parts1);
+ list_free(*parts2);
+ *parts1 = NIL;
+ *parts2 = NIL;
+ }
+}
+
+static PartitionBoundInfo
+build_merged_partition_bounds(char strategy, List *merged_datums,
+ List *merged_indexes, List *merged_kinds,
+ int null_index)
+{
+ int cnt;
+ PartitionBoundInfo merged_bounds;
+ ListCell *lc;
+
+ /* We expect the same number of elements in datums and indexes lists. */
+ Assert(list_length(merged_datums) == list_length(merged_indexes));
+
+ merged_bounds = (PartitionBoundInfo) palloc(sizeof(PartitionBoundInfoData));
+ merged_bounds->strategy = strategy;
+ merged_bounds->ndatums = list_length(merged_datums);
+
+ if (strategy == PARTITION_STRATEGY_RANGE)
+ {
+ Assert(list_length(merged_datums) == list_length(merged_kinds));
+ merged_bounds->kind = (PartitionRangeDatumKind **) palloc(sizeof(PartitionRangeDatumKind *) *
+ list_length(merged_kinds));
+ cnt = 0;
+ foreach(lc, merged_kinds)
+ merged_bounds->kind[cnt++] = lfirst(lc);
+
+ /* There are ndatums+1 indexes in case of range partitions */
+ merged_indexes = lappend_int(merged_indexes, -1);
+ }
+ else
+ merged_bounds->kind = NULL;
+
+ cnt = 0;
+ merged_bounds->datums = (Datum **) palloc(sizeof(Datum *) *
+ list_length(merged_datums));
+ foreach(lc, merged_datums)
+ merged_bounds->datums[cnt++] = lfirst(lc);
+
+ merged_bounds->indexes = (int *) palloc(sizeof(int) *
+ list_length(merged_indexes));
+ cnt = 0;
+ foreach(lc, merged_indexes)
+ merged_bounds->indexes[cnt++] = lfirst_int(lc);
+
+ merged_bounds->null_index = null_index;
+
+ return merged_bounds;
+}
diff --git a/src/backend/optimizer/path/joinrels.c b/src/backend/optimizer/path/joinrels.c
index 79468d2..d4e3047 100644
--- a/src/backend/optimizer/path/joinrels.c
+++ b/src/backend/optimizer/path/joinrels.c
@@ -1308,8 +1308,13 @@ try_partition_wise_join(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2,
RelOptInfo *joinrel, SpecialJoinInfo *parent_sjinfo,
List *parent_restrictlist)
{
- int nparts;
int cnt_parts;
+ PartitionScheme part_scheme;
+ PartitionBoundInfo join_boundinfo;
+ List *parts1;
+ List *parts2;
+ ListCell *lc1;
+ ListCell *lc2;
/* Guard against stack overflow due to overly deep partition hierarchy. */
check_stack_depth();
@@ -1359,39 +1364,54 @@ try_partition_wise_join(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2,
*/
Assert(joinrel->part_scheme == rel1->part_scheme &&
joinrel->part_scheme == rel2->part_scheme);
+ part_scheme = joinrel->part_scheme;
/*
- * Since we allow partition-wise join only when the partition bounds of
- * the joining relations exactly match, the partition bounds of the join
- * should match those of the joining relations.
+ * Get the list of matching partitions from both sides of the join. While
+ * doing so, we also build the partition bounds of the join relation,
+ * which should match the bounds calculated for other pairs. TODO: why
+ * should every pair result in the same partition bounds?
*/
- Assert(partition_bounds_equal(joinrel->part_scheme->partnatts,
- joinrel->part_scheme->parttyplen,
- joinrel->part_scheme->parttypbyval,
- joinrel->boundinfo, rel1->boundinfo));
- Assert(partition_bounds_equal(joinrel->part_scheme->partnatts,
- joinrel->part_scheme->parttyplen,
- joinrel->part_scheme->parttypbyval,
- joinrel->boundinfo, rel2->boundinfo));
-
- nparts = joinrel->nparts;
-
+ join_boundinfo = partition_bounds_merge(part_scheme->partnatts,
+ part_scheme->partsupfunc,
+ part_scheme->parttypcoll,
+ rel1->boundinfo, rel1->nparts,
+ rel2->boundinfo, rel2->nparts,
+ parent_sjinfo->jointype,
+ &parts1, &parts2);
+
+ Assert(join_boundinfo);
+ Assert(partition_bounds_equal(part_scheme->partnatts,
+ part_scheme->parttyplen,
+ part_scheme->parttypbyval, join_boundinfo,
+ joinrel->boundinfo));
elog(DEBUG3, "join between relations %s and %s is considered for partition-wise join.",
bmsToString(rel1->relids), bmsToString(rel2->relids));
- /* Allocate space to hold child-joins RelOptInfos, if not already done. */
+ /*
+ * Every pair of joining relations should result in the same number of
+ * child-joins.
+ */
+ Assert(joinrel->nparts == list_length(parts1));
+ Assert(joinrel->nparts == list_length(parts2));
+
+ /* Allocate space for hold child-joins RelOptInfos, if not already done. */
if (!joinrel->part_rels)
- joinrel->part_rels = (RelOptInfo **) palloc0(sizeof(RelOptInfo *) * nparts);
+ joinrel->part_rels = (RelOptInfo **) palloc0(sizeof(RelOptInfo *) *
+ joinrel->nparts);
/*
* Create child-join relations for this partitioned join, if those don't
* exist. Add paths to child-joins for a pair of child relations
* corresponding to the given pair of parent relations.
*/
- for (cnt_parts = 0; cnt_parts < nparts; cnt_parts++)
+ cnt_parts = 0;
+ forboth(lc1, parts1, lc2, parts2)
{
- RelOptInfo *child_rel1 = rel1->part_rels[cnt_parts];
- RelOptInfo *child_rel2 = rel2->part_rels[cnt_parts];
+ int part1 = lfirst_int(lc1);
+ int part2 = lfirst_int(lc2);
+ RelOptInfo *child_rel1;
+ RelOptInfo *child_rel2;
SpecialJoinInfo *child_sjinfo;
List *child_restrictlist;
RelOptInfo *child_joinrel;
@@ -1399,6 +1419,10 @@ try_partition_wise_join(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2,
AppendRelInfo **appinfos;
int nappinfos;
+ Assert(part1 >= 0 && part2 >= 0);
+ child_rel1 = rel1->part_rels[part1];
+ child_rel2 = rel2->part_rels[part2];
+
/* We should never try to join two overlapping sets of rels. */
Assert(!bms_overlap(child_rel1->relids, child_rel2->relids));
child_joinrelids = bms_union(child_rel1->relids, child_rel2->relids);
@@ -1431,6 +1455,15 @@ try_partition_wise_join(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2,
joinrel->part_rels[cnt_parts] = child_joinrel;
}
+ /*
+ * For every pair of joining relations, the set of matching partitions
+ * would change. However, the base relation partitions constituting
+ * the given child should remain same for all the joining pairs. Since
+ * the order in which children are stored in the array of child-joins,
+ * depends upon partition bounds of the join, which are same for all
+ * the joining pairs, every joining pair yields the child-joins in the
+ * same order.
+ */
Assert(bms_equal(child_joinrel->relids, child_joinrelids));
populate_joinrel_with_paths(root, child_rel1, child_rel2,
@@ -1443,7 +1476,11 @@ try_partition_wise_join(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2,
*/
try_partition_wise_join(root, child_rel1, child_rel2, child_joinrel,
child_sjinfo, child_restrictlist);
+
+ cnt_parts++;
}
+
+ Assert(cnt_parts == joinrel->nparts);
}
/*
diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c
index 81bc2b1..5d1992e 100644
--- a/src/backend/optimizer/util/relnode.c
+++ b/src/backend/optimizer/util/relnode.c
@@ -1613,6 +1613,9 @@ build_joinrel_partition_info(RelOptInfo *joinrel, RelOptInfo *outer_rel,
int partnatts;
int cnt;
PartitionScheme part_scheme;
+ PartitionBoundInfo join_boundinfo;
+ List *parts1;
+ List *parts2;
/* Nothing to do if partition-wise join technique is disabled. */
if (!enable_partition_wise_join)
@@ -1653,17 +1656,26 @@ build_joinrel_partition_info(RelOptInfo *joinrel, RelOptInfo *outer_rel,
REL_HAS_ALL_PART_PROPS(inner_rel));
/*
- * For now, our partition matching algorithm can match partitions only
- * when the partition bounds of the joining relations are exactly same.
- * So, bail out otherwise.
+ * Every pair of joining relations would yield the same partition bounds
+ * for a given join (TODO: why?) so we compute the bounds only the first
+ * time. Then for every pair we find the pairs of matching partitions from
+ * the joining relations and join those. TODO: Needs a better explanation
+ * of why is this true. TODO: Also there is no reason to have
+ * part_indexes1 and part_indexes2 pulled here just to be freed up later.
+ * So, we might want to do something better.
*/
- if (outer_rel->nparts != inner_rel->nparts ||
- !partition_bounds_equal(part_scheme->partnatts,
- part_scheme->parttyplen,
- part_scheme->parttypbyval,
- outer_rel->boundinfo, inner_rel->boundinfo))
+ join_boundinfo = partition_bounds_merge(part_scheme->partnatts,
+ part_scheme->partsupfunc,
+ part_scheme->parttypcoll,
+ outer_rel->boundinfo,
+ outer_rel->nparts,
+ inner_rel->boundinfo,
+ inner_rel->nparts,
+ jointype, &parts1, &parts2);
+ if (!join_boundinfo)
{
Assert(!IS_PARTITIONED_REL(joinrel));
+ Assert(!parts1 && !parts2);
return;
}
@@ -1676,13 +1688,16 @@ build_joinrel_partition_info(RelOptInfo *joinrel, RelOptInfo *outer_rel,
!joinrel->nullable_partexprs && !joinrel->part_rels &&
!joinrel->boundinfo);
+ Assert(list_length(parts1) == list_length(parts2));
+
/*
* Join relation is partitioned using same partitioning scheme as the
- * joining relations and has same bounds.
+ * joining relations. It will have as many partitions as the pairs of
+ * matching partitions we found.
*/
joinrel->part_scheme = part_scheme;
- joinrel->boundinfo = outer_rel->boundinfo;
- joinrel->nparts = outer_rel->nparts;
+ joinrel->nparts = list_length(parts1);
+ joinrel->boundinfo = join_boundinfo;
partnatts = joinrel->part_scheme->partnatts;
/*
@@ -1803,4 +1818,9 @@ build_joinrel_partition_info(RelOptInfo *joinrel, RelOptInfo *outer_rel,
joinrel->nullable_partexprs[cnt] = nullable_partexprs;
}
}
+
+ /* TODO: OR we could actually create the child-join relations here.*/
+ list_free(parts1);
+ list_free(parts2);
+
}
diff --git a/src/include/catalog/partition.h b/src/include/catalog/partition.h
index 2283c67..056a4f9 100644
--- a/src/include/catalog/partition.h
+++ b/src/include/catalog/partition.h
@@ -99,4 +99,10 @@ extern int get_partition_for_tuple(PartitionDispatch *pd,
EState *estate,
PartitionDispatchData **failed_at,
TupleTableSlot **failed_slot);
+extern PartitionBoundInfo partition_bounds_merge(int partnatts,
+ FmgrInfo *supfuncs, Oid *collations,
+ PartitionBoundInfo boundinfo1, int nparts1,
+ PartitionBoundInfo boundinfo2, int nparts2,
+ JoinType jointype, List **parts1, List **parts2);
+
#endif /* PARTITION_H */
--
1.7.9.5
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
