indxpath.c

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

		default:
			return;
	}

	/*
	 * If there are no indexable joinclauses for this rel, exit quickly.
	 */
	if (bms_is_empty(rel->index_outer_relids))
		return;

	/*
	 * Otherwise, we have to do path selection in the main planning context,
	 * so that any created path can be safely attached to the rel's cache of
	 * best inner paths.  (This is not currently an issue for normal planning,
	 * but it is an issue for GEQO planning.)
	 */
	oldcontext = MemoryContextSwitchTo(root->planner_cxt);

	/*
	 * Intersect the given outer relids with index_outer_relids to find the
	 * set of outer relids actually relevant for this rel. If there are none,
	 * again we can fail immediately.
	 */
	outer_relids = bms_intersect(rel->index_outer_relids, outer_rel->relids);
	if (bms_is_empty(outer_relids))
	{
		bms_free(outer_relids);
		MemoryContextSwitchTo(oldcontext);
		return;
	}

	/*
	 * Look to see if we already computed the result for this set of relevant
	 * outerrels.  (We include the isouterjoin status in the cache lookup key
	 * for safety.	In practice I suspect this is not necessary because it
	 * should always be the same for a given combination of rels.)
	 *
	 * NOTE: because we cache on outer_relids rather than outer_rel->relids,
	 * we will report the same paths and hence path cost for joins with
	 * different sets of irrelevant rels on the outside.  Now that cost_index
	 * is sensitive to outer_rel->rows, this is not really right.  However the
	 * error is probably not large.  Is it worth establishing a separate cache
	 * entry for each distinct outer_rel->relids set to get this right?
	 */
	foreach(l, rel->index_inner_paths)
	{
		info = (InnerIndexscanInfo *) lfirst(l);
		if (bms_equal(info->other_relids, outer_relids) &&
			info->isouterjoin == isouterjoin)
		{
			bms_free(outer_relids);
			MemoryContextSwitchTo(oldcontext);
			*cheapest_startup = info->cheapest_startup_innerpath;
			*cheapest_total = info->cheapest_total_innerpath;
			return;
		}
	}

	/*
	 * Find all the relevant restriction and join clauses.
	 *
	 * Note: because we include restriction clauses, we will find indexscans
	 * that could be plain indexscans, ie, they don't require the join context
	 * at all.	This may seem redundant, but we need to include those scans in
	 * the input given to choose_bitmap_and() to be sure we find optimal AND
	 * combinations of join and non-join scans.  Also, even if the "best inner
	 * indexscan" is just a plain indexscan, it will have a different cost
	 * estimate because of cache effects.
	 */
	clause_list = find_clauses_for_join(root, rel, outer_relids, isouterjoin);

	/*
	 * Find all the index paths that are usable for this join, except for
	 * stuff involving OR and ScalarArrayOpExpr clauses.
	 */
	indexpaths = find_usable_indexes(root, rel,
									 clause_list, NIL,
									 false, outer_rel,
									 SAOP_FORBID);

	/*
	 * Generate BitmapOrPaths for any suitable OR-clauses present in the
	 * clause list.
	 */
	bitindexpaths = generate_bitmap_or_paths(root, rel,
											 clause_list, NIL,
											 outer_rel);

	/*
	 * Likewise, generate paths using ScalarArrayOpExpr clauses; these can't
	 * be simple indexscans but they can be used in bitmap scans.
	 */
	bitindexpaths = list_concat(bitindexpaths,
								find_saop_paths(root, rel,
												clause_list, NIL,
												false, outer_rel));

	/*
	 * Include the regular index paths in bitindexpaths.
	 */
	bitindexpaths = list_concat(bitindexpaths, list_copy(indexpaths));

	/*
	 * If we found anything usable, generate a BitmapHeapPath for the most
	 * promising combination of bitmap index paths.
	 */
	if (bitindexpaths != NIL)
	{
		Path	   *bitmapqual;
		BitmapHeapPath *bpath;

		bitmapqual = choose_bitmap_and(root, rel, bitindexpaths, outer_rel);
		bpath = create_bitmap_heap_path(root, rel, bitmapqual, outer_rel);
		indexpaths = lappend(indexpaths, bpath);
	}

	/*
	 * Now choose the cheapest members of indexpaths.
	 */
	if (indexpaths != NIL)
	{
		*cheapest_startup = *cheapest_total = (Path *) linitial(indexpaths);

		for_each_cell(l, lnext(list_head(indexpaths)))
		{
			Path	   *path = (Path *) lfirst(l);

			if (compare_path_costs(path, *cheapest_startup, STARTUP_COST) < 0)
				*cheapest_startup = path;
			if (compare_path_costs(path, *cheapest_total, TOTAL_COST) < 0)
				*cheapest_total = path;
		}
	}

	/* Cache the results --- whether positive or negative */
	info = makeNode(InnerIndexscanInfo);
	info->other_relids = outer_relids;
	info->isouterjoin = isouterjoin;
	info->cheapest_startup_innerpath = *cheapest_startup;
	info->cheapest_total_innerpath = *cheapest_total;
	rel->index_inner_paths = lcons(info, rel->index_inner_paths);

	MemoryContextSwitchTo(oldcontext);
}

