relation.h 56.8 KB
Newer Older
1 2
/*-------------------------------------------------------------------------
 *
3
 * relation.h
4
 *	  Definitions for planner's internal data structures.
5 6
 *
 *
7
 * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
Bruce Momjian's avatar
Add:  
Bruce Momjian committed
8
 * Portions Copyright (c) 1994, Regents of the University of California
9
 *
10
 * $PostgreSQL: pgsql/src/include/nodes/relation.h,v 1.163 2008/10/22 20:17:52 tgl Exp $
11 12 13 14 15 16
 *
 *-------------------------------------------------------------------------
 */
#ifndef RELATION_H
#define RELATION_H

17
#include "access/sdir.h"
18
#include "nodes/bitmapset.h"
19
#include "nodes/params.h"
20
#include "nodes/parsenodes.h"
21
#include "storage/block.h"
22

23

24
/*
Bruce Momjian's avatar
Bruce Momjian committed
25
 * Relids
26
 *		Set of relation identifiers (indexes into the rangetable).
27
 */
28
typedef Bitmapset *Relids;
29

30 31 32 33
/*
 * When looking for a "cheapest path", this enum specifies whether we want
 * cheapest startup cost or cheapest total cost.
 */
34 35
typedef enum CostSelector
{
36
	STARTUP_COST, TOTAL_COST
37
} CostSelector;
38

39 40 41 42 43 44 45 46
/*
 * 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 */
47
} QualCost;
48

49

50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
/*----------
 * PlannerGlobal
 *		Global information for planning/optimization
 *
 * PlannerGlobal holds state for an entire planner invocation; this state
 * is shared across all levels of sub-Queries that exist in the command being
 * planned.
 *----------
 */
typedef struct PlannerGlobal
{
	NodeTag		type;

	ParamListInfo boundParams;	/* Param values provided to planner() */

	List	   *paramlist;		/* to keep track of cross-level Params */

67 68 69 70
	List	   *subplans;		/* Plans for SubPlan nodes */

	List	   *subrtables;		/* Rangetables for SubPlan nodes */

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

73
	List	   *finalrtable;	/* "flat" rangetable for executor */
74

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

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

79 80
	Index		lastPHId;		/* highest PlaceHolderVar ID assigned */

81
	bool		transientPlan;	/* redo plan when TransactionXmin changes? */
82
} PlannerGlobal;
83

84 85 86 87
/* macro for fetching the Plan associated with a SubPlan node */
#define planner_subplan_get_plan(root, subplan) \
	((Plan *) list_nth((root)->glob->subplans, (subplan)->plan_id - 1))

88

89 90 91 92 93 94
/*----------
 * PlannerInfo
 *		Per-query information for planning/optimization
 *
 * This struct is conventionally called "root" in all the planner routines.
 * It holds links to all of the planner's working state, in addition to the
Bruce Momjian's avatar
Bruce Momjian committed
95
 * original Query.	Note that at present the planner extensively modifies
96 97 98 99 100 101 102 103 104
 * the passed-in Query data structure; someday that should stop.
 *----------
 */
typedef struct PlannerInfo
{
	NodeTag		type;

	Query	   *parse;			/* the Query being planned */

105 106 107 108
	PlannerGlobal *glob;		/* global info for current planner run */

	Index		query_level;	/* 1 at the outermost Query */

109 110
	struct PlannerInfo *parent_root; /* NULL at outermost Query */

111
	/*
112
	 * simple_rel_array holds pointers to "base rels" and "other rels" (see
113 114
	 * comments for RelOptInfo for more info).	It is indexed by rangetable
	 * index (so entry 0 is always wasted).  Entries can be NULL when an RTE
115 116
	 * does not correspond to a base relation, such as a join RTE or an
	 * unreferenced view RTE; or if the RelOptInfo hasn't been made yet.
117
	 */
118
	struct RelOptInfo **simple_rel_array;		/* All 1-rel RelOptInfos */
Bruce Momjian's avatar
Bruce Momjian committed
119
	int			simple_rel_array_size;	/* allocated size of array */
120

121 122 123 124 125 126
	/*
	 * simple_rte_array is the same length as simple_rel_array and holds
	 * pointers to the associated rangetable entries.  This lets us avoid
	 * rt_fetch(), which can be a bit slow once large inheritance sets have
	 * been expanded.
	 */
Bruce Momjian's avatar
Bruce Momjian committed
127
	RangeTblEntry **simple_rte_array;	/* rangetable as an array */
128

129 130
	/*
	 * join_rel_list is a list of all join-relation RelOptInfos we have
131 132 133 134 135 136
	 * considered in this planning run.  For small problems we just scan the
	 * list to do lookups, but when there are many join relations we build a
	 * hash table for faster lookups.  The hash table is present and valid
	 * when join_rel_hash is not NULL.	Note that we still maintain the list
	 * even when using the hash table for lookups; this simplifies life for
	 * GEQO.
137
	 */
138
	List	   *join_rel_list;	/* list of join-relation RelOptInfos */
139
	struct HTAB *join_rel_hash; /* optional hashtable for join relations */
140

141 142
	List	   *resultRelations;	/* integer list of RT indexes, or NIL */

Bruce Momjian's avatar
Bruce Momjian committed
143
	List	   *returningLists; /* list of lists of TargetEntry, or NIL */
144

145 146 147
	List	   *init_plans;		/* init SubPlans for query */

	List	   *cte_plan_ids;	/* per-CTE-item list of subplan IDs */
148

Bruce Momjian's avatar
Bruce Momjian committed
149
	List	   *eq_classes;		/* list of active EquivalenceClasses */
150

Bruce Momjian's avatar
Bruce Momjian committed
151
	List	   *canon_pathkeys; /* list of "canonical" PathKeys */
152

153 154 155
	List	   *left_join_clauses;		/* list of RestrictInfos for
										 * mergejoinable outer join clauses
										 * w/nonnullable var on left */
156

157 158 159 160 161 162
	List	   *right_join_clauses;		/* list of RestrictInfos for
										 * mergejoinable outer join clauses
										 * w/nonnullable var on right */

	List	   *full_join_clauses;		/* list of RestrictInfos for
										 * mergejoinable full join clauses */
163

164
	List	   *join_info_list;		/* list of SpecialJoinInfos */
165

Bruce Momjian's avatar
Bruce Momjian committed
166
	List	   *append_rel_list;	/* list of AppendRelInfos */
167

168 169
	List	   *placeholder_list;	/* list of PlaceHolderInfos */

170 171
	List	   *query_pathkeys; /* desired pathkeys for query_planner(), and
								 * actual pathkeys afterwards */
172

173 174 175
	List	   *group_pathkeys;		/* groupClause pathkeys, if any */
	List	   *distinct_pathkeys;	/* distinctClause pathkeys, if any */
	List	   *sort_pathkeys;		/* sortClause pathkeys, if any */
176

177 178
	List	   *initial_rels;	/* RelOptInfos we are now trying to join */

179 180
	MemoryContext planner_cxt;	/* context holding PlannerInfo */

Bruce Momjian's avatar
Bruce Momjian committed
181
	double		total_table_pages;		/* # of pages in all tables of query */
182

183
	double		tuple_fraction; /* tuple_fraction passed to query_planner */
184

185 186
	bool		hasJoinRTEs;	/* true if any RTEs are RTE_JOIN kind */
	bool		hasHavingQual;	/* true if havingQual was non-null */
Bruce Momjian's avatar
Bruce Momjian committed
187
	bool		hasPseudoConstantQuals; /* true if any RestrictInfo has
188
										 * pseudoconstant = true */
189 190 191 192 193
	bool		hasRecursion;	/* true if planning a recursive WITH item */

	/* These fields are used only when hasRecursion is true: */
	int			wt_param_id;			/* PARAM_EXEC ID for the work table */
	struct Plan *non_recursive_plan;	/* plan for non-recursive term */
194 195 196
} PlannerInfo;


