src/include/nodes/plannodes.h

   1 /*-------------------------------------------------------------------------
   2  *
   3  * plannodes.h
   4  *        definitions for query plan nodes
   5  *
   6  *
   7  * Portions Copyright (c) 1996-2009, PostgreSQL Global Development Group
   8  * Portions Copyright (c) 1994, Regents of the University of California
   9  *
  10  * $PostgreSQL$
  11  *
  12  *-------------------------------------------------------------------------
  13  */
  14 #ifndef PLANNODES_H
  15 #define PLANNODES_H
  16
  17 #include "access/sdir.h"
  18 #include "nodes/bitmapset.h"
  19 #include "nodes/primnodes.h"
  20 #include "storage/itemptr.h"
  21
  22
  23 /* ----------------------------------------------------------------
  24  *                                              node definitions
  25  * ----------------------------------------------------------------
  26  */
  27
  28 /* ----------------
  29  *              PlannedStmt node
  30  *
  31  * The output of the planner is a Plan tree headed by a PlannedStmt node.
  32  * PlannedStmt holds the "one time" information needed by the executor.
  33  * ----------------
  34  */
  35 typedef struct PlannedStmt
  36 {
  37         NodeTag         type;
  38
  39         CmdType         commandType;    /* select|insert|update|delete */
  40
  41         bool            canSetTag;              /* do I set the command result tag? */
  42
  43         bool            transientPlan;  /* redo plan when TransactionXmin changes? */
  44
  45         struct Plan *planTree;          /* tree of Plan nodes */
  46
  47         List       *rtable;                     /* list of RangeTblEntry nodes */
  48
  49         /* rtable indexes of target relations for INSERT/UPDATE/DELETE */
  50         List       *resultRelations;    /* integer list of RT indexes, or NIL */
  51
  52         Node       *utilityStmt;        /* non-null if this is DECLARE CURSOR */
  53
  54         IntoClause *intoClause;         /* target for SELECT INTO / CREATE TABLE AS */
  55
  56         List       *subplans;           /* Plan trees for SubPlan expressions */
  57
  58         Bitmapset  *rewindPlanIDs;      /* indices of subplans that require REWIND */
  59
  60         /*
  61          * If the query has a returningList then the planner will store a list of
  62          * processed targetlists (one per result relation) here.  We must have a
  63          * separate RETURNING targetlist for each result rel because column
  64          * numbers may vary within an inheritance tree.  In the targetlists, Vars
  65          * referencing the result relation will have their original varno and
  66          * varattno, while Vars referencing other rels will be converted to have
  67          * varno OUTER and varattno referencing a resjunk entry in the top plan
  68          * node's targetlist.
  69          */
  70         List       *returningLists; /* list of lists of TargetEntry, or NIL */
  71
  72         List       *rowMarks;           /* a list of RowMarkClause's */
  73
  74         List       *relationOids;       /* OIDs of relations the plan depends on */
  75
  76         List       *invalItems;         /* other dependencies, as PlanInvalItems */
  77
  78         int                     nParamExec;             /* number of PARAM_EXEC Params used */
  79 } PlannedStmt;
  80
  81 /* macro for fetching the Plan associated with a SubPlan node */
  82 #define exec_subplan_get_plan(plannedstmt, subplan) \
  83         ((Plan *) list_nth((plannedstmt)->subplans, (subplan)->plan_id - 1))
  84
  85
  86 /* ----------------
  87  *              Plan node
  88  *
  89  * All plan nodes "derive" from the Plan structure by having the
  90  * Plan structure as the first field.  This ensures that everything works
  91  * when nodes are cast to Plan's.  (node pointers are frequently cast to Plan*
  92  * when passed around generically in the executor)
  93  *
  94  * We never actually instantiate any Plan nodes; this is just the common
  95  * abstract superclass for all Plan-type nodes.
  96  * ----------------
  97  */
  98 typedef struct Plan
  99 {
 100         NodeTag         type;
 101
 102         /*
 103          * estimated execution costs for plan (see costsize.c for more info)
 104          */
 105         Cost            startup_cost;   /* cost expended before fetching any tuples */
 106         Cost            total_cost;             /* total cost (assuming all tuples fetched) */
 107
 108         /*
 109          * planner's estimate of result size of this plan step
 110          */
 111         double          plan_rows;              /* number of rows plan is expected to emit */
 112         int                     plan_width;             /* average row width in bytes */
 113
 114         /*
 115          * Common structural data for all Plan types.
 116          */
 117         List       *targetlist;         /* target list to be computed at this node */
 118         List       *qual;                       /* implicitly-ANDed qual conditions */
 119         struct Plan *lefttree;          /* input plan tree(s) */
 120         struct Plan *righttree;
 121         List       *initPlan;           /* Init Plan nodes (un-correlated expr
 122                                                                  * subselects) */
 123
 124         /*
 125          * Information for management of parameter-change-driven rescanning
 126          *
 127          * extParam includes the paramIDs of all external PARAM_EXEC params
 128          * affecting this plan node or its children.  setParam params from the
 129          * node's initPlans are not included, but their extParams are.
 130          *
 131          * allParam includes all the extParam paramIDs, plus the IDs of local
 132          * params that affect the node (i.e., the setParams of its initplans).
 133          * These are _all_ the PARAM_EXEC params that affect this node.
 134          */
 135         Bitmapset  *extParam;
 136         Bitmapset  *allParam;
 137 } Plan;
 138
 139 /* ----------------
 140  *      these are are defined to avoid confusion problems with "left"
 141  *      and "right" and "inner" and "outer".  The convention is that
 142  *      the "left" plan is the "outer" plan and the "right" plan is
 143  *      the inner plan, but these make the code more readable.
 144  * ----------------
 145  */
 146 #define innerPlan(node)                 (((Plan *)(node))->righttree)
 147 #define outerPlan(node)                 (((Plan *)(node))->lefttree)
 148
 149
 150 /* ----------------
 151  *       Result node -
 152  *              If no outer plan, evaluate a variable-free targetlist.
 153  *              If outer plan, return tuples from outer plan (after a level of
 154  *              projection as shown by targetlist).
 155  *
 156  * If resconstantqual isn't NULL, it represents a one-time qualification
 157  * test (i.e., one that doesn't depend on any variables from the outer plan,
 158  * so needs to be evaluated only once).
 159  * ----------------
 160  */
 161 typedef struct Result
 162 {
 163         Plan            plan;
 164         Node       *resconstantqual;
 165 } Result;
 166
 167 /* ----------------
 168  *       Append node -
 169  *              Generate the concatenation of the results of sub-plans.
 170  *
 171  * Append nodes are sometimes used to switch between several result relations
 172  * (when the target of an UPDATE or DELETE is an inheritance set).      Such a
 173  * node will have isTarget true.  The Append executor is then responsible
 174  * for updating the executor state to point at the correct target relation
 175  * whenever it switches subplans.
 176  * ----------------
 177  */
 178 typedef struct Append
 179 {
 180         Plan            plan;
 181         List       *appendplans;
 182         bool            isTarget;
 183 } Append;
 184
 185 /* ----------------
 186  *      RecursiveUnion node -
 187  *              Generate a recursive union of two subplans.
 188  *
 189  * The "outer" subplan is always the non-recursive term, and the "inner"
 190  * subplan is the recursive term.
 191  * ----------------
 192  */
 193 typedef struct RecursiveUnion
 194 {
 195         Plan            plan;
 196         int                     wtParam;                /* ID of Param representing work table */
 197         /* Remaining fields are zero/null in UNION ALL case */
 198         int                     numCols;                /* number of columns to check for
 199                                                                  * duplicate-ness */
 200         AttrNumber *dupColIdx;          /* their indexes in the target list */
 201         Oid                *dupOperators;       /* equality operators to compare with */
 202         long            numGroups;              /* estimated number of groups in input */
 203 } RecursiveUnion;
 204
 205 /* ----------------
 206  *       BitmapAnd node -
 207  *              Generate the intersection of the results of sub-plans.
 208  *
 209  * The subplans must be of types that yield tuple bitmaps.      The targetlist
 210  * and qual fields of the plan are unused and are always NIL.
 211  * ----------------
 212  */
 213 typedef struct BitmapAnd
 214 {
 215         Plan            plan;
 216         List       *bitmapplans;
 217 } BitmapAnd;
 218
 219 /* ----------------
 220  *       BitmapOr node -
 221  *              Generate the union of the results of sub-plans.
 222  *
 223  * The subplans must be of types that yield tuple bitmaps.      The targetlist
 224  * and qual fields of the plan are unused and are always NIL.
 225  * ----------------
 226  */
 227 typedef struct BitmapOr
 228 {
 229         Plan            plan;
 230         List       *bitmapplans;
 231 } BitmapOr;
 232
 233 /*
 234  * ==========
 235  * Scan nodes
 236  * ==========
 237  */
 238 typedef struct Scan
 239 {
 240         Plan            plan;
 241         Index           scanrelid;              /* relid is index into the range table */
 242 } Scan;
 243
 244 /* ----------------
 245  *              sequential scan node
 246  * ----------------
 247  */
 248 typedef Scan SeqScan;
 249
 250 /* ----------------
 251  *              index scan node
 252  *
 253  * indexqualorig is an implicitly-ANDed list of index qual expressions, each
 254  * in the same form it appeared in the query WHERE condition.  Each should
 255  * be of the form (indexkey OP comparisonval) or (comparisonval OP indexkey).
 256  * The indexkey is a Var or expression referencing column(s) of the index's
 257  * base table.  The comparisonval might be any expression, but it won't use
 258  * any columns of the base table.
 259  *
 260  * indexqual has the same form, but the expressions have been commuted if
 261  * necessary to put the indexkeys on the left, and the indexkeys are replaced
 262  * by Var nodes identifying the index columns (varattno is the index column
 263  * position, not the base table's column, even though varno is for the base
 264  * table).      This is a bit hokey ... would be cleaner to use a special-purpose
 265  * node type that could not be mistaken for a regular Var.      But it will do
 266  * for now.
 267  * ----------------
 268  */
 269 typedef struct IndexScan
 270 {
 271         Scan            scan;
 272         Oid                     indexid;                /* OID of index to scan */
 273         List       *indexqual;          /* list of index quals (OpExprs) */
 274         List       *indexqualorig;      /* the same in original form */
 275         ScanDirection indexorderdir;    /* forward or backward or don't care */
 276 } IndexScan;
 277
 278 /* ----------------
 279  *              bitmap index scan node
 280  *
 281  * BitmapIndexScan delivers a bitmap of potential tuple locations;
 282  * it does not access the heap itself.  The bitmap is used by an
 283  * ancestor BitmapHeapScan node, possibly after passing through
 284  * intermediate BitmapAnd and/or BitmapOr nodes to combine it with
 285  * the results of other BitmapIndexScans.
 286  *
 287  * The fields have the same meanings as for IndexScan, except we don't
 288  * store a direction flag because direction is uninteresting.
 289  *
 290  * In a BitmapIndexScan plan node, the targetlist and qual fields are
 291  * not used and are always NIL.  The indexqualorig field is unused at
 292  * run time too, but is saved for the benefit of EXPLAIN.
 293  * ----------------
 294  */
 295 typedef struct BitmapIndexScan
 296 {
 297         Scan            scan;
 298         Oid                     indexid;                /* OID of index to scan */
 299         List       *indexqual;          /* list of index quals (OpExprs) */
 300         List       *indexqualorig;      /* the same in original form */
 301 } BitmapIndexScan;
 302
 303 /* ----------------
 304  *              bitmap sequential scan node
 305  *
 306  * This needs a copy of the qual conditions being used by the input index
 307  * scans because there are various cases where we need to recheck the quals;
 308  * for example, when the bitmap is lossy about the specific rows on a page
 309  * that meet the index condition.
 310  * ----------------
 311  */
 312 typedef struct BitmapHeapScan
 313 {
 314         Scan            scan;
 315         List       *bitmapqualorig; /* index quals, in standard expr form */
 316 } BitmapHeapScan;
 317
 318 /* ----------------
 319  *              tid scan node
 320  *
 321  * tidquals is an implicitly OR'ed list of qual expressions of the form
 322  * "CTID = pseudoconstant" or "CTID = ANY(pseudoconstant_array)".
 323  * ----------------
 324  */
 325 typedef struct TidScan
 326 {
 327         Scan            scan;
 328         List       *tidquals;           /* qual(s) involving CTID = something */
 329 } TidScan;
 330
 331 /* ----------------
 332  *              subquery scan node
 333  *
 334  * SubqueryScan is for scanning the output of a sub-query in the range table.
 335  * We often need an extra plan node above the sub-query's plan to perform
 336  * expression evaluations (which we can't push into the sub-query without
 337  * risking changing its semantics).  Although we are not scanning a physical
 338  * relation, we make this a descendant of Scan anyway for code-sharing
 339  * purposes.
 340  *
 341  * Note: we store the sub-plan in the type-specific subplan field, not in
 342  * the generic lefttree field as you might expect.      This is because we do
 343  * not want plan-tree-traversal routines to recurse into the subplan without
 344  * knowing that they are changing Query contexts.
 345  *
 346  * Note: subrtable is used just to carry the subquery rangetable from
 347  * createplan.c to setrefs.c; it should always be NIL by the time the
 348  * executor sees the plan.
 349  * ----------------
 350  */
 351 typedef struct SubqueryScan
 352 {
 353         Scan            scan;
 354         Plan       *subplan;
 355         List       *subrtable;          /* temporary workspace for planner */
 356 } SubqueryScan;
 357
 358 /* ----------------
 359  *              FunctionScan node
 360  * ----------------
 361  */
 362 typedef struct FunctionScan
 363 {
 364         Scan            scan;
 365         Node       *funcexpr;           /* expression tree for func call */
 366         List       *funccolnames;       /* output column names (string Value nodes) */
 367         List       *funccoltypes;       /* OID list of column type OIDs */
 368         List       *funccoltypmods; /* integer list of column typmods */
 369 } FunctionScan;
 370
 371 /* ----------------
 372  *              ValuesScan node
 373  * ----------------
 374  */
 375 typedef struct ValuesScan
 376 {
 377         Scan            scan;
 378         List       *values_lists;       /* list of expression lists */
 379 } ValuesScan;
 380
 381 /* ----------------
 382  *              CteScan node
 383  * ----------------
 384  */
 385 typedef struct CteScan
 386 {
 387         Scan            scan;
 388         int                     ctePlanId;              /* ID of init SubPlan for CTE */
 389         int                     cteParam;               /* ID of Param representing CTE output */
 390 } CteScan;
 391
 392 /* ----------------
 393  *              WorkTableScan node
 394  * ----------------
 395  */
 396 typedef struct WorkTableScan
 397 {
 398         Scan            scan;
 399         int                     wtParam;                /* ID of Param representing work table */
 400 } WorkTableScan;
 401
 402
 403 /*
 404  * ==========
 405  * Join nodes
 406  * ==========
 407  */
 408
 409 /* ----------------
 410  *              Join node
 411  *
 412  * jointype:    rule for joining tuples from left and right subtrees
 413  * joinqual:    qual conditions that came from JOIN/ON or JOIN/USING
 414  *                              (plan.qual contains conditions that came from WHERE)
 415  *
 416  * When jointype is INNER, joinqual and plan.qual are semantically
 417  * interchangeable.  For OUTER jointypes, the two are *not* interchangeable;
 418  * only joinqual is used to determine whether a match has been found for
 419  * the purpose of deciding whether to generate null-extended tuples.
 420  * (But plan.qual is still applied before actually returning a tuple.)
 421  * For an outer join, only joinquals are allowed to be used as the merge
 422  * or hash condition of a merge or hash join.
 423  * ----------------
 424  */
 425 typedef struct Join
 426 {
 427         Plan            plan;
 428         JoinType        jointype;
 429         List       *joinqual;           /* JOIN quals (in addition to plan.qual) */
 430 } Join;
 431
 432 /* ----------------
 433  *              nest loop join node
 434  * ----------------
 435  */
 436 typedef struct NestLoop
 437 {
 438         Join            join;
 439 } NestLoop;
 440
 441 /* ----------------
 442  *              merge join node
 443  *
 444  * The expected ordering of each mergeable column is described by a btree
 445  * opfamily OID, a direction (BTLessStrategyNumber or BTGreaterStrategyNumber)
 446  * and a nulls-first flag.      Note that the two sides of each mergeclause may
 447  * be of different datatypes, but they are ordered the same way according to
 448  * the common opfamily.  The operator in each mergeclause must be an equality
 449  * operator of the indicated opfamily.
 450  * ----------------
 451  */
 452 typedef struct MergeJoin
 453 {
 454         Join            join;
 455         List       *mergeclauses;       /* mergeclauses as expression trees */
 456         /* these are arrays, but have the same length as the mergeclauses list: */
 457         Oid                *mergeFamilies;      /* per-clause OIDs of btree opfamilies */
 458         int                *mergeStrategies;    /* per-clause ordering (ASC or DESC) */
 459         bool       *mergeNullsFirst;    /* per-clause nulls ordering */
 460 } MergeJoin;
 461
 462 /* ----------------
 463  *              hash join node
 464  * ----------------
 465  */
 466 typedef struct HashJoin
 467 {
 468         Join            join;
 469         List       *hashclauses;
 470 } HashJoin;
 471
 472 /* ----------------
 473  *              materialization node
 474  * ----------------
 475  */
 476 typedef struct Material
 477 {
 478         Plan            plan;
 479 } Material;
 480
 481 /* ----------------
 482  *              sort node
 483  * ----------------
 484  */
 485 typedef struct Sort
 486 {
 487         Plan            plan;
 488         int                     numCols;                /* number of sort-key columns */
 489         AttrNumber *sortColIdx;         /* their indexes in the target list */
 490         Oid                *sortOperators;      /* OIDs of operators to sort them by */
 491         bool       *nullsFirst;         /* NULLS FIRST/LAST directions */
 492 } Sort;
 493
 494 /* ---------------
 495  *       group node -
 496  *              Used for queries with GROUP BY (but no aggregates) specified.
 497  *              The input must be presorted according to the grouping columns.
 498  * ---------------
 499  */
 500 typedef struct Group
 501 {
 502         Plan            plan;
 503         int                     numCols;                /* number of grouping columns */
 504         AttrNumber *grpColIdx;          /* their indexes in the target list */
 505         Oid                *grpOperators;       /* equality operators to compare with */
 506 } Group;
 507
 508 /* ---------------
 509  *              aggregate node
 510  *
 511  * An Agg node implements plain or grouped aggregation.  For grouped
 512  * aggregation, we can work with presorted input or unsorted input;
 513  * the latter strategy uses an internal hashtable.
 514  *
 515  * Notice the lack of any direct info about the aggregate functions to be
 516  * computed.  They are found by scanning the node's tlist and quals during
 517  * executor startup.  (It is possible that there are no aggregate functions;
 518  * this could happen if they get optimized away by constant-folding, or if
 519  * we are using the Agg node to implement hash-based grouping.)
 520  * ---------------
 521  */
 522 typedef enum AggStrategy
 523 {
 524         AGG_PLAIN,                                      /* simple agg across all input rows */
 525         AGG_SORTED,                                     /* grouped agg, input must be sorted */
 526         AGG_HASHED                                      /* grouped agg, use internal hashtable */
 527 } AggStrategy;
 528
 529 typedef struct Agg
 530 {
 531         Plan            plan;
 532         AggStrategy aggstrategy;
 533         int                     numCols;                /* number of grouping columns */
 534         AttrNumber *grpColIdx;          /* their indexes in the target list */
 535         Oid                *grpOperators;       /* equality operators to compare with */
 536         long            numGroups;              /* estimated number of groups in input */
 537 } Agg;
 538
 539 /* ----------------
 540  *              window aggregate node
 541  * ----------------
 542  */
 543 typedef struct WindowAgg
 544 {
 545         Plan            plan;
 546         Index           winref;                 /* ID referenced by window functions */
 547         int                     partNumCols;    /* number of columns in partition clause */
 548         AttrNumber *partColIdx;         /* their indexes in the target list */
 549         Oid                *partOperators;      /* equality operators for partition columns */
 550         int                     ordNumCols;             /* number of columns in ordering clause */
 551         AttrNumber *ordColIdx;          /* their indexes in the target list */
 552         Oid                *ordOperators;       /* equality operators for ordering columns */
 553         int                     frameOptions;   /* frame_clause options, see WindowDef */
 554 } WindowAgg;
 555
 556 /* ----------------
 557  *              unique node
 558  * ----------------
 559  */
 560 typedef struct Unique
 561 {
 562         Plan            plan;
 563         int                     numCols;                /* number of columns to check for uniqueness */
 564         AttrNumber *uniqColIdx;         /* their indexes in the target list */
 565         Oid                *uniqOperators;      /* equality operators to compare with */
 566 } Unique;
 567
 568 /* ----------------
 569  *              hash build node
 570  *
 571  * If the executor is supposed to try to apply skew join optimization, then
 572  * skewTable/skewColumn identify the outer relation's join key column, from
 573  * which the relevant MCV statistics can be fetched.  Also, its type
 574  * information is provided to save a lookup.
 575  * ----------------
 576  */
 577 typedef struct Hash
 578 {
 579         Plan            plan;
 580         Oid                     skewTable;              /* outer join key's table OID, or InvalidOid */
 581         AttrNumber      skewColumn;             /* outer join key's column #, or zero */
 582         Oid                     skewColType;    /* datatype of the outer key column */
 583         int32           skewColTypmod;  /* typmod of the outer key column */
 584         /* all other info is in the parent HashJoin node */
 585 } Hash;
 586
 587 /* ----------------
 588  *              setop node
 589  * ----------------
 590  */
 591 typedef enum SetOpCmd
 592 {
 593         SETOPCMD_INTERSECT,
 594         SETOPCMD_INTERSECT_ALL,
 595         SETOPCMD_EXCEPT,
 596         SETOPCMD_EXCEPT_ALL
 597 } SetOpCmd;
 598
 599 typedef enum SetOpStrategy
 600 {
 601         SETOP_SORTED,                           /* input must be sorted */
 602         SETOP_HASHED                            /* use internal hashtable */
 603 } SetOpStrategy;
 604
 605 typedef struct SetOp
 606 {
 607         Plan            plan;
 608         SetOpCmd        cmd;                    /* what to do */
 609         SetOpStrategy strategy;         /* how to do it */
 610         int                     numCols;                /* number of columns to check for
 611                                                                  * duplicate-ness */
 612         AttrNumber *dupColIdx;          /* their indexes in the target list */
 613         Oid                *dupOperators;       /* equality operators to compare with */
 614         AttrNumber      flagColIdx;             /* where is the flag column, if any */
 615         int                     firstFlag;              /* flag value for first input relation */
 616         long            numGroups;              /* estimated number of groups in input */
 617 } SetOp;
 618
 619 /* ----------------
 620  *              limit node
 621  *
 622  * Note: as of Postgres 8.2, the offset and count expressions are expected
 623  * to yield int8, rather than int4 as before.
 624  * ----------------
 625  */
 626 typedef struct Limit
 627 {
 628         Plan            plan;
 629         Node       *limitOffset;        /* OFFSET parameter, or NULL if none */
 630         Node       *limitCount;         /* COUNT parameter, or NULL if none */
 631 } Limit;
 632
 633
 634 /*
 635  * Plan invalidation info
 636  *
 637  * We track the objects on which a PlannedStmt depends in two ways:
 638  * relations are recorded as a simple list of OIDs, and everything else
 639  * is represented as a list of PlanInvalItems.  A PlanInvalItem is designed
 640  * to be used with the syscache invalidation mechanism, so it identifies a
 641  * system catalog entry by cache ID and tuple TID.
 642  */
 643 typedef struct PlanInvalItem
 644 {
 645         NodeTag         type;
 646         int                     cacheId;                /* a syscache ID, see utils/syscache.h */
 647         ItemPointerData tupleId;        /* TID of the object's catalog tuple */
 648 } PlanInvalItem;
 649
 650 #endif   /* PLANNODES_H */