[postgresql] / src / include / nodes / plannodes.h

/*-------------------------------------------------------------------------
 *
 * plannodes.h
 *        definitions for query plan nodes
 *
 *
 * Portions Copyright (c) 1996-2009, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * $PostgreSQL: pgsql/src/include/nodes/plannodes.h,v 1.113 2009/10/26 02:26:42 tgl Exp $
 *
 *-------------------------------------------------------------------------
 */
#ifndef PLANNODES_H
#define PLANNODES_H

#include "access/sdir.h"
#include "nodes/bitmapset.h"
#include "nodes/primnodes.h"
#include "storage/itemptr.h"


/* ----------------------------------------------------------------
 *                                              node definitions
 * ----------------------------------------------------------------
 */

/* ----------------
 *              PlannedStmt node
 *
 * The output of the planner is a Plan tree headed by a PlannedStmt node.
 * PlannedStmt holds the "one time" information needed by the executor.
 * ----------------
 */
typedef struct PlannedStmt
{
        NodeTag         type;

        CmdType         commandType;    /* select|insert|update|delete */

        bool            hasReturning;   /* is it insert|update|delete RETURNING? */

        bool            canSetTag;              /* do I set the command result tag? */

        bool            transientPlan;  /* redo plan when TransactionXmin changes? */

        struct Plan *planTree;          /* tree of Plan nodes */

        List       *rtable;                     /* list of RangeTblEntry nodes */

        /* rtable indexes of target relations for INSERT/UPDATE/DELETE */
        List       *resultRelations;    /* integer list of RT indexes, or NIL */

        Node       *utilityStmt;        /* non-null if this is DECLARE CURSOR */

        IntoClause *intoClause;         /* target for SELECT INTO / CREATE TABLE AS */

        List       *subplans;           /* Plan trees for SubPlan expressions */

        Bitmapset  *rewindPlanIDs;      /* indices of subplans that require REWIND */

        List       *rowMarks;           /* a list of PlanRowMark's */

        List       *relationOids;       /* OIDs of relations the plan depends on */

        List       *invalItems;         /* other dependencies, as PlanInvalItems */

        int                     nParamExec;             /* number of PARAM_EXEC Params used */
} PlannedStmt;

/* macro for fetching the Plan associated with a SubPlan node */
#define exec_subplan_get_plan(plannedstmt, subplan) \
        ((Plan *) list_nth((plannedstmt)->subplans, (subplan)->plan_id - 1))


/* ----------------
 *              Plan node
 *
 * All plan nodes "derive" from the Plan structure by having the
 * Plan structure as the first field.  This ensures that everything works
 * when nodes are cast to Plan's.  (node pointers are frequently cast to Plan*
 * when passed around generically in the executor)
 *
 * We never actually instantiate any Plan nodes; this is just the common
 * abstract superclass for all Plan-type nodes.
 * ----------------
 */
typedef struct Plan
{
        NodeTag         type;

        /*
         * estimated execution costs for plan (see costsize.c for more info)
         */
        Cost            startup_cost;   /* cost expended before fetching any tuples */
        Cost            total_cost;             /* total cost (assuming all tuples fetched) */

        /*
         * planner's estimate of result size of this plan step
         */
        double          plan_rows;              /* number of rows plan is expected to emit */
        int                     plan_width;             /* average row width in bytes */

        /*
         * Common structural data for all Plan types.
         */
        List       *targetlist;         /* target list to be computed at this node */
        List       *qual;                       /* implicitly-ANDed qual conditions */
        struct Plan *lefttree;          /* input plan tree(s) */
        struct Plan *righttree;
        List       *initPlan;           /* Init Plan nodes (un-correlated expr
                                                                 * subselects) */

        /*
         * Information for management of parameter-change-driven rescanning
         *
         * extParam includes the paramIDs of all external PARAM_EXEC params
         * affecting this plan node or its children.  setParam params from the
         * node's initPlans are not included, but their extParams are.
         *
         * allParam includes all the extParam paramIDs, plus the IDs of local
         * params that affect the node (i.e., the setParams of its initplans).
         * These are _all_ the PARAM_EXEC params that affect this node.
         */
        Bitmapset  *extParam;
        Bitmapset  *allParam;
} Plan;