197 198 199 200 201 202 203 204 205 206
/*
 * In places where it's known that simple_rte_array[] must have been prepared
 * already, we just index into it to fetch RTEs.  In code that might be
 * executed before or after entering query_planner(), use this macro.
 */
#define planner_rt_fetch(rti, root) \
	((root)->simple_rte_array ? (root)->simple_rte_array[rti] : \
	 rt_fetch(rti, (root)->parse->rtable))


207
/*----------
Bruce Momjian's avatar
Bruce Momjian committed
208
 * RelOptInfo
209
 *		Per-relation information for planning/optimization
210
 *
211
 * For planning purposes, a "base rel" is either a plain relation (a table)
212
 * or the output of a sub-SELECT or function that appears in the range table.
213 214 215
 * 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
216
 * nodes for each baserel and joinrel, and store them in the PlannerInfo's
217
 * simple_rel_array and join_rel_list respectively.
218
 *
219 220 221
 * 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.
222
 *
223
 * We also have "other rels", which are like base rels in that they refer to
224 225
 * single RT indexes; but they are not part of the join tree, and are given
 * a different RelOptKind to identify them.
226
 *
227 228 229
 * Currently the only kind of otherrels are those made for member relations
 * of an "append relation", that is an inheritance set or UNION ALL subquery.
 * An append relation has a parent RTE that is a base rel, which represents
Bruce Momjian's avatar
Bruce Momjian committed
230
 * the entire append relation.	The member RTEs are otherrels.	The parent
231 232 233 234 235
 * is present in the query join tree but the members are not.  The member
 * RTEs and otherrels are used to plan the scans of the individual tables or
 * subqueries of the append set; then the parent baserel is given an Append
 * plan comprising the best plans for the individual member rels.  (See
 * comments for AppendRelInfo for more information.)
236
 *
237 238 239 240
 * 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.
 *
241
 * Parts of this data structure are specific to various scan and join
Bruce Momjian's avatar
Bruce Momjian committed
242
 * mechanisms.	It didn't seem worth creating new node types for them.
243
 *
244
 *		relids - Set of base-relation identifiers; it is a base relation
245
 *				if there is just one, a join relation if more than one
246 247
 *		rows - estimated number of tuples in the relation after restriction
 *			   clauses have been applied (ie, output rows of a plan for it)
248
 *		width - avg. number of bytes per tuple in the relation after the
249
 *				appropriate projections have been done (ie, output width)
250 251 252 253
 *		reltargetlist - List of Var and PlaceHolderVar nodes for the values
 *						we need to output from this relation.
 *						List is in no particular order, but all rels of an
 *						appendrel set must use corresponding orders.
254
 *						NOTE: in a child relation, may contain RowExpr or
255
 *						ConvertRowtypeExpr representing a whole-row Var.
256 257
 *		pathlist - List of Path nodes, one for each potentially useful
 *				   method of generating the relation
258 259 260 261
 *		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)
262 263
 *		cheapest_unique_path - for caching cheapest path to produce unique
 *							   (no duplicates) output from relation
264
 *
265
 * If the relation is a base relation it will have these fields set:
266
 *
267 268
 *		relid - RTE index (this is redundant with the relids field, but
 *				is provided for convenience of access)
269
 *		rtekind - distinguishes plain relation, subquery, or function RTE
270 271 272 273 274 275
 *		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
276
 *		indexlist - list of IndexOptInfo nodes for relation's indexes
277 278
 *					(always NIL if it's not a table)
 *		pages - number of disk pages in relation (zero if not a table)
279
 *		tuples - number of tuples in relation (not considering restrictions)
280
 *		subplan - plan for subquery (NULL if it's not a subquery)
281
 *		subrtable - rangetable for subquery (NIL if it's not a subquery)
282 283 284 285
 *
 *		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.
286
 *
287
 *		For otherrels that are appendrel members, these fields are filled
288
 *		in just as for a baserel.
289 290 291
 *
 * The presence of the remaining fields depends on the restrictions
 * and joins that the relation participates in:
292
 *
293
 *		baserestrictinfo - List of RestrictInfo nodes, containing info about
294
 *					each non-join qualification clause in which this relation
295
 *					participates (only used for base rels)
296 297
 *		baserestrictcost - Estimated cost of evaluating the baserestrictinfo
 *					clauses at a single tuple (only used for base rels)
298
 *		joininfo  - List of RestrictInfo nodes, containing info about each
299 300 301 302
 *					join clause in which this relation participates (but
 *					note this excludes clauses that might be derivable from
 *					EquivalenceClasses)
 *		has_eclass_joins - flag that EquivalenceClass joins are possible
303
 *		index_outer_relids - only used for base rels; set of outer relids
304 305 306 307
 *					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.
308 309 310 311 312 313 314
 *
 * 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}
315
 * and should not be processed again at the level of {1 2 3}.)	Therefore,
316 317
 * the restrictinfo list in the join case appears in individual JoinPaths
 * (field joinrestrictinfo), not in the parent relation.  But it's OK for
318
 * the RelOptInfo to store the joininfo list, because that is the same
319
 * for a given rel no matter how we form it.
320 321 322 323
 *
 * 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.
324
 *----------
325
 */
326 327 328 329
typedef enum RelOptKind
{
	RELOPT_BASEREL,
	RELOPT_JOINREL,
330
	RELOPT_OTHER_MEMBER_REL
331
} RelOptKind;
332

Bruce Momjian's avatar
Bruce Momjian committed
333
typedef struct RelOptInfo
334
{
335
	NodeTag		type;
336

337 338
	RelOptKind	reloptkind;

339
	/* all relations included in this RelOptInfo */
340
	Relids		relids;			/* set of base relids (rangetable indexes) */
341

342 343 344
	/* size estimates generated by planner */
	double		rows;			/* estimated number of result tuples */
	int			width;			/* estimated avg width of result tuples */
345 346

	/* materialization information */
347
	List	   *reltargetlist;	/* Vars to be output by scan of relation */
348
	List	   *pathlist;		/* Path structures */
349 350
	struct Path *cheapest_startup_path;
	struct Path *cheapest_total_path;
351
	struct Path *cheapest_unique_path;
352

353
	/* information about a base rel (not set for join rels!) */
354
	Index		relid;
355
	RTEKind		rtekind;		/* RELATION, SUBQUERY, or FUNCTION */
356 357 358 359
	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] */
360
	List	   *indexlist;		/* list of IndexOptInfo */
361
	BlockNumber pages;
362
	double		tuples;
363
	struct Plan *subplan;		/* if subquery */
364
	List	   *subrtable;		/* if subquery */
365 366

	/* used by various scans and joins: */
367 368
	List	   *baserestrictinfo;		/* RestrictInfo structures (if base
										 * rel) */
369
	QualCost	baserestrictcost;		/* cost of evaluating the above */
370 371
	List	   *joininfo;		/* RestrictInfo structures for join clauses
								 * involving this rel */
372
	bool		has_eclass_joins;		/* T means joininfo is incomplete */
373

374 375 376 377
	/* cached info about inner indexscan paths for relation: */
	Relids		index_outer_relids;		/* other relids in indexable join
										 * clauses */
	List	   *index_inner_paths;		/* InnerIndexscanInfo nodes */
Bruce Momjian's avatar
Bruce Momjian committed
378

379
	/*
Bruce Momjian's avatar
Bruce Momjian committed
380
	 * Inner indexscans are not in the main pathlist because they are not
381 382 383
	 * 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.
384
	 */
385
} RelOptInfo;
386

