diff --git a/src/backend/executor/nodeMergejoin.c b/src/backend/executor/nodeMergejoin.c
index f50205ec8a..861327b928 100644
--- a/src/backend/executor/nodeMergejoin.c
+++ b/src/backend/executor/nodeMergejoin.c
@@ -166,8 +166,8 @@ typedef enum
  * In addition to the expressions themselves, the planner passes the btree
  * opfamily OID, collation OID, btree strategy number (BTLessStrategyNumber or
  * BTGreaterStrategyNumber), and nulls-first flag that identify the intended
- * sort ordering for each merge key.  The mergejoinable operator is an
- * equality operator in the opfamily, and the two inputs are guaranteed to be
+ * sort ordering for each merge key.  The mergejoinable operator is a
+ * comparison operator in the opfamily, and the two inputs are guaranteed to be
  * ordered in either increasing or decreasing (respectively) order according
  * to the opfamily and collation, with nulls at the indicated end of the range.
  * This allows us to obtain the needed comparison function from the opfamily.
@@ -200,6 +200,9 @@ MJExamineQuals(List *mergeclauses,
 		Oid			op_righttype;
 		Oid			sortfunc;
 
+		if (parent->mj_Ineq_Present)
+			elog(ERROR, "inequality mergejoin clause must be the last one");
+
 		if (!IsA(qual, OpExpr))
 			elog(ERROR, "mergejoin clause is not an OpExpr");
 
@@ -225,9 +228,40 @@ MJExamineQuals(List *mergeclauses,
 								   &join_strategy,
 								   &op_lefttype,
 								   &op_righttype);
-		if (join_strategy != BTEqualStrategyNumber)	/* should not happen */
-			elog(ERROR, "cannot merge using non-equality operator %u",
-				 qual->opno);
+
+		/*
+		 * Determine whether we accept lesser and/or equal tuples of the inner
+		 * relation.
+		 */
+		if (join_strategy != BTEqualStrategyNumber)
+		{
+			parent->mj_Ineq_Present = true;
+			switch (join_strategy)
+			{
+				case BTLessEqualStrategyNumber:
+					parent->mj_Ineq_JoinEqual = true;
+					/* fall through */
+				case BTLessStrategyNumber:
+					parent->mj_Ineq_JoinLesser = true;
+					if (sort_strategy != BTGreaterStrategyNumber)
+						elog(ERROR, "join strategy %d is not compatible with sort strategy %d",
+							 join_strategy, sort_strategy);
+					break;
+
+				case BTGreaterEqualStrategyNumber:
+					parent->mj_Ineq_JoinEqual = true;
+					/* fall through */
+				case BTGreaterStrategyNumber:
+					parent->mj_Ineq_JoinLesser = true;
+					if (sort_strategy != BTLessStrategyNumber)
+						elog(ERROR, "join strategy %d is not compatible with sort strategy %d",
+							 join_strategy, sort_strategy);
+					break;
+
+				default:
+					elog(ERROR, "unsupported join strategy %d", join_strategy);
+			}
+		}
 
 		/*
 		 * sortsupport routine must know if abbreviation optimization is
@@ -415,6 +449,19 @@ MJCompare(MergeJoinState *mergestate)
 	{
 		MergeJoinClause clause = &mergestate->mj_Clauses[i];
 		int			sort_result;
+		bool join_equal = true;
+		bool join_lesser = false;
+
+		if (mergestate->mj_Ineq_Present && i == mergestate->mj_NumClauses - 1)
+		{
+			/*
+			 * If the last merge clause is an inequality, check whether
+			 * we have to join the inner tuples that are less than outer
+			 * and/or equal to outer.
+			 */
+			join_equal = mergestate->mj_Ineq_JoinEqual;
+			join_lesser = mergestate->mj_Ineq_JoinLesser;
+		}
 
 		/*
 		 * Special case for NULL-vs-NULL, else use standard comparison.
@@ -429,8 +476,22 @@ MJCompare(MergeJoinState *mergestate)
 										  clause->rdatum, clause->risnull,
 										  &clause->ssup);
 
-		result = sort_result == 0 ? MJCR_Join
-					: sort_result < 0 ? MJCR_NextOuter : MJCR_NextInner;
+		if (sort_result < 0)
+			result = MJCR_NextOuter;
+		else if (sort_result == 0)
+		{
+			if (join_equal)
+				result = MJCR_Join;
+			else
+				result = MJCR_NextOuter;
+		}
+		else					/* sort_result > 0 */
+		{
+			if (join_lesser)
+				result = MJCR_Join;
+			else
+				result = MJCR_NextInner;
+		}
 
 		if (result != MJCR_Join)
 			break;
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index d8db0b29e1..9d3f177622 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -2797,6 +2797,24 @@ initial_cost_mergejoin(PlannerInfo *root, JoinCostWorkspace *workspace,
 }
 
 /*
+ * Check whether there is an inequality clause in the list
+ */
+static bool
+have_inequality_mergeclause(List *mergeclauses)
+{
+	ListCell   *lc;
+
+	foreach(lc, mergeclauses)
+	{
+		RestrictInfo *rinfo = castNode(RestrictInfo, lfirst(lc));
+		Assert(rinfo->mergeopfamilies != NIL);
+		if (!rinfo->is_mj_equality)
+			return true;
+	}
+	return false;
+}
+
+/*
  * final_cost_mergejoin
  *	  Final estimate of the cost and result size of a mergejoin path.
  *
@@ -2848,6 +2866,7 @@ final_cost_mergejoin(PlannerInfo *root, MergePath *path,
 	double		mergejointuples,
 				rescannedtuples;
 	double		rescanratio;
+	bool		have_inequality = have_inequality_mergeclause(mergeclauses);
 
 	/* Protect some assumptions below that rowcounts aren't zero or NaN */
 	if (inner_path_rows <= 0 || isnan(inner_path_rows))