/* ----------------
 *      these are are defined to avoid confusion problems with "left"
 *      and "right" and "inner" and "outer".  The convention is that
 *      the "left" plan is the "outer" plan and the "right" plan is
 *      the inner plan, but these make the code more readable.
 * ----------------
 */
#define innerPlan(node)                 (((Plan *)(node))->righttree)
#define outerPlan(node)                 (((Plan *)(node))->lefttree)


/* ----------------
 *       Result node -
 *              If no outer plan, evaluate a variable-free targetlist.
 *              If outer plan, return tuples from outer plan (after a level of
 *              projection as shown by targetlist).
 *
 * If resconstantqual isn't NULL, it represents a one-time qualification
 * test (i.e., one that doesn't depend on any variables from the outer plan,
 * so needs to be evaluated only once).
 * ----------------
 */
typedef struct Result
{
        Plan            plan;
        Node       *resconstantqual;
} Result;

/* ----------------
 *       ModifyTable node -
 *              Apply rows produced by subplan(s) to result table(s),
 *              by inserting, updating, or deleting.
 * ----------------
 */
typedef struct ModifyTable
{
        Plan            plan;
        CmdType         operation;                      /* INSERT, UPDATE, or DELETE */
        List       *resultRelations;    /* integer list of RT indexes */
        List       *plans;                              /* plan(s) producing source data */
        List       *returningLists;             /* per-target-table RETURNING tlists */
        List       *rowMarks;                   /* PlanRowMarks (non-locking only) */
        int                     epqParam;                       /* ID of Param for EvalPlanQual re-eval */
} ModifyTable;

/* ----------------
 *       Append node -
 *              Generate the concatenation of the results of sub-plans.
 * ----------------
 */
typedef struct Append
{
        Plan            plan;
        List       *appendplans;
} Append;

/* ----------------
 *      RecursiveUnion node -
 *              Generate a recursive union of two subplans.
 *
 * The "outer" subplan is always the non-recursive term, and the "inner"
 * subplan is the recursive term.
 * ----------------
 */
typedef struct RecursiveUnion
{
        Plan            plan;
        int                     wtParam;                /* ID of Param representing work table */
        /* Remaining fields are zero/null in UNION ALL case */
        int                     numCols;                /* number of columns to check for
                                                                 * duplicate-ness */
        AttrNumber *dupColIdx;          /* their indexes in the target list */
        Oid                *dupOperators;       /* equality operators to compare with */
        long            numGroups;              /* estimated number of groups in input */
} RecursiveUnion;

/* ----------------
 *       BitmapAnd node -
 *              Generate the intersection of the results of sub-plans.
 *
 * The subplans must be of types that yield tuple bitmaps.      The targetlist
 * and qual fields of the plan are unused and are always NIL.
 * ----------------
 */
typedef struct BitmapAnd
{
        Plan            plan;
        List       *bitmapplans;
} BitmapAnd;

/* ----------------
 *       BitmapOr node -
 *              Generate the union of the results of sub-plans.
 *
 * The subplans must be of types that yield tuple bitmaps.      The targetlist
 * and qual fields of the plan are unused and are always NIL.
 * ----------------
 */
typedef struct BitmapOr
{
        Plan            plan;
        List       *bitmapplans;
} BitmapOr;

/*
 * ==========
 * Scan nodes
 * ==========
 */
typedef struct Scan
{
        Plan            plan;
        Index           scanrelid;              /* relid is index into the range table */
} Scan;

/* ----------------
 *              sequential scan node
 * ----------------
 */
typedef Scan SeqScan;

