text: /*-------------------------------------------------------------------------
   *
   * pathkeys.c
   *	  Utilities for matching and building path keys
   *
   * See src/backend/optimizer/README for a great deal of information about
   * the nature and use of path keys.
   *
   *
   * Portions Copyright (c) 1996-2017, PostgreSQL Global Development Group
   * Portions Copyright (c) 1994, Regents of the University of California
   *
   * IDENTIFICATION
   *	  src/backend/optimizer/path/pathkeys.c
   *
   *-------------------------------------------------------------------------
   */
  #include "postgres.h"
  
  #include "access/stratnum.h"
  #include "nodes/makefuncs.h"
  #include "nodes/nodeFuncs.h"
  #include "nodes/plannodes.h"
  #include "optimizer/clauses.h"
  #include "optimizer/pathnode.h"
  #include "optimizer/paths.h"
  #include "optimizer/tlist.h"
  #include "utils/lsyscache.h"
  
  
  static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys);
  static bool right_merge_direction(PlannerInfo *root, PathKey *pathkey);
  
  
  /****************************************************************************
   *		PATHKEY CONSTRUCTION AND REDUNDANCY TESTING
   ****************************************************************************/
  
  /*
   * make_canonical_pathkey
   *	  Given the parameters for a PathKey, find any pre-existing matching
   *	  pathkey in the query's list of "canonical" pathkeys.  Make a new
   *	  entry if there's not one already.
   *
   * Note that this function must not be used until after we have completed
   * merging EquivalenceClasses.  (We don't try to enforce that here; instead,
   * equivclass.c will complain if a merge occurs after root->canon_pathkeys
   * has become nonempty.)
   */
  PathKey *
  make_canonical_pathkey(PlannerInfo *root,
  					   EquivalenceClass *eclass, Oid opfamily,
  					   int strategy, bool nulls_first)
  {
  	PathKey    *pk;
  	ListCell   *lc;
  	MemoryContext oldcontext;
  
  	/* The passed eclass might be non-canonical, so chase up to the top */
  	while (eclass->ec_merged)
  		eclass = eclass->ec_merged;
  
  	foreach(lc, root->canon_pathkeys)
  	{
  		pk = (PathKey *) lfirst(lc);
  		if (eclass == pk->pk_eclass &&
  			opfamily == pk->pk_opfamily &&
  			strategy == pk->pk_strategy &&
  			nulls_first == pk->pk_nulls_first)
  			return pk;
  	}
  
  	/*
  	 * Be sure canonical pathkeys are allocated in the main planning context.
  	 * Not an issue in normal planning, but it is for GEQO.
  	 */
  	oldcontext = MemoryContextSwitchTo(root->planner_cxt);
  
  	pk = makeNode(PathKey);
  	pk->pk_eclass = eclass;
  	pk->pk_opfamily = opfamily;
  	pk->pk_strategy = strategy;
  	pk->pk_nulls_first = nulls_first;
  
  	root->canon_pathkeys = lappend(root->canon_pathkeys, pk);
  
  	MemoryContextSwitchTo(oldcontext);
  
  	return pk;
  }
  
  /*
   * pathkey_is_redundant
   *	   Is a pathkey redundant with one already in the given list?
   *
   * We detect two cases:
   *
   * 1. If the new pathkey's equivalence class contains a constant, and isn't
   * below an outer join, then we can disregard it as a sort key.  An example:
   *			SELECT ... WHERE x = 42 ORDER BY x, y;
   * We may as well just sort by y.  Note that because of opfamily matching,
   * this is semantically correct: we know that the equality constraint is one
   * that actually binds the variable to a single value in the terms of any
   * ordering operator that might go with the eclass.  This rule not only lets
   * us simplify (or even skip) explicit sorts, but also allows matching index
   * sort orders to a query when there are don't-care index columns.
   *
   * 2. If the new pathkey's equivalence class is the same as that of any
   * existing member of the pathkey list, then it is redundant.  Some examples:
   *			SELECT ... ORDER BY x, x;
   *			SELECT ... ORDER BY x, x DESC;
   *			SELECT ... WHERE x = y ORDER BY x, y;
   * In all these cases the second sort key cannot distinguish values that are
   * considered equal by the first, and so there's no point in using it.
   * Note in particular that we need not compare opfamily (all the opfamilies
   * of the EC have the same notion of equality) nor sort direction.
   *
   * Both the given pathkey and the list members must be canonical for this
   * to work properly, but that's okay since we no longer ever construct any
   * non-canonical pathkeys.  (Note: the notion of a pathkey *list* being
   * canonical includes the additional requirement of no redundant entries,
   * which is exactly what we are checking for here.)
   *
   * Because the equivclass.c machinery forms only one copy of any EC per query,
   * pointer comparison is enough to decide whether canonical ECs are the same.
   */
  static bool
  pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys)
  {
  	EquivalenceClass *new_ec = new_pathkey->pk_eclass;
  	ListCell   *lc;
  
  	/* Check for EC containing a constant --- unconditionally redundant */
  	if (EC_MUST_BE_REDUNDANT(new_ec))
  		return true;
  
  	/* If same EC already used in list, then redundant */
  	foreach(lc, pathkeys)
  	{
  		PathKey    *old_pathkey = (PathKey *) lfirst(lc);
  
  		if (new_ec == old_pathkey->pk_eclass)
  			return true;
  	}
  
  	return false;
  }
  
  /*
   * make_pathkey_from_sortinfo
   *	  Given an expression and sort-order information, create a PathKey.
   *	  The result is always a "canonical" PathKey, but it might be redundant.
   *
   * expr is the expression, and nullable_relids is the set of base relids
   * that are potentially nullable below it.
   *
   * If the PathKey is being generated from a SortGroupClause, sortref should be
   * the SortGroupClause's SortGroupRef; otherwise zero.
   *
   * If rel is not NULL, it identifies a specific relation we're considering
   * a path for, and indicates that child EC members for that relation can be
   * considered.  Otherwise child members are ignored.  (See the comments for
   * get_eclass_for_sort_expr.)
   *
   * create_it is TRUE if we should create any missing EquivalenceClass
   * needed to represent the sort key.  If it's FALSE, we return NULL if the
   * sort key isn't already present in any EquivalenceClass.
   */
  static PathKey *
  make_pathkey_from_sortinfo(PlannerInfo *root,
  						   Expr *expr,
  						   Relids nullable_relids,
  						   Oid opfamily,
  						   Oid opcintype,
  						   Oid collation,
  						   bool reverse_sort,
  						   bool nulls_first,
  						   Index sortref,
  						   Relids rel,
  						   bool create_it)
  {
  	int16		strategy;
  	Oid			equality_op;
  	List	   *opfamilies;
  	EquivalenceClass *eclass;
  
  	strategy = reverse_sort ? BTGreaterStrategyNumber : BTLessStrategyNumber;
  
  	/*
  	 * EquivalenceClasses need to contain opfamily lists based on the family
  	 * membership of mergejoinable equality operators, which could belong to
  	 * more than one opfamily.  So we have to look up the opfamily's equality
  	 * operator and get its membership.
  	 */
  	equality_op = get_opfamily_member(opfamily,
  									  opcintype,
  									  opcintype,
  									  BTEqualStrategyNumber);
  	if (!OidIsValid(equality_op))	/* shouldn't happen */
  		elog(ERROR, "missing operator %d(%u,%u) in opfamily %u",
  			 BTEqualStrategyNumber, opcintype, opcintype, opfamily);
  	opfamilies = get_mergejoin_opfamilies(equality_op);
  	if (!opfamilies)			/* certainly should find some */
  		elog(ERROR, "could not find opfamilies for equality operator %u",
  			 equality_op);
  
  	/* Now find or (optionally) create a matching EquivalenceClass */
  	eclass = get_eclass_for_sort_expr(root, expr, nullable_relids,
  									  opfamilies, opcintype, collation,
  									  sortref, rel, create_it);
  
  	/* Fail if no EC and !create_it */
  	if (!eclass)
  		return NULL;
  
  	/* And finally we can find or create a PathKey node */
  	return make_canonical_pathkey(root, eclass, opfamily,
  								  strategy, nulls_first);
  }
  
  /*
   * make_pathkey_from_sortop
   *	  Like make_pathkey_from_sortinfo, but work from a sort operator.
   *
   * This should eventually go away, but we need to restructure SortGroupClause
   * first.
   */
  static PathKey *
  make_pathkey_from_sortop(PlannerInfo *root,
  						 Expr *expr,
  						 Relids nullable_relids,
  						 Oid ordering_op,
  						 bool nulls_first,
  						 Index sortref,
  						 bool create_it)
  {
  	Oid			opfamily,
  				opcintype,
  				collation;
  	int16		strategy;
  
  	/* Find the operator in pg_amop --- failure shouldn't happen */
  	if (!get_ordering_op_properties(ordering_op,
  									&opfamily, &opcintype, &strategy))
  		elog(ERROR, "operator %u is not a valid ordering operator",
  			 ordering_op);
  
  	/* Because SortGroupClause doesn't carry collation, consult the expr */
  	collation = exprCollation((Node *) expr);
  
  	return make_pathkey_from_sortinfo(root,
  									  expr,
  									  nullable_relids,
  									  opfamily,
  									  opcintype,
  									  collation,
  									  (strategy == BTGreaterStrategyNumber),
  									  nulls_first,
  									  sortref,
  									  NULL,
  									  create_it);
  }
  
  
  /****************************************************************************
   *		PATHKEY COMPARISONS
   ****************************************************************************/
  
  /*
   * compare_pathkeys
   *	  Compare two pathkeys to see if they are equivalent, and if not whether
   *	  one is "better" than the other.
   *
   *	  We assume the pathkeys are canonical, and so they can be checked for
   *	  equality by simple pointer comparison.
   */
  PathKeysComparison
  compare_pathkeys(List *keys1, List *keys2)
  {
  	ListCell   *key1,
  			   *key2;
  
  	/*
  	 * Fall out quickly if we are passed two identical lists.  This mostly
  	 * catches the case where both are NIL, but that's common enough to
  	 * warrant the test.
  	 */
  	if (keys1 == keys2)
  		return PATHKEYS_EQUAL;
  
  	forboth(key1, keys1, key2, keys2)
  	{
  		PathKey    *pathkey1 = (PathKey *) lfirst(key1);
  		PathKey    *pathkey2 = (PathKey *) lfirst(key2);
  
  		if (pathkey1 != pathkey2)
  			return PATHKEYS_DIFFERENT;	/* no need to keep looking */
  	}
  
  	/*
  	 * If we reached the end of only one list, the other is longer and
  	 * therefore not a subset.
  	 */
  	if (key1 != NULL)
  		return PATHKEYS_BETTER1;	/* key1 is longer */
  	if (key2 != NULL)
  		return PATHKEYS_BETTER2;	/* key2 is longer */
  	return PATHKEYS_EQUAL;
  }
  
  /*
   * pathkeys_contained_in
   *	  Common special case of compare_pathkeys: we just want to know
   *	  if keys2 are at least as well sorted as keys1.
   */
  bool
  pathkeys_contained_in(List *keys1, List *keys2)
  {
  	switch (compare_pathkeys(keys1, keys2))
  	{
  		case PATHKEYS_EQUAL:
  		case PATHKEYS_BETTER2:
  			return true;
  		default:
  			break;
  	}
  	return false;
  }
  
  /*
   * get_cheapest_path_for_pathkeys
   *	  Find the cheapest path (according to the specified criterion) that
   *	  satisfies the given pathkeys and parameterization.
   *	  Return NULL if no such path.
   *
   * 'paths' is a list of possible paths that all generate the same relation
   * 'pathkeys' represents a required ordering (in canonical form!)
   * 'required_outer' denotes allowable outer relations for parameterized paths
   * 'cost_criterion' is STARTUP_COST or TOTAL_COST
   * 'require_parallel_safe' causes us to consider only parallel-safe paths
   */
  Path *
  get_cheapest_path_for_pathkeys(List *paths, List *pathkeys,
  							   Relids required_outer,
  							   CostSelector cost_criterion,
  							   bool require_parallel_safe)
  {
  	Path	   *matched_path = NULL;
  	ListCell   *l;
  
  	foreach(l, paths)
  	{
  		Path	   *path = (Path *) lfirst(l);
  
  		/*
  		 * Since cost comparison is a lot cheaper than pathkey comparison, do
  		 * that first.  (XXX is that still true?)
  		 */
  		if (matched_path != NULL &&
  			compare_path_costs(matched_path, path, cost_criterion) <= 0)
  			continue;
  
  		if (require_parallel_safe && !path->parallel_safe)
  			continue;
  
  		if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
  			bms_is_subset(PATH_REQ_OUTER(path), required_outer))
  			matched_path = path;
  	}
  	return matched_path;
  }
  
  /*
   * get_cheapest_fractional_path_for_pathkeys
   *	  Find the cheapest path (for retrieving a specified fraction of all
   *	  the tuples) that satisfies the given pathkeys and parameterization.
   *	  Return NULL if no such path.
   *
   * See compare_fractional_path_costs() for the interpretation of the fraction
   * parameter.
   *
   * 'paths' is a list of possible paths that all generate the same relation
   * 'pathkeys' represents a required ordering (in canonical form!)
   * 'required_outer' denotes allowable outer relations for parameterized paths
   * 'fraction' is the fraction of the total tuples expected to be retrieved
   */
  Path *
  get_cheapest_fractional_path_for_pathkeys(List *paths,
  										  List *pathkeys,
  										  Relids required_outer,
  										  double fraction)
  {
  	Path	   *matched_path = NULL;
  	ListCell   *l;
  
  	foreach(l, paths)
  	{
  		Path	   *path = (Path *) lfirst(l);
  
  		/*
  		 * Since cost comparison is a lot cheaper than pathkey comparison, do
  		 * that first.  (XXX is that still true?)
  		 */
  		if (matched_path != NULL &&
  			compare_fractional_path_costs(matched_path, path, fraction) <= 0)
  			continue;
  
  		if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
  			bms_is_subset(PATH_REQ_OUTER(path), required_outer))
  			matched_path = path;
  	}
  	return matched_path;
  }
  
  
  /*
   * get_cheapest_parallel_safe_total_inner
   *	  Find the unparameterized parallel-safe path with the least total cost.
   */
  Path *
  get_cheapest_parallel_safe_total_inner(List *paths)
  {
  	ListCell   *l;
  
  	foreach(l, paths)
  	{
  		Path	   *innerpath = (Path *) lfirst(l);
  
  		if (innerpath->parallel_safe &&
  			bms_is_empty(PATH_REQ_OUTER(innerpath)))
  			return innerpath;
  	}
  
  	return NULL;
  }
  
  /****************************************************************************
   *		NEW PATHKEY FORMATION
   ****************************************************************************/
  
  /*
   * build_index_pathkeys
   *	  Build a pathkeys list that describes the ordering induced by an index
   *	  scan using the given index.  (Note that an unordered index doesn't
   *	  induce any ordering, so we return NIL.)
   *
   * If 'scandir' is BackwardScanDirection, build pathkeys representing a
   * backwards scan of the index.
   *
   * The result is canonical, meaning that redundant pathkeys are removed;
   * it may therefore have fewer entries than there are index columns.
   *
   * Another reason for stopping early is that we may be able to tell that
   * an index column's sort order is uninteresting for this query.  However,
   * that test is just based on the existence of an EquivalenceClass and not
   * on position in pathkey lists, so it's not complete.  Caller should call
   * truncate_useless_pathkeys() to possibly remove more pathkeys.
   */
  List *
  build_index_pathkeys(PlannerInfo *root,
  					 IndexOptInfo *index,
  					 ScanDirection scandir)
  {
  	List	   *retval = NIL;
  	ListCell   *lc;
  	int			i;
  
  	if (index->sortopfamily == NULL)
  		return NIL;				/* non-orderable index */
  
  	i = 0;
  	foreach(lc, index->indextlist)
  	{
  		TargetEntry *indextle = (TargetEntry *) lfirst(lc);
  		Expr	   *indexkey;
  		bool		reverse_sort;
  		bool		nulls_first;
  		PathKey    *cpathkey;
  
  		/* We assume we don't need to make a copy of the tlist item */
  		indexkey = indextle->expr;
  
  		if (ScanDirectionIsBackward(scandir))
  		{
  			reverse_sort = !index->reverse_sort[i];
  			nulls_first = !index->nulls_first[i];
  		}
  		else
  		{
  			reverse_sort = index->reverse_sort[i];
  			nulls_first = index->nulls_first[i];
  		}
  
  		/*
  		 * OK, try to make a canonical pathkey for this sort key.  Note we're
  		 * underneath any outer joins, so nullable_relids should be NULL.
  		 */
  		cpathkey = make_pathkey_from_sortinfo(root,
  											  indexkey,
  											  NULL,
  											  index->sortopfamily[i],
  											  index->opcintype[i],
  											  index->indexcollations[i],
  											  reverse_sort,
  											  nulls_first,
  											  0,
  											  index->rel->relids,
  											  false);
  
  		if (cpathkey)
  		{
  			/*
  			 * We found the sort key in an EquivalenceClass, so it's relevant
  			 * for this query.  Add it to list, unless it's redundant.
  			 */
  			if (!pathkey_is_redundant(cpathkey, retval))
  				retval = lappend(retval, cpathkey);
  		}
  		else
  		{
  			/*
  			 * Boolean index keys might be redundant even if they do not
  			 * appear in an EquivalenceClass, because of our special treatment
  			 * of boolean equality conditions --- see the comment for
  			 * indexcol_is_bool_constant_for_query().  If that applies, we can
  			 * continue to examine lower-order index columns.  Otherwise, the
  			 * sort key is not an interesting sort order for this query, so we
  			 * should stop considering index columns; any lower-order sort
  			 * keys won't be useful either.
  			 */
  			if (!indexcol_is_bool_constant_for_query(index, i))
  				break;
  		}
  
  		i++;
  	}
  
  	return retval;
  }
  
  /*
   * build_expression_pathkey
   *	  Build a pathkeys list that describes an ordering by a single expression
   *	  using the given sort operator.
   *
   * expr, nullable_relids, and rel are as for make_pathkey_from_sortinfo.
   * We induce the other arguments assuming default sort order for the operator.
   *
   * Similarly to make_pathkey_from_sortinfo, the result is NIL if create_it
   * is false and the expression isn't already in some EquivalenceClass.
   */
  List *
  build_expression_pathkey(PlannerInfo *root,
  						 Expr *expr,
  						 Relids nullable_relids,
  						 Oid opno,
  						 Relids rel,
  						 bool create_it)
  {
  	List	   *pathkeys;
  	Oid			opfamily,
  				opcintype;
  	int16		strategy;
  	PathKey    *cpathkey;
  
  	/* Find the operator in pg_amop --- failure shouldn't happen */
  	if (!get_ordering_op_properties(opno,
  									&opfamily, &opcintype, &strategy))
  		elog(ERROR, "operator %u is not a valid ordering operator",
  			 opno);
  
  	cpathkey = make_pathkey_from_sortinfo(root,
  										  expr,
  										  nullable_relids,
  										  opfamily,
  										  opcintype,
  										  exprCollation((Node *) expr),
  										  (strategy == BTGreaterStrategyNumber),
  										  (strategy == BTGreaterStrategyNumber),
  										  0,
  										  rel,
  										  create_it);
  
  	if (cpathkey)
  		pathkeys = list_make1(cpathkey);
  	else
  		pathkeys = NIL;
  
  	return pathkeys;
  }
  
  /*
   * convert_subquery_pathkeys
   *	  Build a pathkeys list that describes the ordering of a subquery's
   *	  result, in the terms of the outer query.  This is essentially a
   *	  task of conversion.
   *
   * 'rel': outer query's RelOptInfo for the subquery relation.
   * 'subquery_pathkeys': the subquery's output pathkeys, in its terms.
   * 'subquery_tlist': the subquery's output targetlist, in its terms.
   *
   * It is not necessary for caller to do truncate_useless_pathkeys(),
   * because we select keys in a way that takes usefulness of the keys into
   * account.
   */
  List *
  convert_subquery_pathkeys(PlannerInfo *root, RelOptInfo *rel,
  						  List *subquery_pathkeys,
  						  List *subquery_tlist)
  {
  	List	   *retval = NIL;
  	int			retvallen = 0;
  	int			outer_query_keys = list_length(root->query_pathkeys);
  	ListCell   *i;
  
  	foreach(i, subquery_pathkeys)
  	{
  		PathKey    *sub_pathkey = (PathKey *) lfirst(i);
  		EquivalenceClass *sub_eclass = sub_pathkey->pk_eclass;
  		PathKey    *best_pathkey = NULL;
  
  		if (sub_eclass->ec_has_volatile)
  		{
  			/*
  			 * If the sub_pathkey's EquivalenceClass is volatile, then it must
  			 * have come from an ORDER BY clause, and we have to match it to
  			 * that same targetlist entry.
  			 */
  			TargetEntry *tle;
  
  			if (sub_eclass->ec_sortref == 0)	/* can't happen */
  				elog(ERROR, "volatile EquivalenceClass has no sortref");
  			tle = get_sortgroupref_tle(sub_eclass->ec_sortref, subquery_tlist);
  			Assert(tle);
  			/* resjunk items aren't visible to outer query */
  			if (!tle->resjunk)
  			{
  				/* We can represent this sub_pathkey */
  				EquivalenceMember *sub_member;
  				Expr	   *outer_expr;
  				EquivalenceClass *outer_ec;
  
  				Assert(list_length(sub_eclass->ec_members) == 1);
  				sub_member = (EquivalenceMember *) linitial(sub_eclass->ec_members);
  				outer_expr = (Expr *) makeVarFromTargetEntry(rel->relid, tle);
  
  				/*
  				 * Note: it might look funny to be setting sortref = 0 for a
  				 * reference to a volatile sub_eclass.  However, the
  				 * expression is *not* volatile in the outer query: it's just
  				 * a Var referencing whatever the subquery emitted. (IOW, the
  				 * outer query isn't going to re-execute the volatile
  				 * expression itself.)	So this is okay.  Likewise, it's
  				 * correct to pass nullable_relids = NULL, because we're
  				 * underneath any outer joins appearing in the outer query.
  				 */
  				outer_ec =
  					get_eclass_for_sort_expr(root,
  											 outer_expr,
  											 NULL,
  											 sub_eclass->ec_opfamilies,
  											 sub_member->em_datatype,
  											 sub_eclass->ec_collation,
  											 0,
  											 rel->relids,
  											 false);
  
  				/*
  				 * If we don't find a matching EC, sub-pathkey isn't
  				 * interesting to the outer query
  				 */
  				if (outer_ec)
  					best_pathkey =
  						make_canonical_pathkey(root,
  											   outer_ec,
  											   sub_pathkey->pk_opfamily,
  											   sub_pathkey->pk_strategy,
  											   sub_pathkey->pk_nulls_first);
  			}
  		}
  		else
  		{
  			/*
  			 * Otherwise, the sub_pathkey's EquivalenceClass could contain
  			 * multiple elements (representing knowledge that multiple items
  			 * are effectively equal).  Each element might match none, one, or
  			 * more of the output columns that are visible to the outer query.
  			 * This means we may have multiple possible representations of the
  			 * sub_pathkey in the context of the outer query.  Ideally we
  			 * would generate them all and put them all into an EC of the
  			 * outer query, thereby propagating equality knowledge up to the
  			 * outer query.  Right now we cannot do so, because the outer
  			 * query's EquivalenceClasses are already frozen when this is
  			 * called. Instead we prefer the one that has the highest "score"
  			 * (number of EC peers, plus one if it matches the outer
  			 * query_pathkeys). This is the most likely to be useful in the
  			 * outer query.
  			 */
  			int			best_score = -1;
  			ListCell   *j;
  
  			foreach(j, sub_eclass->ec_members)
  			{
  				EquivalenceMember *sub_member = (EquivalenceMember *) lfirst(j);
  				Expr	   *sub_expr = sub_member->em_expr;
  				Oid			sub_expr_type = sub_member->em_datatype;
  				Oid			sub_expr_coll = sub_eclass->ec_collation;
  				ListCell   *k;
  
  				if (sub_member->em_is_child)
  					continue;	/* ignore children here */
  
  				foreach(k, subquery_tlist)
  				{
  					TargetEntry *tle = (TargetEntry *) lfirst(k);
  					Expr	   *tle_expr;
  					Expr	   *outer_expr;
  					EquivalenceClass *outer_ec;
  					PathKey    *outer_pk;
  					int			score;
  
  					/* resjunk items aren't visible to outer query */
  					if (tle->resjunk)
  						continue;
  
  					/*
  					 * The targetlist entry is considered to match if it
  					 * matches after sort-key canonicalization.  That is
  					 * needed since the sub_expr has been through the same
  					 * process.
  					 */
  					tle_expr = canonicalize_ec_expression(tle->expr,
  														  sub_expr_type,
  														  sub_expr_coll);
  					if (!equal(tle_expr, sub_expr))
  						continue;
  
  					/*
  					 * Build a representation of this targetlist entry as an
  					 * outer Var.
  					 */
  					outer_expr = (Expr *) makeVarFromTargetEntry(rel->relid,
  																 tle);
  
  					/* See if we have a matching EC for that */
  					outer_ec = get_eclass_for_sort_expr(root,
  														outer_expr,
  														NULL,
  														sub_eclass->ec_opfamilies,
  														sub_expr_type,
  														sub_expr_coll,
  														0,
  														rel->relids,
  														false);
  
  					/*
  					 * If we don't find a matching EC, this sub-pathkey isn't
  					 * interesting to the outer query
  					 */
  					if (!outer_ec)
  						continue;
  
  					outer_pk = make_canonical_pathkey(root,
  													  outer_ec,
  													  sub_pathkey->pk_opfamily,
  													  sub_pathkey->pk_strategy,
  													  sub_pathkey->pk_nulls_first);
  					/* score = # of equivalence peers */
  					score = list_length(outer_ec->ec_members) - 1;
  					/* +1 if it matches the proper query_pathkeys item */
  					if (retvallen < outer_query_keys &&
  						list_nth(root->query_pathkeys, retvallen) == outer_pk)
  						score++;
  					if (score > best_score)
  					{
  						best_pathkey = outer_pk;
  						best_score = score;
  					}
  				}
  			}
  		}
  
  		/*
  		 * If we couldn't find a representation of this sub_pathkey, we're
  		 * done (we can't use the ones to its right, either).
  		 */
  		if (!best_pathkey)
  			break;
  
  		/*
  		 * Eliminate redundant ordering info; could happen if outer query
  		 * equivalences subquery keys...
  		 */
  		if (!pathkey_is_redundant(best_pathkey, retval))
  		{
  			retval = lappend(retval, best_pathkey);
  			retvallen++;
  		}
  	}
  
  	return retval;
  }
  
  /*
   * build_join_pathkeys
   *	  Build the path keys for a join relation constructed by mergejoin or
   *	  nestloop join.  This is normally the same as the outer path's keys.
   *
   *	  EXCEPTION: in a FULL or RIGHT join, we cannot treat the result as
   *	  having the outer path's path keys, because null lefthand rows may be
   *	  inserted at random points.  It must be treated as unsorted.
   *
   *	  We truncate away any pathkeys that are uninteresting for higher joins.
   *
   * 'joinrel' is the join relation that paths are being formed for
   * 'jointype' is the join type (inner, left, full, etc)
   * 'outer_pathkeys' is the list of the current outer path's path keys
   *
   * Returns the list of new path keys.
   */
  List *
  build_join_pathkeys(PlannerInfo *root,
  					RelOptInfo *joinrel,
  					JoinType jointype,
  					List *outer_pathkeys)
  {
  	if (jointype == JOIN_FULL || jointype == JOIN_RIGHT)
  		return NIL;
  
  	/*
  	 * This used to be quite a complex bit of code, but now that all pathkey
  	 * sublists start out life canonicalized, we don't have to do a darn thing
  	 * here!
  	 *
  	 * We do, however, need to truncate the pathkeys list, since it may
  	 * contain pathkeys that were useful for forming this joinrel but are
  	 * uninteresting to higher levels.
  	 */
  	return truncate_useless_pathkeys(root, joinrel, outer_pathkeys);
  }
  
  /****************************************************************************
   *		PATHKEYS AND SORT CLAUSES
   ****************************************************************************/
  
  /*
   * make_pathkeys_for_sortclauses
   *		Generate a pathkeys list that represents the sort order specified
   *		by a list of SortGroupClauses
   *
   * The resulting PathKeys are always in canonical form.  (Actually, there
   * is no longer any code anywhere that creates non-canonical PathKeys.)
   *
   * We assume that root->nullable_baserels is the set of base relids that could
   * have gone to NULL below the SortGroupClause expressions.  This is okay if
   * the expressions came from the query's top level (ORDER BY, DISTINCT, etc)
   * and if this function is only invoked after deconstruct_jointree.  In the
   * future we might have to make callers pass in the appropriate
   * nullable-relids set, but for now it seems unnecessary.
   *
   * 'sortclauses' is a list of SortGroupClause nodes
   * 'tlist' is the targetlist to find the referenced tlist entries in
   */
  List *
  make_pathkeys_for_sortclauses(PlannerInfo *root,
  							  List *sortclauses,
  							  List *tlist)
  {
  	List	   *pathkeys = NIL;
  	ListCell   *l;
  
  	foreach(l, sortclauses)
  	{
  		SortGroupClause *sortcl = (SortGroupClause *) lfirst(l);
  		Expr	   *sortkey;
  		PathKey    *pathkey;
  
  		sortkey = (Expr *) get_sortgroupclause_expr(sortcl, tlist);
  		Assert(OidIsValid(sortcl->sortop));
  		pathkey = make_pathkey_from_sortop(root,
  										   sortkey,
  										   root->nullable_baserels,
  										   sortcl->sortop,
  										   sortcl->nulls_first,
  										   sortcl->tleSortGroupRef,
  										   true);
  
  		/* Canonical form eliminates redundant ordering keys */
  		if (!pathkey_is_redundant(pathkey, pathkeys))
  			pathkeys = lappend(pathkeys, pathkey);
  	}
  	return pathkeys;
  }
  
  /****************************************************************************
   *		PATHKEYS AND MERGECLAUSES
   ****************************************************************************/
  
  /*
   * initialize_mergeclause_eclasses
   *		Set the EquivalenceClass links in a mergeclause restrictinfo.
   *
   * RestrictInfo contains fields in which we may cache pointers to
   * EquivalenceClasses for the left and right inputs of the mergeclause.
   * (If the mergeclause is a true equivalence clause these will be the
   * same EquivalenceClass, otherwise not.)  If the mergeclause is either
   * used to generate an EquivalenceClass, or derived from an EquivalenceClass,
   * then it's easy to set up the left_ec and right_ec members --- otherwise,
   * this function should be called to set them up.  We will generate new
   * EquivalenceClauses if necessary to represent the mergeclause's left and
   * right sides.
   *
   * Note this is called before EC merging is complete, so the links won't
   * necessarily point to canonical ECs.  Before they are actually used for
   * anything, update_mergeclause_eclasses must be called to ensure that
   * they've been updated to point to canonical ECs.
   */
  void
  initialize_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
  {
  	Expr	   *clause = restrictinfo->clause;
  	Oid			lefttype,
  				righttype;
  
  	/* Should be a mergeclause ... */
  	Assert(restrictinfo->mergeopfamilies != NIL);
  	/* ... with links not yet set */
  	Assert(restrictinfo->left_ec == NULL);
  	Assert(restrictinfo->right_ec == NULL);
  
  	/* Need the declared input types of the operator */
  	op_input_types(((OpExpr *) clause)->opno, &lefttype, &righttype);
  
  	/* Find or create a matching EquivalenceClass for each side */
  	restrictinfo->left_ec =
  		get_eclass_for_sort_expr(root,
  								 (Expr *) get_leftop(clause),
  								 restrictinfo->nullable_relids,
  								 restrictinfo->mergeopfamilies,
  								 lefttype,
  								 ((OpExpr *) clause)->inputcollid,
  								 0,
  								 NULL,
  								 true);
  	restrictinfo->right_ec =
  		get_eclass_for_sort_expr(root,
  								 (Expr *) get_rightop(clause),
  								 restrictinfo->nullable_relids,
  								 restrictinfo->mergeopfamilies,
  								 righttype,
  								 ((OpExpr *) clause)->inputcollid,
  								 0,
  								 NULL,
  								 true);
  }
  
  /*
   * update_mergeclause_eclasses
   *		Make the cached EquivalenceClass links valid in a mergeclause
   *		restrictinfo.
   *
   * These pointers should have been set by process_equivalence or
   * initialize_mergeclause_eclasses, but they might have been set to
   * non-canonical ECs that got merged later.  Chase up to the canonical
   * merged parent if so.
   */
  void
  update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
  {
  	/* Should be a merge clause ... */
  	Assert(restrictinfo->mergeopfamilies != NIL);
  	/* ... with pointers already set */
  	Assert(restrictinfo->left_ec != NULL);
  	Assert(restrictinfo->right_ec != NULL);
  
  	/* Chase up to the top as needed */
  	while (restrictinfo->left_ec->ec_merged)
  		restrictinfo->left_ec = restrictinfo->left_ec->ec_merged;
  	while (restrictinfo->right_ec->ec_merged)
  		restrictinfo->right_ec = restrictinfo->right_ec->ec_merged;
  }
  
  /*
   * find_mergeclauses_for_outer_pathkeys
   *	  This routine attempts to find a list of mergeclauses that can be
   *	  used with a specified ordering for the join's outer relation.
   *	  If successful, it returns a list of mergeclauses.
   *
   * 'pathkeys' is a pathkeys list showing the ordering of an outer-rel path.
   * 'restrictinfos' is a list of mergejoinable restriction clauses for the
   *			join relation being formed, in no particular order.
   *
   * The restrictinfos must be marked (via outer_is_left) to show which side
   * of each clause is associated with the current outer path.  (See
   * select_mergejoin_clauses())
   *
   * The result is NIL if no merge can be done, else a maximal list of
   * usable mergeclauses (represented as a list of their restrictinfo nodes).
   * The list is ordered to match the pathkeys, as required for execution.
   */
  List *
  find_mergeclauses_for_outer_pathkeys(PlannerInfo *root,
  									 List *pathkeys,
  									 List *restrictinfos)
  {
  	List	   *mergeclauses = NIL;
  	ListCell   *i;
  
  	/* make sure we have eclasses cached in the clauses */
  	foreach(i, restrictinfos)
  	{
  		RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
  
  		update_mergeclause_eclasses(root, rinfo);
  	}
  
  	foreach(i, pathkeys)
  	{
  		PathKey    *pathkey = (PathKey *) lfirst(i);
  		EquivalenceClass *pathkey_ec = pathkey->pk_eclass;
  		List	   *matched_restrictinfos = NIL;
  		ListCell   *j;
  
  		/*----------
  		 * A mergejoin clause matches a pathkey if it has the same EC.
  		 * If there are multiple matching clauses, take them all.  In plain
  		 * inner-join scenarios we expect only one match, because
  		 * equivalence-class processing will have removed any redundant
  		 * mergeclauses.  However, in outer-join scenarios there might be
  		 * multiple matches.  An example is
  		 *
  		 *	select * from a full join b
  		 *		on a.v1 = b.v1 and a.v2 = b.v2 and a.v1 = b.v2;
  		 *
  		 * Given the pathkeys ({a.v1}, {a.v2}) it is okay to return all three
  		 * clauses (in the order a.v1=b.v1, a.v1=b.v2, a.v2=b.v2) and indeed
  		 * we *must* do so or we will be unable to form a valid plan.
  		 *
  		 * We expect that the given pathkeys list is canonical, which means
  		 * no two members have the same EC, so it's not possible for this
  		 * code to enter the same mergeclause into the result list twice.
  		 *
  		 * It's possible that multiple matching clauses might have different
  		 * ECs on the other side, in which case the order we put them into our
  		 * result makes a difference in the pathkeys required for the inner
  		 * input rel.  However this routine hasn't got any info about which
  		 * order would be best, so we don't worry about that.
  		 *
  		 * It's also possible that the selected mergejoin clauses produce
  		 * a noncanonical ordering of pathkeys for the inner side, ie, we
  		 * might select clauses that reference b.v1, b.v2, b.v1 in that
  		 * order.  This is not harmful in itself, though it suggests that
  		 * the clauses are partially redundant.  Since the alternative is
  		 * to omit mergejoin clauses and thereby possibly fail to generate a
  		 * plan altogether, we live with it.  make_inner_pathkeys_for_merge()
  		 * has to delete duplicates when it constructs the inner pathkeys
  		 * list, and we also have to deal with such cases specially in
  		 * create_mergejoin_plan().
  		 *----------
  		 */
  		foreach(j, restrictinfos)
  		{
  			RestrictInfo *rinfo = (RestrictInfo *) lfirst(j);
  			EquivalenceClass *clause_ec;
  
  			clause_ec = rinfo->outer_is_left ?
  				rinfo->left_ec : rinfo->right_ec;
  			if (clause_ec == pathkey_ec)
  				matched_restrictinfos = lappend(matched_restrictinfos, rinfo);
  		}
  
  		/*
  		 * 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.)
  		 */
  		if (matched_restrictinfos == NIL)
  			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;
  }
  
  /*
   * select_outer_pathkeys_for_merge
   *	  Builds a pathkey list representing a possible sort ordering
   *	  that can be used with the given mergeclauses.
   *
   * 'mergeclauses' is a list of RestrictInfos for mergejoin clauses
   *			that will be used in a merge join.
   * 'joinrel' is the join relation we are trying to construct.
   *
   * The restrictinfos must be marked (via outer_is_left) to show which side
   * of each clause is associated with the current outer path.  (See
   * select_mergejoin_clauses())
   *
   * Returns a pathkeys list that can be applied to the outer relation.
   *
   * Since we assume here that a sort is required, there is no particular use
   * in matching any available ordering of the outerrel.  (joinpath.c has an
   * entirely separate code path for considering sort-free mergejoins.)  Rather,
   * it's interesting to try to match the requested query_pathkeys so that a
   * second output sort may be avoided; and failing that, we try to list "more
   * popular" keys (those with the most unmatched EquivalenceClass peers)
   * earlier, in hopes of making the resulting ordering useful for as many
   * higher-level mergejoins as possible.
   */
  List *
  select_outer_pathkeys_for_merge(PlannerInfo *root,
  								List *mergeclauses,
  								RelOptInfo *joinrel)
  {
  	List	   *pathkeys = NIL;
  	int			nClauses = list_length(mergeclauses);
  	EquivalenceClass **ecs;
  	int		   *scores;
  	int			necs;
  	ListCell   *lc;
  	int			j;
  
  	/* Might have no mergeclauses */
  	if (nClauses == 0)
  		return NIL;
  
  	/*
  	 * Make arrays of the ECs used by the mergeclauses (dropping any
  	 * duplicates) and their "popularity" scores.
  	 */
  	ecs = (EquivalenceClass **) palloc(nClauses * sizeof(EquivalenceClass *));
  	scores = (int *) palloc(nClauses * sizeof(int));
  	necs = 0;
  
  	foreach(lc, mergeclauses)
  	{
  		RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
  		EquivalenceClass *oeclass;
  		int			score;
  		ListCell   *lc2;
  
  		/* get the outer eclass */
  		update_mergeclause_eclasses(root, rinfo);
  
  		if (rinfo->outer_is_left)
  			oeclass = rinfo->left_ec;
  		else
  			oeclass = rinfo->right_ec;
  
  		/* reject duplicates */
  		for (j = 0; j < necs; j++)
  		{
  			if (ecs[j] == oeclass)
  				break;
  		}
  		if (j < necs)
  			continue;
  
  		/* compute score */
  		score = 0;
  		foreach(lc2, oeclass->ec_members)
  		{
  			EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);
  
  			/* Potential future join partner? */
  			if (!em->em_is_const && !em->em_is_child &&
  				!bms_overlap(em->em_relids, joinrel->relids))
  				score++;
  		}
  
  		ecs[necs] = oeclass;
  		scores[necs] = score;
  		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.
  	 */
  	if (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 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);
  			/* mark their ECs as already-emitted */
  			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)
  					{
  						scores[j] = -1;
  						break;
  					}
  				}
  			}
  		}
  	}
  
  	/*
  	 * 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.)
  	 */
  	for (;;)
  	{
  		int			best_j;
  		int			best_score;
  		EquivalenceClass *ec;
  		PathKey    *pathkey;
  
  		best_j = 0;
  		best_score = scores[0];
  		for (j = 1; j < necs; j++)
  		{
  			if (scores[j] > best_score)
  			{
  				best_j = j;
  				best_score = scores[j];
  			}
  		}
  		if (best_score < 0)
  			break;				/* all done */
  		ec = ecs[best_j];
  		scores[best_j] = -1;
  		pathkey = make_canonical_pathkey(root,
  										 ec,
  										 linitial_oid(ec->ec_opfamilies),
  										 BTLessStrategyNumber,
  										 false);
  		/* can't be redundant because no duplicate ECs */
  		Assert(!pathkey_is_redundant(pathkey, pathkeys));
  		pathkeys = lappend(pathkeys, pathkey);
  	}
  
  	pfree(ecs);
  	pfree(scores);
  
  	return pathkeys;
  }
  
  /*
   * make_inner_pathkeys_for_merge
   *	  Builds a pathkey list representing the explicit sort order that
   *	  must be applied to an inner path to make it usable with the
   *	  given mergeclauses.
   *
   * 'mergeclauses' is a list of RestrictInfos for the mergejoin clauses
   *			that will be used in a merge join, in order.
   * 'outer_pathkeys' are the already-known canonical pathkeys for the outer
   *			side of the join.
   *
   * The restrictinfos must be marked (via outer_is_left) to show which side
   * of each clause is associated with the current outer path.  (See
   * select_mergejoin_clauses())
   *
   * Returns a pathkeys list that can be applied to the inner relation.
   *
   * Note that it is not this routine's job to decide whether sorting is
   * actually needed for a particular input path.  Assume a sort is necessary;
   * just make the keys, eh?
   */
  List *
  make_inner_pathkeys_for_merge(PlannerInfo *root,
  							  List *mergeclauses,
  							  List *outer_pathkeys)
  {
  	List	   *pathkeys = NIL;
  	EquivalenceClass *lastoeclass;
  	PathKey    *opathkey;
  	ListCell   *lc;
  	ListCell   *lop;
  
  	lastoeclass = NULL;
  	opathkey = NULL;
  	lop = list_head(outer_pathkeys);
  
  	foreach(lc, mergeclauses)
  	{
  		RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
  		EquivalenceClass *oeclass;
  		EquivalenceClass *ieclass;
  		PathKey    *pathkey;
  
  		update_mergeclause_eclasses(root, rinfo);
  
  		if (rinfo->outer_is_left)
  		{
  			oeclass = rinfo->left_ec;
  			ieclass = rinfo->right_ec;
  		}
  		else
  		{
  			oeclass = rinfo->right_ec;
  			ieclass = rinfo->left_ec;
  		}
  
  		/* outer eclass should match current or next pathkeys */
  		/* we check this carefully for debugging reasons */
  		if (oeclass != lastoeclass)
  		{
  			if (!lop)
  				elog(ERROR, "too few pathkeys for mergeclauses");
  			opathkey = (PathKey *) lfirst(lop);
  			lop = lnext(lop);
  			lastoeclass = opathkey->pk_eclass;
  			if (oeclass != lastoeclass)
  				elog(ERROR, "outer pathkeys do not match mergeclause");
  		}
  
  		/*
  		 * Often, we'll have same EC on both sides, in which case the outer
  		 * pathkey is also canonical for the inner side, and we can skip a
  		 * useless search.
  		 */
  		if (ieclass == oeclass)
  			pathkey = opathkey;
  		else
  			pathkey = make_canonical_pathkey(root,
  											 ieclass,
  											 opathkey->pk_opfamily,
  											 opathkey->pk_strategy,
  											 opathkey->pk_nulls_first);
  
  		/*
  		 * Don't generate redundant pathkeys (which can happen if multiple
  		 * mergeclauses refer to the same EC).  Because we do this, the output
  		 * pathkey list isn't necessarily ordered like the mergeclauses, which
  		 * complicates life for create_mergejoin_plan().  But if we didn't,
  		 * we'd have a noncanonical sort key list, which would be bad; for one
  		 * reason, it certainly wouldn't match any available sort order for
  		 * the input relation.
  		 */
  		if (!pathkey_is_redundant(pathkey, pathkeys))
  			pathkeys = lappend(pathkeys, pathkey);
  	}
  
  	return pathkeys;
  }
  
  /*
   * trim_mergeclauses_for_inner_pathkeys
   *	  This routine trims a list of mergeclauses to include just those that
   *	  work with a specified ordering for the join's inner relation.
   *
   * 'mergeclauses' is a list of RestrictInfos for mergejoin clauses for the
   *			join relation being formed, in an order known to work for the
   *			currently-considered sort ordering of the join's outer rel.
   * 'pathkeys' is a pathkeys list showing the ordering of an inner-rel path;
   *			it should be equal to, or a truncation of, the result of
   *			make_inner_pathkeys_for_merge for these mergeclauses.
   *
   * What we return will be a prefix of the given mergeclauses list.
   *
   * We need this logic because make_inner_pathkeys_for_merge's result isn't
   * necessarily in the same order as the mergeclauses.  That means that if we
   * consider an inner-rel pathkey list that is a truncation of that result,
   * we might need to drop mergeclauses even though they match a surviving inner
   * pathkey.  This happens when they are to the right of a mergeclause that
   * matches a removed inner pathkey.
   *
   * The mergeclauses must be marked (via outer_is_left) to show which side
   * of each clause is associated with the current outer path.  (See
   * select_mergejoin_clauses())
   */
  List *
  trim_mergeclauses_for_inner_pathkeys(PlannerInfo *root,
  									 List *mergeclauses,
  									 List *pathkeys)
  {
  	List	   *new_mergeclauses = NIL;
  	PathKey    *pathkey;
  	EquivalenceClass *pathkey_ec;
  	bool		matched_pathkey;
  	ListCell   *lip;
  	ListCell   *i;
  
  	/* No pathkeys => no mergeclauses (though we don't expect this case) */
  	if (pathkeys == NIL)
  		return NIL;
  	/* Initialize to consider first pathkey */
  	lip = list_head(pathkeys);
  	pathkey = (PathKey *) lfirst(lip);
  	pathkey_ec = pathkey->pk_eclass;
  	lip = lnext(lip);
  	matched_pathkey = false;
  
  	/* Scan mergeclauses to see how many we can use */
  	foreach(i, mergeclauses)
  	{
  		RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
  		EquivalenceClass *clause_ec;
  
  		/* Assume we needn't do update_mergeclause_eclasses again here */
  
  		/* Check clause's inner-rel EC against current pathkey */
  		clause_ec = rinfo->outer_is_left ?
  			rinfo->right_ec : rinfo->left_ec;
  
  		/* If we don't have a match, attempt to advance to next pathkey */
  		if (clause_ec != pathkey_ec)
  		{
  			/* If we had no clauses matching this inner pathkey, must stop */
  			if (!matched_pathkey)
  				break;
  
  			/* Advance to next inner pathkey, if any */
  			if (lip == NULL)
  				break;
  			pathkey = (PathKey *) lfirst(lip);
  			pathkey_ec = pathkey->pk_eclass;
  			lip = lnext(lip);
  			matched_pathkey = false;
  		}
  
  		/* If mergeclause matches current inner pathkey, we can use it */
  		if (clause_ec == pathkey_ec)
  		{
  			new_mergeclauses = lappend(new_mergeclauses, rinfo);
  			matched_pathkey = true;
  		}
  		else
  		{
  			/* Else, no hope of adding any more mergeclauses */
  			break;
  		}
  	}
  
  	return new_mergeclauses;
  }
  
  
  /****************************************************************************
   *		PATHKEY USEFULNESS CHECKS
   *
   * We only want to remember as many of the pathkeys of a path as have some
   * potential use, either for subsequent mergejoins or for meeting the query's
   * requested output ordering.  This ensures that add_path() won't consider
   * a path to have a usefully different ordering unless it really is useful.
   * These routines check for usefulness of given pathkeys.
   ****************************************************************************/
  
  /*
   * pathkeys_useful_for_merging
   *		Count the number of pathkeys that may be useful for mergejoins
   *		above the given relation.
   *
   * We consider a pathkey potentially useful if it corresponds to the merge
   * ordering of either side of any joinclause for the rel.  This might be
   * overoptimistic, since joinclauses that require different other relations
   * might never be usable at the same time, but trying to be exact is likely
   * to be more trouble than it's worth.
   *
   * To avoid doubling the number of mergejoin paths considered, we would like
   * to consider only one of the two scan directions (ASC or DESC) as useful
   * for merging for any given target column.  The choice is arbitrary unless
   * 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.
   */
  static int
  pathkeys_useful_for_merging(PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
  {
  	int			useful = 0;
  	ListCell   *i;
  
  	foreach(i, pathkeys)
  	{
  		PathKey    *pathkey = (PathKey *) lfirst(i);
  		bool		matched = false;
  		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
  		 * surely possible to generate a mergejoin clause using them.
  		 */
  		if (rel->has_eclass_joins &&
  			eclass_useful_for_merging(root, pathkey->pk_eclass, rel))
  			matched = true;
  		else
  		{
  			/*
  			 * Otherwise search the rel's joininfo list, which contains
  			 * non-EquivalenceClass-derivable join clauses that might
  			 * nonetheless be mergejoinable.
  			 */
  			foreach(j, rel->joininfo)
  			{
  				RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(j);
  
  				if (restrictinfo->mergeopfamilies == NIL)
  					continue;
  				update_mergeclause_eclasses(root, restrictinfo);
  
  				if (pathkey->pk_eclass == restrictinfo->left_ec ||
  					pathkey->pk_eclass == restrictinfo->right_ec)
  				{
  					matched = true;
  					break;
  				}
  			}
  		}
  
  		/*
  		 * 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.)
  		 */
  		if (matched)
  			useful++;
  		else
  			break;
  	}
  
  	return useful;
  }
  
  /*
   * right_merge_direction
   *		Check whether the pathkey embodies the preferred sort direction
   *		for merging its target column.
   */
  static bool
  right_merge_direction(PlannerInfo *root, PathKey *pathkey)
  {
  	ListCell   *l;
  
  	foreach(l, root->query_pathkeys)
  	{
  		PathKey    *query_pathkey = (PathKey *) lfirst(l);
  
  		if (pathkey->pk_eclass == query_pathkey->pk_eclass &&
  			pathkey->pk_opfamily == query_pathkey->pk_opfamily)
  		{
  			/*
  			 * Found a matching query sort column.  Prefer this pathkey's
  			 * direction iff it matches.  Note that we ignore pk_nulls_first,
  			 * which means that a sort might be needed anyway ... but we still
  			 * want to prefer only one of the two possible directions, and we
  			 * might as well use this one.
  			 */
  			return (pathkey->pk_strategy == query_pathkey->pk_strategy);
  		}
  	}
  
  	/* If no matching ORDER BY request, prefer the ASC direction */
  	return (pathkey->pk_strategy == BTLessStrategyNumber);
  }
  
  /*
   * pathkeys_useful_for_ordering
   *		Count the number of pathkeys that are useful for meeting the
   *		query's requested output ordering.
   *
   * Unlike merge pathkeys, this is an all-or-nothing affair: it does us
   * no good to order by just the first key(s) of the requested ordering.
   * So the result is always either 0 or list_length(root->query_pathkeys).
   */
  static int
  pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys)
  {
  	if (root->query_pathkeys == NIL)
  		return 0;				/* no special ordering requested */
  
  	if (pathkeys == NIL)
  		return 0;				/* unordered path */
  
  	if (pathkeys_contained_in(root->query_pathkeys, pathkeys))
  	{
  		/* It's useful ... or at least the first N keys are */
  		return list_length(root->query_pathkeys);
  	}
  
  	return 0;					/* path ordering not useful */
  }
  
  /*
   * truncate_useless_pathkeys
   *		Shorten the given pathkey list to just the useful pathkeys.
   */
  List *
  truncate_useless_pathkeys(PlannerInfo *root,
  						  RelOptInfo *rel,
  						  List *pathkeys)
  {
  	int			nuseful;
  	int			nuseful2;
  
  	nuseful = pathkeys_useful_for_merging(root, rel, pathkeys);
  	nuseful2 = pathkeys_useful_for_ordering(root, pathkeys);
  	if (nuseful2 > nuseful)
  		nuseful = nuseful2;
  
  	/*
  	 * Note: not safe to modify input list destructively, but we can avoid
  	 * copying the list if we're not actually going to change it
  	 */
  	if (nuseful == 0)
  		return NIL;
  	else if (nuseful == list_length(pathkeys))
  		return pathkeys;
  	else
  		return list_truncate(list_copy(pathkeys), nuseful);
  }
  
  /*
   * has_useful_pathkeys
   *		Detect whether the specified rel could have any pathkeys that are
   *		useful according to truncate_useless_pathkeys().
   *
   * This is a cheap test that lets us skip building pathkeys at all in very
   * simple queries.  It's OK to err in the direction of returning "true" when
   * there really aren't any usable pathkeys, but erring in the other direction
   * is bad --- so keep this in sync with the routines above!
   *
   * We could make the test more complex, for example checking to see if any of
   * the joinclauses are really mergejoinable, but that likely wouldn't win
   * often enough to repay the extra cycles.  Queries with neither a join nor
   * a sort are reasonably common, though, so this much work seems worthwhile.
   */
  bool
  has_useful_pathkeys(PlannerInfo *root, RelOptInfo *rel)
  {
  	if (rel->joininfo != NIL || rel->has_eclass_joins)
  		return true;			/* might be able to use pathkeys for merging */
  	if (root->query_pathkeys != NIL)
  		return true;			/* might be able to use them for ordering */
  	return false;				/* definitely useless */
  }
  