@@ -2929,18 +2948,25 @@ final_cost_mergejoin(PlannerInfo *root, MergePath *path,
 	 * when we should not.  Can we do better without expensive selectivity
 	 * computations?
 	 *
+	 * Also, if merge clauses contain inequality, n_i matches all m_k where i <= k.
+	 * From that we derive: rescanned tuples = (m1 - 1) * n1 + (m2 - 1) * (n1 + n2)
+	 * + ... =  m1 * n1 + m2 * (n1 + n2) + ... - n1 - (n1 + n2) - ...
+	 * In the limit case of n_i = 1, n1 + (n1 + n2) + ... = sum(n_i) ^ 2 / 2.
+	 * Therefore, rescanned tuples = size of join - (inner_rows) ^ 2 / 2.
+	 *
 	 * The whole issue is moot if we are working from a unique-ified outer
 	 * input, or if we know we don't need to mark/restore at all.
 	 */
-	if (IsA(outer_path, UniquePath) ||path->skip_mark_restore)
+	if (have_inequality)
+		rescannedtuples = mergejointuples - inner_path_rows * inner_path_rows / 2.;
+	else if (IsA(outer_path, UniquePath) ||path->skip_mark_restore)
 		rescannedtuples = 0;
 	else
-	{
 		rescannedtuples = mergejointuples - inner_path_rows;
-		/* Must clamp because of possible underestimate */
-		if (rescannedtuples < 0)
-			rescannedtuples = 0;
-	}
+
+	/* Must clamp because of possible underestimate */
+	if (rescannedtuples < 0)
+		rescannedtuples = 0;
 	/* We'll inflate various costs this much to account for rescanning */
 	rescanratio = 1.0 + (rescannedtuples / inner_path_rows);
 
diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c
index 396ee2747a..17cdf0cbe2 100644
--- a/src/backend/optimizer/path/joinpath.c
+++ b/src/backend/optimizer/path/joinpath.c
@@ -22,6 +22,7 @@
 #include "optimizer/pathnode.h"
 #include "optimizer/paths.h"
 #include "optimizer/planmain.h"
+#include "utils/lsyscache.h"
 
 /* Hook for plugins to get control in add_paths_to_joinrel() */
 set_join_pathlist_hook_type set_join_pathlist_hook = NULL;
@@ -890,6 +891,7 @@ sort_inner_and_outer(PlannerInfo *root,
 	Path	   *cheapest_safe_inner = NULL;
 	List	   *all_pathkeys;
 	ListCell   *l;
+	bool		have_inequality;
 
 	/*
 	 * We only consider the cheapest-total-cost input paths, since we are
@@ -990,7 +992,7 @@ sort_inner_and_outer(PlannerInfo *root,
 	 */
 	all_pathkeys = select_outer_pathkeys_for_merge(root,
 												   extra->mergeclause_list,
-												   joinrel);
+												   joinrel, &have_inequality);
 
 	foreach(l, all_pathkeys)
 	{
@@ -1002,9 +1004,15 @@ sort_inner_and_outer(PlannerInfo *root,
 
 		/* Make a pathkey list with this guy first */
 		if (l != list_head(all_pathkeys))
+		{
+			if (have_inequality && l == list_tail(all_pathkeys))
+				/* Inequality merge clause must be the last, we can't move it */
+				break;
+
 			outerkeys = lcons(front_pathkey,
 							  list_delete_ptr(list_copy(all_pathkeys),
 											  front_pathkey));
+		}
 		else
 			outerkeys = all_pathkeys;	/* no work at first one... */
 
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index c067f70970..54b464a78d 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -981,6 +981,44 @@ update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
 }
 
 /*
+ * Determine the sort order required by an inequality merge clause.
+ */
+static int
+get_merge_sort_strategy(RestrictInfo *rinfo)
+{
+	Oid opfamily = linitial_oid(rinfo->mergeopfamilies);
+	Oid opno;
+	int join_strategy;
+	Oid lefttype;
+	Oid righttype;
+	bool sort_ascending;
+
+	Assert(IsA(rinfo->clause, OpExpr));
+	opno = ((OpExpr *) rinfo->clause)->opno;
+	get_op_opfamily_properties(opno, opfamily,
+							   false /* ordering_op */ , &join_strategy,
+							   &lefttype, &righttype);
+	switch (join_strategy)
+	{
+		case BTLessEqualStrategyNumber:
+		case BTLessStrategyNumber:
+			sort_ascending = false;
+			break;
+		case BTGreaterEqualStrategyNumber:
+		case BTGreaterStrategyNumber:
+			sort_ascending = true;
+			break;
+		default:
+			elog(ERROR, "unknown merge join clause strategy %d\n", join_strategy);
+	}
+
+	if (!rinfo->outer_is_left)
+		sort_ascending = !sort_ascending;
+
+	return sort_ascending ? BTLessStrategyNumber : BTGreaterStrategyNumber;
+}
+
+/*
  * find_mergeclauses_for_pathkeys
  *	  This routine attempts to find a set of mergeclauses that can be
  *	  used with a specified ordering for one of the input relations.
@@ -1021,6 +1059,7 @@ find_mergeclauses_for_pathkeys(PlannerInfo *root,
 		PathKey    *pathkey = (PathKey *) lfirst(i);
 		EquivalenceClass *pathkey_ec = pathkey->pk_eclass;
 		List	   *matched_restrictinfos = NIL;
+		RestrictInfo *matched_inequality = NULL;
 		ListCell   *j;
 
 		/*----------
@@ -1057,6 +1096,9 @@ find_mergeclauses_for_pathkeys(PlannerInfo *root,
 		 * make_inner_pathkeys_for_merge() has to delete duplicates when
 		 * it constructs the canonical pathkeys list, and we also have to
 		 * deal with the case in create_mergejoin_plan().
+		 *
+		 * If we found an inequality merge clause, we must put it after all
+		 * the equality clauses.
 		 *----------
 		 */
 		foreach(j, restrictinfos)
@@ -1070,29 +1112,64 @@ find_mergeclauses_for_pathkeys(PlannerInfo *root,
 			else
 				clause_ec = rinfo->outer_is_left ?
 					rinfo->right_ec : rinfo->left_ec;
-			if (clause_ec == pathkey_ec)
+
+			if (clause_ec != pathkey_ec)
+				continue;
+
+			if (rinfo->is_mj_equality)
 				matched_restrictinfos = lappend(matched_restrictinfos, rinfo);
+			else
+			{
+				int strategy = get_merge_sort_strategy(rinfo);
+				if (pathkey->pk_strategy != strategy)
+					continue; /* pathkey direction does not match mergeclause */
+				if (matched_inequality)
+					break; /* can't have more than one inequality mergeclause */
+				matched_inequality = rinfo;
+			}
 		}
+		/*
+		 * If we did find usable mergeclause(s) for this sort-key position,
+		 * add them to result list. Put inequality to the end of the list.
+		 */
+		mergeclauses = list_concat(mergeclauses, matched_restrictinfos);
+		if (matched_inequality)
+			mergeclauses = lappend(mergeclauses, matched_inequality);
 
 		/*
 		 * If we didn't find a mergeclause, we're done --- any additional
 		 * sort-key positions in the pathkeys are useless.  (But we can still
 		 * mergejoin if we found at least one mergeclause.)
+		 *
+		 * Also, if we found an inequality clause, we can't add any more
+		 * clauses after it.
 		 */
-		if (matched_restrictinfos == NIL)
+		if (matched_restrictinfos == NIL || matched_inequality != NULL)
 			break;
-
-		/*
-		 * If we did find usable mergeclause(s) for this sort-key position,
-		 * add them to result list.
-		 */
-		mergeclauses = list_concat(mergeclauses, matched_restrictinfos);
 	}
 
 	return mergeclauses;
 }
 
 /*
+ * Find inequality merge clauses in the given list of merge clauses.
+ */
+static List*
+find_inequality_clauses(List *clauses)
+{
+	List *result = NIL;
+	ListCell *lc;
+	foreach(lc, clauses)
+	{
+		RestrictInfo *rinfo = (RestrictInfo*) lfirst(lc);
+		Assert(rinfo->mergeopfamilies);
+		if (!rinfo->is_mj_equality)
+			result = lappend(result, rinfo);
+	}
+	return result;
+}
+
+/*
  * select_outer_pathkeys_for_merge
  *	  Builds a pathkey list representing a possible sort ordering
  *	  that can be used with the given mergeclauses.
@@ -1119,20 +1196,41 @@ find_mergeclauses_for_pathkeys(PlannerInfo *root,
 List *
 select_outer_pathkeys_for_merge(PlannerInfo *root,
 								List *mergeclauses,
-								RelOptInfo *joinrel)
+								RelOptInfo *joinrel,
+								bool *have_inequality)
 {
-	List	   *pathkeys = NIL;
+	List	   *eq_pathkeys = NIL;
 	int			nClauses = list_length(mergeclauses);
 	EquivalenceClass **ecs;
 	int		   *scores;
 	int			necs;
 	ListCell   *lc;
 	int			j;
+	PathKey	   *ineq_pathkey = NULL;
+	int ineq_strategy = BTLessStrategyNumber;
+	RestrictInfo *ineq_clause = NULL;
+	int ineq_ec_index = -1;
+
+	*have_inequality = false;
 
 	/* Might have no mergeclauses */
 	if (nClauses == 0)
 		return NIL;
 