/* ----------------
 *              index scan node
 *
 * indexqualorig is an implicitly-ANDed list of index qual expressions, each
 * in the same form it appeared in the query WHERE condition.  Each should
 * be of the form (indexkey OP comparisonval) or (comparisonval OP indexkey).
 * The indexkey is a Var or expression referencing column(s) of the index's
 * base table.  The comparisonval might be any expression, but it won't use
 * any columns of the base table.
 *
 * indexqual has the same form, but the expressions have been commuted if
 * necessary to put the indexkeys on the left, and the indexkeys are replaced
 * by Var nodes identifying the index columns (varattno is the index column
 * position, not the base table's column, even though varno is for the base
 * table).      This is a bit hokey ... would be cleaner to use a special-purpose
 * node type that could not be mistaken for a regular Var.      But it will do
 * for now.
 * ----------------
 */
typedef struct IndexScan
{
        Scan            scan;
        Oid                     indexid;                /* OID of index to scan */
        List       *indexqual;          /* list of index quals (OpExprs) */
        List       *indexqualorig;      /* the same in original form */
        ScanDirection indexorderdir;    /* forward or backward or don't care */
} IndexScan;

/* ----------------
 *              bitmap index scan node
 *
 * BitmapIndexScan delivers a bitmap of potential tuple locations;
 * it does not access the heap itself.  The bitmap is used by an
 * ancestor BitmapHeapScan node, possibly after passing through
 * intermediate BitmapAnd and/or BitmapOr nodes to combine it with
 * the results of other BitmapIndexScans.
 *
 * The fields have the same meanings as for IndexScan, except we don't
 * store a direction flag because direction is uninteresting.
 *
 * In a BitmapIndexScan plan node, the targetlist and qual fields are
 * not used and are always NIL.  The indexqualorig field is unused at
 * run time too, but is saved for the benefit of EXPLAIN.
 * ----------------
 */
typedef struct BitmapIndexScan
{
        Scan            scan;
        Oid                     indexid;                /* OID of index to scan */
        List       *indexqual;          /* list of index quals (OpExprs) */
        List       *indexqualorig;      /* the same in original form */
} BitmapIndexScan;

/* ----------------
 *              bitmap sequential scan node
 *
 * This needs a copy of the qual conditions being used by the input index
 * scans because there are various cases where we need to recheck the quals;
 * for example, when the bitmap is lossy about the specific rows on a page
 * that meet the index condition.
 * ----------------
 */
typedef struct BitmapHeapScan
{
        Scan            scan;
        List       *bitmapqualorig; /* index quals, in standard expr form */
} BitmapHeapScan;

/* ----------------
 *              tid scan node
 *
 * tidquals is an implicitly OR'ed list of qual expressions of the form
 * "CTID = pseudoconstant" or "CTID = ANY(pseudoconstant_array)".
 * ----------------
 */
typedef struct TidScan
{
        Scan            scan;
        List       *tidquals;           /* qual(s) involving CTID = something */
} TidScan;

/* ----------------
 *              subquery scan node
 *
 * SubqueryScan is for scanning the output of a sub-query in the range table.
 * We often need an extra plan node above the sub-query's plan to perform
 * expression evaluations (which we can't push into the sub-query without
 * risking changing its semantics).  Although we are not scanning a physical
 * relation, we make this a descendant of Scan anyway for code-sharing
 * purposes.
 *
 * Note: we store the sub-plan in the type-specific subplan field, not in
 * the generic lefttree field as you might expect.      This is because we do
 * not want plan-tree-traversal routines to recurse into the subplan without
 * knowing that they are changing Query contexts.
 *
 * Note: subrtable is used just to carry the subquery rangetable from
 * createplan.c to setrefs.c; it should always be NIL by the time the
 * executor sees the plan.  Similarly for subrowmark.
 * ----------------
 */
typedef struct SubqueryScan
{
        Scan            scan;
        Plan       *subplan;
        List       *subrtable;          /* temporary workspace for planner */
        List       *subrowmark;         /* temporary workspace for planner */
} SubqueryScan;

/* ----------------
 *              FunctionScan node
 * ----------------
 */
typedef struct FunctionScan
{
        Scan            scan;
        Node       *funcexpr;           /* expression tree for func call */
        List       *funccolnames;       /* output column names (string Value nodes) */
        List       *funccoltypes;       /* OID list of column type OIDs */
        List       *funccoltypmods; /* integer list of column typmods */
} FunctionScan;

