parallel_mergejoin_v3.patch

diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c
index b5cbcf4..a29fb0e 100644
--- a/src/backend/optimizer/path/joinpath.c
+++ b/src/backend/optimizer/path/joinpath.c
@@ -58,7 +58,9 @@ static void generate_mergejoin_paths(PlannerInfo *root,
 						 JoinPathExtraData *extra,
 						 bool useallclauses,
 						 Path *inner_cheapest_total,
-						 List *merge_pathkeys);
+						 List *merge_pathkeys,
+						 bool is_partial);
+
 
 
 /*
@@ -481,6 +483,76 @@ try_mergejoin_path(PlannerInfo *root,
 }
 
 /*
+ * try_partial_mergejoin_path
+ *	  Consider a partial merge join path; if it appears useful, push it into
+ *	  the joinrel's pathlist via add_path().
+ */
+static void
+try_partial_mergejoin_path(PlannerInfo *root,
+				   RelOptInfo *joinrel,
+				   Path *outer_path,
+				   Path *inner_path,
+				   List *pathkeys,
+				   List *mergeclauses,
+				   List *outersortkeys,
+				   List *innersortkeys,
+				   JoinType jointype,
+				   JoinPathExtraData *extra)
+{
+	JoinCostWorkspace workspace;
+
+	/*
+	 * See comments in try_partial_nestloop_path().
+	 */
+	Assert(bms_is_empty(joinrel->lateral_relids));
+	if (inner_path->param_info != NULL)
+	{
+		Relids		inner_paramrels = inner_path->param_info->ppi_req_outer;
+
+		if (!bms_is_subset(inner_paramrels, outer_path->parent->relids))
+			return;
+	}
+
+	/*
+	 * If the given paths are already well enough ordered, we can skip doing
+	 * an explicit sort.
+	 */
+	if (outersortkeys &&
+		pathkeys_contained_in(outersortkeys, outer_path->pathkeys))
+		outersortkeys = NIL;
+	if (innersortkeys &&
+		pathkeys_contained_in(innersortkeys, inner_path->pathkeys))
+		innersortkeys = NIL;
+
+	/*
+	 * See comments in try_nestloop_path().
+	 */
+	initial_cost_mergejoin(root, &workspace, jointype, mergeclauses,
+						   outer_path, inner_path,
+						   outersortkeys, innersortkeys,
+						   extra->sjinfo);
+
+	if (!add_partial_path_precheck(joinrel, workspace.total_cost, pathkeys))
+		return;
+
+	/* Might be good enough to be worth trying, so let's try it. */
+	add_partial_path(joinrel, (Path *)
+			 create_mergejoin_path(root,
+								   joinrel,
+								   jointype,
+								   &workspace,
+								   extra->sjinfo,
+								   outer_path,
+								   inner_path,
+								   extra->restrictlist,
+								   pathkeys,
+								   NULL,
+								   mergeclauses,
+								   outersortkeys,
+								   innersortkeys));
+}
+
+/*
  * try_hashjoin_path
  *	  Consider a hash join path; if it appears useful, push it into
  *	  the joinrel's pathlist via add_path().
@@ -649,6 +721,7 @@ sort_inner_and_outer(PlannerInfo *root,
 					 JoinType jointype,
 					 JoinPathExtraData *extra)
 {
+	JoinType	save_jointype = jointype;
 	Path	   *outer_path;
 	Path	   *inner_path;
 	List	   *all_pathkeys;
@@ -782,6 +855,37 @@ sort_inner_and_outer(PlannerInfo *root,
 						   innerkeys,
 						   jointype,
 						   extra);
+
+		/*
+		 * If the joinrel is parallel-safe, we may be able to consider a
+		 * partial merge join.  However, we can't handle JOIN_UNIQUE_OUTER,
+		 * because the outer path will be partial, and therefore we won't be
+		 * able to properly guarantee uniqueness.  Similarly, we can't handle
+		 * JOIN_FULL and JOIN_RIGHT, because they can produce false null
+		 * extended rows.  Also, the resulting path must not be parameterized.
+		 */
+		if (joinrel->consider_parallel &&
+			save_jointype != JOIN_UNIQUE_OUTER &&
+			jointype != JOIN_FULL &&
+			jointype != JOIN_RIGHT &&
+			outerrel->partial_pathlist != NIL &&
+			bms_is_empty(joinrel->lateral_relids) &&
+			inner_path->parallel_safe)
+		{
+			Path *cheapest_partial_outer =
+							(Path *) linitial(outerrel->partial_pathlist);
+
+			try_partial_mergejoin_path(root,
+									   joinrel,
+									   cheapest_partial_outer,
+									   inner_path,
+									   merge_pathkeys,
+									   cur_mergeclauses,
+									   outerkeys,
+									   innerkeys,
+									   jointype,
+									   extra);
+		}
 	}
 }
 
