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