387 388 389 390 391 392 393 394
/*
 * 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.
 *
395 396 397 398 399
 *		opfamily[], indexkeys[], opcintype[], fwdsortop[], revsortop[],
 *		and nulls_first[] each have ncolumns entries.
 *		Note: for historical reasons, the opfamily array has an extra entry
 *		that is always zero.  Some code scans until it sees a zero entry,
 *		rather than looking at ncolumns.
400
 *
401 402
 *		Zeroes in the indexkeys[] array indicate index columns that are
 *		expressions; there is one element in indexprs for each such column.
403
 *
Bruce Momjian's avatar
Bruce Momjian committed
404
 *		For an unordered index, the sortop arrays contains zeroes.	Note that
405 406 407
 *		fwdsortop[] and nulls_first[] describe the sort ordering of a forward
 *		indexscan; we can also consider a backward indexscan, which will
 *		generate sort order described by revsortop/!nulls_first.
408 409
 *
 *		The indexprs and indpred expressions have been run through
410
 *		prepqual.c and eval_const_expressions() for ease of matching to
411
 *		WHERE clauses. indpred is in implicit-AND form.
412 413 414 415 416 417
 */
typedef struct IndexOptInfo
{
	NodeTag		type;

	Oid			indexoid;		/* OID of the index relation */
418
	RelOptInfo *rel;			/* back-link to index's table */
419 420

	/* statistics from pg_class */
421
	BlockNumber pages;			/* number of disk pages in index */
422
	double		tuples;			/* number of index tuples in index */
423 424

	/* index descriptor information */
425
	int			ncolumns;		/* number of columns in index */
426
	Oid		   *opfamily;		/* OIDs of operator families for columns */
427
	int		   *indexkeys;		/* column numbers of index's keys, or 0 */
428
	Oid		   *opcintype;		/* OIDs of opclass declared input data types */
429 430 431
	Oid		   *fwdsortop;		/* OIDs of sort operators for each column */
	Oid		   *revsortop;		/* OIDs of sort operators for backward scan */
	bool	   *nulls_first;	/* do NULLs come first in the sort order? */
432 433
	Oid			relam;			/* OID of the access method (in pg_am) */

434
	RegProcedure amcostestimate;	/* OID of the access method's cost fcn */
435

436
	List	   *indexprs;		/* expressions for non-simple index columns */
437
	List	   *indpred;		/* predicate if a partial index, else NIL */
438 439

	bool		predOK;			/* true if predicate matches query */
440
	bool		unique;			/* true if a unique index */
441
	bool		amoptionalkey;	/* can query omit key for the first column? */
442
	bool		amsearchnulls;	/* can AM search for NULL index entries? */
443 444
} IndexOptInfo;

445

446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464
/*
 * EquivalenceClasses
 *
 * Whenever we can determine that a mergejoinable equality clause A = B is
 * not delayed by any outer join, we create an EquivalenceClass containing
 * the expressions A and B to record this knowledge.  If we later find another
 * equivalence B = C, we add C to the existing EquivalenceClass; this may
 * require merging two existing EquivalenceClasses.  At the end of the qual
 * distribution process, we have sets of values that are known all transitively
 * equal to each other, where "equal" is according to the rules of the btree
 * operator family(s) shown in ec_opfamilies.  (We restrict an EC to contain
 * only equalities whose operators belong to the same set of opfamilies.  This
 * could probably be relaxed, but for now it's not worth the trouble, since
 * nearly all equality operators belong to only one btree opclass anyway.)
 *
 * We also use EquivalenceClasses as the base structure for PathKeys, letting
 * us represent knowledge about different sort orderings being equivalent.
 * Since every PathKey must reference an EquivalenceClass, we will end up
 * with single-member EquivalenceClasses whenever a sort key expression has
Bruce Momjian's avatar
Bruce Momjian committed
465
 * not been equivalenced to anything else.	It is also possible that such an
466 467 468 469
 * EquivalenceClass will contain a volatile expression ("ORDER BY random()"),
 * which is a case that can't arise otherwise since clauses containing
 * volatile functions are never considered mergejoinable.  We mark such
 * EquivalenceClasses specially to prevent them from being merged with
470 471 472 473
 * ordinary EquivalenceClasses.  Also, for volatile expressions we have
 * to be careful to match the EquivalenceClass to the correct targetlist
 * entry: consider SELECT random() AS a, random() AS b ... ORDER BY b,a.
 * So we record the SortGroupRef of the originating sort clause.
474 475 476 477
 *
 * We allow equality clauses appearing below the nullable side of an outer join
 * to form EquivalenceClasses, but these have a slightly different meaning:
 * the included values might be all NULL rather than all the same non-null
Bruce Momjian's avatar
Bruce Momjian committed
478
 * values.	See src/backend/optimizer/README for more on that point.
479 480 481 482 483 484 485 486
 *
 * NB: if ec_merged isn't NULL, this class has been merged into another, and
 * should be ignored in favor of using the pointed-to class.
 */
typedef struct EquivalenceClass
{
	NodeTag		type;

Bruce Momjian's avatar
Bruce Momjian committed
487 488 489 490 491 492
	List	   *ec_opfamilies;	/* btree operator family OIDs */
	List	   *ec_members;		/* list of EquivalenceMembers */
	List	   *ec_sources;		/* list of generating RestrictInfos */
	List	   *ec_derives;		/* list of derived RestrictInfos */
	Relids		ec_relids;		/* all relids appearing in ec_members */
	bool		ec_has_const;	/* any pseudoconstants in ec_members? */
493 494
	bool		ec_has_volatile;	/* the (sole) member is a volatile expr */
	bool		ec_below_outer_join;	/* equivalence applies below an OJ */
Bruce Momjian's avatar
Bruce Momjian committed
495 496 497
	bool		ec_broken;		/* failed to generate needed clauses? */
	Index		ec_sortref;		/* originating sortclause label, or 0 */
	struct EquivalenceClass *ec_merged; /* set if merged into another EC */
498
} EquivalenceClass;
499

500 501 502 503 504 505 506
/*
 * If an EC contains a const and isn't below-outer-join, any PathKey depending
 * on it must be redundant, since there's only one possible value of the key.
 */
#define EC_MUST_BE_REDUNDANT(eclass)  \
	((eclass)->ec_has_const && !(eclass)->ec_below_outer_join)

507 508 509 510 511 512 513 514 515 516 517 518
/*
 * EquivalenceMember - one member expression of an EquivalenceClass
 *
 * em_is_child signifies that this element was built by transposing a member
 * for an inheritance parent relation to represent the corresponding expression
 * on an inheritance child.  The element should be ignored for all purposes
 * except constructing inner-indexscan paths for the child relation.  (Other
 * types of join are driven from transposed joininfo-list entries.)  Note
 * that the EC's ec_relids field does NOT include the child relation.
 *
 * em_datatype is usually the same as exprType(em_expr), but can be
 * different when dealing with a binary-compatible opfamily; in particular
Bruce Momjian's avatar
Bruce Momjian committed
519
 * anyarray_ops would never work without this.	Use em_datatype when
520 521 522 523 524 525 526 527 528 529 530
 * looking up a specific btree operator to work with this expression.
 */
typedef struct EquivalenceMember
{
	NodeTag		type;

	Expr	   *em_expr;		/* the expression represented */
	Relids		em_relids;		/* all relids appearing in em_expr */
	bool		em_is_const;	/* expression is pseudoconstant? */
	bool		em_is_child;	/* derived version for a child relation? */
	Oid			em_datatype;	/* the "nominal type" used by the opfamily */
531
} EquivalenceMember;
532

