pathkeys.c

来自「postgresql8.3.4源码,开源数据库」· C语言 代码 · 共 1,494 行 · 第 1/3 页

		{
			sortop = index->fwdsortop[i];
			nulls_first = index->nulls_first[i];
		}

		if (!OidIsValid(sortop))
			break;				/* no more orderable columns */

		ikey = index->indexkeys[i];
		if (ikey != 0)
		{
			/* simple index column */
			indexkey = (Expr *) find_indexkey_var(root, index->rel, ikey);
		}
		else
		{
			/* expression --- assume we need not copy it */
			if (indexprs_item == NULL)
				elog(ERROR, "wrong number of index expressions");
			indexkey = (Expr *) lfirst(indexprs_item);
			indexprs_item = lnext(indexprs_item);
		}

		/* OK, make a canonical pathkey for this sort key */
		cpathkey = make_pathkey_from_sortinfo(root,
											  indexkey,
											  sortop,
											  nulls_first,
											  0,
											  true);

		/* Add to list unless redundant */
		if (!pathkey_is_redundant(cpathkey, retval))
			retval = lappend(retval, cpathkey);
	}

	return retval;
}

/*
 * Find or make a Var node for the specified attribute of the rel.
 *
 * We first look for the var in the rel's target list, because that's
 * easy and fast.  But the var might not be there (this should normally
 * only happen for vars that are used in WHERE restriction clauses,
 * but not in join clauses or in the SELECT target list).  In that case,
 * gin up a Var node the hard way.
 */
static Var *
find_indexkey_var(PlannerInfo *root, RelOptInfo *rel, AttrNumber varattno)
{
	ListCell   *temp;
	Index		relid;
	Oid			reloid,
				vartypeid;
	int32		type_mod;

	foreach(temp, rel->reltargetlist)
	{
		Var		   *var = (Var *) lfirst(temp);

		if (IsA(var, Var) &&
			var->varattno == varattno)
			return var;
	}

	relid = rel->relid;
	reloid = getrelid(relid, root->parse->rtable);
	get_atttypetypmod(reloid, varattno, &vartypeid, &type_mod);

	return makeVar(relid, varattno, vartypeid, type_mod, 0);
}