@@ -798,6 +902,8 @@ sort_inner_and_outer(PlannerInfo *root,
  * some sort key requirements).  So, we consider truncations of the
  * mergeclause list as well as the full list.  (Ideally we'd consider all
  * subsets of the mergeclause list, but that seems way too expensive.)
+ *
+ * is_partial passed true for generating partial merge join paths.
  */
 static void
 generate_mergejoin_paths(PlannerInfo *root,
@@ -808,7 +914,8 @@ generate_mergejoin_paths(PlannerInfo *root,
 						 JoinPathExtraData *extra,
 						 bool useallclauses,
 						 Path *inner_cheapest_total,
-						 List *merge_pathkeys)
+						 List *merge_pathkeys,
+						 bool is_partial)
 {
 	List	   *mergeclauses;
 	List	   *innersortkeys;
@@ -859,16 +966,30 @@ generate_mergejoin_paths(PlannerInfo *root,
 	 * try_mergejoin_path will do the right thing if inner_cheapest_total is
 	 * already correctly sorted.)
 	 */
-	try_mergejoin_path(root,
-					   joinrel,
-					   outerpath,
-					   inner_cheapest_total,
-					   merge_pathkeys,
-					   mergeclauses,
-					   NIL,
-					   innersortkeys,
-					   jointype,
-					   extra);
+	if (!is_partial)
+		try_mergejoin_path(root,
+						joinrel,
+						outerpath,
+						inner_cheapest_total,
+						merge_pathkeys,
+						mergeclauses,
+						NIL,
+						innersortkeys,
+						jointype,
+						extra);
+
+	/* Generate partial path if inner is parallel safe. */
+	else if (inner_cheapest_total->parallel_safe)
+		try_partial_mergejoin_path(root,
+						joinrel,
+						outerpath,
+						inner_cheapest_total,
+						merge_pathkeys,
+						mergeclauses,
+						NIL,
+						innersortkeys,
+						jointype,
+						extra);
 
 	/* Can't do anything else if inner path needs to be unique'd */
 	if (save_jointype == JOIN_UNIQUE_INNER)
@@ -955,16 +1076,30 @@ generate_mergejoin_paths(PlannerInfo *root,
 			}
 			else
 				newclauses = mergeclauses;
-			try_mergejoin_path(root,
-							   joinrel,
-							   outerpath,
-							   innerpath,
-							   merge_pathkeys,
-							   newclauses,
-							   NIL,
-							   NIL,
-							   jointype,
-							   extra);
+			if (!is_partial)
+				try_mergejoin_path(root,
+								joinrel,
+								outerpath,
+								innerpath,
+								merge_pathkeys,
+								newclauses,
+								NIL,
+								NIL,
+								jointype,
+								extra);
+			/* Generate partial path only if innerpath is parallel safe. */
+			else if (innerpath->parallel_safe)
+				try_partial_mergejoin_path(root,
+										   joinrel,
+										   outerpath,
+										   innerpath,
+										   merge_pathkeys,
+										   newclauses,
+										   NIL,
+										   NIL,
+										   jointype,
+										   extra);
+
 			cheapest_total_inner = innerpath;
 		}
 		/* Same on the basis of cheapest startup cost ... */