533 534 535
/*
 * PathKeys
 *
536 537 538 539 540 541
 * The sort ordering of a path is represented by a list of PathKey nodes.
 * An empty list implies no known ordering.  Otherwise the first item
 * represents the primary sort key, the second the first secondary sort key,
 * etc.  The value being sorted is represented by linking to an
 * EquivalenceClass containing that value and including pk_opfamily among its
 * ec_opfamilies.  This is a convenient method because it makes it trivial
Bruce Momjian's avatar
Bruce Momjian committed
542
 * to detect equivalent and closely-related orderings.	(See optimizer/README
543 544 545
 * for more information.)
 *
 * Note: pk_strategy is either BTLessStrategyNumber (for ASC) or
Bruce Momjian's avatar
Bruce Momjian committed
546
 * BTGreaterStrategyNumber (for DESC).	We assume that all ordering-capable
547
 * index types will use btree-compatible strategy numbers.
548
 */
549

550
typedef struct PathKey
551
{
552
	NodeTag		type;
553

554
	EquivalenceClass *pk_eclass;	/* the value that is ordered */
Bruce Momjian's avatar
Bruce Momjian committed
555 556 557
	Oid			pk_opfamily;	/* btree opfamily defining the ordering */
	int			pk_strategy;	/* sort direction (ASC or DESC) */
	bool		pk_nulls_first; /* do NULLs come before normal values? */
558
} PathKey;
559

560
/*
561 562 563
 * Type "Path" is used as-is for sequential-scan paths, as well as some other
 * simple plan types that we don't need any extra information in the path for.
 * For other path types it is the first component of a larger struct.
Tom Lane's avatar
Tom Lane committed
564 565 566 567 568
 *
 * 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.
569
 */
570 571 572

typedef struct Path
{
573
	NodeTag		type;
574

575 576
	NodeTag		pathtype;		/* tag identifying scan/join method */

577
	RelOptInfo *parent;			/* the relation this path can build */
578

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

583
	List	   *pathkeys;		/* sort ordering of path's output */
584
	/* pathkeys is a List of PathKey nodes; see above */
585
} Path;
586

587
/*----------
588
 * IndexPath represents an index scan over a single index.
589
 *
590
 * 'indexinfo' is the index to be scanned.
591
 *
592 593 594
 * 'indexclauses' is a list of index qualification clauses, with implicit
 * AND semantics across the list.  Each clause is a RestrictInfo node from
 * the query's WHERE or JOIN conditions.
595 596
 *
 * 'indexquals' has the same structure as 'indexclauses', but it contains
597
 * the actual indexqual conditions that can be used with the index.
598 599 600 601 602 603
 * In simple cases this is identical to 'indexclauses', but when special
 * indexable operators appear in 'indexclauses', they are replaced by the
 * derived indexscannable conditions in 'indexquals'.
 *
 * 'isjoininner' is TRUE if the path is a nestloop inner scan (that is,
 * some of the index conditions are join rather than restriction clauses).
604 605 606
 * Note that the path costs will be calculated differently from a plain
 * indexscan in this case, and in addition there's a special 'rows' value
 * different from the parent RelOptInfo's (see below).
607
 *
608 609 610 611 612 613 614 615
 * 'indexscandir' is one of:
 *		ForwardScanDirection: forward scan of an ordered index
 *		BackwardScanDirection: backward scan of an ordered index
 *		NoMovementScanDirection: scan of an unordered index, or don't care
 * (The executor doesn't care whether it gets ForwardScanDirection or
 * NoMovementScanDirection for an indexscan, but the planner wants to
 * distinguish ordered from unordered indexes for building pathkeys.)
 *
616 617
 * 'indextotalcost' and 'indexselectivity' are saved in the IndexPath so that
 * we need not recompute them when considering using the same index in a
618 619
 * bitmap index/heap scan (see BitmapHeapPath).  The costs of the IndexPath
 * itself represent the costs of an IndexScan plan type.
620
 *
621 622
 * 'rows' is the estimated result tuple count for the indexscan.  This
 * is the same as path.parent->rows for a simple indexscan, but it is
623
 * different for a nestloop inner scan, because the additional indexquals
624 625
 * coming from join clauses make the scan more selective than the parent
 * rel's restrict clauses alone would do.
626 627
 *----------
 */
628 629
typedef struct IndexPath
{
630
	Path		path;
631
	IndexOptInfo *indexinfo;
632 633 634
	List	   *indexclauses;
	List	   *indexquals;
	bool		isjoininner;
635
	ScanDirection indexscandir;
636 637
	Cost		indextotalcost;
	Selectivity indexselectivity;
638
	double		rows;			/* estimated number of result tuples */
639
} IndexPath;
640

641 642 643 644 645 646 647 648
/*
 * BitmapHeapPath represents one or more indexscans that generate TID bitmaps
 * instead of directly accessing the heap, followed by AND/OR combinations
 * to produce a single bitmap, followed by a heap scan that uses the bitmap.
 * Note that the output is always considered unordered, since it will come
 * out in physical heap order no matter what the underlying indexes did.
 *
 * The individual indexscans are represented by IndexPath nodes, and any
649
 * logic on top of them is represented by a tree of BitmapAndPath and
650
 * BitmapOrPath nodes.	Notice that we can use the same IndexPath node both
651 652 653
 * to represent a regular IndexScan plan, and as the child of a BitmapHeapPath
 * that represents scanning the same index using a BitmapIndexScan.  The
 * startup_cost and total_cost figures of an IndexPath always represent the
654
 * costs to use it as a regular IndexScan.	The costs of a BitmapIndexScan
655
 * can be computed using the IndexPath's indextotalcost and indexselectivity.
656 657 658 659 660 661 662
 *
 * BitmapHeapPaths can be nestloop inner indexscans.  The isjoininner and
 * rows fields serve the same purpose as for plain IndexPaths.
 */
typedef struct BitmapHeapPath
{
	Path		path;
663
	Path	   *bitmapqual;		/* IndexPath, BitmapAndPath, BitmapOrPath */
664 665 666 667
	bool		isjoininner;	/* T if it's a nestloop inner scan */
	double		rows;			/* estimated number of result tuples */
} BitmapHeapPath;

668 669 670 671 672 673 674 675 676
/*
 * BitmapAndPath represents a BitmapAnd plan node; it can only appear as
 * part of the substructure of a BitmapHeapPath.  The Path structure is
 * a bit more heavyweight than we really need for this, but for simplicity
 * we make it a derivative of Path anyway.
 */
typedef struct BitmapAndPath
{
	Path		path;
677
	List	   *bitmapquals;	/* IndexPaths and BitmapOrPaths */
678 679 680 681 682 683 684 685 686 687 688 689
	Selectivity bitmapselectivity;
} BitmapAndPath;

/*
 * BitmapOrPath represents a BitmapOr plan node; it can only appear as
 * part of the substructure of a BitmapHeapPath.  The Path structure is
 * a bit more heavyweight than we really need for this, but for simplicity
 * we make it a derivative of Path anyway.
 */
typedef struct BitmapOrPath
{
	Path		path;
690
	List	   *bitmapquals;	/* IndexPaths and BitmapAndPaths */
691 692 693
	Selectivity bitmapselectivity;
} BitmapOrPath;

694 695
/*
 * TidPath represents a scan by TID
696
 *
697 698 699
 * tidquals is an implicitly OR'ed list of qual expressions of the form
 * "CTID = pseudoconstant" or "CTID = ANY(pseudoconstant_array)".
 * Note they are bare expressions, not RestrictInfos.
700
 */
701 702
typedef struct TidPath
{
703
	Path		path;
704
	List	   *tidquals;		/* qual(s) involving CTID = something */
705
} TidPath;
706

707 708
/*
 * AppendPath represents an Append plan, ie, successive execution of
709
 * several member plans.
710 711 712
 *
 * Note: it is possible for "subpaths" to contain only one, or even no,
 * elements.  These cases are optimized during create_append_plan.
713 714
 * In particular, an AppendPath with no subpaths is a "dummy" path that
 * is created to represent the case that a relation is provably empty.
715 716 717 718 719 720 721
 */
typedef struct AppendPath
{
	Path		path;
	List	   *subpaths;		/* list of component Paths */
} AppendPath;

