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

   1 /*-------------------------------------------------------------------------
   2  *
   3  * clausesel.c--
   4  *        Routines to compute and set clause selectivities
   5  *
   6  * Copyright (c) 1994, Regents of the University of California
   7  *
   8  *
   9  * IDENTIFICATION
  10  *        $Header: /cvsroot/pgsql/src/backend/optimizer/path/clausesel.c,v 1.15 1999/02/03 20:15:28 momjian Exp $
  11  *
  12  *-------------------------------------------------------------------------
  13  */
  14 #include "postgres.h"
  15
  16 #include "catalog/pg_operator.h"
  17 #include "fmgr.h"
  18 #include "nodes/pg_list.h"
  19 #include "nodes/primnodes.h"
  20 #include "nodes/relation.h"
  21 #include "optimizer/clauses.h"
  22 #include "optimizer/restrictinfo.h"
  23 #include "optimizer/cost.h"
  24 #include "optimizer/internal.h"
  25 #include "optimizer/plancat.h"
  26 #include "parser/parsetree.h"   /* for getrelid() */
  27 #include "utils/lsyscache.h"
  28
  29
  30 static Cost compute_selec(Query *root, List *clauses, List *or_selectivities);
  31
  32 /****************************************************************************
  33  *              ROUTINES TO SET CLAUSE SELECTIVITIES
  34  ****************************************************************************/
  35
  36 /*
  37  * set_clause_selectivities -
  38  *        Sets the selectivity field for each of clause in 'restrictinfo-list'
  39  *        to 'new-selectivity'.  If the selectivity has already been set, reset
  40  *        it only if the new one is better.
  41  *
  42  * Returns nothing of interest.
  43  *
  44  */
  45 void
  46 set_clause_selectivities(List *restrictinfo_list, Cost new_selectivity)
  47 {
  48         List       *temp;
  49         RestrictInfo *clausenode;
  50         Cost            cost_clause;
  51
  52         foreach(temp, restrictinfo_list)
  53         {
  54                 clausenode = (RestrictInfo *) lfirst(temp);
  55                 cost_clause = clausenode->selectivity;
  56                 if (FLOAT_IS_ZERO(cost_clause) || new_selectivity < cost_clause)
  57                         clausenode->selectivity = new_selectivity;
  58         }
  59 }
  60
  61 /*
  62  * product_selec -
  63  *        Multiplies the selectivities of each clause in 'restrictinfo-list'.
  64  *
  65  * Returns a flonum corresponding to the selectivity of 'restrictinfo-list'.
  66  */
  67 Cost
  68 product_selec(List *restrictinfo_list)
  69 {
  70         Cost            result = 1.0;
  71
  72         if (restrictinfo_list != NIL)
  73         {
  74                 List       *xclausenode = NIL;
  75                 Cost            temp;
  76
  77                 foreach(xclausenode, restrictinfo_list)
  78                 {
  79                         temp = ((RestrictInfo *) lfirst(xclausenode))->selectivity;
  80                         result = result * temp;
  81                 }
  82         }
  83         return result;
  84 }
  85
  86 /*
  87  * set_rest_relselec -
  88  *        Scans through clauses on each relation and assigns a selectivity to
  89  *        those clauses that haven't been assigned a selectivity by an index.
  90  *
  91  * Returns nothing of interest.
  92  * MODIFIES: selectivities of the various rel's restrictinfo
  93  *                slots.
  94  */
  95 void
  96 set_rest_relselec(Query *root, List *rel_list)
  97 {
  98         RelOptInfo *rel;
  99         List       *x;
 100
 101         foreach(x, rel_list)
 102         {
 103                 rel = (RelOptInfo *) lfirst(x);
 104                 set_rest_selec(root, rel->restrictinfo);
 105         }
 106 }
 107
 108 /*
 109  * set_rest_selec -
 110  *        Sets the selectivity fields for those clauses within a single
 111  *        relation's 'restrictinfo-list' that haven't already been set.
 112  *
 113  * Returns nothing of interest.
 114  *
 115  */
 116 void
 117 set_rest_selec(Query *root, List *restrictinfo_list)
 118 {
 119         List       *temp = NIL;
 120         RestrictInfo *clausenode = (RestrictInfo *) NULL;
 121         Cost            cost_clause;
 122
 123         foreach(temp, restrictinfo_list)
 124         {
 125                 clausenode = (RestrictInfo *) lfirst(temp);
 126                 cost_clause = clausenode->selectivity;
 127
 128                 /*
 129                  * Check to see if the selectivity of this clause or any 'or'
 130                  * subclauses (if any) haven't been set yet.
 131                  */
 132                 if (valid_or_clause(clausenode) || FLOAT_IS_ZERO(cost_clause))
 133                 {
 134                         clausenode->selectivity =
 135                                 compute_clause_selec(root,
 136                                                                          (Node *) clausenode->clause,
 137                                                                          lcons(makeFloat(cost_clause), NIL));
 138                 }
 139         }
 140 }
 141
 142 /****************************************************************************
 143  *              ROUTINES TO COMPUTE SELECTIVITIES
 144  ****************************************************************************/
 145
 146 /*
 147  * compute_clause_selec -
 148  *        Given a clause, this routine will compute the selectivity of the
 149  *        clause by calling 'compute_selec' with the appropriate parameters
 150  *        and possibly use that return value to compute the real selectivity
 151  *        of a clause.
 152  *
 153  * 'or-selectivities' are selectivities that have already been assigned
 154  *              to subclauses of an 'or' clause.
 155  *
 156  * Returns a flonum corresponding to the clause selectivity.
 157  *
 158  */
 159 Cost
 160 compute_clause_selec(Query *root, Node *clause, List *or_selectivities)
 161 {
 162         if (is_opclause(clause))
 163                 return compute_selec(root, lcons(clause, NIL), or_selectivities);
 164         else if (not_clause(clause))
 165         {
 166
 167                 /*
 168                  * 'not' gets "1.0 - selectivity-of-inner-clause".
 169                  */
 170                 return (1.000000 - compute_selec(root,
 171                                                                  lcons(get_notclausearg((Expr *) clause),
 172                                                                            NIL),
 173                                                                                  or_selectivities));
 174         }
 175         else if (or_clause(clause))
 176         {
 177
 178                 /*
 179                  * Both 'or' and 'and' clauses are evaluated as described in
 180                  * (compute_selec).
 181                  */
 182                 return compute_selec(root, ((Expr *) clause)->args, or_selectivities);
 183         }
 184         else
 185                 return compute_selec(root, lcons(clause, NIL), or_selectivities);
 186 }
 187
 188 /*
 189  * compute_selec -
 190  *        Computes the selectivity of a clause.
 191  *
 192  *        If there is more than one clause in the argument 'clauses', then the
 193  *        desired selectivity is that of an 'or' clause.  Selectivities for an
 194  *        'or' clause such as (OR a b) are computed by finding the selectivity
 195  *        of a (s1) and b (s2) and computing s1+s2 - s1*s2.
 196  *
 197  *        In addition, if the clause is an 'or' clause, individual selectivities
 198  *        may have already been assigned by indices to subclauses.      These values
 199  *        are contained in the list 'or-selectivities'.
 200  *
 201  * Returns the clause selectivity as a flonum.
 202  *
 203  */
 204 static Cost
 205 compute_selec(Query *root, List *clauses, List *or_selectivities)
 206 {
 207         Cost            s1 = 0;
 208         List       *clause = lfirst(clauses);
 209
 210         if (clauses == NULL)
 211                 s1 = 1.0;
 212         else if (IsA(clause, Param))
 213         {
 214                 /* XXX How're we handling this before?? -ay */
 215                 s1 = 1.0;
 216         }
 217         else if (IsA(clause, Const))
 218                 s1 = ((bool) ((Const *) clause)->constvalue) ? 1.0 : 0.0;
 219         else if (IsA(clause, Var))
 220         {
 221                 Oid                     relid = getrelid(((Var *) clause)->varno,
 222                                                                          root->rtable);
 223
 224                 /*
 225                  * we have a bool Var.  This is exactly equivalent to the clause:
 226                  * reln.attribute = 't' so we compute the selectivity as if that
 227                  * is what we have. The magic #define constants are a hack.  I
 228                  * didn't want to have to do system cache look ups to find out all
 229                  * of that info.
 230                  */
 231
 232                 s1 = restriction_selectivity(F_EQSEL,
 233                                                                          BooleanEqualOperator,
 234                                                                          relid,
 235                                                                          ((Var *) clause)->varoattno,
 236                                                                          "t",
 237                                                                          _SELEC_CONSTANT_RIGHT_);
 238         }
 239         else if (or_selectivities)
 240         {
 241                 /* If s1 has already been assigned by an index, use that value. */
 242                 List       *this_sel = lfirst(or_selectivities);
 243
 244                 s1 = floatVal(this_sel);
 245         }
 246         else if (is_funcclause((Node *) clause))
 247         {
 248                 /* this isn't an Oper, it's a Func!! */
 249
 250                 /*
 251                  * This is not an operator, so we guess at the selectivity. THIS
 252                  * IS A HACK TO GET V4 OUT THE DOOR.  FUNCS SHOULD BE ABLE TO HAVE
 253                  * SELECTIVITIES THEMSELVES.       -- JMH 7/9/92
 254                  */
 255                 s1 = 0.1;
 256         }
 257         else if (not_clause((Node *) clause))
 258         {
 259                 /* negate this baby */
 260                 return 1 - compute_selec(root, ((Expr *)clause)->args, or_selectivities);
 261         }
 262         else if (is_subplan((Node *) clause))
 263         {
 264
 265                 /*
 266                  * Just for the moment! FIX ME! - vadim 02/04/98
 267                  */
 268                 s1 = 1.0;
 269         }
 270         else if (NumRelids((Node *) clause) == 1)
 271         {
 272
 273                 /*
 274                  * ...otherwise, calculate s1 from 'clauses'. The clause is not a
 275                  * join clause, since there is only one relid in the clause.  The
 276                  * clause selectivity will be based on the operator selectivity
 277                  * and operand values.
 278                  */
 279                 Oid                     opno = ((Oper *) ((Expr *) clause)->oper)->opno;
 280                 RegProcedure oprrest = get_oprrest(opno);
 281                 Oid                     relid;
 282                 int                     relidx;
 283                 AttrNumber      attno;
 284                 Datum           constval;
 285                 int                     flag;
 286
 287                 get_relattval((Node *) clause, &relidx, &attno, &constval, &flag);
 288                 relid = getrelid(relidx, root->rtable);
 289
 290                 /*
 291                  * if the oprrest procedure is missing for whatever reason, use a
 292                  * selectivity of 0.5
 293                  */
 294                 if (!oprrest)
 295                         s1 = (Cost) (0.5);
 296                 else if (attno == InvalidAttrNumber)
 297                 {
 298
 299                         /*
 300                          * attno can be Invalid if the clause had a function in it,
 301                          * i.e.   WHERE myFunc(f) = 10
 302                          */
 303                         /* this should be FIXED somehow to use function selectivity */
 304                         s1 = (Cost) (0.5);
 305                 }
 306                 else
 307                         s1 = (Cost) restriction_selectivity(oprrest,
 308                                                                                                 opno,
 309                                                                                                 relid,
 310                                                                                                 attno,
 311                                                                                                 (char *) constval,
 312                                                                                                 flag);
 313
 314         }
 315         else
 316         {
 317
 318                 /*
 319                  * The clause must be a join clause.  The clause selectivity will
 320                  * be based on the relations to be scanned and the attributes they
 321                  * are to be joined on.
 322                  */
 323                 Oid                     opno = ((Oper *) ((Expr *) clause)->oper)->opno;
 324                 RegProcedure oprjoin = get_oprjoin(opno);
 325                 int                     relid1,
 326                                         relid2;
 327                 AttrNumber      attno1,
 328                                         attno2;
 329
 330                 get_rels_atts((Node *) clause, &relid1, &attno1, &relid2, &attno2);
 331                 relid1 = getrelid(relid1, root->rtable);
 332                 relid2 = getrelid(relid2, root->rtable);
 333
 334                 /*
 335                  * if the oprjoin procedure is missing for whatever reason, use a
 336                  * selectivity of 0.5
 337                  */
 338                 if (!oprjoin)
 339                         s1 = (Cost) (0.5);
 340                 else
 341                         s1 = (Cost) join_selectivity(oprjoin,
 342                                                                                  opno,
 343                                                                                  relid1,
 344                                                                                  attno1,
 345                                                                                  relid2,
 346                                                                                  attno2);
 347         }
 348
 349         /*
 350          * A null clause list eliminates no tuples, so return a selectivity of
 351          * 1.0.  If there is only one clause, the selectivity is not that of
 352          * an 'or' clause, but rather that of the single clause.
 353          */
 354
 355         if (length(clauses) < 2)
 356                 return s1;
 357         else
 358         {
 359                 /* Compute selectivity of the 'or'ed subclauses. */
 360                 /* Added check for taking lnext(NIL).  -- JMH 3/9/92 */
 361                 Cost            s2;
 362
 363                 if (or_selectivities != NIL)
 364                         s2 = compute_selec(root, lnext(clauses), lnext(or_selectivities));
 365                 else
 366                         s2 = compute_selec(root, lnext(clauses), NIL);
 367                 return s1 + s2 - s1 * s2;
 368         }
 369 }