pathkeys.c

来自「PostgreSQL7.4.6 for Linux」· C语言 代码 · 共 1,266 行 · 第 1/3 页

 *	  Compare two pathkeys to see if they are equivalent, and if not whether
 *	  one is "better" than the other.
 *
 *	  This function may only be applied to canonicalized pathkey lists.
 *	  In the canonical representation, sublists can be checked for equality
 *	  by simple pointer comparison.
 */
PathKeysComparison
compare_pathkeys(List *keys1, List *keys2)
{
	List	   *key1,
			   *key2;

	for (key1 = keys1, key2 = keys2;
		 key1 != NIL && key2 != NIL;
		 key1 = lnext(key1), key2 = lnext(key2))
	{
		List	   *subkey1 = lfirst(key1);
		List	   *subkey2 = lfirst(key2);

		/*
		 * XXX would like to check that we've been given canonicalized
		 * input, but query root not accessible here...
		 */
#ifdef NOT_USED
		Assert(ptrMember(subkey1, root->equi_key_list));
		Assert(ptrMember(subkey2, root->equi_key_list));
#endif

		/*
		 * We will never have two subkeys where one is a subset of the
		 * other, because of the canonicalization process.	Either they
		 * are equal or they ain't.  Furthermore, we only need pointer
		 * comparison to detect equality.
		 */
		if (subkey1 != subkey2)
			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.	(We assume the additional sublist(s) of
	 * the other list are not NIL --- no pathkey list should ever have a
	 * NIL sublist.)
	 */
	if (key1 == NIL && key2 == NIL)
		return PATHKEYS_EQUAL;
	if (key1 != NIL)
		return PATHKEYS_BETTER1;	/* key1 is longer */
	return PATHKEYS_BETTER2;	/* key2 is longer */
}

/*
 * compare_noncanonical_pathkeys
 *	  Compare two pathkeys to see if they are equivalent, and if not whether
 *	  one is "better" than the other.  This is used when we must compare
 *	  non-canonicalized pathkeys.
 *
 *	  A pathkey can be considered better than another if it is a superset:
 *	  it contains all the keys of the other plus more.	For example, either
 *	  ((A) (B)) or ((A B)) is better than ((A)).
 *
 *	  Currently, the only user of this routine is grouping_planner(),
 *	  and it will only pass single-element sublists (from
 *	  make_pathkeys_for_sortclauses).  Therefore we don't have to do the
 *	  full two-way-subset-inclusion test on each pair of sublists that is
 *	  implied by the above statement.  Instead we just verify they are
 *	  singleton lists and then do an equal().  This could be improved if
 *	  necessary.
 */
PathKeysComparison
compare_noncanonical_pathkeys(List *keys1, List *keys2)
{
	List	   *key1,
			   *key2;

	for (key1 = keys1, key2 = keys2;
		 key1 != NIL && key2 != NIL;
		 key1 = lnext(key1), key2 = lnext(key2))
	{
		List	   *subkey1 = lfirst(key1);
		List	   *subkey2 = lfirst(key2);

		Assert(length(subkey1) == 1);
		Assert(length(subkey2) == 1);
		if (!equal(subkey1, subkey2))
			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.	(We assume the additional sublist(s) of
	 * the other list are not NIL --- no pathkey list should ever have a
	 * NIL sublist.)
	 */
	if (key1 == NIL && key2 == NIL)
		return PATHKEYS_EQUAL;
	if (key1 != NIL)
		return PATHKEYS_BETTER1;	/* key1 is longer */
	return PATHKEYS_BETTER2;	/* key2 is longer */
}

/*
 * 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;
}

/*
 * noncanonical_pathkeys_contained_in
 *	  The same, when we don't have canonical pathkeys.
 */
bool
noncanonical_pathkeys_contained_in(List *keys1, List *keys2)
{
	switch (compare_noncanonical_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.  Return NULL if no such path.
 *
 * 'paths' is a list of possible paths that all generate the same relation
 * 'pathkeys' represents a required ordering (already canonicalized!)
 * 'cost_criterion' is STARTUP_COST or TOTAL_COST
 */
Path *
get_cheapest_path_for_pathkeys(List *paths, List *pathkeys,
							   CostSelector cost_criterion)
{
	Path	   *matched_path = NULL;
	List	   *i;

	foreach(i, paths)
	{
		Path	   *path = (Path *) lfirst(i);

		/*
		 * 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 (pathkeys_contained_in(pathkeys, path->pathkeys))
			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.
 *	  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 (already canonicalized!)
 * 'fraction' is the fraction of the total tuples expected to be retrieved
 */
Path *
get_cheapest_fractional_path_for_pathkeys(List *paths,
										  List *pathkeys,
										  double fraction)
{
	Path	   *matched_path = NULL;
	List	   *i;

	foreach(i, paths)
	{
		Path	   *path = (Path *) lfirst(i);

		/*
		 * Since cost comparison is a lot cheaper than pathkey comparison,
		 * do that first.
		 */
		if (matched_path != NULL &&
		compare_fractional_path_costs(matched_path, path, fraction) <= 0)
			continue;

		if (pathkeys_contained_in(pathkeys, path->pathkeys))
			matched_path = path;
	}
	return matched_path;
}

/****************************************************************************
 *		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; such an index will have no sortop OIDS in
 *	  its "ordering" field, and we will return NIL.)
 *
 * If 'scandir' is BackwardScanDirection, attempt to build pathkeys
 * representing a backwards scan of the index.	Return NIL if can't do it.
 *
 * We generate the full pathkeys list whether or not all are useful for the
 * current query.  Caller should do truncate_useless_pathkeys().
 */
List *
build_index_pathkeys(Query *root,
					 RelOptInfo *rel,
					 IndexOptInfo *index,
					 ScanDirection scandir)
{
	List	   *retval = NIL;
	int		   *indexkeys = index->indexkeys;
	Oid		   *ordering = index->ordering;
	List	   *indexprs = index->indexprs;

	while (*ordering != InvalidOid)
	{
		PathKeyItem *item;
		Oid			sortop;
		Node	   *indexkey;
		List	   *cpathkey;

		sortop = *ordering;
		if (ScanDirectionIsBackward(scandir))
		{
			sortop = get_commutator(sortop);
			if (sortop == InvalidOid)
				break;			/* oops, no reverse sort operator? */
		}

		if (*indexkeys != 0)
		{
			/* simple index column */
			indexkey = (Node *) find_indexkey_var(root, rel, *indexkeys);
		}
		else
		{
			/* expression --- assume we need not copy it */
			if (indexprs == NIL)
				elog(ERROR, "wrong number of index expressions");
			indexkey = (Node *) lfirst(indexprs);
			indexprs = lnext(indexprs);
		}

		/* OK, make a sublist for this sort key */
		item = makePathKeyItem(indexkey, sortop, true);
		cpathkey = make_canonical_pathkey(root, item);

		/*
		 * Eliminate redundant ordering info; could happen if query is
		 * such that index keys are equijoined...
		 */
		if (!ptrMember(cpathkey, retval))
			retval = lappend(retval, cpathkey);

		indexkeys++;
		ordering++;
	}

	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(Query *root, RelOptInfo *rel, AttrNumber varattno)
{
	List	   *temp;
	Index		relid;
	Oid			reloid,
				vartypeid;
	int32		type_mod;

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

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

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

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

/*
 * build_subquery_pathkeys
 *	  Build a pathkeys list that describes the ordering of a subquery's
 *	  result (in the terms of the outer query).  The subquery must already
 *	  have been planned, so that its query_pathkeys field has been set.
 *
 * 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 *
build_subquery_pathkeys(Query *root, RelOptInfo *rel, Query *subquery)
{
	List	   *retval = NIL;
	int			retvallen = 0;
	int			outer_query_keys = length(root->query_pathkeys);
	List	   *l;

	foreach(l, subquery->query_pathkeys)
	{
		List	   *sub_pathkey = (List *) lfirst(l);
		List	   *j;
		PathKeyItem *best_item = NULL;
		int			best_score = 0;
		List	   *cpathkey;

		/*
		 * The sub_pathkey 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 a pathkey list of the outer query,
		 * thereby propagating equality knowledge up to the outer query.
		 * Right now we cannot do so, because the outer query's canonical
		 * pathkey sets are already frozen when this is called.  Instead
		 * we prefer the one that has the highest "score" (number of
		 * canonical pathkey peers, plus one if it matches the outer
		 * query_pathkeys). This is the most likely to be useful in the
		 * outer query.
		 */
		foreach(j, sub_pathkey)
		{
			PathKeyItem *sub_item = (PathKeyItem *) lfirst(j);
			Node	   *sub_key = sub_item->key;
			List	   *k;

			foreach(k, subquery->targetList)
			{
				TargetEntry *tle = (TargetEntry *) lfirst(k);

				if (!tle->resdom->resjunk &&
					equal(tle->expr, sub_key))
				{
					/* Found a representation for this sub_key */
					Var		   *outer_var;
					PathKeyItem *outer_item;
					int			score;

					outer_var = makeVar(rel->relid,
										tle->resdom->resno,
										tle->resdom->restype,
										tle->resdom->restypmod,
										0);
					outer_item = makePathKeyItem((Node *) outer_var,
												 sub_item->sortop,
												 true);
					/* score = # of mergejoin peers */
					score = count_canonical_peers(root, outer_item);
					/* +1 if it matches the proper query_pathkeys item */
					if (retvallen < outer_query_keys &&
						member(outer_item,
							   nth(retvallen, root->query_pathkeys)))
						score++;
					if (score > best_score)
					{
						best_item = outer_item;
						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_item)
			break;

		/* Canonicalize the chosen item (we did not before) */
		cpathkey = make_canonical_pathkey(root, best_item);

		/*
		 * Eliminate redundant ordering info; could happen if outer query
		 * equijoins subquery keys...
		 */
		if (!ptrMember(cpathkey, retval))
		{
			retval = lappend(retval, cpathkey);