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