/*------------------------------------------------------------------------- * * relation.h *	  Definitions for planner's internal data structures. * * * Portions Copyright (c) 1996-2003, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * * $Id: relation.h,v 1.85 2003/08/08 21:42:48 momjian Exp $ * *------------------------------------------------------------------------- */#ifndef RELATION_H#define RELATION_H#include "access/sdir.h"#include "nodes/bitmapset.h"#include "nodes/parsenodes.h"/* * Relids *		Set of relation identifiers (indexes into the rangetable). */typedef Bitmapset *Relids;/* * When looking for a "cheapest path", this enum specifies whether we want * cheapest startup cost or cheapest total cost. */typedef enum CostSelector{	STARTUP_COST, TOTAL_COST} CostSelector;/* * The cost estimate produced by cost_qual_eval() includes both a one-time * (startup) cost, and a per-tuple cost. */typedef struct QualCost{	Cost		startup;		/* one-time cost */	Cost		per_tuple;		/* per-evaluation cost */} QualCost;/*---------- * RelOptInfo *		Per-relation information for planning/optimization * * For planning purposes, a "base rel" is either a plain relation (a table) * or the output of a sub-SELECT or function that appears in the range table. * In either case it is uniquely identified by an RT index.  A "joinrel" * is the joining of two or more base rels.  A joinrel is identified by * the set of RT indexes for its component baserels.  We create RelOptInfo * nodes for each baserel and joinrel, and store them in the Query's * base_rel_list and join_rel_list respectively. * * Note that there is only one joinrel for any given set of component * baserels, no matter what order we assemble them in; so an unordered * set is the right datatype to identify it with. * * We also have "other rels", which are like base rels in that they refer to * single RT indexes; but they are not part of the join tree, and are stored * in other_rel_list not base_rel_list. * * Currently the only kind of otherrels are those made for child relations * of an inheritance scan (SELECT FROM foo*).  The parent table's RTE and * corresponding baserel represent the whole result of the inheritance scan. * The planner creates separate RTEs and associated RelOptInfos for each child * table (including the parent table, in its capacity as a member of the * inheritance set).  These RelOptInfos are physically identical to baserels, * but are otherrels because they are not in the main join tree.  These added * RTEs and otherrels are used to plan the scans of the individual tables in * the inheritance set; then the parent baserel is given an Append plan * comprising the best plans for the individual child tables. * * At one time we also made otherrels to represent join RTEs, for use in * handling join alias Vars.  Currently this is not needed because all join * alias Vars are expanded to non-aliased form during preprocess_expression. * * Parts of this data structure are specific to various scan and join * mechanisms.	It didn't seem worth creating new node types for them. * *		relids - Set of base-relation identifiers; it is a base relation *				if there is just one, a join relation if more than one *		rows - estimated number of tuples in the relation after restriction *			   clauses have been applied (ie, output rows of a plan for it) *		width - avg. number of bytes per tuple in the relation after the *				appropriate projections have been done (ie, output width) *		reltargetlist - List of Var nodes for the attributes we need to *						output from this relation (in no particular order) *		pathlist - List of Path nodes, one for each potentially useful *				   method of generating the relation *		cheapest_startup_path - the pathlist member with lowest startup cost *								(regardless of its ordering) *		cheapest_total_path - the pathlist member with lowest total cost *							  (regardless of its ordering) *		cheapest_unique_path - for caching cheapest path to produce unique *							   (no duplicates) output from relation *		pruneable - flag to let the planner know whether it can prune the *					pathlist of this RelOptInfo or not. * * If the relation is a base relation it will have these fields set: * *		relid - RTE index (this is redundant with the relids field, but *				is provided for convenience of access) *		rtekind - distinguishes plain relation, subquery, or function RTE *		min_attr, max_attr - range of valid AttrNumbers for rel *		attr_needed - array of bitmapsets indicating the highest joinrel *				in which each attribute is needed; if bit 0 is set then *				the attribute is needed as part of final targetlist *		attr_widths - cache space for per-attribute width estimates; *					  zero means not computed yet *		indexlist - list of IndexOptInfo nodes for relation's indexes *					(always NIL if it's not a table) *		pages - number of disk pages in relation (zero if not a table) *		tuples - number of tuples in relation (not considering restrictions) *		subplan - plan for subquery (NULL if it's not a subquery) * *		Note: for a subquery, tuples and subplan are not set immediately *		upon creation of the RelOptInfo object; they are filled in when *		set_base_rel_pathlist processes the object. * *		For otherrels that are inheritance children, these fields are filled *		in just as for a baserel. * * The presence of the remaining fields depends on the restrictions * and joins that the relation participates in: * *		baserestrictinfo - List of RestrictInfo nodes, containing info about *					each qualification clause in which this relation *					participates (only used for base rels) *		baserestrictcost - Estimated cost of evaluating the baserestrictinfo *					clauses at a single tuple (only used for base rels) *		outerjoinset - For a base rel: if the rel appears within the nullable *					side of an outer join, the set of all relids *					participating in the highest such outer join; else NULL. *					Otherwise, unused. *		joininfo  - List of JoinInfo nodes, containing info about each join *					clause in which this relation participates *		index_outer_relids - only used for base rels; set of outer relids *					that participate in indexable joinclauses for this rel *		index_inner_paths - only used for base rels; list of InnerIndexscanInfo *					nodes showing best indexpaths for various subsets of *					index_outer_relids. * * Note: Keeping a restrictinfo list in the RelOptInfo is useful only for * base rels, because for a join rel the set of clauses that are treated as * restrict clauses varies depending on which sub-relations we choose to join. * (For example, in a 3-base-rel join, a clause relating rels 1 and 2 must be * treated as a restrictclause if we join {1} and {2 3} to make {1 2 3}; but * if we join {1 2} and {3} then that clause will be a restrictclause in {1 2} * and should not be processed again at the level of {1 2 3}.)	Therefore, * the restrictinfo list in the join case appears in individual JoinPaths * (field joinrestrictinfo), not in the parent relation.  But it's OK for * the RelOptInfo to store the joininfo lists, because those are the same * for a given rel no matter how we form it. * * We store baserestrictcost in the RelOptInfo (for base relations) because * we know we will need it at least once (to price the sequential scan) * and may need it multiple times to price index scans. * * outerjoinset is used to ensure correct placement of WHERE clauses that * apply to outer-joined relations; we must not apply such WHERE clauses * until after the outer join is performed. *---------- */typedef enum RelOptKind{	RELOPT_BASEREL,	RELOPT_JOINREL,	RELOPT_OTHER_CHILD_REL} RelOptKind;typedef struct RelOptInfo{	NodeTag		type;	RelOptKind	reloptkind;	/* all relations included in this RelOptInfo */	Relids		relids;			/* set of base relids (rangetable indexes) */	/* size estimates generated by planner */	double		rows;			/* estimated number of result tuples */	int			width;			/* estimated avg width of result tuples */	/* materialization information */	FastList	reltargetlist;	List	   *pathlist;		/* Path structures */	struct Path *cheapest_startup_path;	struct Path *cheapest_total_path;	struct Path *cheapest_unique_path;	bool		pruneable;	/* information about a base rel (not set for join rels!) */	Index		relid;	RTEKind		rtekind;		/* RELATION, SUBQUERY, or FUNCTION */	AttrNumber	min_attr;		/* smallest attrno of rel (often <0) */	AttrNumber	max_attr;		/* largest attrno of rel */	Relids	   *attr_needed;	/* array indexed [min_attr .. max_attr] */	int32	   *attr_widths;	/* array indexed [min_attr .. max_attr] */	List	   *indexlist;	long		pages;	double		tuples;	struct Plan *subplan;		/* if subquery */	/* used by various scans and joins: */	List	   *baserestrictinfo;		/* RestrictInfo structures (if										 * base rel) */	QualCost	baserestrictcost;		/* cost of evaluating the above */	Relids		outerjoinset;	/* set of base relids */	List	   *joininfo;		/* JoinInfo structures */	/* cached info about inner indexscan paths for relation: */	Relids		index_outer_relids;		/* other relids in indexable join										 * clauses */	List	   *index_inner_paths;		/* InnerIndexscanInfo nodes */	/*	 * Inner indexscans are not in the main pathlist because they are not	 * usable except in specific join contexts.  We use the	 * index_inner_paths list just to avoid recomputing the best inner	 * indexscan repeatedly for similar outer relations.  See comments for	 * InnerIndexscanInfo.	 */} RelOptInfo;/* * IndexOptInfo *		Per-index information for planning/optimization * *		Prior to Postgres 7.0, RelOptInfo was used to describe both relations *		and indexes, but that created confusion without actually doing anything *		useful.  So now we have a separate IndexOptInfo struct for indexes. * *		classlist[], indexkeys[], and ordering[] have ncolumns entries. *		Zeroes in the indexkeys[] array indicate index columns that are *		expressions; there is one element in indexprs for each such column. * *		Note: for historical reasons, the classlist and ordering arrays have *		an extra entry that is always zero.  Some code scans until it sees a *		zero entry, rather than looking at ncolumns. * *		The indexprs and indpred expressions have been run through *		eval_const_expressions() for ease of matching to WHERE clauses. */typedef struct IndexOptInfo{	NodeTag		type;	Oid			indexoid;		/* OID of the index relation */	/* statistics from pg_class */	long		pages;			/* number of disk pages in index */	double		tuples;			/* number of index tuples in index */	/* index descriptor information */	int			ncolumns;		/* number of columns in index */	Oid		   *classlist;		/* OIDs of operator classes for columns */	int		   *indexkeys;		/* column numbers of index's keys, or 0 */	Oid		   *ordering;		/* OIDs of sort operators for each column */	Oid			relam;			/* OID of the access method (in pg_am) */	RegProcedure amcostestimate;	/* OID of the access method's cost fcn */	List	   *indexprs;		/* expressions for non-simple index								 * columns */	List	   *indpred;		/* predicate if a partial index, else NIL */	bool		unique;			/* true if a unique index */	/* cached info about inner indexscan paths for index */	Relids		outer_relids;	/* other relids in usable join clauses */	List	   *inner_paths;	/* List of InnerIndexscanInfo nodes */} IndexOptInfo;/* * PathKeys * *	The sort ordering of a path is represented by a list of sublists of *	PathKeyItem nodes.	An empty list implies no known ordering.  Otherwise *	the first sublist represents the primary sort key, the second the *	first secondary sort key, etc.	Each sublist contains one or more *	PathKeyItem nodes, each of which can be taken as the attribute that *	appears at that sort position.	(See the top of optimizer/path/pathkeys.c *	for more information.) */typedef struct PathKeyItem{	NodeTag		type;	Node	   *key;			/* the item that is ordered */	Oid			sortop;			/* the ordering operator ('<' op) */	/*	 * key typically points to a Var node, ie a relation attribute, but it	 * can also point to an arbitrary expression representing the value	 * indexed by an index expression.	 */} PathKeyItem;/* * Type "Path" is used as-is for sequential-scan paths.  For other * path types it is the first component of a larger struct. * * Note: "pathtype" is the NodeTag of the Plan node we could build from this * Path.  It is partially redundant with the Path's NodeTag, but allows us * to use the same Path type for multiple Plan types where there is no need * to distinguish the Plan type during path processing. */typedef struct Path{	NodeTag		type;	RelOptInfo *parent;			/* the relation this path can build */	/* estimated execution costs for path (see costsize.c for more info) */	Cost		startup_cost;	/* cost expended before fetching any								 * tuples */	Cost		total_cost;		/* total cost (assuming all tuples								 * fetched) */	NodeTag		pathtype;		/* tag identifying scan/join method */	List	   *pathkeys;		/* sort ordering of path's output */	/* pathkeys is a List of Lists of PathKeyItem nodes; see above */} Path;/*---------- * IndexPath represents an index scan.	Although an indexscan can only read * a single relation, it can scan it more than once, potentially using a * different index during each scan.  The result is the union (OR) of all the * tuples matched during any scan.	(The executor is smart enough not to return * the same tuple more than once, even if it is matched in multiple scans.) * * 'indexinfo' is a list of IndexOptInfo nodes, one per scan to be performed. * * 'indexqual' is a list of index qualifications, also one per scan. * Each entry in 'indexqual' is a sublist of qualification expressions with * implicit AND semantics across the sublist items.  Only expressions that * are usable as indexquals (as determined by indxpath.c) may appear here. * NOTE that the semantics of the top-level list in 'indexqual' is OR * combination, while the sublists are implicitly AND combinations! * Also note that indexquals lists do not contain RestrictInfo nodes, * just bare clause expressions. * * 'indexjoinclauses' is NIL for an ordinary indexpath (one that does not * use any join clauses in the index conditions).  For an innerjoin indexpath, * it has the same structure as 'indexqual', but references the RestrictInfo * nodes from which the indexqual was built, rather than the bare clause * expressions.  (Note: there isn't necessarily a one-to-one correspondence * between RestrictInfos and expressions, because of expansion of special * indexable operators.)  We need this so that we can eliminate redundant