granicus.if.org Git - postgresql/blob - src/backend/optimizer/util/restrictinfo.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * restrictinfo.c
   4  *        RestrictInfo node manipulation routines.
   5  *
   6  * Portions Copyright (c) 1996-2018, PostgreSQL Global Development Group
   7  * Portions Copyright (c) 1994, Regents of the University of California
   8  *
   9  *
  10  * IDENTIFICATION
  11  *        src/backend/optimizer/util/restrictinfo.c
  12  *
  13  *-------------------------------------------------------------------------
  14  */
  15 #include "postgres.h"
  16
  17 #include "optimizer/clauses.h"
  18 #include "optimizer/restrictinfo.h"
  19 #include "optimizer/var.h"
  20
  21
  22 static RestrictInfo *make_restrictinfo_internal(Expr *clause,
  23                                                    Expr *orclause,
  24                                                    bool is_pushed_down,
  25                                                    bool outerjoin_delayed,
  26                                                    bool pseudoconstant,
  27                                                    Index security_level,
  28                                                    Relids required_relids,
  29                                                    Relids outer_relids,
  30                                                    Relids nullable_relids);
  31 static Expr *make_sub_restrictinfos(Expr *clause,
  32                                            bool is_pushed_down,
  33                                            bool outerjoin_delayed,
  34                                            bool pseudoconstant,
  35                                            Index security_level,
  36                                            Relids required_relids,
  37                                            Relids outer_relids,
  38                                            Relids nullable_relids);
  39
  40
  41 /*
  42  * make_restrictinfo
  43  *
  44  * Build a RestrictInfo node containing the given subexpression.
  45  *
  46  * The is_pushed_down, outerjoin_delayed, and pseudoconstant flags for the
  47  * RestrictInfo must be supplied by the caller, as well as the correct values
  48  * for security_level, outer_relids, and nullable_relids.
  49  * required_relids can be NULL, in which case it defaults to the actual clause
  50  * contents (i.e., clause_relids).
  51  *
  52  * We initialize fields that depend only on the given subexpression, leaving
  53  * others that depend on context (or may never be needed at all) to be filled
  54  * later.
  55  */
  56 RestrictInfo *
  57 make_restrictinfo(Expr *clause,
  58                                   bool is_pushed_down,
  59                                   bool outerjoin_delayed,
  60                                   bool pseudoconstant,
  61                                   Index security_level,
  62                                   Relids required_relids,
  63                                   Relids outer_relids,
  64                                   Relids nullable_relids)
  65 {
  66         /*
  67          * If it's an OR clause, build a modified copy with RestrictInfos inserted
  68          * above each subclause of the top-level AND/OR structure.
  69          */
  70         if (or_clause((Node *) clause))
  71                 return (RestrictInfo *) make_sub_restrictinfos(clause,
  72                                                                                                            is_pushed_down,
  73                                                                                                            outerjoin_delayed,
  74                                                                                                            pseudoconstant,
  75                                                                                                            security_level,
  76                                                                                                            required_relids,
  77                                                                                                            outer_relids,
  78                                                                                                            nullable_relids);
  79
  80         /* Shouldn't be an AND clause, else AND/OR flattening messed up */
  81         Assert(!and_clause((Node *) clause));
  82
  83         return make_restrictinfo_internal(clause,
  84                                                                           NULL,
  85                                                                           is_pushed_down,
  86                                                                           outerjoin_delayed,
  87                                                                           pseudoconstant,
  88                                                                           security_level,
  89                                                                           required_relids,
  90                                                                           outer_relids,
  91                                                                           nullable_relids);
  92 }
  93
  94 /*
  95  * make_restrictinfo_internal
  96  *
  97  * Common code for the main entry points and the recursive cases.
  98  */
  99 static RestrictInfo *
 100 make_restrictinfo_internal(Expr *clause,
 101                                                    Expr *orclause,
 102                                                    bool is_pushed_down,
 103                                                    bool outerjoin_delayed,
 104                                                    bool pseudoconstant,
 105                                                    Index security_level,
 106                                                    Relids required_relids,
 107                                                    Relids outer_relids,
 108                                                    Relids nullable_relids)
 109 {
 110         RestrictInfo *restrictinfo = makeNode(RestrictInfo);
 111
 112         restrictinfo->clause = clause;
 113         restrictinfo->orclause = orclause;
 114         restrictinfo->is_pushed_down = is_pushed_down;
 115         restrictinfo->outerjoin_delayed = outerjoin_delayed;
 116         restrictinfo->pseudoconstant = pseudoconstant;
 117         restrictinfo->can_join = false; /* may get set below */
 118         restrictinfo->security_level = security_level;
 119         restrictinfo->outer_relids = outer_relids;
 120         restrictinfo->nullable_relids = nullable_relids;
 121
 122         /*
 123          * If it's potentially delayable by lower-level security quals, figure out
 124          * whether it's leakproof.  We can skip testing this for level-zero quals,
 125          * since they would never get delayed on security grounds anyway.
 126          */
 127         if (security_level > 0)
 128                 restrictinfo->leakproof = !contain_leaked_vars((Node *) clause);
 129         else
 130                 restrictinfo->leakproof = false;        /* really, "don't know" */
 131
 132         /*
 133          * If it's a binary opclause, set up left/right relids info. In any case
 134          * set up the total clause relids info.
 135          */
 136         if (is_opclause(clause) && list_length(((OpExpr *) clause)->args) == 2)
 137         {
 138                 restrictinfo->left_relids = pull_varnos(get_leftop(clause));
 139                 restrictinfo->right_relids = pull_varnos(get_rightop(clause));
 140
 141                 restrictinfo->clause_relids = bms_union(restrictinfo->left_relids,
 142                                                                                                 restrictinfo->right_relids);
 143
 144                 /*
 145                  * Does it look like a normal join clause, i.e., a binary operator
 146                  * relating expressions that come from distinct relations? If so we
 147                  * might be able to use it in a join algorithm.  Note that this is a
 148                  * purely syntactic test that is made regardless of context.
 149                  */
 150                 if (!bms_is_empty(restrictinfo->left_relids) &&
 151                         !bms_is_empty(restrictinfo->right_relids) &&
 152                         !bms_overlap(restrictinfo->left_relids,
 153                                                  restrictinfo->right_relids))
 154                 {
 155                         restrictinfo->can_join = true;
 156                         /* pseudoconstant should certainly not be true */
 157                         Assert(!restrictinfo->pseudoconstant);
 158                 }
 159         }
 160         else
 161         {
 162                 /* Not a binary opclause, so mark left/right relid sets as empty */
 163                 restrictinfo->left_relids = NULL;
 164                 restrictinfo->right_relids = NULL;
 165                 /* and get the total relid set the hard way */
 166                 restrictinfo->clause_relids = pull_varnos((Node *) clause);
 167         }
 168
 169         /* required_relids defaults to clause_relids */
 170         if (required_relids != NULL)
 171                 restrictinfo->required_relids = required_relids;
 172         else
 173                 restrictinfo->required_relids = restrictinfo->clause_relids;
 174
 175         /*
 176          * Fill in all the cacheable fields with "not yet set" markers. None of
 177          * these will be computed until/unless needed.  Note in particular that we
 178          * don't mark a binary opclause as mergejoinable or hashjoinable here;
 179          * that happens only if it appears in the right context (top level of a
 180          * joinclause list).
 181          */
 182         restrictinfo->parent_ec = NULL;
 183
 184         restrictinfo->eval_cost.startup = -1;
 185         restrictinfo->norm_selec = -1;
 186         restrictinfo->outer_selec = -1;
 187
 188         restrictinfo->mergeopfamilies = NIL;
 189
 190         restrictinfo->left_ec = NULL;
 191         restrictinfo->right_ec = NULL;
 192         restrictinfo->left_em = NULL;
 193         restrictinfo->right_em = NULL;
 194         restrictinfo->scansel_cache = NIL;
 195
 196         restrictinfo->outer_is_left = false;
 197
 198         restrictinfo->hashjoinoperator = InvalidOid;
 199
 200         restrictinfo->left_bucketsize = -1;
 201         restrictinfo->right_bucketsize = -1;
 202         restrictinfo->left_mcvfreq = -1;
 203         restrictinfo->right_mcvfreq = -1;
 204
 205         return restrictinfo;
 206 }
 207
 208 /*
 209  * Recursively insert sub-RestrictInfo nodes into a boolean expression.
 210  *
 211  * We put RestrictInfos above simple (non-AND/OR) clauses and above
 212  * sub-OR clauses, but not above sub-AND clauses, because there's no need.
 213  * This may seem odd but it is closely related to the fact that we use
 214  * implicit-AND lists at top level of RestrictInfo lists.  Only ORs and
 215  * simple clauses are valid RestrictInfos.
 216  *
 217  * The same is_pushed_down, outerjoin_delayed, and pseudoconstant flag
 218  * values can be applied to all RestrictInfo nodes in the result.  Likewise
 219  * for security_level, outer_relids, and nullable_relids.
 220  *
 221  * The given required_relids are attached to our top-level output,
 222  * but any OR-clause constituents are allowed to default to just the
 223  * contained rels.
 224  */
 225 static Expr *
 226 make_sub_restrictinfos(Expr *clause,
 227                                            bool is_pushed_down,
 228                                            bool outerjoin_delayed,
 229                                            bool pseudoconstant,
 230                                            Index security_level,
 231                                            Relids required_relids,
 232                                            Relids outer_relids,
 233                                            Relids nullable_relids)
 234 {
 235         if (or_clause((Node *) clause))
 236         {
 237                 List       *orlist = NIL;
 238                 ListCell   *temp;
 239
 240                 foreach(temp, ((BoolExpr *) clause)->args)
 241                         orlist = lappend(orlist,
 242                                                          make_sub_restrictinfos(lfirst(temp),
 243                                                                                                         is_pushed_down,
 244                                                                                                         outerjoin_delayed,
 245                                                                                                         pseudoconstant,
 246                                                                                                         security_level,
 247                                                                                                         NULL,
 248                                                                                                         outer_relids,
 249                                                                                                         nullable_relids));
 250                 return (Expr *) make_restrictinfo_internal(clause,
 251                                                                                                    make_orclause(orlist),
 252                                                                                                    is_pushed_down,
 253                                                                                                    outerjoin_delayed,
 254                                                                                                    pseudoconstant,
 255                                                                                                    security_level,
 256                                                                                                    required_relids,
 257                                                                                                    outer_relids,
 258                                                                                                    nullable_relids);
 259         }
 260         else if (and_clause((Node *) clause))
 261         {
 262                 List       *andlist = NIL;
 263                 ListCell   *temp;
 264
 265                 foreach(temp, ((BoolExpr *) clause)->args)
 266                         andlist = lappend(andlist,
 267                                                           make_sub_restrictinfos(lfirst(temp),
 268                                                                                                          is_pushed_down,
 269                                                                                                          outerjoin_delayed,
 270                                                                                                          pseudoconstant,
 271                                                                                                          security_level,
 272                                                                                                          required_relids,
 273                                                                                                          outer_relids,
 274                                                                                                          nullable_relids));
 275                 return make_andclause(andlist);
 276         }
 277         else
 278                 return (Expr *) make_restrictinfo_internal(clause,
 279                                                                                                    NULL,
 280                                                                                                    is_pushed_down,
 281                                                                                                    outerjoin_delayed,
 282                                                                                                    pseudoconstant,
 283                                                                                                    security_level,
 284                                                                                                    required_relids,
 285                                                                                                    outer_relids,
 286                                                                                                    nullable_relids);
 287 }
 288
 289 /*
 290  * restriction_is_or_clause
 291  *
 292  * Returns t iff the restrictinfo node contains an 'or' clause.
 293  */
 294 bool
 295 restriction_is_or_clause(RestrictInfo *restrictinfo)
 296 {
 297         if (restrictinfo->orclause != NULL)
 298                 return true;
 299         else
 300                 return false;
 301 }
 302
 303 /*
 304  * restriction_is_securely_promotable
 305  *
 306  * Returns true if it's okay to evaluate this clause "early", that is before
 307  * other restriction clauses attached to the specified relation.
 308  */
 309 bool
 310 restriction_is_securely_promotable(RestrictInfo *restrictinfo,
 311                                                                    RelOptInfo *rel)
 312 {
 313         /*
 314          * It's okay if there are no baserestrictinfo clauses for the rel that
 315          * would need to go before this one, *or* if this one is leakproof.
 316          */
 317         if (restrictinfo->security_level <= rel->baserestrict_min_security ||
 318                 restrictinfo->leakproof)
 319                 return true;
 320         else
 321                 return false;
 322 }
 323
 324 /*
 325  * get_actual_clauses
 326  *
 327  * Returns a list containing the bare clauses from 'restrictinfo_list'.
 328  *
 329  * This is only to be used in cases where none of the RestrictInfos can
 330  * be pseudoconstant clauses (for instance, it's OK on indexqual lists).
 331  */
 332 List *
 333 get_actual_clauses(List *restrictinfo_list)
 334 {
 335         List       *result = NIL;
 336         ListCell   *l;
 337
 338         foreach(l, restrictinfo_list)
 339         {
 340                 RestrictInfo *rinfo = lfirst_node(RestrictInfo, l);
 341
 342                 Assert(!rinfo->pseudoconstant);
 343
 344                 result = lappend(result, rinfo->clause);
 345         }
 346         return result;
 347 }
 348
 349 /*
 350  * extract_actual_clauses
 351  *
 352  * Extract bare clauses from 'restrictinfo_list', returning either the
 353  * regular ones or the pseudoconstant ones per 'pseudoconstant'.
 354  */
 355 List *
 356 extract_actual_clauses(List *restrictinfo_list,
 357                                            bool pseudoconstant)
 358 {
 359         List       *result = NIL;
 360         ListCell   *l;
 361
 362         foreach(l, restrictinfo_list)
 363         {
 364                 RestrictInfo *rinfo = lfirst_node(RestrictInfo, l);
 365
 366                 if (rinfo->pseudoconstant == pseudoconstant)
 367                         result = lappend(result, rinfo->clause);
 368         }
 369         return result;
 370 }
 371
 372 /*
 373  * extract_actual_join_clauses
 374  *
 375  * Extract bare clauses from 'restrictinfo_list', separating those that
 376  * syntactically match the join level from those that were pushed down.
 377  * Pseudoconstant clauses are excluded from the results.
 378  *
 379  * This is only used at outer joins, since for plain joins we don't care
 380  * about pushed-down-ness.
 381  */
 382 void
 383 extract_actual_join_clauses(List *restrictinfo_list,
 384                                                         List **joinquals,
 385                                                         List **otherquals)
 386 {
 387         ListCell   *l;
 388
 389         *joinquals = NIL;
 390         *otherquals = NIL;
 391
 392         foreach(l, restrictinfo_list)
 393         {
 394                 RestrictInfo *rinfo = lfirst_node(RestrictInfo, l);
 395
 396                 if (rinfo->is_pushed_down)
 397                 {
 398                         if (!rinfo->pseudoconstant)
 399                                 *otherquals = lappend(*otherquals, rinfo->clause);
 400                 }
 401                 else
 402                 {
 403                         /* joinquals shouldn't have been marked pseudoconstant */
 404                         Assert(!rinfo->pseudoconstant);
 405                         *joinquals = lappend(*joinquals, rinfo->clause);
 406                 }
 407         }
 408 }
 409
 410
 411 /*
 412  * join_clause_is_movable_to
 413  *              Test whether a join clause is a safe candidate for parameterization
 414  *              of a scan on the specified base relation.
 415  *
 416  * A movable join clause is one that can safely be evaluated at a rel below
 417  * its normal semantic level (ie, its required_relids), if the values of
 418  * variables that it would need from other rels are provided.
 419  *
 420  * We insist that the clause actually reference the target relation; this
 421  * prevents undesirable movement of degenerate join clauses, and ensures
 422  * that there is a unique place that a clause can be moved down to.
 423  *
 424  * We cannot move an outer-join clause into the non-nullable side of its
 425  * outer join, as that would change the results (rows would be suppressed
 426  * rather than being null-extended).
 427  *
 428  * Also there must not be an outer join below the clause that would null the
 429  * Vars coming from the target relation.  Otherwise the clause might give
 430  * results different from what it would give at its normal semantic level.
 431  *
 432  * Also, the join clause must not use any relations that have LATERAL
 433  * references to the target relation, since we could not put such rels on
 434  * the outer side of a nestloop with the target relation.
 435  */
 436 bool
 437 join_clause_is_movable_to(RestrictInfo *rinfo, RelOptInfo *baserel)
 438 {
 439         /* Clause must physically reference target rel */
 440         if (!bms_is_member(baserel->relid, rinfo->clause_relids))
 441                 return false;
 442
 443         /* Cannot move an outer-join clause into the join's outer side */
 444         if (bms_is_member(baserel->relid, rinfo->outer_relids))
 445                 return false;
 446
 447         /* Target rel must not be nullable below the clause */
 448         if (bms_is_member(baserel->relid, rinfo->nullable_relids))
 449                 return false;
 450
 451         /* Clause must not use any rels with LATERAL references to this rel */
 452         if (bms_overlap(baserel->lateral_referencers, rinfo->clause_relids))
 453                 return false;
 454
 455         return true;
 456 }
 457
 458 /*
 459  * join_clause_is_movable_into
 460  *              Test whether a join clause is movable and can be evaluated within
 461  *              the current join context.
 462  *
 463  * currentrelids: the relids of the proposed evaluation location
 464  * current_and_outer: the union of currentrelids and the required_outer
 465  *              relids (parameterization's outer relations)
 466  *
 467  * The API would be a bit clearer if we passed the current relids and the
 468  * outer relids separately and did bms_union internally; but since most
 469  * callers need to apply this function to multiple clauses, we make the
 470  * caller perform the union.
 471  *
 472  * Obviously, the clause must only refer to Vars available from the current
 473  * relation plus the outer rels.  We also check that it does reference at
 474  * least one current Var, ensuring that the clause will be pushed down to
 475  * a unique place in a parameterized join tree.  And we check that we're
 476  * not pushing the clause into its outer-join outer side, nor down into
 477  * a lower outer join's inner side.
 478  *
 479  * The check about pushing a clause down into a lower outer join's inner side
 480  * is only approximate; it sometimes returns "false" when actually it would
 481  * be safe to use the clause here because we're still above the outer join
 482  * in question.  This is okay as long as the answers at different join levels
 483  * are consistent: it just means we might sometimes fail to push a clause as
 484  * far down as it could safely be pushed.  It's unclear whether it would be
 485  * worthwhile to do this more precisely.  (But if it's ever fixed to be
 486  * exactly accurate, there's an Assert in get_joinrel_parampathinfo() that
 487  * should be re-enabled.)
 488  *
 489  * There's no check here equivalent to join_clause_is_movable_to's test on
 490  * lateral_referencers.  We assume the caller wouldn't be inquiring unless
 491  * it'd verified that the proposed outer rels don't have lateral references
 492  * to the current rel(s).  (If we are considering join paths with the outer
 493  * rels on the outside and the current rels on the inside, then this should
 494  * have been checked at the outset of such consideration; see join_is_legal
 495  * and the path parameterization checks in joinpath.c.)  On the other hand,
 496  * in join_clause_is_movable_to we are asking whether the clause could be
 497  * moved for some valid set of outer rels, so we don't have the benefit of
 498  * relying on prior checks for lateral-reference validity.
 499  *
 500  * Note: if this returns true, it means that the clause could be moved to
 501  * this join relation, but that doesn't mean that this is the lowest join
 502  * it could be moved to.  Caller may need to make additional calls to verify
 503  * that this doesn't succeed on either of the inputs of a proposed join.
 504  *
 505  * Note: get_joinrel_parampathinfo depends on the fact that if
 506  * current_and_outer is NULL, this function will always return false
 507  * (since one or the other of the first two tests must fail).
 508  */
 509 bool
 510 join_clause_is_movable_into(RestrictInfo *rinfo,
 511                                                         Relids currentrelids,
 512                                                         Relids current_and_outer)
 513 {
 514         /* Clause must be evaluable given available context */
 515         if (!bms_is_subset(rinfo->clause_relids, current_and_outer))
 516                 return false;
 517
 518         /* Clause must physically reference at least one target rel */
 519         if (!bms_overlap(currentrelids, rinfo->clause_relids))
 520                 return false;
 521
 522         /* Cannot move an outer-join clause into the join's outer side */
 523         if (bms_overlap(currentrelids, rinfo->outer_relids))
 524                 return false;
 525
 526         /*
 527          * Target rel(s) must not be nullable below the clause.  This is
 528          * approximate, in the safe direction, because the current join might be
 529          * above the join where the nulling would happen, in which case the clause
 530          * would work correctly here.  But we don't have enough info to be sure.
 531          */
 532         if (bms_overlap(currentrelids, rinfo->nullable_relids))
 533                 return false;
 534
 535         return true;
 536 }