722 723 724
#define IS_DUMMY_PATH(p) \
	(IsA((p), AppendPath) && ((AppendPath *) (p))->subpaths == NIL)

725
/*
726 727 728 729 730
 * ResultPath represents use of a Result plan node to compute a variable-free
 * targetlist with no underlying tables (a "SELECT expressions" query).
 * The query could have a WHERE clause, too, represented by "quals".
 *
 * Note that quals is a list of bare clauses, not RestrictInfos.
731 732 733 734
 */
typedef struct ResultPath
{
	Path		path;
735
	List	   *quals;
736
} ResultPath;
737

738 739 740 741 742 743 744 745 746 747
/*
 * MaterialPath represents use of a Material plan node, i.e., caching of
 * the output of its subpath.  This is used when the subpath is expensive
 * and needs to be scanned repeatedly, or when we need mark/restore ability
 * and the subpath doesn't have it.
 */
typedef struct MaterialPath
{
	Path		path;
	Path	   *subpath;
748
} MaterialPath;
749

750 751 752 753 754
/*
 * UniquePath represents elimination of distinct rows from the output of
 * its subpath.
 *
 * This is unlike the other Path nodes in that it can actually generate
755
 * different plans: either hash-based or sort-based implementation, or a
Bruce Momjian's avatar
Bruce Momjian committed
756
 * no-op if the input path can be proven distinct already.	The decision
757 758 759 760 761
 * is sufficiently localized that it's not worth having separate Path node
 * types.  (Note: in the no-op case, we could eliminate the UniquePath node
 * entirely and just return the subpath; but it's convenient to have a
 * UniquePath in the path tree to signal upper-level routines that the input
 * is known distinct.)
762
 */
763 764 765 766 767 768 769
typedef enum
{
	UNIQUE_PATH_NOOP,			/* input is known unique already */
	UNIQUE_PATH_HASH,			/* use hashing */
	UNIQUE_PATH_SORT			/* use sorting */
} UniquePathMethod;

770 771 772 773
typedef struct UniquePath
{
	Path		path;
	Path	   *subpath;
774
	UniquePathMethod umethod;
775 776
	List	   *in_operators;	/* equality operators of the IN clause */
	List	   *uniq_exprs;		/* expressions to be made unique */
777
	double		rows;			/* estimated number of result tuples */
778
} UniquePath;
779

780 781 782 783 784
/*
 * All join-type paths share these fields.
 */

typedef struct JoinPath
785
{
786
	Path		path;
787

788 789
	JoinType	jointype;

790 791
	Path	   *outerjoinpath;	/* path for the outer side of the join */
	Path	   *innerjoinpath;	/* path for the inner side of the join */
792

793 794 795 796
	List	   *joinrestrictinfo;		/* RestrictInfos to apply to join */

	/*
	 * See the notes for RelOptInfo to understand why joinrestrictinfo is
797 798
	 * needed in JoinPath, and can't be merged into the parent RelOptInfo.
	 */
799 800 801 802 803 804 805 806 807 808 809
} JoinPath;

/*
 * A nested-loop path needs no special fields.
 */

typedef JoinPath NestPath;

/*
 * A mergejoin path has these fields.
 *
810
 * path_mergeclauses lists the clauses (in the form of RestrictInfos)
811
 * that will be used in the merge.
812
 *
813 814 815 816
 * Note that the mergeclauses are a subset of the parent relation's
 * restriction-clause list.  Any join clauses that are not mergejoinable
 * appear only in the parent's restrict list, and must be checked by a
 * qpqual at execution time.
817 818 819 820 821
 *
 * outersortkeys (resp. innersortkeys) is NIL if the outer path
 * (resp. inner path) is already ordered appropriately for the
 * mergejoin.  If it is not NIL then it is a PathKeys list describing
 * the ordering that must be created by an explicit sort step.
822
 */
Bruce Momjian's avatar
Bruce Momjian committed
823

824 825
typedef struct MergePath
{
Bruce Momjian's avatar
Bruce Momjian committed
826
	JoinPath	jpath;
827
	List	   *path_mergeclauses;		/* join clauses to be used for merge */
828 829
	List	   *outersortkeys;	/* keys for explicit sort, if any */
	List	   *innersortkeys;	/* keys for explicit sort, if any */
830
} MergePath;
831

Bruce Momjian's avatar
Bruce Momjian committed
832
/*
833 834 835
 * A hashjoin path has these fields.
 *
 * The remarks above for mergeclauses apply for hashclauses as well.
836 837 838
 *
 * Hashjoin does not care what order its inputs appear in, so we have
 * no need for sortkeys.
Bruce Momjian's avatar
Bruce Momjian committed
839
 */
840

841
typedef struct HashPath
842
{
843
	JoinPath	jpath;
844
	List	   *path_hashclauses;		/* join clauses used for hashing */
845
} HashPath;
846

