diff --git a/contrib/postgres_fdw/expected/postgres_fdw.out b/contrib/postgres_fdw/expected/postgres_fdw.out
index 50f1261..f9df294 100644
*** a/contrib/postgres_fdw/expected/postgres_fdw.out
--- b/contrib/postgres_fdw/expected/postgres_fdw.out
*************** EXPLAIN (VERBOSE, COSTS false)
*** 386,392 ****
  ---------------------------------------------------------------------------------------
   Limit
     Output: t1.c1, t2."C 1"
!    ->  Merge Join
           Output: t1.c1, t2."C 1"
           Merge Cond: (t1.c1 = t2."C 1")
           ->  Foreign Scan on public.ft2 t1
--- 386,392 ----
  ---------------------------------------------------------------------------------------
   Limit
     Output: t1.c1, t2."C 1"
!    ->  Merge Unique Inner Join
           Output: t1.c1, t2."C 1"
           Merge Cond: (t1.c1 = t2."C 1")
           ->  Foreign Scan on public.ft2 t1
*************** EXPLAIN (VERBOSE, COSTS false)
*** 419,425 ****
  ---------------------------------------------------------------------------------------
   Limit
     Output: t1.c1, t2."C 1"
!    ->  Merge Left Join
           Output: t1.c1, t2."C 1"
           Merge Cond: (t1.c1 = t2."C 1")
           ->  Foreign Scan on public.ft2 t1
--- 419,425 ----
  ---------------------------------------------------------------------------------------
   Limit
     Output: t1.c1, t2."C 1"
!    ->  Merge Unique Left Join
           Output: t1.c1, t2."C 1"
           Merge Cond: (t1.c1 = t2."C 1")
           ->  Foreign Scan on public.ft2 t1
*************** explain (verbose, costs off) select * fr
*** 2520,2526 ****
    where f.f3 = l.f3 COLLATE "POSIX" and l.f1 = 'foo';
                           QUERY PLAN                          
  -------------------------------------------------------------
!  Hash Join
     Output: f.f1, f.f2, f.f3, l.f1, l.f2, l.f3
     Hash Cond: ((f.f3)::text = (l.f3)::text)
     ->  Foreign Scan on public.ft3 f
--- 2520,2526 ----
    where f.f3 = l.f3 COLLATE "POSIX" and l.f1 = 'foo';
                           QUERY PLAN                          
  -------------------------------------------------------------
!  Hash Unique Inner Join
     Output: f.f1, f.f2, f.f3, l.f1, l.f2, l.f3
     Hash Cond: ((f.f3)::text = (l.f3)::text)
     ->  Foreign Scan on public.ft3 f