/*
 * find_clauses_for_join
 *	  Generate a list of clauses that are potentially useful for
 *	  scanning rel as the inner side of a nestloop join.
 *
 * We consider both join and restriction clauses.  Any joinclause that uses
 * only otherrels in the specified outer_relids is fair game.  But there must
 * be at least one such joinclause in the final list, otherwise we return NIL
 * indicating that there isn't any potential win here.
 */
static List *
find_clauses_for_join(PlannerInfo *root, RelOptInfo *rel,
					  Relids outer_relids, bool isouterjoin)
{
	List	   *clause_list = NIL;
	Relids		join_relids;
	ListCell   *l;

	/*
	 * Look for joinclauses that are usable with given outer_relids.  Note
	 * we'll take anything that's applicable to the join whether it has
	 * anything to do with an index or not; since we're only building a list,
	 * it's not worth filtering more finely here.
	 */
	join_relids = bms_union(rel->relids, outer_relids);

	foreach(l, rel->joininfo)
	{
		RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);

		/* Can't use pushed-down join clauses in outer join */
		if (isouterjoin && rinfo->is_pushed_down)
			continue;
		if (!bms_is_subset(rinfo->required_relids, join_relids))
			continue;

		clause_list = lappend(clause_list, rinfo);
	}

	bms_free(join_relids);

	/*
	 * Also check to see if any EquivalenceClasses can produce a relevant
	 * joinclause.	Since all such clauses are effectively pushed-down, this
	 * doesn't apply to outer joins.
	 */
	if (!isouterjoin && rel->has_eclass_joins)
		clause_list = list_concat(clause_list,
								  find_eclass_clauses_for_index_join(root,
																	 rel,
															  outer_relids));

	/* If no join clause was matched then forget it, per comments above */
	if (clause_list == NIL)
		return NIL;

	/* We can also use any plain restriction clauses for the rel */
	clause_list = list_concat(list_copy(rel->baserestrictinfo), clause_list);

	return clause_list;
}


/****************************************************************************
 *				----  PATH CREATION UTILITIES  ----
 ****************************************************************************/

/*
 * flatten_clausegroups_list
 *	  Given a list of lists of RestrictInfos, flatten it to a list
 *	  of RestrictInfos.
 *
 * This is used to flatten out the result of group_clauses_by_indexkey()
 * to produce an indexclauses list.  The original list structure mustn't
 * be altered, but it's OK to share copies of the underlying RestrictInfos.
 */
List *
flatten_clausegroups_list(List *clausegroups)
{
	List	   *allclauses = NIL;
	ListCell   *l;

	foreach(l, clausegroups)
		allclauses = list_concat(allclauses, list_copy((List *) lfirst(l)));
	return allclauses;
}


/****************************************************************************
 *				----  ROUTINES TO CHECK OPERANDS  ----
 ****************************************************************************/

/*
 * match_index_to_operand()
 *	  Generalized test for a match between an index's key
 *	  and the operand on one side of a restriction or join clause.
 *
 * operand: the nodetree to be compared to the index
 * indexcol: the column number of the index (counting from 0)
 * index: the index of interest
 */
bool
match_index_to_operand(Node *operand,
					   int indexcol,
					   IndexOptInfo *index)
{
	int			indkey;

	/*
	 * Ignore any RelabelType node above the operand.	This is needed to be
	 * able to apply indexscanning in binary-compatible-operator cases. Note:
	 * we can assume there is at most one RelabelType node;
	 * eval_const_expressions() will have simplified if more than one.
	 */
	if (operand && IsA(operand, RelabelType))
		operand = (Node *) ((RelabelType *) operand)->arg;

	indkey = index->indexkeys[indexcol];
	if (indkey != 0)
	{
		/*
		 * Simple index column; operand must be a matching Var.
		 */
		if (operand && IsA(operand, Var) &&
			index->rel->relid == ((Var *) operand)->varno &&
			indkey == ((Var *) operand)->varattno)
			return true;
	}
	else
	{
		/*
		 * Index expression; find the correct expression.  (This search could
		 * be avoided, at the cost of complicating all the callers of this
		 * routine; doesn't seem worth it.)
		 */
		ListCell   *indexpr_item;
		int			i;
		Node	   *indexkey;

		indexpr_item = list_head(index->indexprs);
		for (i = 0; i < indexcol; i++)
		{
			if (index->indexkeys[i] == 0)
			{
				if (indexpr_item == NULL)
					elog(ERROR, "wrong number of index expressions");
				indexpr_item = lnext(indexpr_item);
			}
		}
		if (indexpr_item == NULL)
			elog(ERROR, "wrong number of index expressions");
		indexkey = (Node *) lfirst(indexpr_item);

		/*
		 * Does it match the operand?  Again, strip any relabeling.
		 */
		if (indexkey && IsA(indexkey, RelabelType))
			indexkey = (Node *) ((RelabelType *) indexkey)->arg;

		if (equal(indexkey, operand))
			return true;
	}

	return false;
}