Bruce Momjian's avatar
Bruce Momjian committed
847
/*
848
 * Restriction clause info.
849
 *
850
 * We create one of these for each AND sub-clause of a restriction condition
851 852 853 854
 * (WHERE or JOIN/ON clause).  Since the restriction clauses are logically
 * ANDed, we can use any one of them or any subset of them to filter out
 * tuples, without having to evaluate the rest.  The RestrictInfo node itself
 * stores data used by the optimizer while choosing the best query plan.
855
 *
856 857
 * If a restriction clause references a single base relation, it will appear
 * in the baserestrictinfo list of the RelOptInfo for that base rel.
858
 *
859
 * If a restriction clause references more than one base rel, it will
860 861
 * appear in the joininfo list of every RelOptInfo that describes a strict
 * subset of the base rels mentioned in the clause.  The joininfo lists are
862
 * used to drive join tree building by selecting plausible join candidates.
863 864 865
 * The clause cannot actually be applied until we have built a join rel
 * containing all the base rels it references, however.
 *
866 867 868
 * When we construct a join rel that includes all the base rels referenced
 * in a multi-relation restriction clause, we place that clause into the
 * joinrestrictinfo lists of paths for the join rel, if neither left nor
869
 * right sub-path includes all base rels referenced in the clause.	The clause
870 871
 * will be applied at that join level, and will not propagate any further up
 * the join tree.  (Note: the "predicate migration" code was once intended to
872 873 874 875 876 877 878 879
 * push restriction clauses up and down the plan tree based on evaluation
 * costs, but it's dead code and is unlikely to be resurrected in the
 * foreseeable future.)
 *
 * Note that in the presence of more than two rels, a multi-rel restriction
 * might reach different heights in the join tree depending on the join
 * sequence we use.  So, these clauses cannot be associated directly with
 * the join RelOptInfo, but must be kept track of on a per-join-path basis.
880
 *
881 882 883 884 885 886 887 888 889
 * RestrictInfos that represent equivalence conditions (i.e., mergejoinable
 * equalities that are not outerjoin-delayed) are handled a bit differently.
 * Initially we attach them to the EquivalenceClasses that are derived from
 * them.  When we construct a scan or join path, we look through all the
 * EquivalenceClasses and generate derived RestrictInfos representing the
 * minimal set of conditions that need to be checked for this particular scan
 * or join to enforce that all members of each EquivalenceClass are in fact
 * equal in all rows emitted by the scan or join.
 *
890 891
 * When dealing with outer joins we have to be very careful about pushing qual
 * clauses up and down the tree.  An outer join's own JOIN/ON conditions must
892 893 894 895 896
 * be evaluated exactly at that join node, unless they are "degenerate"
 * conditions that reference only Vars from the nullable side of the join.
 * Quals appearing in WHERE or in a JOIN above the outer join cannot be pushed
 * down below the outer join, if they reference any nullable Vars.
 * RestrictInfo nodes contain a flag to indicate whether a qual has been
897 898 899
 * pushed down to a lower level than its original syntactic placement in the
 * join tree would suggest.  If an outer join prevents us from pushing a qual
 * down to its "natural" semantic level (the level associated with just the
900 901
 * base rels used in the qual) then we mark the qual with a "required_relids"
 * value including more than just the base rels it actually uses.  By
902
 * pretending that the qual references all the rels required to form the outer
903 904 905
 * join, we prevent it from being evaluated below the outer join's joinrel.
 * When we do form the outer join's joinrel, we still need to distinguish
 * those quals that are actually in that join's JOIN/ON condition from those
906
 * that appeared elsewhere in the tree and were pushed down to the join rel
907
 * because they used no other rels.  That's what the is_pushed_down flag is
908
 * for; it tells us that a qual is not an OUTER JOIN qual for the set of base
Bruce Momjian's avatar
Bruce Momjian committed
909
 * rels listed in required_relids.	A clause that originally came from WHERE
910 911 912 913
 * or an INNER JOIN condition will *always* have its is_pushed_down flag set.
 * It's possible for an OUTER JOIN clause to be marked is_pushed_down too,
 * if we decide that it can be pushed down into the nullable side of the join.
 * In that case it acts as a plain filter qual for wherever it gets evaluated.
914 915
 * (In short, is_pushed_down is only false for non-degenerate outer join
 * conditions.  Possibly we should rename it to reflect that meaning?)
916
 *
917 918 919 920
 * RestrictInfo nodes also contain an outerjoin_delayed flag, which is true
 * if the clause's applicability must be delayed due to any outer joins
 * appearing below its own syntactic level (ie, it references any Vars from
 * the nullable side of any lower outer join).
921
 *
922
 * In general, the referenced clause might be arbitrarily complex.	The
923
 * kinds of clauses we can handle as indexscan quals, mergejoin clauses,
924 925 926
 * or hashjoin clauses are limited (e.g., no volatile functions).  The code
 * for each kind of path is responsible for identifying the restrict clauses
 * it can use and ignoring the rest.  Clauses not implemented by an indexscan,
927
 * mergejoin, or hashjoin will be placed in the plan qual or joinqual field
928
 * of the finished Plan node, where they will be enforced by general-purpose
929 930 931
 * qual-expression-evaluation code.  (But we are still entitled to count
 * their selectivity when estimating the result tuple count, if we
 * can guess what it is...)
932 933 934 935 936 937
 *
 * When the referenced clause is an OR clause, we generate a modified copy
 * in which additional RestrictInfo nodes are inserted below the top-level
 * OR/AND structure.  This is a convenience for OR indexscan processing:
 * indexquals taken from either the top level or an OR subclause will have
 * associated RestrictInfo nodes.
938 939 940 941 942 943 944 945 946
 *
 * The can_join flag is set true if the clause looks potentially useful as
 * a merge or hash join clause, that is if it is a binary opclause with
 * nonoverlapping sets of relids referenced in the left and right sides.
 * (Whether the operator is actually merge or hash joinable isn't checked,
 * however.)
 *
 * The pseudoconstant flag is set true if the clause contains no Vars of
 * the current query level and no volatile functions.  Such a clause can be
Bruce Momjian's avatar
Bruce Momjian committed
947
 * pulled out and used as a one-time qual in a gating Result node.	We keep
948 949 950 951 952 953
 * pseudoconstant clauses in the same lists as other RestrictInfos so that
 * the regular clause-pushing machinery can assign them to the correct join
 * level, but they need to be treated specially for cost and selectivity
 * estimates.  Note that a pseudoconstant clause can never be an indexqual
 * or merge or hash join clause, so it's of no interest to large parts of
 * the planner.
954 955 956
 *
 * When join clauses are generated from EquivalenceClasses, there may be
 * several equally valid ways to enforce join equivalence, of which we need
Bruce Momjian's avatar
Bruce Momjian committed
957
 * apply only one.	We mark clauses of this kind by setting parent_ec to
958 959
 * point to the generating EquivalenceClass.  Multiple clauses with the same
 * parent_ec in the same join are redundant.
Bruce Momjian's avatar
Bruce Momjian committed
960
 */
961

962
typedef struct RestrictInfo
963
{
964
	NodeTag		type;
965

966 967
	Expr	   *clause;			/* the represented clause of WHERE or JOIN */

Bruce Momjian's avatar
Bruce Momjian committed
968
	bool		is_pushed_down; /* TRUE if clause was pushed down in level */
969

970
	bool		outerjoin_delayed;	/* TRUE if delayed by lower outer join */
971

972 973
	bool		can_join;		/* see comment above */

Bruce Momjian's avatar
Bruce Momjian committed
974
	bool		pseudoconstant; /* see comment above */
975

976
	/* The set of relids (varnos) actually referenced in the clause: */
977 978
	Relids		clause_relids;

979 980 981
	/* The set of relids required to evaluate the clause: */
	Relids		required_relids;

982 983 984 985
	/* These fields are set for any binary opclause: */
	Relids		left_relids;	/* relids in left side of clause */
	Relids		right_relids;	/* relids in right side of clause */

986 987
	/* This field is NULL unless clause is an OR clause: */
	Expr	   *orclause;		/* modified clause with RestrictInfos */
988

989 990 991
	/* This field is NULL unless clause is potentially redundant: */
	EquivalenceClass *parent_ec;	/* generating EquivalenceClass */

992
	/* cache space for cost and selectivity */
993
	QualCost	eval_cost;		/* eval cost of clause; -1 if not yet set */
994
	Selectivity this_selec;		/* selectivity; -1 if not yet set */
995

996 997
	/* valid if clause is mergejoinable, else NIL */
	List	   *mergeopfamilies;	/* opfamilies containing clause operator */
998

999 1000
	/* cache space for mergeclause processing; NULL if not yet set */
	EquivalenceClass *left_ec;	/* EquivalenceClass containing lefthand */
Bruce Momjian's avatar
Bruce Momjian committed
1001 1002
	EquivalenceClass *right_ec; /* EquivalenceClass containing righthand */
	EquivalenceMember *left_em; /* EquivalenceMember for lefthand */
1003 1004
	EquivalenceMember *right_em;	/* EquivalenceMember for righthand */
	List	   *scansel_cache;	/* list of MergeScanSelCache structs */
1005

1006 1007
	/* transient workspace for use while considering a specific join path */
	bool		outer_is_left;	/* T = outer var on left, F = on right */
1008

1009
	/* valid if clause is hashjoinable, else InvalidOid: */
1010
	Oid			hashjoinoperator;		/* copy of clause operator */
1011 1012

	/* cache space for hashclause processing; -1 if not yet set */
1013
	Selectivity left_bucketsize;	/* avg bucketsize of left side */
1014
	Selectivity right_bucketsize;		/* avg bucketsize of right side */
1015
} RestrictInfo;
1016

1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030
/*
 * Since mergejoinscansel() is a relatively expensive function, and would
 * otherwise be invoked many times while planning a large join tree,
 * we go out of our way to cache its results.  Each mergejoinable
 * RestrictInfo carries a list of the specific sort orderings that have
 * been considered for use with it, and the resulting selectivities.
 */
typedef struct MergeScanSelCache
{
	/* Ordering details (cache lookup key) */
	Oid			opfamily;		/* btree opfamily defining the ordering */
	int			strategy;		/* sort direction (ASC or DESC) */
	bool		nulls_first;	/* do NULLs come before normal values? */
	/* Results */
1031 1032 1033 1034
	Selectivity leftstartsel;	/* first-join fraction for clause left side */
	Selectivity leftendsel;		/* last-join fraction for clause left side */
	Selectivity rightstartsel;	/* first-join fraction for clause right side */
	Selectivity rightendsel;	/* last-join fraction for clause right side */
1035
} MergeScanSelCache;
1036

