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-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/util/restrictinfo.c,v 1.36 2005/06/05 22:32:56 tgl Exp $
  12  *
  13  *-------------------------------------------------------------------------
  14  */
  15 #include "postgres.h"
  16
  17 #include "optimizer/clauses.h"
  18 #include "optimizer/cost.h"
  19 #include "optimizer/paths.h"
  20 #include "optimizer/restrictinfo.h"
  21 #include "optimizer/var.h"
  22
  23
  24 static RestrictInfo *make_restrictinfo_internal(Expr *clause,
  25                                                    Expr *orclause,
  26                                                    bool is_pushed_down,
  27                                                    bool valid_everywhere);
  28 static Expr *make_sub_restrictinfos(Expr *clause,
  29                                            bool is_pushed_down,
  30                                            bool valid_everywhere);
  31 static RestrictInfo *join_clause_is_redundant(PlannerInfo *root,
  32                                                  RestrictInfo *rinfo,
  33                                                  List *reference_list,
  34                                                  bool isouterjoin);
  35
  36
  37 /*
  38  * make_restrictinfo
  39  *
  40  * Build a RestrictInfo node containing the given subexpression.
  41  *
  42  * The is_pushed_down and valid_everywhere flags must be supplied by the
  43  * caller.
  44  *
  45  * We initialize fields that depend only on the given subexpression, leaving
  46  * others that depend on context (or may never be needed at all) to be filled
  47  * later.
  48  */
  49 RestrictInfo *
  50 make_restrictinfo(Expr *clause, bool is_pushed_down, bool valid_everywhere)
  51 {
  52         /*
  53          * If it's an OR clause, build a modified copy with RestrictInfos
  54          * inserted above each subclause of the top-level AND/OR structure.
  55          */
  56         if (or_clause((Node *) clause))
  57                 return (RestrictInfo *) make_sub_restrictinfos(clause,
  58                                                                                                            is_pushed_down,
  59                                                                                                            valid_everywhere);
  60
  61         /* Shouldn't be an AND clause, else AND/OR flattening messed up */
  62         Assert(!and_clause((Node *) clause));
  63
  64         return make_restrictinfo_internal(clause, NULL,
  65                                                                           is_pushed_down, valid_everywhere);
  66 }
  67
  68 /*
  69  * make_restrictinfo_from_bitmapqual
  70  *
  71  * Given the bitmapqual Path structure for a bitmap indexscan, generate
  72  * RestrictInfo node(s) equivalent to the condition represented by the
  73  * indexclauses of the Path structure.
  74  *
  75  * The result is a List since we might need to return multiple RestrictInfos.
  76  *
  77  * To do this through the normal make_restrictinfo() API, callers would have
  78  * to strip off the RestrictInfo nodes present in the indexclauses lists, and
  79  * then make_restrictinfo() would have to build new ones.  It's better to have
  80  * a specialized routine to allow sharing of RestrictInfos.
  81  */
  82 List *
  83 make_restrictinfo_from_bitmapqual(Path *bitmapqual,
  84                                                                   bool is_pushed_down,
  85                                                                   bool valid_everywhere)
  86 {
  87         List       *result;
  88
  89         if (IsA(bitmapqual, BitmapAndPath))
  90         {
  91                 BitmapAndPath *apath = (BitmapAndPath *) bitmapqual;
  92                 ListCell   *l;
  93
  94                 result = NIL;
  95                 foreach(l, apath->bitmapquals)
  96                 {
  97                         List       *sublist;
  98
  99                         sublist = make_restrictinfo_from_bitmapqual((Path *) lfirst(l),
 100                                                                                                                 is_pushed_down,
 101                                                                                                                 valid_everywhere);
 102                         result = list_concat(result, sublist);
 103                 }
 104         }
 105         else if (IsA(bitmapqual, BitmapOrPath))
 106         {
 107                 BitmapOrPath *opath = (BitmapOrPath *) bitmapqual;
 108                 List       *withris = NIL;
 109                 List       *withoutris = NIL;
 110                 ListCell   *l;
 111
 112                 foreach(l, opath->bitmapquals)
 113                 {
 114                         List       *sublist;
 115
 116                         sublist = make_restrictinfo_from_bitmapqual((Path *) lfirst(l),
 117                                                                                                                 is_pushed_down,
 118                                                                                                                 valid_everywhere);
 119                         if (sublist == NIL)
 120                         {
 121                                 /* constant TRUE input yields constant TRUE OR result */
 122                                 /* (though this probably cannot happen) */
 123                                 return NIL;
 124                         }
 125                         /* Create AND subclause with RestrictInfos */
 126                         withris = lappend(withris, make_ands_explicit(sublist));
 127                         /* And one without */
 128                         sublist = get_actual_clauses(sublist);
 129                         withoutris = lappend(withoutris, make_ands_explicit(sublist));
 130                 }
 131                 /* Here's the magic part not available to outside callers */
 132                 result =
 133                         list_make1(make_restrictinfo_internal(make_orclause(withoutris),
 134                                                                                                   make_orclause(withris),
 135                                                                                                   is_pushed_down,
 136                                                                                                   valid_everywhere));
 137         }
 138         else if (IsA(bitmapqual, IndexPath))
 139         {
 140                 IndexPath *ipath = (IndexPath *) bitmapqual;
 141
 142                 result = list_copy(ipath->indexclauses);
 143         }
 144         else
 145         {
 146                 elog(ERROR, "unrecognized node type: %d", nodeTag(bitmapqual));
 147                 result = NIL;                   /* keep compiler quiet */
 148         }
 149
 150         return result;
 151 }
 152
 153 /*
 154  * make_restrictinfo_internal
 155  *
 156  * Common code for the main entry points and the recursive cases.
 157  */
 158 static RestrictInfo *
 159 make_restrictinfo_internal(Expr *clause, Expr *orclause,
 160                                                    bool is_pushed_down, bool valid_everywhere)
 161 {
 162         RestrictInfo *restrictinfo = makeNode(RestrictInfo);
 163
 164         restrictinfo->clause = clause;
 165         restrictinfo->orclause = orclause;
 166         restrictinfo->is_pushed_down = is_pushed_down;
 167         restrictinfo->valid_everywhere = valid_everywhere;
 168         restrictinfo->can_join = false;         /* may get set below */
 169
 170         /*
 171          * If it's a binary opclause, set up left/right relids info. In any
 172          * case set up the total clause relids info.
 173          */
 174         if (is_opclause(clause) && list_length(((OpExpr *) clause)->args) == 2)
 175         {
 176                 restrictinfo->left_relids = pull_varnos(get_leftop(clause));
 177                 restrictinfo->right_relids = pull_varnos(get_rightop(clause));
 178
 179                 restrictinfo->clause_relids = bms_union(restrictinfo->left_relids,
 180                                                                                          restrictinfo->right_relids);
 181
 182                 /*
 183                  * Does it look like a normal join clause, i.e., a binary operator
 184                  * relating expressions that come from distinct relations? If so
 185                  * we might be able to use it in a join algorithm.      Note that this
 186                  * is a purely syntactic test that is made regardless of context.
 187                  */
 188                 if (!bms_is_empty(restrictinfo->left_relids) &&
 189                         !bms_is_empty(restrictinfo->right_relids) &&
 190                         !bms_overlap(restrictinfo->left_relids,
 191                                                  restrictinfo->right_relids))
 192                         restrictinfo->can_join = true;
 193         }
 194         else
 195         {
 196                 /* Not a binary opclause, so mark left/right relid sets as empty */
 197                 restrictinfo->left_relids = NULL;
 198                 restrictinfo->right_relids = NULL;
 199                 /* and get the total relid set the hard way */
 200                 restrictinfo->clause_relids = pull_varnos((Node *) clause);
 201         }
 202
 203         /*
 204          * Fill in all the cacheable fields with "not yet set" markers. None
 205          * of these will be computed until/unless needed.  Note in particular
 206          * that we don't mark a binary opclause as mergejoinable or
 207          * hashjoinable here; that happens only if it appears in the right
 208          * context (top level of a joinclause list).
 209          */
 210         restrictinfo->eval_cost.startup = -1;
 211         restrictinfo->this_selec = -1;
 212
 213         restrictinfo->mergejoinoperator = InvalidOid;
 214         restrictinfo->left_sortop = InvalidOid;
 215         restrictinfo->right_sortop = InvalidOid;
 216
 217         restrictinfo->left_pathkey = NIL;
 218         restrictinfo->right_pathkey = NIL;
 219
 220         restrictinfo->left_mergescansel = -1;
 221         restrictinfo->right_mergescansel = -1;
 222
 223         restrictinfo->hashjoinoperator = InvalidOid;
 224
 225         restrictinfo->left_bucketsize = -1;
 226         restrictinfo->right_bucketsize = -1;
 227
 228         return restrictinfo;
 229 }
 230
 231 /*
 232  * Recursively insert sub-RestrictInfo nodes into a boolean expression.
 233  *
 234  * We put RestrictInfos above simple (non-AND/OR) clauses and above
 235  * sub-OR clauses, but not above sub-AND clauses, because there's no need.
 236  * This may seem odd but it is closely related to the fact that we use
 237  * implicit-AND lists at top level of RestrictInfo lists.  Only ORs and
 238  * simple clauses are valid RestrictInfos.
 239  */
 240 static Expr *
 241 make_sub_restrictinfos(Expr *clause, bool is_pushed_down,
 242                                            bool valid_everywhere)
 243 {
 244         if (or_clause((Node *) clause))
 245         {
 246                 List       *orlist = NIL;
 247                 ListCell   *temp;
 248
 249                 foreach(temp, ((BoolExpr *) clause)->args)
 250                         orlist = lappend(orlist,
 251                                                          make_sub_restrictinfos(lfirst(temp),
 252                                                                                                         is_pushed_down,
 253                                                                                                         valid_everywhere));
 254                 return (Expr *) make_restrictinfo_internal(clause,
 255                                                                                                    make_orclause(orlist),
 256                                                                                                    is_pushed_down,
 257                                                                                                    valid_everywhere);
 258         }
 259         else if (and_clause((Node *) clause))
 260         {
 261                 List       *andlist = NIL;
 262                 ListCell   *temp;
 263
 264                 foreach(temp, ((BoolExpr *) clause)->args)
 265                         andlist = lappend(andlist,
 266                                                           make_sub_restrictinfos(lfirst(temp),
 267                                                                                                          is_pushed_down,
 268                                                                                                          valid_everywhere));
 269                 return make_andclause(andlist);
 270         }
 271         else
 272                 return (Expr *) make_restrictinfo_internal(clause,
 273                                                                                                    NULL,
 274                                                                                                    is_pushed_down,
 275                                                                                                    valid_everywhere);
 276 }
 277
 278 /*
 279  * restriction_is_or_clause
 280  *
 281  * Returns t iff the restrictinfo node contains an 'or' clause.
 282  */
 283 bool
 284 restriction_is_or_clause(RestrictInfo *restrictinfo)
 285 {
 286         if (restrictinfo->orclause != NULL)
 287                 return true;
 288         else
 289                 return false;
 290 }
 291
 292 /*
 293  * get_actual_clauses
 294  *
 295  * Returns a list containing the bare clauses from 'restrictinfo_list'.
 296  */
 297 List *
 298 get_actual_clauses(List *restrictinfo_list)
 299 {
 300         List       *result = NIL;
 301         ListCell   *temp;
 302
 303         foreach(temp, restrictinfo_list)
 304         {
 305                 RestrictInfo *rinfo = (RestrictInfo *) lfirst(temp);
 306
 307                 Assert(IsA(rinfo, RestrictInfo));
 308
 309                 result = lappend(result, rinfo->clause);
 310         }
 311         return result;
 312 }
 313
 314 /*
 315  * get_actual_join_clauses
 316  *
 317  * Extract clauses from 'restrictinfo_list', separating those that
 318  * syntactically match the join level from those that were pushed down.
 319  */
 320 void
 321 get_actual_join_clauses(List *restrictinfo_list,
 322                                                 List **joinquals, List **otherquals)
 323 {
 324         ListCell   *temp;
 325
 326         *joinquals = NIL;
 327         *otherquals = NIL;
 328
 329         foreach(temp, restrictinfo_list)
 330         {
 331                 RestrictInfo *clause = (RestrictInfo *) lfirst(temp);
 332
 333                 if (clause->is_pushed_down)
 334                         *otherquals = lappend(*otherquals, clause->clause);
 335                 else
 336                         *joinquals = lappend(*joinquals, clause->clause);
 337         }
 338 }
 339
 340 /*
 341  * remove_redundant_join_clauses
 342  *
 343  * Given a list of RestrictInfo clauses that are to be applied in a join,
 344  * remove any duplicate or redundant clauses.
 345  *
 346  * We must eliminate duplicates when forming the restrictlist for a joinrel,
 347  * since we will see many of the same clauses arriving from both input
 348  * relations. Also, if a clause is a mergejoinable clause, it's possible that
 349  * it is redundant with previous clauses (see optimizer/README for
 350  * discussion). We detect that case and omit the redundant clause from the
 351  * result list.
 352  *
 353  * The result is a fresh List, but it points to the same member nodes
 354  * as were in the input.
 355  */
 356 List *
 357 remove_redundant_join_clauses(PlannerInfo *root, List *restrictinfo_list,
 358                                                           bool isouterjoin)
 359 {
 360         List       *result = NIL;
 361         ListCell   *item;
 362         QualCost        cost;
 363
 364         /*
 365          * If there are any redundant clauses, we want to eliminate the ones
 366          * that are more expensive in favor of the ones that are less so. Run
 367          * cost_qual_eval() to ensure the eval_cost fields are set up.
 368          */
 369         cost_qual_eval(&cost, restrictinfo_list);
 370
 371         /*
 372          * We don't have enough knowledge yet to be able to estimate the
 373          * number of times a clause might be evaluated, so it's hard to weight
 374          * the startup and per-tuple costs appropriately.  For now just weight
 375          * 'em the same.
 376          */
 377 #define CLAUSECOST(r)  ((r)->eval_cost.startup + (r)->eval_cost.per_tuple)
 378
 379         foreach(item, restrictinfo_list)
 380         {
 381                 RestrictInfo *rinfo = (RestrictInfo *) lfirst(item);
 382                 RestrictInfo *prevrinfo;
 383
 384                 /* is it redundant with any prior clause? */
 385                 prevrinfo = join_clause_is_redundant(root, rinfo, result, isouterjoin);
 386                 if (prevrinfo == NULL)
 387                 {
 388                         /* no, so add it to result list */
 389                         result = lappend(result, rinfo);
 390                 }
 391                 else if (CLAUSECOST(rinfo) < CLAUSECOST(prevrinfo))
 392                 {
 393                         /* keep this one, drop the previous one */
 394                         result = list_delete_ptr(result, prevrinfo);
 395                         result = lappend(result, rinfo);
 396                 }
 397                 /* else, drop this one */
 398         }
 399
 400         return result;
 401 }
 402
 403 /*
 404  * select_nonredundant_join_clauses
 405  *
 406  * Given a list of RestrictInfo clauses that are to be applied in a join,
 407  * select the ones that are not redundant with any clause in the
 408  * reference_list.
 409  *
 410  * This is similar to remove_redundant_join_clauses, but we are looking for
 411  * redundancies with a separate list of clauses (i.e., clauses that have
 412  * already been applied below the join itself).
 413  *
 414  * Note that we assume the given restrictinfo_list has already been checked
 415  * for local redundancies, so we don't check again.
 416  */
 417 List *
 418 select_nonredundant_join_clauses(PlannerInfo *root,
 419                                                                  List *restrictinfo_list,
 420                                                                  List *reference_list,
 421                                                                  bool isouterjoin)
 422 {
 423         List       *result = NIL;
 424         ListCell   *item;
 425
 426         foreach(item, restrictinfo_list)
 427         {
 428                 RestrictInfo *rinfo = (RestrictInfo *) lfirst(item);
 429
 430                 /* drop it if redundant with any reference clause */
 431                 if (join_clause_is_redundant(root, rinfo, reference_list, isouterjoin) != NULL)
 432                         continue;
 433
 434                 /* otherwise, add it to result list */
 435                 result = lappend(result, rinfo);
 436         }
 437
 438         return result;
 439 }
 440
 441 /*
 442  * join_clause_is_redundant
 443  *              If rinfo is redundant with any clause in reference_list,
 444  *              return one such clause; otherwise return NULL.
 445  *
 446  * This is the guts of both remove_redundant_join_clauses and
 447  * select_nonredundant_join_clauses.  See the docs above for motivation.
 448  *
 449  * We can detect redundant mergejoinable clauses very cheaply by using their
 450  * left and right pathkeys, which uniquely identify the sets of equijoined
 451  * variables in question.  All the members of a pathkey set that are in the
 452  * left relation have already been forced to be equal; likewise for those in
 453  * the right relation.  So, we need to have only one clause that checks
 454  * equality between any set member on the left and any member on the right;
 455  * by transitivity, all the rest are then equal.
 456  *
 457  * However, clauses that are of the form "var expr = const expr" cannot be
 458  * eliminated as redundant.  This is because when there are const expressions
 459  * in a pathkey set, generate_implied_equalities() suppresses "var = var"
 460  * clauses in favor of "var = const" clauses.  We cannot afford to drop any
 461  * of the latter, even though they might seem redundant by the pathkey
 462  * membership test.
 463  *
 464  * Weird special case: if we have two clauses that seem redundant
 465  * except one is pushed down into an outer join and the other isn't,
 466  * then they're not really redundant, because one constrains the
 467  * joined rows after addition of null fill rows, and the other doesn't.
 468  */
 469 static RestrictInfo *
 470 join_clause_is_redundant(PlannerInfo *root,
 471                                                  RestrictInfo *rinfo,
 472                                                  List *reference_list,
 473                                                  bool isouterjoin)
 474 {
 475         ListCell   *refitem;
 476
 477         /* always consider exact duplicates redundant */
 478         foreach(refitem, reference_list)
 479         {
 480                 RestrictInfo *refrinfo = (RestrictInfo *) lfirst(refitem);
 481
 482                 if (equal(rinfo, refrinfo))
 483                         return refrinfo;
 484         }
 485
 486         /* check for redundant merge clauses */
 487         if (rinfo->mergejoinoperator != InvalidOid)
 488         {
 489                 /* do the cheap test first: is it a "var = const" clause? */
 490                 if (bms_is_empty(rinfo->left_relids) ||
 491                         bms_is_empty(rinfo->right_relids))
 492                         return NULL;            /* var = const, so not redundant */
 493
 494                 cache_mergeclause_pathkeys(root, rinfo);
 495
 496                 foreach(refitem, reference_list)
 497                 {
 498                         RestrictInfo *refrinfo = (RestrictInfo *) lfirst(refitem);
 499
 500                         if (refrinfo->mergejoinoperator != InvalidOid)
 501                         {
 502                                 cache_mergeclause_pathkeys(root, refrinfo);
 503
 504                                 if (rinfo->left_pathkey == refrinfo->left_pathkey &&
 505                                         rinfo->right_pathkey == refrinfo->right_pathkey &&
 506                                         (rinfo->is_pushed_down == refrinfo->is_pushed_down ||
 507                                          !isouterjoin))
 508                                 {
 509                                         /* Yup, it's redundant */
 510                                         return refrinfo;
 511                                 }
 512                         }
 513                 }
 514         }
 515
 516         /* otherwise, not redundant */
 517         return NULL;
 518 }