/* ----------------
 *              ValuesScan node
 * ----------------
 */
typedef struct ValuesScan
{
        Scan            scan;
        List       *values_lists;       /* list of expression lists */
} ValuesScan;

/* ----------------
 *              CteScan node
 * ----------------
 */
typedef struct CteScan
{
        Scan            scan;
        int                     ctePlanId;              /* ID of init SubPlan for CTE */
        int                     cteParam;               /* ID of Param representing CTE output */
} CteScan;

/* ----------------
 *              WorkTableScan node
 * ----------------
 */
typedef struct WorkTableScan
{
        Scan            scan;
        int                     wtParam;                /* ID of Param representing work table */
} WorkTableScan;


/*
 * ==========
 * Join nodes
 * ==========
 */

/* ----------------
 *              Join node
 *
 * jointype:    rule for joining tuples from left and right subtrees
 * joinqual:    qual conditions that came from JOIN/ON or JOIN/USING
 *                              (plan.qual contains conditions that came from WHERE)
 *
 * When jointype is INNER, joinqual and plan.qual are semantically
 * interchangeable.  For OUTER jointypes, the two are *not* interchangeable;
 * only joinqual is used to determine whether a match has been found for
 * the purpose of deciding whether to generate null-extended tuples.
 * (But plan.qual is still applied before actually returning a tuple.)
 * For an outer join, only joinquals are allowed to be used as the merge
 * or hash condition of a merge or hash join.
 * ----------------
 */
typedef struct Join
{
        Plan            plan;
        JoinType        jointype;
        List       *joinqual;           /* JOIN quals (in addition to plan.qual) */
} Join;

/* ----------------
 *              nest loop join node
 * ----------------
 */
typedef struct NestLoop
{
        Join            join;
} NestLoop;

/* ----------------
 *              merge join node
 *
 * The expected ordering of each mergeable column is described by a btree
 * opfamily OID, a direction (BTLessStrategyNumber or BTGreaterStrategyNumber)
 * and a nulls-first flag.      Note that the two sides of each mergeclause may
 * be of different datatypes, but they are ordered the same way according to
 * the common opfamily.  The operator in each mergeclause must be an equality
 * operator of the indicated opfamily.
 * ----------------
 */
typedef struct MergeJoin
{
        Join            join;
        List       *mergeclauses;       /* mergeclauses as expression trees */
        /* these are arrays, but have the same length as the mergeclauses list: */
        Oid                *mergeFamilies;      /* per-clause OIDs of btree opfamilies */
        int                *mergeStrategies;    /* per-clause ordering (ASC or DESC) */
        bool       *mergeNullsFirst;    /* per-clause nulls ordering */
} MergeJoin;

/* ----------------
 *              hash join node
 * ----------------
 */
typedef struct HashJoin
{
        Join            join;
        List       *hashclauses;
} HashJoin;

/* ----------------
 *              materialization node
 * ----------------
 */
typedef struct Material
{
        Plan            plan;
} Material;

/* ----------------
 *              sort node
 * ----------------
 */
typedef struct Sort
{
        Plan            plan;
        int                     numCols;                /* number of sort-key columns */
        AttrNumber *sortColIdx;         /* their indexes in the target list */
        Oid                *sortOperators;      /* OIDs of operators to sort them by */
        bool       *nullsFirst;         /* NULLS FIRST/LAST directions */
} Sort;

/* ---------------
 *       group node -
 *              Used for queries with GROUP BY (but no aggregates) specified.
 *              The input must be presorted according to the grouping columns.
 * ---------------
 */
typedef struct Group
{
        Plan            plan;
        int                     numCols;                /* number of grouping columns */
        AttrNumber *grpColIdx;          /* their indexes in the target list */
        Oid                *grpOperators;       /* equality operators to compare with */
} Group;

