Modify-partition-matching-algorithm-WIP.patch

diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index e6ce8e2110..a61b1741ec 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -2281,6 +2281,7 @@ _outRelOptInfo(StringInfo str, const RelOptInfo *node)
 	WRITE_BOOL_FIELD(has_eclass_joins);
 	WRITE_BOOL_FIELD(consider_partitionwise_join);
 	WRITE_BITMAPSET_FIELD(top_parent_relids);
+	WRITE_BITMAPSET_FIELD(all_partrels);
 	WRITE_NODE_FIELD(partitioned_child_rels);
 }
 
diff --git a/src/backend/optimizer/path/joinrels.c b/src/backend/optimizer/path/joinrels.c
index 52abd8a12f..6607fae57b 100644
--- a/src/backend/optimizer/path/joinrels.c
+++ b/src/backend/optimizer/path/joinrels.c
@@ -48,6 +48,9 @@ static SpecialJoinInfo *build_child_join_sjinfo(PlannerInfo *root,
 												Relids left_relids, Relids right_relids);
 static int	match_expr_to_partition_keys(Expr *expr, RelOptInfo *rel,
 										 bool strict_op);
+static void	get_matching_part_pairs(PlannerInfo *root, RelOptInfo *joinrel,
+						RelOptInfo *rel1, RelOptInfo *rel2,
+						List **parts1, List **parts2);
 
 
 /*
@@ -1357,8 +1360,6 @@ try_partitionwise_join(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2,
 {
 	bool		rel1_is_simple = IS_SIMPLE_REL(rel1);
 	bool		rel2_is_simple = IS_SIMPLE_REL(rel2);
-	PartitionScheme part_scheme;
-	PartitionBoundInfo join_boundinfo;
 	List	   *parts1;
 	List	   *parts2;
 	ListCell   *lc1;
@@ -1369,7 +1370,7 @@ try_partitionwise_join(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2,
 	check_stack_depth();
 
 	/* Nothing to do, if the join relation is not partitioned. */
-	if (joinrel->part_scheme == NULL)
+	if (joinrel->part_scheme == NULL || joinrel->nparts == 0)
 		return;
 
 	/* The join relation should have consider_partitionwise_join set. */
@@ -1394,51 +1395,51 @@ try_partitionwise_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;
 
 	/*
-	 * Get the list of matching partitions to be joined along with the
-	 * partition bounds of the join relation. Because of the restrictions
-	 * imposed by partition matching algorithm, not every pair of joining
-	 * relations for this join will be able to use partition-wise join. But all
-	 * those pairs which can use partition-wise join will produce the same
-	 * partition bounds for the join relation.
+	 * If we haven't created the partition bounds for the join relation yet,
+	 * create it along with the the list of matching partitions to be joined;
+	 * else generate the list of such partitions from the partitioning info
+	 * for the join relation we already have.
 	 */
