indxpath.c

PostgreSQL 8.1.4的源码 适用于Linux下的开源数据库系统

		 * the OR, else we can't use it.
		 */
		pathlist = NIL;
		foreach(j, ((BoolExpr *) rinfo->orclause)->args)
		{
			Node	   *orarg = (Node *) lfirst(j);
			List	   *indlist;

			/* OR arguments should be ANDs or sub-RestrictInfos */
			if (and_clause(orarg))
			{
				List	   *andargs = ((BoolExpr *) orarg)->args;

				indlist = find_usable_indexes(root, rel,
											  andargs,
											  all_clauses,
											  false,
											  isjoininner,
											  outer_relids);
				/* Recurse in case there are sub-ORs */
				indlist = list_concat(indlist,
									  generate_bitmap_or_paths(root, rel,
															   andargs,
															   all_clauses,
															   isjoininner,
															   outer_relids));
			}
			else
			{
				Assert(IsA(orarg, RestrictInfo));
				Assert(!restriction_is_or_clause((RestrictInfo *) orarg));
				indlist = find_usable_indexes(root, rel,
											  list_make1(orarg),
											  all_clauses,
											  false,
											  isjoininner,
											  outer_relids);
			}

			/*
			 * If nothing matched this arm, we can't do anything with this OR
			 * clause.
			 */
			if (indlist == NIL)
			{
				pathlist = NIL;
				break;
			}

			/*
			 * OK, pick the most promising AND combination, and add it to
			 * pathlist.
			 */
			bitmapqual = choose_bitmap_and(root, rel, indlist);
			pathlist = lappend(pathlist, bitmapqual);
		}

		/*
		 * If we have a match for every arm, then turn them into a
		 * BitmapOrPath, and add to result list.
		 */
		if (pathlist != NIL)
		{
			bitmapqual = (Path *) create_bitmap_or_path(root, rel, pathlist);
			result = lappend(result, bitmapqual);
		}
	}

	return result;
}


/*
 * choose_bitmap_and
 *		Given a nonempty list of bitmap paths, AND them into one path.
 *
 * This is a nontrivial decision since we can legally use any subset of the
 * given path set.	We want to choose a good tradeoff between selectivity
 * and cost of computing the bitmap.
 *
 * The result is either a single one of the inputs, or a BitmapAndPath
 * combining multiple inputs.
 */
static Path *
choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel, List *paths)
{
	int			npaths = list_length(paths);
	Path	  **patharray;
	Cost		costsofar;
	List	   *qualsofar;
	ListCell   *lastcell;
	int			i;
	ListCell   *l;

	Assert(npaths > 0);			/* else caller error */
	if (npaths == 1)
		return (Path *) linitial(paths);		/* easy case */

	/*
	 * In theory we should consider every nonempty subset of the given paths.
	 * In practice that seems like overkill, given the crude nature of the
	 * estimates, not to mention the possible effects of higher-level AND and
	 * OR clauses.	As a compromise, we sort the paths by selectivity.  We
	 * always take the first, and sequentially add on paths that result in a
	 * lower estimated cost.
	 *
	 * We also make some effort to detect directly redundant input paths, as
	 * can happen if there are multiple possibly usable indexes.  We
	 * consider an index redundant if any of its index conditions were already
	 * used by earlier indexes.  (We could use predicate_implied_by to have a
	 * more intelligent, but much more expensive, check --- but in most cases
	 * simple pointer equality should suffice, since after all the index
	 * conditions are all coming from the same RestrictInfo lists.)
	 *
	 * You might think the condition for redundancy should be "all index
	 * conditions already used", not "any", but this turns out to be wrong.
	 * For example, if we use an index on A, and then come to an index with
	 * conditions on A and B, the only way that the second index can be later
	 * in the selectivity-order sort is if the condition on B is completely
	 * non-selective.  In any case, we'd surely be drastically misestimating
	 * the selectivity if we count the same condition twice.
	 *
	 * We include index predicate conditions in the redundancy test.  Because
	 * the test is just for pointer equality and not equal(), the effect is
	 * that use of the same partial index in two different AND elements is
	 * considered redundant.  (XXX is this too strong?)
	 *
	 * Note: outputting the selected sub-paths in selectivity order is a good
	 * thing even if we weren't using that as part of the selection method,
	 * because it makes the short-circuit case in MultiExecBitmapAnd() more
	 * likely to apply.
	 */

	/* Convert list to array so we can apply qsort */
	patharray = (Path **) palloc(npaths * sizeof(Path *));
	i = 0;
	foreach(l, paths)
	{
		patharray[i++] = (Path *) lfirst(l);
	}
	qsort(patharray, npaths, sizeof(Path *), bitmap_path_comparator);

	paths = list_make1(patharray[0]);
	costsofar = bitmap_and_cost_est(root, rel, paths);
	qualsofar = pull_indexpath_quals(patharray[0]);
	lastcell = list_head(paths);	/* for quick deletions */

	for (i = 1; i < npaths; i++)
	{
		Path	   *newpath = patharray[i];
		List	   *newqual;
		Cost		newcost;

		newqual = pull_indexpath_quals(newpath);
		if (lists_intersect_ptr(newqual, qualsofar))
			continue;			/* consider it redundant */
		/* tentatively add newpath to paths, so we can estimate cost */
		paths = lappend(paths, newpath);
		newcost = bitmap_and_cost_est(root, rel, paths);
		if (newcost < costsofar)
		{
			/* keep newpath in paths, update subsidiary variables */
			costsofar = newcost;
			qualsofar = list_concat(qualsofar, newqual);
			lastcell = lnext(lastcell);
		}
		else
		{
			/* reject newpath, remove it from paths list */
			paths = list_delete_cell(paths, lnext(lastcell), lastcell);
		}
		Assert(lnext(lastcell) == NULL);
	}

	if (list_length(paths) == 1)
		return (Path *) linitial(paths);		/* no need for AND */
	return (Path *) create_bitmap_and_path(root, rel, paths);
}