/* ---------------
 *              aggregate node
 *
 * An Agg node implements plain or grouped aggregation.  For grouped
 * aggregation, we can work with presorted input or unsorted input;
 * the latter strategy uses an internal hashtable.
 *
 * Notice the lack of any direct info about the aggregate functions to be
 * computed.  They are found by scanning the node's tlist and quals during
 * executor startup.  (It is possible that there are no aggregate functions;
 * this could happen if they get optimized away by constant-folding, or if
 * we are using the Agg node to implement hash-based grouping.)
 * ---------------
 */
typedef enum AggStrategy
{
        AGG_PLAIN,                                      /* simple agg across all input rows */
        AGG_SORTED,                                     /* grouped agg, input must be sorted */
        AGG_HASHED                                      /* grouped agg, use internal hashtable */
} AggStrategy;

typedef struct Agg
{
        Plan            plan;
        AggStrategy aggstrategy;
        int                     numCols;                /* number of grouping columns */
        AttrNumber *grpColIdx;          /* their indexes in the target list */
        Oid                *grpOperators;       /* equality operators to compare with */
        long            numGroups;              /* estimated number of groups in input */
} Agg;

/* ----------------
 *              window aggregate node
 * ----------------
 */
typedef struct WindowAgg
{
        Plan            plan;
        Index           winref;                 /* ID referenced by window functions */
        int                     partNumCols;    /* number of columns in partition clause */
        AttrNumber *partColIdx;         /* their indexes in the target list */
        Oid                *partOperators;      /* equality operators for partition columns */
        int                     ordNumCols;             /* number of columns in ordering clause */
        AttrNumber *ordColIdx;          /* their indexes in the target list */
        Oid                *ordOperators;       /* equality operators for ordering columns */
        int                     frameOptions;   /* frame_clause options, see WindowDef */
} WindowAgg;

/* ----------------
 *              unique node
 * ----------------
 */
typedef struct Unique
{
        Plan            plan;
        int                     numCols;                /* number of columns to check for uniqueness */
        AttrNumber *uniqColIdx;         /* their indexes in the target list */
        Oid                *uniqOperators;      /* equality operators to compare with */
} Unique;

/* ----------------
 *              hash build node
 *
 * If the executor is supposed to try to apply skew join optimization, then
 * skewTable/skewColumn identify the outer relation's join key column, from
 * which the relevant MCV statistics can be fetched.  Also, its type
 * information is provided to save a lookup.
 * ----------------
 */
typedef struct Hash
{
        Plan            plan;
        Oid                     skewTable;              /* outer join key's table OID, or InvalidOid */
        AttrNumber      skewColumn;             /* outer join key's column #, or zero */
        Oid                     skewColType;    /* datatype of the outer key column */
        int32           skewColTypmod;  /* typmod of the outer key column */
        /* all other info is in the parent HashJoin node */
} Hash;

/* ----------------
 *              setop node
 * ----------------
 */
typedef enum SetOpCmd
{
        SETOPCMD_INTERSECT,
        SETOPCMD_INTERSECT_ALL,
        SETOPCMD_EXCEPT,
        SETOPCMD_EXCEPT_ALL
} SetOpCmd;

typedef enum SetOpStrategy
{
        SETOP_SORTED,                           /* input must be sorted */
        SETOP_HASHED                            /* use internal hashtable */
} SetOpStrategy;

typedef struct SetOp
{
        Plan            plan;
        SetOpCmd        cmd;                    /* what to do */
        SetOpStrategy strategy;         /* how to do it */
        int                     numCols;                /* number of columns to check for
                                                                 * duplicate-ness */
        AttrNumber *dupColIdx;          /* their indexes in the target list */
        Oid                *dupOperators;       /* equality operators to compare with */
        AttrNumber      flagColIdx;             /* where is the flag column, if any */
        int                     firstFlag;              /* flag value for first input relation */
        long            numGroups;              /* estimated number of groups in input */
} SetOp;

/* ----------------
 *              lock-rows node
 *
 * rowMarks identifies the rels to be locked by this node; it should be
 * a subset of the rowMarks listed in the top-level PlannedStmt.
 * epqParam is a Param that all scan nodes below this one must depend on.
 * It is used to force re-evaluation of the plan during EvalPlanQual.
 * ----------------
 */