-	join_boundinfo = partition_bounds_merge(part_scheme->partnatts,
-											part_scheme->parttyplen,
-											part_scheme->parttypbyval,
-											part_scheme->partsupfunc,
-											part_scheme->partcollation,
-											rel1, rel2,
-											parent_sjinfo->jointype,
-											&parts1, &parts2);
-
-	if (join_boundinfo == NULL)
-		return;
-
-	if (joinrel->boundinfo == NULL)
+	if (joinrel->nparts == -1)
 	{
-		Assert(joinrel->nparts == 0 && joinrel->part_rels == NULL);
-		joinrel->boundinfo = join_boundinfo;
-		joinrel->nparts = list_length(parts1);
-		Assert(joinrel->nparts == list_length(parts2));
+		PartitionBoundInfo boundinfo;
+		int			nparts;
+
+		Assert(joinrel->boundinfo == NULL);
+		boundinfo = partition_bounds_merge(joinrel->part_scheme->partnatts,
+										   joinrel->part_scheme->parttyplen,
+										   joinrel->part_scheme->parttypbyval,
+										   joinrel->part_scheme->partsupfunc,
+										   joinrel->part_scheme->partcollation,
+										   rel1, rel2,
+										   parent_sjinfo->jointype,
+										   &parts1, &parts2);
+		if (boundinfo == NULL)
+		{
+			joinrel->nparts = 0;
+			return;
+		}
+		joinrel->boundinfo = boundinfo;
+
+		Assert(list_length(parts1) == list_length(parts2));
+		nparts = list_length(parts1);
+		Assert(nparts > 0);
+		joinrel->nparts = nparts;
+		Assert(joinrel->part_rels == NULL);
 		joinrel->part_rels =
-			(RelOptInfo **) palloc0(sizeof(RelOptInfo *) *
-									joinrel->nparts);
+			(RelOptInfo **) palloc0(sizeof(RelOptInfo *) * nparts);
 	}
 	else
 	{
-		Assert(partition_bounds_equal(part_scheme->partnatts,
-									  part_scheme->parttyplen,
-									  part_scheme->parttypbyval,
-									  join_boundinfo, joinrel->boundinfo));
-		/*
-		 * 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));
+		Assert(joinrel->nparts > 0);
+		Assert(joinrel->boundinfo);
 		Assert(joinrel->part_rels);
+
+		get_matching_part_pairs(root, joinrel, rel1, rel2, &parts1, &parts2);
+		Assert(list_length(parts1) == joinrel->nparts);
+		Assert(list_length(parts2) == joinrel->nparts);
 	}
 
 	/*
@@ -1449,12 +1450,12 @@ try_partitionwise_join(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2,
 	cnt_parts = -1;
 	forboth(lc1, parts1, lc2, parts2)
 	{
-		int			part1 = lfirst_int(lc1);
-		int			part2 = lfirst_int(lc2);
-		RelOptInfo *child_rel1;
-		RelOptInfo *child_rel2;
-		bool		rel1_empty;
-		bool		rel2_empty;
+		RelOptInfo *child_rel1 = (RelOptInfo *) lfirst(lc1);
+		RelOptInfo *child_rel2 = (RelOptInfo *) lfirst(lc2);
+		bool		rel1_empty = (child_rel1 == NULL ||
+								  IS_DUMMY_REL(child_rel1));
+		bool		rel2_empty = (child_rel2 == NULL ||
+								  IS_DUMMY_REL(child_rel2));
 		SpecialJoinInfo *child_sjinfo;
 		List	   *child_restrictlist;
 		RelOptInfo *child_joinrel;
@@ -1462,11 +1463,6 @@ try_partitionwise_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];
-		rel1_empty = (child_rel1 == NULL || IS_DUMMY_REL(child_rel1));
-		rel2_empty = (child_rel2 == NULL || IS_DUMMY_REL(child_rel2));
 		cnt_parts++;
 
 		/*
@@ -1566,25 +1562,19 @@ try_partitionwise_join(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2,
 												 child_sjinfo,
 												 child_sjinfo->jointype);
 			joinrel->part_rels[cnt_parts] = child_joinrel;
+			joinrel->all_partrels = bms_add_members(joinrel->all_partrels,
+													child_joinrel->relids);
 		}
 
-		/*
-		 * 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,
 									child_joinrel, child_sjinfo,
 									child_restrictlist);
+
 	}
 
-	Assert(cnt_parts == (joinrel->nparts - 1));
+	Assert(cnt_parts == joinrel->nparts - 1);
 }
 
 /*
@@ -1793,3 +1783,70 @@ match_expr_to_partition_keys(Expr *expr, RelOptInfo *rel, bool strict_op)
 
 	return -1;
 }
+
+static void
+get_matching_part_pairs(PlannerInfo *root, RelOptInfo *joinrel,
+						RelOptInfo *rel1, RelOptInfo *rel2,
+						List **parts1, List **parts2)
+{
+	bool		rel1_is_simple = IS_SIMPLE_REL(rel1);
+	bool		rel2_is_simple = IS_SIMPLE_REL(rel2);
+	int 		cnt_parts;
+
+	*parts1 = NIL;
+	*parts2 = NIL;
+
+	for (cnt_parts = 0; cnt_parts < joinrel->nparts; cnt_parts++)
+	{
+		RelOptInfo *child_joinrel = joinrel->part_rels[cnt_parts];
+		RelOptInfo *child_rel1;
+		RelOptInfo *child_rel2;
+		Relids		child_relids1;
+		Relids		child_relids2;
+
+		/*
+		 * If the segment of the join is empty, it means that the segment was
+		 * ignored in the child-join creation step in try_partitionwise_join()
+		 * since it would not contribute to the join result, due to one or
+		 * both inputs being empty; add NULL for each list so that it will be
+		 * ignored again in that step.
+		 */
+		if (!child_joinrel)
+		{
+			*parts1 = lappend(*parts1, NULL);
+			*parts2 = lappend(*parts2, NULL);
+			continue;
+		}
+
+		child_relids1 = bms_intersect(child_joinrel->relids,
+									  rel1->all_partrels);
+		Assert(bms_num_members(child_relids1) == bms_num_members(rel1->relids));
+		if (rel1_is_simple)
+		{
+			int			varno = bms_singleton_member(child_relids1);
+
+			child_rel1 = find_base_rel(root, varno);
+		}
+		else
+			child_rel1 = find_join_rel(root, child_relids1);
+		/* We should have a rel for child_relids1 */
+		Assert(child_rel1);
+
+		child_relids2 = bms_intersect(child_joinrel->relids,
+									  rel2->all_partrels);
+		Assert(bms_num_members(child_relids2) == bms_num_members(rel2->relids));
+		if (rel2_is_simple)
+		{
+			int			varno = bms_singleton_member(child_relids2);
+
+			child_rel2 = find_base_rel(root, varno);
+		}
+		else
+			child_rel2 = find_join_rel(root, child_relids2);
+		/* We should have a rel for child_relids2 */
+		Assert(child_rel2);
+
+		*parts1 = lappend(*parts1, child_rel1);
+		*parts2 = lappend(*parts2, child_rel2);
+	}
+}
diff --git a/src/backend/optimizer/util/inherit.c b/src/backend/optimizer/util/inherit.c
index 38bc61e687..caf6039c10 100644
--- a/src/backend/optimizer/util/inherit.c
+++ b/src/backend/optimizer/util/inherit.c
@@ -376,6 +376,8 @@ expand_partitioned_rtentry(PlannerInfo *root, RelOptInfo *relinfo,
 		/* Create the otherrel RelOptInfo too. */
 		childrelinfo = build_simple_rel(root, childRTindex, relinfo);
 		relinfo->part_rels[i] = childrelinfo;
+		relinfo->all_partrels = bms_add_members(relinfo->all_partrels,
+												childrelinfo->relids);
 
 		/* If this child is itself partitioned, recurse */
 		if (childrel->rd_rel->relkind == RELKIND_PARTITIONED_TABLE)
diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c
index 1e883bc994..f9ac8ab82a 100644
--- a/src/backend/optimizer/util/relnode.c
+++ b/src/backend/optimizer/util/relnode.c
@@ -237,10 +237,11 @@ build_simple_rel(PlannerInfo *root, int relid, RelOptInfo *parent)
 	rel->has_eclass_joins = false;
 	rel->consider_partitionwise_join = false;	/* might get changed later */
 	rel->part_scheme = NULL;
-	rel->nparts = 0;
+	rel->nparts = -1;
 	rel->boundinfo = NULL;
 	rel->partition_qual = NIL;
 	rel->part_rels = NULL;
+	rel->all_partrels = NULL;
 	rel->partexprs = NULL;
 	rel->nullable_partexprs = NULL;
 	rel->partitioned_child_rels = NIL;
@@ -650,10 +651,11 @@ build_join_rel(PlannerInfo *root,
 	joinrel->consider_partitionwise_join = false;	/* might get changed later */
 	joinrel->top_parent_relids = NULL;
 	joinrel->part_scheme = NULL;
-	joinrel->nparts = 0;
+	joinrel->nparts = -1;
 	joinrel->boundinfo = NULL;
 	joinrel->partition_qual = NIL;
 	joinrel->part_rels = NULL;
+	joinrel->all_partrels = NULL;
 	joinrel->partexprs = NULL;
 	joinrel->nullable_partexprs = NULL;
 	joinrel->partitioned_child_rels = NIL;
@@ -826,10 +828,11 @@ build_child_join_rel(PlannerInfo *root, RelOptInfo *outer_rel,
 	joinrel->consider_partitionwise_join = false;	/* might get changed later */
 	joinrel->top_parent_relids = NULL;
 	joinrel->part_scheme = NULL;
-	joinrel->nparts = 0;
+	joinrel->nparts = -1;
 	joinrel->boundinfo = NULL;
 	joinrel->partition_qual = NIL;
 	joinrel->part_rels = NULL;
+	joinrel->all_partrels = NULL;
 	joinrel->partexprs = NULL;
 	joinrel->nullable_partexprs = NULL;
 	joinrel->partitioned_child_rels = NIL;
diff --git a/src/backend/partitioning/partbounds.c b/src/backend/partitioning/partbounds.c
index 88afc05a60..a5b3072c0f 100644
--- a/src/backend/partitioning/partbounds.c
+++ b/src/backend/partitioning/partbounds.c
@@ -128,11 +128,14 @@ static PartitionBoundInfo partition_hash_bounds_merge(int partnatts,
 							int16 *parttyplen, bool *parttypbyval,
 							RelOptInfo *outer_rel, RelOptInfo *inner_rel,
 							List **outer_parts, List **inner_parts);
-static void generate_matching_part_pairs(PartitionMap *outer_maps,
-										 PartitionMap *inner_maps,
-										 int nparts1, int nparts2,
-										 JoinType jointype, int nparts,
-										 List **parts1, List **parts2);
+static void	generate_matching_part_pairs(RelOptInfo *rel1,
+							 RelOptInfo *rel2,
+							 PartitionMap *partmaps1,
+							 PartitionMap *partmaps2,
+							 int nparts1, int nparts2,
+							 int nparts,
+							 List **matched_parts1,
+							 List **matched_parts2);
 static PartitionBoundInfo build_merged_partition_bounds(char strategy,
 							  List *merged_datums, List *merged_indexes,
 							  List *merged_contents, int null_index,
@@ -3839,9 +3842,10 @@ partition_range_bounds_merge(RelOptInfo *outer_rel, RelOptInfo *inner_rel,
 		return NULL;
 
 	/* Use maps to match partition from the joining relations. */
-	generate_matching_part_pairs(outer_maps, inner_maps,
+	generate_matching_part_pairs(outer_rel, inner_rel,
+								 outer_maps, inner_maps,
 								 outer_nparts, inner_nparts,
-								 jointype, next_index,
+								 next_index,
 								 outer_parts, inner_parts);
 
 	/* Craft a PartitionBoundInfo to return. */
@@ -4099,9 +4103,10 @@ partition_list_bounds_merge(FmgrInfo *partsupfunc, Oid *partcollation,
 		return NULL;
 
 	/* Use maps to match partition from the joining relations. */
-	generate_matching_part_pairs(outer_maps, inner_maps,
+	generate_matching_part_pairs(outer_rel, inner_rel,
+								 outer_maps, inner_maps,
 								 outer_nparts, inner_nparts,
-								 jointype, next_index,
+								 next_index,
 								 outer_parts, inner_parts);
 
 	/* Craft a PartitionBoundInfo to return. */
@@ -4170,8 +4175,8 @@ partition_hash_bounds_merge(int partnatts,
 	  */
 	for (cnt = 0; cnt < outer_rel->nparts; cnt++)
 	{
-		*outer_parts = lappend_int(*outer_parts, cnt);
-		*inner_parts = lappend_int(*inner_parts, cnt);
+		*outer_parts = lappend(*outer_parts, outer_rel->part_rels[cnt]);
+		*inner_parts = lappend(*inner_parts, inner_rel->part_rels[cnt]);
 	}
 
 	return outer_bi;
@@ -4312,12 +4317,11 @@ map_and_merge_partitions(PartitionMap *partmaps1, PartitionMap *partmaps2,
  * set to NIL.
  */
 static void
-generate_matching_part_pairs(PartitionMap *partmaps1, PartitionMap *partmaps2,
-							 int nparts1, int nparts2,
-							 JoinType jointype, int nparts,
+generate_matching_part_pairs(RelOptInfo *rel1, RelOptInfo *rel2,
+							 PartitionMap *partmaps1, PartitionMap *partmaps2,
+							 int nparts1, int nparts2, int nparts,
 							 List **matched_parts1, List **matched_parts2)
 {
-	bool		merged = true;
 	int		   *matching1,
 			   *matching2;
 	int 		i;
@@ -4358,16 +4362,6 @@ generate_matching_part_pairs(PartitionMap *partmaps1, PartitionMap *partmaps2,
 		}
 	}
 
-	/*
-	 * 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 (i = 0; i < nparts; i++)
 	{
 		int			part1 = matching1[i];
@@ -4376,52 +4370,14 @@ generate_matching_part_pairs(PartitionMap *partmaps1, PartitionMap *partmaps2,
 		/* 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_FULL:
-				if (part1 < 0 || part2 < 0)
-					merged = false;
-				break;
-
-			default:
-				elog(ERROR, "unrecognized join type: %d", (int) jointype);
-		}
-
-		if (!merged)
-			break;
-
-		*matched_parts1 = lappend_int(*matched_parts1, part1);
-		*matched_parts2 = lappend_int(*matched_parts2, part2);
+		*matched_parts1 = lappend(*matched_parts1,
+								  part1 >= 0 ? rel1->part_rels[part1] : NULL);
+		*matched_parts2 = lappend(*matched_parts2,
+								  part2 >= 0 ? rel2->part_rels[part2] : NULL);
 	}
 
 	pfree(matching1);
 	pfree(matching2);
-
-	if (!merged)
-	{
-		list_free(*matched_parts1);
-		list_free(*matched_parts2);
-		*matched_parts1 = NIL;
-		*matched_parts2 = NIL;
-	}
 }
 
 static PartitionBoundInfo
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index e3c579ee44..1d2dc68201 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -581,6 +581,7 @@ typedef struct PartitionSchemeData *PartitionScheme;
  *		boundinfo - Partition bounds
  *		partition_qual - Partition constraint if not the root
  *		part_rels - RelOptInfos for each partition
+ *		all_partrels - Relids set of all partition relids
  *		partexprs, nullable_partexprs - Partition key expressions
  *		partitioned_child_rels - RT indexes of unpruned partitions of
  *								 this relation that are partitioned tables
@@ -723,6 +724,7 @@ typedef struct RelOptInfo
 	List	   *partition_qual; /* partition constraint */
 	struct RelOptInfo **part_rels;	/* Array of RelOptInfos of partitions,
 									 * stored in the same order of bounds */
+	Relids		all_partrels;	/* Relids set of all partition relids */
 	List	  **partexprs;		/* Non-nullable partition key expressions. */
 	List	  **nullable_partexprs; /* Nullable partition key expressions. */
 	List	   *partitioned_child_rels; /* List of RT indexes. */