1 /*-------------------------------------------------------------------------
4 * Routines to find index paths that match a set of 'or' clauses
6 * Copyright (c) 1994, Regents of the University of California
10 * $Header: /cvsroot/pgsql/src/backend/optimizer/path/orindxpath.c,v 1.15 1999/02/08 04:29:12 momjian Exp $
12 *-------------------------------------------------------------------------
16 #include "nodes/pg_list.h"
17 #include "nodes/relation.h"
18 #include "nodes/primnodes.h"
20 #include "nodes/makefuncs.h"
21 #include "nodes/nodeFuncs.h"
23 #include "optimizer/internal.h"
24 #include "optimizer/clauses.h"
25 #include "optimizer/restrictinfo.h"
26 #include "optimizer/paths.h"
27 #include "optimizer/cost.h"
28 #include "optimizer/plancat.h"
29 #include "optimizer/xfunc.h"
31 #include "parser/parsetree.h"
35 best_or_subclause_indices(Query *root, RelOptInfo * rel, List *subclauses,
36 List *indices, List *examined_indexids, Cost subcost, List *selectivities,
37 List **indexids, Cost *cost, List **selecs);
38 static void best_or_subclause_index(Query *root, RelOptInfo * rel, Expr *subclause,
39 List *indices, int *indexid, Cost *cost, Cost *selec);
43 * create-or-index-paths--
44 * Creates index paths for indices that match 'or' clauses.
46 * 'rel' is the relation entry for which the paths are to be defined on
47 * 'clauses' is the list of available restriction clause nodes
49 * Returns a list of these index path nodes.
53 create_or_index_paths(Query *root,
54 RelOptInfo * rel, List *clauses)
59 foreach(clist, clauses)
61 RestrictInfo *clausenode = (RestrictInfo *) (lfirst(clist));
64 * Check to see if this clause is an 'or' clause, and, if so,
65 * whether or not each of the subclauses within the 'or' clause
66 * has been matched by an index (the 'Index field was set in
67 * (match_or) if no index matches a given subclause, one of the
68 * lists of index nodes returned by (get_index) will be 'nil').
70 if (valid_or_clause(clausenode) &&
74 List *index_list = NIL;
75 bool index_flag = true;
77 index_list = clausenode->indexids;
78 foreach(temp, index_list)
86 /* do they all have indexes? */
88 { /* used to be a lisp every function */
89 IndexPath *pathnode = makeNode(IndexPath);
94 best_or_subclause_indices(root,
96 clausenode->clause->args,
105 pathnode->path.pathtype = T_IndexScan;
106 pathnode->path.parent = rel;
107 pathnode->path.path_order.ordtype = SORTOP_ORDER;
109 * This is an IndexScan, but it does index lookups based
110 * on the order of the fields specified in the WHERE clause,
111 * not in any order, so the sortop is NULL.
113 pathnode->path.path_order.ord.sortop = NULL;
114 pathnode->path.keys = NIL; /* not sure about this, bjm 1998/09/21 */
116 pathnode->indexqual = lcons(clausenode, NIL);
117 pathnode->indexid = indexids;
118 pathnode->path.path_cost = cost;
121 * copy restrictinfo list into path for expensive function
122 * processing -- JMH, 7/7/92
124 pathnode->path.loc_restrictinfo = set_difference(copyObject((Node *) rel->restrictinfo),
125 lcons(clausenode, NIL));
127 #if 0 /* fix xfunc */
128 /* add in cost for expensive functions! -- JMH, 7/7/92 */
129 if (XfuncMode != XFUNC_OFF)
131 ((Path *) pathnode)->path_cost += xfunc_get_path_cost((Path) pathnode);
134 clausenode->selectivity = (Cost) floatVal(selecs);
135 t_list = lappend(t_list, pathnode);
144 * best-or-subclause-indices--
145 * Determines the best index to be used in conjunction with each subclause
146 * of an 'or' clause and the cost of scanning a relation using these
147 * indices. The cost is the sum of the individual index costs.
149 * 'rel' is the node of the relation on which the index is defined
150 * 'subclauses' are the subclauses of the 'or' clause
151 * 'indices' are those index nodes that matched subclauses of the 'or'
153 * 'examined-indexids' is a list of those index ids to be used with
154 * subclauses that have already been examined
155 * 'subcost' is the cost of using the indices in 'examined-indexids'
156 * 'selectivities' is a list of the selectivities of subclauses that
157 * have already been examined
159 * Returns a list of the indexids, cost, and selectivities of each
160 * subclause, e.g., ((i1 i2 i3) cost (s1 s2 s3)), where 'i' is an OID,
161 * 'cost' is a flonum, and 's' is a flonum.
164 best_or_subclause_indices(Query *root,
168 List *examined_indexids,
171 List **indexids, /* return value */
172 Cost *cost, /* return value */
173 List **selecs) /* return value */
177 foreach(slist, subclauses)
183 best_or_subclause_index(root, rel, lfirst(slist), lfirst(indices),
184 &best_indexid, &best_cost, &best_selec);
186 examined_indexids = lappendi(examined_indexids, best_indexid);
187 subcost += best_cost;
188 selectivities = lappend(selectivities, makeFloat(best_selec));
190 indices = lnext(indices);
193 *indexids = examined_indexids;
195 *selecs = selectivities;
201 * best-or-subclause-index--
202 * Determines which is the best index to be used with a subclause of
203 * an 'or' clause by estimating the cost of using each index and selecting
204 * the least expensive.
206 * 'rel' is the node of the relation on which the index is defined
207 * 'subclause' is the subclause
208 * 'indices' is a list of index nodes that match the subclause
210 * Returns a list (index-id index-subcost index-selectivity)
211 * (a fixnum, a fixnum, and a flonum respectively).
215 best_or_subclause_index(Query *root,
219 int *retIndexid, /* return value */
220 Cost *retCost, /* return value */
221 Cost *retSelec) /* return value */
224 bool first_run = true;
226 /* if we don't match anything, return zeros */
231 foreach(ilist, indices)
233 RelOptInfo *index = (RelOptInfo *) lfirst(ilist);
238 AttrNumber attno = (get_leftop(subclause))->varattno;
239 Oid opno = ((Oper *) subclause->oper)->opno;
240 bool constant_on_right = non_null((Expr *) get_rightop(subclause));
244 if (constant_on_right)
245 value = ((Const *) get_rightop(subclause))->constvalue;
247 value = NameGetDatum("");
248 if (constant_on_right)
249 flag = (_SELEC_IS_CONSTANT_ || _SELEC_CONSTANT_RIGHT_);
251 flag = _SELEC_CONSTANT_RIGHT_;
253 index_selectivity(lfirsti(index->relids),
256 getrelid(lfirsti(rel->relids),
265 subcost = cost_index((Oid) lfirsti(index->relids),
274 if (first_run || subcost < *retCost)
276 *retIndexid = lfirsti(index->relids);