granicus.if.org Git - postgresql/blob - src/backend/optimizer/path/orindxpath.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * orindxpath.c--
   4  *        Routines to find index paths that match a set of 'or' clauses
   5  *
   6  * Copyright (c) 1994, Regents of the University of California
   7  *
   8  *
   9  * IDENTIFICATION
  10  *        $Header: /cvsroot/pgsql/src/backend/optimizer/path/orindxpath.c,v 1.15 1999/02/08 04:29:12 momjian Exp $
  11  *
  12  *-------------------------------------------------------------------------
  13  */
  14 #include "postgres.h"
  15
  16 #include "nodes/pg_list.h"
  17 #include "nodes/relation.h"
  18 #include "nodes/primnodes.h"
  19
  20 #include "nodes/makefuncs.h"
  21 #include "nodes/nodeFuncs.h"
  22
  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"
  30
  31 #include "parser/parsetree.h"
  32
  33
  34 static void
  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);
  40
  41
  42 /*
  43  * create-or-index-paths--
  44  *        Creates index paths for indices that match 'or' clauses.
  45  *
  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
  48  *
  49  * Returns a list of these index path nodes.
  50  *
  51  */
  52 List *
  53 create_or_index_paths(Query *root,
  54                                           RelOptInfo * rel, List *clauses)
  55 {
  56         List       *t_list = NIL;
  57         List       *clist;
  58
  59         foreach(clist, clauses)
  60         {
  61                 RestrictInfo *clausenode = (RestrictInfo *) (lfirst(clist));
  62
  63                 /*
  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').
  69                  */
  70                 if (valid_or_clause(clausenode) &&
  71                         clausenode->indexids)
  72                 {
  73                         List       *temp = NIL;
  74                         List       *index_list = NIL;
  75                         bool            index_flag = true;
  76
  77                         index_list = clausenode->indexids;
  78                         foreach(temp, index_list)
  79                         {
  80                                 if (!lfirst(temp))
  81                                 {
  82                                         index_flag = false;
  83                                         break;
  84                                 }
  85                         }
  86                         /* do they all have indexes? */
  87                         if (index_flag)
  88                         {                                       /* used to be a lisp every function */
  89                                 IndexPath  *pathnode = makeNode(IndexPath);
  90                                 List       *indexids;
  91                                 Cost            cost;
  92                                 List       *selecs;
  93
  94                                 best_or_subclause_indices(root,
  95                                                                                   rel,
  96                                                                                   clausenode->clause->args,
  97                                                                                   clausenode->indexids,
  98                                                                                   NIL,
  99                                                                                   (Cost) 0,
 100                                                                                   NIL,
 101                                                                                   &indexids,
 102                                                                                   &cost,
 103                                                                                   &selecs);
 104
 105                                 pathnode->path.pathtype = T_IndexScan;
 106                                 pathnode->path.parent = rel;
 107                             pathnode->path.path_order.ordtype = SORTOP_ORDER;
 108                             /*
 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.
 112                                  */
 113                             pathnode->path.path_order.ord.sortop = NULL;
 114                             pathnode->path.keys = NIL;  /* not sure about this, bjm 1998/09/21 */
 115
 116                                 pathnode->indexqual = lcons(clausenode, NIL);
 117                                 pathnode->indexid = indexids;
 118                                 pathnode->path.path_cost = cost;
 119
 120                                 /*
 121                                  * copy restrictinfo list into path for expensive function
 122                                  * processing    -- JMH, 7/7/92
 123                                  */
 124                                 pathnode->path.loc_restrictinfo = set_difference(copyObject((Node *) rel->restrictinfo),
 125                                                                    lcons(clausenode, NIL));
 126
 127 #if 0                                                   /* fix xfunc */
 128                                 /* add in cost for expensive functions!  -- JMH, 7/7/92 */
 129                                 if (XfuncMode != XFUNC_OFF)
 130                                 {
 131                                         ((Path *) pathnode)->path_cost += xfunc_get_path_cost((Path) pathnode);
 132                                 }
 133 #endif
 134                                 clausenode->selectivity = (Cost) floatVal(selecs);
 135                                 t_list = lappend(t_list, pathnode);
 136                         }
 137                 }
 138         }
 139
 140         return t_list;
 141 }
 142
 143 /*
 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.
 148  *
 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'
 152  *              clause
 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
 158  *
 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.
 162  */
 163 static void
 164 best_or_subclause_indices(Query *root,
 165                                                   RelOptInfo * rel,
 166                                                   List *subclauses,
 167                                                   List *indices,
 168                                                   List *examined_indexids,
 169                                                   Cost subcost,
 170                                                   List *selectivities,
 171                                                   List **indexids,              /* return value */
 172                                                   Cost *cost,   /* return value */
 173                                                   List **selecs)                /* return value */
 174 {
 175         List       *slist;
 176
 177         foreach(slist, subclauses)
 178         {
 179                 int                     best_indexid;
 180                 Cost            best_cost;
 181                 Cost            best_selec;
 182
 183                 best_or_subclause_index(root, rel, lfirst(slist), lfirst(indices),
 184                                                                 &best_indexid, &best_cost, &best_selec);
 185
 186                 examined_indexids = lappendi(examined_indexids, best_indexid);
 187                 subcost += best_cost;
 188                 selectivities = lappend(selectivities, makeFloat(best_selec));
 189
 190                 indices = lnext(indices);
 191         }
 192
 193         *indexids = examined_indexids;
 194         *cost = subcost;
 195         *selecs = selectivities;
 196
 197         return;
 198 }
 199
 200 /*
 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.
 205  *
 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
 209  *
 210  * Returns a list (index-id index-subcost index-selectivity)
 211  * (a fixnum, a fixnum, and a flonum respectively).
 212  *
 213  */
 214 static void
 215 best_or_subclause_index(Query *root,
 216                                                 RelOptInfo * rel,
 217                                                 Expr *subclause,
 218                                                 List *indices,
 219                                                 int *retIndexid,                /* return value */
 220                                                 Cost *retCost,  /* return value */
 221                                                 Cost *retSelec) /* return value */
 222 {
 223         List       *ilist;
 224         bool            first_run = true;
 225
 226         /* if we don't match anything, return zeros */
 227         *retIndexid = 0;
 228         *retCost = 0.0;
 229         *retSelec = 0.0;
 230
 231         foreach(ilist, indices)
 232         {
 233                 RelOptInfo *index = (RelOptInfo *) lfirst(ilist);
 234
 235                 Datum           value;
 236                 int                     flag = 0;
 237                 Cost            subcost;
 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));
 241                 float           npages,
 242                                         selec;
 243
 244                 if (constant_on_right)
 245                         value = ((Const *) get_rightop(subclause))->constvalue;
 246                 else
 247                         value = NameGetDatum("");
 248                 if (constant_on_right)
 249                         flag = (_SELEC_IS_CONSTANT_ || _SELEC_CONSTANT_RIGHT_);
 250                 else
 251                         flag = _SELEC_CONSTANT_RIGHT_;
 252
 253                 index_selectivity(lfirsti(index->relids),
 254                                                   index->classlist,
 255                                                   lconsi(opno, NIL),
 256                                                   getrelid(lfirsti(rel->relids),
 257                                                                    root->rtable),
 258                                                   lconsi(attno, NIL),
 259                                                   lconsi(value, NIL),
 260                                                   lconsi(flag, NIL),
 261                                                   1,
 262                                                   &npages,
 263                                                   &selec);
 264
 265                 subcost = cost_index((Oid) lfirsti(index->relids),
 266                                                          (int) npages,
 267                                                          (Cost) selec,
 268                                                          rel->pages,
 269                                                          rel->tuples,
 270                                                          index->pages,
 271                                                          index->tuples,
 272                                                          false);
 273
 274                 if (first_run || subcost < *retCost)
 275                 {
 276                         *retIndexid = lfirsti(index->relids);
 277                         *retCost = subcost;
 278                         *retSelec = selec;
 279                         first_run = false;
 280                 }
 281         }
 282
 283         return;
 284 }