+	{
+		List *ineq_clauses = find_inequality_clauses(mergeclauses);
+
+		if (list_length(ineq_clauses) > 1)
+			return NIL;
+
+		if (list_length(ineq_clauses) == 1)
+		{
+			*have_inequality = true;
+			ineq_clause = linitial(ineq_clauses);
+			ineq_strategy = get_merge_sort_strategy(ineq_clause);
+		}
+	}
+
 	/*
 	 * Make arrays of the ECs used by the mergeclauses (dropping any
 	 * duplicates) and their "popularity" scores.
@@ -1183,32 +1281,79 @@ select_outer_pathkeys_for_merge(PlannerInfo *root,
 	}
 
 	/*
+	 * Find the equivalence class corresponding to the inequality clause.
+	 */
+	if (ineq_clause)
+	{
+		EquivalenceClass *oeclass = ineq_clause->outer_is_left
+				? ineq_clause->left_ec : ineq_clause->right_ec;
+
+		for (ineq_ec_index = 0; ineq_ec_index < necs; ineq_ec_index++)
+			if (ecs[ineq_ec_index] == oeclass)
+				break;
+
+		Assert(ineq_ec_index < necs);
+	}
+
+	/*
 	 * Find out if we have all the ECs mentioned in query_pathkeys; if so we
 	 * can generate a sort order that's also useful for final output. There is
 	 * no percentage in a partial match, though, so we have to have 'em all.
+	 *
+	 * Moreover, for the pathkey that corresponds to the inequality merge clause,
+	 * we have to use a particular sort direction, so we check this too.
 	 */