typedef struct LockRows
{
        Plan            plan;
        List       *rowMarks;           /* a list of PlanRowMark's */
        int                     epqParam;               /* ID of Param for EvalPlanQual re-eval */
} LockRows;

/* ----------------
 *              limit node
 *
 * Note: as of Postgres 8.2, the offset and count expressions are expected
 * to yield int8, rather than int4 as before.
 * ----------------
 */
typedef struct Limit
{
        Plan            plan;
        Node       *limitOffset;        /* OFFSET parameter, or NULL if none */
        Node       *limitCount;         /* COUNT parameter, or NULL if none */
} Limit;


/*
 * RowMarkType -
 *        enums for types of row-marking operations
 *
 * When doing UPDATE, DELETE, or SELECT FOR UPDATE/SHARE, we have to uniquely
 * identify all the source rows, not only those from the target relations, so
 * that we can perform EvalPlanQual rechecking at need.  For plain tables we
 * can just fetch the TID, the same as for a target relation.  Otherwise (for
 * example for VALUES or FUNCTION scans) we have to copy the whole row value.
 * The latter is pretty inefficient but fortunately the case is not
 * performance-critical in practice.
 */
typedef enum RowMarkType
{
        ROW_MARK_EXCLUSIVE,                     /* obtain exclusive tuple lock */
        ROW_MARK_SHARE,                         /* obtain shared tuple lock */
        ROW_MARK_REFERENCE,                     /* just fetch the TID */
        ROW_MARK_COPY                           /* physically copy the row value */
} RowMarkType;

#define RowMarkRequiresRowShareLock(marktype)  ((marktype) <= ROW_MARK_SHARE)

/*
 * PlanRowMark -
 *         plan-time representation of FOR UPDATE/SHARE clauses
 *
 * When doing UPDATE, DELETE, or SELECT FOR UPDATE/SHARE, we create a separate
 * PlanRowMark node for each non-target relation in the query.  Relations that
 * are not specified as FOR UPDATE/SHARE are marked ROW_MARK_REFERENCE (if
 * real tables) or ROW_MARK_COPY (if not).
 *
 * Initially all PlanRowMarks have rti == prti and isParent == false.
 * When the planner discovers that a relation is the root of an inheritance
 * tree, it sets isParent true, and adds an additional PlanRowMark to the
 * list for each child relation (including the target rel itself in its role
 * as a child).  The child entries have rti == child rel's RT index and
 * prti == parent's RT index, and can therefore be recognized as children by
 * the fact that prti != rti.
 *
 * The AttrNumbers are filled in during preprocess_targetlist.  We use
 * different subsets of them for plain relations, inheritance children,
 * and non-table relations.
 */
typedef struct PlanRowMark
{
        NodeTag         type;
        Index           rti;                    /* range table index of markable relation */
        Index           prti;                   /* range table index of parent relation */
        RowMarkType     markType;               /* see enum above */
        bool            noWait;                 /* NOWAIT option */
        bool            isParent;               /* true if this is a "dummy" parent entry */
        AttrNumber      ctidAttNo;              /* resno of ctid junk attribute, if any */
        AttrNumber      toidAttNo;              /* resno of tableoid junk attribute, if any */
        AttrNumber      wholeAttNo;             /* resno of whole-row junk attribute, if any */
} PlanRowMark;


/*
 * Plan invalidation info
 *
 * We track the objects on which a PlannedStmt depends in two ways:
 * relations are recorded as a simple list of OIDs, and everything else
 * is represented as a list of PlanInvalItems.  A PlanInvalItem is designed
 * to be used with the syscache invalidation mechanism, so it identifies a
 * system catalog entry by cache ID and tuple TID.
 */
typedef struct PlanInvalItem
{
        NodeTag         type;
        int                     cacheId;                /* a syscache ID, see utils/syscache.h */
        ItemPointerData tupleId;        /* TID of the object's catalog tuple */
} PlanInvalItem;

#endif   /* PLANNODES_H */