diff options
Diffstat (limited to 'src/backend/partitioning/partbounds.c')
| -rw-r--r-- | src/backend/partitioning/partbounds.c | 1865 |
1 files changed, 1865 insertions, 0 deletions
diff --git a/src/backend/partitioning/partbounds.c b/src/backend/partitioning/partbounds.c index 4c47f54a57c..7607501fe7f 100644 --- a/src/backend/partitioning/partbounds.c +++ b/src/backend/partitioning/partbounds.c @@ -26,6 +26,7 @@ #include "miscadmin.h" #include "nodes/makefuncs.h" #include "nodes/nodeFuncs.h" +#include "nodes/pathnodes.h" #include "parser/parse_coerce.h" #include "partitioning/partbounds.h" #include "partitioning/partdesc.h" @@ -68,6 +69,28 @@ typedef struct PartitionRangeBound bool lower; /* this is the lower (vs upper) bound */ } PartitionRangeBound; +/* + * Mapping from partitions of a joining relation to partitions of a join + * relation being computed (a.k.a merged partitions) + */ +typedef struct PartitionMap +{ + int nparts; /* number of partitions */ + int *merged_indexes; /* indexes of merged partitions */ + bool *merged; /* flags to indicate whether partitions are + * merged with non-dummy partitions */ + bool did_remapping; /* did we re-map partitions? */ + int *old_indexes; /* old indexes of merged partitions if + * did_remapping */ +} PartitionMap; + +/* Macro for comparing two range bounds */ +#define compare_range_bounds(partnatts, partsupfunc, partcollations, \ + bound1, bound2) \ + (partition_rbound_cmp(partnatts, partsupfunc, partcollations, \ + (bound1)->datums, (bound1)->kind, (bound1)->lower, \ + bound2)) + static int32 qsort_partition_hbound_cmp(const void *a, const void *b); static int32 qsort_partition_list_value_cmp(const void *a, const void *b, void *arg); @@ -79,6 +102,116 @@ static PartitionBoundInfo create_list_bounds(PartitionBoundSpec **boundspecs, int nparts, PartitionKey key, int **mapping); static PartitionBoundInfo create_range_bounds(PartitionBoundSpec **boundspecs, int nparts, PartitionKey key, int **mapping); +static PartitionBoundInfo merge_list_bounds(FmgrInfo *partsupfunc, + Oid *collations, + RelOptInfo *outer_rel, + RelOptInfo *inner_rel, + JoinType jointype, + List **outer_parts, + List **inner_parts); +static PartitionBoundInfo merge_range_bounds(int partnatts, + FmgrInfo *partsupfuncs, + Oid *partcollations, + RelOptInfo *outer_rel, + RelOptInfo *inner_rel, + JoinType jointype, + List **outer_parts, + List **inner_parts); +static void init_partition_map(RelOptInfo *rel, PartitionMap *map); +static void free_partition_map(PartitionMap *map); +static bool is_dummy_partition(RelOptInfo *rel, int part_index); +static int merge_matching_partitions(PartitionMap *outer_map, + PartitionMap *inner_map, + int outer_part, + int inner_part, + int *next_index); +static int process_outer_partition(PartitionMap *outer_map, + PartitionMap *inner_map, + bool outer_has_default, + bool inner_has_default, + int outer_index, + int inner_default, + JoinType jointype, + int *next_index, + int *default_index); +static int process_inner_partition(PartitionMap *outer_map, + PartitionMap *inner_map, + bool outer_has_default, + bool inner_has_default, + int inner_index, + int outer_default, + JoinType jointype, + int *next_index, + int *default_index); +static void merge_null_partitions(PartitionMap *outer_map, + PartitionMap *inner_map, + bool outer_has_null, + bool inner_has_null, + int outer_null, + int inner_null, + JoinType jointype, + int *next_index, + int *null_index); +static void merge_default_partitions(PartitionMap *outer_map, + PartitionMap *inner_map, + bool outer_has_default, + bool inner_has_default, + int outer_default, + int inner_default, + JoinType jointype, + int *next_index, + int *default_index); +static int merge_partition_with_dummy(PartitionMap *map, int index, + int *next_index); +static void fix_merged_indexes(PartitionMap *outer_map, + PartitionMap *inner_map, + int nmerged, List *merged_indexes); +static void generate_matching_part_pairs(RelOptInfo *outer_rel, + RelOptInfo *inner_rel, + PartitionMap *outer_map, + PartitionMap *inner_map, + int nmerged, + List **outer_parts, + List **inner_parts); +static PartitionBoundInfo build_merged_partition_bounds(char strategy, + List *merged_datums, + List *merged_kinds, + List *merged_indexes, + int null_index, + int default_index); +static int get_range_partition(RelOptInfo *rel, + PartitionBoundInfo bi, + int *lb_pos, + PartitionRangeBound *lb, + PartitionRangeBound *ub); +static int get_range_partition_internal(PartitionBoundInfo bi, + int *lb_pos, + PartitionRangeBound *lb, + PartitionRangeBound *ub); +static bool compare_range_partitions(int partnatts, FmgrInfo *partsupfuncs, + Oid *partcollations, + PartitionRangeBound *outer_lb, + PartitionRangeBound *outer_ub, + PartitionRangeBound *inner_lb, + PartitionRangeBound *inner_ub, + int *lb_cmpval, int *ub_cmpval); +static void get_merged_range_bounds(int partnatts, FmgrInfo *partsupfuncs, + Oid *partcollations, JoinType jointype, + PartitionRangeBound *outer_lb, + PartitionRangeBound *outer_ub, + PartitionRangeBound *inner_lb, + PartitionRangeBound *inner_ub, + int lb_cmpval, int ub_cmpval, + PartitionRangeBound *merged_lb, + PartitionRangeBound *merged_ub); +static void add_merged_range_bounds(int partnatts, FmgrInfo *partsupfuncs, + Oid *partcollations, + PartitionRangeBound *merged_lb, + PartitionRangeBound *merged_ub, + int merged_index, + List **merged_datums, + List **merged_kinds, + List **merged_indexes); static PartitionRangeBound *make_one_partition_rbound(PartitionKey key, int index, List *datums, bool lower); static int32 partition_hbound_cmp(int modulus1, int remainder1, int modulus2, @@ -867,6 +1000,1738 @@ partition_bounds_copy(PartitionBoundInfo src, } /* + * partition_bounds_merge + * Check to see whether every partition of 'outer_rel' matches/overlaps + * one partition of 'inner_rel' at most, and vice versa; and if so, build + * and return the partition bounds for a join relation between the rels, + * generating two lists of the matching/overlapping partitions, which are + * returned to *outer_parts and *inner_parts respectively. + * + * The lists contain the same number of partitions, and the partitions at the + * same positions in the lists indicate join pairs used for partitioned join. + * If a partition on one side matches/overlaps multiple partitions on the other + * side, this function returns NULL, setting *outer_parts and *inner_parts to + * NIL. + */ +PartitionBoundInfo +partition_bounds_merge(int partnatts, + FmgrInfo *partsupfunc, Oid *partcollation, + RelOptInfo *outer_rel, RelOptInfo *inner_rel, + JoinType jointype, + List **outer_parts, List **inner_parts) +{ + PartitionBoundInfo outer_binfo = outer_rel->boundinfo; + PartitionBoundInfo inner_binfo = inner_rel->boundinfo; + + /* + * Currently, this function is called only from try_partitionwise_join(), + * so the join type should be INNER, LEFT, FULL, SEMI, or ANTI. + */ + Assert(jointype == JOIN_INNER || jointype == JOIN_LEFT || + jointype == JOIN_FULL || jointype == JOIN_SEMI || + jointype == JOIN_ANTI); + + /* The partitioning strategies should be the same. */ + Assert(outer_binfo->strategy == inner_binfo->strategy); + + *outer_parts = *inner_parts = NIL; + switch (outer_binfo->strategy) + { + case PARTITION_STRATEGY_HASH: + + /* + * For hash partitioned tables, we currently support partitioned + * join only when they have exactly the same partition bounds. + * + * XXX: it might be possible to relax the restriction to support + * cases where hash partitioned tables have missing partitions + * and/or different moduli, but it's not clear if it would be + * useful to support the former case since it's unusual to have + * missing partitions. On the other hand, it would be useful to + * support the latter case, but in that case, there is a high + * probability that a partition on one side will match multiple + * partitions on the other side, which is the scenario the current + * implementation of partitioned join can't handle. + */ + return NULL; + + case PARTITION_STRATEGY_LIST: + return merge_list_bounds(partsupfunc, + partcollation, + outer_rel, + inner_rel, + jointype, + outer_parts, + inner_parts); + + case PARTITION_STRATEGY_RANGE: + return merge_range_bounds(partnatts, + partsupfunc, + partcollation, + outer_rel, + inner_rel, + jointype, + outer_parts, + inner_parts); + + default: + elog(ERROR, "unexpected partition strategy: %d", + (int) outer_binfo->strategy); + return NULL; /* keep compiler quiet */ + } +} + +/* + * merge_list_bounds + * Create the partition bounds for a join relation between list + * partitioned tables, if possible + * + * In this function we try to find sets of matching partitions from both sides + * by comparing list values stored in their partition bounds. Since the list + * values appear in the ascending order, an algorithm similar to merge join is + * used for that. If a partition on one side doesn't have a matching + * partition on the other side, the algorithm tries to match it with the + * default partition on the other side if any; if not, the algorithm tries to + * match it with a dummy partition on the other side if it's on the + * non-nullable side of an outer join. Also, if both sides have the default + * partitions, the algorithm tries to match them with each other. We give up + * if the algorithm finds a partition matching multiple partitions on the + * other side, which is the scenario the current implementation of partitioned + * join can't handle. + */ +static PartitionBoundInfo +merge_list_bounds(FmgrInfo *partsupfunc, Oid *partcollation, + RelOptInfo *outer_rel, RelOptInfo *inner_rel, + JoinType jointype, + List **outer_parts, List **inner_parts) +{ + PartitionBoundInfo merged_bounds = NULL; + PartitionBoundInfo outer_bi = outer_rel->boundinfo; + PartitionBoundInfo inner_bi = inner_rel->boundinfo; + bool outer_has_default = partition_bound_has_default(outer_bi); + bool inner_has_default = partition_bound_has_default(inner_bi); + int outer_default = outer_bi->default_index; + int inner_default = inner_bi->default_index; + bool outer_has_null = partition_bound_accepts_nulls(outer_bi); + bool inner_has_null = partition_bound_accepts_nulls(inner_bi); + PartitionMap outer_map; + PartitionMap inner_map; + int outer_pos; + int inner_pos; + int next_index = 0; + int null_index = -1; + int default_index = -1; + List *merged_datums = NIL; + List *merged_indexes = NIL; + + Assert(*outer_parts == NIL); + Assert(*inner_parts == NIL); + Assert(outer_bi->strategy == inner_bi->strategy && + outer_bi->strategy == PARTITION_STRATEGY_LIST); + /* List partitioning doesn't require kinds. */ + Assert(!outer_bi->kind && !inner_bi->kind); + + init_partition_map(outer_rel, &outer_map); + init_partition_map(inner_rel, &inner_map); + + /* + * If the default partitions (if any) have been proven empty, deem them + * non-existent. + */ + if (outer_has_default && is_dummy_partition(outer_rel, outer_default)) + outer_has_default = false; + if (inner_has_default && is_dummy_partition(inner_rel, inner_default)) + inner_has_default = false; + + /* + * Merge partitions from both sides. In each iteration we compare a pair + * of list values, one from each side, and decide whether the corresponding + * partitions match or not. If the two values match exactly, move to the + * next pair of list values, otherwise move to the next list value on the + * side with a smaller list value. + */ + outer_pos = inner_pos = 0; + while (outer_pos < outer_bi->ndatums || inner_pos < inner_bi->ndatums) + { + int outer_index = -1; + int inner_index = -1; + Datum *outer_datums; + Datum *inner_datums; + int cmpval; + Datum *merged_datum = NULL; + int merged_index = -1; + + if (outer_pos < outer_bi->ndatums) + { + /* + * If the partition on the outer side has been proven empty, ignore + * it and move to the next datum on the outer side. + */ + outer_index = outer_bi->indexes[outer_pos]; + if (is_dummy_partition(outer_rel, outer_index)) + { + outer_pos++; + continue; + } + } + if (inner_pos < inner_bi->ndatums) + { + /* + * If the partition on the inner side has been proven empty, ignore + * it and move to the next datum on the inner side. + */ + inner_index = inner_bi->indexes[inner_pos]; + if (is_dummy_partition(inner_rel, inner_index)) + { + inner_pos++; + continue; + } + } + + /* Get the list values. */ + outer_datums = outer_pos < outer_bi->ndatums ? + outer_bi->datums[outer_pos] : NULL; + inner_datums = inner_pos < inner_bi->ndatums ? + inner_bi->datums[inner_pos] : NULL; + + /* + * We run this loop till both sides finish. This allows us to avoid + * duplicating code to handle the remaining values on the side which + * finishes later. For that we set the comparison parameter cmpval in + * such a way that it appears as if the side which finishes earlier has + * an extra value higher than any other value on the unfinished side. + * That way we advance the values on the unfinished side till all of + * its values are exhausted. + */ + if (outer_pos >= outer_bi->ndatums) + cmpval = 1; + else if (inner_pos >= inner_bi->ndatums) + cmpval = -1; + else + { + Assert(outer_datums != NULL && inner_datums != NULL); + cmpval = DatumGetInt32(FunctionCall2Coll(&partsupfunc[0], + partcollation[0], + outer_datums[0], + inner_datums[0])); + } + + if (cmpval == 0) + { + /* Two list values match exactly. */ + Assert(outer_pos < outer_bi->ndatums); + Assert(inner_pos < inner_bi->ndatums); + Assert(outer_index >= 0); + Assert(inner_index >= 0); + + /* + * Try merging both paritions. If successful, add the list value + * and index of the merged partition below. + */ + merged_index = merge_matching_partitions(&outer_map, &inner_map, + outer_index, inner_index, + &next_index); + if (merged_index == -1) + goto cleanup; + + merged_datum = outer_datums; + + /* Move to the next pair of list values. */ + outer_pos++; + inner_pos++; + } + else if (cmpval < 0) + { + /* A list value missing from the inner side. */ + Assert(outer_pos < outer_bi->ndatums); + + /* + * If the inner side has the default partition, or this is an outer + * join, try to assign a merged partition to the outer partition + * (see process_outer_partition()). Otherwise, the outer partition + * will not contribute to the result. + */ + if (inner_has_default || IS_OUTER_JOIN(jointype)) + { + /* Get the outer partition. */ + outer_index = outer_bi->indexes[outer_pos]; + Assert(outer_index >= 0); + merged_index = process_outer_partition(&outer_map, + &inner_map, + outer_has_default, + inner_has_default, + outer_index, + inner_default, + jointype, + &next_index, + &default_index); + if (merged_index == -1) + goto cleanup; + merged_datum = outer_datums; + } + + /* Move to the next list value on the outer side. */ + outer_pos++; + } + else + { + /* A list value missing from the outer side. */ + Assert(cmpval > 0); + Assert(inner_pos < inner_bi->ndatums); + + /* + * If the outer side has the default partition, or this is a FULL + * join, try to assign a merged partition to the inner partition + * (see process_inner_partition()). Otherwise, the inner partition + * will not contribute to the result. + */ + if (outer_has_default || jointype == JOIN_FULL) + { + /* Get the inner partition. */ + inner_index = inner_bi->indexes[inner_pos]; + Assert(inner_index >= 0); + merged_index = process_inner_partition(&outer_map, + &inner_map, + outer_has_default, + inner_has_default, + inner_index, + outer_default, + jointype, + &next_index, + &default_index); + if (merged_index == -1) + goto cleanup; + merged_datum = inner_datums; + } + + /* Move to the next list value on the inner side. */ + inner_pos++; + } + + /* + * If we assigned a merged partition, add the list value and index of + * the merged partition if appropriate. + */ + if (merged_index >= 0 && merged_index != default_index) + { + merged_datums = lappend(merged_datums, merged_datum); + merged_indexes = lappend_int(merged_indexes, merged_index); + } + } + + /* + * If the NULL partitions (if any) have been proven empty, deem them + * non-existent. + */ + if (outer_has_null && + is_dummy_partition(outer_rel, outer_bi->null_index)) + outer_has_null = false; + if (inner_has_null && + is_dummy_partition(inner_rel, inner_bi->null_index)) + inner_has_null = false; + + /* Merge the NULL partitions if any. */ + if (outer_has_null || inner_has_null) + merge_null_partitions(&outer_map, &inner_map, + outer_has_null, inner_has_null, + outer_bi->null_index, inner_bi->null_index, + jointype, &next_index, &null_index); + else + Assert(null_index == -1); + + /* Merge the default partitions if any. */ + if (outer_has_default || inner_has_default) + merge_default_partitions(&outer_map, &inner_map, + outer_has_default, inner_has_default, + outer_default, inner_default, + jointype, &next_index, &default_index); + else + Assert(default_index == -1); + + /* If we have merged partitions, create the partition bounds. */ + if (next_index > 0) + { + /* Fix the merged_indexes list if necessary. */ + if (outer_map.did_remapping || inner_map.did_remapping) + { + Assert(jointype == JOIN_FULL); + fix_merged_indexes(&outer_map, &inner_map, + next_index, merged_indexes); + } + + /* Use maps to match partitions from inputs. */ + generate_matching_part_pairs(outer_rel, inner_rel, + &outer_map, &inner_map, + next_index, + outer_parts, inner_parts); + Assert(*outer_parts != NIL); + Assert(*inner_parts != NIL); + Assert(list_length(*outer_parts) == list_length(*inner_parts)); + Assert(list_length(*outer_parts) <= next_index); + + /* Make a PartitionBoundInfo struct to return. */ + merged_bounds = build_merged_partition_bounds(outer_bi->strategy, + merged_datums, + NIL, + merged_indexes, + null_index, + default_index); + Assert(merged_bounds); + } + +cleanup: + /* Free local memory before returning. */ + list_free(merged_datums); + list_free(merged_indexes); + free_partition_map(&outer_map); + free_partition_map(&inner_map); + + return merged_bounds; +} + +/* + * merge_range_bounds + * Create the partition bounds for a join relation between range + * partitioned tables, if possible + * + * In this function we try to find sets of overlapping partitions from both + * sides by comparing ranges stored in their partition bounds. Since the + * ranges appear in the ascending order, an algorithm similar to merge join is + * used for that. If a partition on one side doesn't have an overlapping + * partition on the other side, the algorithm tries to match it with the + * default partition on the other side if any; if not, the algorithm tries to + * match it with a dummy partition on the other side if it's on the + * non-nullable side of an outer join. Also, if both sides have the default + * partitions, the algorithm tries to match them with each other. We give up + * if the algorithm finds a partition overlapping multiple partitions on the + * other side, which is the scenario the current implementation of partitioned + * join can't handle. + */ +static PartitionBoundInfo +merge_range_bounds(int partnatts, FmgrInfo *partsupfuncs, + Oid *partcollations, + RelOptInfo *outer_rel, RelOptInfo *inner_rel, + JoinType jointype, + List **outer_parts, List **inner_parts) +{ + PartitionBoundInfo merged_bounds = NULL; + PartitionBoundInfo outer_bi = outer_rel->boundinfo; + PartitionBoundInfo inner_bi = inner_rel->boundinfo; + bool outer_has_default = partition_bound_has_default(outer_bi); + bool inner_has_default = partition_bound_has_default(inner_bi); + int outer_default = outer_bi->default_index; + int inner_default = inner_bi->default_index; + PartitionMap outer_map; + PartitionMap inner_map; + int outer_index; + int inner_index; + int outer_lb_pos; + int inner_lb_pos; + PartitionRangeBound outer_lb; + PartitionRangeBound outer_ub; + PartitionRangeBound inner_lb; + PartitionRangeBound inner_ub; + int next_index = 0; + int default_index = -1; + List *merged_datums = NIL; + List *merged_kinds = NIL; + List *merged_indexes = NIL; + + Assert(*outer_parts == NIL); + Assert(*inner_parts == NIL); + Assert(outer_bi->strategy == inner_bi->strategy && + outer_bi->strategy == PARTITION_STRATEGY_RANGE); + + init_partition_map(outer_rel, &outer_map); + init_partition_map(inner_rel, &inner_map); + + /* + * If the default partitions (if any) have been proven empty, deem them + * non-existent. + */ + if (outer_has_default && is_dummy_partition(outer_rel, outer_default)) + outer_has_default = false; + if (inner_has_default && is_dummy_partition(inner_rel, inner_default)) + inner_has_default = false; + + /* + * Merge partitions from both sides. In each iteration we compare a pair + * of ranges, one from each side, and decide whether the corresponding + * partitions match or not. If the two ranges overlap, move to the next + * pair of ranges, otherwise move to the next range on the side with a + * lower range. outer_lb_pos/inner_lb_pos keep track of the positions of + * lower bounds in the datums arrays in the outer/inner PartitionBoundInfos + * respectively. + */ + outer_lb_pos = inner_lb_pos = 0; + outer_index = get_range_partition(outer_rel, outer_bi, &outer_lb_pos, + &outer_lb, &outer_ub); + inner_index = get_range_partition(inner_rel, inner_bi, &inner_lb_pos, + &inner_lb, &inner_ub); + while (outer_index >= 0 || inner_index >= 0) + { + bool overlap; + int ub_cmpval; + int lb_cmpval; + PartitionRangeBound merged_lb = {-1, NULL, NULL, true}; + PartitionRangeBound merged_ub = {-1, NULL, NULL, false}; + int merged_index = -1; + + /* + * We run this loop till both sides finish. This allows us to avoid + * duplicating code to handle the remaining ranges on the side which + * finishes later. For that we set the comparison parameter cmpval in + * such a way that it appears as if the side which finishes earlier has + * an extra range higher than any other range on the unfinished side. + * That way we advance the ranges on the unfinished side till all of + * its ranges are exhausted. + */ + if (outer_index == -1) + { + overlap = false; + lb_cmpval = 1; + ub_cmpval = 1; + } + else if (inner_index == -1) + { + overlap = false; + lb_cmpval = -1; + ub_cmpval = -1; + } + else + overlap = compare_range_partitions(partnatts, partsupfuncs, + partcollations, + &outer_lb, &outer_ub, + &inner_lb, &inner_ub, + &lb_cmpval, &ub_cmpval); + + if (overlap) + { + /* Two ranges overlap; form a join pair. */ + + PartitionRangeBound save_outer_ub; + PartitionRangeBound save_inner_ub; + + /* Both partitions should not have been merged yet. */ + Assert(outer_index >= 0); + Assert(outer_map.merged_indexes[outer_index] == -1 && + outer_map.merged[outer_index] == false); + Assert(inner_index >= 0); + Assert(inner_map.merged_indexes[inner_index] == -1 && + inner_map.merged[inner_index] == false); + + /* + * Get the index of the merged partition. Both partitions aren't + * merged yet, so the partitions should be merged successfully. + */ + merged_index = merge_matching_partitions(&outer_map, &inner_map, + outer_index, inner_index, + &next_index); + Assert(merged_index >= 0); + + /* Get the range of the merged partition. */ + get_merged_range_bounds(partnatts, partsupfuncs, + partcollations, jointype, + &outer_lb, &outer_ub, + &inner_lb, &inner_ub, + lb_cmpval, ub_cmpval, + &merged_lb, &merged_ub); + + /* Save the upper bounds of both partitions for use below. */ + save_outer_ub = outer_ub; + save_inner_ub = inner_ub; + + /* Move to the next pair of ranges. */ + outer_index = get_range_partition(outer_rel, outer_bi, &outer_lb_pos, + &outer_lb, &outer_ub); + inner_index = get_range_partition(inner_rel, inner_bi, &inner_lb_pos, + &inner_lb, &inner_ub); + + /* + * If the range of a partition on one side overlaps the range of + * the next partition on the other side, that will cause the + * partition on one side to match at least two partitions on the + * other side, which is the case that we currently don't support + * partitioned join for; give up. + */ + if (ub_cmpval > 0 && inner_index >= 0 && + compare_range_bounds(partnatts, partsupfuncs, partcollations, + &save_outer_ub, &inner_lb) > 0) + goto cleanup; + if (ub_cmpval < 0 && outer_index >= 0 && + compare_range_bounds(partnatts, partsupfuncs, partcollations, + &outer_lb, &save_inner_ub) < 0) + goto cleanup; + + /* + * A row from a non-overlapping portion (if any) of a partition + * on one side might find its join partner in the default + * partition (if any) on the other side, causing the same + * situation as above; give up in that case. + */ + if ((outer_has_default && (lb_cmpval > 0 || ub_cmpval < 0)) || + (inner_has_default && (lb_cmpval < 0 || ub_cmpval > 0))) + goto cleanup; + } + else if (ub_cmpval < 0) + { + /* A non-overlapping outer range. */ + + /* The outer partition should not have been merged yet. */ + Assert(outer_index >= 0); + Assert(outer_map.merged_indexes[outer_index] == -1 && + outer_map.merged[outer_index] == false); + + /* + * If the inner side has the default partition, or this is an outer + * join, try to assign a merged partition to the outer partition + * (see process_outer_partition()). Otherwise, the outer partition + * will not contribute to the result. + */ + if (inner_has_default || IS_OUTER_JOIN(jointype)) + { + merged_index = process_outer_partition(&outer_map, + &inner_map, + outer_has_default, + inner_has_default, + outer_index, + inner_default, + jointype, + &next_index, + &default_index); + if (merged_index == -1) + goto cleanup; + merged_lb = outer_lb; + merged_ub = outer_ub; + } + + /* Move to the next range on the outer side. */ + outer_index = get_range_partition(outer_rel, outer_bi, &outer_lb_pos, + &outer_lb, &outer_ub); + } + else + { + /* A non-overlapping inner range. */ + Assert(ub_cmpval > 0); + + /* The inner partition should not have been merged yet. */ + Assert(inner_index >= 0); + Assert(inner_map.merged_indexes[inner_index] == -1 && + inner_map.merged[inner_index] == false); + + /* + * If the outer side has the default partition, or this is a FULL + * join, try to assign a merged partition to the inner partition + * (see process_inner_partition()). Otherwise, the inner partition + * will not contribute to the result. + */ + if (outer_has_default || jointype == JOIN_FULL) + { + merged_index = process_inner_partition(&outer_map, + &inner_map, + outer_has_default, + inner_has_default, + inner_index, + outer_default, + jointype, + &next_index, + &default_index); + if (merged_index == -1) + goto cleanup; + merged_lb = inner_lb; + merged_ub = inner_ub; + } + + /* Move to the next range on the inner side. */ + inner_index = get_range_partition(inner_rel, inner_bi, &inner_lb_pos, + &inner_lb, &inner_ub); + } + + /* + * If we assigned a merged partition, add the range bounds and index of + * the merged partition if appropriate. + */ + if (merged_index >= 0 && merged_index != default_index) + add_merged_range_bounds(partnatts, partsupfuncs, partcollations, + &merged_lb, &merged_ub, merged_index, + &merged_datums, &merged_kinds, + &merged_indexes); + } + + /* Merge the default partitions if any. */ + if (outer_has_default || inner_has_default) + merge_default_partitions(&outer_map, &inner_map, + outer_has_default, inner_has_default, + outer_default, inner_default, + jointype, &next_index, &default_index); + else + Assert(default_index == -1); + + /* If we have merged partitions, create the partition bounds. */ + if (next_index > 0) + { + /* + * Unlike the case of list partitioning, we wouldn't have re-merged + * partitions, so did_remapping should be left alone. + */ + Assert(!outer_map.did_remapping); + Assert(!inner_map.did_remapping); + + /* Use maps to match partitions from inputs. */ + generate_matching_part_pairs(outer_rel, inner_rel, + &outer_map, &inner_map, + next_index, + outer_parts, inner_parts); + Assert(*outer_parts != NIL); + Assert(*inner_parts != NIL); + Assert(list_length(*outer_parts) == list_length(*inner_parts)); + Assert(list_length(*outer_parts) == next_index); + + /* Make a PartitionBoundInfo struct to return. */ + merged_bounds = build_merged_partition_bounds(outer_bi->strategy, + merged_datums, + merged_kinds, + merged_indexes, + -1, + default_index); + Assert(merged_bounds); + } + +cleanup: + /* Free local memory before returning. */ + list_free(merged_datums); + list_free(merged_kinds); + list_free(merged_indexes); + free_partition_map(&outer_map); + free_partition_map(&inner_map); + + return merged_bounds; +} + +/* + * init_partition_map + * Initialize a PartitionMap struct for given relation + */ +static void +init_partition_map(RelOptInfo *rel, PartitionMap *map) +{ + int nparts = rel->nparts; + int i; + + map->nparts = nparts; + map->merged_indexes = (int *) palloc(sizeof(int) * nparts); + map->merged = (bool *) palloc(sizeof(bool) * nparts); + map->did_remapping = false; + map->old_indexes = (int *) palloc(sizeof(int) * nparts); + for (i = 0; i < nparts; i++) + { + map->merged_indexes[i] = map->old_indexes[i] = -1; + map->merged[i] = false; + } +} + +/* + * free_partition_map + */ +static void +free_partition_map(PartitionMap *map) +{ + pfree(map->merged_indexes); + pfree(map->merged); + pfree(map->old_indexes); +} + +/* + * is_dummy_partition --- has partition been proven empty? + */ +static bool +is_dummy_partition(RelOptInfo *rel, int part_index) +{ + RelOptInfo *part_rel; + + Assert(part_index >= 0); + part_rel = rel->part_rels[part_index]; + if (part_rel == NULL || IS_DUMMY_REL(part_rel)) + return true; + return false; +} + +/* + * merge_matching_partitions + * Try to merge given outer/inner partitions, and return the index of a + * merged partition produced from them if successful, -1 otherwise + * + * If the merged partition is newly created, *next_index is incremented. + */ +static int +merge_matching_partitions(PartitionMap *outer_map, PartitionMap *inner_map, + int outer_index, int inner_index, int *next_index) +{ + int outer_merged_index; + int inner_merged_index; + bool outer_merged; + bool inner_merged; + + Assert(outer_index >= 0 && outer_index < outer_map->nparts); + outer_merged_index = outer_map->merged_indexes[outer_index]; + outer_merged = outer_map->merged[outer_index]; + Assert(inner_index >= 0 && inner_index < inner_map->nparts); + inner_merged_index = inner_map->merged_indexes[inner_index]; + inner_merged = inner_map->merged[inner_index]; + + /* + * Handle cases where we have already assigned a merged partition to each + * of the given partitions. + */ + if (outer_merged_index >= 0 && inner_merged_index >= 0) + { + /* + * If the mereged partitions are the same, no need to do anything; + * return the index of the merged partitions. Otherwise, if each of + * the given partitions has been merged with a dummy partition on the + * other side, re-map them to either of the two merged partitions. + * Otherwise, they can't be merged, so return -1. + */ + if (outer_merged_index == inner_merged_index) + { + Assert(outer_merged); + Assert(inner_merged); + return outer_merged_index; + } + if (!outer_merged && !inner_merged) + { + /* + * This can only happen for a list-partitioning case. We re-map + * them to the merged partition with the smaller of the two merged + * indexes to preserve the property that the canonical order of + * list partitions is determined by the indexes assigned to the + * smallest list value of each partition. + */ + if (outer_merged_index < inner_merged_index) + { + outer_map->merged[outer_index] = true; + inner_map->merged_indexes[inner_index] = outer_merged_index; + inner_map->merged[inner_index] = true; + inner_map->did_remapping = true; + inner_map->old_indexes[inner_index] = inner_merged_index; + return outer_merged_index; + } + else + { + inner_map->merged[inner_index] = true; + outer_map->merged_indexes[outer_index] = inner_merged_index; + outer_map->merged[outer_index] = true; + outer_map->did_remapping = true; + outer_map->old_indexes[outer_index] = outer_merged_index; + return inner_merged_index; + } + } + return -1; + } + + /* At least one of the given partitions should not have yet been merged. */ + Assert(outer_merged_index == -1 || inner_merged_index == -1); + + /* + * If neither of them has been merged, merge them. Otherwise, if one has + * been merged with a dummy relation on the other side (and the other + * hasn't yet been merged with anything), re-merge them. Otherwise, they + * can't be merged, so return -1. + */ + if (outer_merged_index == -1 && inner_merged_index == -1) + { + int merged_index = *next_index; + + Assert(!outer_merged); + Assert(!inner_merged); + outer_map->merged_indexes[outer_index] = merged_index; + outer_map->merged[outer_index] = true; + inner_map->merged_indexes[inner_index] = merged_index; + inner_map->merged[inner_index] = true; + *next_index = *next_index + 1; + return merged_index; + } + if (outer_merged_index >= 0 && !outer_map->merged[outer_index]) + { + Assert(inner_merged_index == -1); + Assert(!inner_merged); + inner_map->merged_indexes[inner_index] = outer_merged_index; + inner_map->merged[inner_index] = true; + outer_map->merged[outer_index] = true; + return outer_merged_index; + } + if (inner_merged_index >= 0 && !inner_map->merged[inner_index]) + { + Assert(outer_merged_index == -1); + Assert(!outer_merged); + outer_map->merged_indexes[outer_index] = inner_merged_index; + outer_map->merged[outer_index] = true; + inner_map->merged[inner_index] = true; + return inner_merged_index; + } + return -1; +} + +/* + * process_outer_partition + * Try to assign given outer partition a merged partition, and return the + * index of the merged partition if successful, -1 otherwise + * + * If the partition is newly created, *next_index is incremented. Also, if it + * is the default partition of the join relation, *default_index is set to the + * index if not already done. + */ +static int +process_outer_partition(PartitionMap *outer_map, + PartitionMap *inner_map, + bool outer_has_default, + bool inner_has_default, + int outer_index, + int inner_default, + JoinType jointype, + int *next_index, + int *default_index) +{ + int merged_index = -1; + + Assert(outer_index >= 0); + + /* + * If the inner side has the default partition, a row from the outer + * partition might find its join partner in the default partition; try + * merging the outer partition with the default partition. Otherwise, this + * should be an outer join, in which case the outer partition has to be + * scanned all the way anyway; merge the outer partition with a dummy + * partition on the other side. + */ + if (inner_has_default) + { + Assert(inner_default >= 0); + + /* + * If the outer side has the default partition as well, the default + * partition on the inner side will have two matching partitions on the + * other side: the outer partition and the default partition on the + * outer side. Partitionwise join doesn't handle this scenario yet. + */ + if (outer_has_default) + return -1; + + merged_index = merge_matching_partitions(outer_map, inner_map, + outer_index, inner_default, + next_index); + if (merged_index == -1) + return -1; + + /* + * If this is a FULL join, the default partition on the inner side + * has to be scanned all the way anyway, so the resulting partition + * will contain all key values from the default partition, which any + * other partition of the join relation will not contain. Thus the + * resulting partition will act as the default partition of the join + * relation; record the index in *default_index if not already done. + */ + if (jointype == JOIN_FULL) + { + if (*default_index == -1) + *default_index = merged_index; + else + Assert(*default_index == merged_index); + } + } + else + { + Assert(IS_OUTER_JOIN(jointype)); + Assert(jointype != JOIN_RIGHT); + + /* If we have already assigned a partition, no need to do anything. */ + merged_index = outer_map->merged_indexes[outer_index]; + if (merged_index == -1) + merged_index = merge_partition_with_dummy(outer_map, outer_index, + next_index); + } + return merged_index; +} + +/* + * process_inner_partition + * Try to assign given inner partition a merged partition, and return the + * index of the merged partition if successful, -1 otherwise + * + * If the partition is newly created, *next_index is incremented. Also, if it + * is the default partition of the join relation, *default_index is set to the + * index if not already done. + */ +static int +process_inner_partition(PartitionMap *outer_map, + PartitionMap *inner_map, + bool outer_has_default, + bool inner_has_default, + int inner_index, + int outer_default, + JoinType jointype, + int *next_index, + int *default_index) +{ + int merged_index = -1; + + Assert(inner_index >= 0); + + /* + * If the outer side has the default partition, a row from the inner + * partition might find its join partner in the default partition; try + * merging the inner partition with the default partition. Otherwise, this + * should be a FULL join, in which case the inner partition has to be + * scanned all the way anyway; merge the inner partition with a dummy + * partition on the other side. + */ + if (outer_has_default) + { + Assert(outer_default >= 0); + + /* + * If the inner side has the default partition as well, the default + * partition on the outer side will have two matching partitions on the + * other side: the inner partition and the default partition on the + * inner side. Partitionwise join doesn't handle this scenario yet. + */ + if (inner_has_default) + return -1; + + merged_index = merge_matching_partitions(outer_map, inner_map, + outer_default, inner_index, + next_index); + if (merged_index == -1) + return -1; + + /* + * If this is an outer join, the default partition on the outer side + * has to be scanned all the way anyway, so the resulting partition + * will contain all key values from the default partition, which any + * other partition of the join relation will not contain. Thus the + * resulting partition will act as the default partition of the join + * relation; record the index in *default_index if not already done. + */ + if (IS_OUTER_JOIN(jointype)) + { + Assert(jointype != JOIN_RIGHT); + if (*default_index == -1) + *default_index = merged_index; + else + Assert(*default_index == merged_index); + } + } + else + { + Assert(jointype == JOIN_FULL); + + /* If we have already assigned a partition, no need to do anything. */ + merged_index = inner_map->merged_indexes[inner_index]; + if (merged_index == -1) + merged_index = merge_partition_with_dummy(inner_map, inner_index, + next_index); + } + return merged_index; +} + +/* + * merge_null_partitions + * Merge the NULL partitions from a join's outer and inner sides. + * + * If the merged partition produced from them is the NULL partition of the join + * relation, *null_index is set to the index of the merged partition. + * + * Note: We assume here that the join clause for a partitioned join is strict + * because have_partkey_equi_join() requires that the corresponding operator + * be mergejoinable, and we currently assume that mergejoinable operators are + * strict (see MJEvalOuterValues()/MJEvalInnerValues()). + */ +static void +merge_null_partitions(PartitionMap *outer_map, + PartitionMap *inner_map, + bool outer_has_null, + bool inner_has_null, + int outer_null, + int inner_null, + JoinType jointype, + int *next_index, + int *null_index) +{ + bool consider_outer_null = false; + bool consider_inner_null = false; + + Assert(outer_has_null || inner_has_null); + Assert(*null_index == -1); + + /* + * Check whether the NULL partitions have already been merged and if so, + * set the consider_outer_null/consider_inner_null flags. + */ + if (outer_has_null) + { + Assert(outer_null >= 0 && outer_null < outer_map->nparts); + if (outer_map->merged_indexes[outer_null] == -1) + consider_outer_null = true; + } + if (inner_has_null) + { + Assert(inner_null >= 0 && inner_null < inner_map->nparts); + if (inner_map->merged_indexes[inner_null] == -1) + consider_inner_null = true; + } + + /* If both flags are set false, we don't need to do anything. */ + if (!consider_outer_null && !consider_inner_null) + return; + + if (consider_outer_null && !consider_inner_null) + { + Assert(outer_has_null); + + /* + * If this is an outer join, the NULL partition on the outer side has + * to be scanned all the way anyway; merge the NULL partition with a + * dummy partition on the other side. In that case consider_outer_null + * means that the NULL partition only contains NULL values as the key + * values, so the merged partition will do so; treat it as the NULL + * partition of the join relation. + */ + if (IS_OUTER_JOIN(jointype)) + { + Assert(jointype != JOIN_RIGHT); + *null_index = merge_partition_with_dummy(outer_map, outer_null, + next_index); + } + } + else if (!consider_outer_null && consider_inner_null) + { + Assert(inner_has_null); + + /* + * If this is a FULL join, the NULL partition on the inner side has + * to be scanned all the way anyway; merge the NULL partition with a + * dummy partition on the other side. In that case consider_inner_null + * means that the NULL partition only contains NULL values as the key + * values, so the merged partition will do so; treat it as the NULL + * partition of the join relation. + */ + if (jointype == JOIN_FULL) + *null_index = merge_partition_with_dummy(inner_map, inner_null, + next_index); + } + else + { + Assert(consider_outer_null && consider_inner_null); + Assert(outer_has_null); + Assert(inner_has_null); + + /* + * If this is an outer join, the NULL partition on the outer side (and + * that on the inner side if this is a FULL join) have to be scanned + * all the way anyway, so merge them. Note that each of the NULL + * partitions isn't merged yet, so they should be merged successfully. + * Like the above, each of the NULL partitions only contains NULL + * values as the key values, so the merged partition will do so; treat + * it as the NULL partition of the join relation. + * + * Note: if this an INNER/SEMI join, the join clause will never be + * satisfied by two NULL values (see comments above), so both the NULL + * partitions can be eliminated. + */ + if (IS_OUTER_JOIN(jointype)) + { + Assert(jointype != JOIN_RIGHT); + *null_index = merge_matching_partitions(outer_map, inner_map, + outer_null, inner_null, + next_index); + Assert(*null_index >= 0); + } + } +} + +/* + * merge_default_partitions + * Merge the default partitions from a join's outer and inner sides. + * + * If the merged partition produced from them is the default partition of the + * join relation, *default_index is set to the index of the merged partition. + */ +static void +merge_default_partitions(PartitionMap *outer_map, + PartitionMap *inner_map, + bool outer_has_default, + bool inner_has_default, + int outer_default, + int inner_default, + JoinType jointype, + int *next_index, + int *default_index) +{ + int outer_merged_index = -1; + int inner_merged_index = -1; + + Assert(outer_has_default || inner_has_default); + + /* Get the merged partition indexes for the default partitions. */ + if (outer_has_default) + { + Assert(outer_default >= 0 && outer_default < outer_map->nparts); + outer_merged_index = outer_map->merged_indexes[outer_default]; + } + if (inner_has_default) + { + Assert(inner_default >= 0 && inner_default < inner_map->nparts); + inner_merged_index = inner_map->merged_indexes[inner_default]; + } + + if (outer_has_default && !inner_has_default) + { + /* + * If this is an outer join, the default partition on the outer side + * has to be scanned all the way anyway; if we have not yet assigned a + * partition, merge the default partition with a dummy partition on the + * other side. The merged partition will act as the default partition + * of the join relation (see comments in process_inner_partition()). + */ + if (IS_OUTER_JOIN(jointype)) + { + Assert(jointype != JOIN_RIGHT); + if (outer_merged_index == -1) + { + Assert(*default_index == -1); + *default_index = merge_partition_with_dummy(outer_map, + outer_default, + next_index); + } + else + Assert(*default_index == outer_merged_index); + } + else + Assert(*default_index == -1); + } + else if (!outer_has_default && inner_has_default) + { + /* + * If this is a FULL join, the default partition on the inner side + * has to be scanned all the way anyway; if we have not yet assigned a + * partition, merge the default partition with a dummy partition on the + * other side. The merged partition will act as the default partition + * of the join relation (see comments in process_outer_partition()). + */ + if (jointype == JOIN_FULL) + { + if (inner_merged_index == -1) + { + Assert(*default_index == -1); + *default_index = merge_partition_with_dummy(inner_map, + inner_default, + next_index); + } + else + Assert(*default_index == inner_merged_index); + } + else + Assert(*default_index == -1); + } + else + { + Assert(outer_has_default && inner_has_default); + + /* + * The default partitions have to be joined with each other, so merge + * them. Note that each of the default partitions isn't merged yet + * (see, process_outer_partition()/process_innerer_partition()), so + * they should be merged successfully. The merged partition will act + * as the default partition of the join relation. + */ + Assert(outer_merged_index == -1); + Assert(inner_merged_index == -1); + Assert(*default_index == -1); + *default_index = merge_matching_partitions(outer_map, + inner_map, + outer_default, + inner_default, + next_index); + Assert(*default_index >= 0); + } +} + +/* + * merge_partition_with_dummy + * Assign given partition a new partition of a join relation + * + * Note: The caller assumes that the given partition doesn't have a non-dummy + * matching partition on the other side, but if the given partition finds the + * matching partition later, we will adjust the assignment. + */ +static int +merge_partition_with_dummy(PartitionMap *map, int index, int *next_index) +{ + int merged_index = *next_index; + + Assert(index >= 0 && index < map->nparts); + Assert(map->merged_indexes[index] == -1); + Assert(!map->merged[index]); + map->merged_indexes[index] = merged_index; + /* Leave the merged flag alone! */ + *next_index = *next_index + 1; + return merged_index; +} + +/* + * fix_merged_indexes + * Adjust merged indexes of re-merged partitions + */ +static void +fix_merged_indexes(PartitionMap *outer_map, PartitionMap *inner_map, + int nmerged, List *merged_indexes) +{ + int *new_indexes; + int merged_index; + int i; + ListCell *lc; + + Assert(nmerged > 0); + + new_indexes = (int *) palloc(sizeof(int) * nmerged); + for (i = 0; i < nmerged; i++) + new_indexes[i] = -1; + + /* Build the mapping of old merged indexes to new merged indexes. */ + if (outer_map->did_remapping) + { + for (i = 0; i < outer_map->nparts; i++) + { + merged_index = outer_map->old_indexes[i]; + if (merged_index >= 0) + new_indexes[merged_index] = outer_map->merged_indexes[i]; + } + } + if (inner_map->did_remapping) + { + for (i = 0; i < inner_map->nparts; i++) + { + merged_index = inner_map->old_indexes[i]; + if (merged_index >= 0) + new_indexes[merged_index] = inner_map->merged_indexes[i]; + } + } + + /* Fix the merged_indexes list using the mapping. */ + foreach(lc, merged_indexes) + { + merged_index = lfirst_int(lc); + Assert(merged_index >= 0); + if (new_indexes[merged_index] >= 0) + lfirst_int(lc) = new_indexes[merged_index]; + } + + pfree(new_indexes); +} + +/* + * generate_matching_part_pairs + * Generate a pair of lists of partitions that produce merged partitions + * + * The lists of partitions are built in the order of merged partition indexes, + * and returned in *outer_parts and *inner_parts. + */ +static void +generate_matching_part_pairs(RelOptInfo *outer_rel, RelOptInfo *inner_rel, + PartitionMap *outer_map, PartitionMap *inner_map, + int nmerged, + List **outer_parts, List **inner_parts) +{ + int outer_nparts = outer_map->nparts; + int inner_nparts = inner_map->nparts; + int *outer_indexes; + int *inner_indexes; + int max_nparts; + int i; + + Assert(nmerged > 0); + Assert(*outer_parts == NIL); + Assert(*inner_parts == NIL); + + outer_indexes = (int *) palloc(sizeof(int) * nmerged); + inner_indexes = (int *) palloc(sizeof(int) * nmerged); + for (i = 0; i < nmerged; i++) + outer_indexes[i] = inner_indexes[i] = -1; + + /* Set pairs of matching partitions. */ + Assert(outer_nparts == outer_rel->nparts); + Assert(inner_nparts == inner_rel->nparts); + max_nparts = Max(outer_nparts, inner_nparts); + for (i = 0; i < max_nparts; i++) + { + if (i < outer_nparts) + { + int merged_index = outer_map->merged_indexes[i]; + + if (merged_index >= 0) + { + Assert(merged_index < nmerged); + outer_indexes[merged_index] = i; + } + } + if (i < inner_nparts) + { + int merged_index = inner_map->merged_indexes[i]; + + if (merged_index >= 0) + { + Assert(merged_index < nmerged); + inner_indexes[merged_index] = i; + } + } + } + + /* Build the list pairs. */ + for (i = 0; i < nmerged; i++) + { + int outer_index = outer_indexes[i]; + int inner_index = inner_indexes[i]; + + /* + * If both partitions are dummy, it means the merged partition that had + * been assigned to the outer/inner partition was removed when + * re-merging the outer/inner partition in merge_matching_partitions(); + * ignore the merged partition. + */ + if (outer_index == -1 && inner_index == -1) + continue; + + *outer_parts = lappend(*outer_parts, outer_index >= 0 ? + outer_rel->part_rels[outer_index] : NULL); + *inner_parts = lappend(*inner_parts, inner_index >= 0 ? + inner_rel->part_rels[inner_index] : NULL); + } + + pfree(outer_indexes); + pfree(inner_indexes); +} + +/* + * build_merged_partition_bounds + * Create a PartitionBoundInfo struct from merged partition bounds + */ +static PartitionBoundInfo +build_merged_partition_bounds(char strategy, List *merged_datums, + List *merged_kinds, List *merged_indexes, + int null_index, int default_index) +{ + PartitionBoundInfo merged_bounds; + int ndatums = list_length(merged_datums); + int pos; + ListCell *lc; + + merged_bounds = (PartitionBoundInfo) palloc(sizeof(PartitionBoundInfoData)); + merged_bounds->strategy = strategy; + merged_bounds->ndatums = ndatums; + + merged_bounds->datums = (Datum **) palloc(sizeof(Datum *) * ndatums); + pos = 0; + foreach(lc, merged_datums) + merged_bounds->datums[pos++] = (Datum *) lfirst(lc); + + if (strategy == PARTITION_STRATEGY_RANGE) + { + Assert(list_length(merged_kinds) == ndatums); + merged_bounds->kind = (PartitionRangeDatumKind **) + palloc(sizeof(PartitionRangeDatumKind *) * ndatums); + pos = 0; + foreach(lc, merged_kinds) + merged_bounds->kind[pos++] = (PartitionRangeDatumKind *) lfirst(lc); + + /* There are ndatums+1 indexes in the case of range partitioning. */ + merged_indexes = lappend_int(merged_indexes, -1); + ndatums++; + } + else + { + Assert(strategy == PARTITION_STRATEGY_LIST); + Assert(merged_kinds == NIL); + merged_bounds->kind = NULL; + } + + Assert(list_length(merged_indexes) == ndatums); + merged_bounds->indexes = (int *) palloc(sizeof(int) * ndatums); + pos = 0; + foreach(lc, merged_indexes) + merged_bounds->indexes[pos++] = lfirst_int(lc); + + merged_bounds->null_index = null_index; + merged_bounds->default_index = default_index; + + return merged_bounds; +} + +/* + * get_range_partition + * Get the next non-dummy partition of a range-partitioned relation, + * returning the index of that partition + * + * *lb and *ub are set to the lower and upper bounds of that partition + * respectively, and *lb_pos is advanced to the next lower bound, if any. + */ +static int +get_range_partition(RelOptInfo *rel, + PartitionBoundInfo bi, + int *lb_pos, + PartitionRangeBound *lb, + PartitionRangeBound *ub) +{ + int part_index; + + Assert(bi->strategy == PARTITION_STRATEGY_RANGE); + + do { + part_index = get_range_partition_internal(bi, lb_pos, lb, ub); + if (part_index == -1) + return -1; + } while (is_dummy_partition(rel, part_index)); + + return part_index; +} + +static int +get_range_partition_internal(PartitionBoundInfo bi, + int *lb_pos, + PartitionRangeBound *lb, + PartitionRangeBound *ub) +{ + /* Return the index as -1 if we've exhausted all lower bounds. */ + if (*lb_pos >= bi->ndatums) + return -1; + + /* A lower bound should have at least one more bound after it. */ + Assert(*lb_pos + 1 < bi->ndatums); + + /* Set the lower bound. */ + lb->index = bi->indexes[*lb_pos]; + lb->datums = bi->datums[*lb_pos]; + lb->kind = bi->kind[*lb_pos]; + lb->lower = true; + /* Set the upper bound. */ + ub->index = bi->indexes[*lb_pos + 1]; + ub->datums = bi->datums[*lb_pos + 1]; + ub->kind = bi->kind[*lb_pos + 1]; + ub->lower = false; + + /* The index assigned to an upper bound should be valid. */ + Assert(ub->index >= 0); + + /* + * Advance the position to the next lower bound. If there are no bounds + * left beyond the upper bound, we have reached the last lower bound. + */ + if (*lb_pos + 2 >= bi->ndatums) + *lb_pos = bi->ndatums; + else + { + /* + * If the index assigned to the bound next to the upper bound isn't + * valid, that is the next lower bound; else, the upper bound is also + * the lower bound of the next range partition. + */ + if (bi->indexes[*lb_pos + 2] < 0) + *lb_pos = *lb_pos + 2; + else + *lb_pos = *lb_pos + 1; + } + + return ub->index; +} + +/* + * compare_range_partitions + * Compare the bounds of two range partitions, and return true if the + * two partitions overlap, false otherwise + * + * *lb_cmpval is set to -1, 0, or 1 if the outer partition's lower bound is + * lower than, equal to, or higher than the inner partition's lower bound + * respectively. Likewise, *ub_cmpval is set to -1, 0, or 1 if the outer + * partition's upper bound is lower than, equal to, or higher than the inner + * partition's upper bound respectively. + */ +static bool +compare_range_partitions(int partnatts, FmgrInfo *partsupfuncs, + Oid *partcollations, + PartitionRangeBound *outer_lb, + PartitionRangeBound *outer_ub, + PartitionRangeBound *inner_lb, + PartitionRangeBound *inner_ub, + int *lb_cmpval, int *ub_cmpval) +{ + /* + * Check if the outer partition's upper bound is lower than the inner + * partition's lower bound; if so the partitions aren't overlapping. + */ + if (compare_range_bounds(partnatts, partsupfuncs, partcollations, + outer_ub, inner_lb) < 0) + { + *lb_cmpval = -1; + *ub_cmpval = -1; + return false; + } + + /* + * Check if the outer partition's lower bound is higher than the inner + * partition's upper bound; if so the partitions aren't overlapping. + */ + if (compare_range_bounds(partnatts, partsupfuncs, partcollations, + outer_lb, inner_ub) > 0) + { + *lb_cmpval = 1; + *ub_cmpval = 1; + return false; + } + + /* All other cases indicate overlapping partitions. */ + *lb_cmpval = compare_range_bounds(partnatts, partsupfuncs, partcollations, + outer_lb, inner_lb); + *ub_cmpval = compare_range_bounds(partnatts, partsupfuncs, partcollations, + outer_ub, inner_ub); + return true; +} + +/* + * get_merged_range_bounds + * Given the bounds of range partitions to be joined, determine the bounds + * of a merged partition produced from the range partitions + * + * *merged_lb and *merged_ub are set to the lower and upper bounds of the + * merged partition. + */ +static void +get_merged_range_bounds(int partnatts, FmgrInfo *partsupfuncs, + Oid *partcollations, JoinType jointype, + PartitionRangeBound *outer_lb, + PartitionRangeBound *outer_ub, + PartitionRangeBound *inner_lb, + PartitionRangeBound *inner_ub, + int lb_cmpval, int ub_cmpval, + PartitionRangeBound *merged_lb, + PartitionRangeBound *merged_ub) +{ + Assert(compare_range_bounds(partnatts, partsupfuncs, partcollations, + outer_lb, inner_lb) == lb_cmpval); + Assert(compare_range_bounds(partnatts, partsupfuncs, partcollations, + outer_ub, inner_ub) == ub_cmpval); + + switch (jointype) + { + case JOIN_INNER: + case JOIN_SEMI: + + /* + * An INNER/SEMI join will have the rows that fit both sides, so + * the lower bound of the merged partition will be the higher of + * the two lower bounds, and the upper bound of the merged + * partition will be the lower of the two upper bounds. + */ + *merged_lb = (lb_cmpval > 0) ? *outer_lb : *inner_lb; + *merged_ub = (ub_cmpval < 0) ? *outer_ub : *inner_ub; + break; + + case JOIN_LEFT: + case JOIN_ANTI: + + /* + * A LEFT/ANTI join will have all the rows from the outer side, so + * the bounds of the merged partition will be the same as the outer + * bounds. + */ + *merged_lb = *outer_lb; + *merged_ub = *outer_ub; + break; + + case JOIN_FULL: + + /* + * A FULL join will have all the rows from both sides, so the lower + * bound of the merged partition will be the lower of the two lower + * bounds, and the upper bound of the merged partition will be the + * higher of the two upper bounds. + */ + *merged_lb = (lb_cmpval < 0) ? *outer_lb : *inner_lb; + *merged_ub = (ub_cmpval > 0) ? *outer_ub : *inner_ub; + break; + + default: + elog(ERROR, "unrecognized join type: %d", (int) jointype); + } +} + +/* + * add_merged_range_bounds + * Add the bounds of a merged partition to the lists of range bounds + */ +static void +add_merged_range_bounds(int partnatts, FmgrInfo *partsupfuncs, + Oid *partcollations, + PartitionRangeBound *merged_lb, + PartitionRangeBound *merged_ub, + int merged_index, + List **merged_datums, + List **merged_kinds, + List **merged_indexes) +{ + int cmpval; + + if (!*merged_datums) + { + /* First merged partition */ + Assert(!*merged_kinds); + Assert(!*merged_indexes); + cmpval = 1; + } + else + { + PartitionRangeBound prev_ub; + + Assert(*merged_datums); + Assert(*merged_kinds); + Assert(*merged_indexes); + + /* Get the last upper bound. */ + prev_ub.index = llast_int(*merged_indexes); + prev_ub.datums = (Datum *) llast(*merged_datums); + prev_ub.kind = (PartitionRangeDatumKind *) llast(*merged_kinds); + prev_ub.lower = false; + + /* + * We pass to partition_rbound_cmp() lower1 as false to prevent it + * from considering the last upper bound to be smaller than the lower + * bound of the merged partition when the values of the two range + * bounds compare equal. + */ + cmpval = partition_rbound_cmp(partnatts, partsupfuncs, partcollations, + merged_lb->datums, merged_lb->kind, + false, &prev_ub); + Assert(cmpval >= 0); + } + + /* + * If the lower bound is higher than the last upper bound, add the lower + * bound with the index as -1 indicating that that is a lower bound; else, + * the last upper bound will be reused as the lower bound of the merged + * partition, so skip this. + */ + if (cmpval > 0) + { + *merged_datums = lappend(*merged_datums, merged_lb->datums); + *merged_kinds = lappend(*merged_kinds, merged_lb->kind); + *merged_indexes = lappend_int(*merged_indexes, -1); + } + + /* Add the upper bound and index of the merged partition. */ + *merged_datums = lappend(*merged_datums, merged_ub->datums); + *merged_kinds = lappend(*merged_kinds, merged_ub->kind); + *merged_indexes = lappend_int(*merged_indexes, merged_index); +} + +/* * partitions_are_ordered * Determine whether the partitions described by 'boundinfo' are ordered, * that is partitions appearing earlier in the PartitionDesc sequence |