diff --git a/contrib/postgres_fdw/postgres_fdw.c b/contrib/postgres_fdw/postgres_fdw.c
index ee0220a..59084c6 100644
*** a/contrib/postgres_fdw/postgres_fdw.c
--- b/contrib/postgres_fdw/postgres_fdw.c
*************** foreign_join_ok(PlannerInfo *root, RelOp
*** 3923,3932 ****
  	/*
  	 * We support pushing down INNER, LEFT, RIGHT and FULL OUTER joins.
  	 * Constructing queries representing SEMI and ANTI joins is hard, hence
! 	 * not considered right now.
  	 */
  	if (jointype != JOIN_INNER && jointype != JOIN_LEFT &&
! 		jointype != JOIN_RIGHT && jointype != JOIN_FULL)
  		return false;
  
  	/*
--- 3923,3935 ----
  	/*
  	 * We support pushing down INNER, LEFT, RIGHT and FULL OUTER joins.
  	 * Constructing queries representing SEMI and ANTI joins is hard, hence
! 	 * not considered right now. INNER_UNIQUE and LEFT_UNIQUE joins are ok
! 	 * here, since they're merely an optimization their non-unique
! 	 * counterparts.
  	 */
  	if (jointype != JOIN_INNER && jointype != JOIN_LEFT &&
! 		jointype != JOIN_RIGHT && jointype != JOIN_FULL &&
! 		jointype != JOIN_INNER_UNIQUE && jointype != JOIN_LEFT_UNIQUE)
  		return false;
  
  	/*
*************** foreign_join_ok(PlannerInfo *root, RelOp
*** 4052,4057 ****
--- 4055,4061 ----
  	switch (jointype)
  	{
  		case JOIN_INNER:
+ 		case JOIN_INNER_UNIQUE:
  			fpinfo->remote_conds = list_concat(fpinfo->remote_conds,
  										  list_copy(fpinfo_i->remote_conds));
  			fpinfo->remote_conds = list_concat(fpinfo->remote_conds,
*************** foreign_join_ok(PlannerInfo *root, RelOp
*** 4059,4064 ****
--- 4063,4069 ----
  			break;
  
  		case JOIN_LEFT:
+ 		case JOIN_LEFT_UNIQUE:
  			fpinfo->joinclauses = list_concat(fpinfo->joinclauses,
  										  list_copy(fpinfo_i->remote_conds));
  			fpinfo->remote_conds = list_concat(fpinfo->remote_conds,
diff --git a/src/backend/commands/explain.c b/src/backend/commands/explain.c
index 713cd0e..e05925b 100644
*** a/src/backend/commands/explain.c
--- b/src/backend/commands/explain.c
*************** ExplainNode(PlanState *planstate, List *
*** 1118,1126 ****
--- 1118,1132 ----
  					case JOIN_INNER:
  						jointype = "Inner";
  						break;
+ 					case JOIN_INNER_UNIQUE:
+ 						jointype = "Unique Inner";
+ 						break;
  					case JOIN_LEFT:
  						jointype = "Left";
  						break;
+ 					case JOIN_LEFT_UNIQUE:
+ 						jointype = "Unique Left";
+ 						break;
  					case JOIN_FULL:
  						jointype = "Full";
  						break;
diff --git a/src/backend/executor/nodeHashjoin.c b/src/backend/executor/nodeHashjoin.c
index 369e666..196a075 100644
*** a/src/backend/executor/nodeHashjoin.c
--- b/src/backend/executor/nodeHashjoin.c
*************** ExecHashJoin(HashJoinState *node)
*** 306,315 ****
  					}
  
  					/*
! 					 * In a semijoin, we'll consider returning the first
! 					 * match, but after that we're done with this outer tuple.
  					 */
! 					if (node->js.jointype == JOIN_SEMI)
  						node->hj_JoinState = HJ_NEED_NEW_OUTER;
  
  					if (otherqual == NIL ||
--- 306,318 ----
  					}
  
  					/*
! 					 * In an inner unique, left unique or semi join, we'll
! 					 * consider returning the first match, but after that
! 					 * we're done with this outer tuple.
  					 */
! 					if (node->js.jointype == JOIN_INNER_UNIQUE ||
! 						node->js.jointype == JOIN_LEFT_UNIQUE ||
! 						node->js.jointype == JOIN_SEMI)
  						node->hj_JoinState = HJ_NEED_NEW_OUTER;
  
  					if (otherqual == NIL ||
*************** ExecInitHashJoin(HashJoin *node, EState 
*** 499,507 ****
--- 502,512 ----
  	switch (node->join.jointype)
  	{
  		case JOIN_INNER:
+ 		case JOIN_INNER_UNIQUE:
  		case JOIN_SEMI:
  			break;
  		case JOIN_LEFT:
+ 		case JOIN_LEFT_UNIQUE:
  		case JOIN_ANTI:
  			hjstate->hj_NullInnerTupleSlot =
  				ExecInitNullTupleSlot(estate,
diff --git a/src/backend/executor/nodeMergejoin.c b/src/backend/executor/nodeMergejoin.c
index 6db09b8..aa3e144 100644
*** a/src/backend/executor/nodeMergejoin.c
--- b/src/backend/executor/nodeMergejoin.c
*************** ExecMergeJoin(MergeJoinState *node)
*** 840,849 ****
  					}
  
  					/*
! 					 * In a semijoin, we'll consider returning the first
! 					 * match, but after that we're done with this outer tuple.
  					 */
! 					if (node->js.jointype == JOIN_SEMI)
  						node->mj_JoinState = EXEC_MJ_NEXTOUTER;
  
  					qualResult = (otherqual == NIL ||
--- 840,852 ----
  					}
  
  					/*
! 					 * In an inner unique, left unique or semi join, we'll
! 					 * consider returning the first match, but after that
! 					 * we're done with this outer tuple.
  					 */
! 					if (node->js.jointype == JOIN_INNER_UNIQUE ||
! 						node->js.jointype == JOIN_LEFT_UNIQUE ||
! 						node->js.jointype == JOIN_SEMI)
  						node->mj_JoinState = EXEC_MJ_NEXTOUTER;
  
  					qualResult = (otherqual == NIL ||
*************** ExecInitMergeJoin(MergeJoin *node, EStat
*** 1555,1564 ****
--- 1558,1569 ----
  	{
  		case JOIN_INNER:
  		case JOIN_SEMI:
+ 		case JOIN_INNER_UNIQUE:
  			mergestate->mj_FillOuter = false;
  			mergestate->mj_FillInner = false;
  			break;
  		case JOIN_LEFT:
+ 		case JOIN_LEFT_UNIQUE:
  		case JOIN_ANTI:
  			mergestate->mj_FillOuter = true;
  			mergestate->mj_FillInner = false;
diff --git a/src/backend/executor/nodeNestloop.c b/src/backend/executor/nodeNestloop.c
index 555fa09..0526170 100644
*** a/src/backend/executor/nodeNestloop.c
--- b/src/backend/executor/nodeNestloop.c
*************** ExecNestLoop(NestLoopState *node)
*** 182,187 ****
--- 182,188 ----
  
  			if (!node->nl_MatchedOuter &&
  				(node->js.jointype == JOIN_LEFT ||
+ 				 node->js.jointype == JOIN_LEFT_UNIQUE ||
  				 node->js.jointype == JOIN_ANTI))
  			{
  				/*
*************** ExecNestLoop(NestLoopState *node)
*** 247,256 ****
  			}
  
  			/*
! 			 * In a semijoin, we'll consider returning the first match, but
! 			 * after that we're done with this outer tuple.
  			 */
! 			if (node->js.jointype == JOIN_SEMI)
  				node->nl_NeedNewOuter = true;
  
  			if (otherqual == NIL || ExecQual(otherqual, econtext, false))
--- 248,260 ----
  			}
  
  			/*
! 			 * In an inner unique, left unique or semi join, we'll consider
! 			 * returning the first match, but after that we're done with this
! 			 * outer tuple.
  			 */
! 			if (node->js.jointype == JOIN_INNER_UNIQUE ||
! 				node->js.jointype == JOIN_LEFT_UNIQUE ||
! 				node->js.jointype == JOIN_SEMI)
  				node->nl_NeedNewOuter = true;
  
  			if (otherqual == NIL || ExecQual(otherqual, econtext, false))
*************** ExecInitNestLoop(NestLoop *node, EState 
*** 355,363 ****
--- 359,369 ----
  	switch (node->join.jointype)
  	{
  		case JOIN_INNER:
+ 		case JOIN_INNER_UNIQUE:
  		case JOIN_SEMI:
  			break;
  		case JOIN_LEFT:
+ 		case JOIN_LEFT_UNIQUE:
  		case JOIN_ANTI:
  			nlstate->nl_NullInnerTupleSlot =
  				ExecInitNullTupleSlot(estate,
diff --git a/src/backend/nodes/copyfuncs.c b/src/backend/nodes/copyfuncs.c
index a21928b..a2a91e5 100644
*** a/src/backend/nodes/copyfuncs.c
--- b/src/backend/nodes/copyfuncs.c
*************** _copySpecialJoinInfo(const SpecialJoinIn
*** 2065,2070 ****
--- 2065,2071 ----
  	COPY_BITMAPSET_FIELD(syn_lefthand);
  	COPY_BITMAPSET_FIELD(syn_righthand);
  	COPY_SCALAR_FIELD(jointype);
+ 	COPY_SCALAR_FIELD(optimal_jointype);
  	COPY_SCALAR_FIELD(lhs_strict);
  	COPY_SCALAR_FIELD(delay_upper_joins);
  	COPY_SCALAR_FIELD(semi_can_btree);
diff --git a/src/backend/nodes/equalfuncs.c b/src/backend/nodes/equalfuncs.c
index 3c6c567..3302a69 100644
*** a/src/backend/nodes/equalfuncs.c
--- b/src/backend/nodes/equalfuncs.c
*************** _equalSpecialJoinInfo(const SpecialJoinI
*** 837,842 ****
--- 837,843 ----
  	COMPARE_BITMAPSET_FIELD(syn_lefthand);
  	COMPARE_BITMAPSET_FIELD(syn_righthand);
  	COMPARE_SCALAR_FIELD(jointype);
+ 	COMPARE_SCALAR_FIELD(optimal_jointype);
  	COMPARE_SCALAR_FIELD(lhs_strict);
  	COMPARE_SCALAR_FIELD(delay_upper_joins);
  	COMPARE_SCALAR_FIELD(semi_can_btree);
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index f783a49..06323d4 100644
*** a/src/backend/nodes/outfuncs.c
--- b/src/backend/nodes/outfuncs.c
*************** _outSpecialJoinInfo(StringInfo str, cons
*** 2276,2281 ****
--- 2276,2282 ----
  	WRITE_BITMAPSET_FIELD(syn_lefthand);
  	WRITE_BITMAPSET_FIELD(syn_righthand);
  	WRITE_ENUM_FIELD(jointype, JoinType);
+ 	WRITE_ENUM_FIELD(optimal_jointype, JoinType);
  	WRITE_BOOL_FIELD(lhs_strict);
  	WRITE_BOOL_FIELD(delay_upper_joins);
  	WRITE_BOOL_FIELD(semi_can_btree);
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index 70a4c27..e4d5cc9 100644
*** a/src/backend/optimizer/path/costsize.c
--- b/src/backend/optimizer/path/costsize.c
*************** cost_group(Path *path, PlannerInfo *root
*** 1893,1900 ****
   * estimate and getting a tight lower bound.  We choose to not examine the
   * join quals here, since that's by far the most expensive part of the
   * calculations.  The end result is that CPU-cost considerations must be
!  * left for the second phase; and for SEMI/ANTI joins, we must also postpone
!  * incorporation of the inner path's run cost.
   *
   * 'workspace' is to be filled with startup_cost, total_cost, and perhaps
   *		other data to be used by final_cost_nestloop
--- 1893,1901 ----
   * estimate and getting a tight lower bound.  We choose to not examine the
   * join quals here, since that's by far the most expensive part of the
   * calculations.  The end result is that CPU-cost considerations must be
!  * left for the second phase; and for INNER_UNIQUE, LEFT_UNIQUE, SEMI, and
!  * ANTI joins, we must also postpone incorporation of the inner path's run
!  * cost.
   *
   * 'workspace' is to be filled with startup_cost, total_cost, and perhaps
   *		other data to be used by final_cost_nestloop
*************** cost_group(Path *path, PlannerInfo *root
*** 1902,1908 ****
   * 'outer_path' is the outer input to the join
   * 'inner_path' is the inner input to the join
   * 'sjinfo' is extra info about the join for selectivity estimation
!  * 'semifactors' contains valid data if jointype is SEMI or ANTI
   */
  void
  initial_cost_nestloop(PlannerInfo *root, JoinCostWorkspace *workspace,
--- 1903,1910 ----
   * 'outer_path' is the outer input to the join
   * 'inner_path' is the inner input to the join
   * 'sjinfo' is extra info about the join for selectivity estimation
!  * 'semifactors' contains valid data if jointype is INNER_UNIQUE, LEFT_UNIQUE,
!  * SEMI, or ANTI
   */
  void
  initial_cost_nestloop(PlannerInfo *root, JoinCostWorkspace *workspace,
*************** initial_cost_nestloop(PlannerInfo *root,
*** 1940,1949 ****
  	inner_run_cost = inner_path->total_cost - inner_path->startup_cost;
  	inner_rescan_run_cost = inner_rescan_total_cost - inner_rescan_start_cost;
  
! 	if (jointype == JOIN_SEMI || jointype == JOIN_ANTI)
  	{
  		/*
! 		 * SEMI or ANTI join: executor will stop after first match.
  		 *
  		 * Getting decent estimates requires inspection of the join quals,
  		 * which we choose to postpone to final_cost_nestloop.
--- 1942,1955 ----
  	inner_run_cost = inner_path->total_cost - inner_path->startup_cost;
  	inner_rescan_run_cost = inner_rescan_total_cost - inner_rescan_start_cost;
  
! 	if (jointype == JOIN_INNER_UNIQUE ||
! 		jointype == JOIN_LEFT_UNIQUE ||
! 		jointype == JOIN_SEMI ||
! 		jointype == JOIN_ANTI)
  	{
  		/*
! 		 * INNER_UNIQUE, LEFT_UNIQUE, SEMI, or ANTI join: executor will stop
! 		 * after first match.
  		 *
  		 * Getting decent estimates requires inspection of the join quals,
  		 * which we choose to postpone to final_cost_nestloop.
*************** initial_cost_nestloop(PlannerInfo *root,
*** 1977,1983 ****
   * 'path' is already filled in except for the rows and cost fields
   * 'workspace' is the result from initial_cost_nestloop
   * 'sjinfo' is extra info about the join for selectivity estimation
!  * 'semifactors' contains valid data if path->jointype is SEMI or ANTI
   */
  void
  final_cost_nestloop(PlannerInfo *root, NestPath *path,
--- 1983,1990 ----
   * 'path' is already filled in except for the rows and cost fields
   * 'workspace' is the result from initial_cost_nestloop
   * 'sjinfo' is extra info about the join for selectivity estimation
!  * 'semifactors' contains valid data if jointype is INNER_UNIQUE, LEFT_UNIQUE,
!  * SEMI, or ANTI
   */
  void
  final_cost_nestloop(PlannerInfo *root, NestPath *path,
*************** final_cost_nestloop(PlannerInfo *root, N
*** 2017,2026 ****
  
  	/* cost of inner-relation source data (we already dealt with outer rel) */
  
! 	if (path->jointype == JOIN_SEMI || path->jointype == JOIN_ANTI)
  	{
  		/*
! 		 * SEMI or ANTI join: executor will stop after first match.
  		 */
  		Cost		inner_run_cost = workspace->inner_run_cost;
  		Cost		inner_rescan_run_cost = workspace->inner_rescan_run_cost;
--- 2024,2037 ----
  
  	/* cost of inner-relation source data (we already dealt with outer rel) */
  
! 	if (path->jointype == JOIN_INNER_UNIQUE ||
! 		path->jointype == JOIN_LEFT_UNIQUE ||
! 		path->jointype == JOIN_SEMI ||
! 		path->jointype == JOIN_ANTI)
  	{
  		/*
! 		 * INNER_UNIQUE, LEFT_UNIQUE, SEMI, or ANTI join: executor will stop
! 		 * after first match.
  		 */
  		Cost		inner_run_cost = workspace->inner_run_cost;
  		Cost		inner_rescan_run_cost = workspace->inner_rescan_run_cost;
*************** initial_cost_mergejoin(PlannerInfo *root
*** 2250,2255 ****
--- 2261,2267 ----
  			innerendsel = cache->leftendsel;
  		}
  		if (jointype == JOIN_LEFT ||
+ 			jointype == JOIN_LEFT_UNIQUE ||
  			jointype == JOIN_ANTI)
  		{
  			outerstartsel = 0.0;
*************** initial_cost_hashjoin(PlannerInfo *root,
*** 2773,2779 ****
   *		num_batches
   * 'workspace' is the result from initial_cost_hashjoin
   * 'sjinfo' is extra info about the join for selectivity estimation
!  * 'semifactors' contains valid data if path->jointype is SEMI or ANTI
   */
  void
  final_cost_hashjoin(PlannerInfo *root, HashPath *path,
--- 2785,2792 ----
   *		num_batches
   * 'workspace' is the result from initial_cost_hashjoin
   * 'sjinfo' is extra info about the join for selectivity estimation
!  * 'semifactors' contains valid data if path->jointype is INNER_UNIQUE,
!  * LEFT_UNIQUE, SEMI or ANTI
   */
  void
  final_cost_hashjoin(PlannerInfo *root, HashPath *path,
*************** final_cost_hashjoin(PlannerInfo *root, H
*** 2896,2908 ****
  
  	/* CPU costs */
  
! 	if (path->jpath.jointype == JOIN_SEMI || path->jpath.jointype == JOIN_ANTI)
  	{
  		double		outer_matched_rows;
  		Selectivity inner_scan_frac;
  
  		/*
! 		 * SEMI or ANTI join: executor will stop after first match.
  		 *
  		 * For an outer-rel row that has at least one match, we can expect the
  		 * bucket scan to stop after a fraction 1/(match_count+1) of the
--- 2909,2925 ----
  
  	/* CPU costs */
  
! 	if (path->jpath.jointype == JOIN_INNER_UNIQUE ||
! 		path->jpath.jointype == JOIN_LEFT_UNIQUE ||
! 		path->jpath.jointype == JOIN_SEMI ||
! 		path->jpath.jointype == JOIN_ANTI)
  	{
  		double		outer_matched_rows;
  		Selectivity inner_scan_frac;
  
  		/*
! 		 * INNER_UNIQUE, LEFT_UNIQUE, SEMI or ANTI join: executor will stop
! 		 * after first match.
  		 *
  		 * For an outer-rel row that has at least one match, we can expect the
  		 * bucket scan to stop after a fraction 1/(match_count+1) of the
*************** final_cost_hashjoin(PlannerInfo *root, H
*** 2937,2946 ****
  			clamp_row_est(inner_path_rows / virtualbuckets) * 0.05;
  
  		/* Get # of tuples that will pass the basic join */
! 		if (path->jpath.jointype == JOIN_SEMI)
! 			hashjointuples = outer_matched_rows;
! 		else
  			hashjointuples = outer_path_rows - outer_matched_rows;
  	}
  	else
  	{
--- 2954,2963 ----
  			clamp_row_est(inner_path_rows / virtualbuckets) * 0.05;
  
  		/* Get # of tuples that will pass the basic join */
! 		if (path->jpath.jointype == JOIN_ANTI)
  			hashjointuples = outer_path_rows - outer_matched_rows;
+ 		else
+ 			hashjointuples = outer_matched_rows;
  	}
  	else
  	{
*************** get_restriction_qual_cost(PlannerInfo *r
*** 3469,3481 ****
  
  /*
   * compute_semi_anti_join_factors
!  *	  Estimate how much of the inner input a SEMI or ANTI join
!  *	  can be expected to scan.
   *
!  * In a hash or nestloop SEMI/ANTI join, the executor will stop scanning
!  * inner rows as soon as it finds a match to the current outer row.
!  * We should therefore adjust some of the cost components for this effect.
!  * This function computes some estimates needed for these adjustments.
   * These estimates will be the same regardless of the particular paths used
   * for the outer and inner relation, so we compute these once and then pass
   * them to all the join cost estimation functions.
--- 3486,3498 ----
  
  /*
   * compute_semi_anti_join_factors
!  *	  Estimate how much of the inner input a INNER_UNIQUE, LEFT_UNIQUE, SEMI,
!  *	  ANTI join can be expected to scan.
   *
!  * In a hash or nestloop INNER_UNIQUE/LEFT_UNIQUE/SEMI/ANTI join, the executor
!  * will stop scanning inner rows as soon as it finds a match to the current
!  * outer row. We should therefore adjust some of the cost components for this
!  * effect. This function computes some estimates needed for these adjustments.
   * These estimates will be the same regardless of the particular paths used
   * for the outer and inner relation, so we compute these once and then pass
   * them to all the join cost estimation functions.
*************** get_restriction_qual_cost(PlannerInfo *r
*** 3483,3489 ****
   * Input parameters:
   *	outerrel: outer relation under consideration
   *	innerrel: inner relation under consideration
!  *	jointype: must be JOIN_SEMI or JOIN_ANTI
   *	sjinfo: SpecialJoinInfo relevant to this join
   *	restrictlist: join quals
   * Output parameters:
--- 3500,3507 ----
   * Input parameters:
   *	outerrel: outer relation under consideration
   *	innerrel: inner relation under consideration
!  *	jointype: must be JOIN_INNER_UNIQUE, JOIN_LEFT_UNIQUE,JOIN_SEMI or
!  *	JOIN_ANTI
   *	sjinfo: SpecialJoinInfo relevant to this join
   *	restrictlist: join quals
   * Output parameters:
*************** compute_semi_anti_join_factors(PlannerIn
*** 3506,3512 ****
  	ListCell   *l;
  
  	/* Should only be called in these cases */
! 	Assert(jointype == JOIN_SEMI || jointype == JOIN_ANTI);
  
  	/*
  	 * In an ANTI join, we must ignore clauses that are "pushed down", since
--- 3524,3533 ----
  	ListCell   *l;
  
  	/* Should only be called in these cases */
! 	Assert(jointype == JOIN_INNER_UNIQUE ||
! 		   jointype == JOIN_LEFT_UNIQUE ||
! 		   jointype == JOIN_SEMI ||
! 		   jointype == JOIN_ANTI);
  
  	/*
  	 * In an ANTI join, we must ignore clauses that are "pushed down", since
*************** compute_semi_anti_join_factors(PlannerIn
*** 3530,3536 ****
  		joinquals = restrictlist;
  
  	/*
! 	 * Get the JOIN_SEMI or JOIN_ANTI selectivity of the join clauses.
  	 */
  	jselec = clauselist_selectivity(root,
  									joinquals,
--- 3551,3558 ----
  		joinquals = restrictlist;
  
  	/*
! 	 * Get the JOIN_INNER_UNIQUE, JOIN_LEFT_UNIQUE, JOIN_SEMI or JOIN_ANTI
! 	 * selectivity of the join clauses.
  	 */
  	jselec = clauselist_selectivity(root,
  									joinquals,
*************** calc_joinrel_size_estimate(PlannerInfo *
*** 3967,3974 ****
  	 * pushed-down quals are applied after the outer join, so their
  	 * selectivity applies fully.
  	 *
! 	 * For JOIN_SEMI and JOIN_ANTI, the selectivity is defined as the fraction
! 	 * of LHS rows that have matches, and we apply that straightforwardly.
  	 */
  	switch (jointype)
  	{
--- 3989,4001 ----
  	 * pushed-down quals are applied after the outer join, so their
  	 * selectivity applies fully.
  	 *
! 	 * For JOIN_INNER_UNIQUE, JOIN_SEMI and JOIN_ANTI, the selectivity is
! 	 * defined as the fraction of LHS rows that have matches, and we apply
! 	 * that straightforwardly.
! 	 *
! 	 * For JOIN_SEMI_LEFT, the selectivity is defined as the fraction of the
! 	 * LHS rows that have matches, although unlike JOIN_SEMI we must consider
! 	 * NULL RHS rows, and take the higher estimate of the two.
  	 */
  	switch (jointype)
  	{
*************** calc_joinrel_size_estimate(PlannerInfo *
*** 3990,3998 ****
--- 4017,4032 ----
  			nrows *= pselec;
  			break;
  		case JOIN_SEMI:
+ 		case JOIN_INNER_UNIQUE:
  			nrows = outer_rows * jselec;
  			/* pselec not used */
  			break;
+ 		case JOIN_LEFT_UNIQUE:
+ 			nrows = outer_rows * jselec;
+ 			if (nrows < outer_rows)
+ 				nrows = outer_rows;
+ 			nrows *= pselec;
+ 			break;
  		case JOIN_ANTI:
  			nrows = outer_rows * (1.0 - jselec);
  			nrows *= pselec;
diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c
index 41b60d0..c92f561 100644
*** a/src/backend/optimizer/path/joinpath.c
--- b/src/backend/optimizer/path/joinpath.c
***************
*** 19,24 ****
--- 19,25 ----
  #include "executor/executor.h"
  #include "foreign/fdwapi.h"
  #include "optimizer/cost.h"
+ #include "optimizer/planmain.h"
  #include "optimizer/pathnode.h"
  #include "optimizer/paths.h"
  
*************** add_paths_to_joinrel(PlannerInfo *root,
*** 88,93 ****
--- 89,101 ----
  	bool		mergejoin_allowed = true;
  	ListCell   *lc;
  
+ 	/*
+ 	 * There may be a more optimal JoinType to use. Check for such cases
+ 	 * first.
+ 	 */
+ 	jointype = get_optimal_jointype(root, outerrel, innerrel, jointype, sjinfo,
+ 									restrictlist);
+ 
  	extra.restrictlist = restrictlist;
  	extra.mergeclause_list = NIL;
  	extra.sjinfo = sjinfo;
*************** add_paths_to_joinrel(PlannerInfo *root,
*** 109,118 ****
  														  &mergejoin_allowed);
  
  	/*
! 	 * If it's SEMI or ANTI join, compute correction factors for cost
! 	 * estimation.  These will be the same for all paths.
  	 */
! 	if (jointype == JOIN_SEMI || jointype == JOIN_ANTI)
  		compute_semi_anti_join_factors(root, outerrel, innerrel,
  									   jointype, sjinfo, restrictlist,
  									   &extra.semifactors);
--- 117,130 ----
  														  &mergejoin_allowed);
  
  	/*
! 	 * If it's INNER_UNIQUE, LEFT_UNIQUE, SEMI or ANTI join, compute
! 	 * correction factors for cost estimation.  These will be the same for all
! 	 * paths.
  	 */
! 	if (jointype == JOIN_INNER_UNIQUE ||
! 		jointype == JOIN_LEFT_UNIQUE ||
! 		jointype == JOIN_SEMI ||
! 		jointype == JOIN_ANTI)
  		compute_semi_anti_join_factors(root, outerrel, innerrel,
  									   jointype, sjinfo, restrictlist,
  									   &extra.semifactors);
*************** match_unsorted_outer(PlannerInfo *root,
*** 827,842 ****
  	ListCell   *lc1;
  
  	/*
! 	 * Nestloop only supports inner, left, semi, and anti joins.  Also, if we
! 	 * are doing a right or full mergejoin, we must use *all* the mergeclauses
! 	 * as join clauses, else we will not have a valid plan.  (Although these
! 	 * two flags are currently inverses, keep them separate for clarity and
! 	 * possible future changes.)
  	 */
  	switch (jointype)
  	{
  		case JOIN_INNER:
  		case JOIN_LEFT:
  		case JOIN_SEMI:
  		case JOIN_ANTI:
  			nestjoinOK = true;
--- 839,856 ----
  	ListCell   *lc1;
  
  	/*
! 	 * Nestloop only supports inner, inner unique, left, left unique, semi,
! 	 * and anti joins.  Also, if we are doing a right or full mergejoin, we
! 	 * must use *all* the mergeclauses as join clauses, else we will not have
! 	 * a valid plan. (Although these two flags are currently inverses, keep
! 	 * them separate for clarity and possible future changes.)
  	 */
  	switch (jointype)
  	{
  		case JOIN_INNER:
+ 		case JOIN_INNER_UNIQUE:
  		case JOIN_LEFT:
+ 		case JOIN_LEFT_UNIQUE:
  		case JOIN_SEMI:
  		case JOIN_ANTI:
  			nestjoinOK = true;
diff --git a/src/backend/optimizer/path/joinrels.c b/src/backend/optimizer/path/joinrels.c
index 01d4fea..547d09d 100644
*** a/src/backend/optimizer/path/joinrels.c
--- b/src/backend/optimizer/path/joinrels.c
*************** join_is_legal(PlannerInfo *root, RelOptI
*** 490,499 ****
  			/*
  			 * The proposed join could still be legal, but only if we're
  			 * allowed to associate it into the RHS of this SJ.  That means
! 			 * this SJ must be a LEFT join (not SEMI or ANTI, and certainly
! 			 * not FULL) and the proposed join must not overlap the LHS.
  			 */
! 			if (sjinfo->jointype != JOIN_LEFT ||
  				bms_overlap(joinrelids, sjinfo->min_lefthand))
  				return false;	/* invalid join path */
  
--- 490,501 ----
  			/*
  			 * The proposed join could still be legal, but only if we're
  			 * allowed to associate it into the RHS of this SJ.  That means
! 			 * this SJ must be a LEFT or LEFT_UNIQUE join (not SEMI or ANTI,
! 			 * and certainly not FULL) and the proposed join must not overlap
! 			 * the LHS.
  			 */
! 			if ((sjinfo->jointype != JOIN_LEFT &&
! 				 sjinfo->jointype != JOIN_LEFT_UNIQUE) ||
  				bms_overlap(joinrelids, sjinfo->min_lefthand))
  				return false;	/* invalid join path */
  
*************** join_is_legal(PlannerInfo *root, RelOptI
*** 508,515 ****
  	}
  
  	/*
! 	 * Fail if violated any SJ's RHS and didn't match to a LEFT SJ: the
! 	 * proposed join can't associate into an SJ's RHS.
  	 *
  	 * Also, fail if the proposed join's predicate isn't strict; we're
  	 * essentially checking to see if we can apply outer-join identity 3, and
--- 510,517 ----
  	}
  
  	/*
! 	 * Fail if violated any SJ's RHS and didn't match to a LEFT or LEFT_UNIQUE
! 	 * SJ: the proposed join can't associate into an SJ's RHS.
  	 *
  	 * Also, fail if the proposed join's predicate isn't strict; we're
  	 * essentially checking to see if we can apply outer-join identity 3, and
*************** join_is_legal(PlannerInfo *root, RelOptI
*** 518,524 ****
  	 */
  	if (must_be_leftjoin &&
  		(match_sjinfo == NULL ||
! 		 match_sjinfo->jointype != JOIN_LEFT ||
  		 !match_sjinfo->lhs_strict))
  		return false;			/* invalid join path */
  
--- 520,527 ----
  	 */
  	if (must_be_leftjoin &&
  		(match_sjinfo == NULL ||
! 		 (match_sjinfo->jointype != JOIN_LEFT &&
! 		  match_sjinfo->jointype != JOIN_LEFT_UNIQUE) ||
  		 !match_sjinfo->lhs_strict))
  		return false;			/* invalid join path */
  
*************** make_join_rel(PlannerInfo *root, RelOptI
*** 698,703 ****
--- 701,707 ----
  		sjinfo->syn_lefthand = rel1->relids;
  		sjinfo->syn_righthand = rel2->relids;
  		sjinfo->jointype = JOIN_INNER;
+ 		sjinfo->optimal_jointype = JOIN_INNER;
  		/* we don't bother trying to make the remaining fields valid */
  		sjinfo->lhs_strict = false;
  		sjinfo->delay_upper_joins = false;
diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c
index 3d305eb..f00d4a1 100644
*** a/src/backend/optimizer/plan/analyzejoins.c
--- b/src/backend/optimizer/plan/analyzejoins.c
***************
*** 34,39 ****
--- 34,41 ----
  
  /* local functions */
  static bool join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo);
+ static bool specialjoin_is_unique_join(PlannerInfo *root,
+ 						   SpecialJoinInfo *sjinfo);
  static void remove_rel_from_query(PlannerInfo *root, int relid,
  					  Relids joinrelids);
  static List *remove_rel_from_joinlist(List *joinlist, int relid, int *nremoved);
*************** static bool rel_supports_distinctness(Pl
*** 41,46 ****
--- 43,80 ----
  static bool rel_is_distinct_for(PlannerInfo *root, RelOptInfo *rel,
  					List *clause_list);
  static Oid	distinct_col_search(int colno, List *colnos, List *opids);
+ static bool is_innerrel_unique_for(PlannerInfo *root,
+ 					   RelOptInfo *outerrel,
+ 					   RelOptInfo *innerrel,
+ 					   List *restrictlist);
+ 
+ 
+ /*
+  * optimize_outerjoin_types
+  *		Determine the most optimal JoinType for each outer join, and update
+  *		SpecialJoinInfo's optimal_jointype to that join type.
+  */
+ void
+ optimize_outerjoin_types(PlannerInfo *root)
+ {
+ 	ListCell   *lc;
+ 
+ 	foreach(lc, root->join_info_list)
+ 	{
+ 		SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
+ 
+ 		/*
+ 		 * Currently we're only interested in LEFT JOINs. If we can prove
+ 		 * these to have a unique inner side, based on the join condition then
+ 		 * this can save the executor from having to attempt fruitless
+ 		 * searches for subsequent matching outer tuples.
+ 		 */
+ 		if (sjinfo->jointype == JOIN_LEFT &&
+ 			sjinfo->optimal_jointype != JOIN_LEFT_UNIQUE &&
+ 			specialjoin_is_unique_join(root, sjinfo))
+ 			sjinfo->optimal_jointype = JOIN_LEFT_UNIQUE;
+ 	}
+ }
  
  
  /*
*************** restart:
*** 95,100 ****
--- 129,140 ----
  		root->join_info_list = list_delete_ptr(root->join_info_list, sjinfo);
  
  		/*
+ 		 * We may now be able to optimize some joins which we could not
+ 		 * optimize before.  (XXX huh? how would that happen?)
+ 		 */
+ 		optimize_outerjoin_types(root);
+ 
+ 		/*
  		 * Restart the scan.  This is necessary to ensure we find all
  		 * removable joins independently of ordering of the join_info_list
  		 * (note that removal of attr_needed bits may make a join appear
*************** join_is_removable(PlannerInfo *root, Spe
*** 156,186 ****
  	int			innerrelid;
  	RelOptInfo *innerrel;
  	Relids		joinrelids;
- 	List	   *clause_list = NIL;
- 	ListCell   *l;
  	int			attroff;
  
  	/*
! 	 * Must be a non-delaying left join to a single baserel, else we aren't
! 	 * going to be able to do anything with it.
  	 */
! 	if (sjinfo->jointype != JOIN_LEFT ||
  		sjinfo->delay_upper_joins)
  		return false;
  
  	if (!bms_get_singleton_member(sjinfo->min_righthand, &innerrelid))
! 		return false;
  
  	innerrel = find_base_rel(root, innerrelid);
  
- 	/*
- 	 * Before we go to the effort of checking whether any innerrel variables
- 	 * are needed above the join, make a quick check to eliminate cases in
- 	 * which we will surely be unable to prove uniqueness of the innerrel.
- 	 */
- 	if (!rel_supports_distinctness(root, innerrel))
- 		return false;
- 
  	/* Compute the relid set for the join we are considering */
  	joinrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
  
--- 196,219 ----
  	int			innerrelid;
  	RelOptInfo *innerrel;
  	Relids		joinrelids;
  	int			attroff;
+ 	ListCell   *l;
  
  	/*
! 	 * Join must have a unique inner side and must be a non-delaying join to a
! 	 * single baserel, else we aren't going to be able to do anything with it.
  	 */
! 	if (sjinfo->optimal_jointype != JOIN_LEFT_UNIQUE ||
  		sjinfo->delay_upper_joins)
  		return false;
  
+ 	/* Now we know specialjoin_is_unique_join() succeeded for this join */
+ 
  	if (!bms_get_singleton_member(sjinfo->min_righthand, &innerrelid))
! 		return false;			/* should not happen */
  
  	innerrel = find_base_rel(root, innerrelid);
  
  	/* Compute the relid set for the join we are considering */
  	joinrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
  
*************** join_is_removable(PlannerInfo *root, Spe
*** 190,196 ****
  	 *
  	 * Note that this test only detects use of inner-rel attributes in higher
  	 * join conditions and the target list.  There might be such attributes in
! 	 * pushed-down conditions at this join, too.  We check that case below.
  	 *
  	 * As a micro-optimization, it seems better to start with max_attr and
  	 * count down rather than starting with min_attr and counting up, on the
--- 223,230 ----
  	 *
  	 * Note that this test only detects use of inner-rel attributes in higher
  	 * join conditions and the target list.  There might be such attributes in
! 	 * pushed-down conditions at this join, too, but in this case the join
! 	 * would not have been optimized into a LEFT_UNIQUE join.
  	 *
  	 * As a micro-optimization, it seems better to start with max_attr and
  	 * count down rather than starting with min_attr and counting up, on the
*************** join_is_removable(PlannerInfo *root, Spe
*** 231,236 ****
--- 265,305 ----
  			return false;		/* it does reference innerrel */
  	}
  
+ 	return true;
+ }
+ 
+ /*
+  * specialjoin_is_unique_join
+  *		True if it can be proved that this special join can only ever match at
+  *		most one inner row for any single outer row. False is returned if
+  *		there's insufficient evidence to prove the join is unique.
+  */
+ static bool
+ specialjoin_is_unique_join(PlannerInfo *root, SpecialJoinInfo *sjinfo)
+ {
+ 	int			innerrelid;
+ 	RelOptInfo *innerrel;
+ 	Relids		joinrelids;
+ 	List	   *clause_list = NIL;
+ 	ListCell   *lc;
+ 
+ 	/* if there's more than one relation involved, then punt */
+ 	if (!bms_get_singleton_member(sjinfo->min_righthand, &innerrelid))
+ 		return false;
+ 
+ 	innerrel = find_base_rel(root, innerrelid);
+ 
+ 	/*
+ 	 * Before we go to the effort of pulling out the join condition's columns,
+ 	 * make a quick check to eliminate cases in which we will surely be unable
+ 	 * to prove uniqueness of the innerrel.
+ 	 */
+ 	if (!rel_supports_distinctness(root, innerrel))
+ 		return false;
+ 
+ 	/* Compute the relid set for the join we are considering */
+ 	joinrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
+ 
  	/*
  	 * Search for mergejoinable clauses that constrain the inner rel against
  	 * either the outer rel or a pseudoconstant.  If an operator is
*************** join_is_removable(PlannerInfo *root, Spe
*** 238,246 ****
  	 * it's what we want.  The mergejoinability test also eliminates clauses
  	 * containing volatile functions, which we couldn't depend on.
  	 */
! 	foreach(l, innerrel->joininfo)
  	{
! 		RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
  
  		/*
  		 * If it's not a join clause for this outer join, we can't use it.
--- 307,315 ----
  	 * it's what we want.  The mergejoinability test also eliminates clauses
  	 * containing volatile functions, which we couldn't depend on.
  	 */
! 	foreach(lc, innerrel->joininfo)
  	{
! 		RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(lc);
  
  		/*
  		 * If it's not a join clause for this outer join, we can't use it.
*************** join_is_removable(PlannerInfo *root, Spe
*** 252,261 ****
  			!bms_equal(restrictinfo->required_relids, joinrelids))
  		{
  			/*
! 			 * If such a clause actually references the inner rel then join
! 			 * removal has to be disallowed.  We have to check this despite
! 			 * the previous attr_needed checks because of the possibility of
! 			 * pushed-down clauses referencing the rel.
  			 */
  			if (bms_is_member(innerrelid, restrictinfo->clause_relids))
  				return false;
--- 321,331 ----
  			!bms_equal(restrictinfo->required_relids, joinrelids))
  		{
  			/*
! 			 * If such a clause actually references the inner rel then we
! 			 * can't say we're unique.  (XXX this is confusing conditions for
! 			 * join removability with conditions for uniqueness, and could
! 			 * probably stand to be improved.  But for the moment, keep on
! 			 * applying the stricter condition.)
  			 */
  			if (bms_is_member(innerrelid, restrictinfo->clause_relids))
  				return false;
*************** distinct_col_search(int colno, List *col
*** 837,839 ****
--- 907,1074 ----
  	}
  	return InvalidOid;
  }
+ 
+ 
+ /*
+  * is_innerrel_unique_for
+  *	  Determine if this innerrel can, at most, return a single tuple for each
+  *	  outer tuple, based on the 'restrictlist'.
+  */
+ static bool
+ is_innerrel_unique_for(PlannerInfo *root,
+ 					   RelOptInfo *outerrel,
+ 					   RelOptInfo *innerrel,
+ 					   List *restrictlist)
+ {
+ 	List	   *clause_list = NIL;
+ 	ListCell   *lc;
+ 
+ 	/* Fall out quickly if we certainly can't prove anything */
+ 	if (restrictlist == NIL ||
+ 		!rel_supports_distinctness(root, innerrel))
+ 		return false;
+ 
+ 	/*
+ 	 * Search for mergejoinable clauses that constrain the inner rel against
+ 	 * the outer rel.  If an operator is mergejoinable then it behaves like
+ 	 * equality for some btree opclass, so it's what we want.  The
+ 	 * mergejoinability test also eliminates clauses containing volatile
+ 	 * functions, which we couldn't depend on.
+ 	 */
+ 	foreach(lc, restrictlist)
+ 	{
+ 		RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(lc);
+ 
+ 		/* Ignore if it's not a mergejoinable clause */
+ 		if (!restrictinfo->can_join ||
+ 			restrictinfo->mergeopfamilies == NIL)
+ 			continue;			/* not mergejoinable */
+ 
+ 		/*
+ 		 * Check if clause has the form "outer op inner" or "inner op outer",
+ 		 * and if so mark which side is inner.
+ 		 */
+ 		if (!clause_sides_match_join(restrictinfo, outerrel->relids,
+ 									 innerrel->relids))
+ 			continue;			/* no good for these input relations */
+ 
+ 		/* OK, add to list */
+ 		clause_list = lappend(clause_list, restrictinfo);
+ 	}
+ 
+ 	/* Let rel_is_distinct_for() do the hard work */
+ 	return rel_is_distinct_for(root, innerrel, clause_list);
+ }
+ 
+ /*
+  * get_optimal_jointype
+  *	  We may be able to optimize some joins by converting the JoinType to one
+  *	  which the executor is able to run more efficiently. Here we look for
+  *	  such cases and if we find a better choice, then we'll return it,
+  *	  otherwise we'll return the original JoinType.
+  */
+ JoinType
+ get_optimal_jointype(PlannerInfo *root,
+ 					 RelOptInfo *outerrel,
+ 					 RelOptInfo *innerrel,
+ 					 JoinType jointype,
+ 					 SpecialJoinInfo *sjinfo,
+ 					 List *restrictlist)
+ {
+ 	int			innerrelid;
+ 
+ 	/* left joins were already optimized in optimize_outerjoin_types() */
+ 	if (jointype == JOIN_LEFT)
+ 		return sjinfo->optimal_jointype;
+ 
+ 	if (!bms_get_singleton_member(innerrel->relids, &innerrelid))
+ 		return jointype;
+ 
+ 	/*
+ 	 * Any INNER JOINs which can be proven to return at most one inner tuple
+ 	 * for each outer tuple can be converted in to a JOIN_SEMI.
+ 	 */
+ 	if (jointype == JOIN_INNER)
+ 	{
+ 		MemoryContext old_context;
+ 		ListCell   *lc;
+ 
+ 		/* can't optimize jointype with an empty restrictlist */
+ 		if (restrictlist == NIL)
+ 			return jointype;
+ 
+ 		/*
+ 		 * First let's query the unique and non-unique caches to see if we've
+ 		 * managed to prove that innerrel is unique for some subset of this
+ 		 * outerrel. We don't need an exact match, as if we have any extra
+ 		 * outerrels than were previously cached, then they can't make the
+ 		 * innerrel any less unique.
+ 		 */
+ 		foreach(lc, root->unique_rels[innerrelid])
+ 		{
+ 			Bitmapset  *unique_rels = (Bitmapset *) lfirst(lc);
+ 
+ 			if (bms_is_subset(unique_rels, outerrel->relids))
+ 				return JOIN_INNER_UNIQUE;		/* Success! */
+ 		}
+ 
+ 		/*
+ 		 * We may have previously determined that this outerrel, or some
+ 		 * superset thereof, cannot prove this innerrel to be unique.
+ 		 */
+ 		foreach(lc, root->non_unique_rels[innerrelid])
+ 		{
+ 			Bitmapset  *unique_rels = (Bitmapset *) lfirst(lc);
+ 
+ 			if (bms_is_subset(outerrel->relids, unique_rels))
+ 				return jointype;
+ 		}
+ 
+ 		/* No cached information, so try to make the proof. */
+ 		if (is_innerrel_unique_for(root, outerrel, innerrel, restrictlist))
+ 		{
+ 			jointype = JOIN_INNER_UNIQUE;		/* Success! */
+ 
+ 			/*
+ 			 * Cache the positive result for future probes, being sure to keep
+ 			 * it in the planner_cxt even if we are working in GEQO.
+ 			 *
+ 			 * Note: one might consider trying to isolate the minimal subset
+ 			 * of the outerrels that proved the innerrel unique.  But it's not
+ 			 * worth the trouble, because the planner builds up joinrels
+ 			 * incrementally and so we'll see the minimally sufficient
+ 			 * outerrels before any supersets of them anyway.
+ 			 */
+ 			old_context = MemoryContextSwitchTo(root->planner_cxt);
+ 			root->unique_rels[innerrelid] =
+ 				lappend(root->unique_rels[innerrelid],
+ 						bms_copy(outerrel->relids));
+ 			MemoryContextSwitchTo(old_context);
+ 		}
+ 		else
+ 		{
+ 			/*
+ 			 * None of the join conditions for outerrel proved innerrel
+ 			 * unique, so we can safely reject this outerrel or any subset of
+ 			 * it in future checks.
+ 			 *
+ 			 * However, in normal planning mode, caching this knowledge is
+ 			 * totally pointless; it won't be queried again, because we build
+ 			 * up joinrels from smaller to larger.  It is useful in GEQO mode,
+ 			 * where the knowledge can be carried across successive planning
+ 			 * attempts; and it's likely to be useful when using join-search
+ 			 * plugins, too.  Hence cache only when join_search_private is
+ 			 * non-NULL.  (Yeah, that's a hack, but it seems reasonable.)
+ 			 */
+ 			if (root->join_search_private)
+ 			{
+ 				old_context = MemoryContextSwitchTo(root->planner_cxt);
+ 				root->non_unique_rels[innerrelid] =
+ 					lappend(root->non_unique_rels[innerrelid],
+ 							bms_copy(outerrel->relids));
+ 				MemoryContextSwitchTo(old_context);
+ 			}
+ 		}
+ 	}
+ 	return jointype;
+ }
diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c
index 9999eea..a615680 100644
*** a/src/backend/optimizer/plan/initsplan.c
--- b/src/backend/optimizer/plan/initsplan.c
*************** make_outerjoininfo(PlannerInfo *root,
*** 1128,1133 ****
--- 1128,1135 ----
  	sjinfo->syn_lefthand = left_rels;
  	sjinfo->syn_righthand = right_rels;
  	sjinfo->jointype = jointype;
+ 	/* this may be changed later */
+ 	sjinfo->optimal_jointype = jointype;
  	/* this always starts out false */
  	sjinfo->delay_upper_joins = false;
  
diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/plan/planmain.c
index edd95d8..690349d 100644
*** a/src/backend/optimizer/plan/planmain.c
--- b/src/backend/optimizer/plan/planmain.c
*************** query_planner(PlannerInfo *root, List *t
*** 124,129 ****
--- 124,132 ----
  	 */
  	setup_simple_rel_arrays(root);
  
+ 	/* Allocate memory for caching which joins are unique. */
+ 	setup_unique_join_caches(root);
+ 
  	/*
  	 * Construct RelOptInfo nodes for all base relations in query, and
  	 * indirectly for all appendrel member relations ("other rels").  This
*************** query_planner(PlannerInfo *root, List *t
*** 185,190 ****
--- 188,196 ----
  	 */
  	fix_placeholder_input_needed_levels(root);
  
+ 	/* Determine if there's a better JoinType for each outer join */
+ 	optimize_outerjoin_types(root);
+ 
  	/*
  	 * Remove any useless outer joins.  Ideally this would be done during
  	 * jointree preprocessing, but the necessary information isn't available
diff --git a/src/backend/optimizer/plan/setrefs.c b/src/backend/optimizer/plan/setrefs.c
index 5537c14..95c3a2f 100644
*** a/src/backend/optimizer/plan/setrefs.c
--- b/src/backend/optimizer/plan/setrefs.c
*************** set_join_references(PlannerInfo *root, J
*** 1617,1622 ****
--- 1617,1623 ----
  	switch (join->jointype)
  	{
  		case JOIN_LEFT:
+ 		case JOIN_LEFT_UNIQUE:
  		case JOIN_SEMI:
  		case JOIN_ANTI:
  			inner_itlist->has_non_vars = false;
diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c
index 802eab3..c11769e 100644
*** a/src/backend/optimizer/util/relnode.c
--- b/src/backend/optimizer/util/relnode.c
*************** setup_simple_rel_arrays(PlannerInfo *roo
*** 81,86 ****
--- 81,102 ----
  }
  
  /*
+  * setup_unique_join_caches
+  *	  Prepare the arrays we use for caching which joins are proved to be
+  *	  unique and non-unique.
+  */
+ void
+ setup_unique_join_caches(PlannerInfo *root)
+ {
+ 	int			size = list_length(root->parse->rtable) + 1;
+ 
+ 	/* initialize the unique relation cache to all NULLs */
+ 	root->unique_rels = (List **) palloc0(size * sizeof(List *));
+ 
+ 	root->non_unique_rels = (List **) palloc0(size * sizeof(List *));
+ }
+ 
+ /*
   * build_simple_rel
   *	  Construct a new RelOptInfo for a base relation or 'other' relation.
   */
diff --git a/src/backend/parser/parse_clause.c b/src/backend/parser/parse_clause.c
index 751de4b..66eb670 100644
*** a/src/backend/parser/parse_clause.c
--- b/src/backend/parser/parse_clause.c
*************** transformFromClauseItem(ParseState *psta
*** 978,988 ****
  		/*
  		 * Make the left-side RTEs available for LATERAL access within the
  		 * right side, by temporarily adding them to the pstate's namespace
! 		 * list.  Per SQL:2008, if the join type is not INNER or LEFT then the
! 		 * left-side names must still be exposed, but it's an error to
! 		 * reference them.  (Stupid design, but that's what it says.)  Hence,
! 		 * we always push them into the namespace, but mark them as not
! 		 * lateral_ok if the jointype is wrong.
  		 *
  		 * Notice that we don't require the merged namespace list to be
  		 * conflict-free.  See the comments for scanNameSpaceForRefname().
--- 978,988 ----
  		/*
  		 * Make the left-side RTEs available for LATERAL access within the
  		 * right side, by temporarily adding them to the pstate's namespace
! 		 * list.  Per SQL:2008, if the join type is not INNER, INNER_UNIQUE,
! 		 * LEFT or LEFT_UNIQUE then the left-side names must still be exposed,
! 		 * but it's an error to reference them.  (Stupid design, but that's
! 		 * what it says.)  Hence, we always push them into the namespace, but
! 		 * mark them as not lateral_ok if the jointype is wrong.
  		 *
  		 * Notice that we don't require the merged namespace list to be
  		 * conflict-free.  See the comments for scanNameSpaceForRefname().
*************** transformFromClauseItem(ParseState *psta
*** 990,996 ****
  		 * NB: this coding relies on the fact that list_concat is not
  		 * destructive to its second argument.
  		 */
! 		lateral_ok = (j->jointype == JOIN_INNER || j->jointype == JOIN_LEFT);
  		setNamespaceLateralState(l_namespace, true, lateral_ok);
  
  		sv_namespace_length = list_length(pstate->p_namespace);
--- 990,999 ----
  		 * NB: this coding relies on the fact that list_concat is not
  		 * destructive to its second argument.
  		 */
! 		lateral_ok = (j->jointype == JOIN_INNER ||
! 					  j->jointype == JOIN_INNER_UNIQUE ||
! 					  j->jointype == JOIN_LEFT ||
! 					  j->jointype == JOIN_LEFT_UNIQUE);
  		setNamespaceLateralState(l_namespace, true, lateral_ok);
  
  		sv_namespace_length = list_length(pstate->p_namespace);
diff --git a/src/backend/utils/adt/network_selfuncs.c b/src/backend/utils/adt/network_selfuncs.c
index 2e39687..f14a3cb 100644
*** a/src/backend/utils/adt/network_selfuncs.c
--- b/src/backend/utils/adt/network_selfuncs.c
*************** networkjoinsel(PG_FUNCTION_ARGS)
*** 215,221 ****
--- 215,223 ----
  	switch (sjinfo->jointype)
  	{
  		case JOIN_INNER:
+ 		case JOIN_INNER_UNIQUE:
  		case JOIN_LEFT:
+ 		case JOIN_LEFT_UNIQUE:
  		case JOIN_FULL:
  
  			/*
diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index cc2a9a1..346952e 100644
*** a/src/backend/utils/adt/selfuncs.c
--- b/src/backend/utils/adt/selfuncs.c
*************** eqjoinsel(PG_FUNCTION_ARGS)
*** 2202,2207 ****
--- 2202,2208 ----
  	{
  		case JOIN_INNER:
  		case JOIN_LEFT:
+ 		case JOIN_LEFT_UNIQUE:
  		case JOIN_FULL:
  			selec = eqjoinsel_inner(operator, &vardata1, &vardata2);
  			break;
diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h
index 84efa8e..2ba7b07 100644
*** a/src/include/nodes/nodes.h
--- b/src/include/nodes/nodes.h
*************** typedef enum JoinType
*** 640,645 ****
--- 640,655 ----
  	JOIN_ANTI,					/* 1 copy of each LHS row that has no match */
  
  	/*
+ 	 * The following join types are a variants of JOIN_INNER and JOIN_LEFT for
+ 	 * when the inner side of the join is known to be unique. This serves
+ 	 * solely as an optimization to allow the executor to skip looking for
+ 	 * another matching tuple in the inner side, when it's known that another
+ 	 * cannot exist.
+ 	 */
+ 	JOIN_INNER_UNIQUE,
+ 	JOIN_LEFT_UNIQUE,
+ 
+ 	/*
  	 * These codes are used internally in the planner, but are not supported
  	 * by the executor (nor, indeed, by most of the planner).
  	 */
*************** typedef enum JoinType
*** 668,673 ****
--- 678,684 ----
  #define IS_OUTER_JOIN(jointype) \
  	(((1 << (jointype)) & \
  	  ((1 << JOIN_LEFT) | \
+ 	   (1 << JOIN_LEFT_UNIQUE) | \
  	   (1 << JOIN_FULL) | \
  	   (1 << JOIN_RIGHT) | \
  	   (1 << JOIN_ANTI))) != 0)
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index d430f6e..b00aba3 100644
*** a/src/include/nodes/relation.h
--- b/src/include/nodes/relation.h
*************** typedef struct PlannerInfo
*** 221,226 ****
--- 221,238 ----
  	List	  **join_rel_level; /* lists of join-relation RelOptInfos */
  	int			join_cur_level; /* index of list being extended */
  
+ 	/*
+ 	 * During the join search we attempt to optimize joins to try to prove
+ 	 * their inner side to be unique based on the join condition. This is a
+ 	 * rather expensive thing to do as it requires checking each relations
+ 	 * unique indexes to see if the relation can, at most, return one tuple
+ 	 * for each outer tuple. We use this cache during the join search to
+ 	 * record lists of the sets of relations which both prove, and disprove
+ 	 * the uniqueness properties for the relid indexed by these arrays.
+ 	 */
+ 	List	  **unique_rels;	/* cache for proven unique rels */
+ 	List	  **non_unique_rels;	/* cache for proven non-unique rels */
+ 
  	List	   *init_plans;		/* init SubPlans for query */
  
  	List	   *cte_plan_ids;	/* per-CTE-item list of subplan IDs */
*************** typedef struct SpecialJoinInfo
*** 1750,1755 ****
--- 1762,1769 ----
  	Relids		syn_lefthand;	/* base relids syntactically within LHS */
  	Relids		syn_righthand;	/* base relids syntactically within RHS */
  	JoinType	jointype;		/* always INNER, LEFT, FULL, SEMI, or ANTI */
+ 	JoinType	optimal_jointype;		/* as above but may also be
+ 										 * INNER_UNIQUE or LEFT_UNIQUE */
  	bool		lhs_strict;		/* joinclause is strict for some LHS rel */
  	bool		delay_upper_joins;		/* can't commute with upper RHS */
  	/* Remaining fields are set only for JOIN_SEMI jointype: */
diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h
index acc827d..13b212f 100644
*** a/src/include/optimizer/pathnode.h
--- b/src/include/optimizer/pathnode.h
*************** extern Path *reparameterize_path(Planner
*** 236,241 ****
--- 236,242 ----
   * prototypes for relnode.c
   */
  extern void setup_simple_rel_arrays(PlannerInfo *root);
+ extern void setup_unique_join_caches(PlannerInfo *root);
  extern RelOptInfo *build_simple_rel(PlannerInfo *root, int relid,
  				 RelOptKind reloptkind);
  extern RelOptInfo *find_base_rel(PlannerInfo *root, int relid);
diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h
index da9c640..a10146c 100644
*** a/src/include/optimizer/planmain.h
--- b/src/include/optimizer/planmain.h
*************** extern RestrictInfo *build_implied_join_
*** 99,107 ****
--- 99,114 ----
  /*
   * prototypes for plan/analyzejoins.c
   */
+ extern void optimize_outerjoin_types(PlannerInfo *root);
  extern List *remove_useless_joins(PlannerInfo *root, List *joinlist);
  extern bool query_supports_distinctness(Query *query);
  extern bool query_is_distinct_for(Query *query, List *colnos, List *opids);
+ extern JoinType get_optimal_jointype(PlannerInfo *root,
+ 					 RelOptInfo *outerrel,
+ 					 RelOptInfo *innerrel,
+ 					 JoinType jointype,
+ 					 SpecialJoinInfo *sjinfo,
+ 					 List *restrictlist);
  
  /*
   * prototypes for plan/setrefs.c
diff --git a/src/test/regress/expected/aggregates.out b/src/test/regress/expected/aggregates.out
index 3ff6691..691fa11 100644
*** a/src/test/regress/expected/aggregates.out
--- b/src/test/regress/expected/aggregates.out
*************** explain (costs off) select a,c from t1 g
*** 880,908 ****
  explain (costs off) select *
  from t1 inner join t2 on t1.a = t2.x and t1.b = t2.y
  group by t1.a,t1.b,t1.c,t1.d,t2.x,t2.y,t2.z;
!                       QUERY PLAN                       
! -------------------------------------------------------
!  Group
     Group Key: t1.a, t1.b, t2.x, t2.y
!    ->  Merge Join
!          Merge Cond: ((t1.a = t2.x) AND (t1.b = t2.y))
!          ->  Index Scan using t1_pkey on t1
!          ->  Index Scan using t2_pkey on t2
! (6 rows)
  
  -- Test case where t1 can be optimized but not t2
  explain (costs off) select t1.*,t2.x,t2.z
  from t1 inner join t2 on t1.a = t2.x and t1.b = t2.y
  group by t1.a,t1.b,t1.c,t1.d,t2.x,t2.z;
!                       QUERY PLAN                       
! -------------------------------------------------------
   HashAggregate
     Group Key: t1.a, t1.b, t2.x, t2.z
!    ->  Merge Join
!          Merge Cond: ((t1.a = t2.x) AND (t1.b = t2.y))
!          ->  Index Scan using t1_pkey on t1
!          ->  Index Scan using t2_pkey on t2
! (6 rows)
  
  -- Cannot optimize when PK is deferrable
  explain (costs off) select * from t3 group by a,b,c;
--- 880,910 ----
  explain (costs off) select *
  from t1 inner join t2 on t1.a = t2.x and t1.b = t2.y
  group by t1.a,t1.b,t1.c,t1.d,t2.x,t2.y,t2.z;
!                       QUERY PLAN                      
! ------------------------------------------------------
!  HashAggregate
     Group Key: t1.a, t1.b, t2.x, t2.y
!    ->  Hash Unique Inner Join
!          Hash Cond: ((t2.x = t1.a) AND (t2.y = t1.b))
!          ->  Seq Scan on t2
!          ->  Hash
!                ->  Seq Scan on t1
! (7 rows)
  
  -- Test case where t1 can be optimized but not t2
  explain (costs off) select t1.*,t2.x,t2.z
  from t1 inner join t2 on t1.a = t2.x and t1.b = t2.y
  group by t1.a,t1.b,t1.c,t1.d,t2.x,t2.z;
!                       QUERY PLAN                      
! ------------------------------------------------------
   HashAggregate
     Group Key: t1.a, t1.b, t2.x, t2.z
!    ->  Hash Unique Inner Join
!          Hash Cond: ((t2.x = t1.a) AND (t2.y = t1.b))
!          ->  Seq Scan on t2
!          ->  Hash
!                ->  Seq Scan on t1
! (7 rows)
  
  -- Cannot optimize when PK is deferrable
  explain (costs off) select * from t3 group by a,b,c;
diff --git a/src/test/regress/expected/equivclass.out b/src/test/regress/expected/equivclass.out
index 0391b8e..f446284 100644
*** a/src/test/regress/expected/equivclass.out
--- b/src/test/regress/expected/equivclass.out
*************** explain (costs off)
*** 186,192 ****
    select * from ec1, ec2 where ff = x1 and x1 = '42'::int8alias2;
                 QUERY PLAN                
  -----------------------------------------
!  Nested Loop
     ->  Seq Scan on ec2
           Filter: (x1 = '42'::int8alias2)
     ->  Index Scan using ec1_pkey on ec1
--- 186,192 ----
    select * from ec1, ec2 where ff = x1 and x1 = '42'::int8alias2;
                 QUERY PLAN                
  -----------------------------------------
!  Nested Loop Unique Inner Join
     ->  Seq Scan on ec2
           Filter: (x1 = '42'::int8alias2)
     ->  Index Scan using ec1_pkey on ec1
*************** explain (costs off)
*** 310,316 ****
           ->  Index Scan using ec1_expr3 on ec1 ec1_5
           ->  Index Scan using ec1_expr4 on ec1 ec1_6
     ->  Materialize
!          ->  Merge Join
                 Merge Cond: ((((ec1_1.ff + 2) + 1)) = ec1.f1)
                 ->  Merge Append
                       Sort Key: (((ec1_1.ff + 2) + 1))
--- 310,316 ----
           ->  Index Scan using ec1_expr3 on ec1 ec1_5
           ->  Index Scan using ec1_expr4 on ec1 ec1_6
     ->  Materialize
!          ->  Merge Unique Inner Join
                 Merge Cond: ((((ec1_1.ff + 2) + 1)) = ec1.f1)
                 ->  Merge Append
                       Sort Key: (((ec1_1.ff + 2) + 1))
*************** explain (costs off)
*** 365,371 ****
    where ss1.x = ec1.f1 and ec1.ff = 42::int8;
                       QUERY PLAN                      
  -----------------------------------------------------
!  Merge Join
     Merge Cond: ((((ec1_1.ff + 2) + 1)) = ec1.f1)
     ->  Merge Append
           Sort Key: (((ec1_1.ff + 2) + 1))
--- 365,371 ----
    where ss1.x = ec1.f1 and ec1.ff = 42::int8;
                       QUERY PLAN                      
  -----------------------------------------------------
!  Merge Unique Inner Join
     Merge Cond: ((((ec1_1.ff + 2) + 1)) = ec1.f1)
     ->  Merge Append
           Sort Key: (((ec1_1.ff + 2) + 1))
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index cafbc5e..7d0aaa7 100644
*** a/src/test/regress/expected/join.out
--- b/src/test/regress/expected/join.out
*************** from nt3 as nt3
*** 2756,2763 ****
  where nt3.id = 1 and ss2.b3;
                    QUERY PLAN                   
  -----------------------------------------------
!  Nested Loop
!    ->  Nested Loop
           ->  Index Scan using nt3_pkey on nt3
                 Index Cond: (id = 1)
           ->  Index Scan using nt2_pkey on nt2
--- 2756,2763 ----
  where nt3.id = 1 and ss2.b3;
                    QUERY PLAN                   
  -----------------------------------------------
!  Nested Loop Unique Inner Join
!    ->  Nested Loop Unique Inner Join
           ->  Index Scan using nt3_pkey on nt3
                 Index Cond: (id = 1)
           ->  Index Scan using nt2_pkey on nt2
*************** explain (costs off)
*** 4035,4041 ****
      on (p.k = ss.k);
             QUERY PLAN            
  ---------------------------------
!  Hash Left Join
     Hash Cond: (p.k = c.k)
     ->  Seq Scan on parent p
     ->  Hash
--- 4035,4041 ----
      on (p.k = ss.k);
             QUERY PLAN            
  ---------------------------------
!  Hash Unique Left Join
     Hash Cond: (p.k = c.k)
     ->  Seq Scan on parent p
     ->  Hash
*************** ERROR:  invalid reference to FROM-clause
*** 5260,5262 ****
--- 5260,5497 ----
  LINE 1: ...xx1 using lateral (select * from int4_tbl where f1 = x1) ss;
                                                                  ^
  HINT:  There is an entry for table "xx1", but it cannot be referenced from this part of the query.
+ --
+ -- test planner's ability to change joins into their appropriate semi join
+ -- type
+ --
+ create table j1 (id int primary key);
+ create table j2 (id int primary key);
+ create table j3 (id int);
+ insert into j1 values(1),(2),(3);
+ insert into j2 values(1),(2),(3);
+ insert into j3 values(1),(1);
+ analyze j1;
+ analyze j2;
+ analyze j3;
+ -- ensure join is changed to a semi join
+ explain (verbose, costs off)
+ select * from j1 inner join j2 on j1.id = j2.id;
+             QUERY PLAN             
+ -----------------------------------
+  Hash Unique Inner Join
+    Output: j1.id, j2.id
+    Hash Cond: (j1.id = j2.id)
+    ->  Seq Scan on public.j1
+          Output: j1.id
+    ->  Hash
+          Output: j2.id
+          ->  Seq Scan on public.j2
+                Output: j2.id
+ (9 rows)
+ 
+ -- ensure join not changed when not an equi-join
+ explain (verbose, costs off)
+ select * from j1 inner join j2 on j1.id > j2.id;
+             QUERY PLAN             
+ -----------------------------------
+  Nested Loop
+    Output: j1.id, j2.id
+    Join Filter: (j1.id > j2.id)
+    ->  Seq Scan on public.j1
+          Output: j1.id
+    ->  Materialize
+          Output: j2.id
+          ->  Seq Scan on public.j2
+                Output: j2.id
+ (9 rows)
+ 
+ -- don't change, as j3 has no unique index or pk on id
+ explain (verbose, costs off)
+ select * from j1 inner join j3 on j1.id = j3.id;
+             QUERY PLAN             
+ -----------------------------------
+  Hash Unique Inner Join
+    Output: j1.id, j3.id
+    Hash Cond: (j3.id = j1.id)
+    ->  Seq Scan on public.j3
+          Output: j3.id
+    ->  Hash
+          Output: j1.id
+          ->  Seq Scan on public.j1
+                Output: j1.id
+ (9 rows)
+ 
+ -- ensure left join is converted to left semi join
+ explain (verbose, costs off)
+ select * from j1 left join j2 on j1.id = j2.id;
+             QUERY PLAN             
+ -----------------------------------
+  Hash Unique Left Join
+    Output: j1.id, j2.id
+    Hash Cond: (j1.id = j2.id)
+    ->  Seq Scan on public.j1
+          Output: j1.id
+    ->  Hash
+          Output: j2.id
+          ->  Seq Scan on public.j2
+                Output: j2.id
+ (9 rows)
+ 
+ -- ensure right join is converted too
+ explain (verbose, costs off)
+ select * from j1 right join j2 on j1.id = j2.id;
+             QUERY PLAN             
+ -----------------------------------
+  Hash Unique Left Join
+    Output: j1.id, j2.id
+    Hash Cond: (j2.id = j1.id)
+    ->  Seq Scan on public.j2
+          Output: j2.id
+    ->  Hash
+          Output: j1.id
+          ->  Seq Scan on public.j1
+                Output: j1.id
+ (9 rows)
+ 
+ -- a clauseless (cross) join can't be converted
+ explain (verbose, costs off)
+ select * from j1 cross join j2;
+             QUERY PLAN             
+ -----------------------------------
+  Nested Loop
+    Output: j1.id, j2.id
+    ->  Seq Scan on public.j1
+          Output: j1.id
+    ->  Materialize
+          Output: j2.id
+          ->  Seq Scan on public.j2
+                Output: j2.id
+ (8 rows)
+ 
+ -- ensure a natural join is converted to a semi join
+ explain (verbose, costs off)
+ select * from j1 natural join j2;
+             QUERY PLAN             
+ -----------------------------------
+  Hash Unique Inner Join
+    Output: j1.id
+    Hash Cond: (j1.id = j2.id)
+    ->  Seq Scan on public.j1
+          Output: j1.id
+    ->  Hash
+          Output: j2.id
+          ->  Seq Scan on public.j2
+                Output: j2.id
+ (9 rows)
+ 
+ -- ensure distinct clause allows the inner to become a semi join
+ explain (verbose, costs off)
+ select * from j1
+ inner join (select distinct id from j3) j3 on j1.id = j3.id;
+                   QUERY PLAN                   
+ -----------------------------------------------
+  Nested Loop Unique Inner Join
+    Output: j1.id, j3.id
+    Join Filter: (j1.id = j3.id)
+    ->  Seq Scan on public.j1
+          Output: j1.id
+    ->  Materialize
+          Output: j3.id
+          ->  Unique
+                Output: j3.id
+                ->  Sort
+                      Output: j3.id
+                      Sort Key: j3.id
+                      ->  Seq Scan on public.j3
+                            Output: j3.id
+ (14 rows)
+ 
+ -- ensure group by clause allows the inner to become a semi join
+ explain (verbose, costs off)
+ select * from j1
+ inner join (select id from j3 group by id) j3 on j1.id = j3.id;
+                   QUERY PLAN                   
+ -----------------------------------------------
+  Nested Loop Unique Inner Join
+    Output: j1.id, j3.id
+    Join Filter: (j1.id = j3.id)
+    ->  Seq Scan on public.j1
+          Output: j1.id
+    ->  Materialize
+          Output: j3.id
+          ->  Group
+                Output: j3.id
+                Group Key: j3.id
+                ->  Sort
+                      Output: j3.id
+                      Sort Key: j3.id
+                      ->  Seq Scan on public.j3
+                            Output: j3.id
+ (15 rows)
+ 
+ -- ensure a full join is not altered
+ explain (verbose, costs off)
+ select * from j1 full join j2 on j1.id = j2.id;
+             QUERY PLAN             
+ -----------------------------------
+  Hash Full Join
+    Output: j1.id, j2.id
+    Hash Cond: (j1.id = j2.id)
+    ->  Seq Scan on public.j1
+          Output: j1.id
+    ->  Hash
+          Output: j2.id
+          ->  Seq Scan on public.j2
+                Output: j2.id
+ (9 rows)
+ 
+ drop table j1;
+ drop table j2;
+ drop table j3;
+ -- test a more complex permutations of join conversions
+ create table j1 (id1 int, id2 int, primary key(id1,id2));
+ create table j2 (id1 int, id2 int, primary key(id1,id2));
+ create table j3 (id1 int, id2 int, primary key(id1,id2));
+ insert into j1 values(1,1),(2,2);
+ insert into j2 values(1,1);
+ insert into j3 values(1,1);
+ analyze j1;
+ analyze j2;
+ analyze j3;
+ -- ensure there's no join conversion when not all columns which are part of
+ -- the unique index are part of the join clause
+ explain (verbose, costs off)
+ select * from j1
+ inner join j2 on j1.id1 = j2.id1;
+                 QUERY PLAN                
+ ------------------------------------------
+  Nested Loop
+    Output: j1.id1, j1.id2, j2.id1, j2.id2
+    Join Filter: (j1.id1 = j2.id1)
+    ->  Seq Scan on public.j2
+          Output: j2.id1, j2.id2
+    ->  Seq Scan on public.j1
+          Output: j1.id1, j1.id2
+ (7 rows)
+ 
+ -- ensure inner is converted to semi join when there's multiple columns in the
+ -- join condition
+ explain (verbose, costs off)
+ select * from j1
+ inner join j2 on j1.id1 = j2.id1 and j1.id2 = j2.id2;
+                         QUERY PLAN                        
+ ----------------------------------------------------------
+  Nested Loop Unique Inner Join
+    Output: j1.id1, j1.id2, j2.id1, j2.id2
+    Join Filter: ((j1.id1 = j2.id1) AND (j1.id2 = j2.id2))
+    ->  Seq Scan on public.j1
+          Output: j1.id1, j1.id2
+    ->  Materialize
+          Output: j2.id1, j2.id2
+          ->  Seq Scan on public.j2
+                Output: j2.id1, j2.id2
+ (9 rows)
+ 
+ drop table j1;
+ drop table j2;
+ drop table j3;
diff --git a/src/test/regress/expected/rowsecurity.out b/src/test/regress/expected/rowsecurity.out
index 067aa8d..9fdc695 100644
*** a/src/test/regress/expected/rowsecurity.out
--- b/src/test/regress/expected/rowsecurity.out
*************** EXPLAIN (COSTS OFF) SELECT * FROM docume
*** 276,282 ****
  EXPLAIN (COSTS OFF) SELECT * FROM document NATURAL JOIN category WHERE f_leak(dtitle);
                       QUERY PLAN                     
  ----------------------------------------------------
!  Nested Loop
     ->  Subquery Scan on document
           Filter: f_leak(document.dtitle)
           ->  Seq Scan on document document_1
--- 276,282 ----
  EXPLAIN (COSTS OFF) SELECT * FROM document NATURAL JOIN category WHERE f_leak(dtitle);
                       QUERY PLAN                     
  ----------------------------------------------------
!  Nested Loop Unique Inner Join
     ->  Subquery Scan on document
           Filter: f_leak(document.dtitle)
           ->  Seq Scan on document document_1
diff --git a/src/test/regress/expected/select_views.out b/src/test/regress/expected/select_views.out
index 7f57526..2651ff8 100644
*** a/src/test/regress/expected/select_views.out
--- b/src/test/regress/expected/select_views.out
*************** NOTICE:  f_leak => 9801-2345-6789-0123
*** 1411,1417 ****
  EXPLAIN (COSTS OFF) SELECT * FROM my_credit_card_normal WHERE f_leak(cnum);
                         QUERY PLAN                        
  ---------------------------------------------------------
!  Hash Join
     Hash Cond: (r.cid = l.cid)
     ->  Seq Scan on credit_card r
           Filter: f_leak(cnum)
--- 1411,1417 ----
  EXPLAIN (COSTS OFF) SELECT * FROM my_credit_card_normal WHERE f_leak(cnum);
                         QUERY PLAN                        
  ---------------------------------------------------------
!  Hash Unique Inner Join
     Hash Cond: (r.cid = l.cid)
     ->  Seq Scan on credit_card r
           Filter: f_leak(cnum)
*************** EXPLAIN (COSTS OFF) SELECT * FROM my_cre
*** 1432,1438 ****
  ---------------------------------------------------------------
   Subquery Scan on my_credit_card_secure
     Filter: f_leak(my_credit_card_secure.cnum)
!    ->  Hash Join
           Hash Cond: (r.cid = l.cid)
           ->  Seq Scan on credit_card r
           ->  Hash
--- 1432,1438 ----
  ---------------------------------------------------------------
   Subquery Scan on my_credit_card_secure
     Filter: f_leak(my_credit_card_secure.cnum)
!    ->  Hash Unique Inner Join
           Hash Cond: (r.cid = l.cid)
           ->  Seq Scan on credit_card r
           ->  Hash
*************** EXPLAIN (COSTS OFF) SELECT * FROM my_cre
*** 1466,1472 ****
     ->  Materialize
           ->  Subquery Scan on l
                 Filter: f_leak(l.cnum)
!                ->  Hash Join
                       Hash Cond: (r_1.cid = l_1.cid)
                       ->  Seq Scan on credit_card r_1
                       ->  Hash
--- 1466,1472 ----
     ->  Materialize
           ->  Subquery Scan on l
                 Filter: f_leak(l.cnum)
!                ->  Hash Unique Inner Join
                       Hash Cond: (r_1.cid = l_1.cid)
                       ->  Seq Scan on credit_card r_1
                       ->  Hash
*************** EXPLAIN (COSTS OFF) SELECT * FROM my_cre
*** 1497,1503 ****
           ->  Seq Scan on credit_usage r
                 Filter: ((ymd >= '10-01-2011'::date) AND (ymd < '11-01-2011'::date))
           ->  Materialize
!                ->  Hash Join
                       Hash Cond: (r_1.cid = l.cid)
                       ->  Seq Scan on credit_card r_1
                       ->  Hash
--- 1497,1503 ----
           ->  Seq Scan on credit_usage r
                 Filter: ((ymd >= '10-01-2011'::date) AND (ymd < '11-01-2011'::date))
           ->  Materialize
!                ->  Hash Unique Inner Join
                       Hash Cond: (r_1.cid = l.cid)
                       ->  Seq Scan on credit_card r_1
                       ->  Hash
diff --git a/src/test/regress/expected/select_views_1.out b/src/test/regress/expected/select_views_1.out
index 5275ef0..81795d8 100644
*** a/src/test/regress/expected/select_views_1.out
--- b/src/test/regress/expected/select_views_1.out
*************** NOTICE:  f_leak => 9801-2345-6789-0123
*** 1411,1417 ****
  EXPLAIN (COSTS OFF) SELECT * FROM my_credit_card_normal WHERE f_leak(cnum);
                         QUERY PLAN                        
  ---------------------------------------------------------
!  Hash Join
     Hash Cond: (r.cid = l.cid)
     ->  Seq Scan on credit_card r
           Filter: f_leak(cnum)
--- 1411,1417 ----
  EXPLAIN (COSTS OFF) SELECT * FROM my_credit_card_normal WHERE f_leak(cnum);
                         QUERY PLAN                        
  ---------------------------------------------------------
!  Hash Unique Inner Join
     Hash Cond: (r.cid = l.cid)
     ->  Seq Scan on credit_card r
           Filter: f_leak(cnum)
*************** EXPLAIN (COSTS OFF) SELECT * FROM my_cre
*** 1432,1438 ****
  ---------------------------------------------------------------
   Subquery Scan on my_credit_card_secure
     Filter: f_leak(my_credit_card_secure.cnum)
!    ->  Hash Join
           Hash Cond: (r.cid = l.cid)
           ->  Seq Scan on credit_card r
           ->  Hash
--- 1432,1438 ----
  ---------------------------------------------------------------
   Subquery Scan on my_credit_card_secure
     Filter: f_leak(my_credit_card_secure.cnum)
!    ->  Hash Unique Inner Join
           Hash Cond: (r.cid = l.cid)
           ->  Seq Scan on credit_card r
           ->  Hash
*************** EXPLAIN (COSTS OFF) SELECT * FROM my_cre
*** 1466,1472 ****
     ->  Materialize
           ->  Subquery Scan on l
                 Filter: f_leak(l.cnum)
!                ->  Hash Join
                       Hash Cond: (r_1.cid = l_1.cid)
                       ->  Seq Scan on credit_card r_1
                       ->  Hash
--- 1466,1472 ----
     ->  Materialize
           ->  Subquery Scan on l
                 Filter: f_leak(l.cnum)
!                ->  Hash Unique Inner Join
                       Hash Cond: (r_1.cid = l_1.cid)
                       ->  Seq Scan on credit_card r_1
                       ->  Hash
*************** EXPLAIN (COSTS OFF) SELECT * FROM my_cre
*** 1497,1503 ****
           ->  Seq Scan on credit_usage r
                 Filter: ((ymd >= '10-01-2011'::date) AND (ymd < '11-01-2011'::date))
           ->  Materialize
!                ->  Hash Join
                       Hash Cond: (r_1.cid = l.cid)
                       ->  Seq Scan on credit_card r_1
                       ->  Hash
--- 1497,1503 ----
           ->  Seq Scan on credit_usage r
                 Filter: ((ymd >= '10-01-2011'::date) AND (ymd < '11-01-2011'::date))
           ->  Materialize
!                ->  Hash Unique Inner Join
                       Hash Cond: (r_1.cid = l.cid)
                       ->  Seq Scan on credit_card r_1
                       ->  Hash
diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql
index 3430f91..38cc39c 100644
*** a/src/test/regress/sql/join.sql
--- b/src/test/regress/sql/join.sql
*************** update xx1 set x2 = f1 from xx1, lateral
*** 1696,1698 ****
--- 1696,1791 ----
  delete from xx1 using (select * from int4_tbl where f1 = x1) ss;
  delete from xx1 using (select * from int4_tbl where f1 = xx1.x1) ss;
  delete from xx1 using lateral (select * from int4_tbl where f1 = x1) ss;
+ 
+ --
+ -- test planner's ability to change joins into their appropriate semi join
+ -- type
+ --
+ 
+ create table j1 (id int primary key);
+ create table j2 (id int primary key);
+ create table j3 (id int);
+ 
+ insert into j1 values(1),(2),(3);
+ insert into j2 values(1),(2),(3);
+ insert into j3 values(1),(1);
+ 
+ analyze j1;
+ analyze j2;
+ analyze j3;
+ 
+ -- ensure join is changed to a semi join
+ explain (verbose, costs off)
+ select * from j1 inner join j2 on j1.id = j2.id;
+ 
+ -- ensure join not changed when not an equi-join
+ explain (verbose, costs off)
+ select * from j1 inner join j2 on j1.id > j2.id;
+ 
+ -- don't change, as j3 has no unique index or pk on id
+ explain (verbose, costs off)
+ select * from j1 inner join j3 on j1.id = j3.id;
+ 
+ -- ensure left join is converted to left semi join
+ explain (verbose, costs off)
+ select * from j1 left join j2 on j1.id = j2.id;
+ 
+ -- ensure right join is converted too
+ explain (verbose, costs off)
+ select * from j1 right join j2 on j1.id = j2.id;
+ 
+ -- a clauseless (cross) join can't be converted
+ explain (verbose, costs off)
+ select * from j1 cross join j2;
+ 
+ -- ensure a natural join is converted to a semi join
+ explain (verbose, costs off)
+ select * from j1 natural join j2;
+ 
+ -- ensure distinct clause allows the inner to become a semi join
+ explain (verbose, costs off)
+ select * from j1
+ inner join (select distinct id from j3) j3 on j1.id = j3.id;
+ 
+ -- ensure group by clause allows the inner to become a semi join
+ explain (verbose, costs off)
+ select * from j1
+ inner join (select id from j3 group by id) j3 on j1.id = j3.id;
+ 
+ -- ensure a full join is not altered
+ explain (verbose, costs off)
+ select * from j1 full join j2 on j1.id = j2.id;
+ 
+ drop table j1;
+ drop table j2;
+ drop table j3;
+ 
+ -- test a more complex permutations of join conversions
+ 
+ create table j1 (id1 int, id2 int, primary key(id1,id2));
+ create table j2 (id1 int, id2 int, primary key(id1,id2));
+ create table j3 (id1 int, id2 int, primary key(id1,id2));
+ 
+ insert into j1 values(1,1),(2,2);
+ insert into j2 values(1,1);
+ insert into j3 values(1,1);
+ 
+ analyze j1;
+ analyze j2;
+ analyze j3;
+ 
+ -- ensure there's no join conversion when not all columns which are part of
+ -- the unique index are part of the join clause
+ explain (verbose, costs off)
+ select * from j1
+ inner join j2 on j1.id1 = j2.id1;
+ 
+ -- ensure inner is converted to semi join when there's multiple columns in the
+ -- join condition
+ explain (verbose, costs off)
+ select * from j1
+ inner join j2 on j1.id1 = j2.id1 and j1.id2 = j2.id2;
+ 
+ drop table j1;
+ drop table j2;
+ drop table j3;