/****************************************************************************
 *			----  ROUTINES FOR "SPECIAL" INDEXABLE OPERATORS  ----
 ****************************************************************************/

/*----------
 * These routines handle special optimization of operators that can be
 * used with index scans even though they are not known to the executor's
 * indexscan machinery.  The key idea is that these operators allow us
 * to derive approximate indexscan qual clauses, such that any tuples
 * that pass the operator clause itself must also satisfy the simpler
 * indexscan condition(s).	Then we can use the indexscan machinery
 * to avoid scanning as much of the table as we'd otherwise have to,
 * while applying the original operator as a qpqual condition to ensure
 * we deliver only the tuples we want.	(In essence, we're using a regular
 * index as if it were a lossy index.)
 *
 * An example of what we're doing is
 *			textfield LIKE 'abc%'
 * from which we can generate the indexscanable conditions
 *			textfield >= 'abc' AND textfield < 'abd'
 * which allow efficient scanning of an index on textfield.
 * (In reality, character set and collation issues make the transformation
 * from LIKE to indexscan limits rather harder than one might think ...
 * but that's the basic idea.)
 *
 * Another thing that we do with this machinery is to provide special
 * smarts for "boolean" indexes (that is, indexes on boolean columns
 * that support boolean equality).	We can transform a plain reference
 * to the indexkey into "indexkey = true", or "NOT indexkey" into
 * "indexkey = false", so as to make the expression indexable using the
 * regular index operators.  (As of Postgres 8.1, we must do this here
 * because constant simplification does the reverse transformation;
 * without this code there'd be no way to use such an index at all.)
 *
 * Three routines are provided here:
 *
 * match_special_index_operator() is just an auxiliary function for
 * match_clause_to_indexcol(); after the latter fails to recognize a
 * restriction opclause's operator as a member of an index's opfamily,
 * it asks match_special_index_operator() whether the clause should be
 * considered an indexqual anyway.
 *
 * match_boolean_index_clause() similarly detects clauses that can be
 * converted into boolean equality operators.
 *
 * expand_indexqual_conditions() converts a list of lists of RestrictInfo
 * nodes (with implicit AND semantics across list elements) into
 * a list of clauses that the executor can actually handle.  For operators
 * that are members of the index's opfamily this transformation is a no-op,
 * but clauses recognized by match_special_index_operator() or
 * match_boolean_index_clause() must be converted into one or more "regular"
 * indexqual conditions.
 *----------
 */

/*
 * match_boolean_index_clause
 *	  Recognize restriction clauses that can be matched to a boolean index.
 *
 * This should be called only when IsBooleanOpfamily() recognizes the
 * index's operator family.  We check to see if the clause matches the
 * index's key.
 */
static bool
match_boolean_index_clause(Node *clause,
						   int indexcol,
						   IndexOptInfo *index)
{
	/* Direct match? */
	if (match_index_to_operand(clause, indexcol, index))
		return true;
	/* NOT clause? */
	if (not_clause(clause))
	{
		if (match_index_to_operand((Node *) get_notclausearg((Expr *) clause),
								   indexcol, index))
			return true;
	}

	/*
	 * Since we only consider clauses at top level of WHERE, we can convert
	 * indexkey IS TRUE and indexkey IS FALSE to index searches as well. The
	 * different meaning for NULL isn't important.
	 */
	else if (clause && IsA(clause, BooleanTest))
	{
		BooleanTest *btest = (BooleanTest *) clause;

		if (btest->booltesttype == IS_TRUE ||
			btest->booltesttype == IS_FALSE)
			if (match_index_to_operand((Node *) btest->arg,
									   indexcol, index))
				return true;
	}
	return false;
}

/*
 * match_special_index_operator
 *	  Recognize restriction clauses that can be used to generate
 *	  additional indexscanable qualifications.
 *
 * The g