/* qsort comparator to sort in increasing selectivity order */
static int
bitmap_path_comparator(const void *a, const void *b)
{
	Path	   *pa = *(Path *const *) a;
	Path	   *pb = *(Path *const *) b;
	Cost		acost;
	Cost		bcost;
	Selectivity aselec;
	Selectivity bselec;
	Selectivity diff;

	cost_bitmap_tree_node(pa, &acost, &aselec);
	cost_bitmap_tree_node(pb, &bcost, &bselec);

	/*
	 * Since selectivities are often pretty crude, don't put blind faith
	 * in them; if the selectivities are within 1% of being the same, treat
	 * them as equal and sort by cost instead.
	 */
	diff = aselec - bselec;
	if (diff < -0.01)
		return -1;
	if (diff > 0.01)
		return 1;

	if (acost < bcost)
		return -1;
	if (acost > bcost)
		return 1;

	return 0;
}

/*
 * Estimate the cost of actually executing a BitmapAnd with the given
 * inputs.
 */
static Cost
bitmap_and_cost_est(PlannerInfo *root, RelOptInfo *rel, List *paths)
{
	BitmapAndPath apath;
	Path		bpath;

	/* Set up a dummy BitmapAndPath */
	apath.path.type = T_BitmapAndPath;
	apath.path.parent = rel;
	apath.bitmapquals = paths;
	cost_bitmap_and_node(&apath, root);

	/* Now we can do cost_bitmap_heap_scan */
	cost_bitmap_heap_scan(&bpath, root, rel, (Path *) &apath, false);

	return bpath.total_cost;
}

/*
 * pull_indexpath_quals
 *
 * Given the Path structure for a plain or bitmap indexscan, extract a list
 * of all the indexquals and index predicate conditions used in the Path.
 *
 * This is sort of a simplified version of make_restrictinfo_from_bitmapqual;
 * here, we are not trying to produce an accurate representation of the AND/OR
 * semantics of the Path, but just find out all the base conditions used.
 *
 * The result list contains pointers to the expressions used in the Path,
 * but all the list cells are freshly built, so it's safe to destructively
 * modify the list (eg, by concat'ing it with other lists).
 */