1037 1038 1039 1040 1041 1042 1043 1044 1045
/*
 * Inner indexscan info.
 *
 * An inner indexscan is one that uses one or more joinclauses as index
 * conditions (perhaps in addition to plain restriction clauses).  So it
 * can only be used as the inner path of a nestloop join where the outer
 * relation includes all other relids appearing in those joinclauses.
 * The set of usable joinclauses, and thus the best inner indexscan,
 * thus varies depending on which outer relation we consider; so we have
1046
 * to recompute the best such paths for every join.  To avoid lots of
1047
 * redundant computation, we cache the results of such searches.  For
1048 1049
 * each relation we compute the set of possible otherrelids (all relids
 * appearing in joinquals that could become indexquals for this table).
1050 1051
 * Two outer relations whose relids have the same intersection with this
 * set will have the same set of available joinclauses and thus the same
1052
 * best inner indexscans for the inner relation.  By taking the intersection
1053 1054
 * before scanning the cache, we avoid recomputing when considering
 * join rels that differ only by the inclusion of irrelevant other rels.
1055 1056 1057 1058
 *
 * The search key also includes a bool showing whether the join being
 * considered is an outer join.  Since we constrain the join order for
 * outer joins, I believe that this bool can only have one possible value
1059
 * for any particular lookup key; but store it anyway to avoid confusion.
1060 1061 1062 1063 1064 1065 1066 1067
 */

typedef struct InnerIndexscanInfo
{
	NodeTag		type;
	/* The lookup key: */
	Relids		other_relids;	/* a set of relevant other relids */
	bool		isouterjoin;	/* true if join is outer */
1068
	/* Best paths for this lookup key (NULL if no available indexscans): */
Bruce Momjian's avatar
Bruce Momjian committed
1069 1070
	Path	   *cheapest_startup_innerpath;		/* cheapest startup cost */
	Path	   *cheapest_total_innerpath;		/* cheapest total cost */
1071
} InnerIndexscanInfo;
1072

1073
/*
1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096
 * "Flattened SubLinks"
 *
 * When we pull an IN or EXISTS SubLink up into the parent query, the
 * join conditions extracted from the IN/EXISTS clause need to be specially
 * treated in distribute_qual_to_rels processing.  We handle this by
 * wrapping such expressions in a FlattenedSubLink node that identifies
 * the join they come from.  The FlattenedSubLink node is discarded after
 * distribute_qual_to_rels, having served its purpose.
 *
 * Although the planner treats this as an expression node type, it is not
 * recognized by the parser or executor, so we declare it here rather than
 * in primnodes.h.
 */

typedef struct FlattenedSubLink
{
	Expr		xpr;
	JoinType	jointype;		/* must be JOIN_SEMI or JOIN_ANTI */
	Relids		lefthand;		/* base relids treated as syntactic LHS */
	Relids		righthand;		/* base relids syntactically within RHS */
	Expr	   *quals;			/* join quals (in explicit-AND format) */
} FlattenedSubLink;

1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119
/*
 * Placeholder node for an expression to be evaluated below the top level
 * of a plan tree.  This is used during planning to represent the contained
 * expression.  At the end of the planning process it is replaced by either
 * the contained expression or a Var referring to a lower-level evaluation of
 * the contained expression.  Typically the evaluation occurs below an outer
 * join, and Var references above the outer join might thereby yield NULL
 * instead of the expression value.
 *
 * Although the planner treats this as an expression node type, it is not
 * recognized by the parser or executor, so we declare it here rather than
 * in primnodes.h.
 */

typedef struct PlaceHolderVar
{
	Expr		xpr;
	Expr	   *phexpr;			/* the represented expression */
	Relids		phrels;			/* base relids syntactically within expr src */
	Index		phid;			/* ID for PHV (unique within planner run) */
	Index		phlevelsup;		/* > 0 if PHV belongs to outer query */
} PlaceHolderVar;

1120 1121
/*
 * "Special join" info.
1122 1123
 *
 * One-sided outer joins constrain the order of joining partially but not
Bruce Momjian's avatar
Bruce Momjian committed
1124
 * completely.	We flatten such joins into the planner's top-level list of
1125 1126 1127 1128 1129 1130 1131 1132 1133 1134
 * relations to join, but record information about each outer join in a
 * SpecialJoinInfo struct.  These structs are kept in the PlannerInfo node's
 * join_info_list.
 *
 * Similarly, semijoins and antijoins created by flattening IN (subselect)
 * and EXISTS(subselect) clauses create partial constraints on join order.
 * These are likewise recorded in SpecialJoinInfo structs.
 *
 * We make SpecialJoinInfos for FULL JOINs even though there is no flexibility
 * of planning for them, because this simplifies make_join_rel()'s API.
1135 1136
 *
 * min_lefthand and min_righthand are the sets of base relids that must be
1137 1138 1139
 * available on each side when performing the special join.  lhs_strict is
 * true if the special join's condition cannot succeed when the LHS variables
 * are all NULL (this means that an outer join can commute with upper-level
1140 1141 1142 1143 1144 1145
 * outer joins even if it appears in their RHS).  We don't bother to set
 * lhs_strict for FULL JOINs, however.
 *
 * It is not valid for either min_lefthand or min_righthand to be empty sets;
 * if they were, this would break the logic that enforces join order.
 *
1146
 * syn_lefthand and syn_righthand are the sets of base relids that are
1147 1148
 * syntactically below this special join.  (These are needed to help compute
 * min_lefthand and min_righthand for higher joins.)
1149
 *
1150 1151 1152 1153
 * delay_upper_joins is set TRUE if we detect a pushed-down clause that has
 * to be evaluated after this join is formed (because it references the RHS).
 * Any outer joins that have such a clause and this join in their RHS cannot
 * commute with this join, because that would leave noplace to check the
Bruce Momjian's avatar
Bruce Momjian committed
1154
 * pushed-down clause.	(We don't track this for FULL JOINs, either.)
1155
 *
1156 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170
 * join_quals is an implicit-AND list of the quals syntactically associated
 * with the join (they may or may not end up being applied at the join level).
 * This is just a side list and does not drive actual application of quals.
 * For JOIN_SEMI joins, this is cleared to NIL in create_unique_path() if
 * the join is found not to be suitable for a uniqueify-the-RHS plan.
 *
 * jointype is never JOIN_RIGHT; a RIGHT JOIN is handled by switching
 * the inputs to make it a LEFT JOIN.  So the allowed values of jointype
 * in a join_info_list member are only LEFT, FULL, SEMI, or ANTI.
 *
 * For purposes of join selectivity estimation, we create transient
 * SpecialJoinInfo structures for regular inner joins; so it is possible
 * to have jointype == JOIN_INNER in such a structure, even though this is
 * not allowed within join_info_list.  Note that lhs_strict, delay_upper_joins,
 * and join_quals are not set meaningfully for such structs.
1171 1172
 */

1173
typedef struct SpecialJoinInfo
1174 1175 1176 1177
{
	NodeTag		type;
	Relids		min_lefthand;	/* base relids in minimum LHS for join */
	Relids		min_righthand;	/* base relids in minimum RHS for join */
1178 1179
	Relids		syn_lefthand;	/* base relids syntactically within LHS */
	Relids		syn_righthand;	/* base relids syntactically within RHS */
1180
	JoinType	jointype;		/* always INNER, LEFT, FULL, SEMI, or ANTI */
1181
	bool		lhs_strict;		/* joinclause is strict for some LHS rel */
Bruce Momjian's avatar
Bruce Momjian committed
1182
	bool		delay_upper_joins;		/* can't commute with upper RHS */
1183 1184
	List	   *join_quals;		/* join quals, in implicit-AND list format */
} SpecialJoinInfo;
1185

