LCOV - code coverage report
Current view: top level - src/backend/optimizer/util - orclauses.c (source / functions) Hit Total Coverage
Test: PostgreSQL 17devel Lines: 74 80 92.5 %
Date: 2023-12-11 15:11:28 Functions: 4 4 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * orclauses.c
       4             :  *    Routines to extract restriction OR clauses from join OR clauses
       5             :  *
       6             :  * Portions Copyright (c) 1996-2023, PostgreSQL Global Development Group
       7             :  * Portions Copyright (c) 1994, Regents of the University of California
       8             :  *
       9             :  *
      10             :  * IDENTIFICATION
      11             :  *    src/backend/optimizer/util/orclauses.c
      12             :  *
      13             :  *-------------------------------------------------------------------------
      14             :  */
      15             : 
      16             : #include "postgres.h"
      17             : 
      18             : #include "nodes/makefuncs.h"
      19             : #include "nodes/nodeFuncs.h"
      20             : #include "optimizer/clauses.h"
      21             : #include "optimizer/cost.h"
      22             : #include "optimizer/optimizer.h"
      23             : #include "optimizer/orclauses.h"
      24             : #include "optimizer/restrictinfo.h"
      25             : 
      26             : 
      27             : static bool is_safe_restriction_clause_for(RestrictInfo *rinfo, RelOptInfo *rel);
      28             : static Expr *extract_or_clause(RestrictInfo *or_rinfo, RelOptInfo *rel);
      29             : static void consider_new_or_clause(PlannerInfo *root, RelOptInfo *rel,
      30             :                                    Expr *orclause, RestrictInfo *join_or_rinfo);
      31             : 
      32             : 
      33             : /*
      34             :  * extract_restriction_or_clauses
      35             :  *    Examine join OR-of-AND clauses to see if any useful restriction OR
      36             :  *    clauses can be extracted.  If so, add them to the query.
      37             :  *
      38             :  * Although a join clause must reference multiple relations overall,
      39             :  * an OR of ANDs clause might contain sub-clauses that reference just one
      40             :  * relation and can be used to build a restriction clause for that rel.
      41             :  * For example consider
      42             :  *      WHERE ((a.x = 42 AND b.y = 43) OR (a.x = 44 AND b.z = 45));
      43             :  * We can transform this into
      44             :  *      WHERE ((a.x = 42 AND b.y = 43) OR (a.x = 44 AND b.z = 45))
      45             :  *          AND (a.x = 42 OR a.x = 44)
      46             :  *          AND (b.y = 43 OR b.z = 45);
      47             :  * which allows the latter clauses to be applied during the scans of a and b,
      48             :  * perhaps as index qualifications, and in any case reducing the number of
      49             :  * rows arriving at the join.  In essence this is a partial transformation to
      50             :  * CNF (AND of ORs format).  It is not complete, however, because we do not
      51             :  * unravel the original OR --- doing so would usually bloat the qualification
      52             :  * expression to little gain.
      53             :  *
      54             :  * The added quals are partially redundant with the original OR, and therefore
      55             :  * would cause the size of the joinrel to be underestimated when it is finally
      56             :  * formed.  (This would be true of a full transformation to CNF as well; the
      57             :  * fault is not really in the transformation, but in clauselist_selectivity's
      58             :  * inability to recognize redundant conditions.)  We can compensate for this
      59             :  * redundancy by changing the cached selectivity of the original OR clause,
      60             :  * canceling out the (valid) reduction in the estimated sizes of the base
      61             :  * relations so that the estimated joinrel size remains the same.  This is
      62             :  * a MAJOR HACK: it depends on the fact that clause selectivities are cached
      63             :  * and on the fact that the same RestrictInfo node will appear in every
      64             :  * joininfo list that might be used when the joinrel is formed.
      65             :  * And it doesn't work in cases where the size estimation is nonlinear
      66             :  * (i.e., outer and IN joins).  But it beats not doing anything.
      67             :  *
      68             :  * We examine each base relation to see if join clauses associated with it
      69             :  * contain extractable restriction conditions.  If so, add those conditions
      70             :  * to the rel's baserestrictinfo and update the cached selectivities of the
      71             :  * join clauses.  Note that the same join clause will be examined afresh
      72             :  * from the point of view of each baserel that participates in it, so its
      73             :  * cached selectivity may get updated multiple times.
      74             :  */
      75             : void
      76      261200 : extract_restriction_or_clauses(PlannerInfo *root)
      77             : {
      78             :     Index       rti;
      79             : 
      80             :     /* Examine each baserel for potential join OR clauses */
      81      751300 :     for (rti = 1; rti < root->simple_rel_array_size; rti++)
      82             :     {
      83      490100 :         RelOptInfo *rel = root->simple_rel_array[rti];
      84             :         ListCell   *lc;
      85             : 
      86             :         /* there may be empty slots corresponding to non-baserel RTEs */
      87      490100 :         if (rel == NULL)
      88      121990 :             continue;
      89             : 
      90             :         Assert(rel->relid == rti);   /* sanity check on array */
      91             : 
      92             :         /* ignore RTEs that are "other rels" */
      93      368110 :         if (rel->reloptkind != RELOPT_BASEREL)
      94           0 :             continue;
      95             : 
      96             :         /*
      97             :          * Find potentially interesting OR joinclauses.  We can use any
      98             :          * joinclause that is considered safe to move to this rel by the
      99             :          * parameterized-path machinery, even though what we are going to do
     100             :          * with it is not exactly a parameterized path.
     101             :          */
     102      474454 :         foreach(lc, rel->joininfo)
     103             :         {
     104      106344 :             RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
     105             : 
     106      113394 :             if (restriction_is_or_clause(rinfo) &&
     107        7050 :                 join_clause_is_movable_to(rinfo, rel))
     108             :             {
     109             :                 /* Try to extract a qual for this rel only */
     110        4746 :                 Expr       *orclause = extract_or_clause(rinfo, rel);
     111             : 
     112             :                 /*
     113             :                  * If successful, decide whether we want to use the clause,
     114             :                  * and insert it into the rel's restrictinfo list if so.
     115             :                  */
     116        4746 :                 if (orclause)
     117         202 :                     consider_new_or_clause(root, rel, orclause, rinfo);
     118             :             }
     119             :         }
     120             :     }
     121      261200 : }
     122             : 
     123             : /*
     124             :  * Is the given primitive (non-OR) RestrictInfo safe to move to the rel?
     125             :  */
     126             : static bool
     127        9336 : is_safe_restriction_clause_for(RestrictInfo *rinfo, RelOptInfo *rel)
     128             : {
     129             :     /*
     130             :      * We want clauses that mention the rel, and only the rel.  So in
     131             :      * particular pseudoconstant clauses can be rejected quickly.  Then check
     132             :      * the clause's Var membership.
     133             :      */
     134        9336 :     if (rinfo->pseudoconstant)
     135           0 :         return false;
     136        9336 :     if (!bms_equal(rinfo->clause_relids, rel->relids))
     137        5138 :         return false;
     138             : 
     139             :     /* We don't want extra evaluations of any volatile functions */
     140        4198 :     if (contain_volatile_functions((Node *) rinfo->clause))
     141           0 :         return false;
     142             : 
     143        4198 :     return true;
     144             : }
     145             : 
     146             : /*
     147             :  * Try to extract a restriction clause mentioning only "rel" from the given
     148             :  * join OR-clause.
     149             :  *
     150             :  * We must be able to extract at least one qual for this rel from each of
     151             :  * the arms of the OR, else we can't use it.
     152             :  *
     153             :  * Returns an OR clause (not a RestrictInfo!) pertaining to rel, or NULL
     154             :  * if no OR clause could be extracted.
     155             :  */
     156             : static Expr *
     157        4782 : extract_or_clause(RestrictInfo *or_rinfo, RelOptInfo *rel)
     158             : {
     159        4782 :     List       *clauselist = NIL;
     160             :     ListCell   *lc;
     161             : 
     162             :     /*
     163             :      * Scan each arm of the input OR clause.  Notice we descend into
     164             :      * or_rinfo->orclause, which has RestrictInfo nodes embedded below the
     165             :      * toplevel OR/AND structure.  This is useful because we can use the info
     166             :      * in those nodes to make is_safe_restriction_clause_for()'s checks
     167             :      * cheaper.  We'll strip those nodes from the returned tree, though,
     168             :      * meaning that fresh ones will be built if the clause is accepted as a
     169             :      * restriction clause.  This might seem wasteful --- couldn't we re-use
     170             :      * the existing RestrictInfos?  But that'd require assuming that
     171             :      * selectivity and other cached data is computed exactly the same way for
     172             :      * a restriction clause as for a join clause, which seems undesirable.
     173             :      */
     174             :     Assert(is_orclause(or_rinfo->orclause));
     175        8542 :     foreach(lc, ((BoolExpr *) or_rinfo->orclause)->args)
     176             :     {
     177        8334 :         Node       *orarg = (Node *) lfirst(lc);
     178        8334 :         List       *subclauses = NIL;
     179             :         Node       *subclause;
     180             : 
     181             :         /* OR arguments should be ANDs or sub-RestrictInfos */
     182        8334 :         if (is_andclause(orarg))
     183             :         {
     184         718 :             List       *andargs = ((BoolExpr *) orarg)->args;
     185             :             ListCell   *lc2;
     186             : 
     187        2474 :             foreach(lc2, andargs)
     188             :             {
     189        1756 :                 RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc2);
     190             : 
     191        1756 :                 if (restriction_is_or_clause(rinfo))
     192             :                 {
     193             :                     /*
     194             :                      * Recurse to deal with nested OR.  Note we *must* recurse
     195             :                      * here, this isn't just overly-tense optimization: we
     196             :                      * have to descend far enough to find and strip all
     197             :                      * RestrictInfos in the expression.
     198             :                      */
     199             :                     Expr       *suborclause;
     200             : 
     201          36 :                     suborclause = extract_or_clause(rinfo, rel);
     202          36 :                     if (suborclause)
     203           6 :                         subclauses = lappend(subclauses, suborclause);
     204             :                 }
     205        1720 :                 else if (is_safe_restriction_clause_for(rinfo, rel))
     206        1126 :                     subclauses = lappend(subclauses, rinfo->clause);
     207             :             }
     208             :         }
     209             :         else
     210             :         {
     211        7616 :             RestrictInfo *rinfo = castNode(RestrictInfo, orarg);
     212             : 
     213             :             Assert(!restriction_is_or_clause(rinfo));
     214        7616 :             if (is_safe_restriction_clause_for(rinfo, rel))
     215        3072 :                 subclauses = lappend(subclauses, rinfo->clause);
     216             :         }
     217             : 
     218             :         /*
     219             :          * If nothing could be extracted from this arm, we can't do anything
     220             :          * with this OR clause.
     221             :          */
     222        8334 :         if (subclauses == NIL)
     223        4574 :             return NULL;
     224             : 
     225             :         /*
     226             :          * OK, add subclause(s) to the result OR.  If we found more than one,
     227             :          * we need an AND node.  But if we found only one, and it is itself an
     228             :          * OR node, add its subclauses to the result instead; this is needed
     229             :          * to preserve AND/OR flatness (ie, no OR directly underneath OR).
     230             :          */
     231        3760 :         subclause = (Node *) make_ands_explicit(subclauses);
     232        3760 :         if (is_orclause(subclause))
     233           6 :             clauselist = list_concat(clauselist,
     234           6 :                                      ((BoolExpr *) subclause)->args);
     235             :         else
     236        3754 :             clauselist = lappend(clauselist, subclause);
     237             :     }
     238             : 
     239             :     /*
     240             :      * If we got a restriction clause from every arm, wrap them up in an OR
     241             :      * node.  (In theory the OR node might be unnecessary, if there was only
     242             :      * one arm --- but then the input OR node was also redundant.)
     243             :      */
     244         208 :     if (clauselist != NIL)
     245         208 :         return make_orclause(clauselist);
     246           0 :     return NULL;
     247             : }
     248             : 
     249             : /*
     250             :  * Consider whether a successfully-extracted restriction OR clause is
     251             :  * actually worth using.  If so, add it to the planner's data structures,
     252             :  * and adjust the original join clause (join_or_rinfo) to compensate.
     253             :  */
     254             : static void
     255         202 : consider_new_or_clause(PlannerInfo *root, RelOptInfo *rel,
     256             :                        Expr *orclause, RestrictInfo *join_or_rinfo)
     257             : {
     258             :     RestrictInfo *or_rinfo;
     259             :     Selectivity or_selec,
     260             :                 orig_selec;
     261             : 
     262             :     /*
     263             :      * Build a RestrictInfo from the new OR clause.  We can assume it's valid
     264             :      * as a base restriction clause.
     265             :      */
     266         202 :     or_rinfo = make_restrictinfo(root,
     267             :                                  orclause,
     268             :                                  true,
     269             :                                  false,
     270             :                                  false,
     271             :                                  false,
     272             :                                  join_or_rinfo->security_level,
     273             :                                  NULL,
     274             :                                  NULL,
     275             :                                  NULL);
     276             : 
     277             :     /*
     278             :      * Estimate its selectivity.  (We could have done this earlier, but doing
     279             :      * it on the RestrictInfo representation allows the result to get cached,
     280             :      * saving work later.)
     281             :      */
     282         202 :     or_selec = clause_selectivity(root, (Node *) or_rinfo,
     283             :                                   0, JOIN_INNER, NULL);
     284             : 
     285             :     /*
     286             :      * The clause is only worth adding to the query if it rejects a useful
     287             :      * fraction of the base relation's rows; otherwise, it's just going to
     288             :      * cause duplicate computation (since we will still have to check the
     289             :      * original OR clause when the join is formed).  Somewhat arbitrarily, we
     290             :      * set the selectivity threshold at 0.9.
     291             :      */
     292         202 :     if (or_selec > 0.9)
     293           0 :         return;                 /* forget it */
     294             : 
     295             :     /*
     296             :      * OK, add it to the rel's restriction-clause list.
     297             :      */
     298         202 :     rel->baserestrictinfo = lappend(rel->baserestrictinfo, or_rinfo);
     299         202 :     rel->baserestrict_min_security = Min(rel->baserestrict_min_security,
     300             :                                          or_rinfo->security_level);
     301             : 
     302             :     /*
     303             :      * Adjust the original join OR clause's cached selectivity to compensate
     304             :      * for the selectivity of the added (but redundant) lower-level qual. This
     305             :      * should result in the join rel getting approximately the same rows
     306             :      * estimate as it would have gotten without all these shenanigans.
     307             :      *
     308             :      * XXX major hack alert: this depends on the assumption that the
     309             :      * selectivity will stay cached.
     310             :      *
     311             :      * XXX another major hack: we adjust only norm_selec, the cached
     312             :      * selectivity for JOIN_INNER semantics, even though the join clause
     313             :      * might've been an outer-join clause.  This is partly because we can't
     314             :      * easily identify the relevant SpecialJoinInfo here, and partly because
     315             :      * the linearity assumption we're making would fail anyway.  (If it is an
     316             :      * outer-join clause, "rel" must be on the nullable side, else we'd not
     317             :      * have gotten here.  So the computation of the join size is going to be
     318             :      * quite nonlinear with respect to the size of "rel", so it's not clear
     319             :      * how we ought to adjust outer_selec even if we could compute its
     320             :      * original value correctly.)
     321             :      */
     322         202 :     if (or_selec > 0)
     323             :     {
     324             :         SpecialJoinInfo sjinfo;
     325             : 
     326             :         /*
     327             :          * Make up a SpecialJoinInfo for JOIN_INNER semantics.  (Compare
     328             :          * approx_tuple_count() in costsize.c.)
     329             :          */
     330         202 :         sjinfo.type = T_SpecialJoinInfo;
     331         404 :         sjinfo.min_lefthand = bms_difference(join_or_rinfo->clause_relids,
     332         202 :                                              rel->relids);
     333         202 :         sjinfo.min_righthand = rel->relids;
     334         202 :         sjinfo.syn_lefthand = sjinfo.min_lefthand;
     335         202 :         sjinfo.syn_righthand = sjinfo.min_righthand;
     336         202 :         sjinfo.jointype = JOIN_INNER;
     337         202 :         sjinfo.ojrelid = 0;
     338         202 :         sjinfo.commute_above_l = NULL;
     339         202 :         sjinfo.commute_above_r = NULL;
     340         202 :         sjinfo.commute_below_l = NULL;
     341         202 :         sjinfo.commute_below_r = NULL;
     342             :         /* we don't bother trying to make the remaining fields valid */
     343         202 :         sjinfo.lhs_strict = false;
     344         202 :         sjinfo.semi_can_btree = false;
     345         202 :         sjinfo.semi_can_hash = false;
     346         202 :         sjinfo.semi_operators = NIL;
     347         202 :         sjinfo.semi_rhs_exprs = NIL;
     348             : 
     349             :         /* Compute inner-join size */
     350         202 :         orig_selec = clause_selectivity(root, (Node *) join_or_rinfo,
     351             :                                         0, JOIN_INNER, &sjinfo);
     352             : 
     353             :         /* And hack cached selectivity so join size remains the same */
     354         202 :         join_or_rinfo->norm_selec = orig_selec / or_selec;
     355             :         /* ensure result stays in sane range */
     356         202 :         if (join_or_rinfo->norm_selec > 1)
     357           0 :             join_or_rinfo->norm_selec = 1;
     358             :         /* as explained above, we don't touch outer_selec */
     359             :     }
     360             : }

Generated by: LCOV version 1.14