@@ -998,16 +1133,29 @@ generate_mergejoin_paths(PlannerInfo *root,
 					else
 						newclauses = mergeclauses;
 				}
-				try_mergejoin_path(root,
-								   joinrel,
-								   outerpath,
-								   innerpath,
-								   merge_pathkeys,
-								   newclauses,
-								   NIL,
-								   NIL,
-								   jointype,
-								   extra);
+				if (!is_partial)
+					try_mergejoin_path(root,
+									   joinrel,
+									   outerpath,
+									   innerpath,
+									   merge_pathkeys,
+									   newclauses,
+									   NIL,
+									   NIL,
+									   jointype,
+									   extra);
+				/* Generate partial path only if innerpath is parallel safe. */
+				else if (innerpath->parallel_safe)
+					try_partial_mergejoin_path(root,
+											   joinrel,
+											   outerpath,
+											   innerpath,
+											   merge_pathkeys,
+											   newclauses,
+											   NIL,
+											   NIL,
+											   jointype,
+											   extra);
 			}
 			cheapest_startup_inner = innerpath;
 		}
@@ -1219,22 +1367,55 @@ match_unsorted_outer(PlannerInfo *root,
 		/* Generate merge join paths */
 		generate_mergejoin_paths(root, joinrel, innerrel, outerpath,
 								 save_jointype, extra, useallclauses,
-								 inner_cheapest_total, merge_pathkeys);
+								 inner_cheapest_total, merge_pathkeys,
+								 false);
 	}
 
 	/*
-	 * If the joinrel is parallel-safe and the join type supports nested
-	 * loops, we may be able to consider a partial nestloop plan.  However, we
-	 * can't handle JOIN_UNIQUE_OUTER, because the outer path will be partial,
-	 * and therefore we won't be able to properly guarantee uniqueness.  Nor
-	 * can we handle extra_lateral_rels, since partial paths must not be
-	 * parameterized.
+	 * Consider partial nestloop and mergejoin plan if the joinrel is
+	 * parallel-safe. However, we can't handle JOIN_UNIQUE_OUTER, because
+	 * the outer path will be partial, and therefore we won't be able to
+	 * properly guarantee uniqueness.  Nor can we handle extra_lateral_rels,
+	 * since partial paths must not be parameterized.
+	 * Similarly, we can't handle JOIN_FULL and JOIN_RIGHT, because they
+	 * can produce false null extended rows.
 	 */
-	if (joinrel->consider_parallel && nestjoinOK &&
-		save_jointype != JOIN_UNIQUE_OUTER &&
-		bms_is_empty(joinrel->lateral_relids))
+	if (!joinrel->consider_parallel ||
+		save_jointype == JOIN_UNIQUE_OUTER ||
+		!bms_is_empty(joinrel->lateral_relids) ||
+		jointype == JOIN_FULL ||
+		jointype == JOIN_RIGHT)
+		return;
+
+	if (nestjoinOK)
 		consider_parallel_nestloop(root, joinrel, outerrel, innerrel,
 								   save_jointype, extra);
+
+	/* Can't generate mergejoin path if inner rel is parameterized by outer */
+	if (inner_cheapest_total != NULL)
+	{
+		ListCell   *lc1;
+
+		/* generate merge join path for each partial outer path */
+		foreach(lc1, outerrel->partial_pathlist)
+		{
+			Path	   *outerpath = (Path *) lfirst(lc1);
+			List	   *merge_pathkeys;
+
+			/*
+			 * Figure out what useful ordering any paths we create
+			 * will have.
+			 */
+			merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
+											   outerpath->pathkeys);
+
+			generate_mergejoin_paths(root, joinrel, innerrel, outerpath,
+									 save_jointype, extra, false,
+									 inner_cheapest_total, merge_pathkeys,
+									 true);
+		}
+
+	}
 }
 
 /*