1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222
/*
 * Append-relation info.
 *
 * When we expand an inheritable table or a UNION-ALL subselect into an
 * "append relation" (essentially, a list of child RTEs), we build an
 * AppendRelInfo for each child RTE.  The list of AppendRelInfos indicates
 * which child RTEs must be included when expanding the parent, and each
 * node carries information needed to translate Vars referencing the parent
 * into Vars referencing that child.
 *
 * These structs are kept in the PlannerInfo node's append_rel_list.
 * Note that we just throw all the structs into one list, and scan the
 * whole list when desiring to expand any one parent.  We could have used
 * a more complex data structure (eg, one list per parent), but this would
 * be harder to update during operations such as pulling up subqueries,
 * and not really any easier to scan.  Considering that typical queries
 * will not have many different append parents, it doesn't seem worthwhile
 * to complicate things.
 *
 * Note: after completion of the planner prep phase, any given RTE is an
 * append parent having entries in append_rel_list if and only if its
 * "inh" flag is set.  We clear "inh" for plain tables that turn out not
 * to have inheritance children, and (in an abuse of the original meaning
 * of the flag) we set "inh" for subquery RTEs that turn out to be
 * flattenable UNION ALL queries.  This lets us avoid useless searches
 * of append_rel_list.
 *
 * Note: the data structure assumes that append-rel members are single
 * baserels.  This is OK for inheritance, but it prevents us from pulling
 * up a UNION ALL member subquery if it contains a join.  While that could
 * be fixed with a more complex data structure, at present there's not much
 * point because no improvement in the plan could result.
 */

typedef struct AppendRelInfo
{
	NodeTag		type;
Bruce Momjian's avatar
Bruce Momjian committed
1223

1224
	/*
Bruce Momjian's avatar
Bruce Momjian committed
1225 1226 1227 1228
	 * These fields uniquely identify this append relationship.  There can be
	 * (in fact, always should be) multiple AppendRelInfos for the same
	 * parent_relid, but never more than one per child_relid, since a given
	 * RTE cannot be a child of more than one append parent.
1229 1230 1231
	 */
	Index		parent_relid;	/* RT index of append parent rel */
	Index		child_relid;	/* RT index of append child rel */
Bruce Momjian's avatar
Bruce Momjian committed
1232

1233 1234 1235
	/*
	 * For an inheritance appendrel, the parent and child are both regular
	 * relations, and we store their rowtype OIDs here for use in translating
Bruce Momjian's avatar
Bruce Momjian committed
1236
	 * whole-row Vars.	For a UNION-ALL appendrel, the parent and child are
1237 1238
	 * both subqueries with no named rowtype, and we store InvalidOid here.
	 */
Bruce Momjian's avatar
Bruce Momjian committed
1239
	Oid			parent_reltype; /* OID of parent's composite type */
1240 1241 1242
	Oid			child_reltype;	/* OID of child's composite type */

	/*
Bruce Momjian's avatar
Bruce Momjian committed
1243 1244 1245 1246
	 * The N'th element of this list is the integer column number of the child
	 * column corresponding to the N'th column of the parent. A list element
	 * is zero if it corresponds to a dropped column of the parent (this is
	 * only possible for inheritance cases, not UNION ALL).
1247 1248 1249 1250
	 */
	List	   *col_mappings;	/* list of child attribute numbers */

	/*
Bruce Momjian's avatar
Bruce Momjian committed
1251 1252 1253 1254 1255 1256
	 * The N'th element of this list is a Var or expression representing the
	 * child column corresponding to the N'th column of the parent. This is
	 * used to translate Vars referencing the parent rel into references to
	 * the child.  A list element is NULL if it corresponds to a dropped
	 * column of the parent (this is only possible for inheritance cases, not
	 * UNION ALL).
1257 1258
	 *
	 * This might seem redundant with the col_mappings data, but it is handy
Bruce Momjian's avatar
Bruce Momjian committed
1259 1260 1261 1262
	 * because flattening of sub-SELECTs that are members of a UNION ALL will
	 * cause changes in the expressions that need to be substituted for a
	 * parent Var.	Adjusting this data structure lets us track what really
	 * needs to be substituted.
1263 1264
	 *
	 * Notice we only store entries for user columns (attno > 0).  Whole-row
Bruce Momjian's avatar
Bruce Momjian committed
1265 1266
	 * Vars are special-cased, and system columns (attno < 0) need no special
	 * translation since their attnos are the same for all tables.
1267
	 *
Bruce Momjian's avatar
Bruce Momjian committed
1268 1269
	 * Caution: the Vars have varlevelsup = 0.	Be careful to adjust as needed
	 * when copying into a subquery.
1270
	 */
Bruce Momjian's avatar
Bruce Momjian committed
1271 1272
	List	   *translated_vars;	/* Expressions in the child's Vars */

1273
	/*
Bruce Momjian's avatar
Bruce Momjian committed
1274 1275 1276
	 * We store the parent table's OID here for inheritance, or InvalidOid for
	 * UNION ALL.  This is only needed to help in generating error messages if
	 * an attempt is made to reference a dropped parent column.
1277 1278 1279 1280
	 */
	Oid			parent_reloid;	/* OID of parent relation */
} AppendRelInfo;

1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292
/*
 * For each distinct placeholder expression generated during planning, we
 * store a PlaceHolderInfo node in the PlannerInfo node's placeholder_list.
 * This stores info that is needed centrally rather than in each copy of the
 * PlaceHolderVar.  The phid fields identify which PlaceHolderInfo goes with
 * each PlaceHolderVar.  Note that phid is unique throughout a planner run,
 * not just within a query level --- this is so that we need not reassign ID's
 * when pulling a subquery into its parent.
 *
 * The idea is to evaluate the expression at (only) the ph_eval_at join level,
 * then allow it to bubble up like a Var until the ph_needed join level.
 * ph_needed has the same definition as attr_needed for a regular Var.
1293 1294 1295
 *
 * We create a PlaceHolderInfo only after determining that the PlaceHolderVar
 * is actually referenced in the plan tree.
1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308
 */

typedef struct PlaceHolderInfo
{
	NodeTag		type;

	Index		phid;			/* ID for PH (unique within planner run) */
	PlaceHolderVar *ph_var;		/* copy of PlaceHolderVar tree */
	Relids		ph_eval_at;		/* lowest level we can evaluate value at */
	Relids		ph_needed;		/* highest level the value is needed at */
	int32		ph_width;		/* estimated attribute width */
} PlaceHolderInfo;

1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 1336 1337 1338 1339 1340 1341 1342 1343
/*
 * glob->paramlist keeps track of the PARAM_EXEC slots that we have decided
 * we need for the query.  At runtime these slots are used to pass values
 * either down into subqueries (for outer references in subqueries) or up out
 * of subqueries (for the results of a subplan).  The n'th entry in the list
 * (n counts from 0) corresponds to Param->paramid = n.
 *
 * Each paramlist item shows the absolute query level it is associated with,
 * where the outermost query is level 1 and nested subqueries have higher
 * numbers.  The item the parameter slot represents can be one of three kinds:
 *
 * A Var: the slot represents a variable of that level that must be passed
 * down because subqueries have outer references to it.  The varlevelsup
 * value in the Var will always be zero.
 *
 * An Aggref (with an expression tree representing its argument): the slot
 * represents an aggregate expression that is an outer reference for some
 * subquery.  The Aggref itself has agglevelsup = 0, and its argument tree
 * is adjusted to match in level.
 *
 * A Param: the slot holds the result of a subplan (it is a setParam item
 * for that subplan).  The absolute level shown for such items corresponds
 * to the parent query of the subplan.
 *
 * Note: we detect duplicate Var parameters and coalesce them into one slot,
 * but we do not do this for Aggref or Param slots.
 */
typedef struct PlannerParamItem
{
	NodeTag		type;

	Node	   *item;			/* the Var, Aggref, or Param */
	Index		abslevel;		/* its absolute query level */
} PlannerParamItem;

1344
#endif   /* RELATION_H */