aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/backend/nodes/copyfuncs.c33
-rw-r--r--src/backend/nodes/equalfuncs.c31
-rw-r--r--src/backend/nodes/list.c42
-rw-r--r--src/backend/nodes/outfuncs.c10
-rw-r--r--src/backend/nodes/readfuncs.c9
-rw-r--r--src/backend/optimizer/path/indxpath.c776
-rw-r--r--src/backend/optimizer/path/joinpath.c71
-rw-r--r--src/backend/optimizer/path/orindxpath.c5
-rw-r--r--src/backend/optimizer/path/tidpath.c42
-rw-r--r--src/backend/optimizer/plan/initsplan.c15
-rw-r--r--src/backend/optimizer/util/pathnode.c9
-rw-r--r--src/backend/optimizer/util/plancat.c6
-rw-r--r--src/backend/optimizer/util/relnode.c66
-rw-r--r--src/backend/optimizer/util/restrictinfo.c87
-rw-r--r--src/include/nodes/nodes.h3
-rw-r--r--src/include/nodes/pg_list.h3
-rw-r--r--src/include/nodes/relation.h104
-rw-r--r--src/include/optimizer/paths.h4
-rw-r--r--src/include/optimizer/restrictinfo.h5
19 files changed, 742 insertions, 579 deletions
diff --git a/src/backend/nodes/copyfuncs.c b/src/backend/nodes/copyfuncs.c
index eb9bbe93658..da3bf7b7213 100644
--- a/src/backend/nodes/copyfuncs.c
+++ b/src/backend/nodes/copyfuncs.c
@@ -15,7 +15,7 @@
* Portions Copyright (c) 1994, Regents of the University of California
*
* IDENTIFICATION
- * $Header: /cvsroot/pgsql/src/backend/nodes/copyfuncs.c,v 1.220 2002/11/23 03:59:07 momjian Exp $
+ * $Header: /cvsroot/pgsql/src/backend/nodes/copyfuncs.c,v 1.221 2002/11/24 21:52:13 tgl Exp $
*
*-------------------------------------------------------------------------
*/
@@ -1148,7 +1148,9 @@ _copyRelOptInfo(RelOptInfo *from)
newnode->baserestrictcost = from->baserestrictcost;
newnode->outerjoinset = listCopy(from->outerjoinset);
Node_Copy(from, newnode, joininfo);
- Node_Copy(from, newnode, innerjoin);
+
+ newnode->index_outer_relids = listCopy(from->index_outer_relids);
+ Node_Copy(from, newnode, index_inner_paths);
return newnode;
}
@@ -1200,6 +1202,9 @@ _copyIndexOptInfo(IndexOptInfo *from)
Node_Copy(from, newnode, indpred);
newnode->unique = from->unique;
+ newnode->outer_relids = listCopy(from->outer_relids);
+ Node_Copy(from, newnode, inner_paths);
+
return newnode;
}
@@ -1262,8 +1267,6 @@ _copyIndexPath(IndexPath *from)
Node_Copy(from, newnode, indexinfo);
Node_Copy(from, newnode, indexqual);
newnode->indexscandir = from->indexscandir;
- newnode->joinrelids = listCopy(from->joinrelids);
- newnode->alljoinquals = from->alljoinquals;
newnode->rows = from->rows;
return newnode;
@@ -1491,6 +1494,25 @@ _copyJoinInfo(JoinInfo *from)
return newnode;
}
+/* ----------------
+ * _copyInnerIndexscanInfo
+ * ----------------
+ */
+static InnerIndexscanInfo *
+_copyInnerIndexscanInfo(InnerIndexscanInfo *from)
+{
+ InnerIndexscanInfo *newnode = makeNode(InnerIndexscanInfo);
+
+ /*
+ * copy remainder of node
+ */
+ newnode->other_relids = listCopy(from->other_relids);
+ newnode->isouterjoin = from->isouterjoin;
+ Node_Copy(from, newnode, best_innerpath);
+
+ return newnode;
+}
+
/* ****************************************************************
* parsenodes.h copy functions
* ****************************************************************
@@ -2952,6 +2974,9 @@ copyObject(void *from)
case T_IndexOptInfo:
retval = _copyIndexOptInfo(from);
break;
+ case T_InnerIndexscanInfo:
+ retval = _copyInnerIndexscanInfo(from);
+ break;
/*
* VALUE NODES
diff --git a/src/backend/nodes/equalfuncs.c b/src/backend/nodes/equalfuncs.c
index 12781797c3d..3e0ea75d251 100644
--- a/src/backend/nodes/equalfuncs.c
+++ b/src/backend/nodes/equalfuncs.c
@@ -20,7 +20,7 @@
* Portions Copyright (c) 1994, Regents of the University of California
*
* IDENTIFICATION
- * $Header: /cvsroot/pgsql/src/backend/nodes/equalfuncs.c,v 1.166 2002/11/23 03:59:07 momjian Exp $
+ * $Header: /cvsroot/pgsql/src/backend/nodes/equalfuncs.c,v 1.167 2002/11/24 21:52:13 tgl Exp $
*
*-------------------------------------------------------------------------
*/
@@ -429,10 +429,6 @@ _equalIndexPath(IndexPath *a, IndexPath *b)
return false;
if (a->indexscandir != b->indexscandir)
return false;
- if (!equali(a->joinrelids, b->joinrelids))
- return false;
- if (a->alljoinquals != b->alljoinquals)
- return false;
/*
* Skip 'rows' because of possibility of floating-point roundoff
@@ -548,13 +544,11 @@ _equalRestrictInfo(RestrictInfo *a, RestrictInfo *b)
return false;
/*
- * We ignore eval_cost, this_selec, left/right_pathkey, and
- * left/right_bucketsize, since they may not be set yet, and should be
- * derivable from the clause anyway. Probably it's not really
- * necessary to compare any of these remaining fields ...
+ * We ignore subclauseindices, eval_cost, this_selec, left/right_pathkey,
+ * and left/right_bucketsize, since they may not be set yet, and should be
+ * derivable from the clause anyway. Probably it's not really necessary
+ * to compare any of these remaining fields ...
*/
- if (!equal(a->subclauseindices, b->subclauseindices))
- return false;
if (a->mergejoinoperator != b->mergejoinoperator)
return false;
if (a->left_sortop != b->left_sortop)
@@ -576,6 +570,18 @@ _equalJoinInfo(JoinInfo *a, JoinInfo *b)
return true;
}
+static bool
+_equalInnerIndexscanInfo(InnerIndexscanInfo *a, InnerIndexscanInfo *b)
+{
+ if (!equali(a->other_relids, b->other_relids))
+ return false;
+ if (a->isouterjoin != b->isouterjoin)
+ return false;
+ if (!equal(a->best_innerpath, b->best_innerpath))
+ return false;
+ return true;
+}
+
/*
* Stuff from parsenodes.h
*/
@@ -2120,6 +2126,9 @@ equal(void *a, void *b)
case T_JoinInfo:
retval = _equalJoinInfo(a, b);
break;
+ case T_InnerIndexscanInfo:
+ retval = _equalInnerIndexscanInfo(a, b);
+ break;
case T_TidPath:
retval = _equalTidPath(a, b);
break;
diff --git a/src/backend/nodes/list.c b/src/backend/nodes/list.c
index 063212e25fa..6dc6001a0f2 100644
--- a/src/backend/nodes/list.c
+++ b/src/backend/nodes/list.c
@@ -8,7 +8,7 @@
*
*
* IDENTIFICATION
- * $Header: /cvsroot/pgsql/src/backend/nodes/list.c,v 1.41 2002/06/20 20:29:29 momjian Exp $
+ * $Header: /cvsroot/pgsql/src/backend/nodes/list.c,v 1.42 2002/11/24 21:52:13 tgl Exp $
*
* NOTES
* XXX a few of the following functions are duplicated to handle
@@ -373,6 +373,46 @@ set_unioni(List *l1, List *l2)
}
/*
+ * Generate the intersection of two lists,
+ * ie, all members of both l1 and l2.
+ *
+ * NOTE: if there are duplicates in l1 they will still be duplicate in the
+ * result; but duplicates in l2 are discarded.
+ *
+ * The result is a fresh List, but it points to the same member nodes
+ * as were in the inputs.
+ */
+#ifdef NOT_USED
+List *
+set_intersect(List *l1, List *l2)
+{
+ List *retval = NIL;
+ List *i;
+
+ foreach(i, l1)
+ {
+ if (member(lfirst(i), l2))
+ retval = lappend(retval, lfirst(i));
+ }
+ return retval;
+}
+#endif
+
+List *
+set_intersecti(List *l1, List *l2)
+{
+ List *retval = NIL;
+ List *i;
+
+ foreach(i, l1)
+ {
+ if (intMember(lfirsti(i), l2))
+ retval = lappendi(retval, lfirsti(i));
+ }
+ return retval;
+}
+
+/*
* member()
* nondestructive, returns t iff l1 is a member of the list l2
*/
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index 2d1f2236c9b..8df0783fb89 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -5,7 +5,7 @@
* Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
* Portions Copyright (c) 1994, Regents of the University of California
*
- * $Header: /cvsroot/pgsql/src/backend/nodes/outfuncs.c,v 1.180 2002/11/15 02:50:07 momjian Exp $
+ * $Header: /cvsroot/pgsql/src/backend/nodes/outfuncs.c,v 1.181 2002/11/24 21:52:13 tgl Exp $
*
* NOTES
* Every (plan) node in POSTGRES has an associated "out" routine which
@@ -1067,12 +1067,8 @@ _outIndexPath(StringInfo str, IndexPath *node)
appendStringInfo(str, " :indexqual ");
_outNode(str, node->indexqual);
- appendStringInfo(str, " :indexscandir %d :joinrelids ",
- (int) node->indexscandir);
- _outIntList(str, node->joinrelids);
-
- appendStringInfo(str, " :alljoinquals %s :rows %.2f ",
- booltostr(node->alljoinquals),
+ appendStringInfo(str, " :indexscandir %d :rows %.2f ",
+ (int) node->indexscandir,
node->rows);
}
diff --git a/src/backend/nodes/readfuncs.c b/src/backend/nodes/readfuncs.c
index 9b2198ec5a5..43fe5bbd35f 100644
--- a/src/backend/nodes/readfuncs.c
+++ b/src/backend/nodes/readfuncs.c
@@ -8,7 +8,7 @@
*
*
* IDENTIFICATION
- * $Header: /cvsroot/pgsql/src/backend/nodes/readfuncs.c,v 1.137 2002/11/15 02:50:07 momjian Exp $
+ * $Header: /cvsroot/pgsql/src/backend/nodes/readfuncs.c,v 1.138 2002/11/24 21:52:13 tgl Exp $
*
* NOTES
* Most of the read functions for plan nodes are tested. (In fact, they
@@ -1824,13 +1824,6 @@ _readIndexPath(void)
token = pg_strtok(&length); /* now read it */
local_node->indexscandir = (ScanDirection) atoi(token);
- token = pg_strtok(&length); /* get :joinrelids */
- local_node->joinrelids = toIntList(nodeRead(true));
-
- token = pg_strtok(&length); /* get :alljoinquals */
- token = pg_strtok(&length); /* now read it */
- local_node->alljoinquals = strtobool(token);
-
token = pg_strtok(&length); /* get :rows */
token = pg_strtok(&length); /* now read it */
local_node->rows = atof(token);
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 2dab5e54cdd..ae5db3634ff 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -9,7 +9,7 @@
*
*
* IDENTIFICATION
- * $Header: /cvsroot/pgsql/src/backend/optimizer/path/indxpath.c,v 1.124 2002/11/01 19:33:09 tgl Exp $
+ * $Header: /cvsroot/pgsql/src/backend/optimizer/path/indxpath.c,v 1.125 2002/11/24 21:52:14 tgl Exp $
*
*-------------------------------------------------------------------------
*/
@@ -46,15 +46,11 @@
/*
* DoneMatchingIndexKeys() - MACRO
*
- * Determine whether we should continue matching index keys in a clause.
- * Depends on if there are more to match or if this is a functional index.
- * In the latter case we stop after the first match since there can
- * be only 1 key (i.e. the function's return value) and the attributes in
- * keys list represent the arguments to the function. -mer 3 Oct. 1991
+ * Formerly this looked at indexkeys, but that's the wrong thing for a
+ * functional index.
*/
-#define DoneMatchingIndexKeys(indexkeys, index) \
- (indexkeys[0] == 0 || \
- (index->indproc != InvalidOid))
+#define DoneMatchingIndexKeys(indexkeys, classes) \
+ (classes[0] == InvalidOid)
#define is_indexable_operator(clause,opclass,indexkey_on_left) \
(indexable_operator(clause,opclass,indexkey_on_left) != InvalidOid)
@@ -68,28 +64,25 @@ static List *match_index_orclause(RelOptInfo *rel, IndexOptInfo *index,
static bool match_or_subclause_to_indexkey(RelOptInfo *rel,
IndexOptInfo *index,
Expr *clause);
-static List *group_clauses_by_indexkey(RelOptInfo *rel, IndexOptInfo *index,
- int *indexkeys, Oid *classes,
- List *restrictinfo_list);
-static List *group_clauses_by_ikey_for_joins(RelOptInfo *rel,
+static List *group_clauses_by_indexkey(RelOptInfo *rel, IndexOptInfo *index);
+static List *group_clauses_by_indexkey_for_join(RelOptInfo *rel,
IndexOptInfo *index,
- int *indexkeys, Oid *classes,
- List *join_cinfo_list,
- List *restr_cinfo_list);
+ Relids outer_relids,
+ bool isouterjoin);
static bool match_clause_to_indexkey(RelOptInfo *rel, IndexOptInfo *index,
- int indexkey, Oid opclass,
- Expr *clause, bool join);
+ int indexkey, Oid opclass, Expr *clause);
+static bool match_join_clause_to_indexkey(RelOptInfo *rel, IndexOptInfo *index,
+ int indexkey, Oid opclass, Expr *clause);
static bool pred_test(List *predicate_list, List *restrictinfo_list,
List *joininfo_list, int relvarno);
static bool pred_test_restrict_list(Expr *predicate, List *restrictinfo_list);
static bool pred_test_recurse_clause(Expr *predicate, Node *clause);
static bool pred_test_recurse_pred(Expr *predicate, Node *clause);
static bool pred_test_simple_clause(Expr *predicate, Node *clause);
-static void indexable_joinclauses(RelOptInfo *rel, IndexOptInfo *index,
- List *joininfo_list, List *restrictinfo_list,
- List **clausegroups, List **outerrelids);
-static List *index_innerjoin(Query *root, RelOptInfo *rel, IndexOptInfo *index,
- List *clausegroup_list, List *outerrelids_list);
+static Relids indexable_outerrelids(RelOptInfo *rel, IndexOptInfo *index);
+static Path *make_innerjoin_index_path(Query *root,
+ RelOptInfo *rel, IndexOptInfo *index,
+ List *clausegroup);
static bool match_index_to_operand(int indexkey, Var *operand,
RelOptInfo *rel, IndexOptInfo *index);
static bool function_index_operand(Expr *funcOpnd, RelOptInfo *rel,
@@ -108,7 +101,6 @@ static Const *string_to_const(const char *str, Oid datatype);
* create_index_paths()
* Generate all interesting index paths for the given relation.
* Candidate paths are added to the rel's pathlist (using add_path).
- * Additional IndexPath nodes may also be added to rel's innerjoin list.
*
* 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,
@@ -123,12 +115,14 @@ static Const *string_to_const(const char *str, Oid datatype);
* in its join clauses. In that context, values for the other rels'
* attributes are available and fixed during any one scan of the indexpath.
*
- * An IndexPath is generated and submitted to add_path() for each index
- * this routine deems potentially interesting for the current query.
- * An innerjoin path is also generated for each interesting combination of
- * outer join relations. The innerjoin paths are *not* passed to add_path(),
- * but are appended to the "innerjoin" list of the relation for later
- * consideration in nested-loop joins.
+ * An IndexPath is generated and submitted to add_path() for each plain index
+ * scan this routine deems potentially interesting for the current query.
+ *
+ * We also determine the set of other relids that participate in join
+ * clauses that could be used with each index. The actually best innerjoin
+ * path will be generated for each outer relation later on, but knowing the
+ * set of potential otherrels allows us to identify equivalent outer relations
+ * and avoid repeated computation.
*
* 'rel' is the relation for which we want to generate index paths
*/
@@ -137,6 +131,7 @@ create_index_paths(Query *root, RelOptInfo *rel)
{
List *restrictinfo_list = rel->baserestrictinfo;
List *joininfo_list = rel->joininfo;
+ Relids all_join_outerrelids = NIL;
List *ilist;
foreach(ilist, rel->indexlist)
@@ -146,8 +141,7 @@ create_index_paths(Query *root, RelOptInfo *rel)
List *index_pathkeys;
List *useful_pathkeys;
bool index_is_ordered;
- List *joinclausegroups;
- List *joinouterrelids;
+ Relids join_outerrelids;
/*
* If this is a partial index, we can only use it if it passes the
@@ -178,11 +172,7 @@ create_index_paths(Query *root, RelOptInfo *rel)
/*
* 2. Match the index against non-'or' restriction clauses.
*/
- restrictclauses = group_clauses_by_indexkey(rel,
- index,
- index->indexkeys,
- index->classlist,
- restrictinfo_list);
+ restrictclauses = group_clauses_by_indexkey(rel, index);
/*
* 3. Compute pathkeys describing index's ordering, if any, then
@@ -234,26 +224,19 @@ create_index_paths(Query *root, RelOptInfo *rel)
}
/*
- * 6. Create an innerjoin index path for each combination of other
- * rels used in available join clauses. These paths will be
- * considered as the inner side of nestloop joins against those
- * sets of other rels. indexable_joinclauses() finds sets of
- * clauses that can be used with each combination of outer rels,
- * and index_innerjoin builds the paths themselves. We add the
- * paths to the rel's innerjoin list, NOT to the result list.
+ * 6. Examine join clauses to see which ones are potentially
+ * usable with this index, and generate a list of all other relids
+ * that participate in such join clauses. We'll use this list later
+ * to recognize outer rels that are equivalent for joining purposes.
+ * We compute both per-index and overall-for-relation lists.
*/
- indexable_joinclauses(rel, index,
- joininfo_list, restrictinfo_list,
- &joinclausegroups,
- &joinouterrelids);
- if (joinclausegroups != NIL)
- {
- rel->innerjoin = nconc(rel->innerjoin,
- index_innerjoin(root, rel, index,
- joinclausegroups,
- joinouterrelids));
- }
+ join_outerrelids = indexable_outerrelids(rel, index);
+ index->outer_relids = join_outerrelids;
+ all_join_outerrelids = set_unioni(all_join_outerrelids,
+ join_outerrelids);
}
+
+ rel->index_outer_relids = all_join_outerrelids;
}
@@ -397,14 +380,14 @@ match_or_subclause_to_indexkey(RelOptInfo *rel,
foreach(item, clause->args)
{
if (match_clause_to_indexkey(rel, index, indexkey, opclass,
- lfirst(item), false))
+ lfirst(item)))
return true;
}
return false;
}
else
return match_clause_to_indexkey(rel, index, indexkey, opclass,
- clause, false);
+ clause);
}
/*----------
@@ -466,13 +449,13 @@ extract_or_indexqual_conditions(RelOptInfo *rel,
if (match_clause_to_indexkey(rel, index,
curIndxKey, curClass,
- subsubclause, false))
+ subsubclause))
clausegroup = lappend(clausegroup, subsubclause);
}
}
else if (match_clause_to_indexkey(rel, index,
curIndxKey, curClass,
- orsubclause, false))
+ orsubclause))
clausegroup = makeList1(orsubclause);
/*
@@ -487,7 +470,7 @@ extract_or_indexqual_conditions(RelOptInfo *rel,
if (match_clause_to_indexkey(rel, index,
curIndxKey, curClass,
- rinfo->clause, false))
+ rinfo->clause))
clausegroup = lappend(clausegroup, rinfo->clause);
}
}
@@ -503,7 +486,8 @@ extract_or_indexqual_conditions(RelOptInfo *rel,
indexkeys++;
classes++;
- } while (!DoneMatchingIndexKeys(indexkeys, index));
+
+ } while (!DoneMatchingIndexKeys(indexkeys, classes));
if (quals == NIL)
elog(ERROR, "extract_or_indexqual_conditions: no matching clause");
@@ -523,15 +507,12 @@ extract_or_indexqual_conditions(RelOptInfo *rel,
*
* 'rel' is the node of the relation itself.
* 'index' is a index on 'rel'.
- * 'indexkeys' are the index keys to be matched.
- * 'classes' are the classes of the index operators on those keys.
- * 'restrictinfo_list' is the list of available restriction clauses for 'rel'.
*
* Returns a list of all the RestrictInfo nodes for clauses that can be
* used with this index.
*
* The list is ordered by index key. (This is not depended on by any part
- * of the planner, as far as I can tell; but some parts of the executor
+ * 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_orderkeys() in the btree support.
* Perhaps that ought to be fixed someday --- tgl 7/00)
@@ -544,15 +525,14 @@ extract_or_indexqual_conditions(RelOptInfo *rel,
* clauses matching column C, because the executor couldn't use them anyway.
*/
static List *
-group_clauses_by_indexkey(RelOptInfo *rel,
- IndexOptInfo *index,
- int *indexkeys,
- Oid *classes,
- List *restrictinfo_list)
+group_clauses_by_indexkey(RelOptInfo *rel, IndexOptInfo *index)
{
List *clausegroup_list = NIL;
+ List *restrictinfo_list = rel->baserestrictinfo;
+ int *indexkeys = index->indexkeys;
+ Oid *classes = index->classlist;
- if (restrictinfo_list == NIL || indexkeys[0] == 0)
+ if (restrictinfo_list == NIL)
return NIL;
do
@@ -560,18 +540,17 @@ group_clauses_by_indexkey(RelOptInfo *rel,
int curIndxKey = indexkeys[0];
Oid curClass = classes[0];
List *clausegroup = NIL;
- List *curCinfo;
+ List *i;
- foreach(curCinfo, restrictinfo_list)
+ foreach(i, restrictinfo_list)
{
- RestrictInfo *rinfo = (RestrictInfo *) lfirst(curCinfo);
+ RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
if (match_clause_to_indexkey(rel,
index,
curIndxKey,
curClass,
- rinfo->clause,
- false))
+ rinfo->clause))
clausegroup = lappend(clausegroup, rinfo);
}
@@ -587,71 +566,84 @@ group_clauses_by_indexkey(RelOptInfo *rel,
indexkeys++;
classes++;
- } while (!DoneMatchingIndexKeys(indexkeys, index));
+ } while (!DoneMatchingIndexKeys(indexkeys, classes));
/* clausegroup_list holds all matched clauses ordered by indexkeys */
return clausegroup_list;
}
/*
- * group_clauses_by_ikey_for_joins
- * Generates a list of join clauses that can be used with an index
+ * group_clauses_by_indexkey_for_join
+ * Generates a list of clauses that can be used with an index
* to scan the inner side of a nestloop join.
*
* This is much like group_clauses_by_indexkey(), but we consider both
- * join and restriction clauses. For each indexkey in the index, we
- * accept both join and restriction clauses that match it, since both
- * will make useful indexquals if the index is being used to scan the
- * inner side of a nestloop join. But there must be at least one matching
- * join clause, or we return NIL indicating that this index isn't useful
- * for nestloop joining.
+ * 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.)
*/
static List *
-group_clauses_by_ikey_for_joins(RelOptInfo *rel,
- IndexOptInfo *index,
- int *indexkeys,
- Oid *classes,
- List *join_cinfo_list,
- List *restr_cinfo_list)
+group_clauses_by_indexkey_for_join(RelOptInfo *rel, IndexOptInfo *index,
+ Relids outer_relids, bool isouterjoin)
{
List *clausegroup_list = NIL;
bool jfound = false;
-
- if (join_cinfo_list == NIL || indexkeys[0] == 0)
- return NIL;
+ int *indexkeys = index->indexkeys;
+ Oid *classes = index->classlist;
do
{
int curIndxKey = indexkeys[0];
Oid curClass = classes[0];
List *clausegroup = NIL;
- List *curCinfo;
+ List *i;
- foreach(curCinfo, join_cinfo_list)
+ /* Look for joinclauses that are usable with given outer_relids */
+ foreach(i, rel->joininfo)
{
- RestrictInfo *rinfo = (RestrictInfo *) lfirst(curCinfo);
+ JoinInfo *joininfo = (JoinInfo *) lfirst(i);
+ List *j;
- if (match_clause_to_indexkey(rel,
- index,
- curIndxKey,
- curClass,
- rinfo->clause,
- true))
+ if (!is_subseti(joininfo->unjoined_relids, outer_relids))
+ continue;
+
+ foreach(j, joininfo->jinfo_restrictinfo)
{
- clausegroup = lappend(clausegroup, rinfo);
- jfound = true;
+ RestrictInfo *rinfo = (RestrictInfo *) lfirst(j);
+
+ /* Can't use pushed-down clauses in outer join */
+ if (isouterjoin && rinfo->ispusheddown)
+ continue;
+
+ if (match_join_clause_to_indexkey(rel,
+ index,
+ curIndxKey,
+ curClass,
+ rinfo->clause))
+ {
+ clausegroup = lappend(clausegroup, rinfo);
+ jfound = true;
+ }
}
}
- foreach(curCinfo, restr_cinfo_list)
+
+ /* We can also use plain restriction clauses for the rel */
+ foreach(i, rel->baserestrictinfo)
{
- RestrictInfo *rinfo = (RestrictInfo *) lfirst(curCinfo);
+ RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
+
+ /* Can't use pushed-down clauses in outer join */
+ if (isouterjoin && rinfo->ispusheddown)
+ continue;
if (match_clause_to_indexkey(rel,
index,
curIndxKey,
curClass,
- rinfo->clause,
- false))
+ rinfo->clause))
clausegroup = lappend(clausegroup, rinfo);
}
@@ -667,11 +659,10 @@ group_clauses_by_ikey_for_joins(RelOptInfo *rel,
indexkeys++;
classes++;
- } while (!DoneMatchingIndexKeys(indexkeys, index));
+ } while (!DoneMatchingIndexKeys(indexkeys, classes));
/*
- * if no join clause was matched then there ain't clauses for joins at
- * all.
+ * if no join clause was matched then forget it, per comments above.
*/
if (!jfound)
{
@@ -686,16 +677,12 @@ group_clauses_by_ikey_for_joins(RelOptInfo *rel,
/*
* match_clause_to_indexkey()
- * Determines whether a restriction or join clause matches
- * a key of an index.
+ * Determines whether a restriction clause matches a key of an index.
*
* To match, the clause:
*
- * (1a) for a restriction clause: must be in the form (indexkey op const)
- * or (const op indexkey), or
- * (1b) for a join clause: 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
+ * (1) must be in the form (indexkey op const) or (const op indexkey);
+ * and
* (2) must contain an operator which is in the same class as the index
* operator for this key, or is a "special" operator as recognized
* by match_special_index_operator().
@@ -706,18 +693,11 @@ group_clauses_by_ikey_for_joins(RelOptInfo *rel,
* We do not actually do the commuting here, but we check whether a
* suitable commutator operator is available.
*
- * Note that in the join case, 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.
- *
* 'rel' is the relation of interest.
* 'index' is an index on 'rel'.
* 'indexkey' is a key of 'index'.
* 'opclass' is the corresponding operator class.
* 'clause' is the clause to be tested.
- * 'join' is true if we are considering this clause for joins.
*
* Returns true if the clause can be used with this index key.
*
@@ -729,8 +709,7 @@ match_clause_to_indexkey(RelOptInfo *rel,
IndexOptInfo *index,
int indexkey,
Oid opclass,
- Expr *clause,
- bool join)
+ Expr *clause)
{
Var *leftop,
*rightop;
@@ -743,75 +722,124 @@ match_clause_to_indexkey(RelOptInfo *rel,
if (!leftop || !rightop)
return false;
- if (!join)
+ /*
+ * Check for clauses of the form:
+ * (indexkey operator constant) or (constant operator indexkey).
+ * Anything that is a "pseudo constant" expression will do.
+ */
+ if (match_index_to_operand(indexkey, leftop, rel, index) &&
+ is_pseudo_constant_clause((Node *) rightop))
{
+ if (is_indexable_operator(clause, opclass, true))
+ return true;
+
/*
- * Not considering joins, so check for clauses of the form:
- * (indexkey operator constant) or (constant operator indexkey).
- * Anything that is a "pseudo constant" expression will do.
+ * If we didn't find a member of the index's opclass, see
+ * whether it is a "special" indexable operator.
*/
+ if (match_special_index_operator(clause, opclass, true))
+ return true;
+ return false;
+ }
- if (match_index_to_operand(indexkey, leftop, rel, index) &&
- is_pseudo_constant_clause((Node *) rightop))
- {
- if (is_indexable_operator(clause, opclass, true))
- return true;
+ if (match_index_to_operand(indexkey, rightop, rel, index) &&
+ is_pseudo_constant_clause((Node *) leftop))
+ {
+ if (is_indexable_operator(clause, opclass, false))
+ return true;
- /*
- * If we didn't find a member of the index's opclass, see
- * whether it is a "special" indexable operator.
- */
- if (match_special_index_operator(clause, opclass, true))
- return true;
- return false;
- }
- if (match_index_to_operand(indexkey, rightop, rel, index) &&
- is_pseudo_constant_clause((Node *) leftop))
- {
- if (is_indexable_operator(clause, opclass, false))
- return true;
+ /*
+ * If we didn't find a member of the index's opclass, see
+ * whether it is a "special" indexable operator.
+ */
+ if (match_special_index_operator(clause, opclass, false))
+ return true;
+ return false;
+ }
- /*
- * If we didn't find a member of the index's opclass, see
- * whether it is a "special" indexable operator.
- */
- if (match_special_index_operator(clause, opclass, false))
- return true;
- return false;
- }
+ return false;
+}
+
+/*
+ * match_join_clause_to_indexkey()
+ * Determines whether a join clause matches a key 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 key, or is a "special" operator as recognized
+ * by match_special_index_operator().
+ *
+ * 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.
+ *
+ * 'rel' is the relation of interest.
+ * 'index' is an index on 'rel'.
+ * 'indexkey' is a key of 'index'.
+ * 'opclass' is the corresponding operator class.
+ * 'clause' is the clause to be tested.
+ *
+ * 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_indexkey(RelOptInfo *rel,
+ IndexOptInfo *index,
+ int indexkey,
+ Oid opclass,
+ Expr *clause)
+{
+ Var *leftop,
+ *rightop;
+
+ /* Clause must be a binary opclause. */
+ if (!is_opclause((Node *) 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(indexkey, leftop, rel, index))
+ {
+ List *othervarnos = pull_varnos((Node *) rightop);
+ bool isIndexable;
+
+ isIndexable =
+ !intMember(lfirsti(rel->relids), othervarnos) &&
+ !contain_volatile_functions((Node *) rightop) &&
+ is_indexable_operator(clause, opclass, true);
+ freeList(othervarnos);
+ return isIndexable;
}
- else
+
+ if (match_index_to_operand(indexkey, rightop, rel, index))
{
- /*
- * 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(indexkey, leftop, rel, index))
- {
- List *othervarnos = pull_varnos((Node *) rightop);
- bool isIndexable;
-
- isIndexable =
- !intMember(lfirsti(rel->relids), othervarnos) &&
- !contain_volatile_functions((Node *) rightop) &&
- is_indexable_operator(clause, opclass, true);
- freeList(othervarnos);
- return isIndexable;
- }
- else if (match_index_to_operand(indexkey, rightop, rel, index))
- {
- List *othervarnos = pull_varnos((Node *) leftop);
- bool isIndexable;
-
- isIndexable =
- !intMember(lfirsti(rel->relids), othervarnos) &&
- !contain_volatile_functions((Node *) leftop) &&
- is_indexable_operator(clause, opclass, false);
- freeList(othervarnos);
- return isIndexable;
- }
+ List *othervarnos = pull_varnos((Node *) leftop);
+ bool isIndexable;
+
+ isIndexable =
+ !intMember(lfirsti(rel->relids), othervarnos) &&
+ !contain_volatile_functions((Node *) leftop) &&
+ is_indexable_operator(clause, opclass, false);
+ freeList(othervarnos);
+ return isIndexable;
}
return false;
@@ -1267,164 +1295,288 @@ pred_test_simple_clause(Expr *predicate, Node *clause)
****************************************************************************/
/*
- * indexable_joinclauses
- * Finds all groups of join clauses from among 'joininfo_list' that can
- * be used in conjunction with 'index' for the inner scan of a nestjoin.
- *
- * Each clause group comes from a single joininfo node plus the current
- * rel's restrictinfo list. Therefore, every clause in the group references
- * the current rel plus the same set of other rels (except for the restrict
- * clauses, which only reference the current rel). Therefore, this set
- * of clauses could be used as an indexqual if the relation is scanned
- * as the inner side of a nestloop join when the outer side contains
- * (at least) all those "other rels".
- *
- * XXX Actually, given that we are considering a join that requires an
- * outer rel set (A,B,C), we should use all qual clauses that reference
- * any subset of these rels, not just the full set or none. This is
- * doable with a doubly nested loop over joininfo_list; is it worth it?
- *
- * Returns two parallel lists of the same length: the clause groups,
- * and the required outer rel set for each one.
+ * indexable_outerrelids
+ * Finds all other relids that participate in any indexable join clause
+ * for the specified index. Returns a list of relids.
*
* 'rel' is the relation for which 'index' is defined
- * 'joininfo_list' is the list of JoinInfo nodes for 'rel'
- * 'restrictinfo_list' is the list of restriction clauses for 'rel'
- * '*clausegroups' receives a list of clause sublists
- * '*outerrelids' receives a list of relid lists
*/
-static void
-indexable_joinclauses(RelOptInfo *rel, IndexOptInfo *index,
- List *joininfo_list, List *restrictinfo_list,
- List **clausegroups, List **outerrelids)
+static Relids
+indexable_outerrelids(RelOptInfo *rel, IndexOptInfo *index)
{
- List *cg_list = NIL;
- List *relid_list = NIL;
+ Relids outer_relids = NIL;
List *i;
- foreach(i, joininfo_list)
+ foreach(i, rel->joininfo)
{
JoinInfo *joininfo = (JoinInfo *) lfirst(i);
- List *clausegroup;
+ bool match_found = false;
+ List *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)
+ {
+ RestrictInfo *rinfo = (RestrictInfo *) lfirst(j);
+ Expr *clause = rinfo->clause;
+ int *indexkeys = index->indexkeys;
+ Oid *classes = index->classlist;
+
+ do
+ {
+ int curIndxKey = indexkeys[0];
+ Oid curClass = classes[0];
+
+ if (match_join_clause_to_indexkey(rel,
+ index,
+ curIndxKey,
+ curClass,
+ clause))
+ {
+ match_found = true;
+ break;
+ }
+
+ indexkeys++;
+ classes++;
- clausegroup = group_clauses_by_ikey_for_joins(rel,
- index,
- index->indexkeys,
- index->classlist,
- joininfo->jinfo_restrictinfo,
- restrictinfo_list);
+ } while (!DoneMatchingIndexKeys(indexkeys, classes));
- if (clausegroup != NIL)
+ if (match_found)
+ break;
+ }
+
+ if (match_found)
{
- cg_list = lappend(cg_list, clausegroup);
- relid_list = lappend(relid_list, joininfo->unjoined_relids);
+ outer_relids = set_unioni(outer_relids,
+ joininfo->unjoined_relids);
}
}
- *clausegroups = cg_list;
- *outerrelids = relid_list;
+ return outer_relids;
}
-/****************************************************************************
- * ---- PATH CREATION UTILITIES ----
- ****************************************************************************/
-
/*
- * index_innerjoin
- * Creates index path nodes corresponding to paths to be used as inner
- * relations in nestloop joins.
- *
- * 'rel' is the relation for which 'index' is defined
- * 'clausegroup_list' is a list of lists of restrictinfo nodes which can use
- * 'index'. Each sublist refers to the same set of outer rels.
- * 'outerrelids_list' is a list of the required outer rels for each sublist
- * of join clauses.
+ * best_inner_indexscan
+ * Finds the best available inner indexscan for a nestloop join
+ * with the given rel on the inside and the given outer_relids outside.
+ * May return NULL if there are no possible inner indexscans.
*
- * Returns a list of index pathnodes.
+ * We ignore ordering considerations (since a nestloop's inner scan's order
+ * is uninteresting). Also, we consider only total cost when deciding which
+ * of two possible paths is better --- this assumes that all indexpaths have
+ * negligible startup cost. (True today, but someday we might have to think
+ * harder.) Therefore, there is only one dimension of comparison and so it's
+ * sufficient to return a single "best" path.
*/
-static List *
-index_innerjoin(Query *root, RelOptInfo *rel, IndexOptInfo *index,
- List *clausegroup_list, List *outerrelids_list)
+Path *
+best_inner_indexscan(Query *root, RelOptInfo *rel,
+ Relids outer_relids, JoinType jointype)
{
- List *path_list = NIL;
- List *i;
+ Path *cheapest = NULL;
+ bool isouterjoin;
+ List *ilist;
+ List *jlist;
+ InnerIndexscanInfo *info;
- foreach(i, clausegroup_list)
+ /*
+ * Nestloop only supports inner and left joins.
+ */
+ switch (jointype)
{
- List *clausegroup = lfirst(i);
- IndexPath *pathnode = makeNode(IndexPath);
- List *indexquals = NIL;
- bool alljoinquals = true;
- List *temp;
-
- /* XXX this code ought to be merged with create_index_path? */
-
- pathnode->path.pathtype = T_IndexScan;
- pathnode->path.parent = rel;
+ case JOIN_INNER:
+ isouterjoin = false;
+ break;
+ case JOIN_LEFT:
+ isouterjoin = true;
+ break;
+ default:
+ return NULL;
+ }
+ /*
+ * If there are no indexable joinclauses for this rel, exit quickly.
+ * Otherwise, intersect the given outer_relids with index_outer_relids
+ * to find the set of outer relids actually relevant for this index.
+ * If there are none, again we can fail immediately.
+ */
+ if (!rel->index_outer_relids)
+ return NULL;
+ outer_relids = set_intersecti(rel->index_outer_relids, outer_relids);
+ if (!outer_relids)
+ return NULL;
+ /*
+ * 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 innerrel.)
+ */
+ foreach(jlist, rel->index_inner_paths)
+ {
+ info = (InnerIndexscanInfo *) lfirst(jlist);
+ if (sameseti(info->other_relids, outer_relids) &&
+ info->isouterjoin == isouterjoin)
+ {
+ freeList(outer_relids);
+ return info->best_innerpath;
+ }
+ }
+ /*
+ * 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.)
+ */
+ foreach(ilist, rel->indexlist)
+ {
+ IndexOptInfo *index = (IndexOptInfo *) lfirst(ilist);
+ Relids index_outer_relids;
+ Path *path = NULL;
+
+ /* skip quickly if index has no useful join clauses */
+ if (!index->outer_relids)
+ continue;
+ /* identify set of relevant outer relids for this index */
+ index_outer_relids = set_intersecti(index->outer_relids, outer_relids);
+ if (!index_outer_relids)
+ continue;
/*
- * 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.
+ * Look to see if we already computed the result for this index.
*/
- pathnode->path.pathkeys = NIL;
+ foreach(jlist, index->inner_paths)
+ {
+ info = (InnerIndexscanInfo *) lfirst(jlist);
+ if (sameseti(info->other_relids, index_outer_relids) &&
+ info->isouterjoin == isouterjoin)
+ {
+ path = info->best_innerpath;
+ freeList(index_outer_relids); /* not needed anymore */
+ break;
+ }
+ }
- /* extract bare indexqual clauses, check whether all from JOIN/ON */
- foreach(temp, clausegroup)
+ if (jlist == NIL) /* failed to find a match? */
{
- RestrictInfo *clause = (RestrictInfo *) lfirst(temp);
+ List *clausegroup;
+
+ /* find useful clauses for this index and outerjoin set */
+ clausegroup = group_clauses_by_indexkey_for_join(rel,
+ index,
+ index_outer_relids,
+ isouterjoin);
+ if (clausegroup)
+ {
+ /* remove duplicate and redundant clauses */
+ clausegroup = remove_redundant_join_clauses(root,
+ clausegroup,
+ jointype);
+ /* make the path */
+ path = make_innerjoin_index_path(root, rel, index,
+ clausegroup);
+ }
- indexquals = lappend(indexquals, clause->clause);
- if (clause->ispusheddown)
- alljoinquals = false;
+ /* 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);
}
- /* expand special operators to indexquals the executor can handle */
- indexquals = expand_indexqual_conditions(indexquals);
+ if (path != NULL &&
+ (cheapest == NULL ||
+ compare_path_costs(path, cheapest, TOTAL_COST) < 0))
+ cheapest = path;
+ }
- /*
- * Note that we are making a pathnode for a single-scan indexscan;
- * therefore, both indexinfo and indexqual should be
- * single-element lists.
- */
- pathnode->indexinfo = makeList1(index);
- pathnode->indexqual = makeList1(indexquals);
+ /* Cache the result --- whether positive or negative */
+ info = makeNode(InnerIndexscanInfo);
+ info->other_relids = outer_relids;
+ info->isouterjoin = isouterjoin;
+ info->best_innerpath = cheapest;
+ rel->index_inner_paths = lcons(info, rel->index_inner_paths);
- /* We don't actually care what order the index scans in ... */
- pathnode->indexscandir = NoMovementScanDirection;
+ return cheapest;
+}
- /* joinrelids saves the rels needed on the outer side of the join */
- pathnode->joinrelids = lfirst(outerrelids_list);
+/****************************************************************************
+ * ---- PATH CREATION UTILITIES ----
+ ****************************************************************************/
- pathnode->alljoinquals = alljoinquals;
+/*
+ * make_innerjoin_index_path
+ * Create an index path node for a path to be used as an inner
+ * relation in a nestloop join.
+ *
+ * 'rel' is the relation for which 'index' is defined
+ * 'clausegroup' is a list of restrictinfo nodes that can use 'index'
+ */
+static Path *
+make_innerjoin_index_path(Query *root,
+ RelOptInfo *rel, IndexOptInfo *index,
+ List *clausegroup)
+{
+ IndexPath *pathnode = makeNode(IndexPath);
+ List *indexquals;
- /*
- * 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 clausegroup
- * 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. (We can't just
- * nconc the two lists; then we might have some restriction
- * clauses appearing twice, which'd mislead
- * restrictlist_selectivity into double-counting their
- * selectivity.)
- */
- pathnode->rows = rel->tuples *
- restrictlist_selectivity(root,
- set_union(rel->baserestrictinfo,
- clausegroup),
- lfirsti(rel->relids));
- /* Like costsize.c, force estimate to be at least one row */
- if (pathnode->rows < 1.0)
- pathnode->rows = 1.0;
-
- cost_index(&pathnode->path, root, rel, index, indexquals, true);
-
- path_list = lappend(path_list, pathnode);
- outerrelids_list = lnext(outerrelids_list);
- }
- return path_list;
+ /* XXX this code ought to be merged with create_index_path? */
+
+ pathnode->path.pathtype = T_IndexScan;
+ pathnode->path.parent = rel;
+
+ /*
+ * 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.
+ */
+ pathnode->path.pathkeys = NIL;
+
+ /* Extract bare indexqual clauses from restrictinfos */
+ indexquals = get_actual_clauses(clausegroup);
+
+ /* expand special operators to indexquals the executor can handle */
+ indexquals = expand_indexqual_conditions(indexquals);
+
+ /*
+ * Note that we are making a pathnode for a single-scan indexscan;
+ * therefore, both indexinfo and indexqual should be single-element lists.
+ */
+ pathnode->indexinfo = makeList1(index);
+ pathnode->indexqual = makeList1(indexquals);
+
+ /* We don't actually care what order the index scans in ... */
+ pathnode->indexscandir = NoMovementScanDirection;
+
+ /*
+ * 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 clausegroup
+ * 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. (We can't just
+ * nconc the two lists; then we might have some restriction
+ * clauses appearing twice, which'd mislead
+ * restrictlist_selectivity into double-counting their
+ * selectivity.)
+ */
+ pathnode->rows = rel->tuples *
+ restrictlist_selectivity(root,
+ set_union(rel->baserestrictinfo,
+ clausegroup),
+ lfirsti(rel->relids));
+ /* Like costsize.c, force estimate to be at least one row */
+ if (pathnode->rows < 1.0)
+ pathnode->rows = 1.0;
+
+ cost_index(&pathnode->path, root, rel, index, indexquals, true);
+
+ return (Path *) pathnode;
}
/****************************************************************************
diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c
index 8e73bd2f419..ac5d4a72d45 100644
--- a/src/backend/optimizer/path/joinpath.c
+++ b/src/backend/optimizer/path/joinpath.c
@@ -8,7 +8,7 @@
*
*
* IDENTIFICATION
- * $Header: /cvsroot/pgsql/src/backend/optimizer/path/joinpath.c,v 1.71 2002/09/04 20:31:20 momjian Exp $
+ * $Header: /cvsroot/pgsql/src/backend/optimizer/path/joinpath.c,v 1.72 2002/11/24 21:52:14 tgl Exp $
*
*-------------------------------------------------------------------------
*/
@@ -42,8 +42,6 @@ static void match_unsorted_inner(Query *root, RelOptInfo *joinrel,
static void hash_inner_and_outer(Query *root, RelOptInfo *joinrel,
RelOptInfo *outerrel, RelOptInfo *innerrel,
List *restrictlist, JoinType jointype);
-static Path *best_innerjoin(List *join_paths, List *outer_relid,
- JoinType jointype);
static List *select_mergejoin_clauses(RelOptInfo *joinrel,
RelOptInfo *outerrel,
RelOptInfo *innerrel,
@@ -351,8 +349,8 @@ match_unsorted_outer(Query *root,
* Get the best innerjoin indexpath (if any) for this outer rel. It's
* the same for all outer paths.
*/
- bestinnerjoin = best_innerjoin(innerrel->innerjoin, outerrel->relids,
- jointype);
+ bestinnerjoin = best_inner_indexscan(root, innerrel,
+ outerrel->relids, jointype);
foreach(i, outerrel->pathlist)
{
@@ -813,69 +811,6 @@ hash_inner_and_outer(Query *root,
}
/*
- * best_innerjoin
- * Find the cheapest index path that has already been identified by
- * indexable_joinclauses() as being a possible inner path for the given
- * outer relation(s) in a nestloop join.
- *
- * We compare indexpaths on total_cost only, assuming that they will all have
- * zero or negligible startup_cost. We might have to think harder someday...
- *
- * 'join_paths' is a list of potential inner indexscan join paths
- * 'outer_relids' is the relid list of the outer join relation
- *
- * Returns the pathnode of the best path, or NULL if there's no
- * usable path.
- */
-static Path *
-best_innerjoin(List *join_paths, Relids outer_relids, JoinType jointype)
-{
- Path *cheapest = (Path *) NULL;
- bool isouterjoin;
- List *join_path;
-
- /*
- * Nestloop only supports inner and left joins.
- */
- switch (jointype)
- {
- case JOIN_INNER:
- isouterjoin = false;
- break;
- case JOIN_LEFT:
- isouterjoin = true;
- break;
- default:
- return NULL;
- }
-
- foreach(join_path, join_paths)
- {
- IndexPath *path = (IndexPath *) lfirst(join_path);
-
- Assert(IsA(path, IndexPath));
-
- /*
- * If processing an outer join, only use explicit join clauses in
- * the inner indexscan. For inner joins we need not be so picky.
- */
- if (isouterjoin && !path->alljoinquals)
- continue;
-
- /*
- * path->joinrelids is the set of base rels that must be part of
- * outer_relids in order to use this inner path, because those
- * rels are used in the index join quals of this inner path.
- */
- if (is_subseti(path->joinrelids, outer_relids) &&
- (cheapest == NULL ||
- compare_path_costs((Path *) path, cheapest, TOTAL_COST) < 0))
- cheapest = (Path *) path;
- }
- return cheapest;
-}
-
-/*
* select_mergejoin_clauses
* Select mergejoin clauses that are usable for a particular join.
* Returns a list of RestrictInfo nodes for those clauses.
diff --git a/src/backend/optimizer/path/orindxpath.c b/src/backend/optimizer/path/orindxpath.c
index f0c1a44196d..009afdff079 100644
--- a/src/backend/optimizer/path/orindxpath.c
+++ b/src/backend/optimizer/path/orindxpath.c
@@ -8,7 +8,7 @@
*
*
* IDENTIFICATION
- * $Header: /cvsroot/pgsql/src/backend/optimizer/path/orindxpath.c,v 1.47 2002/06/20 20:29:30 momjian Exp $
+ * $Header: /cvsroot/pgsql/src/backend/optimizer/path/orindxpath.c,v 1.48 2002/11/24 21:52:14 tgl Exp $
*
*-------------------------------------------------------------------------
*/
@@ -92,9 +92,6 @@ create_or_index_paths(Query *root, RelOptInfo *rel)
/* We don't actually care what order the index scans in. */
pathnode->indexscandir = NoMovementScanDirection;
- /* This isn't a nestloop innerjoin, so: */
- pathnode->joinrelids = NIL; /* no join clauses here */
- pathnode->alljoinquals = false;
pathnode->rows = rel->rows;
best_or_subclause_indices(root,
diff --git a/src/backend/optimizer/path/tidpath.c b/src/backend/optimizer/path/tidpath.c
index f8d4f79d4db..27fe9e281f3 100644
--- a/src/backend/optimizer/path/tidpath.c
+++ b/src/backend/optimizer/path/tidpath.c
@@ -9,7 +9,7 @@
*
*
* IDENTIFICATION
- * $Header: /cvsroot/pgsql/src/backend/optimizer/path/tidpath.c,v 1.11 2002/09/05 00:43:06 tgl Exp $
+ * $Header: /cvsroot/pgsql/src/backend/optimizer/path/tidpath.c,v 1.12 2002/11/24 21:52:14 tgl Exp $
*
*-------------------------------------------------------------------------
*/
@@ -25,7 +25,6 @@
#include "parser/parse_coerce.h"
#include "utils/lsyscache.h"
-static void create_tidscan_joinpaths(Query *root, RelOptInfo *rel);
static List *TidqualFromRestrictinfo(List *relids, List *restrictinfo);
static bool isEvaluable(int varno, Node *node);
static Node *TidequalClause(int varno, Expr *node);
@@ -237,44 +236,6 @@ TidqualFromRestrictinfo(List *relids, List *restrictinfo)
}
/*
- * create_tidscan_joinpaths
- * Create innerjoin paths if there are suitable joinclauses.
- *
- * XXX does this actually work?
- */
-static void
-create_tidscan_joinpaths(Query *root, RelOptInfo *rel)
-{
- List *rlst = NIL,
- *lst;
-
- foreach(lst, rel->joininfo)
- {
- JoinInfo *joininfo = (JoinInfo *) lfirst(lst);
- List *restinfo,
- *tideval;
-
- restinfo = joininfo->jinfo_restrictinfo;
- tideval = TidqualFromRestrictinfo(rel->relids, restinfo);
- if (length(tideval) == 1)
- {
- TidPath *pathnode = makeNode(TidPath);
-
- pathnode->path.pathtype = T_TidScan;
- pathnode->path.parent = rel;
- pathnode->path.pathkeys = NIL;
- pathnode->tideval = tideval;
- pathnode->unjoined_relids = joininfo->unjoined_relids;
-
- cost_tidscan(&pathnode->path, root, rel, tideval);
-
- rlst = lappend(rlst, pathnode);
- }
- }
- rel->innerjoin = nconc(rel->innerjoin, rlst);
-}
-
-/*
* create_tidscan_paths
* Creates paths corresponding to tid direct scans of the given rel.
* Candidate paths are added to the rel's pathlist (using add_path).
@@ -287,5 +248,4 @@ create_tidscan_paths(Query *root, RelOptInfo *rel)
if (tideval)
add_path(rel, (Path *) create_tidscan_path(root, rel, tideval));
- create_tidscan_joinpaths(root, rel);
}
diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c
index e43c52f6dfe..529ba712f41 100644
--- a/src/backend/optimizer/plan/initsplan.c
+++ b/src/backend/optimizer/plan/initsplan.c
@@ -8,7 +8,7 @@
*
*
* IDENTIFICATION
- * $Header: /cvsroot/pgsql/src/backend/optimizer/plan/initsplan.c,v 1.76 2002/11/19 23:21:58 tgl Exp $
+ * $Header: /cvsroot/pgsql/src/backend/optimizer/plan/initsplan.c,v 1.77 2002/11/24 21:52:14 tgl Exp $
*
*-------------------------------------------------------------------------
*/
@@ -577,15 +577,12 @@ distribute_qual_to_rels(Query *root, Node *clause,
* the relid list. Set additional RestrictInfo fields for
* joining.
*
- * We don't bother setting the merge/hashjoin info if we're not going
- * to need it. We do want to know about mergejoinable ops in any
- * potential equijoin clause (see later in this routine), and we
- * ignore enable_mergejoin if isouterjoin is true, because
- * mergejoin is the only implementation we have for full and right
- * outer joins.
+ * We don't bother setting the hashjoin info if we're not going
+ * to need it. We do want to know about mergejoinable ops in all
+ * cases, however, because we use mergejoinable ops for other
+ * purposes such as detecting redundant clauses.
*/
- if (enable_mergejoin || isouterjoin || can_be_equijoin)
- check_mergejoinable(restrictinfo);
+ check_mergejoinable(restrictinfo);
if (enable_hashjoin)
check_hashjoinable(restrictinfo);
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index 7dd0dce6891..e99435a6edf 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -8,7 +8,7 @@
*
*
* IDENTIFICATION
- * $Header: /cvsroot/pgsql/src/backend/optimizer/util/pathnode.c,v 1.79 2002/11/06 00:00:44 tgl Exp $
+ * $Header: /cvsroot/pgsql/src/backend/optimizer/util/pathnode.c,v 1.80 2002/11/24 21:52:14 tgl Exp $
*
*-------------------------------------------------------------------------
*/
@@ -354,12 +354,9 @@ create_index_path(Query *root,
pathnode->indexscandir = indexscandir;
/*
- * This routine is only used to generate "standalone" indexpaths, not
- * nestloop inner indexpaths. So joinrelids is always NIL and the
- * number of rows is the same as the parent rel's estimate.
+ * The number of rows is the same as the parent rel's estimate, since
+ * this isn't a join inner indexscan.
*/
- pathnode->joinrelids = NIL; /* no join clauses here */
- pathnode->alljoinquals = false;
pathnode->rows = rel->rows;
/*
diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.c
index 3aee668448d..15120fafcd8 100644
--- a/src/backend/optimizer/util/plancat.c
+++ b/src/backend/optimizer/util/plancat.c
@@ -9,7 +9,7 @@
*
*
* IDENTIFICATION
- * $Header: /cvsroot/pgsql/src/backend/optimizer/util/plancat.c,v 1.74 2002/09/04 20:31:22 momjian Exp $
+ * $Header: /cvsroot/pgsql/src/backend/optimizer/util/plancat.c,v 1.75 2002/11/24 21:52:14 tgl Exp $
*
*-------------------------------------------------------------------------
*/
@@ -172,6 +172,10 @@ find_secondary_indexes(Oid relationObjectId)
}
}
+ /* initialize cached join info to empty */
+ info->outer_relids = NIL;
+ info->inner_paths = NIL;
+
index_close(indexRelation);
indexinfos = lcons(info, indexinfos);
diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c
index a07a208ecff..b93816bd21b 100644
--- a/src/backend/optimizer/util/relnode.c
+++ b/src/backend/optimizer/util/relnode.c
@@ -8,7 +8,7 @@
*
*
* IDENTIFICATION
- * $Header: /cvsroot/pgsql/src/backend/optimizer/util/relnode.c,v 1.40 2002/10/12 22:24:49 tgl Exp $
+ * $Header: /cvsroot/pgsql/src/backend/optimizer/util/relnode.c,v 1.41 2002/11/24 21:52:14 tgl Exp $
*
*-------------------------------------------------------------------------
*/
@@ -17,8 +17,8 @@
#include "optimizer/cost.h"
#include "optimizer/joininfo.h"
#include "optimizer/pathnode.h"
-#include "optimizer/paths.h"
#include "optimizer/plancat.h"
+#include "optimizer/restrictinfo.h"
#include "optimizer/tlist.h"
#include "parser/parsetree.h"
@@ -152,7 +152,8 @@ make_base_rel(Query *root, int relid)
rel->baserestrictcost = 0;
rel->outerjoinset = NIL;
rel->joininfo = NIL;
- rel->innerjoin = NIL;
+ rel->index_outer_relids = NIL;
+ rel->index_inner_paths = NIL;
/* Check type of rtable entry */
switch (rte->rtekind)
@@ -365,7 +366,8 @@ build_join_rel(Query *root,
joinrel->baserestrictcost = 0;
joinrel->outerjoinset = NIL;
joinrel->joininfo = NIL;
- joinrel->innerjoin = NIL;
+ joinrel->index_outer_relids = NIL;
+ joinrel->index_inner_paths = NIL;
/* Is there a join RTE matching this join? */
joinrterel = find_other_rel_for_join(root, joinrelids);
@@ -529,9 +531,8 @@ build_joinrel_restrictlist(Query *root,
RelOptInfo *inner_rel,
JoinType jointype)
{
- List *result = NIL;
+ List *result;
List *rlist;
- List *item;
/*
* Collect all the clauses that syntactically belong at this level.
@@ -549,59 +550,8 @@ build_joinrel_restrictlist(Query *root,
* mergejoinable clause, it's possible that it is redundant with
* previous clauses (see optimizer/README for discussion). We detect
* that case and omit the redundant clause from the result list.
- *
- * We can detect redundant mergejoinable clauses very cheaply by using
- * their left and right pathkeys, which uniquely identify the sets of
- * equijoined variables in question. All the members of a pathkey set
- * that are in the left relation have already been forced to be equal;
- * likewise for those in the right relation. So, we need to have only
- * one clause that checks equality between any set member on the left
- * and any member on the right; by transitivity, all the rest are then
- * equal.
- *
- * Weird special case: if we have two clauses that seem redundant
- * except one is pushed down into an outer join and the other isn't,
- * then they're not really redundant, because one constrains the
- * joined rows after addition of null fill rows, and the other doesn't.
*/
- foreach(item, rlist)
- {
- RestrictInfo *rinfo = (RestrictInfo *) lfirst(item);
-
- /* eliminate duplicates */
- if (member(rinfo, result))
- continue;
-
- /* check for redundant merge clauses */
- if (rinfo->mergejoinoperator != InvalidOid)
- {
- bool redundant = false;
- List *olditem;
-
- cache_mergeclause_pathkeys(root, rinfo);
-
- foreach(olditem, result)
- {
- RestrictInfo *oldrinfo = (RestrictInfo *) lfirst(olditem);
-
- if (oldrinfo->mergejoinoperator != InvalidOid &&
- rinfo->left_pathkey == oldrinfo->left_pathkey &&
- rinfo->right_pathkey == oldrinfo->right_pathkey &&
- (rinfo->ispusheddown == oldrinfo->ispusheddown ||
- !IS_OUTER_JOIN(jointype)))
- {
- redundant = true;
- break;
- }
- }
-
- if (redundant)
- continue;
- }
-
- /* otherwise, add it to result list */
- result = lappend(result, rinfo);
- }
+ result = remove_redundant_join_clauses(root, rlist, jointype);
freeList(rlist);
diff --git a/src/backend/optimizer/util/restrictinfo.c b/src/backend/optimizer/util/restrictinfo.c
index c9f1e75e232..bc1fcc36464 100644
--- a/src/backend/optimizer/util/restrictinfo.c
+++ b/src/backend/optimizer/util/restrictinfo.c
@@ -8,21 +8,21 @@
*
*
* IDENTIFICATION
- * $Header: /cvsroot/pgsql/src/backend/optimizer/util/restrictinfo.c,v 1.14 2002/06/20 20:29:31 momjian Exp $
+ * $Header: /cvsroot/pgsql/src/backend/optimizer/util/restrictinfo.c,v 1.15 2002/11/24 21:52:14 tgl Exp $
*
*-------------------------------------------------------------------------
*/
#include "postgres.h"
-
#include "optimizer/clauses.h"
+#include "optimizer/paths.h"
#include "optimizer/restrictinfo.h"
+
/*
* restriction_is_or_clause
*
* Returns t iff the restrictinfo node contains an 'or' clause.
- *
*/
bool
restriction_is_or_clause(RestrictInfo *restrictinfo)
@@ -37,8 +37,7 @@ restriction_is_or_clause(RestrictInfo *restrictinfo)
/*
* get_actual_clauses
*
- * Returns a list containing the clauses from 'restrictinfo_list'.
- *
+ * Returns a list containing the bare clauses from 'restrictinfo_list'.
*/
List *
get_actual_clauses(List *restrictinfo_list)
@@ -80,3 +79,81 @@ get_actual_join_clauses(List *restrictinfo_list,
*joinquals = lappend(*joinquals, clause->clause);
}
}
+
+/*
+ * remove_redundant_join_clauses
+ *
+ * Given a list of RestrictInfo clauses that are to be applied in a join,
+ * remove any duplicate or redundant clauses.
+ *
+ * We must eliminate duplicates when forming the restrictlist for a joinrel,
+ * since we will see many of the same clauses arriving from both input
+ * relations. Also, if a clause is a mergejoinable clause, it's possible that
+ * it is redundant with previous clauses (see optimizer/README for
+ * discussion). We detect that case and omit the redundant clause from the
+ * result list.
+ *
+ * We can detect redundant mergejoinable clauses very cheaply by using their
+ * left and right pathkeys, which uniquely identify the sets of equijoined
+ * variables in question. All the members of a pathkey set that are in the
+ * left relation have already been forced to be equal; likewise for those in
+ * the right relation. So, we need to have only one clause that checks
+ * equality between any set member on the left and any member on the right;
+ * by transitivity, all the rest are then equal.
+ *
+ * Weird special case: if we have two clauses that seem redundant
+ * except one is pushed down into an outer join and the other isn't,
+ * then they're not really redundant, because one constrains the
+ * joined rows after addition of null fill rows, and the other doesn't.
+ *
+ * The result is a fresh List, but it points to the same member nodes
+ * as were in the input.
+ */
+List *
+remove_redundant_join_clauses(Query *root, List *restrictinfo_list,
+ JoinType jointype)
+{
+ List *result = NIL;
+ List *item;
+
+ foreach(item, restrictinfo_list)
+ {
+ RestrictInfo *rinfo = (RestrictInfo *) lfirst(item);
+
+ /* eliminate duplicates */
+ if (member(rinfo, result))
+ continue;
+
+ /* check for redundant merge clauses */
+ if (rinfo->mergejoinoperator != InvalidOid)
+ {
+ bool redundant = false;
+ List *olditem;
+
+ cache_mergeclause_pathkeys(root, rinfo);
+
+ foreach(olditem, result)
+ {
+ RestrictInfo *oldrinfo = (RestrictInfo *) lfirst(olditem);
+
+ if (oldrinfo->mergejoinoperator != InvalidOid &&
+ rinfo->left_pathkey == oldrinfo->left_pathkey &&
+ rinfo->right_pathkey == oldrinfo->right_pathkey &&
+ (rinfo->ispusheddown == oldrinfo->ispusheddown ||
+ !IS_OUTER_JOIN(jointype)))
+ {
+ redundant = true;
+ break;
+ }
+ }
+
+ if (redundant)
+ continue;
+ }
+
+ /* otherwise, add it to result list */
+ result = lappend(result, rinfo);
+ }
+
+ return result;
+}
diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h
index 112eac34680..d2b984de4f8 100644
--- a/src/include/nodes/nodes.h
+++ b/src/include/nodes/nodes.h
@@ -7,7 +7,7 @@
* Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
* Portions Copyright (c) 1994, Regents of the University of California
*
- * $Id: nodes.h,v 1.123 2002/11/15 02:50:10 momjian Exp $
+ * $Id: nodes.h,v 1.124 2002/11/24 21:52:14 tgl Exp $
*
*-------------------------------------------------------------------------
*/
@@ -87,6 +87,7 @@ typedef enum NodeTag
T_RestrictInfo,
T_JoinInfo,
T_IndexOptInfo,
+ T_InnerIndexscanInfo,
/*
* TAGS FOR EXECUTOR NODES (execnodes.h)
diff --git a/src/include/nodes/pg_list.h b/src/include/nodes/pg_list.h
index e1de57b53e9..9ef4fab957e 100644
--- a/src/include/nodes/pg_list.h
+++ b/src/include/nodes/pg_list.h
@@ -7,7 +7,7 @@
* Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
* Portions Copyright (c) 1994, Regents of the University of California
*
- * $Id: pg_list.h,v 1.29 2002/08/19 00:10:03 tgl Exp $
+ * $Id: pg_list.h,v 1.30 2002/11/24 21:52:15 tgl Exp $
*
*-------------------------------------------------------------------------
*/
@@ -141,6 +141,7 @@ extern List *set_differencei(List *list1, List *list2);
extern List *lreverse(List *l);
extern List *set_union(List *list1, List *list2);
extern List *set_unioni(List *list1, List *list2);
+extern List *set_intersecti(List *list1, List *list2);
extern bool equali(List *list1, List *list2);
extern bool sameseti(List *list1, List *list2);
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index 480fd9630be..d441e6bdc49 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -7,7 +7,7 @@
* Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
* Portions Copyright (c) 1994, Regents of the University of California
*
- * $Id: relation.h,v 1.68 2002/11/06 00:00:44 tgl Exp $
+ * $Id: relation.h,v 1.69 2002/11/24 21:52:15 tgl Exp $
*
*-------------------------------------------------------------------------
*/
@@ -129,9 +129,11 @@ typedef enum CostSelector
* syntactically within the join. Otherwise, unused.
* joininfo - List of JoinInfo nodes, containing info about each join
* clause in which this relation participates
- * innerjoin - List of Path nodes that represent indices that may be used
- * as inner paths of nestloop joins. This field is non-null
- * only for base rels, since join rels have no indices.
+ * index_outer_relids - only used for base rels; list of outer relids
+ * that participate in indexable joinclauses for this rel
+ * index_inner_paths - only used for base rels; list of InnerIndexscanInfo
+ * nodes showing best indexpaths for various subsets of
+ * index_outer_relids.
*
* Note: Keeping a restrictinfo list in the RelOptInfo is useful only for
* base rels, because for a join rel the set of clauses that are treated as
@@ -200,12 +202,17 @@ typedef struct RelOptInfo
Cost baserestrictcost; /* cost of evaluating the above */
Relids outerjoinset; /* integer list of base relids */
List *joininfo; /* JoinInfo structures */
- List *innerjoin; /* potential indexscans for nestloop joins */
+ /* cached info about inner indexscan paths for relation: */
+ Relids index_outer_relids; /* other relids in indexable join
+ * clauses */
+ List *index_inner_paths; /* InnerIndexscanInfo nodes */
/*
- * innerjoin indexscans are not in the main pathlist because they are
- * not usable except in specific join contexts; we have to test before
- * seeing whether they can be used.
+ * Inner indexscans are not in the main pathlist because they are
+ * not usable except in specific join contexts. We use the
+ * index_inner_paths list just to avoid recomputing the best inner
+ * indexscan repeatedly for similar outer relations. See comments
+ * for InnerIndexscanInfo.
*/
} RelOptInfo;
@@ -217,20 +224,6 @@ typedef struct RelOptInfo
* and indexes, but that created confusion without actually doing anything
* useful. So now we have a separate IndexOptInfo struct for indexes.
*
- * indexoid - OID of the index relation itself
- * pages - number of disk pages in index
- * tuples - number of index tuples in index
- * ncolumns - number of columns in index
- * nkeys - number of keys used by index (input columns)
- * classlist - List of PG_OPCLASS OIDs for the index
- * indexkeys - List of base-relation attribute numbers that are index keys
- * ordering - List of PG_OPERATOR OIDs which order the indexscan result
- * relam - the OID of the pg_am of the index
- * amcostestimate - OID of the relam's cost estimator
- * indproc - OID of the function if a functional index, else 0
- * indpred - index predicate if a partial index, else NULL
- * unique - true if index is unique
- *
* ncolumns and nkeys are the same except for a functional index,
* wherein ncolumns is 1 (the single function output) while nkeys
* is the number of table columns passed to the function. classlist[]
@@ -249,22 +242,26 @@ typedef struct IndexOptInfo
Oid indexoid; /* OID of the index relation */
/* statistics from pg_class */
- long pages;
- double tuples;
+ long pages; /* number of disk pages in index */
+ double tuples; /* number of index tuples in index */
/* index descriptor information */
int ncolumns; /* number of columns in index */
int nkeys; /* number of keys used by index */
- Oid *classlist; /* AM operator classes for columns */
+ Oid *classlist; /* OIDs of operator classes for columns */
int *indexkeys; /* column numbers of index's keys */
Oid *ordering; /* OIDs of sort operators for each column */
Oid relam; /* OID of the access method (in pg_am) */
RegProcedure amcostestimate; /* OID of the access method's cost fcn */
- Oid indproc; /* if a functional index */
- List *indpred; /* if a partial index */
- bool unique; /* if a unique index */
+ Oid indproc; /* OID of func if functional index, else 0 */
+ List *indpred; /* predicate if a partial index, else NIL */
+ bool unique; /* true if a unique index */
+
+ /* cached info about inner indexscan paths for index */
+ Relids outer_relids; /* other relids in usable join clauses */
+ List *inner_paths; /* List of InnerIndexscanInfo nodes */
} IndexOptInfo;
@@ -354,18 +351,9 @@ typedef struct Path
* NoMovementScanDirection for an indexscan, but the planner wants to
* distinguish ordered from unordered indexes for building pathkeys.)
*
- * 'joinrelids' is only used in IndexPaths that are constructed for use
- * as the inner path of a nestloop join. These paths have indexquals
- * that refer to values of other rels, so those other rels must be
- * included in the outer joinrel in order to make a usable join.
- *
- * 'alljoinquals' is also used only for inner paths of nestloop joins.
- * This flag is TRUE iff all the indexquals came from non-pushed-down
- * JOIN/ON conditions, which means the path is safe to use for an outer join.
- *
* 'rows' is the estimated result tuple count for the indexscan. This
* is the same as path.parent->rows for a simple indexscan, but it is
- * different for a nestloop inner path, because the additional indexquals
+ * different for a nestloop inner scan, because the additional indexquals
* coming from join clauses make the scan more selective than the parent
* rel's restrict clauses alone would do.
*----------
@@ -376,8 +364,6 @@ typedef struct IndexPath
List *indexinfo;
List *indexqual;
ScanDirection indexscandir;
- Relids joinrelids; /* other rels mentioned in indexqual */
- bool alljoinquals; /* all indexquals derived from JOIN conds? */
double rows; /* estimated number of result tuples */
} IndexPath;
@@ -616,4 +602,42 @@ typedef struct JoinInfo
List *jinfo_restrictinfo; /* relevant RestrictInfos */
} JoinInfo;
+/*
+ * Inner indexscan info.
+ *
+ * An inner indexscan is one that uses one or more joinclauses as index
+ * conditions (perhaps in addition to plain restriction clauses). So it
+ * can only be used as the inner path of a nestloop join where the outer
+ * relation includes all other relids appearing in those joinclauses.
+ * The set of usable joinclauses, and thus the best inner indexscan,
+ * thus varies depending on which outer relation we consider; so we have
+ * to recompute the best such path for every join. To avoid lots of
+ * redundant computation, we cache the results of such searches. For
+ * each index we compute the set of possible otherrelids (all relids
+ * appearing in joinquals that could become indexquals for this index).
+ * Two outer relations whose relids have the same intersection with this
+ * set will have the same set of available joinclauses and thus the same
+ * best inner indexscan for that index. Similarly, for each base relation,
+ * we form the union of the per-index otherrelids sets. Two outer relations
+ * with the same intersection with that set will have the same best overall
+ * inner indexscan for the base relation. We use lists of InnerIndexscanInfo
+ * nodes to cache the results of these searches at both the index and
+ * relation level.
+ *
+ * The search key also includes a bool showing whether the join being
+ * considered is an outer join. Since we constrain the join order for
+ * outer joins, I believe that this bool can only have one possible value
+ * for any particular base relation; but store it anyway to avoid confusion.
+ */
+
+typedef struct InnerIndexscanInfo
+{
+ NodeTag type;
+ /* The lookup key: */
+ Relids other_relids; /* a set of relevant other relids */
+ bool isouterjoin; /* true if join is outer */
+ /* Best path for this lookup key: */
+ Path *best_innerpath; /* best inner indexscan, or NULL if none */
+} InnerIndexscanInfo;
+
#endif /* RELATION_H */
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 4222c77ad97..b03ce0453e6 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -8,7 +8,7 @@
* Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
* Portions Copyright (c) 1994, Regents of the University of California
*
- * $Id: paths.h,v 1.60 2002/06/20 20:29:51 momjian Exp $
+ * $Id: paths.h,v 1.61 2002/11/24 21:52:15 tgl Exp $
*
*-------------------------------------------------------------------------
*/
@@ -40,6 +40,8 @@ extern void debug_print_rel(Query *root, RelOptInfo *rel);
* routines to generate index paths
*/
extern void create_index_paths(Query *root, RelOptInfo *rel);
+extern Path *best_inner_indexscan(Query *root, RelOptInfo *rel,
+ Relids outer_relids, JoinType jointype);
extern Oid indexable_operator(Expr *clause, Oid opclass,
bool indexkey_on_left);
extern List *extract_or_indexqual_conditions(RelOptInfo *rel,
diff --git a/src/include/optimizer/restrictinfo.h b/src/include/optimizer/restrictinfo.h
index 3806415fe8c..997d4ab8c52 100644
--- a/src/include/optimizer/restrictinfo.h
+++ b/src/include/optimizer/restrictinfo.h
@@ -7,7 +7,7 @@
* Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
* Portions Copyright (c) 1994, Regents of the University of California
*
- * $Id: restrictinfo.h,v 1.15 2002/06/20 20:29:51 momjian Exp $
+ * $Id: restrictinfo.h,v 1.16 2002/11/24 21:52:15 tgl Exp $
*
*-------------------------------------------------------------------------
*/
@@ -20,5 +20,8 @@ extern bool restriction_is_or_clause(RestrictInfo *restrictinfo);
extern List *get_actual_clauses(List *restrictinfo_list);
extern void get_actual_join_clauses(List *restrictinfo_list,
List **joinquals, List **otherquals);
+extern List *remove_redundant_join_clauses(Query *root,
+ List *restrictinfo_list,
+ JoinType jointype);
#endif /* RESTRICTINFO_H */
generated by cgit v1.2.3 (git 2.25.1) at 2025-05-30 12:01:21 +0000