+
 	if (root->query_pathkeys)
 	{
+		List *root_pathkeys = root->query_pathkeys;
 		foreach(lc, root->query_pathkeys)
 		{
 			PathKey    *query_pathkey = (PathKey *) lfirst(lc);
 			EquivalenceClass *query_ec = query_pathkey->pk_eclass;
 
 			for (j = 0; j < necs; j++)
-			{
 				if (ecs[j] == query_ec)
 					break;		/* found match */
-			}
+
 			if (j >= necs)
 				break;			/* didn't find match */
+
+			if (j == ineq_ec_index)
+			{
+				/*
+				 * We found query pathkey corresponding to the inequality merge
+				 * clause. Check that it has a suitable sort direction. If it
+				 * does, store it separately, because it must be the last one
+				 * in the list of join pathkeys.
+				 */
+				if (query_pathkey->pk_strategy == ineq_strategy)
+				{
+					/*
+					 * root->query_pathkeys shouldn't be redundant, so this pathkey
+					 * must be the first one we see for this equivalence class.
+					 */
+					Assert(ineq_pathkey == 0);
+					ineq_pathkey = query_pathkey;
+					/*
+					 * Mark this pathkey as already-emitted and remove it from the
+					 * list of root pathkeys.
+					 */
+					scores[ineq_ec_index] = -1;
+					root_pathkeys = list_delete(list_copy(root_pathkeys), ineq_pathkey);
+				}
+				else
+					break;	/* pathkey for inequality clause has wrong direction */
+			}
 		}
+
 		/* if we got to the end of the list, we have them all */
 		if (lc == NULL)
 		{
 			/* copy query_pathkeys as starting point for our output */
-			pathkeys = list_copy(root->query_pathkeys);
+			eq_pathkeys = list_copy(root_pathkeys);
 			/* mark their ECs as already-emitted */
-			foreach(lc, root->query_pathkeys)
+			foreach(lc, root_pathkeys)
 			{
 				PathKey    *query_pathkey = (PathKey *) lfirst(lc);
 				EquivalenceClass *query_ec = query_pathkey->pk_eclass;
@@ -1226,9 +1371,10 @@ select_outer_pathkeys_for_merge(PlannerInfo *root,
 	}
 
 	/*
-	 * Add remaining ECs to the list in popularity order, using a default sort
-	 * ordering.  (We could use qsort() here, but the list length is usually
-	 * so small it's not worth it.)
+	 * Add remaining ECs to the list in popularity order. (We could use qsort()
+	 * here, but the list length is usually so small it's not worth it.) Use
+	 * a default sort ordering for the equality clauses, and the ordering we
+	 * computed earlier for the inequality clause.
 	 */
 	for (;;)
 	{
@@ -1236,6 +1382,7 @@ select_outer_pathkeys_for_merge(PlannerInfo *root,
 		int			best_score;
 		EquivalenceClass *ec;
 		PathKey    *pathkey;
+		int 		strategy;
 
 		best_j = 0;
 		best_score = scores[0];
@@ -1251,20 +1398,35 @@ select_outer_pathkeys_for_merge(PlannerInfo *root,
 			break;				/* all done */
 		ec = ecs[best_j];
 		scores[best_j] = -1;
+		strategy = best_j == ineq_ec_index ? ineq_strategy : BTLessStrategyNumber;
 		pathkey = make_canonical_pathkey(root,
 										 ec,
 										 linitial_oid(ec->ec_opfamilies),
-										 BTLessStrategyNumber,
-										 false);
+										 strategy,
+										 strategy == BTGreaterStrategyNumber);
 		/* can't be redundant because no duplicate ECs */
-		Assert(!pathkey_is_redundant(pathkey, pathkeys));
-		pathkeys = lappend(pathkeys, pathkey);
+		Assert(!pathkey_is_redundant(pathkey, eq_pathkeys));
+
+		if (best_j == ineq_ec_index)
+			/*
+			 * Pathkey for inequality clause must be the last one,
+			 * record it separately.
+			 */
+			ineq_pathkey = pathkey;
+		else
+			eq_pathkeys = lappend(eq_pathkeys, pathkey);
 	}
 
 	pfree(ecs);
 	pfree(scores);
 
-	return pathkeys;
+	if (ineq_pathkey)
+	{
+		Assert(!pathkey_is_redundant(ineq_pathkey, eq_pathkeys));
+		return lappend(eq_pathkeys, ineq_pathkey);
+	}
+	else
+		return eq_pathkeys;
 }
 
 /*
@@ -1388,6 +1550,10 @@ make_inner_pathkeys_for_merge(PlannerInfo *root,
  * one of the directions happens to match an ORDER BY key, in which case
  * that direction should be preferred, in hopes of avoiding a final sort step.
  * right_merge_direction() implements this heuristic.
+ *
+ * Note that a merge join on an inequality clause can be performed only for
+ * a particular ordering of inputs, so we keep both sort directions if such
+ * clause is present.
  */
 static int
 pathkeys_useful_for_merging(PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
@@ -1399,12 +1565,9 @@ pathkeys_useful_for_merging(PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
 	{
 		PathKey    *pathkey = (PathKey *) lfirst(i);
 		bool		matched = false;
+		bool		right_direction = right_merge_direction(root, pathkey);
 		ListCell   *j;
 
-		/* If "wrong" direction, not useful for merging */
-		if (!right_merge_direction(root, pathkey))
-			break;
-
 		/*
 		 * First look into the EquivalenceClass of the pathkey, to see if
 		 * there are any members not yet joined to the rel.  If so, it's
@@ -1412,7 +1575,16 @@ pathkeys_useful_for_merging(PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
 		 */
 		if (rel->has_eclass_joins &&
 			eclass_useful_for_merging(root, pathkey->pk_eclass, rel))
+		{
+			/*
+			 * If "wrong" direction, not useful for merging on an equality 
+			 * clause.
+			 */
+			if (!right_direction)
+				return useful;
+
 			matched = true;
+		}
 		else
 		{
 			/*
@@ -1426,10 +1598,16 @@ pathkeys_useful_for_merging(PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
 
 				if (restrictinfo->mergeopfamilies == NIL)
 					continue;
+
 				update_mergeclause_eclasses(root, restrictinfo);
 
-				if (pathkey->pk_eclass == restrictinfo->left_ec ||
-					pathkey->pk_eclass == restrictinfo->right_ec)
+				/*
+				 * Consider pathkey useful if it has the "right" direction,
+				 * or if the correspoinding join clause is an inequality.
+				 */
+				if ((pathkey->pk_eclass == restrictinfo->left_ec
+					|| pathkey->pk_eclass == restrictinfo->right_ec)
+					&& (right_direction || !restrictinfo->is_mj_equality))
 				{
 					matched = true;
 					break;
diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c
index 8f474bd97c..5acd20a3ef 100644
--- a/src/backend/optimizer/plan/initsplan.c
+++ b/src/backend/optimizer/plan/initsplan.c
@@ -2013,6 +2013,20 @@ distribute_qual_to_rels(PlannerInfo *root, Node *clause,
 			initialize_mergeclause_eclasses(root, restrictinfo);
 		}
 	}
+	else if (restrictinfo->mergeopfamilies)
+	{
+		/* Not an equality clause, but maybe still mergejoinable? */
+		initialize_mergeclause_eclasses(root, restrictinfo);
+
+		if (maybe_outer_join
+			&& jointype == JOIN_FULL
+			&& restrictinfo->can_join)
+		{
+			root->full_join_clauses = lappend(root->full_join_clauses,
+							  restrictinfo);
+			return;
+		}
+	}
 
 	/* No EC special case applies, so push it into the clause lists */
 	distribute_restrictinfo_to_rels(root, restrictinfo);
@@ -2625,6 +2639,11 @@ check_mergejoinable(RestrictInfo *restrictinfo)
 			restrictinfo->mergeopfamilies = get_equality_opfamilies(opno);
 			restrictinfo->is_mj_equality = true;
 		}
+		else
+		{
+			restrictinfo->mergeopfamilies = get_inequality_opfamilies(opno);
+			restrictinfo->is_mj_equality = false;
+		}
 	}
 
 	/*
diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index fcc8323f62..60b29f5eec 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -3022,7 +3022,6 @@ mergejoinscansel(PlannerInfo *root, Node *clause,
 							   &op_strategy,
 							   &op_lefttype,
 							   &op_righttype);
-	Assert(op_strategy == BTEqualStrategyNumber);
 
 	/*
 	 * Look up the various operators we need.  If we don't find them all, it
@@ -3205,18 +3204,39 @@ mergejoinscansel(PlannerInfo *root, Node *clause,
 	if (selec != DEFAULT_INEQ_SEL)
 		*rightstart = selec;
 
-	/*
-	 * Only one of the two "start" fractions can really be more than zero;
-	 * believe the larger estimate and reset the other one to exactly 0.0. If
-	 * we get exactly equal estimates (as can easily happen with self-joins),
-	 * believe neither.
-	 */
-	if (*leftstart < *rightstart)
+	if (op_strategy == BTLessStrategyNumber
+		|| op_strategy == BTLessEqualStrategyNumber)
+	{
+		/*
+		 * If the left variable must be less than right, its first tuple
+		 * will already produce the first join pair.
+		 */
 		*leftstart = 0.0;
-	else if (*leftstart > *rightstart)
+	}
+	else if (op_strategy == BTGreaterStrategyNumber
+			 || op_strategy == BTGreaterEqualStrategyNumber)
+	{
+		/*
+		 * Similarly for the right variable and greater operator.
+		 */
 		*rightstart = 0.0;
+	}
 	else
-		*leftstart = *rightstart = 0.0;
+	{
+		Assert(op_strategy == BTEqualStrategyNumber);
+		/*
+		 * Only one of the two "start" fractions can really be more than zero;
+		 * believe the larger estimate and reset the other one to exactly 0.0. If
+		 * we get exactly equal estimates (as can easily happen with self-joins),
+		 * believe neither.
+		 */
+		if (*leftstart < *rightstart)
+			*leftstart = 0.0;
+		else if (*leftstart > *rightstart)
+			*rightstart = 0.0;
+		else
+			*leftstart = *rightstart = 0.0;
+	}
 
 	/*
 	 * If the sort order is nulls-first, we're going to have to skip over any
diff --git a/src/backend/utils/cache/lsyscache.c b/src/backend/utils/cache/lsyscache.c
index 4a69fbb4c9..e914da39a5 100644
--- a/src/backend/utils/cache/lsyscache.c
+++ b/src/backend/utils/cache/lsyscache.c
@@ -389,6 +389,46 @@ get_equality_opfamilies(Oid opno)
 }
 
 /*
+ * get_inequality_opfamilies
+ *		Given an operator, returns a list of operator families in which it
+ * 		represents btree inequality.
+ *
+ * Also see the comment for get_equality_opfamilies().
+ */
+List *
+get_inequality_opfamilies(Oid opno)
+{
+	List	   *result = NIL;
+	CatCList   *catlist;
+	int			i;
+
+	/*
+	 * Search pg_amop to see if the target operator is registered as the "<"
+	 * or ">" operator of any btree opfamily.
+	 */
+	catlist = SearchSysCacheList1(AMOPOPID, ObjectIdGetDatum(opno));
+
+	for (i = 0; i < catlist->n_members; i++)
+	{
+		HeapTuple	tuple = &catlist->members[i]->tuple;
+		Form_pg_amop aform = (Form_pg_amop) GETSTRUCT(tuple);
+
+		if (aform->amopmethod == BTREE_AM_OID
+			&& (aform->amopstrategy == BTLessStrategyNumber
+				|| aform->amopstrategy == BTLessEqualStrategyNumber
+				|| aform->amopstrategy == BTGreaterStrategyNumber
+				|| aform->amopstrategy == BTGreaterEqualStrategyNumber))
+		{
+			result = lappend_oid(result, aform->amopfamily);
+		}
+	}
+
+	ReleaseSysCacheList(catlist);
+
+	return result;
+}
+
+/*
  * get_compatible_hash_operators
  *		Get the OID(s) of hash equality operator(s) compatible with the given
  *		operator, but operating on its LHS and/or RHS datatype.
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index a953820f43..7c02299b71 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -1661,6 +1661,9 @@ typedef struct NestLoopState
  *		NullInnerTupleSlot prepared null tuple for left outer joins
  *		OuterEContext	   workspace for computing outer tuple's join values
  *		InnerEContext	   workspace for computing inner tuple's join values
+ *		Ineq_Present	   true if the last merge clause is inequalty
+ *		Ineq_JoinLesser	   true if join lesser values for inequality
+ *		Ineq_JoinEqual	   true if join equal values for inequality
  * ----------------
  */
 /* private in nodeMergejoin.c: */
@@ -1671,6 +1674,9 @@ typedef struct MergeJoinState
 	JoinState	js;				/* its first field is NodeTag */
 	int			mj_NumClauses;
 	MergeJoinClause mj_Clauses; /* array of length mj_NumClauses */
+	bool		mj_Ineq_Present;
+	bool		mj_Ineq_JoinLesser;
+	bool		mj_Ineq_JoinEqual;
 	int			mj_JoinState;
 	bool		mj_SkipMarkRestore;
 	bool		mj_ExtraMarks;
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index c9e44318ad..3b6f17652a 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -222,7 +222,8 @@ extern List *find_mergeclauses_for_pathkeys(PlannerInfo *root,
 							   List *restrictinfos);
 extern List *select_outer_pathkeys_for_merge(PlannerInfo *root,
 								List *mergeclauses,
-								RelOptInfo *joinrel);
+								RelOptInfo *joinrel,
+								bool *have_inequality);
 extern List *make_inner_pathkeys_for_merge(PlannerInfo *root,
 							  List *mergeclauses,
 							  List *outer_pathkeys);
diff --git a/src/include/utils/lsyscache.h b/src/include/utils/lsyscache.h
index 68b01ef377..e8d9187053 100644
--- a/src/include/utils/lsyscache.h
+++ b/src/include/utils/lsyscache.h
@@ -75,6 +75,7 @@ extern bool get_ordering_op_properties(Oid opno,
 extern Oid	get_equality_op_for_ordering_op(Oid opno, bool *reverse);
 extern Oid	get_ordering_op_for_equality_op(Oid opno, bool use_lhs_type);
 extern List *get_equality_opfamilies(Oid opno);
+extern List *get_inequality_opfamilies(Oid opno);
 extern bool get_compatible_hash_operators(Oid opno,
 							  Oid *lhs_opno, Oid *rhs_opno);
 extern bool get_op_hash_functions(Oid opno,
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index c50a206efb..91e49d5244 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -1700,18 +1700,19 @@ SELECT '' AS "xxx", *
 -- Non-equi-joins
 --
 SELECT '' AS "xxx", *
-  FROM J1_TBL JOIN J2_TBL ON (J1_TBL.i <= J2_TBL.k);
+  FROM J1_TBL JOIN J2_TBL ON (J1_TBL.i <= J2_TBL.k)
+  ORDER BY J1_TBL.i, J2_TBL.k;
  xxx | i | j |   t   | i | k 
 -----+---+---+-------+---+---
-     | 1 | 4 | one   | 2 | 2
-     | 2 | 3 | two   | 2 | 2
+     | 0 |   | zero  |   | 0
      | 0 |   | zero  | 2 | 2
+     | 0 |   | zero  | 2 | 4
+     | 1 | 4 | one   | 2 | 2
      | 1 | 4 | one   | 2 | 4
+     | 2 | 3 | two   | 2 | 2
      | 2 | 3 | two   | 2 | 4
      | 3 | 2 | three | 2 | 4
      | 4 | 1 | four  | 2 | 4
-     | 0 |   | zero  | 2 | 4
-     | 0 |   | zero  |   | 0
 (9 rows)
 
 --
@@ -1846,6 +1847,122 @@ SELECT '' AS "xxx", *
 (1 row)
 
 --
+-- Full merge join
+--
+set enable_hashjoin to 0;
+-- simple
+select * from j1_tbl full join j2_tbl on j1_tbl.i < j2_tbl.k;
+ i | j |   t   | i | k  
+---+---+-------+---+----
+   | 0 | zero  |   |   
+   |   | null  |   |   
+   |   |       | 0 |   
+   |   |       |   |   
+ 8 | 8 | eight |   |   
+ 7 | 7 | seven |   |   
+ 6 | 6 | six   |   |   
+ 5 | 0 | five  |   |   
+ 4 | 1 | four  |   |   
+ 3 | 2 | three | 2 |  4
+ 2 | 3 | two   | 2 |  4
+ 1 | 4 | one   | 2 |  4
+ 1 | 4 | one   | 2 |  2
+ 0 |   | zero  | 2 |  4
+ 0 |   | zero  | 2 |  2
+   |   |       |   |  0
+   |   |       | 1 | -1
+   |   |       | 3 | -3
+   |   |       | 5 | -5
+   |   |       | 5 | -5
+(20 rows)
+
+-- output ordering
+select * from j1_tbl full join j2_tbl on j1_tbl.i < j2_tbl.k order by j2_tbl.k desc;
+ i | j |   t   | i | k  
+---+---+-------+---+----
+   |   | null  |   |   
+   | 0 | zero  |   |   
+   |   |       | 0 |   
+   |   |       |   |   
+ 8 | 8 | eight |   |   
+ 7 | 7 | seven |   |   
+ 6 | 6 | six   |   |   
+ 5 | 0 | five  |   |   
+ 4 | 1 | four  |   |   
+ 2 | 3 | two   | 2 |  4
+ 3 | 2 | three | 2 |  4
+ 1 | 4 | one   | 2 |  4
+ 0 |   | zero  | 2 |  4
+ 1 | 4 | one   | 2 |  2
+ 0 |   | zero  | 2 |  2
+   |   |       |   |  0
+   |   |       | 1 | -1
+   |   |       | 3 | -3
+   |   |       | 5 | -5
+   |   |       | 5 | -5
+(20 rows)
+
+-- multiple clauses
+select * from j1_tbl full join j2_tbl on j1_tbl.i > j2_tbl.i and j1_tbl.i = j2_tbl.k;
+ i | j |   t   | i | k  
+---+---+-------+---+----
+   |   |       | 5 | -5
+   |   |       | 5 | -5
+   |   |       | 3 | -3
+   |   |       | 1 | -1
+   |   |       |   |  0
+ 0 |   | zero  |   |   
+ 1 | 4 | one   |   |   
+ 2 | 3 | two   |   |   
+   |   |       | 2 |  2
+ 3 | 2 | three |   |   
+ 4 | 1 | four  | 2 |  4
+   |   |       | 0 |   
+   |   |       |   |   
+ 5 | 0 | five  |   |   
+ 6 | 6 | six   |   |   
+ 7 | 7 | seven |   |   
+ 8 | 8 | eight |   |   
+   |   | null  |   |   
+   | 0 | zero  |   |   
+(19 rows)
+
+-- multiple inequality clauses
+select * from j1_tbl full join j2_tbl on j1_tbl.i > j2_tbl.i and j1_tbl.i < j2_tbl.k;
+ERROR:  FULL JOIN is only supported with merge-joinable or hash-joinable join conditions
+-- using an index
+create index idx_j1_tbl_i on j1_tbl(i);
+analyze j1_tbl;
+explain (costs off) select * from j1_tbl full join j2_tbl on j1_tbl.i > j2_tbl.k;
+             QUERY PLAN              
+-------------------------------------
+ Merge Full Join
+   Merge Cond: (j1_tbl.i > j2_tbl.k)
+   ->  Sort
+         Sort Key: j1_tbl.i
+         ->  Seq Scan on j1_tbl
+   ->  Sort
+         Sort Key: j2_tbl.k
+         ->  Seq Scan on j2_tbl
+(8 rows)
+
+explain (costs off) select * from j1_tbl full join j2_tbl on j1_tbl.i < j2_tbl.k;
+             QUERY PLAN              
+-------------------------------------
+ Merge Full Join
+   Merge Cond: (j1_tbl.i < j2_tbl.k)
+   ->  Sort
+         Sort Key: j1_tbl.i DESC
+         ->  Seq Scan on j1_tbl
+   ->  Sort
+         Sort Key: j2_tbl.k DESC
+         ->  Seq Scan on j2_tbl
+(8 rows)
+
+drop index idx_j1_tbl_i;
+analyze j1_tbl;
+reset enable_hashjoin;
+--
 -- semijoin selectivity for <>
 --
 explain (costs off)
@@ -5128,43 +5245,51 @@ select c.*,a.*,ss1.q1,ss2.q1,ss3.* from
     lateral (select q1, coalesce(ss1.x,q2) as y from int8_tbl d) ss2
   ) on c.q2 = ss2.q1,
   lateral (select * from int4_tbl i where ss2.y > f1) ss3;
-                                               QUERY PLAN                                                
----------------------------------------------------------------------------------------------------------
- Nested Loop
+                                                  QUERY PLAN                                                   
+---------------------------------------------------------------------------------------------------------------
+ Merge Join
    Output: c.q1, c.q2, a.q1, a.q2, b.q1, d.q1, i.f1
-   Join Filter: ((COALESCE((COALESCE(b.q2, (b2.f1)::bigint)), d.q2)) > i.f1)
-   ->  Hash Right Join
+   Merge Cond: (i.f1 < (COALESCE((COALESCE(b.q2, (b2.f1)::bigint)), d.q2)))
+   ->  Sort
+         Output: i.f1
+         Sort Key: i.f1 DESC
+         ->  Seq Scan on public.int4_tbl i
+               Output: i.f1
+   ->  Sort
          Output: c.q1, c.q2, a.q1, a.q2, b.q1, d.q1, (COALESCE((COALESCE(b.q2, (b2.f1)::bigint)), d.q2))
-         Hash Cond: (d.q1 = c.q2)
-         ->  Nested Loop
-               Output: a.q1, a.q2, b.q1, d.q1, (COALESCE((COALESCE(b.q2, (b2.f1)::bigint)), d.q2))
-               ->  Hash Right Join
-                     Output: a.q1, a.q2, b.q1, (COALESCE(b.q2, (b2.f1)::bigint))
-                     Hash Cond: (b.q1 = a.q2)
-                     ->  Nested Loop
-                           Output: b.q1, COALESCE(b.q2, (b2.f1)::bigint)
-                           Join Filter: (b.q1 < b2.f1)
-                           ->  Seq Scan on public.int8_tbl b
-                                 Output: b.q1, b.q2
-                           ->  Materialize
-                                 Output: b2.f1
-                                 ->  Seq Scan on public.int4_tbl b2
-                                       Output: b2.f1
-                     ->  Hash
-                           Output: a.q1, a.q2
+         Sort Key: (COALESCE((COALESCE(b.q2, (b2.f1)::bigint)), d.q2)) DESC
+         ->  Hash Right Join
+               Output: c.q1, c.q2, a.q1, a.q2, b.q1, d.q1, (COALESCE((COALESCE(b.q2, (b2.f1)::bigint)), d.q2))
+               Hash Cond: (d.q1 = c.q2)
+               ->  Nested Loop
+                     Output: a.q1, a.q2, b.q1, d.q1, (COALESCE((COALESCE(b.q2, (b2.f1)::bigint)), d.q2))
+                     ->  Hash Left Join
+                           Output: a.q1, a.q2, b.q1, (COALESCE(b.q2, (b2.f1)::bigint))
+                           Hash Cond: (a.q2 = b.q1)
                            ->  Seq Scan on public.int8_tbl a
                                  Output: a.q1, a.q2
-               ->  Seq Scan on public.int8_tbl d
-                     Output: d.q1, COALESCE((COALESCE(b.q2, (b2.f1)::bigint)), d.q2)
-         ->  Hash
-               Output: c.q1, c.q2
-               ->  Seq Scan on public.int8_tbl c
+                           ->  Hash
+                                 Output: b.q1, (COALESCE(b.q2, (b2.f1)::bigint))
+                                 ->  Merge Join
+                                       Output: b.q1, COALESCE(b.q2, (b2.f1)::bigint)
+                                       Merge Cond: (b.q1 < b2.f1)
+                                       ->  Sort
+                                             Output: b.q1, b.q2
+                                             Sort Key: b.q1 DESC
+                                             ->  Seq Scan on public.int8_tbl b
+                                                   Output: b.q1, b.q2
+                                       ->  Sort
+                                             Output: b2.f1
+                                             Sort Key: b2.f1 DESC
+                                             ->  Seq Scan on public.int4_tbl b2
+                                                   Output: b2.f1
+                     ->  Seq Scan on public.int8_tbl d
+                           Output: d.q1, COALESCE((COALESCE(b.q2, (b2.f1)::bigint)), d.q2)
+               ->  Hash
                      Output: c.q1, c.q2
-   ->  Materialize
-         Output: i.f1
-         ->  Seq Scan on public.int4_tbl i
-               Output: i.f1
-(34 rows)
+                     ->  Seq Scan on public.int8_tbl c
+                           Output: c.q1, c.q2
+(42 rows)
 
 -- check processing of postponed quals (bug #9041)
 explain (verbose, costs off)
@@ -5471,6 +5596,7 @@ rollback;
 --
 -- test planner's ability to mark joins as unique
 --
+set enable_mergejoin to 0;
 create table j1 (id int primary key);
 create table j2 (id int primary key);
 create table j3 (id int);
@@ -5740,6 +5866,7 @@ left join j2 on j1.id1 = j2.id1 where j1.id2 = 1;
 set enable_nestloop to 0;
 set enable_hashjoin to 0;
 set enable_sort to 0;
+set enable_mergejoin to 1;
 -- create an index that will be preferred over the PK to perform the join
 create index j1_id1_idx on j1 (id1) where id1 % 1000 = 1;
 explain (costs off) select * from j1 j1
diff --git a/src/test/regress/expected/partition_join.out b/src/test/regress/expected/partition_join.out
index 4fccd9ae54..5d4028ba79 100644
--- a/src/test/regress/expected/partition_join.out
+++ b/src/test/regress/expected/partition_join.out
@@ -4,6 +4,8 @@
 --
 -- Enable partitionwise join, which by default is disabled.
 SET enable_partitionwise_join to true;
+-- Disable merge joins to get predictable plans
+SET enable_mergejoin TO off;
 --
 -- partitioned by a single column
 --
@@ -869,6 +871,7 @@ SELECT t1.* FROM prt1 t1 WHERE t1.a IN (SELECT t1.b FROM prt2 t1 WHERE t1.b IN (
 -- test merge joins
 SET enable_hashjoin TO off;
 SET enable_nestloop TO off;
+SET enable_mergejoin TO on;
 EXPLAIN (COSTS OFF)
 SELECT t1.* FROM prt1 t1 WHERE t1.a IN (SELECT t1.b FROM prt2 t1 WHERE t1.b IN (SELECT (t1.a + t1.b)/2 FROM prt1_e t1 WHERE t1.c = 0)) AND t1.b = 0 ORDER BY t1.a;
                            QUERY PLAN                           
@@ -1052,6 +1055,7 @@ SELECT t1.a, t2.b FROM (SELECT * FROM prt1 WHERE a < 450) t1 LEFT JOIN (SELECT *
 
 RESET enable_hashjoin;
 RESET enable_nestloop;
+SET enable_mergejoin TO off;
 --
 -- partitioned by multiple columns
 --
diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql
index fc84237ce9..f85eeb00aa 100644
--- a/src/test/regress/sql/join.sql
+++ b/src/test/regress/sql/join.sql
@@ -157,7 +157,8 @@ SELECT '' AS "xxx", *
 --
 
 SELECT '' AS "xxx", *
-  FROM J1_TBL JOIN J2_TBL ON (J1_TBL.i <= J2_TBL.k);
+  FROM J1_TBL JOIN J2_TBL ON (J1_TBL.i <= J2_TBL.k)
+  ORDER BY J1_TBL.i, J2_TBL.k;
 
 
 --
@@ -194,6 +195,36 @@ SELECT '' AS "xxx", *
   FROM J1_TBL LEFT JOIN J2_TBL USING (i) WHERE (i = 1);
 
 --
+-- Full merge join
+--
+
+set enable_hashjoin to 0;
+
+-- simple
+select * from j1_tbl full join j2_tbl on j1_tbl.i < j2_tbl.k;
+
+-- output ordering
+select * from j1_tbl full join j2_tbl on j1_tbl.i < j2_tbl.k order by j2_tbl.k desc;
+
+-- multiple clauses
+select * from j1_tbl full join j2_tbl on j1_tbl.i > j2_tbl.i and j1_tbl.i = j2_tbl.k;
+
+-- multiple inequality clauses
+select * from j1_tbl full join j2_tbl on j1_tbl.i > j2_tbl.i and j1_tbl.i < j2_tbl.k;
+
+-- using an index
+create index idx_j1_tbl_i on j1_tbl(i);
+analyze j1_tbl;
+
+explain (costs off) select * from j1_tbl full join j2_tbl on j1_tbl.i > j2_tbl.k;
+explain (costs off) select * from j1_tbl full join j2_tbl on j1_tbl.i < j2_tbl.k;
+
+drop index idx_j1_tbl_i;
+analyze j1_tbl;
+
+reset enable_hashjoin;
+
+--
 -- semijoin selectivity for <>
 --
 explain (costs off)
@@ -1812,6 +1843,8 @@ rollback;
 -- test planner's ability to mark joins as unique
 --
 
+set enable_mergejoin to 0;
+
 create table j1 (id int primary key);
 create table j2 (id int primary key);
 create table j3 (id int);
@@ -1912,6 +1945,7 @@ left join j2 on j1.id1 = j2.id1 where j1.id2 = 1;
 set enable_nestloop to 0;
 set enable_hashjoin to 0;
 set enable_sort to 0;
+set enable_mergejoin to 1;
 
 -- create an index that will be preferred over the PK to perform the join
 create index j1_id1_idx on j1 (id1) where id1 % 1000 = 1;
diff --git a/src/test/regress/sql/partition_join.sql b/src/test/regress/sql/partition_join.sql
index a2d8b1be55..54c5e46d99 100644
--- a/src/test/regress/sql/partition_join.sql
+++ b/src/test/regress/sql/partition_join.sql
@@ -6,6 +6,9 @@
 -- Enable partitionwise join, which by default is disabled.
 SET enable_partitionwise_join to true;
 
+-- Disable merge joins to get predictable plans
+SET enable_mergejoin TO off;
+
 --
 -- partitioned by a single column
 --
@@ -146,6 +149,7 @@ SELECT t1.* FROM prt1 t1 WHERE t1.a IN (SELECT t1.b FROM prt2 t1 WHERE t1.b IN (
 -- test merge joins
 SET enable_hashjoin TO off;
 SET enable_nestloop TO off;
+SET enable_mergejoin TO on;
 
 EXPLAIN (COSTS OFF)
 SELECT t1.* FROM prt1 t1 WHERE t1.a IN (SELECT t1.b FROM prt2 t1 WHERE t1.b IN (SELECT (t1.a + t1.b)/2 FROM prt1_e t1 WHERE t1.c = 0)) AND t1.b = 0 ORDER BY t1.a;
@@ -162,6 +166,7 @@ SELECT t1.a, t2.b FROM (SELECT * FROM prt1 WHERE a < 450) t1 LEFT JOIN (SELECT *
 
 RESET enable_hashjoin;
 RESET enable_nestloop;
+SET enable_mergejoin TO off;
 
 --
 -- partitioned by multiple columns