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

   1 /*-------------------------------------------------------------------------
   2  *
   3  * plancat.c
   4  *         routines for accessing the system catalogs
   5  *
   6  *
   7  * Portions Copyright (c) 1996-2007, PostgreSQL Global Development Group
   8  * Portions Copyright (c) 1994, Regents of the University of California
   9  *
  10  *
  11  * IDENTIFICATION
  12  *        $PostgreSQL: pgsql/src/backend/optimizer/util/plancat.c,v 1.135 2007/05/25 17:54:25 tgl Exp $
  13  *
  14  *-------------------------------------------------------------------------
  15  */
  16 #include "postgres.h"
  17
  18 #include <math.h>
  19
  20 #include "access/genam.h"
  21 #include "access/heapam.h"
  22 #include "catalog/pg_inherits.h"
  23 #include "nodes/makefuncs.h"
  24 #include "optimizer/clauses.h"
  25 #include "optimizer/plancat.h"
  26 #include "optimizer/predtest.h"
  27 #include "optimizer/prep.h"
  28 #include "parser/parse_expr.h"
  29 #include "parser/parse_relation.h"
  30 #include "parser/parsetree.h"
  31 #include "rewrite/rewriteManip.h"
  32 #include "utils/fmgroids.h"
  33 #include "utils/lsyscache.h"
  34 #include "utils/relcache.h"
  35 #include "utils/syscache.h"
  36 #include "catalog/catalog.h"
  37 #include "miscadmin.h"
  38
  39
  40 /* GUC parameter */
  41 bool            constraint_exclusion = false;
  42
  43 /* Hook for plugins to get control in get_relation_info() */
  44 get_relation_info_hook_type get_relation_info_hook = NULL;
  45
  46
  47 static void estimate_rel_size(Relation rel, int32 *attr_widths,
  48                                   BlockNumber *pages, double *tuples);
  49 static List *get_relation_constraints(Oid relationObjectId, RelOptInfo *rel);
  50
  51
  52 /*
  53  * get_relation_info -
  54  *        Retrieves catalog information for a given relation.
  55  *
  56  * Given the Oid of the relation, return the following info into fields
  57  * of the RelOptInfo struct:
  58  *
  59  *      min_attr        lowest valid AttrNumber
  60  *      max_attr        highest valid AttrNumber
  61  *      indexlist       list of IndexOptInfos for relation's indexes
  62  *      pages           number of pages
  63  *      tuples          number of tuples
  64  *
  65  * Also, initialize the attr_needed[] and attr_widths[] arrays.  In most
  66  * cases these are left as zeroes, but sometimes we need to compute attr
  67  * widths here, and we may as well cache the results for costsize.c.
  68  *
  69  * If inhparent is true, all we need to do is set up the attr arrays:
  70  * the RelOptInfo actually represents the appendrel formed by an inheritance
  71  * tree, and so the parent rel's physical size and index information isn't
  72  * important for it.
  73  */
  74 void
  75 get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
  76                                   RelOptInfo *rel)
  77 {
  78         Index           varno = rel->relid;
  79         Relation        relation;
  80         bool            hasindex;
  81         List       *indexinfos = NIL;
  82
  83         /*
  84          * We need not lock the relation since it was already locked, either by
  85          * the rewriter or when expand_inherited_rtentry() added it to the query's
  86          * rangetable.
  87          */
  88         relation = heap_open(relationObjectId, NoLock);
  89
  90         rel->min_attr = FirstLowInvalidHeapAttributeNumber + 1;
  91         rel->max_attr = RelationGetNumberOfAttributes(relation);
  92
  93         Assert(rel->max_attr >= rel->min_attr);
  94         rel->attr_needed = (Relids *)
  95                 palloc0((rel->max_attr - rel->min_attr + 1) * sizeof(Relids));
  96         rel->attr_widths = (int32 *)
  97                 palloc0((rel->max_attr - rel->min_attr + 1) * sizeof(int32));
  98
  99         /*
 100          * Estimate relation size --- unless it's an inheritance parent, in which
 101          * case the size will be computed later in set_append_rel_pathlist, and we
 102          * must leave it zero for now to avoid bollixing the total_table_pages
 103          * calculation.
 104          */
 105         if (!inhparent)
 106                 estimate_rel_size(relation, rel->attr_widths - rel->min_attr,
 107                                                   &rel->pages, &rel->tuples);
 108
 109         /*
 110          * Make list of indexes.  Ignore indexes on system catalogs if told to.
 111          * Don't bother with indexes for an inheritance parent, either.
 112          */
 113         if (inhparent ||
 114                 (IgnoreSystemIndexes && IsSystemClass(relation->rd_rel)))
 115                 hasindex = false;
 116         else
 117                 hasindex = relation->rd_rel->relhasindex;
 118
 119         if (hasindex)
 120         {
 121                 List       *indexoidlist;
 122                 ListCell   *l;
 123                 LOCKMODE        lmode;
 124
 125                 indexoidlist = RelationGetIndexList(relation);
 126
 127                 /*
 128                  * For each index, we get the same type of lock that the executor will
 129                  * need, and do not release it.  This saves a couple of trips to the
 130                  * shared lock manager while not creating any real loss of
 131                  * concurrency, because no schema changes could be happening on the
 132                  * index while we hold lock on the parent rel, and neither lock type
 133                  * blocks any other kind of index operation.
 134                  */
 135                 if (rel->relid == root->parse->resultRelation)
 136                         lmode = RowExclusiveLock;
 137                 else
 138                         lmode = AccessShareLock;
 139
 140                 foreach(l, indexoidlist)
 141                 {
 142                         Oid                     indexoid = lfirst_oid(l);
 143                         Relation        indexRelation;
 144                         Form_pg_index index;
 145                         IndexOptInfo *info;
 146                         int                     ncolumns;
 147                         int                     i;
 148
 149                         /*
 150                          * Extract info from the relation descriptor for the index.
 151                          */
 152                         indexRelation = index_open(indexoid, lmode);
 153                         index = indexRelation->rd_index;
 154
 155                         /*
 156                          * Ignore invalid indexes, since they can't safely be used for
 157                          * queries.  Note that this is OK because the data structure we
 158                          * are constructing is only used by the planner --- the executor
 159                          * still needs to insert into "invalid" indexes!
 160                          */
 161                         if (!index->indisvalid)
 162                         {
 163                                 index_close(indexRelation, NoLock);
 164                                 continue;
 165                         }
 166
 167                         info = makeNode(IndexOptInfo);
 168
 169                         info->indexoid = index->indexrelid;
 170                         info->rel = rel;
 171                         info->ncolumns = ncolumns = index->indnatts;
 172
 173                         /*
 174                          * Need to make opfamily array large enough to put a terminating
 175                          * zero at the end.
 176                          */
 177                         info->indexkeys = (int *) palloc(sizeof(int) * ncolumns);
 178                         info->opfamily = (Oid *) palloc0(sizeof(Oid) * (ncolumns + 1));
 179                         /* initialize these to zeroes in case index is unordered */
 180                         info->fwdsortop = (Oid *) palloc0(sizeof(Oid) * ncolumns);
 181                         info->revsortop = (Oid *) palloc0(sizeof(Oid) * ncolumns);
 182                         info->nulls_first = (bool *) palloc0(sizeof(bool) * ncolumns);
 183
 184                         for (i = 0; i < ncolumns; i++)
 185                         {
 186                                 info->opfamily[i] = indexRelation->rd_opfamily[i];
 187                                 info->indexkeys[i] = index->indkey.values[i];
 188                         }
 189
 190                         info->relam = indexRelation->rd_rel->relam;
 191                         info->amcostestimate = indexRelation->rd_am->amcostestimate;
 192                         info->amoptionalkey = indexRelation->rd_am->amoptionalkey;
 193                         info->amsearchnulls = indexRelation->rd_am->amsearchnulls;
 194
 195                         /*
 196                          * Fetch the ordering operators associated with the index, if any.
 197                          * We expect that all ordering-capable indexes use btree's
 198                          * strategy numbers for the ordering operators.
 199                          */
 200                         if (indexRelation->rd_am->amcanorder)
 201                         {
 202                                 int                     nstrat = indexRelation->rd_am->amstrategies;
 203
 204                                 for (i = 0; i < ncolumns; i++)
 205                                 {
 206                                         int16   opt = indexRelation->rd_indoption[i];
 207                                         int             fwdstrat;
 208                                         int             revstrat;
 209
 210                                         if (opt & INDOPTION_DESC)
 211                                         {
 212                                                 fwdstrat = BTGreaterStrategyNumber;
 213                                                 revstrat = BTLessStrategyNumber;
 214                                         }
 215                                         else
 216                                         {
 217                                                 fwdstrat = BTLessStrategyNumber;
 218                                                 revstrat = BTGreaterStrategyNumber;
 219                                         }
 220                                         /*
 221                                          * Index AM must have a fixed set of strategies for it
 222                                          * to make sense to specify amcanorder, so we
 223                                          * need not allow the case amstrategies == 0.
 224                                          */
 225                                         if (fwdstrat > 0)
 226                                         {
 227                                                 Assert(fwdstrat <= nstrat);
 228                                                 info->fwdsortop[i] = indexRelation->rd_operator[i * nstrat + fwdstrat - 1];
 229                                         }
 230                                         if (revstrat > 0)
 231                                         {
 232                                                 Assert(revstrat <= nstrat);
 233                                                 info->revsortop[i] = indexRelation->rd_operator[i * nstrat + revstrat - 1];
 234                                         }
 235                                         info->nulls_first[i] = (opt & INDOPTION_NULLS_FIRST) != 0;
 236                                 }
 237                         }
 238
 239                         /*
 240                          * Fetch the index expressions and predicate, if any.  We must
 241                          * modify the copies we obtain from the relcache to have the
 242                          * correct varno for the parent relation, so that they match up
 243                          * correctly against qual clauses.
 244                          */
 245                         info->indexprs = RelationGetIndexExpressions(indexRelation);
 246                         info->indpred = RelationGetIndexPredicate(indexRelation);
 247                         if (info->indexprs && varno != 1)
 248                                 ChangeVarNodes((Node *) info->indexprs, 1, varno, 0);
 249                         if (info->indpred && varno != 1)
 250                                 ChangeVarNodes((Node *) info->indpred, 1, varno, 0);
 251                         info->predOK = false;           /* set later in indxpath.c */
 252                         info->unique = index->indisunique;
 253
 254                         /*
 255                          * Estimate the index size.  If it's not a partial index, we lock
 256                          * the number-of-tuples estimate to equal the parent table; if it
 257                          * is partial then we have to use the same methods as we would for
 258                          * a table, except we can be sure that the index is not larger
 259                          * than the table.
 260                          */
 261                         if (info->indpred == NIL)
 262                         {
 263                                 info->pages = RelationGetNumberOfBlocks(indexRelation);
 264                                 info->tuples = rel->tuples;
 265                         }
 266                         else
 267                         {
 268                                 estimate_rel_size(indexRelation, NULL,
 269                                                                   &info->pages, &info->tuples);
 270                                 if (info->tuples > rel->tuples)
 271                                         info->tuples = rel->tuples;
 272                         }
 273
 274                         index_close(indexRelation, NoLock);
 275
 276                         indexinfos = lcons(info, indexinfos);
 277                 }
 278
 279                 list_free(indexoidlist);
 280         }
 281
 282         rel->indexlist = indexinfos;
 283
 284         heap_close(relation, NoLock);
 285
 286         /*
 287          * Allow a plugin to editorialize on the info we obtained from the
 288          * catalogs.  Actions might include altering the assumed relation size,
 289          * removing an index, or adding a hypothetical index to the indexlist.
 290          */
 291         if (get_relation_info_hook)
 292                 (*get_relation_info_hook) (root, relationObjectId, inhparent, rel);
 293 }
 294
 295 /*
 296  * estimate_rel_size - estimate # pages and # tuples in a table or index
 297  *
 298  * If attr_widths isn't NULL, it points to the zero-index entry of the
 299  * relation's attr_width[] cache; we fill this in if we have need to compute
 300  * the attribute widths for estimation purposes.
 301  */
 302 static void
 303 estimate_rel_size(Relation rel, int32 *attr_widths,
 304                                   BlockNumber *pages, double *tuples)
 305 {
 306         BlockNumber curpages;
 307         BlockNumber relpages;
 308         double          reltuples;
 309         double          density;
 310
 311         switch (rel->rd_rel->relkind)
 312         {
 313                 case RELKIND_RELATION:
 314                 case RELKIND_INDEX:
 315                 case RELKIND_TOASTVALUE:
 316                         /* it has storage, ok to call the smgr */
 317                         curpages = RelationGetNumberOfBlocks(rel);
 318
 319                         /*
 320                          * HACK: if the relation has never yet been vacuumed, use a
 321                          * minimum estimate of 10 pages.  This emulates a desirable aspect
 322                          * of pre-8.0 behavior, which is that we wouldn't assume a newly
 323                          * created relation is really small, which saves us from making
 324                          * really bad plans during initial data loading.  (The plans are
 325                          * not wrong when they are made, but if they are cached and used
 326                          * again after the table has grown a lot, they are bad.) It would
 327                          * be better to force replanning if the table size has changed a
 328                          * lot since the plan was made ... but we don't currently have any
 329                          * infrastructure for redoing cached plans at all, so we have to
 330                          * kluge things here instead.
 331                          *
 332                          * We approximate "never vacuumed" by "has relpages = 0", which
 333                          * means this will also fire on genuinely empty relations.      Not
 334                          * great, but fortunately that's a seldom-seen case in the real
 335                          * world, and it shouldn't degrade the quality of the plan too
 336                          * much anyway to err in this direction.
 337                          */
 338                         if (curpages < 10 && rel->rd_rel->relpages == 0)
 339                                 curpages = 10;
 340
 341                         /* report estimated # pages */
 342                         *pages = curpages;
 343                         /* quick exit if rel is clearly empty */
 344                         if (curpages == 0)
 345                         {
 346                                 *tuples = 0;
 347                                 break;
 348                         }
 349                         /* coerce values in pg_class to more desirable types */
 350                         relpages = (BlockNumber) rel->rd_rel->relpages;
 351                         reltuples = (double) rel->rd_rel->reltuples;
 352
 353                         /*
 354                          * If it's an index, discount the metapage.  This is a kluge
 355                          * because it assumes more than it ought to about index contents;
 356                          * it's reasonably OK for btrees but a bit suspect otherwise.
 357                          */
 358                         if (rel->rd_rel->relkind == RELKIND_INDEX &&
 359                                 relpages > 0)
 360                         {
 361                                 curpages--;
 362                                 relpages--;
 363                         }
 364                         /* estimate number of tuples from previous tuple density */
 365                         if (relpages > 0)
 366                                 density = reltuples / (double) relpages;
 367                         else
 368                         {
 369                                 /*
 370                                  * When we have no data because the relation was truncated,
 371                                  * estimate tuple width from attribute datatypes.  We assume
 372                                  * here that the pages are completely full, which is OK for
 373                                  * tables (since they've presumably not been VACUUMed yet) but
 374                                  * is probably an overestimate for indexes.  Fortunately
 375                                  * get_relation_info() can clamp the overestimate to the
 376                                  * parent table's size.
 377                                  *
 378                                  * Note: this code intentionally disregards alignment
 379                                  * considerations, because (a) that would be gilding the lily
 380                                  * considering how crude the estimate is, and (b) it creates
 381                                  * platform dependencies in the default plans which are kind
 382                                  * of a headache for regression testing.
 383                                  */
 384                                 int32           tuple_width = 0;
 385                                 int                     i;
 386
 387                                 for (i = 1; i <= RelationGetNumberOfAttributes(rel); i++)
 388                                 {
 389                                         Form_pg_attribute att = rel->rd_att->attrs[i - 1];
 390                                         int32           item_width;
 391
 392                                         if (att->attisdropped)
 393                                                 continue;
 394                                         /* This should match set_rel_width() in costsize.c */
 395                                         item_width = get_attavgwidth(RelationGetRelid(rel), i);
 396                                         if (item_width <= 0)
 397                                         {
 398                                                 item_width = get_typavgwidth(att->atttypid,
 399                                                                                                          att->atttypmod);
 400                                                 Assert(item_width > 0);
 401                                         }
 402                                         if (attr_widths != NULL)
 403                                                 attr_widths[i] = item_width;
 404                                         tuple_width += item_width;
 405                                 }
 406                                 tuple_width += sizeof(HeapTupleHeaderData);
 407                                 tuple_width += sizeof(ItemPointerData);
 408                                 /* note: integer division is intentional here */
 409                                 density = (BLCKSZ - sizeof(PageHeaderData)) / tuple_width;
 410                         }
 411                         *tuples = rint(density * (double) curpages);
 412                         break;
 413                 case RELKIND_SEQUENCE:
 414                         /* Sequences always have a known size */
 415                         *pages = 1;
 416                         *tuples = 1;
 417                         break;
 418                 default:
 419                         /* else it has no disk storage; probably shouldn't get here? */
 420                         *pages = 0;
 421                         *tuples = 0;
 422                         break;
 423         }
 424 }
 425
 426
 427 /*
 428  * get_relation_constraints
 429  *
 430  * Retrieve the CHECK constraint expressions of the given relation.
 431  *
 432  * Returns a List (possibly empty) of constraint expressions.  Each one
 433  * has been canonicalized, and its Vars are changed to have the varno
 434  * indicated by rel->relid.  This allows the expressions to be easily
 435  * compared to expressions taken from WHERE.
 436  *
 437  * Note: at present this is invoked at most once per relation per planner
 438  * run, and in many cases it won't be invoked at all, so there seems no
 439  * point in caching the data in RelOptInfo.
 440  */
 441 static List *
 442 get_relation_constraints(Oid relationObjectId, RelOptInfo *rel)
 443 {
 444         List       *result = NIL;
 445         Index           varno = rel->relid;
 446         Relation        relation;
 447         TupleConstr *constr;
 448
 449         /*
 450          * We assume the relation has already been safely locked.
 451          */
 452         relation = heap_open(relationObjectId, NoLock);
 453
 454         constr = relation->rd_att->constr;
 455         if (constr != NULL)
 456         {
 457                 int                     num_check = constr->num_check;
 458                 int                     i;
 459
 460                 for (i = 0; i < num_check; i++)
 461                 {
 462                         Node       *cexpr;
 463
 464                         cexpr = stringToNode(constr->check[i].ccbin);
 465
 466                         /*
 467                          * Run each expression through const-simplification and
 468                          * canonicalization.  This is not just an optimization, but is
 469                          * necessary, because we will be comparing it to
 470                          * similarly-processed qual clauses, and may fail to detect valid
 471                          * matches without this.  This must match the processing done to
 472                          * qual clauses in preprocess_expression()!  (We can skip the
 473                          * stuff involving subqueries, however, since we don't allow any
 474                          * in check constraints.)
 475                          */
 476                         cexpr = eval_const_expressions(cexpr);
 477
 478                         cexpr = (Node *) canonicalize_qual((Expr *) cexpr);
 479
 480                         /*
 481                          * Also mark any coercion format fields as "don't care", so that
 482                          * we can match to both explicit and implicit coercions.
 483                          */
 484                         set_coercionform_dontcare(cexpr);
 485
 486                         /* Fix Vars to have the desired varno */
 487                         if (varno != 1)
 488                                 ChangeVarNodes(cexpr, 1, varno, 0);
 489
 490                         /*
 491                          * Finally, convert to implicit-AND format (that is, a List) and
 492                          * append the resulting item(s) to our output list.
 493                          */
 494                         result = list_concat(result,
 495                                                                  make_ands_implicit((Expr *) cexpr));
 496                 }
 497         }
 498
 499         heap_close(relation, NoLock);
 500
 501         return result;
 502 }
 503
 504
 505 /*
 506  * relation_excluded_by_constraints
 507  *
 508  * Detect whether the relation need not be scanned because it has either
 509  * self-inconsistent restrictions, or restrictions inconsistent with the
 510  * relation's CHECK constraints.
 511  *
 512  * Note: this examines only rel->relid and rel->baserestrictinfo; therefore
 513  * it can be called before filling in other fields of the RelOptInfo.
 514  */
 515 bool
 516 relation_excluded_by_constraints(RelOptInfo *rel, RangeTblEntry *rte)
 517 {
 518         List       *safe_restrictions;
 519         List       *constraint_pred;
 520         List       *safe_constraints;
 521         ListCell   *lc;
 522
 523         /* Skip the test if constraint exclusion is disabled */
 524         if (!constraint_exclusion)
 525                 return false;
 526
 527         /*
 528          * Check for self-contradictory restriction clauses.  We dare not make
 529          * deductions with non-immutable functions, but any immutable clauses that
 530          * are self-contradictory allow us to conclude the scan is unnecessary.
 531          *
 532          * Note: strip off RestrictInfo because predicate_refuted_by() isn't
 533          * expecting to see any in its predicate argument.
 534          */
 535         safe_restrictions = NIL;
 536         foreach(lc, rel->baserestrictinfo)
 537         {
 538                 RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
 539
 540                 if (!contain_mutable_functions((Node *) rinfo->clause))
 541                         safe_restrictions = lappend(safe_restrictions, rinfo->clause);
 542         }
 543
 544         if (predicate_refuted_by(safe_restrictions, safe_restrictions))
 545                 return true;
 546
 547         /* Only plain relations have constraints */
 548         if (rte->rtekind != RTE_RELATION || rte->inh)
 549                 return false;
 550
 551         /* OK to fetch the constraint expressions */
 552         constraint_pred = get_relation_constraints(rte->relid, rel);
 553
 554         /*
 555          * We do not currently enforce that CHECK constraints contain only
 556          * immutable functions, so it's necessary to check here. We daren't draw
 557          * conclusions from plan-time evaluation of non-immutable functions. Since
 558          * they're ANDed, we can just ignore any mutable constraints in the list,
 559          * and reason about the rest.
 560          */
 561         safe_constraints = NIL;
 562         foreach(lc, constraint_pred)
 563         {
 564                 Node       *pred = (Node *) lfirst(lc);
 565
 566                 if (!contain_mutable_functions(pred))
 567                         safe_constraints = lappend(safe_constraints, pred);
 568         }
 569
 570         /*
 571          * The constraints are effectively ANDed together, so we can just try to
 572          * refute the entire collection at once.  This may allow us to make proofs
 573          * that would fail if we took them individually.
 574          *
 575          * Note: we use rel->baserestrictinfo, not safe_restrictions as might seem
 576          * an obvious optimization.  Some of the clauses might be OR clauses that
 577          * have volatile and nonvolatile subclauses, and it's OK to make
 578          * deductions with the nonvolatile parts.
 579          */
 580         if (predicate_refuted_by(safe_constraints, rel->baserestrictinfo))
 581                 return true;
 582
 583         return false;
 584 }
 585
 586
 587 /*
 588  * build_physical_tlist
 589  *
 590  * Build a targetlist consisting of exactly the relation's user attributes,
 591  * in order.  The executor can special-case such tlists to avoid a projection
 592  * step at runtime, so we use such tlists preferentially for scan nodes.
 593  *
 594  * Exception: if there are any dropped columns, we punt and return NIL.
 595  * Ideally we would like to handle the dropped-column case too.  However this
 596  * creates problems for ExecTypeFromTL, which may be asked to build a tupdesc
 597  * for a tlist that includes vars of no-longer-existent types.  In theory we
 598  * could dig out the required info from the pg_attribute entries of the
 599  * relation, but that data is not readily available to ExecTypeFromTL.
 600  * For now, we don't apply the physical-tlist optimization when there are
 601  * dropped cols.
 602  *
 603  * We also support building a "physical" tlist for subqueries, functions,
 604  * and values lists, since the same optimization can occur in SubqueryScan,
 605  * FunctionScan, and ValuesScan nodes.
 606  */
 607 List *
 608 build_physical_tlist(PlannerInfo *root, RelOptInfo *rel)
 609 {
 610         List       *tlist = NIL;
 611         Index           varno = rel->relid;
 612         RangeTblEntry *rte = planner_rt_fetch(varno, root);
 613         Relation        relation;
 614         Query      *subquery;
 615         Var                *var;
 616         ListCell   *l;
 617         int                     attrno,
 618                                 numattrs;
 619         List       *colvars;
 620
 621         switch (rte->rtekind)
 622         {
 623                 case RTE_RELATION:
 624                         /* Assume we already have adequate lock */
 625                         relation = heap_open(rte->relid, NoLock);
 626
 627                         numattrs = RelationGetNumberOfAttributes(relation);
 628                         for (attrno = 1; attrno <= numattrs; attrno++)
 629                         {
 630                                 Form_pg_attribute att_tup = relation->rd_att->attrs[attrno - 1];
 631
 632                                 if (att_tup->attisdropped)
 633                                 {
 634                                         /* found a dropped col, so punt */
 635                                         tlist = NIL;
 636                                         break;
 637                                 }
 638
 639                                 var = makeVar(varno,
 640                                                           attrno,
 641                                                           att_tup->atttypid,
 642                                                           att_tup->atttypmod,
 643                                                           0);
 644
 645                                 tlist = lappend(tlist,
 646                                                                 makeTargetEntry((Expr *) var,
 647                                                                                                 attrno,
 648                                                                                                 NULL,
 649                                                                                                 false));
 650                         }
 651
 652                         heap_close(relation, NoLock);
 653                         break;
 654
 655                 case RTE_SUBQUERY:
 656                         subquery = rte->subquery;
 657                         foreach(l, subquery->targetList)
 658                         {
 659                                 TargetEntry *tle = (TargetEntry *) lfirst(l);
 660
 661                                 /*
 662                                  * A resjunk column of the subquery can be reflected as
 663                                  * resjunk in the physical tlist; we need not punt.
 664                                  */
 665                                 var = makeVar(varno,
 666                                                           tle->resno,
 667                                                           exprType((Node *) tle->expr),
 668                                                           exprTypmod((Node *) tle->expr),
 669                                                           0);
 670
 671                                 tlist = lappend(tlist,
 672                                                                 makeTargetEntry((Expr *) var,
 673                                                                                                 tle->resno,
 674                                                                                                 NULL,
 675                                                                                                 tle->resjunk));
 676                         }
 677                         break;
 678
 679                 case RTE_FUNCTION:
 680                         expandRTE(rte, varno, 0, true /* include dropped */ ,
 681                                           NULL, &colvars);
 682                         foreach(l, colvars)
 683                         {
 684                                 var = (Var *) lfirst(l);
 685
 686                                 /*
 687                                  * A non-Var in expandRTE's output means a dropped column;
 688                                  * must punt.
 689                                  */
 690                                 if (!IsA(var, Var))
 691                                 {
 692                                         tlist = NIL;
 693                                         break;
 694                                 }
 695
 696                                 tlist = lappend(tlist,
 697                                                                 makeTargetEntry((Expr *) var,
 698                                                                                                 var->varattno,
 699                                                                                                 NULL,
 700                                                                                                 false));
 701                         }
 702                         break;
 703
 704                 case RTE_VALUES:
 705                         expandRTE(rte, varno, 0, false /* dropped not applicable */ ,
 706                                           NULL, &colvars);
 707                         foreach(l, colvars)
 708                         {
 709                                 var = (Var *) lfirst(l);
 710
 711                                 tlist = lappend(tlist,
 712                                                                 makeTargetEntry((Expr *) var,
 713                                                                                                 var->varattno,
 714                                                                                                 NULL,
 715                                                                                                 false));
 716                         }
 717                         break;
 718
 719                 default:
 720                         /* caller error */
 721                         elog(ERROR, "unsupported RTE kind %d in build_physical_tlist",
 722                                  (int) rte->rtekind);
 723                         break;
 724         }
 725
 726         return tlist;
 727 }
 728
 729 /*
 730  * restriction_selectivity
 731  *
 732  * Returns the selectivity of a specified restriction operator clause.
 733  * This code executes registered procedures stored in the
 734  * operator relation, by calling the function manager.
 735  *
 736  * See clause_selectivity() for the meaning of the additional parameters.
 737  */
 738 Selectivity
 739 restriction_selectivity(PlannerInfo *root,
 740                                                 Oid operator,
 741                                                 List *args,
 742                                                 int varRelid)
 743 {
 744         RegProcedure oprrest = get_oprrest(operator);
 745         float8          result;
 746
 747         /*
 748          * if the oprrest procedure is missing for whatever reason, use a
 749          * selectivity of 0.5
 750          */
 751         if (!oprrest)
 752                 return (Selectivity) 0.5;
 753
 754         result = DatumGetFloat8(OidFunctionCall4(oprrest,
 755                                                                                          PointerGetDatum(root),
 756                                                                                          ObjectIdGetDatum(operator),
 757                                                                                          PointerGetDatum(args),
 758                                                                                          Int32GetDatum(varRelid)));
 759
 760         if (result < 0.0 || result > 1.0)
 761                 elog(ERROR, "invalid restriction selectivity: %f", result);
 762
 763         return (Selectivity) result;
 764 }
 765
 766 /*
 767  * join_selectivity
 768  *
 769  * Returns the selectivity of a specified join operator clause.
 770  * This code executes registered procedures stored in the
 771  * operator relation, by calling the function manager.
 772  */
 773 Selectivity
 774 join_selectivity(PlannerInfo *root,
 775                                  Oid operator,
 776                                  List *args,
 777                                  JoinType jointype)
 778 {
 779         RegProcedure oprjoin = get_oprjoin(operator);
 780         float8          result;
 781
 782         /*
 783          * if the oprjoin procedure is missing for whatever reason, use a
 784          * selectivity of 0.5
 785          */
 786         if (!oprjoin)
 787                 return (Selectivity) 0.5;
 788
 789         result = DatumGetFloat8(OidFunctionCall4(oprjoin,
 790                                                                                          PointerGetDatum(root),
 791                                                                                          ObjectIdGetDatum(operator),
 792                                                                                          PointerGetDatum(args),
 793                                                                                          Int16GetDatum(jointype)));
 794
 795         if (result < 0.0 || result > 1.0)
 796                 elog(ERROR, "invalid join selectivity: %f", result);
 797
 798         return (Selectivity) result;
 799 }
 800
 801 /*
 802  * find_inheritance_children
 803  *
 804  * Returns a list containing the OIDs of all relations which
 805  * inherit *directly* from the relation with OID 'inhparent'.
 806  *
 807  * XXX might be a good idea to create an index on pg_inherits' inhparent
 808  * field, so that we can use an indexscan instead of sequential scan here.
 809  * However, in typical databases pg_inherits won't have enough entries to
 810  * justify an indexscan...
 811  */
 812 List *
 813 find_inheritance_children(Oid inhparent)
 814 {
 815         List       *list = NIL;
 816         Relation        relation;
 817         HeapScanDesc scan;
 818         HeapTuple       inheritsTuple;
 819         Oid                     inhrelid;
 820         ScanKeyData key[1];
 821
 822         /*
 823          * Can skip the scan if pg_class shows the relation has never had a
 824          * subclass.
 825          */
 826         if (!has_subclass(inhparent))
 827                 return NIL;
 828
 829         ScanKeyInit(&key[0],
 830                                 Anum_pg_inherits_inhparent,
 831                                 BTEqualStrategyNumber, F_OIDEQ,
 832                                 ObjectIdGetDatum(inhparent));
 833         relation = heap_open(InheritsRelationId, AccessShareLock);
 834         scan = heap_beginscan(relation, SnapshotNow, 1, key);
 835         while ((inheritsTuple = heap_getnext(scan, ForwardScanDirection)) != NULL)
 836         {
 837                 inhrelid = ((Form_pg_inherits) GETSTRUCT(inheritsTuple))->inhrelid;
 838                 list = lappend_oid(list, inhrelid);
 839         }
 840         heap_endscan(scan);
 841         heap_close(relation, AccessShareLock);
 842         return list;
 843 }
 844
 845 /*
 846  * has_subclass
 847  *
 848  * In the current implementation, has_subclass returns whether a
 849  * particular class *might* have a subclass. It will not return the
 850  * correct result if a class had a subclass which was later dropped.
 851  * This is because relhassubclass in pg_class is not updated when a
 852  * subclass is dropped, primarily because of concurrency concerns.
 853  *
 854  * Currently has_subclass is only used as an efficiency hack to skip
 855  * unnecessary inheritance searches, so this is OK.
 856  */
 857 bool
 858 has_subclass(Oid relationId)
 859 {
 860         HeapTuple       tuple;
 861         bool            result;
 862
 863         tuple = SearchSysCache(RELOID,
 864                                                    ObjectIdGetDatum(relationId),
 865                                                    0, 0, 0);
 866         if (!HeapTupleIsValid(tuple))
 867                 elog(ERROR, "cache lookup failed for relation %u", relationId);
 868
 869         result = ((Form_pg_class) GETSTRUCT(tuple))->relhassubclass;
 870         ReleaseSysCache(tuple);
 871         return result;
 872 }
 873
 874 /*
 875  * has_unique_index
 876  *
 877  * Detect whether there is a unique index on the specified attribute
 878  * of the specified relation, thus allowing us to conclude that all
 879  * the (non-null) values of the attribute are distinct.
 880  */
 881 bool
 882 has_unique_index(RelOptInfo *rel, AttrNumber attno)
 883 {
 884         ListCell   *ilist;
 885
 886         foreach(ilist, rel->indexlist)
 887         {
 888                 IndexOptInfo *index = (IndexOptInfo *) lfirst(ilist);
 889
 890                 /*
 891                  * Note: ignore partial indexes, since they don't allow us to conclude
 892                  * that all attr values are distinct.  We don't take any interest in
 893                  * expressional indexes either. Also, a multicolumn unique index
 894                  * doesn't allow us to conclude that just the specified attr is
 895                  * unique.
 896                  */
 897                 if (index->unique &&
 898                         index->ncolumns == 1 &&
 899                         index->indexkeys[0] == attno &&
 900                         index->indpred == NIL)
 901                         return true;
 902         }
 903         return false;
 904 }