/*
 * 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.
 *
 * 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	   *retval = NIL;
	int			retvallen = 0;
	int			outer_query_keys = list_length(root->query_pathkeys);
	List	   *sub_tlist = rel->subplan->targetlist;
	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, sub_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 *)
					makeVar(rel->relid,
							tle->resno,
							exprType((Node *) tle->expr),
							exprTypmod((Node *) tle->expr),
							0);
				outer_ec =
					get_eclass_for_sort_expr(root,
											 outer_expr,
											 sub_member->em_datatype,
											 sub_eclass->ec_opfamilies,
											 0);
				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;
				Expr	   *sub_stripped;
				ListCell   *k;

				/*
				 * We handle two cases: the sub_pathkey key can be either an
				 * exact match for a targetlist entry, or it could match after
				 * stripping RelabelType nodes.  (We need that case since
				 * make_pathkey_from_sortinfo could add or remove
				 * RelabelType.)
				 */
				sub_stripped = sub_expr;
				while (sub_stripped && IsA(sub_stripped, RelabelType))
					sub_stripped = ((RelabelType *) sub_stripped)->arg;

				foreach(k, sub_tlist)
				{
					TargetEntry *tle = (TargetEntry *) lfirst(k);
					Expr	   *outer_expr;
					EquivalenceClass *outer_ec;
					PathKey    *outer_pk;
					int			score;

					/* resjunk items aren't visible to outer query */
					if (tle->resjunk)
						continue;

					if (equal(tle->expr, sub_expr))
					{
						/* Exact match */
						outer_expr = (Expr *)
							makeVar(rel->relid,
									tle->resno,
									exprType((Node *) tle->expr),
									exprTypmod((Node *) tle->expr),
									0);
					}
					else
					{
						Expr	   *tle_stripped;

						tle_stripped = tle->expr;
						while (tle_stripped && IsA(tle_stripped, RelabelType))
							tle_stripped = ((RelabelType *) tle_stripped)->arg;

						if (equal(tle_stripped, sub_stripped))
						{
							/* Match after discarding RelabelType */
							outer_expr = (Expr *)
								makeVar(rel->relid,
										tle->resno,
										exprType((Node *) tle->expr),
										exprTypmod((Node *) tle->expr),
										0);
							if (exprType((Node *) outer_expr) !=
								exprType((Node *) sub_expr))
								outer_expr = (Expr *)
									makeRelabelType(outer_expr,
												 exprType((Node *) sub_expr),
													-1,
													COERCE_DONTCARE);
						}
						else
							continue;
					}

					/* Found a representation for this sub_pathkey */
					outer_ec = get_eclass_for_sort_expr(root,
														outer_expr,
													 sub_member->em_datatype,
												   sub_eclass->ec_opfamilies,
														0);
					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 SortClauses (GroupClauses will work too!)
 *
 * If canonicalize is TRUE, the resulting PathKeys are all in canonical form;
 * otherwise not.  canonicalize should always be TRUE after EquivalenceClass
 * merging has been performed, but FALSE if we haven't done EquivalenceClass
 * merging yet.  (We provide this option because grouping_planner() needs to
 * be able to represent requested pathkeys before the equivalence classes have
 * been created for the query.)
 *
 * 'sortclauses' is a list of SortClause or GroupClause nodes
 * 'tlist' is the targetlist to find the referenced tlist entries in
 */
List *
make_pathkeys_for_sortclauses(PlannerInfo *root,
							  List *sortclauses,
							  List *tlist,
							  bool canonicalize)
{
	List	   *pathkeys = NIL;
	ListCell   *l;

	foreach(l, sortclauses)
	{
		SortClause *sortcl = (SortClause *) lfirst(l);
		Expr	   *sortkey;
		PathKey    *pathkey;

		sortkey = (Expr *) get_sortgroupclause_expr(sortcl, tlist);
		pathkey = make_pathkey_from_sortinfo(root,
											 sortkey,
											 sortcl->sortop,
											 sortcl->nulls_first,
											 sortcl->tleSortGroupRef,
											 canonicalize);

		/* Canonical form eliminates redundant ordering keys */
		if (canonicalize)
		{
			if (!pathkey_is_redundant(pathkey, pathkeys))
				pathkeys = lappend(pathkeys, pathkey);
		}
		else
			pathkeys = lappend(pathkeys, pathkey);
	}
	return pathkeys;
}

/****************************************************************************
 *		PATHKEYS AND MERGECLAUSES
 ****************************************************************************/

/*
 * cache_mergeclause_eclasses
 *		Make the cached EquivalenceClass links valid 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.)
 */
void
cache_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
{
	Assert(restrictinfo->mergeopfamilies != NIL);

	/* the cached values should be either both set or both not */
	if (restrictinfo->left_ec == NULL)
	{
		Expr	   *clause = restrictinfo->clause;
		Oid			lefttype,
					righttype;

		/* 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),
									 lefttype,
									 restrictinfo->mergeopfamilies,
									 0);
		restrictinfo->right_ec =
			get_eclass_for_sort_expr(root,
									 (Expr *) get_rightop(clause),
									 righttype,
									 restrictinfo->mergeopfamilies,
									 0);
	}
	else
		Assert(restrictinfo->right_ec != NULL);
}

/*
 * 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.
 *	  If successful, it returns a list of mergeclauses.
 *
 * 'pathkeys' is a pathkeys list showing the ordering of an input path.
 * 'outer_keys' is TRUE if these keys are for the outer input path,
 *			FALSE if for inner.
 * 'restrictinfos' is a list of mergejoinable restriction clauses for the
 *			join relation being formed.
 *
 * 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).
 */
List *
find_mergeclauses_for_pathkeys(PlannerInfo *root,
							   List *pathkeys,
							   bool outer_keys,
							   List *restrictinfos)
{
	List	   *mergeclauses = NIL;
	ListCell   *i;

	/* make sure we have eclasses cached in the clauses */
	foreach(i, restrictinfos)
	{
		RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);

		cache_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.
		 *
		 * XXX 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 other input path.  However this routine hasn't got any info
		 * about which order would be best, so for now we disregard that case
		 * (which is probably a corner case anyway).
		 *----------
		 */
		foreach(j, restrictinfos)
		{
			RestrictInfo *rinfo = (RestrictInfo *) lfirst(j);
			EquivalenceClass *clause_ec;

			if (outer_keys)
				clause_ec = rinfo->outer_is_left ?