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  * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
   7  * Portions Copyright (c) 1994, Regents of the University of California
   8  *
   9  *
  10  * IDENTIFICATION
  11  *        $PostgreSQL: pgsql/src/backend/optimizer/path/orindxpath.c,v 1.73 2005/07/02 23:00:40 tgl Exp $
  12  *
  13  *-------------------------------------------------------------------------
  14  */
  15
  16 #include "postgres.h"
  17
  18 #include "optimizer/cost.h"
  19 #include "optimizer/paths.h"
  20 #include "optimizer/planmain.h"
  21 #include "optimizer/restrictinfo.h"
  22
  23
  24 /*----------
  25  * create_or_index_quals
  26  *        Examine join OR-of-AND quals to see if any useful restriction OR
  27  *        clauses can be extracted.  If so, add them to the query.
  28  *
  29  * Although a join clause must reference other relations overall,
  30  * an OR of ANDs clause might contain sub-clauses that reference just this
  31  * relation and can be used to build a restriction clause.
  32  * For example consider
  33  *              WHERE ((a.x = 42 AND b.y = 43) OR (a.x = 44 AND b.z = 45));
  34  * We can transform this into
  35  *              WHERE ((a.x = 42 AND b.y = 43) OR (a.x = 44 AND b.z = 45))
  36  *                      AND (a.x = 42 OR a.x = 44)
  37  *                      AND (b.y = 43 OR b.z = 45);
  38  * which opens the potential to build OR indexscans on a and b.  In essence
  39  * this is a partial transformation to CNF (AND of ORs format).  It is not
  40  * complete, however, because we do not unravel the original OR --- doing so
  41  * would usually bloat the qualification expression to little gain.
  42  *
  43  * The added quals are partially redundant with the original OR, and therefore
  44  * will cause the size of the joinrel to be underestimated when it is finally
  45  * formed.      (This would be true of a full transformation to CNF as well; the
  46  * fault is not really in the transformation, but in clauselist_selectivity's
  47  * inability to recognize redundant conditions.)  To minimize the collateral
  48  * damage, we want to minimize the number of quals added.  Therefore we do
  49  * not add every possible extracted restriction condition to the query.
  50  * Instead, we search for the single restriction condition that generates
  51  * the most useful (cheapest) OR indexscan, and add only that condition.
  52  * This is a pretty ad-hoc heuristic, but quite useful.
  53  *
  54  * We can then compensate for the redundancy of the added qual by poking
  55  * the recorded selectivity of the original OR clause, thereby ensuring
  56  * the added qual doesn't change the estimated size of the joinrel when
  57  * it is finally formed.  This is a MAJOR HACK: it depends on the fact
  58  * that clause selectivities are cached and on the fact that the same
  59  * RestrictInfo node will appear in every joininfo list that might be used
  60  * when the joinrel is formed.  And it probably isn't right in cases where
  61  * the size estimation is nonlinear (i.e., outer and IN joins).  But it
  62  * beats not doing anything.
  63  *
  64  * NOTE: one might think this messiness could be worked around by generating
  65  * the indexscan path with a small path->rows value, and not touching the
  66  * rel's baserestrictinfo or rel->rows.  However, that does not work.
  67  * The optimizer's fundamental design assumes that every general-purpose
  68  * Path for a given relation generates the same number of rows.  Without
  69  * this assumption we'd not be able to optimize solely on the cost of Paths,
  70  * but would have to take number of output rows into account as well.
  71  * (Perhaps someday that'd be worth doing, but it's a pretty big change...)
  72  *
  73  * 'rel' is the relation entry for which quals are to be created
  74  *
  75  * If successful, adds qual(s) to rel->baserestrictinfo and returns TRUE.
  76  * If no quals available, returns FALSE and doesn't change rel.
  77  *
  78  * Note: check_partial_indexes() must have been run previously.
  79  *----------
  80  */
  81 bool
  82 create_or_index_quals(PlannerInfo *root, RelOptInfo *rel)
  83 {
  84         BitmapOrPath *bestpath = NULL;
  85         RestrictInfo *bestrinfo = NULL;
  86         List       *newrinfos;
  87         RestrictInfo *or_rinfo;
  88         Selectivity or_selec,
  89                                 orig_selec;
  90         ListCell   *i;
  91
  92         /*
  93          * Find potentially interesting OR joinclauses.
  94          */
  95         foreach(i, rel->joininfo)
  96         {
  97                 RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
  98
  99                 if (restriction_is_or_clause(rinfo))
 100                 {
 101                         /*
 102                          * Use the generate_bitmap_or_paths() machinery to estimate
 103                          * the value of each OR clause.  We can use regular
 104                          * restriction clauses along with the OR clause contents to
 105                          * generate indexquals.  We pass outer_relids = NULL so that
 106                          * sub-clauses that are actually joins will be ignored.
 107                          */
 108                         List *orpaths;
 109                         ListCell *k;
 110
 111                         orpaths = generate_bitmap_or_paths(root, rel,
 112                                                                                            list_make1(rinfo),
 113                                                                                            rel->baserestrictinfo,
 114                                                                                            false, NULL);
 115
 116                         /* Locate the cheapest OR path */
 117                         foreach(k, orpaths)
 118                         {
 119                                 BitmapOrPath   *path = (BitmapOrPath *) lfirst(k);
 120
 121                                 Assert(IsA(path, BitmapOrPath));
 122                                 if (bestpath == NULL ||
 123                                         path->path.total_cost < bestpath->path.total_cost)
 124                                 {
 125                                         bestpath = path;
 126                                         bestrinfo = rinfo;
 127                                 }
 128                         }
 129                 }
 130         }
 131
 132         /* Fail if no suitable clauses found */
 133         if (bestpath == NULL)
 134                 return false;
 135
 136         /*
 137          * Convert the path's indexclauses structure to a RestrictInfo tree,
 138          * and add it to the rel's restriction list.
 139          */
 140         newrinfos = make_restrictinfo_from_bitmapqual((Path *) bestpath, true);
 141         Assert(list_length(newrinfos) == 1);
 142         or_rinfo = (RestrictInfo *) linitial(newrinfos);
 143         Assert(IsA(or_rinfo, RestrictInfo));
 144
 145         rel->baserestrictinfo = list_concat(rel->baserestrictinfo, newrinfos);
 146
 147         /*
 148          * Adjust the original OR clause's cached selectivity to compensate
 149          * for the selectivity of the added (but redundant) lower-level qual.
 150          * This should result in the join rel getting approximately the same
 151          * rows estimate as it would have gotten without all these
 152          * shenanigans. (XXX major hack alert ... this depends on the
 153          * assumption that the selectivity will stay cached ...)
 154          */
 155         or_selec = clause_selectivity(root, (Node *) or_rinfo,
 156                                                                   0, JOIN_INNER);
 157         if (or_selec > 0 && or_selec < 1)
 158         {
 159                 orig_selec = clause_selectivity(root, (Node *) bestrinfo,
 160                                                                                 0, JOIN_INNER);
 161                 bestrinfo->this_selec = orig_selec / or_selec;
 162                 /* clamp result to sane range */
 163                 if (bestrinfo->this_selec > 1)
 164                         bestrinfo->this_selec = 1;
 165         }
 166
 167         /* Tell caller to recompute rel's rows estimate */
 168         return true;
 169 }