static List *
pull_indexpath_quals(Path *bitmapqual)
{
	List	   *result = NIL;
	ListCell   *l;

	if (IsA(bitmapqual, BitmapAndPath))
	{
		BitmapAndPath *apath = (BitmapAndPath *) bitmapqual;

		foreach(l, apath->bitmapquals)
		{
			List	   *sublist;

			sublist = pull_indexpath_quals((Path *) lfirst(l));
			result = list_concat(result, sublist);
		}
	}
	else if (IsA(bitmapqual, BitmapOrPath))
	{
		BitmapOrPath *opath = (BitmapOrPath *) bitmapqual;

		foreach(l, opath->bitmapquals)
		{
			List	   *sublist;

			sublist = pull_indexpath_quals((Path *) lfirst(l));
			result = list_concat(result, sublist);
		}
	}
	else if (IsA(bitmapqual, IndexPath))
	{
		IndexPath  *ipath = (IndexPath *) bitmapqual;

		result = get_actual_clauses(ipath->indexclauses);
		result = list_concat(result, list_copy(ipath->indexinfo->indpred));
	}
	else
		elog(ERROR, "unrecognized node type: %d", nodeTag(bitmapqual));

	return result;
}


/*
 * lists_intersect_ptr
 *		Detect whether two lists have a nonempty intersection,
 *		using pointer equality to compare members.
 *
 * This possibly should go into list.c, but it doesn't yet have any use
 * except in choose_bitmap_and.
 */
static bool
lists_intersect_ptr(List *list1, List *list2)
{
	ListCell   *cell1;

	foreach(cell1, list1)
	{
		void   *datum1 = lfirst(cell1);
		ListCell   *cell2;

		foreach(cell2, list2)
		{
			if (lfirst(cell2) == datum1)
				return true;
		}
	}

	return false;
}


/****************************************************************************
 *				----  ROUTINES TO CHECK RESTRICTIONS  ----
 ****************************************************************************/


/*
 * group_clauses_by_indexkey
 *	  Find restriction clauses that can be used with an index.
 *
 * Returns a list of sublists of RestrictInfo nodes for clauses that can be
 * used with this index.  Each sublist contains clauses that can be used
 * with one index key (in no particular order); the top list is ordered by
 * index key.  (This is depended on by expand_indexqual_conditions().)
 *
 * We can use clauses from either the current clauses or outer_clauses lists,
 * but *found_clause is set TRUE only if we used at least one clause from
 * the "current clauses" list.	See find_usable_indexes() for motivation.
 *
 * outer_relids determines what Vars will be allowed on the other side
 * of a possible index qual; see match_clause_to_indexcol().
 *
 * If the index has amoptionalkey = false, we give up and return NIL when
 * there are no restriction clauses matching the first index key.  Otherwise,
 * we return NIL if there are no restriction clauses matching any index key.
 * A non-NIL result will have one (possibly empty) sublist for each index key.
 *
 * Example: given an index on (A,B,C), we would return ((C1 C2) () (C3 C4))
 * if we find that clauses C1 and C2 use column A, clauses C3 and C4 use
 * column C, and no clauses use column B.
 *
 * Note: in some circumstances we may find the same RestrictInfos coming
 * from multiple places.  Defend against redundant outputs by using
 * list_append_unique_ptr (pointer equality should be good enough).
 */
List *
group_clauses_by_indexkey(IndexOptInfo *index,
						  List *clauses, List *outer_clauses,
						  Relids outer_relids,
						  bool *found_clause)
{
	List	   *clausegroup_list = NIL;
	bool		found_outer_clause = false;
	int			indexcol = 0;
	Oid		   *classes = index->classlist;

	*found_clause = false;		/* default result */

	if (clauses == NIL && outer_clauses == NIL)
		return NIL;				/* cannot succeed */

	do
	{
		Oid			curClass = classes[0];
		List	   *clausegroup = NIL;
		ListCell   *l;

		/* check the current clauses */
		foreach(l, clauses)
		{
			RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);

			Assert(IsA(rinfo, RestrictInfo));
			if (match_clause_to_indexcol(index,
										 indexcol,
										 curClass,
										 rinfo,
										 outer_relids))
			{
				clausegroup = list_append_unique_ptr(clausegroup, rinfo);
				*found_clause = true;
			}
		}

		/* check the outer clauses */
		foreach(l, outer_clauses)
		{
			RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);

			Assert(IsA(rinfo, RestrictInfo));
			if (match_clause_to_indexcol(index,
										 indexcol,
										 curClass,
										 rinfo,
										 outer_relids))
			{
				clausegroup = list_append_unique_ptr(clausegroup, rinfo);
				found_outer_clause = true;
			}
		}

		/*
		 * If no clauses match this key, check for amoptionalkey restriction.
		 */
		if (clausegroup == NIL && !index->amoptionalkey && indexcol == 0)
			return NIL;

		clausegroup_list = lappend(clausegroup_list, clausegroup);

		indexcol++;
		classes++;