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-2017, 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
 203         return restrictinfo;
 204 }
 205
 206 /*
 207  * Recursively insert sub-RestrictInfo nodes into a boolean expression.
 208  *
 209  * We put RestrictInfos above simple (non-AND/OR) clauses and above
 210  * sub-OR clauses, but not above sub-AND clauses, because there's no need.
 211  * This may seem odd but it is closely related to the fact that we use
 212  * implicit-AND lists at top level of RestrictInfo lists.  Only ORs and
 213  * simple clauses are valid RestrictInfos.
 214  *
 215  * The same is_pushed_down, outerjoin_delayed, and pseudoconstant flag
 216  * values can be applied to all RestrictInfo nodes in the result.  Likewise
 217  * for security_level, outer_relids, and nullable_relids.
 218  *
 219  * The given required_relids are attached to our top-level output,
 220  * but any OR-clause constituents are allowed to default to just the
 221  * contained rels.
 222  */
 223 static Expr *
 224 make_sub_restrictinfos(Expr *clause,
 225                                            bool is_pushed_down,
 226                                            bool outerjoin_delayed,
 227                                            bool pseudoconstant,
 228                                            Index security_level,
 229                                            Relids required_relids,
 230                                            Relids outer_relids,
 231                                            Relids nullable_relids)
 232 {
 233         if (or_clause((Node *) clause))
 234         {
 235                 List       *orlist = NIL;
 236                 ListCell   *temp;
 237
 238                 foreach(temp, ((BoolExpr *) clause)->args)
 239                         orlist = lappend(orlist,
 240                                                          make_sub_restrictinfos(lfirst(temp),
 241                                                                                                         is_pushed_down,
 242                                                                                                         outerjoin_delayed,
 243                                                                                                         pseudoconstant,
 244                                                                                                         security_level,
 245                                                                                                         NULL,
 246                                                                                                         outer_relids,
 247                                                                                                         nullable_relids));
 248                 return (Expr *) make_restrictinfo_internal(clause,
 249                                                                                                    make_orclause(orlist),
 250                                                                                                    is_pushed_down,
 251                                                                                                    outerjoin_delayed,
 252                                                                                                    pseudoconstant,
 253                                                                                                    security_level,
 254                                                                                                    required_relids,
 255                                                                                                    outer_relids,
 256                                                                                                    nullable_relids);
 257         }
 258         else if (and_clause((Node *) clause))
 259         {
 260                 List       *andlist = NIL;
 261                 ListCell   *temp;
 262
 263                 foreach(temp, ((BoolExpr *) clause)->args)
 264                         andlist = lappend(andlist,
 265                                                           make_sub_restrictinfos(lfirst(temp),
 266                                                                                                          is_pushed_down,
 267                                                                                                          outerjoin_delayed,
 268                                                                                                          pseudoconstant,
 269                                                                                                          security_level,
 270                                                                                                          required_relids,
 271                                                                                                          outer_relids,
 272                                                                                                          nullable_relids));
 273                 return make_andclause(andlist);
 274         }
 275         else
 276                 return (Expr *) make_restrictinfo_internal(clause,
 277                                                                                                    NULL,
 278                                                                                                    is_pushed_down,
 279                                                                                                    outerjoin_delayed,
 280                                                                                                    pseudoconstant,
 281                                                                                                    security_level,
 282                                                                                                    required_relids,
 283                                                                                                    outer_relids,
 284                                                                                                    nullable_relids);
 285 }
 286
 287 /*
 288  * restriction_is_or_clause
 289  *
 290  * Returns t iff the restrictinfo node contains an 'or' clause.
 291  */
 292 bool
 293 restriction_is_or_clause(RestrictInfo *restrictinfo)
 294 {
 295         if (restrictinfo->orclause != NULL)
 296                 return true;
 297         else
 298                 return false;
 299 }
 300
 301 /*
 302  * restriction_is_securely_promotable
 303  *
 304  * Returns true if it's okay to evaluate this clause "early", that is before
 305  * other restriction clauses attached to the specified relation.
 306  */
 307 bool
 308 restriction_is_securely_promotable(RestrictInfo *restrictinfo,
 309                                                                    RelOptInfo *rel)
 310 {
 311         /*
 312          * It's okay if there are no baserestrictinfo clauses for the rel that
 313          * would need to go before this one, *or* if this one is leakproof.
 314          */
 315         if (restrictinfo->security_level <= rel->baserestrict_min_security ||
 316                 restrictinfo->leakproof)
 317                 return true;
 318         else
 319                 return false;
 320 }
 321
 322 /*
 323  * get_actual_clauses
 324  *
 325  * Returns a list containing the bare clauses from 'restrictinfo_list'.
 326  *
 327  * This is only to be used in cases where none of the RestrictInfos can
 328  * be pseudoconstant clauses (for instance, it's OK on indexqual lists).
 329  */
 330 List *
 331 get_actual_clauses(List *restrictinfo_list)
 332 {
 333         List       *result = NIL;
 334         ListCell   *l;
 335
 336         foreach(l, restrictinfo_list)
 337         {
 338                 RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
 339
 340                 Assert(IsA(rinfo, RestrictInfo));
 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 = (RestrictInfo *) lfirst(l);
 365
 366                 Assert(IsA(rinfo, RestrictInfo));
 367
 368                 if (rinfo->pseudoconstant == pseudoconstant)
 369                         result = lappend(result, rinfo->clause);
 370         }
 371         return result;
 372 }
 373
 374 /*
 375  * extract_actual_join_clauses
 376  *
 377  * Extract bare clauses from 'restrictinfo_list', separating those that
 378  * syntactically match the join level from those that were pushed down.
 379  * Pseudoconstant clauses are excluded from the results.
 380  *
 381  * This is only used at outer joins, since for plain joins we don't care
 382  * about pushed-down-ness.
 383  */
 384 void
 385 extract_actual_join_clauses(List *restrictinfo_list,
 386                                                         List **joinquals,
 387                                                         List **otherquals)
 388 {
 389         ListCell   *l;
 390
 391         *joinquals = NIL;
 392         *otherquals = NIL;
 393
 394         foreach(l, restrictinfo_list)
 395         {
 396                 RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
 397
 398                 Assert(IsA(rinfo, RestrictInfo));
 399
 400                 if (rinfo->is_pushed_down)
 401                 {
 402                         if (!rinfo->pseudoconstant)
 403                                 *otherquals = lappend(*otherquals, rinfo->clause);
 404                 }
 405                 else
 406                 {
 407                         /* joinquals shouldn't have been marked pseudoconstant */
 408                         Assert(!rinfo->pseudoconstant);
 409                         *joinquals = lappend(*joinquals, rinfo->clause);
 410                 }
 411         }
 412 }
 413
 414
 415 /*
 416  * join_clause_is_movable_to
 417  *              Test whether a join clause is a safe candidate for parameterization
 418  *              of a scan on the specified base relation.
 419  *
 420  * A movable join clause is one that can safely be evaluated at a rel below
 421  * its normal semantic level (ie, its required_relids), if the values of
 422  * variables that it would need from other rels are provided.
 423  *
 424  * We insist that the clause actually reference the target relation; this
 425  * prevents undesirable movement of degenerate join clauses, and ensures
 426  * that there is a unique place that a clause can be moved down to.
 427  *
 428  * We cannot move an outer-join clause into the non-nullable side of its
 429  * outer join, as that would change the results (rows would be suppressed
 430  * rather than being null-extended).
 431  *
 432  * Also there must not be an outer join below the clause that would null the
 433  * Vars coming from the target relation.  Otherwise the clause might give
 434  * results different from what it would give at its normal semantic level.
 435  *
 436  * Also, the join clause must not use any relations that have LATERAL
 437  * references to the target relation, since we could not put such rels on
 438  * the outer side of a nestloop with the target relation.
 439  */
 440 bool
 441 join_clause_is_movable_to(RestrictInfo *rinfo, RelOptInfo *baserel)
 442 {
 443         /* Clause must physically reference target rel */
 444         if (!bms_is_member(baserel->relid, rinfo->clause_relids))
 445                 return false;
 446
 447         /* Cannot move an outer-join clause into the join's outer side */
 448         if (bms_is_member(baserel->relid, rinfo->outer_relids))
 449                 return false;
 450
 451         /* Target rel must not be nullable below the clause */
 452         if (bms_is_member(baserel->relid, rinfo->nullable_relids))
 453                 return false;
 454
 455         /* Clause must not use any rels with LATERAL references to this rel */
 456         if (bms_overlap(baserel->lateral_referencers, rinfo->clause_relids))
 457                 return false;
 458
 459         return true;
 460 }
 461
 462 /*
 463  * join_clause_is_movable_into
 464  *              Test whether a join clause is movable and can be evaluated within
 465  *              the current join context.
 466  *
 467  * currentrelids: the relids of the proposed evaluation location
 468  * current_and_outer: the union of currentrelids and the required_outer
 469  *              relids (parameterization's outer relations)
 470  *
 471  * The API would be a bit clearer if we passed the current relids and the
 472  * outer relids separately and did bms_union internally; but since most
 473  * callers need to apply this function to multiple clauses, we make the
 474  * caller perform the union.
 475  *
 476  * Obviously, the clause must only refer to Vars available from the current
 477  * relation plus the outer rels.  We also check that it does reference at
 478  * least one current Var, ensuring that the clause will be pushed down to
 479  * a unique place in a parameterized join tree.  And we check that we're
 480  * not pushing the clause into its outer-join outer side, nor down into
 481  * a lower outer join's inner side.
 482  *
 483  * The check about pushing a clause down into a lower outer join's inner side
 484  * is only approximate; it sometimes returns "false" when actually it would
 485  * be safe to use the clause here because we're still above the outer join
 486  * in question.  This is okay as long as the answers at different join levels
 487  * are consistent: it just means we might sometimes fail to push a clause as
 488  * far down as it could safely be pushed.  It's unclear whether it would be
 489  * worthwhile to do this more precisely.  (But if it's ever fixed to be
 490  * exactly accurate, there's an Assert in get_joinrel_parampathinfo() that
 491  * should be re-enabled.)
 492  *
 493  * There's no check here equivalent to join_clause_is_movable_to's test on
 494  * lateral_referencers.  We assume the caller wouldn't be inquiring unless
 495  * it'd verified that the proposed outer rels don't have lateral references
 496  * to the current rel(s).  (If we are considering join paths with the outer
 497  * rels on the outside and the current rels on the inside, then this should
 498  * have been checked at the outset of such consideration; see join_is_legal
 499  * and the path parameterization checks in joinpath.c.)  On the other hand,
 500  * in join_clause_is_movable_to we are asking whether the clause could be
 501  * moved for some valid set of outer rels, so we don't have the benefit of
 502  * relying on prior checks for lateral-reference validity.
 503  *
 504  * Note: if this returns true, it means that the clause could be moved to
 505  * this join relation, but that doesn't mean that this is the lowest join
 506  * it could be moved to.  Caller may need to make additional calls to verify
 507  * that this doesn't succeed on either of the inputs of a proposed join.
 508  *
 509  * Note: get_joinrel_parampathinfo depends on the fact that if
 510  * current_and_outer is NULL, this function will always return false
 511  * (since one or the other of the first two tests must fail).
 512  */
 513 bool
 514 join_clause_is_movable_into(RestrictInfo *rinfo,
 515                                                         Relids currentrelids,
 516                                                         Relids current_and_outer)
 517 {
 518         /* Clause must be evaluable given available context */
 519         if (!bms_is_subset(rinfo->clause_relids, current_and_outer))
 520                 return false;
 521
 522         /* Clause must physically reference at least one target rel */
 523         if (!bms_overlap(currentrelids, rinfo->clause_relids))
 524                 return false;
 525
 526         /* Cannot move an outer-join clause into the join's outer side */
 527         if (bms_overlap(currentrelids, rinfo->outer_relids))
 528                 return false;
 529
 530         /*
 531          * Target rel(s) must not be nullable below the clause.  This is
 532          * approximate, in the safe direction, because the current join might be
 533          * above the join where the nulling would happen, in which case the clause
 534          * would work correctly here.  But we don't have enough info to be sure.
 535          */
 536         if (bms_overlap(currentrelids, rinfo->nullable_relids))
 537                 return false;
 538
 539         return true;
 540 }