/*-------------------------------------------------------------------------
*
* indxpath.c
- * Routines to determine which indices are usable for scanning a
- * given relation, and create IndexPaths accordingly.
+ * Routines to determine which indexes are usable for scanning a
+ * given relation, and create Paths accordingly.
*
* Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
* Portions Copyright (c) 1994, Regents of the University of California
*
*
* IDENTIFICATION
- * $PostgreSQL: pgsql/src/backend/optimizer/path/indxpath.c,v 1.173 2005/04/11 23:06:55 tgl Exp $
+ * $PostgreSQL: pgsql/src/backend/optimizer/path/indxpath.c,v 1.190 2005/09/24 22:54:36 tgl Exp $
*
*-------------------------------------------------------------------------
*/
#include <math.h>
-#include "access/nbtree.h"
-#include "catalog/pg_amop.h"
-#include "catalog/pg_namespace.h"
+#include "access/skey.h"
#include "catalog/pg_opclass.h"
#include "catalog/pg_operator.h"
-#include "catalog/pg_proc.h"
#include "catalog/pg_type.h"
-#include "executor/executor.h"
#include "nodes/makefuncs.h"
#include "optimizer/clauses.h"
#include "optimizer/cost.h"
#include "optimizer/pathnode.h"
#include "optimizer/paths.h"
+#include "optimizer/predtest.h"
#include "optimizer/restrictinfo.h"
-#include "optimizer/var.h"
-#include "parser/parse_expr.h"
-#include "rewrite/rewriteManip.h"
#include "utils/builtins.h"
-#include "utils/catcache.h"
#include "utils/lsyscache.h"
+#include "utils/memutils.h"
#include "utils/pg_locale.h"
#include "utils/selfuncs.h"
-#include "utils/syscache.h"
/*
((opclass) == BOOL_BTREE_OPS_OID || (opclass) == BOOL_HASH_OPS_OID)
-static List *group_clauses_by_indexkey_for_join(Query *root,
- IndexOptInfo *index,
- Relids outer_relids,
- JoinType jointype, bool isouterjoin);
+static List *find_usable_indexes(PlannerInfo *root, RelOptInfo *rel,
+ List *clauses, List *outer_clauses,
+ bool istoplevel, bool isjoininner,
+ Relids outer_relids);
+static Path *choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel, List *paths);
+static int bitmap_path_comparator(const void *a, const void *b);
+static Cost bitmap_and_cost_est(PlannerInfo *root, RelOptInfo *rel, List *paths);
static bool match_clause_to_indexcol(IndexOptInfo *index,
int indexcol, Oid opclass,
- RestrictInfo *rinfo);
-static bool match_join_clause_to_indexcol(IndexOptInfo *index,
- int indexcol, Oid opclass,
- RestrictInfo *rinfo);
+ RestrictInfo *rinfo,
+ Relids outer_relids);
static Oid indexable_operator(Expr *clause, Oid opclass,
bool indexkey_on_left);
-static bool pred_test_recurse(Node *clause, Node *predicate);
-static bool pred_test_simple_clause(Expr *predicate, Node *clause);
-static Relids indexable_outerrelids(IndexOptInfo *index);
-static Path *make_innerjoin_index_path(Query *root, IndexOptInfo *index,
- List *clausegroups);
+static Relids indexable_outerrelids(RelOptInfo *rel);
+static bool matches_any_index(RestrictInfo *rinfo, RelOptInfo *rel,
+ Relids outer_relids);
+static List *find_clauses_for_join(PlannerInfo *root, RelOptInfo *rel,
+ Relids outer_relids, bool isouterjoin);
+static ScanDirection match_variant_ordering(PlannerInfo *root,
+ IndexOptInfo *index,
+ List *restrictclauses);
+static List *identify_ignorable_ordering_cols(PlannerInfo *root,
+ IndexOptInfo *index,
+ List *restrictclauses);
+static bool match_index_to_query_keys(PlannerInfo *root,
+ IndexOptInfo *index,
+ ScanDirection indexscandir,
+ List *ignorables);
static bool match_boolean_index_clause(Node *clause, int indexcol,
IndexOptInfo *index);
static bool match_special_index_operator(Expr *clause, Oid opclass,
*
* To be considered for an index scan, an index must match one or more
* restriction clauses or join clauses from the query's qual condition,
- * or match the query's ORDER BY condition.
+ * or match the query's ORDER BY condition, or have a predicate that
+ * matches the query's qual condition.
*
* There are two basic kinds of index scans. A "plain" index scan uses
* only restriction clauses (possibly none at all) in its indexqual,
* Note: check_partial_indexes() must have been run previously.
*/
void
-create_index_paths(Query *root, RelOptInfo *rel)
+create_index_paths(PlannerInfo *root, RelOptInfo *rel)
{
- Relids all_join_outerrelids = NULL;
+ List *indexpaths;
+ List *bitindexpaths;
+ ListCell *l;
+
+ /* Skip the whole mess if no indexes */
+ if (rel->indexlist == NIL)
+ {
+ rel->index_outer_relids = NULL;
+ return;
+ }
+
+ /*
+ * Examine join clauses to see which ones are potentially usable with
+ * indexes of this rel, and generate the set of all other relids that
+ * participate in such join clauses. We'll use this set later to
+ * recognize outer rels that are equivalent for joining purposes.
+ */
+ rel->index_outer_relids = indexable_outerrelids(rel);
+
+ /*
+ * Find all the index paths that are directly usable for this relation
+ * (ie, are valid without considering OR or JOIN clauses).
+ */
+ indexpaths = find_usable_indexes(root, rel,
+ rel->baserestrictinfo, NIL,
+ true, false, NULL);
+
+ /*
+ * We can submit them all to add_path. (This generates access paths for
+ * plain IndexScan plans.) However, for the next step we will only want
+ * the ones that have some selectivity; we must discard anything that was
+ * generated solely for ordering purposes.
+ */
+ bitindexpaths = NIL;
+ foreach(l, indexpaths)
+ {
+ IndexPath *ipath = (IndexPath *) lfirst(l);
+
+ add_path(rel, (Path *) ipath);
+
+ if (ipath->indexselectivity < 1.0 &&
+ !ScanDirectionIsBackward(ipath->indexscandir))
+ bitindexpaths = lappend(bitindexpaths, ipath);
+ }
+
+ /*
+ * Generate BitmapOrPaths for any suitable OR-clauses present in the
+ * restriction list. Add these to bitindexpaths.
+ */
+ indexpaths = generate_bitmap_or_paths(root, rel,
+ rel->baserestrictinfo, NIL,
+ false, NULL);
+ bitindexpaths = list_concat(bitindexpaths, 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);
+ bpath = create_bitmap_heap_path(root, rel, bitmapqual, false);
+ add_path(rel, (Path *) bpath);
+ }
+}
+
+
+/*----------
+ * find_usable_indexes
+ * Given a list of restriction clauses, find all the potentially usable
+ * indexes for the given relation, and return a list of IndexPaths.
+ *
+ * The caller actually supplies two lists of restriction clauses: some
+ * "current" ones and some "outer" ones. Both lists can be used freely
+ * to match keys of the index, but an index must use at least one of the
+ * "current" clauses to be considered usable. The motivation for this is
+ * examples like
+ * WHERE (x = 42) AND (... OR (y = 52 AND z = 77) OR ....)
+ * While we are considering the y/z subclause of the OR, we can use "x = 42"
+ * as one of the available index conditions; but we shouldn't match the
+ * subclause to any index on x alone, because such a Path would already have
+ * been generated at the upper level. So we could use an index on x,y,z
+ * or an index on x,y for the OR subclause, but not an index on just x.
+ * When dealing with a partial index, a match of the index predicate to
+ * one of the "current" clauses also makes the index usable.
+ *
+ * If istoplevel is true (indicating we are considering the top level of a
+ * rel's restriction clauses), we will include indexes in the result that
+ * have an interesting sort order, even if they have no matching restriction
+ * clauses.
+ *
+ * 'rel' is the relation for which we want to generate index paths
+ * 'clauses' is the current list of clauses (RestrictInfo nodes)
+ * 'outer_clauses' is the list of additional upper-level clauses
+ * 'istoplevel' is true if clauses are the rel's top-level restriction list
+ * (outer_clauses must be NIL when this is true)
+ * 'isjoininner' is true if forming an inner indexscan (so some of the
+ * given clauses are join clauses)
+ * 'outer_relids' identifies the outer side of the join (pass NULL
+ * if not isjoininner)
+ *
+ * Note: check_partial_indexes() must have been run previously.
+ *----------
+ */
+static List *
+find_usable_indexes(PlannerInfo *root, RelOptInfo *rel,
+ List *clauses, List *outer_clauses,
+ bool istoplevel, bool isjoininner,
+ Relids outer_relids)
+{
+ List *result = NIL;
+ List *all_clauses = NIL; /* not computed till needed */
ListCell *ilist;
foreach(ilist, rel->indexlist)
{
IndexOptInfo *index = (IndexOptInfo *) lfirst(ilist);
+ IndexPath *ipath;
List *restrictclauses;
List *index_pathkeys;
List *useful_pathkeys;
+ bool useful_predicate;
+ bool found_clause;
bool index_is_ordered;
- Relids join_outerrelids;
-
- /* Ignore partial indexes that do not match the query */
- if (index->indpred != NIL && !index->predOK)
- continue;
/*
- * 1. Match the index against non-OR restriction clauses. (OR
- * clauses will be considered later by orindxpath.c.)
+ * Ignore partial indexes that do not match the query. If a partial
+ * index is marked predOK then we know it's OK; otherwise, if we
+ * are at top level we know it's not OK (since predOK is exactly
+ * whether its predicate could be proven from the toplevel clauses).
+ * Otherwise, we have to test whether the added clauses are
+ * sufficient to imply the predicate. If so, we could use
+ * the index in the current context.
+ *
+ * We set useful_predicate to true iff the predicate was proven
+ * using the current set of clauses. This is needed to prevent
+ * matching a predOK index to an arm of an OR, which would be
+ * a legal but pointlessly inefficient plan. (A better plan will
+ * be generated by just scanning the predOK index alone, no OR.)
*/
- restrictclauses = group_clauses_by_indexkey(index);
+ useful_predicate = false;
+ if (index->indpred != NIL)
+ {
+ if (index->predOK)
+ {
+ if (istoplevel)
+ {
+ /* we know predicate was proven from these clauses */
+ useful_predicate = true;
+ }
+ }
+ else
+ {
+ if (istoplevel)
+ continue; /* no point in trying to prove it */
+
+ /* Form all_clauses if not done already */
+ if (all_clauses == NIL)
+ all_clauses = list_concat(list_copy(clauses),
+ outer_clauses);
+
+ if (!predicate_implied_by(index->indpred, all_clauses))
+ continue; /* can't use it at all */
+
+ if (!predicate_implied_by(index->indpred, outer_clauses))
+ useful_predicate = true;
+ }
+ }
/*
- * 2. Compute pathkeys describing index's ordering, if any, then
- * see how many of them are actually useful for this query.
+ * 1. Match the index against the available restriction clauses.
+ * found_clause is set true only if at least one of the current
+ * clauses was used.
*/
- index_pathkeys = build_index_pathkeys(root, index,
- ForwardScanDirection);
- index_is_ordered = (index_pathkeys != NIL);
- useful_pathkeys = truncate_useless_pathkeys(root, rel,
- index_pathkeys);
+ restrictclauses = group_clauses_by_indexkey(index,
+ clauses,
+ outer_clauses,
+ outer_relids,
+ &found_clause);
/*
- * 3. Generate an indexscan path if there are relevant restriction
- * clauses OR the index ordering is potentially useful for later
- * merging or final output ordering.
- *
- * If there is a predicate, consider it anyway since the index
- * predicate has already been found to match the query. The
- * selectivity of the predicate might alone make the index useful.
+ * Not all index AMs support scans with no restriction clauses.
+ * We can't generate a scan over an index with amoptionalkey = false
+ * unless there's at least one restriction clause.
*/
- if (restrictclauses != NIL ||
- useful_pathkeys != NIL ||
- index->indpred != NIL)
- add_path(rel, (Path *)
- create_index_path(root, index,
- restrictclauses,
- useful_pathkeys,
- index_is_ordered ?
- ForwardScanDirection :
- NoMovementScanDirection));
+ if (restrictclauses == NIL && !index->amoptionalkey)
+ continue;
/*
- * 4. If the index is ordered, a backwards scan might be
- * interesting. Currently this is only possible for a DESC query
- * result ordering.
+ * 2. Compute pathkeys describing index's ordering, if any, then
+ * see how many of them are actually useful for this query. This
+ * is not relevant unless we are at top level.
*/
- if (index_is_ordered)
+ index_is_ordered = OidIsValid(index->ordering[0]);
+ if (istoplevel && index_is_ordered && !isjoininner)
{
index_pathkeys = build_index_pathkeys(root, index,
- BackwardScanDirection);
+ ForwardScanDirection);
useful_pathkeys = truncate_useless_pathkeys(root, rel,
index_pathkeys);
- if (useful_pathkeys != NIL)
- add_path(rel, (Path *)
- create_index_path(root, index,
- restrictclauses,
- useful_pathkeys,
- BackwardScanDirection));
}
+ else
+ useful_pathkeys = NIL;
/*
- * 5. Examine join clauses to see which ones are potentially
- * usable with this index, and generate the set of all other
- * relids that participate in such join clauses. We'll use this
- * set later to recognize outer rels that are equivalent for
- * joining purposes. We compute both per-index and
- * overall-for-relation sets.
+ * 3. Generate an indexscan path if there are relevant restriction
+ * clauses in the current clauses, OR the index ordering is
+ * potentially useful for later merging or final output ordering,
+ * OR the index has a predicate that was proven by the current
+ * clauses.
*/
- join_outerrelids = indexable_outerrelids(index);
- index->outer_relids = join_outerrelids;
- all_join_outerrelids = bms_add_members(all_join_outerrelids,
- join_outerrelids);
- }
+ if (found_clause || useful_pathkeys != NIL || useful_predicate)
+ {
+ ipath = create_index_path(root, index,
+ restrictclauses,
+ useful_pathkeys,
+ index_is_ordered ?
+ ForwardScanDirection :
+ NoMovementScanDirection,
+ isjoininner);
+ result = lappend(result, ipath);
+ }
- rel->index_outer_relids = all_join_outerrelids;
-}
+ /*
+ * 4. If the index is ordered, and there is a requested query
+ * ordering that we failed to match, consider variant ways of
+ * achieving the ordering. Again, this is only interesting
+ * at top level.
+ */
+ if (istoplevel && index_is_ordered && !isjoininner &&
+ root->query_pathkeys != NIL &&
+ pathkeys_useful_for_ordering(root, useful_pathkeys) == 0)
+ {
+ ScanDirection scandir;
+ scandir = match_variant_ordering(root, index, restrictclauses);
+ if (!ScanDirectionIsNoMovement(scandir))
+ {
+ ipath = create_index_path(root, index,
+ restrictclauses,
+ root->query_pathkeys,
+ scandir,
+ false);
+ result = lappend(result, ipath);
+ }
+ }
+ }
-/****************************************************************************
- * ---- ROUTINES TO CHECK RESTRICTIONS ----
- ****************************************************************************/
+ return result;
+}
/*
- * 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().)
- *
- * Note that in a multi-key index, we stop if we find a key that cannot be
- * used with any clause. For example, given an index on (A,B,C), we might
- * return ((C1 C2) (C3 C4)) if we find that clauses C1 and C2 use column A,
- * clauses C3 and C4 use column B, and no clauses use column C. But if
- * no clauses match B we will return ((C1 C2)), whether or not there are
- * clauses matching column C, because the executor couldn't use them anyway.
- * Therefore, there are no empty sublists in the result.
+ * generate_bitmap_or_paths
+ * Look through the list of clauses to find OR clauses, and generate
+ * a BitmapOrPath for each one we can handle that way. Return a list
+ * of the generated BitmapOrPaths.
+ *
+ * outer_clauses is a list of additional clauses that can be assumed true
+ * for the purpose of generating indexquals, but are not to be searched for
+ * ORs. (See find_usable_indexes() for motivation.)
*/
List *
-group_clauses_by_indexkey(IndexOptInfo *index)
+generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel,
+ List *clauses, List *outer_clauses,
+ bool isjoininner,
+ Relids outer_relids)
{
- List *clausegroup_list = NIL;
- List *restrictinfo_list = index->rel->baserestrictinfo;
- int indexcol = 0;
- Oid *classes = index->classlist;
+ List *result = NIL;
+ List *all_clauses;
+ ListCell *l;
- if (restrictinfo_list == NIL)
- return NIL;
+ /*
+ * We can use both the current and outer clauses as context for
+ * find_usable_indexes
+ */
+ all_clauses = list_concat(list_copy(clauses), outer_clauses);
- do
+ foreach(l, clauses)
{
- Oid curClass = classes[0];
- List *clausegroup = NIL;
- ListCell *l;
+ RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
+ List *pathlist;
+ Path *bitmapqual;
+ ListCell *j;
+
+ Assert(IsA(rinfo, RestrictInfo));
+ /* Ignore RestrictInfos that aren't ORs */
+ if (!restriction_is_or_clause(rinfo))
+ continue;
- foreach(l, restrictinfo_list)
+ /*
+ * We must be able to match at least one index to each of the arms
+ * of the OR, else we can't use it.
+ */
+ pathlist = NIL;
+ foreach(j, ((BoolExpr *) rinfo->orclause)->args)
{
- RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
+ Node *orarg = (Node *) lfirst(j);
+ List *indlist;
- if (match_clause_to_indexcol(index,
- indexcol,
- curClass,
- rinfo))
- clausegroup = lappend(clausegroup, rinfo);
+ /* 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 no clauses match this key, we're done; we don't want to look
- * at keys to its right.
+ * If we have a match for every arm, then turn them
+ * into a BitmapOrPath, and add to result list.
*/
- if (clausegroup == NIL)
- break;
-
- clausegroup_list = lappend(clausegroup_list, clausegroup);
-
- indexcol++;
- classes++;
-
- } while (!DoneMatchingIndexKeys(classes));
+ if (pathlist != NIL)
+ {
+ bitmapqual = (Path *) create_bitmap_or_path(root, rel, pathlist);
+ result = lappend(result, bitmapqual);
+ }
+ }
- return clausegroup_list;
+ return result;
}
+
/*
- * group_clauses_by_indexkey_for_join
- * Generate a list of sublists of clauses that can be used with an index
- * to scan the inner side of a nestloop join.
+ * 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.
*
- * This is much like group_clauses_by_indexkey(), but 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 this index isn't interesting as an inner indexscan. (A scan using
- * only restriction clauses shouldn't be created here, because a regular Path
- * will already have been generated for it.)
+ * The result is either a single one of the inputs, or a BitmapAndPath
+ * combining multiple inputs.
*/
-static List *
-group_clauses_by_indexkey_for_join(Query *root, IndexOptInfo *index,
- Relids outer_relids,
- JoinType jointype, bool isouterjoin)
+static Path *
+choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel, List *paths)
{
- List *clausegroup_list = NIL;
- bool jfound = false;
- int indexcol = 0;
- Oid *classes = index->classlist;
+ int npaths = list_length(paths);
+ Path **patharray;
+ Cost costsofar;
+ List *qualsofar;
+ ListCell *lastcell;
+ int i;
+ ListCell *l;
- do
- {
- Oid curClass = classes[0];
- List *clausegroup = NIL;
- int numsources;
- ListCell *l;
+ Assert(npaths > 0); /* else caller error */
+ if (npaths == 1)
+ return (Path *) linitial(paths); /* easy case */
- /*
- * We can always use plain restriction clauses for the rel. We
- * scan these first because we want them first in the clausegroup
- * list for the convenience of remove_redundant_join_clauses,
- * which can never remove non-join clauses and hence won't be able
- * to get rid of a non-join clause if it appears after a join
- * clause it is redundant with.
- */
- foreach(l, index->rel->baserestrictinfo)
- {
- RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
+ /*
+ * 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. For
+ * this we look only at plain IndexPath inputs, not at sub-OR clauses.
+ * And we consider an index redundant if all 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.)
+ *
+ * XXX is there any risk of throwing away a useful partial index here
+ * because we don't explicitly look at indpred? At least in simple
+ * cases, the partial index will sort before competing non-partial
+ * indexes and so it makes the right choice, but perhaps we need to
+ * work harder.
+ *
+ * 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.
+ */
- /* Can't use pushed-down clauses in outer join */
- if (isouterjoin && rinfo->is_pushed_down)
- continue;
+ /* 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);
- if (match_clause_to_indexcol(index,
- indexcol,
- curClass,
- rinfo))
- clausegroup = lappend(clausegroup, rinfo);
- }
+ paths = list_make1(patharray[0]);
+ costsofar = bitmap_and_cost_est(root, rel, paths);
+ if (IsA(patharray[0], IndexPath))
+ qualsofar = list_copy(((IndexPath *) patharray[0])->indexclauses);
+ else
+ qualsofar = NIL;
+ lastcell = list_head(paths); /* for quick deletions */
- /* found anything in base restrict list? */
- numsources = (clausegroup != NIL) ? 1 : 0;
+ for (i = 1; i < npaths; i++)
+ {
+ Path *newpath = patharray[i];
+ List *newqual = NIL;
+ Cost newcost;
- /* Look for joinclauses that are usable with given outer_relids */
- foreach(l, index->rel->joininfo)
+ if (IsA(newpath, IndexPath))
{
- JoinInfo *joininfo = (JoinInfo *) lfirst(l);
- bool jfoundhere = false;
- ListCell *j;
-
- if (!bms_is_subset(joininfo->unjoined_relids, outer_relids))
- continue;
-
- foreach(j, joininfo->jinfo_restrictinfo)
- {
- RestrictInfo *rinfo = (RestrictInfo *) lfirst(j);
-
- /* Can't use pushed-down clauses in outer join */
- if (isouterjoin && rinfo->is_pushed_down)
- continue;
-
- if (match_join_clause_to_indexcol(index,
- indexcol,
- curClass,
- rinfo))
- {
- clausegroup = lappend(clausegroup, rinfo);
- if (!jfoundhere)
- {
- jfoundhere = true;
- jfound = true;
- numsources++;
- }
- }
- }
+ newqual = ((IndexPath *) newpath)->indexclauses;
+ if (list_difference_ptr(newqual, qualsofar) == NIL)
+ continue; /* redundant */
}
- /*
- * If we found clauses in more than one list, we may now have
- * clauses that are known redundant. Get rid of 'em.
- */
- if (numsources > 1)
+ paths = lappend(paths, newpath);
+ newcost = bitmap_and_cost_est(root, rel, paths);
+ if (newcost < costsofar)
+ {
+ costsofar = newcost;
+ if (newqual)
+ qualsofar = list_concat(qualsofar, list_copy(newqual));
+ lastcell = lnext(lastcell);
+ }
+ else
{
- clausegroup = remove_redundant_join_clauses(root,
- clausegroup,
- jointype);
+ paths = list_delete_cell(paths, lnext(lastcell), lastcell);
}
+ Assert(lnext(lastcell) == NULL);
+ }
- /*
- * If no clauses match this key, we're done; we don't want to look
- * at keys to its right.
- */
- if (clausegroup == NIL)
- break;
+ if (list_length(paths) == 1)
+ return (Path *) linitial(paths); /* no need for AND */
+ return (Path *) create_bitmap_and_path(root, rel, paths);
+}
- clausegroup_list = lappend(clausegroup_list, clausegroup);
+/* 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;
+
+ cost_bitmap_tree_node(pa, &acost, &aselec);
+ cost_bitmap_tree_node(pb, &bcost, &bselec);
+
+ if (aselec < bselec)
+ return -1;
+ if (aselec > bselec)
+ return 1;
+ /* if identical selectivity, sort by cost */
+ if (acost < bcost)
+ return -1;
+ if (acost > bcost)
+ return 1;
+ return 0;
+}
- indexcol++;
- classes++;
+/*
+ * 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;
- } while (!DoneMatchingIndexKeys(classes));
+ /* Set up a dummy BitmapAndPath */
+ apath.path.type = T_BitmapAndPath;
+ apath.path.parent = rel;
+ apath.bitmapquals = paths;
+ cost_bitmap_and_node(&apath, root);
- /* if no join clause was matched then forget it, per comments above */
- if (!jfound)
- return NIL;
+ /* Now we can do cost_bitmap_heap_scan */
+ cost_bitmap_heap_scan(&bpath, root, rel, (Path *) &apath, false);
- return clausegroup_list;
+ return bpath.total_cost;
}
+/****************************************************************************
+ * ---- ROUTINES TO CHECK RESTRICTIONS ----
+ ****************************************************************************/
+
+
/*
- * group_clauses_by_indexkey_for_or
- * Generate a list of sublists of clauses that can be used with an index
- * to find rows matching an OR subclause.
+ * 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().
*
- * This is essentially just like group_clauses_by_indexkey() except that
- * we can use the given clause (or any AND subclauses of it) as well as
- * top-level restriction clauses of the relation. Furthermore, we demand
- * that at least one such use be made, otherwise we fail and return NIL.
- * (Any path we made without such a use would be redundant with non-OR
- * indexscans. Compare also group_clauses_by_indexkey_for_join.)
+ * 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.
*
- * XXX When we generate an indexqual list that uses both the OR subclause
- * and top-level restriction clauses, we end up with a slightly inefficient
- * plan because create_indexscan_plan is not very bright about figuring out
- * which restriction clauses are implied by the generated indexqual condition.
- * Currently we'll end up rechecking both the OR clause and the top-level
- * restriction clause as qpquals. FIXME someday.
+ * 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_for_or(IndexOptInfo *index, Expr *orsubclause)
+group_clauses_by_indexkey(IndexOptInfo *index,
+ List *clauses, List *outer_clauses,
+ Relids outer_relids,
+ bool *found_clause)
{
List *clausegroup_list = NIL;
- bool matched = false;
+ 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 *item;
+ ListCell *l;
- /* Try to match the OR subclause to the index key */
- if (IsA(orsubclause, RestrictInfo))
- {
- if (match_clause_to_indexcol(index, indexcol, curClass,
- (RestrictInfo *) orsubclause))
- {
- clausegroup = lappend(clausegroup, orsubclause);
- matched = true;
- }
- }
- else if (and_clause((Node *) orsubclause))
+ /* check the current clauses */
+ foreach(l, clauses)
{
- foreach(item, ((BoolExpr *) orsubclause)->args)
- {
- RestrictInfo *subsubclause = (RestrictInfo *) lfirst(item);
+ RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
- if (IsA(subsubclause, RestrictInfo) &&
- match_clause_to_indexcol(index, indexcol, curClass,
- subsubclause))
- {
- clausegroup = lappend(clausegroup, subsubclause);
- matched = true;
- }
+ 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;
}
}
- /*
- * If we found no clauses for this indexkey in the OR subclause
- * itself, try looking in the rel's top-level restriction list.
- *
- * XXX should we always search the top-level list? Slower but could
- * sometimes yield a better plan.
- */
- if (clausegroup == NIL)
+ /* check the outer clauses */
+ foreach(l, outer_clauses)
{
- foreach(item, index->rel->baserestrictinfo)
- {
- RestrictInfo *rinfo = (RestrictInfo *) lfirst(item);
+ RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
- if (match_clause_to_indexcol(index, indexcol, curClass,
- rinfo))
- clausegroup = lappend(clausegroup, rinfo);
+ 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 still no clauses match this key, we're done; we don't want
- * to look at keys to its right.
+ * If no clauses match this key, check for amoptionalkey restriction.
*/
- if (clausegroup == NIL)
- break;
+ if (clausegroup == NIL && !index->amoptionalkey && indexcol == 0)
+ return NIL;
clausegroup_list = lappend(clausegroup_list, clausegroup);
indexcol++;
classes++;
+
} while (!DoneMatchingIndexKeys(classes));
- /* if OR clause was not used then forget it, per comments above */
- if (!matched)
- return NIL;
+ if (!*found_clause && !found_outer_clause)
+ return NIL; /* no indexable clauses anywhere */
return clausegroup_list;
}
* operator for this column, or is a "special" operator as recognized
* by match_special_index_operator().
*
+ * Our definition of "const" is pretty liberal: we allow Vars belonging
+ * to the caller-specified outer_relids relations (which had better not
+ * include the relation whose index is being tested). outer_relids should
+ * be NULL when checking simple restriction clauses, and the outer side
+ * of the join when building a join inner scan. Other than that, the
+ * only thing we don't like is volatile functions.
+ *
+ * Note: in most cases we already know that the clause as a whole uses
+ * vars from the interesting set of relations. The reason for the
+ * outer_relids test is to reject clauses like (a.f1 OP (b.f2 OP a.f3));
+ * that's not processable by an indexscan nestloop join on A, whereas
+ * (a.f1 OP (b.f2 OP c.f3)) is.
+ *
* Presently, the executor can only deal with indexquals that have the
* indexkey on the left, so we can only use clauses that have the indexkey
* on the right if we can commute the clause to put the key on the left.
match_clause_to_indexcol(IndexOptInfo *index,
int indexcol,
Oid opclass,
- RestrictInfo *rinfo)
+ RestrictInfo *rinfo,
+ Relids outer_relids)
{
Expr *clause = rinfo->clause;
Node *leftop,
/*
* Check for clauses of the form: (indexkey operator constant) or
- * (constant operator indexkey). Anything that is a "pseudo constant"
- * expression will do.
+ * (constant operator indexkey). See above notes about const-ness.
*/
if (match_index_to_operand(leftop, indexcol, index) &&
- is_pseudo_constant_clause_relids(rightop, rinfo->right_relids))
+ bms_is_subset(rinfo->right_relids, outer_relids) &&
+ !contain_volatile_functions(rightop))
{
if (is_indexable_operator(clause, opclass, true))
return true;
}
if (match_index_to_operand(rightop, indexcol, index) &&
- is_pseudo_constant_clause_relids(leftop, rinfo->left_relids))
+ bms_is_subset(rinfo->left_relids, outer_relids) &&
+ !contain_volatile_functions(leftop))
{
if (is_indexable_operator(clause, opclass, false))
return true;
}
/*
- * match_join_clause_to_indexcol()
- * Determines whether a join clause matches a column of an index.
- *
- * To match, the clause:
- *
- * (1) must be in the form (indexkey op others) or (others op indexkey),
- * where others is an expression involving only vars of the other
- * relation(s); and
- * (2) must contain an operator which is in the same class as the index
- * operator for this column, or is a "special" operator as recognized
- * by match_special_index_operator().
- *
- * The boolean-index cases don't apply.
- *
- * As above, we must be able to commute the clause to put the indexkey
- * on the left.
- *
- * Note that we already know that the clause as a whole uses vars from
- * the interesting set of relations. But we need to defend against
- * expressions like (a.f1 OP (b.f2 OP a.f3)); that's not processable by
- * an indexscan nestloop join, whereas (a.f1 OP (b.f2 OP c.f3)) is.
+ * indexable_operator
+ * Does a binary opclause contain an operator matching the index opclass?
*
- * 'index' is the index of interest.
- * 'indexcol' is a column number of 'index' (counting from 0).
- * 'opclass' is the corresponding operator class.
- * 'rinfo' is the clause to be tested (as a RestrictInfo node).
- *
- * Returns true if the clause can be used with this index key.
- *
- * NOTE: returns false if clause is an OR or AND clause; it is the
- * responsibility of higher-level routines to cope with those.
- */
-static bool
-match_join_clause_to_indexcol(IndexOptInfo *index,
- int indexcol,
- Oid opclass,
- RestrictInfo *rinfo)
-{
- Expr *clause = rinfo->clause;
- Node *leftop,
- *rightop;
-
- /* Clause must be a binary opclause. */
- if (!is_opclause(clause))
- return false;
- leftop = get_leftop(clause);
- rightop = get_rightop(clause);
- if (!leftop || !rightop)
- return false;
-
- /*
- * Check for an indexqual that could be handled by a nestloop join. We
- * need the index key to be compared against an expression that uses
- * none of the indexed relation's vars and contains no volatile
- * functions.
- */
- if (match_index_to_operand(leftop, indexcol, index))
- {
- Relids othervarnos = rinfo->right_relids;
- bool isIndexable;
-
- isIndexable =
- !bms_overlap(index->rel->relids, othervarnos) &&
- !contain_volatile_functions(rightop) &&
- is_indexable_operator(clause, opclass, true);
- return isIndexable;
- }
-
- if (match_index_to_operand(rightop, indexcol, index))
- {
- Relids othervarnos = rinfo->left_relids;
- bool isIndexable;
-
- isIndexable =
- !bms_overlap(index->rel->relids, othervarnos) &&
- !contain_volatile_functions(leftop) &&
- is_indexable_operator(clause, opclass, false);
- return isIndexable;
- }
-
- return false;
-}
-
-/*
- * indexable_operator
- * Does a binary opclause contain an operator matching the index opclass?
- *
- * If the indexkey is on the right, what we actually want to know
- * is whether the operator has a commutator operator that matches
- * the index's opclass.
+ * If the indexkey is on the right, what we actually want to know
+ * is whether the operator has a commutator operator that matches
+ * the index's opclass.
*
* Returns the OID of the matching operator, or InvalidOid if no match.
* (Formerly, this routine might return a binary-compatible operator
* depending on whether the predicate is satisfied for this query.
*/
void
-check_partial_indexes(Query *root, RelOptInfo *rel)
+check_partial_indexes(PlannerInfo *root, RelOptInfo *rel)
{
List *restrictinfo_list = rel->baserestrictinfo;
ListCell *ilist;
- foreach(ilist, rel->indexlist)
- {
- IndexOptInfo *index = (IndexOptInfo *) lfirst(ilist);
-
- /*
- * If this is a partial index, we can only use it if it passes the
- * predicate test.
- */
- if (index->indpred == NIL)
- continue; /* ignore non-partial indexes */
-
- index->predOK = pred_test(index->indpred, restrictinfo_list);
- }
-}
-
-/*
- * pred_test
- * Does the "predicate inclusion test" for partial indexes.
- *
- * Recursively checks whether the clauses in restrictinfo_list imply
- * that the given predicate is true.
- *
- * The top-level List structure of each list corresponds to an AND list.
- * We assume that eval_const_expressions() has been applied and so there
- * are no un-flattened ANDs or ORs (e.g., no AND immediately within an AND,
- * including AND just below the top-level List structure).
- * If this is not true we might fail to prove an implication that is
- * valid, but no worse consequences will ensue.
- */
-bool
-pred_test(List *predicate_list, List *restrictinfo_list)
-{
- ListCell *item;
-
/*
* Note: if Postgres tried to optimize queries by forming equivalence
* classes over equi-joined attributes (i.e., if it recognized that a
* qualification such as "where a.b=c.d and a.b=5" could make use of
* an index on c.d), then we could use that equivalence class info
- * here with joininfo_list to do more complete tests for the usability
+ * here with joininfo lists to do more complete tests for the usability
* of a partial index. For now, the test only uses restriction
- * clauses (those in restrictinfo_list). --Nels, Dec '92
+ * clauses (those in baserestrictinfo). --Nels, Dec '92
*
* XXX as of 7.1, equivalence class info *is* available. Consider
* improving this code as foreseen by Nels.
*/
- if (predicate_list == NIL)
- return true; /* no predicate: the index is usable */
- if (restrictinfo_list == NIL)
- return false; /* no restriction clauses: the test must
- * fail */
-
- /*
- * In all cases where the predicate is an AND-clause, pred_test_recurse()
- * will prefer to iterate over the predicate's components. So we can
- * just do that to start with here, and eliminate the need for
- * pred_test_recurse() to handle a bare List on the predicate side.
- *
- * Logic is: restriction must imply each of the AND'ed predicate items.
- */
- foreach(item, predicate_list)
+ foreach(ilist, rel->indexlist)
{
- if (!pred_test_recurse((Node *) restrictinfo_list, lfirst(item)))
- return false;
+ IndexOptInfo *index = (IndexOptInfo *) lfirst(ilist);
+
+ if (index->indpred == NIL)
+ continue; /* ignore non-partial indexes */
+
+ index->predOK = predicate_implied_by(index->indpred,
+ restrictinfo_list);
}
- return true;
}
+/****************************************************************************
+ * ---- ROUTINES TO CHECK JOIN CLAUSES ----
+ ****************************************************************************/
-/*----------
- * pred_test_recurse
- * Does the "predicate inclusion test" for non-NULL restriction and
- * predicate clauses.
- *
- * The logic followed here is ("=>" means "implies"):
- * atom A => atom B iff: pred_test_simple_clause says so
- * atom A => AND-expr B iff: A => each of B's components
- * atom A => OR-expr B iff: A => any of B's components
- * AND-expr A => atom B iff: any of A's components => B
- * AND-expr A => AND-expr B iff: A => each of B's components
- * AND-expr A => OR-expr B iff: A => any of B's components,
- * *or* any of A's components => B
- * OR-expr A => atom B iff: each of A's components => B
- * OR-expr A => AND-expr B iff: A => each of B's components
- * OR-expr A => OR-expr B iff: each of A's components => any of B's
- *
- * An "atom" is anything other than an AND or OR node. Notice that we don't
- * have any special logic to handle NOT nodes; these should have been pushed
- * down or eliminated where feasible by prepqual.c.
- *
- * We can't recursively expand either side first, but have to interleave
- * the expansions per the above rules, to be sure we handle all of these
- * examples:
- * (x OR y) => (x OR y OR z)
- * (x AND y AND z) => (x AND y)
- * (x AND y) => ((x AND y) OR z)
- * ((x OR y) AND z) => (x OR y)
- * This is still not an exhaustive test, but it handles most normal cases
- * under the assumption that both inputs have been AND/OR flattened.
- *
- * A bare List node on the restriction side is interpreted as an AND clause,
- * in order to handle the top-level restriction List properly. However we
- * need not consider a List on the predicate side since pred_test() already
- * expanded it.
- *
- * We have to be prepared to handle RestrictInfo nodes in the restrictinfo
- * tree, though not in the predicate tree.
- *----------
+/*
+ * indexable_outerrelids
+ * Finds all other relids that participate in any indexable join clause
+ * for the specified table. Returns a set of relids.
*/
-static bool
-pred_test_recurse(Node *clause, Node *predicate)
+static Relids
+indexable_outerrelids(RelOptInfo *rel)
{
- ListCell *item;
-
- Assert(clause != NULL);
- /* skip through RestrictInfo */
- if (IsA(clause, RestrictInfo))
- {
- clause = (Node *) ((RestrictInfo *) clause)->clause;
- Assert(clause != NULL);
- Assert(!IsA(clause, RestrictInfo));
- }
- Assert(predicate != NULL);
+ Relids outer_relids = NULL;
+ ListCell *l;
/*
- * Since a restriction List clause is handled the same as an AND clause,
- * we can avoid duplicate code like this:
+ * Examine each joinclause in the joininfo list to see if it matches any
+ * key of any index. If so, add the clause's other rels to the result.
*/
- if (and_clause(clause))
- clause = (Node *) ((BoolExpr *) clause)->args;
-
- if (IsA(clause, List))
+ foreach(l, rel->joininfo)
{
- if (and_clause(predicate))
- {
- /* AND-clause => AND-clause if A implies each of B's items */
- foreach(item, ((BoolExpr *) predicate)->args)
- {
- if (!pred_test_recurse(clause, lfirst(item)))
- return false;
- }
- return true;
- }
- else if (or_clause(predicate))
- {
- /* AND-clause => OR-clause if A implies any of B's items */
- /* Needed to handle (x AND y) => ((x AND y) OR z) */
- foreach(item, ((BoolExpr *) predicate)->args)
- {
- if (pred_test_recurse(clause, lfirst(item)))
- return true;
- }
- /* Also check if any of A's items implies B */
- /* Needed to handle ((x OR y) AND z) => (x OR y) */
- foreach(item, (List *) clause)
- {
- if (pred_test_recurse(lfirst(item), predicate))
- return true;
- }
- return false;
- }
- else
- {
- /* AND-clause => atom if any of A's items implies B */
- foreach(item, (List *) clause)
- {
- if (pred_test_recurse(lfirst(item), predicate))
- return true;
- }
- return false;
- }
- }
- else if (or_clause(clause))
- {
- if (or_clause(predicate))
- {
- /*
- * OR-clause => OR-clause if each of A's items implies any of
- * B's items. Messy but can't do it any more simply.
- */
- foreach(item, ((BoolExpr *) clause)->args)
- {
- Node *citem = lfirst(item);
- ListCell *item2;
+ RestrictInfo *joininfo = (RestrictInfo *) lfirst(l);
+ Relids other_rels;
- foreach(item2, ((BoolExpr *) predicate)->args)
- {
- if (pred_test_recurse(citem, lfirst(item2)))
- break;
- }
- if (item2 == NULL)
- return false; /* doesn't imply any of B's */
- }
- return true;
- }
- else
- {
- /* OR-clause => AND-clause if each of A's items implies B */
- /* OR-clause => atom if each of A's items implies B */
- foreach(item, ((BoolExpr *) clause)->args)
- {
- if (!pred_test_recurse(lfirst(item), predicate))
- return false;
- }
- return true;
- }
- }
- else
- {
- if (and_clause(predicate))
- {
- /* atom => AND-clause if A implies each of B's items */
- foreach(item, ((BoolExpr *) predicate)->args)
- {
- if (!pred_test_recurse(clause, lfirst(item)))
- return false;
- }
- return true;
- }
- else if (or_clause(predicate))
- {
- /* atom => OR-clause if A implies any of B's items */
- foreach(item, ((BoolExpr *) predicate)->args)
- {
- if (pred_test_recurse(clause, lfirst(item)))
- return true;
- }
- return false;
- }
+ other_rels = bms_difference(joininfo->required_relids, rel->relids);
+ if (matches_any_index(joininfo, rel, other_rels))
+ outer_relids = bms_join(outer_relids, other_rels);
else
- {
- /* atom => atom is the base case */
- return pred_test_simple_clause((Expr *) predicate, clause);
- }
+ bms_free(other_rels);
}
-}
+ return outer_relids;
+}
/*
- * Define an "operator implication table" for btree operators ("strategies").
- *
- * The strategy numbers defined by btree indexes (see access/skey.h) are:
- * (1) < (2) <= (3) = (4) >= (5) >
- * and in addition we use (6) to represent <>. <> is not a btree-indexable
- * operator, but we assume here that if the equality operator of a btree
- * opclass has a negator operator, the negator behaves as <> for the opclass.
- *
- * The interpretation of:
- *
- * test_op = BT_implic_table[given_op-1][target_op-1]
- *
- * where test_op, given_op and target_op are strategy numbers (from 1 to 6)
- * of btree operators, is as follows:
- *
- * If you know, for some ATTR, that "ATTR given_op CONST1" is true, and you
- * want to determine whether "ATTR target_op CONST2" must also be true, then
- * you can use "CONST2 test_op CONST1" as a test. If this test returns true,
- * then the target expression must be true; if the test returns false, then
- * the target expression may be false.
- *
- * An entry where test_op == 0 means the implication cannot be determined,
- * i.e., this test should always be considered false.
- */
-
-#define BTLT BTLessStrategyNumber
-#define BTLE BTLessEqualStrategyNumber
-#define BTEQ BTEqualStrategyNumber
-#define BTGE BTGreaterEqualStrategyNumber
-#define BTGT BTGreaterStrategyNumber
-#define BTNE 6
-
-static const StrategyNumber
- BT_implic_table[6][6] = {
-/*
- * The target operator:
- *
- * LT LE EQ GE GT NE
- */
- {BTGE, BTGE, 0, 0, 0, BTGE}, /* LT */
- {BTGT, BTGE, 0, 0, 0, BTGT}, /* LE */
- {BTGT, BTGE, BTEQ, BTLE, BTLT, BTNE}, /* EQ */
- {0, 0, 0, BTLE, BTLT, BTLT}, /* GE */
- {0, 0, 0, BTLE, BTLE, BTLE}, /* GT */
- {0, 0, 0, 0, 0, BTEQ} /* NE */
-};
-
-
-/*----------
- * pred_test_simple_clause
- * Does the "predicate inclusion test" for a "simple clause" predicate
- * and a "simple clause" restriction.
- *
- * We have three strategies for determining whether one simple clause
- * implies another:
- *
- * A simple and general way is to see if they are equal(); this works for any
- * kind of expression. (Actually, there is an implied assumption that the
- * functions in the expression are immutable, ie dependent only on their input
- * arguments --- but this was checked for the predicate by CheckPredicate().)
- *
- * When the predicate is of the form "foo IS NOT NULL", we can conclude that
- * the predicate is implied if the clause is a strict operator or function
- * that has "foo" as an input. In this case the clause must yield NULL when
- * "foo" is NULL, which we can take as equivalent to FALSE because we know
- * we are within an AND/OR subtree of a WHERE clause. (Again, "foo" is
- * already known immutable, so the clause will certainly always fail.)
- *
- * Our other way works only for binary boolean opclauses of the form
- * "foo op constant", where "foo" is the same in both clauses. The operators
- * and constants can be different but the operators must be in the same btree
- * operator class. We use the above operator implication table to be able to
- * derive implications between nonidentical clauses. (Note: "foo" is known
- * immutable, and constants are surely immutable, but we have to check that
- * the operators are too. As of 8.0 it's possible for opclasses to contain
- * operators that are merely stable, and we dare not make deductions with
- * these.)
- *
- * Eventually, rtree operators could also be handled by defining an
- * appropriate "RT_implic_table" array.
- *----------
+ * matches_any_index
+ * Workhorse for indexable_outerrelids: see if a joinclause can be
+ * matched to any index of the given rel.
*/
static bool
-pred_test_simple_clause(Expr *predicate, Node *clause)
+matches_any_index(RestrictInfo *rinfo, RelOptInfo *rel, Relids outer_relids)
{
- Node *leftop,
- *rightop;
- Node *pred_var,
- *clause_var;
- Const *pred_const,
- *clause_const;
- bool pred_var_on_left,
- clause_var_on_left,
- pred_op_negated;
- Oid pred_op,
- clause_op,
- pred_op_negator,
- clause_op_negator,
- test_op = InvalidOid;
- Oid opclass_id;
- bool found = false;
- StrategyNumber pred_strategy,
- clause_strategy,
- test_strategy;
- Oid clause_subtype;
- Expr *test_expr;
- ExprState *test_exprstate;
- Datum test_result;
- bool isNull;
- CatCList *catlist;
- int i;
- EState *estate;
- MemoryContext oldcontext;
-
- /* First try the equal() test */
- if (equal((Node *) predicate, clause))
- return true;
-
- /* Next try the IS NOT NULL case */
- if (predicate && IsA(predicate, NullTest) &&
- ((NullTest *) predicate)->nulltesttype == IS_NOT_NULL)
- {
- Expr *nonnullarg = ((NullTest *) predicate)->arg;
-
- if (is_opclause(clause) &&
- list_member(((OpExpr *) clause)->args, nonnullarg) &&
- op_strict(((OpExpr *) clause)->opno))
- return true;
- if (is_funcclause(clause) &&
- list_member(((FuncExpr *) clause)->args, nonnullarg) &&
- func_strict(((FuncExpr *) clause)->funcid))
- return true;
- return false; /* we can't succeed below... */
- }
-
- /*
- * Can't do anything more unless they are both binary opclauses with a
- * Const on one side, and identical subexpressions on the other sides.
- * Note we don't have to think about binary relabeling of the Const
- * node, since that would have been folded right into the Const.
- *
- * If either Const is null, we also fail right away; this assumes that
- * the test operator will always be strict.
- */
- if (!is_opclause(predicate))
- return false;
- leftop = get_leftop(predicate);
- rightop = get_rightop(predicate);
- if (rightop == NULL)
- return false; /* not a binary opclause */
- if (IsA(rightop, Const))
- {
- pred_var = leftop;
- pred_const = (Const *) rightop;
- pred_var_on_left = true;
- }
- else if (IsA(leftop, Const))
- {
- pred_var = rightop;
- pred_const = (Const *) leftop;
- pred_var_on_left = false;
- }
- else
- return false; /* no Const to be found */
- if (pred_const->constisnull)
- return false;
-
- if (!is_opclause(clause))
- return false;
- leftop = get_leftop((Expr *) clause);
- rightop = get_rightop((Expr *) clause);
- if (rightop == NULL)
- return false; /* not a binary opclause */
- if (IsA(rightop, Const))
- {
- clause_var = leftop;
- clause_const = (Const *) rightop;
- clause_var_on_left = true;
- }
- else if (IsA(leftop, Const))
- {
- clause_var = rightop;
- clause_const = (Const *) leftop;
- clause_var_on_left = false;
- }
- else
- return false; /* no Const to be found */
- if (clause_const->constisnull)
- return false;
-
- /*
- * Check for matching subexpressions on the non-Const sides. We used
- * to only allow a simple Var, but it's about as easy to allow any
- * expression. Remember we already know that the pred expression does
- * not contain any non-immutable functions, so identical expressions
- * should yield identical results.
- */
- if (!equal(pred_var, clause_var))
- return false;
-
- /*
- * Okay, get the operators in the two clauses we're comparing. Commute
- * them if needed so that we can assume the variables are on the left.
- */
- pred_op = ((OpExpr *) predicate)->opno;
- if (!pred_var_on_left)
- {
- pred_op = get_commutator(pred_op);
- if (!OidIsValid(pred_op))
- return false;
- }
-
- clause_op = ((OpExpr *) clause)->opno;
- if (!clause_var_on_left)
- {
- clause_op = get_commutator(clause_op);
- if (!OidIsValid(clause_op))
- return false;
- }
+ ListCell *l;
- /*
- * Try to find a btree opclass containing the needed operators.
- *
- * We must find a btree opclass that contains both operators, else the
- * implication can't be determined. Also, the pred_op has to be of
- * default subtype (implying left and right input datatypes are the
- * same); otherwise it's unsafe to put the pred_const on the left side
- * of the test. Also, the opclass must contain a suitable test
- * operator matching the clause_const's type (which we take to mean
- * that it has the same subtype as the original clause_operator).
- *
- * If there are multiple matching opclasses, assume we can use any one to
- * determine the logical relationship of the two operators and the
- * correct corresponding test operator. This should work for any
- * logically consistent opclasses.
- */
- catlist = SearchSysCacheList(AMOPOPID, 1,
- ObjectIdGetDatum(pred_op),
- 0, 0, 0);
+ Assert(IsA(rinfo, RestrictInfo));
- /*
- * If we couldn't find any opclass containing the pred_op, perhaps it
- * is a <> operator. See if it has a negator that is in an opclass.
- */
- pred_op_negated = false;
- if (catlist->n_members == 0)
+ if (restriction_is_or_clause(rinfo))
{
- pred_op_negator = get_negator(pred_op);
- if (OidIsValid(pred_op_negator))
+ foreach(l, ((BoolExpr *) rinfo->orclause)->args)
{
- pred_op_negated = true;
- ReleaseSysCacheList(catlist);
- catlist = SearchSysCacheList(AMOPOPID, 1,
- ObjectIdGetDatum(pred_op_negator),
- 0, 0, 0);
- }
- }
-
- /* Also may need the clause_op's negator */
- clause_op_negator = get_negator(clause_op);
-
- /* Now search the opclasses */
- for (i = 0; i < catlist->n_members; i++)
- {
- HeapTuple pred_tuple = &catlist->members[i]->tuple;
- Form_pg_amop pred_form = (Form_pg_amop) GETSTRUCT(pred_tuple);
- HeapTuple clause_tuple;
-
- opclass_id = pred_form->amopclaid;
+ Node *orarg = (Node *) lfirst(l);
- /* must be btree */
- if (!opclass_is_btree(opclass_id))
- continue;
- /* predicate operator must be default within this opclass */
- if (pred_form->amopsubtype != InvalidOid)
- continue;
-
- /* Get the predicate operator's btree strategy number */
- pred_strategy = (StrategyNumber) pred_form->amopstrategy;
- Assert(pred_strategy >= 1 && pred_strategy <= 5);
-
- if (pred_op_negated)
- {
- /* Only consider negators that are = */
- if (pred_strategy != BTEqualStrategyNumber)
- continue;
- pred_strategy = BTNE;
- }
-
- /*
- * From the same opclass, find a strategy number for the
- * clause_op, if possible
- */
- clause_tuple = SearchSysCache(AMOPOPID,
- ObjectIdGetDatum(clause_op),
- ObjectIdGetDatum(opclass_id),
- 0, 0);
- if (HeapTupleIsValid(clause_tuple))
- {
- Form_pg_amop clause_form = (Form_pg_amop) GETSTRUCT(clause_tuple);
-
- /* Get the restriction clause operator's strategy/subtype */
- clause_strategy = (StrategyNumber) clause_form->amopstrategy;
- Assert(clause_strategy >= 1 && clause_strategy <= 5);
- clause_subtype = clause_form->amopsubtype;
- ReleaseSysCache(clause_tuple);
- }
- else if (OidIsValid(clause_op_negator))
- {
- clause_tuple = SearchSysCache(AMOPOPID,
- ObjectIdGetDatum(clause_op_negator),
- ObjectIdGetDatum(opclass_id),
- 0, 0);
- if (HeapTupleIsValid(clause_tuple))
+ /* OR arguments should be ANDs or sub-RestrictInfos */
+ if (and_clause(orarg))
{
- Form_pg_amop clause_form = (Form_pg_amop) GETSTRUCT(clause_tuple);
+ ListCell *j;
- /* Get the restriction clause operator's strategy/subtype */
- clause_strategy = (StrategyNumber) clause_form->amopstrategy;
- Assert(clause_strategy >= 1 && clause_strategy <= 5);
- clause_subtype = clause_form->amopsubtype;
- ReleaseSysCache(clause_tuple);
+ /* Recurse to examine AND items and sub-ORs */
+ foreach(j, ((BoolExpr *) orarg)->args)
+ {
+ RestrictInfo *arinfo = (RestrictInfo *) lfirst(j);
- /* Only consider negators that are = */
- if (clause_strategy != BTEqualStrategyNumber)
- continue;
- clause_strategy = BTNE;
+ if (matches_any_index(arinfo, rel, outer_relids))
+ return true;
+ }
}
else
- continue;
- }
- else
- continue;
-
- /*
- * Look up the "test" strategy number in the implication table
- */
- test_strategy = BT_implic_table[clause_strategy - 1][pred_strategy - 1];
- if (test_strategy == 0)
- {
- /* Can't determine implication using this interpretation */
- continue;
- }
-
- /*
- * See if opclass has an operator for the test strategy and the
- * clause datatype.
- */
- if (test_strategy == BTNE)
- {
- test_op = get_opclass_member(opclass_id, clause_subtype,
- BTEqualStrategyNumber);
- if (OidIsValid(test_op))
- test_op = get_negator(test_op);
- }
- else
- {
- test_op = get_opclass_member(opclass_id, clause_subtype,
- test_strategy);
- }
- if (OidIsValid(test_op))
- {
- /*
- * Last check: test_op must be immutable.
- *
- * Note that we require only the test_op to be immutable, not the
- * original clause_op. (pred_op must be immutable, else it
- * would not be allowed in an index predicate.) Essentially
- * we are assuming that the opclass is consistent even if it
- * contains operators that are merely stable.
- */
- if (op_volatile(test_op) == PROVOLATILE_IMMUTABLE)
{
- found = true;
- break;
+ /* Recurse to examine simple clause */
+ Assert(IsA(orarg, RestrictInfo));
+ Assert(!restriction_is_or_clause((RestrictInfo *) orarg));
+ if (matches_any_index((RestrictInfo *) orarg, rel,
+ outer_relids))
+ return true;
}
}
- }
- ReleaseSysCacheList(catlist);
-
- if (!found)
- {
- /* couldn't find a btree opclass to interpret the operators */
return false;
}
- /*
- * Evaluate the test. For this we need an EState.
- */
- estate = CreateExecutorState();
-
- /* We can use the estate's working context to avoid memory leaks. */
- oldcontext = MemoryContextSwitchTo(estate->es_query_cxt);
-
- /* Build expression tree */
- test_expr = make_opclause(test_op,
- BOOLOID,
- false,
- (Expr *) pred_const,
- (Expr *) clause_const);
-
- /* Prepare it for execution */
- test_exprstate = ExecPrepareExpr(test_expr, estate);
-
- /* And execute it. */
- test_result = ExecEvalExprSwitchContext(test_exprstate,
- GetPerTupleExprContext(estate),
- &isNull, NULL);
-
- /* Get back to outer memory context */
- MemoryContextSwitchTo(oldcontext);
-
- /* Release all the junk we just created */
- FreeExecutorState(estate);
-
- if (isNull)
+ /* Normal case for a simple restriction clause */
+ foreach(l, rel->indexlist)
{
- /* Treat a null result as false ... but it's a tad fishy ... */
- elog(DEBUG2, "null predicate test result");
- return false;
- }
- return DatumGetBool(test_result);
-}
+ IndexOptInfo *index = (IndexOptInfo *) lfirst(l);
+ int indexcol = 0;
+ Oid *classes = index->classlist;
-
-/****************************************************************************
- * ---- ROUTINES TO CHECK JOIN CLAUSES ----
- ****************************************************************************/
-
-/*
- * indexable_outerrelids
- * Finds all other relids that participate in any indexable join clause
- * for the specified index. Returns a set of relids.
- */
-static Relids
-indexable_outerrelids(IndexOptInfo *index)
-{
- Relids outer_relids = NULL;
- ListCell *l;
-
- foreach(l, index->rel->joininfo)
- {
- JoinInfo *joininfo = (JoinInfo *) lfirst(l);
- bool match_found = false;
- ListCell *j;
-
- /*
- * Examine each joinclause in the JoinInfo node's list to see if
- * it matches any key of the index. If so, add the JoinInfo's
- * otherrels to the result. We can skip examining other
- * joinclauses in the same list as soon as we find a match (since
- * by definition they all have the same otherrels).
- */
- foreach(j, joininfo->jinfo_restrictinfo)
+ do
{
- RestrictInfo *rinfo = (RestrictInfo *) lfirst(j);
- int indexcol = 0;
- Oid *classes = index->classlist;
-
- do
- {
- Oid curClass = classes[0];
-
- if (match_join_clause_to_indexcol(index,
- indexcol,
- curClass,
- rinfo))
- {
- match_found = true;
- break;
- }
-
- indexcol++;
- classes++;
+ Oid curClass = classes[0];
- } while (!DoneMatchingIndexKeys(classes));
-
- if (match_found)
- break;
- }
+ if (match_clause_to_indexcol(index,
+ indexcol,
+ curClass,
+ rinfo,
+ outer_relids))
+ return true;
- if (match_found)
- {
- outer_relids = bms_add_members(outer_relids,
- joininfo->unjoined_relids);
- }
+ indexcol++;
+ classes++;
+ } while (!DoneMatchingIndexKeys(classes));
}
- return outer_relids;
+ return false;
}
/*
* sufficient to return a single "best" path.
*/
Path *
-best_inner_indexscan(Query *root, RelOptInfo *rel,
+best_inner_indexscan(PlannerInfo *root, RelOptInfo *rel,
Relids outer_relids, JoinType jointype)
{
- Path *cheapest = NULL;
+ Path *cheapest;
bool isouterjoin;
- ListCell *ilist;
- ListCell *jlist;
+ List *clause_list;
+ List *indexpaths;
+ List *bitindexpaths;
+ ListCell *l;
InnerIndexscanInfo *info;
MemoryContext oldcontext;
/*
* Intersect the given outer_relids with index_outer_relids to find
- * the set of outer relids actually relevant for this index. If there
+ * 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_relids);
* necessary because it should always be the same for a given
* innerrel.)
*/
- foreach(jlist, rel->index_inner_paths)
+ foreach(l, rel->index_inner_paths)
{
- info = (InnerIndexscanInfo *) lfirst(jlist);
+ info = (InnerIndexscanInfo *) lfirst(l);
if (bms_equal(info->other_relids, outer_relids) &&
info->isouterjoin == isouterjoin)
{
}
/*
- * For each index of the rel, find the best path; then choose the best
- * overall. We cache the per-index results as well as the overall
- * result. (This is useful because different indexes may have
- * different relevant outerrel sets, so different overall outerrel
- * sets might still map to the same computation for a given index.)
+ * Find all the relevant restriction and join clauses.
*/
- foreach(ilist, rel->indexlist)
- {
- IndexOptInfo *index = (IndexOptInfo *) lfirst(ilist);
- Relids index_outer_relids;
- Path *path = NULL;
+ clause_list = find_clauses_for_join(root, rel, outer_relids, isouterjoin);
- /* identify set of relevant outer relids for this index */
- index_outer_relids = bms_intersect(index->outer_relids, outer_relids);
- /* skip if none */
- if (bms_is_empty(index_outer_relids))
- {
- bms_free(index_outer_relids);
- continue;
- }
+ /*
+ * Find all the index paths that are usable for this join, except for
+ * stuff involving OR clauses.
+ */
+ indexpaths = find_usable_indexes(root, rel,
+ clause_list, NIL,
+ false, true,
+ outer_relids);
- /*
- * Look to see if we already computed the result for this index.
- */
- foreach(jlist, index->inner_paths)
- {
- info = (InnerIndexscanInfo *) lfirst(jlist);
- if (bms_equal(info->other_relids, index_outer_relids) &&
- info->isouterjoin == isouterjoin)
- {
- path = info->best_innerpath;
- bms_free(index_outer_relids); /* not needed anymore */
- break;
- }
- }
+ /*
+ * Generate BitmapOrPaths for any suitable OR-clauses present in the
+ * clause list.
+ */
+ bitindexpaths = generate_bitmap_or_paths(root, rel,
+ clause_list, NIL,
+ true,
+ outer_relids);
- if (jlist == NULL) /* failed to find a match? */
- {
- List *clausegroups;
-
- /* find useful clauses for this index and outerjoin set */
- clausegroups = group_clauses_by_indexkey_for_join(root,
- index,
- index_outer_relids,
- jointype,
- isouterjoin);
- if (clausegroups)
- {
- /* make the path */
- path = make_innerjoin_index_path(root, index, clausegroups);
- }
+ /*
+ * Include the regular index paths in bitindexpaths.
+ */
+ bitindexpaths = list_concat(bitindexpaths, list_copy(indexpaths));
- /* Cache the result --- whether positive or negative */
- info = makeNode(InnerIndexscanInfo);
- info->other_relids = index_outer_relids;
- info->isouterjoin = isouterjoin;
- info->best_innerpath = path;
- index->inner_paths = lcons(info, index->inner_paths);
- }
+ /*
+ * 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);
+ bpath = create_bitmap_heap_path(root, rel, bitmapqual, true);
+ indexpaths = lappend(indexpaths, bpath);
+ }
+
+ /*
+ * Now choose the cheapest member of indexpaths.
+ */
+ cheapest = NULL;
+ foreach(l, indexpaths)
+ {
+ Path *path = (Path *) lfirst(l);
- if (path != NULL &&
- (cheapest == NULL ||
- compare_path_costs(path, cheapest, TOTAL_COST) < 0))
+ if (cheapest == NULL ||
+ compare_path_costs(path, cheapest, TOTAL_COST) < 0)
cheapest = path;
}
return cheapest;
}
-/****************************************************************************
- * ---- PATH CREATION UTILITIES ----
- ****************************************************************************/
-
/*
- * make_innerjoin_index_path
- * Create an index path node for a path to be used as an inner
- * relation in a nestloop join.
- *
- * 'index' is the index of interest
- * 'clausegroups' is a list of lists of RestrictInfos that can use 'index'
+ * 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 Path *
-make_innerjoin_index_path(Query *root,
- IndexOptInfo *index,
- List *clausegroups)
+static List *
+find_clauses_for_join(PlannerInfo *root, RelOptInfo *rel,
+ Relids outer_relids, bool isouterjoin)
{
- IndexPath *pathnode = makeNode(IndexPath);
- RelOptInfo *rel = index->rel;
- List *indexquals,
- *allclauses;
-
- /* XXX perhaps this code should be merged with create_index_path? */
-
- pathnode->path.pathtype = T_IndexScan;
- pathnode->path.parent = rel;
+ List *clause_list = NIL;
+ bool jfound = false;
+ Relids join_relids;
+ ListCell *l;
/*
- * There's no point in marking the path with any pathkeys, since it
- * will only ever be used as the inner path of a nestloop, and so its
- * ordering does not matter.
+ * We can always use plain restriction clauses for the rel. We
+ * scan these first because we want them first in the clause
+ * list for the convenience of remove_redundant_join_clauses,
+ * which can never remove non-join clauses and hence won't be able
+ * to get rid of a non-join clause if it appears after a join
+ * clause it is redundant with.
*/
- pathnode->path.pathkeys = NIL;
+ foreach(l, rel->baserestrictinfo)
+ {
+ RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
+
+ /* Can't use pushed-down clauses in outer join */
+ if (isouterjoin && rinfo->is_pushed_down)
+ continue;
+ clause_list = lappend(clause_list, rinfo);
+ }
+
+ /* Look for joinclauses that are usable with given outer_relids */
+ join_relids = bms_union(rel->relids, outer_relids);
+
+ foreach(l, rel->joininfo)
+ {
+ RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
+
+ /* Can't use pushed-down 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);
+ jfound = true;
+ }
- /* Convert clauses to indexquals the executor can handle */
- indexquals = expand_indexqual_conditions(index, clausegroups);
+ bms_free(join_relids);
- /* Flatten the clausegroups list to produce indexclauses list */
- allclauses = flatten_clausegroups_list(clausegroups);
+ /* if no join clause was matched then forget it, per comments above */
+ if (!jfound)
+ return NIL;
/*
- * Note that we are making a pathnode for a single-scan indexscan;
- * therefore, indexinfo etc should be single-element lists.
+ * We may now have clauses that are known redundant. Get rid of 'em.
*/
- pathnode->indexinfo = list_make1(index);
- pathnode->indexclauses = list_make1(allclauses);
- pathnode->indexquals = list_make1(indexquals);
+ if (list_length(clause_list) > 1)
+ {
+ clause_list = remove_redundant_join_clauses(root,
+ clause_list,
+ isouterjoin);
+ }
- pathnode->isjoininner = true;
+ return clause_list;
+}
- /* We don't actually care what order the index scans in ... */
- pathnode->indexscandir = NoMovementScanDirection;
+/****************************************************************************
+ * ---- ROUTINES TO HANDLE PATHKEYS ----
+ ****************************************************************************/
+
+/*
+ * match_variant_ordering
+ * Try to match an index's ordering to the query's requested ordering
+ *
+ * This is used when the index is ordered but a naive comparison fails to
+ * match its ordering (pathkeys) to root->query_pathkeys. It may be that
+ * we need to scan the index backwards. Also, a less naive comparison can
+ * help for both forward and backward indexscans. Columns of the index
+ * that have an equality restriction clause can be ignored in the match;
+ * that is, an index on (x,y) can be considered to match the ordering of
+ * ... WHERE x = 42 ORDER BY y;
+ *
+ * Note: it would be possible to similarly ignore useless ORDER BY items;
+ * that is, an index on just y could be considered to match the ordering of
+ * ... WHERE x = 42 ORDER BY x, y;
+ * But proving that this is safe would require finding a btree opclass
+ * containing both the = operator and the < or > operator in the ORDER BY
+ * item. That's significantly more expensive than what we do here, since
+ * we'd have to look at restriction clauses unrelated to the current index
+ * and search for opclasses without any hint from the index. The practical
+ * use-cases seem to be mostly covered by ignoring index columns, so that's
+ * all we do for now.
+ *
+ * Inputs:
+ * 'index' is the index of interest.
+ * 'restrictclauses' is the list of sublists of restriction clauses
+ * matching the columns of the index (NIL if none)
+ *
+ * If able to match the requested query pathkeys, returns either
+ * ForwardScanDirection or BackwardScanDirection to indicate the proper index
+ * scan direction. If no match, returns NoMovementScanDirection.
+ */
+static ScanDirection
+match_variant_ordering(PlannerInfo *root,
+ IndexOptInfo *index,
+ List *restrictclauses)
+{
+ List *ignorables;
/*
- * We must compute the estimated number of output rows for the
- * indexscan. This is less than rel->rows because of the additional
- * selectivity of the join clauses. Since clausegroups may contain
- * both restriction and join clauses, we have to do a set union to get
- * the full set of clauses that must be considered to compute the
- * correct selectivity. (Without the union operation, we might have
- * some restriction clauses appearing twice, which'd mislead
- * clauselist_selectivity into double-counting their selectivity.
- * However, since RestrictInfo nodes aren't copied when linking them
- * into different lists, it should be sufficient to use pointer
- * comparison to remove duplicates.)
+ * Forget the whole thing if not a btree index; our check for ignorable
+ * columns assumes we are dealing with btree opclasses. (It'd be possible
+ * to factor out just the try for backwards indexscan, but considering
+ * that we presently have no orderable indexes except btrees anyway,
+ * it's hardly worth contorting this code for that case.)
*
- * Always assume the join type is JOIN_INNER; even if some of the join
- * clauses come from other contexts, that's not our problem.
+ * Note: if you remove this, you probably need to put in a check on
+ * amoptionalkey to prevent possible clauseless scan on an index that
+ * won't cope.
+ */
+ if (index->relam != BTREE_AM_OID)
+ return NoMovementScanDirection;
+ /*
+ * Figure out which index columns can be optionally ignored because
+ * they have an equality constraint. This is the same set for either
+ * forward or backward scan, so we do it just once.
+ */
+ ignorables = identify_ignorable_ordering_cols(root, index,
+ restrictclauses);
+ /*
+ * Try to match to forward scan, then backward scan. However, we can
+ * skip the forward-scan case if there are no ignorable columns,
+ * because find_usable_indexes() would have found the match already.
*/
- allclauses = list_union_ptr(rel->baserestrictinfo, allclauses);
- pathnode->rows = rel->tuples *
- clauselist_selectivity(root,
- allclauses,
- rel->relid, /* do not use 0! */
- JOIN_INNER);
- /* Like costsize.c, force estimate to be at least one row */
- pathnode->rows = clamp_row_est(pathnode->rows);
-
- cost_index(&pathnode->path, root, index, indexquals, true);
-
- return (Path *) pathnode;
+ if (ignorables &&
+ match_index_to_query_keys(root, index, ForwardScanDirection,
+ ignorables))
+ return ForwardScanDirection;
+
+ if (match_index_to_query_keys(root, index, BackwardScanDirection,
+ ignorables))
+ return BackwardScanDirection;
+
+ return NoMovementScanDirection;
}
/*
- * flatten_clausegroups_list
- * Given a list of lists of RestrictInfos, flatten it to a list
- * of RestrictInfos.
+ * identify_ignorable_ordering_cols
+ * Determine which index columns can be ignored for ordering purposes
*
- * This is used to flatten out the result of group_clauses_by_indexkey()
- * or one of its sibling routines, to produce an indexclauses list.
+ * Returns an integer List of column numbers (1-based) of ignorable
+ * columns. The ignorable columns are those that have equality constraints
+ * against pseudoconstants.
*/
-List *
-flatten_clausegroups_list(List *clausegroups)
+static List *
+identify_ignorable_ordering_cols(PlannerInfo *root,
+ IndexOptInfo *index,
+ List *restrictclauses)
{
- List *allclauses = NIL;
+ List *result = NIL;
+ int indexcol = 0; /* note this is 0-based */
ListCell *l;
- foreach(l, clausegroups)
- allclauses = list_concat(allclauses, list_copy((List *) lfirst(l)));
- return allclauses;
+ /* restrictclauses is either NIL or has a sublist per column */
+ foreach(l, restrictclauses)
+ {
+ List *sublist = (List *) lfirst(l);
+ Oid opclass = index->classlist[indexcol];
+ ListCell *l2;
+
+ foreach(l2, sublist)
+ {
+ RestrictInfo *rinfo = (RestrictInfo *) lfirst(l2);
+ OpExpr *clause = (OpExpr *) rinfo->clause;
+ Oid clause_op;
+ int op_strategy;
+ bool varonleft;
+ bool ispc;
+
+ /* We know this clause passed match_clause_to_indexcol */
+
+ /* First check for boolean-index cases. */
+ if (IsBooleanOpclass(opclass))
+ {
+ if (match_boolean_index_clause((Node *) clause, indexcol,
+ index))
+ {
+ /*
+ * The clause means either col = TRUE or col = FALSE;
+ * we do not care which, it's an equality constraint
+ * either way.
+ */
+ result = lappend_int(result, indexcol+1);
+ break;
+ }
+ }
+
+ /* Else clause must be a binary opclause. */
+ Assert(IsA(clause, OpExpr));
+
+ /* Determine left/right sides and check the operator */
+ clause_op = clause->opno;
+ if (match_index_to_operand(linitial(clause->args), indexcol,
+ index))
+ {
+ /* clause_op is correct */
+ varonleft = true;
+ }
+ else
+ {
+ Assert(match_index_to_operand(lsecond(clause->args), indexcol,
+ index));
+ /* Must flip operator to get the opclass member */
+ clause_op = get_commutator(clause_op);
+ varonleft = false;
+ }
+ if (!OidIsValid(clause_op))
+ continue; /* ignore non match, per next comment */
+ op_strategy = get_op_opclass_strategy(clause_op, opclass);
+
+ /*
+ * You might expect to see Assert(op_strategy != 0) here,
+ * but you won't: the clause might contain a special indexable
+ * operator rather than an ordinary opclass member. Currently
+ * none of the special operators are very likely to expand to
+ * an equality operator; we do not bother to check, but just
+ * assume no match.
+ */
+ if (op_strategy != BTEqualStrategyNumber)
+ continue;
+
+ /* Now check that other side is pseudoconstant */
+ if (varonleft)
+ ispc = is_pseudo_constant_clause_relids(lsecond(clause->args),
+ rinfo->right_relids);
+ else
+ ispc = is_pseudo_constant_clause_relids(linitial(clause->args),
+ rinfo->left_relids);
+ if (ispc)
+ {
+ result = lappend_int(result, indexcol+1);
+ break;
+ }
+ }
+ indexcol++;
+ }
+ return result;
}
/*
- * make_expr_from_indexclauses()
- * Given an indexclauses structure, produce an ordinary boolean expression.
+ * match_index_to_query_keys
+ * Check a single scan direction for "intelligent" match to query keys
+ *
+ * 'index' is the index of interest.
+ * 'indexscandir' is the scan direction to consider
+ * 'ignorables' is an integer list of indexes of ignorable index columns
*
- * This consists of stripping out the RestrictInfo nodes and inserting
- * explicit AND and OR nodes as needed. There's not much to it, but
- * the functionality is needed in a few places, so centralize the logic.
+ * Returns TRUE on successful match (ie, the query_pathkeys can be considered
+ * to match this index).
*/
-Expr *
-make_expr_from_indexclauses(List *indexclauses)
+static bool
+match_index_to_query_keys(PlannerInfo *root,
+ IndexOptInfo *index,
+ ScanDirection indexscandir,
+ List *ignorables)
{
- List *orclauses = NIL;
- ListCell *orlist;
+ List *index_pathkeys;
+ ListCell *index_cell;
+ int index_col;
+ ListCell *r;
- /* There's no such thing as an indexpath with zero scans */
- Assert(indexclauses != NIL);
+ /* Get the pathkeys that exactly describe the index */
+ index_pathkeys = build_index_pathkeys(root, index, indexscandir);
- foreach(orlist, indexclauses)
+ /*
+ * Can we match to the query's requested pathkeys? The inner loop
+ * skips over ignorable index columns while trying to match.
+ */
+ index_cell = list_head(index_pathkeys);
+ index_col = 0;
+
+ foreach(r, root->query_pathkeys)
{
- List *andlist = (List *) lfirst(orlist);
+ List *rsubkey = (List *) lfirst(r);
+
+ for (;;)
+ {
+ List *isubkey;
+
+ if (index_cell == NULL)
+ return false;
+ isubkey = (List *) lfirst(index_cell);
+ index_cell = lnext(index_cell);
+ index_col++; /* index_col is now 1-based */
+ /*
+ * Since we are dealing with canonicalized pathkeys, pointer
+ * comparison is sufficient to determine a match.
+ */
+ if (rsubkey == isubkey)
+ break; /* matched current query pathkey */
- /* Strip RestrictInfos */
- andlist = get_actual_clauses(andlist);
- /* Insert AND node if needed, and add to orclauses list */
- orclauses = lappend(orclauses, make_ands_explicit(andlist));
+ if (!list_member_int(ignorables, index_col))
+ return false; /* definite failure to match */
+ /* otherwise loop around and try to match to next index col */
+ }
}
- if (list_length(orclauses) > 1)
- return make_orclause(orclauses);
- else
- return (Expr *) linitial(orclauses);
+ return true;
+}
+
+/****************************************************************************
+ * ---- 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;
}
* will know what to do with.
*
* The input list is ordered by index key, and so the output list is too.
- * (The latter is not depended on by any part of the planner, so far as I can
- * tell; but some parts of the executor do assume that the indxqual list
- * ultimately delivered to the executor is so ordered. One such place is
- * _bt_preprocess_keys() in the btree support. Perhaps that ought to be fixed
- * someday --- tgl 7/00)
+ * (The latter is not depended on by any part of the core planner, I believe,
+ * but parts of the executor require it, and so do the amcostestimate
+ * functions.)
*/
List *
expand_indexqual_conditions(IndexOptInfo *index, List *clausegroups)
{
resultquals = lappend(resultquals,
make_restrictinfo(boolqual,
- true, true));
+ true,
+ NULL));
continue;
}
}
elog(ERROR, "no = operator for opclass %u", opclass);
expr = make_opclause(oproid, BOOLOID, false,
(Expr *) leftop, (Expr *) prefix_const);
- result = list_make1(make_restrictinfo(expr, true, true));
+ result = list_make1(make_restrictinfo(expr, true, NULL));
return result;
}
elog(ERROR, "no >= operator for opclass %u", opclass);
expr = make_opclause(oproid, BOOLOID, false,
(Expr *) leftop, (Expr *) prefix_const);
- result = list_make1(make_restrictinfo(expr, true, true));
+ result = list_make1(make_restrictinfo(expr, true, NULL));
/*-------
* If we can create a string larger than the prefix, we can say
elog(ERROR, "no < operator for opclass %u", opclass);
expr = make_opclause(oproid, BOOLOID, false,
(Expr *) leftop, (Expr *) greaterstr);
- result = lappend(result, make_restrictinfo(expr, true, true));
+ result = lappend(result, make_restrictinfo(expr, true, NULL));
}
return result;
(Expr *) leftop,
(Expr *) makeConst(datatype, -1, opr1right,
false, false));
- result = list_make1(make_restrictinfo(expr, true, true));
+ result = list_make1(make_restrictinfo(expr, true, NULL));
/* create clause "key <= network_scan_last( rightop )" */
(Expr *) leftop,
(Expr *) makeConst(datatype, -1, opr2right,
false, false));
- result = lappend(result, make_restrictinfo(expr, true, true));
+ result = lappend(result, make_restrictinfo(expr, true, NULL));
return result;
}
projects / postgresql / blobdiff