createplan.c 101 KB
Newer Older
1 2
/*-------------------------------------------------------------------------
 *
3
 * createplan.c
4 5 6
 *	  Routines to create the desired plan for processing a query.
 *	  Planning is complete, we just need to convert the selected
 *	  Path into a Plan.
7
 *
8
 * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
Bruce Momjian's avatar
Add:  
Bruce Momjian committed
9
 * Portions Copyright (c) 1994, Regents of the University of California
10 11 12
 *
 *
 * IDENTIFICATION
13
 *	  $PostgreSQL: pgsql/src/backend/optimizer/plan/createplan.c,v 1.251 2008/10/21 20:42:53 tgl Exp $
14 15 16
 *
 *-------------------------------------------------------------------------
 */
Marc G. Fournier's avatar
Marc G. Fournier committed
17
#include "postgres.h"
18

19
#include <limits.h>
20
#include <math.h>
21

22
#include "access/skey.h"
23
#include "nodes/makefuncs.h"
24
#include "nodes/nodeFuncs.h"
25
#include "optimizer/clauses.h"
Bruce Momjian's avatar
Bruce Momjian committed
26
#include "optimizer/cost.h"
27
#include "optimizer/plancat.h"
28
#include "optimizer/planmain.h"
29
#include "optimizer/predtest.h"
Bruce Momjian's avatar
Bruce Momjian committed
30
#include "optimizer/restrictinfo.h"
31
#include "optimizer/tlist.h"
32
#include "optimizer/var.h"
33
#include "parser/parse_clause.h"
34
#include "parser/parsetree.h"
Bruce Momjian's avatar
Bruce Momjian committed
35
#include "utils/lsyscache.h"
36 37


38
static Plan *create_scan_plan(PlannerInfo *root, Path *best_path);
39
static List *build_relation_tlist(RelOptInfo *rel);
40
static bool use_physical_tlist(PlannerInfo *root, RelOptInfo *rel);
41
static void disuse_physical_tlist(Plan *plan, Path *path);
42 43
static Plan *create_gating_plan(PlannerInfo *root, Plan *plan, List *quals);
static Plan *create_join_plan(PlannerInfo *root, JoinPath *best_path);
44
static Plan *create_append_plan(PlannerInfo *root, AppendPath *best_path);
45 46 47 48
static Result *create_result_plan(PlannerInfo *root, ResultPath *best_path);
static Material *create_material_plan(PlannerInfo *root, MaterialPath *best_path);
static Plan *create_unique_plan(PlannerInfo *root, UniquePath *best_path);
static SeqScan *create_seqscan_plan(PlannerInfo *root, Path *best_path,
Bruce Momjian's avatar
Bruce Momjian committed
49
					List *tlist, List *scan_clauses);
50
static IndexScan *create_indexscan_plan(PlannerInfo *root, IndexPath *best_path,
51
					  List *tlist, List *scan_clauses);
52
static BitmapHeapScan *create_bitmap_scan_plan(PlannerInfo *root,
53 54
						BitmapHeapPath *best_path,
						List *tlist, List *scan_clauses);
55
static Plan *create_bitmap_subplan(PlannerInfo *root, Path *bitmapqual,
56
					  List **qual);
57
static TidScan *create_tidscan_plan(PlannerInfo *root, TidPath *best_path,
Bruce Momjian's avatar
Bruce Momjian committed
58
					List *tlist, List *scan_clauses);
59
static SubqueryScan *create_subqueryscan_plan(PlannerInfo *root, Path *best_path,
60
						 List *tlist, List *scan_clauses);
61
static FunctionScan *create_functionscan_plan(PlannerInfo *root, Path *best_path,
62
						 List *tlist, List *scan_clauses);
63
static ValuesScan *create_valuesscan_plan(PlannerInfo *root, Path *best_path,
Bruce Momjian's avatar
Bruce Momjian committed
64
					   List *tlist, List *scan_clauses);
65 66 67 68
static CteScan *create_ctescan_plan(PlannerInfo *root, Path *best_path,
									List *tlist, List *scan_clauses);
static WorkTableScan *create_worktablescan_plan(PlannerInfo *root, Path *best_path,
												List *tlist, List *scan_clauses);
69
static NestLoop *create_nestloop_plan(PlannerInfo *root, NestPath *best_path,
70
					 Plan *outer_plan, Plan *inner_plan);
71
static MergeJoin *create_mergejoin_plan(PlannerInfo *root, MergePath *best_path,
72
					  Plan *outer_plan, Plan *inner_plan);
73
static HashJoin *create_hashjoin_plan(PlannerInfo *root, HashPath *best_path,
74
					 Plan *outer_plan, Plan *inner_plan);
75 76
static List *fix_indexqual_references(List *indexquals, IndexPath *index_path);
static Node *fix_indexqual_operand(Node *node, IndexOptInfo *index);
77
static List *get_switched_clauses(List *clauses, Relids outerrelids);
78
static List *order_qual_clauses(PlannerInfo *root, List *clauses);
79 80
static void copy_path_costsize(Plan *dest, Path *src);
static void copy_plan_costsize(Plan *dest, Plan *src);
81
static SeqScan *make_seqscan(List *qptlist, List *qpqual, Index scanrelid);
82
static IndexScan *make_indexscan(List *qptlist, List *qpqual, Index scanrelid,
83
			   Oid indexid, List *indexqual, List *indexqualorig,
84
			   ScanDirection indexscandir);
85
static BitmapIndexScan *make_bitmap_indexscan(Index scanrelid, Oid indexid,
86
					  List *indexqual,
87
					  List *indexqualorig);
88
static BitmapHeapScan *make_bitmap_heapscan(List *qptlist,
89 90 91 92
					 List *qpqual,
					 Plan *lefttree,
					 List *bitmapqualorig,
					 Index scanrelid);
93
static TidScan *make_tidscan(List *qptlist, List *qpqual, Index scanrelid,
94
			 List *tidquals);
95
static FunctionScan *make_functionscan(List *qptlist, List *qpqual,
96 97
				  Index scanrelid, Node *funcexpr, List *funccolnames,
				  List *funccoltypes, List *funccoltypmods);
98
static ValuesScan *make_valuesscan(List *qptlist, List *qpqual,
99
				Index scanrelid, List *values_lists);
100 101 102 103
static CteScan *make_ctescan(List *qptlist, List *qpqual,
							 Index scanrelid, int ctePlanId, int cteParam);
static WorkTableScan *make_worktablescan(List *qptlist, List *qpqual,
										 Index scanrelid, int wtParam);
104 105
static BitmapAnd *make_bitmap_and(List *bitmapplans);
static BitmapOr *make_bitmap_or(List *bitmapplans);
106
static NestLoop *make_nestloop(List *tlist,
107 108
			  List *joinclauses, List *otherclauses,
			  Plan *lefttree, Plan *righttree,
109
			  JoinType jointype);
110
static HashJoin *make_hashjoin(List *tlist,
111 112 113
			  List *joinclauses, List *otherclauses,
			  List *hashclauses,
			  Plan *lefttree, Plan *righttree,
114
			  JoinType jointype);
115
static Hash *make_hash(Plan *lefttree);
116
static MergeJoin *make_mergejoin(List *tlist,
117
			   List *joinclauses, List *otherclauses,
118 119 120 121
			   List *mergeclauses,
			   Oid *mergefamilies,
			   int *mergestrategies,
			   bool *mergenullsfirst,
122
			   Plan *lefttree, Plan *righttree,
123
			   JoinType jointype);
124
static Sort *make_sort(PlannerInfo *root, Plan *lefttree, int numCols,
125 126
		  AttrNumber *sortColIdx, Oid *sortOperators, bool *nullsFirst,
		  double limit_tuples);
127
static Material *make_material(Plan *lefttree);
128

129 130

/*
131
 * create_plan
132
 *	  Creates the access plan for a query by tracing backwards through the
133
 *	  desired chain of pathnodes, starting at the node 'best_path'.  For
134 135 136 137 138 139
 *	  every pathnode found, we create a corresponding plan node containing
 *	  appropriate id, target list, and qualification information.
 *
 *	  The tlists and quals in the plan tree are still in planner format,
 *	  ie, Vars still correspond to the parser's numbering.  This will be
 *	  fixed later by setrefs.c.
140
 *
141
 *	  best_path is the best access path
142
 *
143
 *	  Returns a Plan tree.
144
 */
145
Plan *
146
create_plan(PlannerInfo *root, Path *best_path)
147
{
148
	Plan	   *plan;
149 150

	switch (best_path->pathtype)
151
	{
152
		case T_SeqScan:
153 154
		case T_IndexScan:
		case T_BitmapHeapScan:
155
		case T_TidScan:
156
		case T_SubqueryScan:
157
		case T_FunctionScan:
158
		case T_ValuesScan:
159 160
		case T_CteScan:
		case T_WorkTableScan:
161
			plan = create_scan_plan(root, best_path);
162 163 164 165
			break;
		case T_HashJoin:
		case T_MergeJoin:
		case T_NestLoop:
166 167
			plan = create_join_plan(root,
									(JoinPath *) best_path);
168 169
			break;
		case T_Append:
170 171
			plan = create_append_plan(root,
									  (AppendPath *) best_path);
172
			break;
173 174 175 176
		case T_Result:
			plan = (Plan *) create_result_plan(root,
											   (ResultPath *) best_path);
			break;
177 178
		case T_Material:
			plan = (Plan *) create_material_plan(root,
179
												 (MaterialPath *) best_path);
180
			break;
181
		case T_Unique:
182 183
			plan = create_unique_plan(root,
									  (UniquePath *) best_path);
184
			break;
185
		default:
186 187
			elog(ERROR, "unrecognized node type: %d",
				 (int) best_path->pathtype);
188
			plan = NULL;		/* keep compiler quiet */
189
			break;
190 191
	}

192
	return plan;
193 194
}

195
/*
196 197
 * create_scan_plan
 *	 Create a scan plan for the parent relation of 'best_path'.
198
 */
199
static Plan *
200
create_scan_plan(PlannerInfo *root, Path *best_path)
201
{
202 203
	RelOptInfo *rel = best_path->parent;
	List	   *tlist;
204
	List	   *scan_clauses;
205
	Plan	   *plan;
206 207

	/*
208 209 210 211 212 213
	 * For table scans, rather than using the relation targetlist (which is
	 * only those Vars actually needed by the query), we prefer to generate a
	 * tlist containing all Vars in order.	This will allow the executor to
	 * optimize away projection of the table tuples, if possible.  (Note that
	 * planner.c may replace the tlist we generate here, forcing projection to
	 * occur.)
214
	 */
215
	if (use_physical_tlist(root, rel))
216
	{
217 218 219 220
		tlist = build_physical_tlist(root, rel);
		/* if fail because of dropped cols, use regular method */
		if (tlist == NIL)
			tlist = build_relation_tlist(rel);
221 222
	}
	else
223
		tlist = build_relation_tlist(rel);
224 225

	/*
Bruce Momjian's avatar
Bruce Momjian committed
226 227 228
	 * Extract the relevant restriction clauses from the parent relation. The
	 * executor must apply all these restrictions during the scan, except for
	 * pseudoconstants which we'll take care of below.
229
	 */
230
	scan_clauses = rel->baserestrictinfo;
231

232 233
	switch (best_path->pathtype)
	{
234
		case T_SeqScan:
235
			plan = (Plan *) create_seqscan_plan(root,
236
												best_path,
237 238
												tlist,
												scan_clauses);
239 240 241
			break;

		case T_IndexScan:
242
			plan = (Plan *) create_indexscan_plan(root,
243
												  (IndexPath *) best_path,
244
												  tlist,
245
												  scan_clauses);
246 247
			break;

248
		case T_BitmapHeapScan:
249
			plan = (Plan *) create_bitmap_scan_plan(root,
250
												(BitmapHeapPath *) best_path,
251 252 253 254
													tlist,
													scan_clauses);
			break;

255
		case T_TidScan:
256
			plan = (Plan *) create_tidscan_plan(root,
257
												(TidPath *) best_path,
258 259
												tlist,
												scan_clauses);
260 261
			break;

262
		case T_SubqueryScan:
263
			plan = (Plan *) create_subqueryscan_plan(root,
264
													 best_path,
265 266 267 268
													 tlist,
													 scan_clauses);
			break;

269
		case T_FunctionScan:
270
			plan = (Plan *) create_functionscan_plan(root,
271
													 best_path,
Bruce Momjian's avatar
Bruce Momjian committed
272 273
													 tlist,
													 scan_clauses);
274 275
			break;

276 277 278 279 280 281 282
		case T_ValuesScan:
			plan = (Plan *) create_valuesscan_plan(root,
												   best_path,
												   tlist,
												   scan_clauses);
			break;

283 284 285 286 287 288 289 290 291 292 293 294 295 296
		case T_CteScan:
			plan = (Plan *) create_ctescan_plan(root,
												best_path,
												tlist,
												scan_clauses);
			break;

		case T_WorkTableScan:
			plan = (Plan *) create_worktablescan_plan(root,
													  best_path,
													  tlist,
													  scan_clauses);
			break;

297
		default:
298 299
			elog(ERROR, "unrecognized node type: %d",
				 (int) best_path->pathtype);
300
			plan = NULL;		/* keep compiler quiet */
301
			break;
302 303
	}

304
	/*
Bruce Momjian's avatar
Bruce Momjian committed
305 306 307
	 * If there are any pseudoconstant clauses attached to this node, insert a
	 * gating Result node that evaluates the pseudoconstants as one-time
	 * quals.
308 309 310 311
	 */
	if (root->hasPseudoConstantQuals)
		plan = create_gating_plan(root, plan, scan_clauses);

312
	return plan;
313 314
}

315 316 317 318 319 320
/*
 * Build a target list (ie, a list of TargetEntry) for a relation.
 */
static List *
build_relation_tlist(RelOptInfo *rel)
{
321
	List	   *tlist = NIL;
322
	int			resno = 1;
323
	ListCell   *v;
324

325
	foreach(v, rel->reltargetlist)
326
	{
Bruce Momjian's avatar
Bruce Momjian committed
327
		/* Do we really need to copy here?	Not sure */
328
		Node   *node = (Node *) copyObject(lfirst(v));
329

330
		tlist = lappend(tlist, makeTargetEntry((Expr *) node,
331 332 333 334
											   resno,
											   NULL,
											   false));
		resno++;
335
	}
336
	return tlist;
337 338
}

339 340 341 342 343 344
/*
 * use_physical_tlist
 *		Decide whether to use a tlist matching relation structure,
 *		rather than only those Vars actually referenced.
 */
static bool
345
use_physical_tlist(PlannerInfo *root, RelOptInfo *rel)
346
{
347
	int			i;
348
	ListCell   *lc;
349 350

	/*
Bruce Momjian's avatar
Bruce Momjian committed
351
	 * We can do this for real relation scans, subquery scans, function scans,
352
	 * values scans, and CTE scans (but not for, eg, joins).
353
	 */
354 355
	if (rel->rtekind != RTE_RELATION &&
		rel->rtekind != RTE_SUBQUERY &&
356
		rel->rtekind != RTE_FUNCTION &&
357 358
		rel->rtekind != RTE_VALUES &&
		rel->rtekind != RTE_CTE)
359
		return false;
Bruce Momjian's avatar
Bruce Momjian committed
360

361 362 363 364 365 366
	/*
	 * Can't do it with inheritance cases either (mainly because Append
	 * doesn't project).
	 */
	if (rel->reloptkind != RELOPT_BASEREL)
		return false;
Bruce Momjian's avatar
Bruce Momjian committed
367

368
	/*
369 370 371
	 * Can't do it if any system columns or whole-row Vars are requested.
	 * (This could possibly be fixed but would take some fragile assumptions
	 * in setrefs.c, I think.)
372
	 */
373
	for (i = rel->min_attr; i <= 0; i++)
374
	{
375 376
		if (!bms_is_empty(rel->attr_needed[i - rel->min_attr]))
			return false;
377
	}
378

379 380 381 382 383 384 385 386 387 388 389 390 391
	/*
	 * Can't do it if the rel is required to emit any placeholder expressions,
	 * either.
	 */
	foreach(lc, root->placeholder_list)
	{
		PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);

		if (bms_nonempty_difference(phinfo->ph_needed, rel->relids) &&
			bms_is_subset(phinfo->ph_eval_at, rel->relids))
			return false;
	}

392 393 394
	return true;
}

395 396 397 398 399 400
/*
 * disuse_physical_tlist
 *		Switch a plan node back to emitting only Vars actually referenced.
 *
 * If the plan node immediately above a scan would prefer to get only
 * needed Vars and not a physical tlist, it must call this routine to
Bruce Momjian's avatar
Bruce Momjian committed
401
 * undo the decision made by use_physical_tlist().	Currently, Hash, Sort,
402 403 404 405 406 407 408 409 410
 * and Material nodes want this, so they don't have to store useless columns.
 */
static void
disuse_physical_tlist(Plan *plan, Path *path)
{
	/* Only need to undo it for path types handled by create_scan_plan() */
	switch (path->pathtype)
	{
		case T_SeqScan:
411 412
		case T_IndexScan:
		case T_BitmapHeapScan:
413 414 415
		case T_TidScan:
		case T_SubqueryScan:
		case T_FunctionScan:
416
		case T_ValuesScan:
417 418
		case T_CteScan:
		case T_WorkTableScan:
419
			plan->targetlist = build_relation_tlist(path->parent);
420 421 422 423 424 425
			break;
		default:
			break;
	}
}

426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449
/*
 * create_gating_plan
 *	  Deal with pseudoconstant qual clauses
 *
 * If the node's quals list includes any pseudoconstant quals, put them
 * into a gating Result node atop the already-built plan.  Otherwise,
 * return the plan as-is.
 *
 * Note that we don't change cost or size estimates when doing gating.
 * The costs of qual eval were already folded into the plan's startup cost.
 * Leaving the size alone amounts to assuming that the gating qual will
 * succeed, which is the conservative estimate for planning upper queries.
 * We certainly don't want to assume the output size is zero (unless the
 * gating qual is actually constant FALSE, and that case is dealt with in
 * clausesel.c).  Interpolating between the two cases is silly, because
 * it doesn't reflect what will really happen at runtime, and besides which
 * in most cases we have only a very bad idea of the probability of the gating
 * qual being true.
 */
static Plan *
create_gating_plan(PlannerInfo *root, Plan *plan, List *quals)
{
	List	   *pseudoconstants;

450 451 452
	/* Sort into desirable execution order while still in RestrictInfo form */
	quals = order_qual_clauses(root, quals);

453 454 455 456 457 458
	/* Pull out any pseudoconstant quals from the RestrictInfo list */
	pseudoconstants = extract_actual_clauses(quals, true);

	if (!pseudoconstants)
		return plan;

459 460
	return (Plan *) make_result(root,
								plan->targetlist,
461 462 463 464
								(Node *) pseudoconstants,
								plan);
}

465
/*
466 467
 * create_join_plan
 *	  Create a join plan for 'best_path' and (recursively) plans for its
468
 *	  inner and outer paths.
469
 */
470
static Plan *
471
create_join_plan(PlannerInfo *root, JoinPath *best_path)
472
{
473 474
	Plan	   *outer_plan;
	Plan	   *inner_plan;
475
	Plan	   *plan;
476

477 478
	outer_plan = create_plan(root, best_path->outerjoinpath);
	inner_plan = create_plan(root, best_path->innerjoinpath);
479 480 481

	switch (best_path->path.pathtype)
	{
482
		case T_MergeJoin:
483
			plan = (Plan *) create_mergejoin_plan(root,
484
												  (MergePath *) best_path,
485
												  outer_plan,
486
												  inner_plan);
487 488
			break;
		case T_HashJoin:
489
			plan = (Plan *) create_hashjoin_plan(root,
490
												 (HashPath *) best_path,
491
												 outer_plan,
492
												 inner_plan);
493 494
			break;
		case T_NestLoop:
495
			plan = (Plan *) create_nestloop_plan(root,
496
												 (NestPath *) best_path,
497
												 outer_plan,
498
												 inner_plan);
499 500
			break;
		default:
501 502
			elog(ERROR, "unrecognized node type: %d",
				 (int) best_path->path.pathtype);
503 504
			plan = NULL;		/* keep compiler quiet */
			break;
505
	}
506

507
	/*
Bruce Momjian's avatar
Bruce Momjian committed
508 509 510
	 * If there are any pseudoconstant clauses attached to this node, insert a
	 * gating Result node that evaluates the pseudoconstants as one-time
	 * quals.
511 512 513 514
	 */
	if (root->hasPseudoConstantQuals)
		plan = create_gating_plan(root, plan, best_path->joinrestrictinfo);

515
#ifdef NOT_USED
516

517
	/*
518 519 520
	 * * Expensive function pullups may have pulled local predicates * into
	 * this path node.	Put them in the qpqual of the plan node. * JMH,
	 * 6/15/92
521
	 */
522
	if (get_loc_restrictinfo(best_path) != NIL)
523
		set_qpqual((Plan) plan,
524
				   list_concat(get_qpqual((Plan) plan),
525
					   get_actual_clauses(get_loc_restrictinfo(best_path))));
526 527
#endif

528
	return plan;
529 530
}

531 532 533 534 535 536 537
/*
 * create_append_plan
 *	  Create an Append plan for 'best_path' and (recursively) plans
 *	  for its subpaths.
 *
 *	  Returns a Plan node.
 */
538
static Plan *
539
create_append_plan(PlannerInfo *root, AppendPath *best_path)
540 541
{
	Append	   *plan;
542
	List	   *tlist = build_relation_tlist(best_path->path.parent);
543
	List	   *subplans = NIL;
544
	ListCell   *subpaths;
545

546
	/*
547 548
	 * It is possible for the subplans list to contain only one entry, or even
	 * no entries.	Handle these cases specially.
549
	 *
550 551 552 553
	 * XXX ideally, if there's just one entry, we'd not bother to generate an
	 * Append node but just return the single child.  At the moment this does
	 * not work because the varno of the child scan plan won't match the
	 * parent-rel Vars it'll be asked to emit.
554 555 556 557
	 */
	if (best_path->subpaths == NIL)
	{
		/* Generate a Result plan with constant-FALSE gating qual */
558 559
		return (Plan *) make_result(root,
									tlist,
560 561 562 563 564 565
									(Node *) list_make1(makeBoolConst(false,
																	  false)),
									NULL);
	}

	/* Normal case with multiple subpaths */
566 567
	foreach(subpaths, best_path->subpaths)
	{
568 569
		Path	   *subpath = (Path *) lfirst(subpaths);

570 571 572 573 574
		subplans = lappend(subplans, create_plan(root, subpath));
	}

	plan = make_append(subplans, false, tlist);

575
	return (Plan *) plan;
576 577
}

578 579
/*
 * create_result_plan
580 581
 *	  Create a Result plan for 'best_path'.
 *	  This is only used for the case of a query with an empty jointree.
582 583 584 585
 *
 *	  Returns a Plan node.
 */
static Result *
586
create_result_plan(PlannerInfo *root, ResultPath *best_path)
587 588
{
	List	   *tlist;
589
	List	   *quals;
590

591 592 593
	/* The tlist will be installed later, since we have no RelOptInfo */
	Assert(best_path->path.parent == NULL);
	tlist = NIL;
594

595 596
	/* best_path->quals is just bare clauses */

597
	quals = order_qual_clauses(root, best_path->quals);
598

599
	return make_result(root, tlist, (Node *) quals, NULL);
600 601
}

602 603 604 605 606 607 608 609
/*
 * create_material_plan
 *	  Create a Material plan for 'best_path' and (recursively) plans
 *	  for its subpaths.
 *
 *	  Returns a Plan node.
 */
static Material *
610
create_material_plan(PlannerInfo *root, MaterialPath *best_path)
611 612 613 614 615 616
{
	Material   *plan;
	Plan	   *subplan;

	subplan = create_plan(root, best_path->subpath);

617 618 619
	/* We don't want any excess columns in the materialized tuples */
	disuse_physical_tlist(subplan, best_path->subpath);

620
	plan = make_material(subplan);
621 622 623 624 625 626

	copy_path_costsize(&plan->plan, (Path *) best_path);

	return plan;
}

627 628 629 630 631 632 633 634
/*
 * create_unique_plan
 *	  Create a Unique plan for 'best_path' and (recursively) plans
 *	  for its subpaths.
 *
 *	  Returns a Plan node.
 */
static Plan *
635
create_unique_plan(PlannerInfo *root, UniquePath *best_path)
636 637 638
{
	Plan	   *plan;
	Plan	   *subplan;
639
	List	   *in_operators;
640
	List	   *uniq_exprs;
641 642 643
	List	   *newtlist;
	int			nextresno;
	bool		newitems;
644 645 646
	int			numGroupCols;
	AttrNumber *groupColIdx;
	int			groupColPos;
647
	ListCell   *l;
648 649 650

	subplan = create_plan(root, best_path->subpath);

651 652 653 654
	/* Done if we don't need to do any actual unique-ifying */
	if (best_path->umethod == UNIQUE_PATH_NOOP)
		return subplan;

655
	/*
656 657 658
	 * As constructed, the subplan has a "flat" tlist containing just the
	 * Vars needed here and at upper levels.  The values we are supposed
	 * to unique-ify may be expressions in these variables.  We have to
659
	 * add any such expressions to the subplan's tlist.
660
	 *
661
	 * The subplan may have a "physical" tlist if it is a simple scan plan.
662 663 664
	 * If we're going to sort, this should be reduced to the regular tlist,
	 * so that we don't sort more data than we need to.  For hashing, the
	 * tlist should be left as-is if we don't need to add any expressions;
665
	 * but if we do have to add expressions, then a projection step will be
666
	 * needed at runtime anyway, so we may as well remove unneeded items.
667 668
	 * Therefore newtlist starts from build_relation_tlist() not just a
	 * copy of the subplan's tlist; and we don't install it into the subplan
669
	 * unless we are sorting or stuff has to be added.
670
	 */
671 672
	in_operators = best_path->in_operators;
	uniq_exprs = best_path->uniq_exprs;
673

674 675
	/* initialize modified subplan tlist as just the "required" vars */
	newtlist = build_relation_tlist(best_path->path.parent);
676
	nextresno = list_length(newtlist) + 1;
677 678 679
	newitems = false;

	foreach(l, uniq_exprs)
680
	{
681 682
		Node	   *uniqexpr = lfirst(l);
		TargetEntry *tle;
683

684
		tle = tlist_member(uniqexpr, newtlist);
685
		if (!tle)
686
		{
687 688 689 690
			tle = makeTargetEntry((Expr *) uniqexpr,
								  nextresno,
								  NULL,
								  false);
691
			newtlist = lappend(newtlist, tle);
692 693
			nextresno++;
			newitems = true;
694
		}
695
	}
Bruce Momjian's avatar
Bruce Momjian committed
696

697
	if (newitems || best_path->umethod == UNIQUE_PATH_SORT)
698
	{
699
		/*
700 701
		 * If the top plan node can't do projections, we need to add a Result
		 * node to help it along.
702
		 */
703
		if (!is_projection_capable_plan(subplan))
704
			subplan = (Plan *) make_result(root, newtlist, NULL, subplan);
705 706 707 708
		else
			subplan->targetlist = newtlist;
	}

709
	/*
710 711
	 * Build control information showing which subplan output columns are to
	 * be examined by the grouping step.  Unfortunately we can't merge this
712 713 714 715 716 717 718
	 * with the previous loop, since we didn't then know which version of the
	 * subplan tlist we'd end up using.
	 */
	newtlist = subplan->targetlist;
	numGroupCols = list_length(uniq_exprs);
	groupColIdx = (AttrNumber *) palloc(numGroupCols * sizeof(AttrNumber));

719
	groupColPos = 0;
720 721 722 723 724 725 726 727 728 729
	foreach(l, uniq_exprs)
	{
		Node	   *uniqexpr = lfirst(l);
		TargetEntry *tle;

		tle = tlist_member(uniqexpr, newtlist);
		if (!tle)				/* shouldn't happen */
			elog(ERROR, "failed to find unique expression in subplan tlist");
		groupColIdx[groupColPos++] = tle->resno;
	}
730 731

	if (best_path->umethod == UNIQUE_PATH_HASH)
732
	{
Bruce Momjian's avatar
Bruce Momjian committed
733
		long		numGroups;
734
		Oid		   *groupOperators;
735 736 737

		numGroups = (long) Min(best_path->rows, (double) LONG_MAX);

738
		/*
739 740
		 * Get the hashable equality operators for the Agg node to use.
		 * Normally these are the same as the IN clause operators, but if
Bruce Momjian's avatar
Bruce Momjian committed
741 742
		 * those are cross-type operators then the equality operators are the
		 * ones for the IN clause operators' RHS datatype.
743 744 745 746 747 748 749 750
		 */
		groupOperators = (Oid *) palloc(numGroupCols * sizeof(Oid));
		groupColPos = 0;
		foreach(l, in_operators)
		{
			Oid			in_oper = lfirst_oid(l);
			Oid			eq_oper;

751
			if (!get_compatible_hash_operators(in_oper, NULL, &eq_oper))
752 753 754 755 756
				elog(ERROR, "could not find compatible hash operator for operator %u",
					 in_oper);
			groupOperators[groupColPos++] = eq_oper;
		}

757
		/*
758 759 760
		 * Since the Agg node is going to project anyway, we can give it the
		 * minimum output tlist, without any stuff we might have added to the
		 * subplan tlist.
761
		 */
762
		plan = (Plan *) make_agg(root,
763
								 build_relation_tlist(best_path->path.parent),
764 765 766 767
								 NIL,
								 AGG_HASHED,
								 numGroupCols,
								 groupColIdx,
768
								 groupOperators,
769 770 771
								 numGroups,
								 0,
								 subplan);
772 773 774
	}
	else
	{
775 776
		List	   *sortList = NIL;

777 778 779
		/* Create an ORDER BY list to sort the input compatibly */
		groupColPos = 0;
		foreach(l, in_operators)
780
		{
781 782
			Oid			in_oper = lfirst_oid(l);
			Oid			sortop;
783
			TargetEntry *tle;
784
			SortGroupClause *sortcl;
785

786
			sortop = get_ordering_op_for_equality_op(in_oper, false);
Bruce Momjian's avatar
Bruce Momjian committed
787
			if (!OidIsValid(sortop))	/* shouldn't happen */
788 789
				elog(ERROR, "could not find ordering operator for equality operator %u",
					 in_oper);
790 791
			tle = get_tle_by_resno(subplan->targetlist,
								   groupColIdx[groupColPos]);
792
			Assert(tle != NULL);
793
			sortcl = makeNode(SortGroupClause);
794 795
			sortcl->tleSortGroupRef = assignSortGroupRef(tle,
														 subplan->targetlist);
796
			sortcl->eqop = in_oper;
797 798 799 800
			sortcl->sortop = sortop;
			sortcl->nulls_first = false;
			sortList = lappend(sortList, sortcl);
			groupColPos++;
801
		}
802 803
		plan = (Plan *) make_sort_from_sortclauses(root, sortList, subplan);
		plan = (Plan *) make_unique(plan, sortList);
804 805
	}

806
	/* Adjust output size estimate (other fields should be OK already) */
807 808 809 810 811
	plan->plan_rows = best_path->rows;

	return plan;
}

812

813 814
/*****************************************************************************
 *
815
 *	BASE-RELATION SCAN METHODS
816 817 818
 *
 *****************************************************************************/

819 820

/*
821 822
 * create_seqscan_plan
 *	 Returns a seqscan plan for the base relation scanned by 'best_path'
823
 *	 with restriction clauses 'scan_clauses' and targetlist 'tlist'.
824 825
 */
static SeqScan *
826
create_seqscan_plan(PlannerInfo *root, Path *best_path,
827
					List *tlist, List *scan_clauses)
828
{
829
	SeqScan    *scan_plan;
830
	Index		scan_relid = best_path->parent->relid;
831

832 833
	/* it should be a base rel... */
	Assert(scan_relid > 0);
834
	Assert(best_path->parent->rtekind == RTE_RELATION);
835

836 837 838
	/* Sort clauses into best execution order */
	scan_clauses = order_qual_clauses(root, scan_clauses);

839 840 841
	/* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
	scan_clauses = extract_actual_clauses(scan_clauses, false);

842
	scan_plan = make_seqscan(tlist,
843
							 scan_clauses,
844
							 scan_relid);
845

846
	copy_path_costsize(&scan_plan->plan, best_path);
847

848
	return scan_plan;
849 850
}

851
/*
852
 * create_indexscan_plan
853
 *	  Returns an indexscan plan for the base relation scanned by 'best_path'
854
 *	  with restriction clauses 'scan_clauses' and targetlist 'tlist'.
855
 *
856 857 858
 * The indexquals list of the path contains implicitly-ANDed qual conditions.
 * The list can be empty --- then no index restrictions will be applied during
 * the scan.
859 860
 */
static IndexScan *
861
create_indexscan_plan(PlannerInfo *root,
862
					  IndexPath *best_path,
863
					  List *tlist,
864
					  List *scan_clauses)
865
{
866
	List	   *indexquals = best_path->indexquals;
867
	Index		baserelid = best_path->path.parent->relid;
868
	Oid			indexoid = best_path->indexinfo->indexoid;
869
	List	   *qpqual;
870 871
	List	   *stripped_indexquals;
	List	   *fixed_indexquals;
872
	ListCell   *l;
873
	IndexScan  *scan_plan;
874

875 876
	/* it should be a base rel... */
	Assert(baserelid > 0);
877
	Assert(best_path->path.parent->rtekind == RTE_RELATION);
878

879 880
	/*
	 * Build "stripped" indexquals structure (no RestrictInfos) to pass to
881
	 * executor as indexqualorig
882
	 */
883
	stripped_indexquals = get_actual_clauses(indexquals);
884 885

	/*
886
	 * The executor needs a copy with the indexkey on the left of each clause
887
	 * and with index attr numbers substituted for table ones.
888
	 */
889
	fixed_indexquals = fix_indexqual_references(indexquals, best_path);
890

891
	/*
892
	 * If this is an innerjoin scan, the indexclauses will contain join
893 894 895 896 897
	 * clauses that are not present in scan_clauses (since the passed-in value
	 * is just the rel's baserestrictinfo list).  We must add these clauses to
	 * scan_clauses to ensure they get checked.  In most cases we will remove
	 * the join clauses again below, but if a join clause contains a special
	 * operator, we need to make sure it gets into the scan_clauses.
898 899 900
	 *
	 * Note: pointer comparison should be enough to determine RestrictInfo
	 * matches.
901
	 */
902
	if (best_path->isjoininner)
903
		scan_clauses = list_union_ptr(scan_clauses, best_path->indexclauses);
904

905
	/*
906 907 908 909
	 * The qpqual list must contain all restrictions not automatically handled
	 * by the index.  All the predicates in the indexquals will be checked
	 * (either by the index itself, or by nodeIndexscan.c), but if there are
	 * any "special" operators involved then they must be included in qpqual.
910 911
	 * The upshot is that qpqual must contain scan_clauses minus whatever
	 * appears in indexquals.
912
	 *
913 914 915 916 917 918
	 * In normal cases simple pointer equality checks will be enough to spot
	 * duplicate RestrictInfos, so we try that first.  In some situations
	 * (particularly with OR'd index conditions) we may have scan_clauses that
	 * are not equal to, but are logically implied by, the index quals; so we
	 * also try a predicate_implied_by() check to see if we can discard quals
	 * that way.  (predicate_implied_by assumes its first input contains only
919 920 921 922 923 924
	 * immutable functions, so we have to check that.)
	 *
	 * We can also discard quals that are implied by a partial index's
	 * predicate, but only in a plain SELECT; when scanning a target relation
	 * of UPDATE/DELETE/SELECT FOR UPDATE, we must leave such quals in the
	 * plan so that they'll be properly rechecked by EvalPlanQual testing.
925
	 */
926 927 928 929 930 931
	qpqual = NIL;
	foreach(l, scan_clauses)
	{
		RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);

		Assert(IsA(rinfo, RestrictInfo));
932
		if (rinfo->pseudoconstant)
933
			continue;			/* we may drop pseudoconstants here */
934
		if (list_member_ptr(indexquals, rinfo))
935
			continue;
936 937
		if (!contain_mutable_functions((Node *) rinfo->clause))
		{
938
			List	   *clausel = list_make1(rinfo->clause);
939

940
			if (predicate_implied_by(clausel, indexquals))
941
				continue;
942 943 944
			if (best_path->indexinfo->indpred)
			{
				if (baserelid != root->parse->resultRelation &&
945
					get_rowmark(root->parse, baserelid) == NULL)
946 947 948 949
					if (predicate_implied_by(clausel,
											 best_path->indexinfo->indpred))
						continue;
			}
950
		}
951
		qpqual = lappend(qpqual, rinfo);
952
	}
953

954 955
	/* Sort clauses into best execution order */
	qpqual = order_qual_clauses(root, qpqual);
956

957 958 959
	/* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
	qpqual = extract_actual_clauses(qpqual, false);

960
	/* Finally ready to build the plan node */
961
	scan_plan = make_indexscan(tlist,
Bruce Momjian's avatar
Bruce Momjian committed
962
							   qpqual,
963
							   baserelid,
964 965 966
							   indexoid,
							   fixed_indexquals,
							   stripped_indexquals,
967
							   best_path->indexscandir);
968

969
	copy_path_costsize(&scan_plan->scan.plan, &best_path->path);
970
	/* use the indexscan-specific rows estimate, not the parent rel's */
971
	scan_plan->scan.plan.plan_rows = best_path->rows;
972

973
	return scan_plan;
974 975
}

976 977 978 979 980 981
/*
 * create_bitmap_scan_plan
 *	  Returns a bitmap scan plan for the base relation scanned by 'best_path'
 *	  with restriction clauses 'scan_clauses' and targetlist 'tlist'.
 */
static BitmapHeapScan *
982
create_bitmap_scan_plan(PlannerInfo *root,
983 984 985 986 987 988 989 990
						BitmapHeapPath *best_path,
						List *tlist,
						List *scan_clauses)
{
	Index		baserelid = best_path->path.parent->relid;
	Plan	   *bitmapqualplan;
	List	   *bitmapqualorig;
	List	   *qpqual;
991
	ListCell   *l;
992 993 994 995 996 997
	BitmapHeapScan *scan_plan;

	/* it should be a base rel... */
	Assert(baserelid > 0);
	Assert(best_path->path.parent->rtekind == RTE_RELATION);

998
	/* Process the bitmapqual tree into a Plan tree and qual list */
999
	bitmapqualplan = create_bitmap_subplan(root, best_path->bitmapqual,
1000
										   &bitmapqualorig);
1001

1002 1003
	/* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
	scan_clauses = extract_actual_clauses(scan_clauses, false);
1004

1005
	/*
1006 1007 1008 1009 1010 1011
	 * If this is a innerjoin scan, the indexclauses will contain join clauses
	 * that are not present in scan_clauses (since the passed-in value is just
	 * the rel's baserestrictinfo list).  We must add these clauses to
	 * scan_clauses to ensure they get checked.  In most cases we will remove
	 * the join clauses again below, but if a join clause contains a special
	 * operator, we need to make sure it gets into the scan_clauses.
1012 1013 1014
	 */
	if (best_path->isjoininner)
	{
1015
		scan_clauses = list_concat_unique(scan_clauses, bitmapqualorig);
1016 1017 1018
	}

	/*
1019 1020 1021
	 * The qpqual list must contain all restrictions not automatically handled
	 * by the index.  All the predicates in the indexquals will be checked
	 * (either by the index itself, or by nodeBitmapHeapscan.c), but if there
1022 1023 1024
	 * are any "special" operators involved then they must be added to qpqual.
	 * The upshot is that qpqual must contain scan_clauses minus whatever
	 * appears in bitmapqualorig.
1025
	 *
1026 1027 1028 1029
	 * In normal cases simple equal() checks will be enough to spot duplicate
	 * clauses, so we try that first.  In some situations (particularly with
	 * OR'd index conditions) we may have scan_clauses that are not equal to,
	 * but are logically implied by, the index quals; so we also try a
1030
	 * predicate_implied_by() check to see if we can discard quals that way.
1031
	 * (predicate_implied_by assumes its first input contains only immutable
1032 1033
	 * functions, so we have to check that.)
	 *
1034 1035
	 * Unlike create_indexscan_plan(), we need take no special thought here
	 * for partial index predicates; this is because the predicate conditions
1036 1037 1038
	 * are already listed in bitmapqualorig.  Bitmap scans have to do it that
	 * way because predicate conditions need to be rechecked if the scan's
	 * bitmap becomes lossy.
1039
	 */
1040 1041 1042
	qpqual = NIL;
	foreach(l, scan_clauses)
	{
1043
		Node	   *clause = (Node *) lfirst(l);
1044

1045
		if (list_member(bitmapqualorig, clause))
1046
			continue;
1047 1048
		if (!contain_mutable_functions(clause))
		{
1049
			List	   *clausel = list_make1(clause);
1050

1051
			if (predicate_implied_by(clausel, bitmapqualorig))
1052 1053
				continue;
		}
1054 1055
		qpqual = lappend(qpqual, clause);
	}
1056 1057 1058 1059

	/* Sort clauses into best execution order */
	qpqual = order_qual_clauses(root, qpqual);

1060
	/*
1061
	 * When dealing with special operators, we will at this point
1062 1063 1064 1065 1066 1067
	 * have duplicate clauses in qpqual and bitmapqualorig.  We may as well
	 * drop 'em from bitmapqualorig, since there's no point in making the
	 * tests twice.
	 */
	bitmapqualorig = list_difference_ptr(bitmapqualorig, qpqual);

1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083
	/* Finally ready to build the plan node */
	scan_plan = make_bitmap_heapscan(tlist,
									 qpqual,
									 bitmapqualplan,
									 bitmapqualorig,
									 baserelid);

	copy_path_costsize(&scan_plan->scan.plan, &best_path->path);
	/* use the indexscan-specific rows estimate, not the parent rel's */
	scan_plan->scan.plan.plan_rows = best_path->rows;

	return scan_plan;
}

/*
 * Given a bitmapqual tree, generate the Plan tree that implements it
1084
 *
1085 1086 1087 1088 1089 1090
 * As a byproduct, we also return in *qual a qual list (in implicit-AND
 * form, without RestrictInfos) describing the generated indexqual
 * conditions, as needed for rechecking heap tuples in lossy cases.
 * This list also includes partial-index predicates, because we have to
 * recheck predicates as well as index conditions if the scan's bitmap
 * becomes lossy.
1091 1092 1093
 *
 * Note: if you find yourself changing this, you probably need to change
 * make_restrictinfo_from_bitmapqual too.
1094 1095
 */
static Plan *
1096
create_bitmap_subplan(PlannerInfo *root, Path *bitmapqual,
1097
					  List **qual)
1098 1099 1100
{
	Plan	   *plan;

1101
	if (IsA(bitmapqual, BitmapAndPath))
1102
	{
1103
		BitmapAndPath *apath = (BitmapAndPath *) bitmapqual;
1104 1105
		List	   *subplans = NIL;
		List	   *subquals = NIL;
1106 1107
		ListCell   *l;

1108 1109 1110
		/*
		 * There may well be redundant quals among the subplans, since a
		 * top-level WHERE qual might have gotten used to form several
1111 1112 1113
		 * different index quals.  We don't try exceedingly hard to eliminate
		 * redundancies, but we do eliminate obvious duplicates by using
		 * list_concat_unique.
1114
		 */
1115
		foreach(l, apath->bitmapquals)
1116
		{
1117 1118
			Plan	   *subplan;
			List	   *subqual;
1119 1120

			subplan = create_bitmap_subplan(root, (Path *) lfirst(l),
1121
											&subqual);
1122
			subplans = lappend(subplans, subplan);
1123
			subquals = list_concat_unique(subquals, subqual);
1124
		}
1125
		plan = (Plan *) make_bitmap_and(subplans);
1126 1127 1128 1129
		plan->startup_cost = apath->path.startup_cost;
		plan->total_cost = apath->path.total_cost;
		plan->plan_rows =
			clamp_row_est(apath->bitmapselectivity * apath->path.parent->tuples);
1130
		plan->plan_width = 0;	/* meaningless */
1131
		*qual = subquals;
1132
	}
1133
	else if (IsA(bitmapqual, BitmapOrPath))
1134
	{
1135
		BitmapOrPath *opath = (BitmapOrPath *) bitmapqual;
1136 1137
		List	   *subplans = NIL;
		List	   *subquals = NIL;
1138
		bool		const_true_subqual = false;
1139 1140
		ListCell   *l;

1141
		/*
1142 1143
		 * Here, we only detect qual-free subplans.  A qual-free subplan would
		 * cause us to generate "... OR true ..."  which we may as well reduce
1144
		 * to just "true".	We do not try to eliminate redundant subclauses
1145 1146 1147 1148
		 * because (a) it's not as likely as in the AND case, and (b) we might
		 * well be working with hundreds or even thousands of OR conditions,
		 * perhaps from a long IN list.  The performance of list_append_unique
		 * would be unacceptable.
1149
		 */
1150 1151
		foreach(l, opath->bitmapquals)
		{
1152 1153
			Plan	   *subplan;
			List	   *subqual;
1154 1155

			subplan = create_bitmap_subplan(root, (Path *) lfirst(l),
1156
											&subqual);
1157
			subplans = lappend(subplans, subplan);
1158 1159 1160
			if (subqual == NIL)
				const_true_subqual = true;
			else if (!const_true_subqual)
1161 1162
				subquals = lappend(subquals,
								   make_ands_explicit(subqual));
1163
		}
Bruce Momjian's avatar
Bruce Momjian committed
1164

1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179
		/*
		 * In the presence of ScalarArrayOpExpr quals, we might have built
		 * BitmapOrPaths with just one subpath; don't add an OR step.
		 */
		if (list_length(subplans) == 1)
		{
			plan = (Plan *) linitial(subplans);
		}
		else
		{
			plan = (Plan *) make_bitmap_or(subplans);
			plan->startup_cost = opath->path.startup_cost;
			plan->total_cost = opath->path.total_cost;
			plan->plan_rows =
				clamp_row_est(opath->bitmapselectivity * opath->path.parent->tuples);
Bruce Momjian's avatar
Bruce Momjian committed
1180
			plan->plan_width = 0;		/* meaningless */
1181
		}
1182

1183 1184 1185
		/*
		 * If there were constant-TRUE subquals, the OR reduces to constant
		 * TRUE.  Also, avoid generating one-element ORs, which could happen
1186
		 * due to redundancy elimination or ScalarArrayOpExpr quals.
1187 1188 1189 1190 1191 1192 1193
		 */
		if (const_true_subqual)
			*qual = NIL;
		else if (list_length(subquals) <= 1)
			*qual = subquals;
		else
			*qual = list_make1(make_orclause(subquals));
1194 1195 1196
	}
	else if (IsA(bitmapqual, IndexPath))
	{
1197 1198
		IndexPath  *ipath = (IndexPath *) bitmapqual;
		IndexScan  *iscan;
1199
		ListCell   *l;
1200 1201

		/* Use the regular indexscan plan build machinery... */
1202
		iscan = create_indexscan_plan(root, ipath, NIL, NIL);
1203
		/* then convert to a bitmap indexscan */
1204
		plan = (Plan *) make_bitmap_indexscan(iscan->scan.scanrelid,
1205 1206
											  iscan->indexid,
											  iscan->indexqual,
1207
											  iscan->indexqualorig);
1208 1209 1210
		plan->startup_cost = 0.0;
		plan->total_cost = ipath->indextotalcost;
		plan->plan_rows =
1211
			clamp_row_est(ipath->indexselectivity * ipath->path.parent->tuples);
1212
		plan->plan_width = 0;	/* meaningless */
1213
		*qual = get_actual_clauses(ipath->indexclauses);
1214 1215 1216 1217 1218
		foreach(l, ipath->indexinfo->indpred)
		{
			Expr	   *pred = (Expr *) lfirst(l);

			/*
Bruce Momjian's avatar
Bruce Momjian committed
1219 1220 1221 1222
			 * We know that the index predicate must have been implied by the
			 * query condition as a whole, but it may or may not be implied by
			 * the conditions that got pushed into the bitmapqual.	Avoid
			 * generating redundant conditions.
1223 1224 1225 1226
			 */
			if (!predicate_implied_by(list_make1(pred), ipath->indexclauses))
				*qual = lappend(*qual, pred);
		}
1227 1228 1229 1230 1231 1232 1233 1234 1235 1236
	}
	else
	{
		elog(ERROR, "unrecognized node type: %d", nodeTag(bitmapqual));
		plan = NULL;			/* keep compiler quiet */
	}

	return plan;
}

1237
/*
1238 1239
 * create_tidscan_plan
 *	 Returns a tidscan plan for the base relation scanned by 'best_path'
1240 1241 1242
 *	 with restriction clauses 'scan_clauses' and targetlist 'tlist'.
 */
static TidScan *
1243
create_tidscan_plan(PlannerInfo *root, TidPath *best_path,
1244
					List *tlist, List *scan_clauses)
1245
{
1246
	TidScan    *scan_plan;
1247
	Index		scan_relid = best_path->path.parent->relid;
1248
	List	   *ortidquals;
1249

1250 1251
	/* it should be a base rel... */
	Assert(scan_relid > 0);
1252
	Assert(best_path->path.parent->rtekind == RTE_RELATION);
1253

1254 1255 1256
	/* Sort clauses into best execution order */
	scan_clauses = order_qual_clauses(root, scan_clauses);

1257 1258
	/* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
	scan_clauses = extract_actual_clauses(scan_clauses, false);
1259

1260
	/*
Bruce Momjian's avatar
Bruce Momjian committed
1261 1262
	 * Remove any clauses that are TID quals.  This is a bit tricky since the
	 * tidquals list has implicit OR semantics.
1263 1264 1265 1266 1267 1268
	 */
	ortidquals = best_path->tidquals;
	if (list_length(ortidquals) > 1)
		ortidquals = list_make1(make_orclause(ortidquals));
	scan_clauses = list_difference(scan_clauses, ortidquals);

1269
	scan_plan = make_tidscan(tlist,
1270 1271
							 scan_clauses,
							 scan_relid,
1272
							 best_path->tidquals);
1273

1274
	copy_path_costsize(&scan_plan->scan.plan, &best_path->path);
1275

1276
	return scan_plan;
1277 1278
}

1279
/*
1280 1281
 * create_subqueryscan_plan
 *	 Returns a subqueryscan plan for the base relation scanned by 'best_path'
1282 1283 1284
 *	 with restriction clauses 'scan_clauses' and targetlist 'tlist'.
 */
static SubqueryScan *
1285
create_subqueryscan_plan(PlannerInfo *root, Path *best_path,
1286
						 List *tlist, List *scan_clauses)
1287
{
1288
	SubqueryScan *scan_plan;
1289
	Index		scan_relid = best_path->parent->relid;
1290

1291 1292
	/* it should be a subquery base rel... */
	Assert(scan_relid > 0);
1293
	Assert(best_path->parent->rtekind == RTE_SUBQUERY);
1294

1295 1296 1297
	/* Sort clauses into best execution order */
	scan_clauses = order_qual_clauses(root, scan_clauses);

1298 1299 1300
	/* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
	scan_clauses = extract_actual_clauses(scan_clauses, false);

1301
	scan_plan = make_subqueryscan(tlist,
1302 1303
								  scan_clauses,
								  scan_relid,
1304 1305
								  best_path->parent->subplan,
								  best_path->parent->subrtable);
1306

1307 1308
	copy_path_costsize(&scan_plan->scan.plan, best_path);

1309
	return scan_plan;
1310 1311
}

1312 1313 1314 1315 1316 1317
/*
 * create_functionscan_plan
 *	 Returns a functionscan plan for the base relation scanned by 'best_path'
 *	 with restriction clauses 'scan_clauses' and targetlist 'tlist'.
 */
static FunctionScan *
1318
create_functionscan_plan(PlannerInfo *root, Path *best_path,
1319
						 List *tlist, List *scan_clauses)
1320 1321
{
	FunctionScan *scan_plan;
1322
	Index		scan_relid = best_path->parent->relid;
1323
	RangeTblEntry *rte;
1324

1325 1326
	/* it should be a function base rel... */
	Assert(scan_relid > 0);
1327
	rte = planner_rt_fetch(scan_relid, root);
1328
	Assert(rte->rtekind == RTE_FUNCTION);
1329

1330 1331 1332
	/* Sort clauses into best execution order */
	scan_clauses = order_qual_clauses(root, scan_clauses);

1333 1334 1335
	/* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
	scan_clauses = extract_actual_clauses(scan_clauses, false);

1336 1337 1338 1339 1340
	scan_plan = make_functionscan(tlist, scan_clauses, scan_relid,
								  rte->funcexpr,
								  rte->eref->colnames,
								  rte->funccoltypes,
								  rte->funccoltypmods);
1341 1342 1343 1344 1345 1346

	copy_path_costsize(&scan_plan->scan.plan, best_path);

	return scan_plan;
}

1347 1348 1349 1350 1351 1352 1353
/*
 * create_valuesscan_plan
 *	 Returns a valuesscan plan for the base relation scanned by 'best_path'
 *	 with restriction clauses 'scan_clauses' and targetlist 'tlist'.
 */
static ValuesScan *
create_valuesscan_plan(PlannerInfo *root, Path *best_path,
Bruce Momjian's avatar
Bruce Momjian committed
1354
					   List *tlist, List *scan_clauses)
1355 1356 1357
{
	ValuesScan *scan_plan;
	Index		scan_relid = best_path->parent->relid;
1358
	RangeTblEntry *rte;
1359 1360 1361

	/* it should be a values base rel... */
	Assert(scan_relid > 0);
1362
	rte = planner_rt_fetch(scan_relid, root);
1363
	Assert(rte->rtekind == RTE_VALUES);
1364 1365 1366 1367

	/* Sort clauses into best execution order */
	scan_clauses = order_qual_clauses(root, scan_clauses);

1368 1369 1370
	/* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
	scan_clauses = extract_actual_clauses(scan_clauses, false);

1371 1372
	scan_plan = make_valuesscan(tlist, scan_clauses, scan_relid,
								rte->values_lists);
1373 1374 1375 1376 1377 1378

	copy_path_costsize(&scan_plan->scan.plan, best_path);

	return scan_plan;
}

1379 1380 1381 1382 1383 1384 1385 1386 1387 1388 1389 1390 1391 1392 1393 1394 1395 1396 1397 1398 1399 1400 1401 1402 1403 1404 1405 1406 1407 1408 1409 1410 1411 1412 1413 1414 1415 1416 1417 1418 1419 1420 1421 1422 1423 1424 1425 1426 1427 1428 1429 1430 1431 1432 1433 1434 1435 1436 1437 1438 1439 1440 1441 1442 1443 1444 1445 1446 1447 1448 1449 1450 1451 1452 1453 1454 1455 1456 1457 1458 1459 1460 1461 1462 1463 1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476 1477 1478 1479 1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 1500 1501 1502 1503 1504 1505 1506 1507 1508 1509 1510 1511 1512 1513 1514 1515 1516 1517
/*
 * create_ctescan_plan
 *	 Returns a ctescan plan for the base relation scanned by 'best_path'
 *	 with restriction clauses 'scan_clauses' and targetlist 'tlist'.
 */
static CteScan *
create_ctescan_plan(PlannerInfo *root, Path *best_path,
					List *tlist, List *scan_clauses)
{
	CteScan	   *scan_plan;
	Index		scan_relid = best_path->parent->relid;
	RangeTblEntry *rte;
	SubPlan	   *ctesplan = NULL;
	int			plan_id;
	int			cte_param_id;
	PlannerInfo *cteroot;
	Index		levelsup;
	int			ndx;
	ListCell   *lc;

	Assert(scan_relid > 0);
	rte = planner_rt_fetch(scan_relid, root);
	Assert(rte->rtekind == RTE_CTE);
	Assert(!rte->self_reference);

	/*
	 * Find the referenced CTE, and locate the SubPlan previously made for it.
	 */
	levelsup = rte->ctelevelsup;
	cteroot = root;
	while (levelsup-- > 0)
	{
		cteroot = cteroot->parent_root;
		if (!cteroot)			/* shouldn't happen */
			elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename);
	}
	/*
	 * Note: cte_plan_ids can be shorter than cteList, if we are still working
	 * on planning the CTEs (ie, this is a side-reference from another CTE).
	 * So we mustn't use forboth here.
	 */
	ndx = 0;
	foreach(lc, cteroot->parse->cteList)
	{
		CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc);

		if (strcmp(cte->ctename, rte->ctename) == 0)
			break;
		ndx++;
	}
	if (lc == NULL)				/* shouldn't happen */
		elog(ERROR, "could not find CTE \"%s\"", rte->ctename);
	if (ndx >= list_length(cteroot->cte_plan_ids))
		elog(ERROR, "could not find plan for CTE \"%s\"", rte->ctename);
	plan_id = list_nth_int(cteroot->cte_plan_ids, ndx);
	Assert(plan_id > 0);
	foreach(lc, cteroot->init_plans)
	{
		ctesplan = (SubPlan *) lfirst(lc);
		if (ctesplan->plan_id == plan_id)
			break;
	}
	if (lc == NULL)				/* shouldn't happen */
		elog(ERROR, "could not find plan for CTE \"%s\"", rte->ctename);

	/*
	 * We need the CTE param ID, which is the sole member of the
	 * SubPlan's setParam list.
	 */
	cte_param_id = linitial_int(ctesplan->setParam);

	/* Sort clauses into best execution order */
	scan_clauses = order_qual_clauses(root, scan_clauses);

	/* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
	scan_clauses = extract_actual_clauses(scan_clauses, false);

	scan_plan = make_ctescan(tlist, scan_clauses, scan_relid,
							 plan_id, cte_param_id);

	copy_path_costsize(&scan_plan->scan.plan, best_path);

	return scan_plan;
}

/*
 * create_worktablescan_plan
 *	 Returns a worktablescan plan for the base relation scanned by 'best_path'
 *	 with restriction clauses 'scan_clauses' and targetlist 'tlist'.
 */
static WorkTableScan *
create_worktablescan_plan(PlannerInfo *root, Path *best_path,
						  List *tlist, List *scan_clauses)
{
	WorkTableScan *scan_plan;
	Index		scan_relid = best_path->parent->relid;
	RangeTblEntry *rte;
	Index		levelsup;
	PlannerInfo *cteroot;

	Assert(scan_relid > 0);
	rte = planner_rt_fetch(scan_relid, root);
	Assert(rte->rtekind == RTE_CTE);
	Assert(rte->self_reference);

	/*
	 * We need to find the worktable param ID, which is in the plan level
	 * that's processing the recursive UNION, which is one level *below*
	 * where the CTE comes from.
	 */
	levelsup = rte->ctelevelsup;
	if (levelsup == 0)			/* shouldn't happen */
			elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename);
	levelsup--;
	cteroot = root;
	while (levelsup-- > 0)
	{
		cteroot = cteroot->parent_root;
		if (!cteroot)			/* shouldn't happen */
			elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename);
	}
	if (cteroot->wt_param_id < 0)	/* shouldn't happen */
		elog(ERROR, "could not find param ID for CTE \"%s\"", rte->ctename);

	/* Sort clauses into best execution order */
	scan_clauses = order_qual_clauses(root, scan_clauses);

	/* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
	scan_clauses = extract_actual_clauses(scan_clauses, false);

	scan_plan = make_worktablescan(tlist, scan_clauses, scan_relid,
								   cteroot->wt_param_id);

	copy_path_costsize(&scan_plan->scan.plan, best_path);

	return scan_plan;
}


1518 1519
/*****************************************************************************
 *
1520
 *	JOIN METHODS
1521 1522 1523 1524
 *
 *****************************************************************************/

static NestLoop *
1525
create_nestloop_plan(PlannerInfo *root,
1526
					 NestPath *best_path,
1527
					 Plan *outer_plan,
1528
					 Plan *inner_plan)
1529
{
1530
	List	   *tlist = build_relation_tlist(best_path->path.parent);
1531 1532 1533
	List	   *joinrestrictclauses = best_path->joinrestrictinfo;
	List	   *joinclauses;
	List	   *otherclauses;
1534
	NestLoop   *join_plan;
1535

1536
	if (IsA(best_path->innerjoinpath, IndexPath))
1537 1538
	{
		/*
1539 1540 1541 1542
		 * An index is being used to reduce the number of tuples scanned in
		 * the inner relation.	If there are join clauses being used with the
		 * index, we may remove those join clauses from the list of clauses
		 * that have to be checked as qpquals at the join node.
1543
		 *
1544
		 * We can also remove any join clauses that are redundant with those
1545 1546 1547
		 * being used in the index scan; this check is needed because
		 * find_eclass_clauses_for_index_join() may emit different clauses
		 * than generate_join_implied_equalities() did.
1548
		 *
1549
		 * We can skip this if the index path is an ordinary indexpath and not
1550 1551
		 * a special innerjoin path, since it then wouldn't be using any join
		 * clauses.
1552
		 */
1553
		IndexPath  *innerpath = (IndexPath *) best_path->innerjoinpath;
1554

1555
		if (innerpath->isjoininner)
1556 1557 1558
			joinrestrictclauses =
				select_nonredundant_join_clauses(root,
												 joinrestrictclauses,
1559
												 innerpath->indexclauses);
1560 1561 1562 1563 1564
	}
	else if (IsA(best_path->innerjoinpath, BitmapHeapPath))
	{
		/*
		 * Same deal for bitmapped index scans.
1565
		 *
1566 1567 1568 1569 1570 1571
		 * Note: both here and above, we ignore any implicit index
		 * restrictions associated with the use of partial indexes.  This is
		 * OK because we're only trying to prove we can dispense with some
		 * join quals; failing to prove that doesn't result in an incorrect
		 * plan.  It is the right way to proceed because adding more quals to
		 * the stuff we got from the original query would just make it harder
Bruce Momjian's avatar
Bruce Momjian committed
1572 1573 1574
		 * to detect duplication.  (Also, to change this we'd have to be wary
		 * of UPDATE/DELETE/SELECT FOR UPDATE target relations; see notes
		 * above about EvalPlanQual.)
1575 1576 1577 1578 1579 1580 1581
		 */
		BitmapHeapPath *innerpath = (BitmapHeapPath *) best_path->innerjoinpath;

		if (innerpath->isjoininner)
		{
			List	   *bitmapclauses;

1582
			bitmapclauses =
1583 1584 1585
				make_restrictinfo_from_bitmapqual(innerpath->bitmapqual,
												  true,
												  false);
1586 1587 1588
			joinrestrictclauses =
				select_nonredundant_join_clauses(root,
												 joinrestrictclauses,
1589
												 bitmapclauses);
1590
		}
1591
	}
1592

1593 1594 1595
	/* Sort join qual clauses into best execution order */
	joinrestrictclauses = order_qual_clauses(root, joinrestrictclauses);

1596
	/* Get the join qual clauses (in plain expression form) */
1597
	/* Any pseudoconstant clauses are ignored here */
1598 1599
	if (IS_OUTER_JOIN(best_path->jointype))
	{
1600 1601
		extract_actual_join_clauses(joinrestrictclauses,
									&joinclauses, &otherclauses);
1602 1603 1604 1605
	}
	else
	{
		/* We can treat all clauses alike for an inner join */
1606
		joinclauses = extract_actual_clauses(joinrestrictclauses, false);
1607 1608 1609
		otherclauses = NIL;
	}

1610
	join_plan = make_nestloop(tlist,
1611 1612
							  joinclauses,
							  otherclauses,
1613 1614
							  outer_plan,
							  inner_plan,
1615
							  best_path->jointype);
1616

1617
	copy_path_costsize(&join_plan->join.plan, &best_path->path);
1618

1619
	return join_plan;
1620 1621 1622
}

static MergeJoin *
1623
create_mergejoin_plan(PlannerInfo *root,
1624
					  MergePath *best_path,
1625
					  Plan *outer_plan,
1626
					  Plan *inner_plan)
1627
{
1628
	List	   *tlist = build_relation_tlist(best_path->jpath.path.parent);
1629 1630
	List	   *joinclauses;
	List	   *otherclauses;
1631
	List	   *mergeclauses;
1632 1633 1634 1635 1636 1637
	List	   *outerpathkeys;
	List	   *innerpathkeys;
	int			nClauses;
	Oid		   *mergefamilies;
	int		   *mergestrategies;
	bool	   *mergenullsfirst;
1638
	MergeJoin  *join_plan;
1639 1640 1641
	int			i;
	EquivalenceClass *lastoeclass;
	EquivalenceClass *lastieclass;
Bruce Momjian's avatar
Bruce Momjian committed
1642 1643
	PathKey    *opathkey;
	PathKey    *ipathkey;
1644 1645 1646
	ListCell   *lc;
	ListCell   *lop;
	ListCell   *lip;
1647

1648 1649 1650 1651
	/* Sort join qual clauses into best execution order */
	/* NB: do NOT reorder the mergeclauses */
	joinclauses = order_qual_clauses(root, best_path->jpath.joinrestrictinfo);

1652
	/* Get the join qual clauses (in plain expression form) */
1653
	/* Any pseudoconstant clauses are ignored here */
1654 1655
	if (IS_OUTER_JOIN(best_path->jpath.jointype))
	{
1656
		extract_actual_join_clauses(joinclauses,
1657
									&joinclauses, &otherclauses);
1658 1659 1660 1661
	}
	else
	{
		/* We can treat all clauses alike for an inner join */
1662
		joinclauses = extract_actual_clauses(joinclauses, false);
1663 1664 1665
		otherclauses = NIL;
	}

1666
	/*
1667 1668
	 * Remove the mergeclauses from the list of join qual clauses, leaving the
	 * list of quals that must be checked as qpquals.
1669
	 */
1670
	mergeclauses = get_actual_clauses(best_path->path_mergeclauses);
1671
	joinclauses = list_difference(joinclauses, mergeclauses);
1672

1673
	/*
1674
	 * Rearrange mergeclauses, if needed, so that the outer variable is always
1675 1676
	 * on the left; mark the mergeclause restrictinfos with correct
	 * outer_is_left status.
1677
	 */
1678
	mergeclauses = get_switched_clauses(best_path->path_mergeclauses,
1679
							 best_path->jpath.outerjoinpath->parent->relids);
1680

1681
	/*
1682
	 * Create explicit sort nodes for the outer and inner join paths if
1683 1684
	 * necessary.  The sort cost was already accounted for in the path. Make
	 * sure there are no excess columns in the inputs if sorting.
1685 1686
	 */
	if (best_path->outersortkeys)
1687 1688
	{
		disuse_physical_tlist(outer_plan, best_path->jpath.outerjoinpath);
1689
		outer_plan = (Plan *)
1690
			make_sort_from_pathkeys(root,
1691
									outer_plan,
1692 1693
									best_path->outersortkeys,
									-1.0);
1694
		outerpathkeys = best_path->outersortkeys;
1695
	}
1696 1697
	else
		outerpathkeys = best_path->jpath.outerjoinpath->pathkeys;
1698 1699

	if (best_path->innersortkeys)
1700 1701
	{
		disuse_physical_tlist(inner_plan, best_path->jpath.innerjoinpath);
1702
		inner_plan = (Plan *)
1703
			make_sort_from_pathkeys(root,
1704
									inner_plan,
1705 1706
									best_path->innersortkeys,
									-1.0);
1707 1708 1709 1710 1711
		innerpathkeys = best_path->innersortkeys;
	}
	else
		innerpathkeys = best_path->jpath.innerjoinpath->pathkeys;

1712 1713 1714
	/*
	 * If inner plan is a sort that is expected to spill to disk, add a
	 * materialize node to shield it from the need to handle mark/restore.
Bruce Momjian's avatar
Bruce Momjian committed
1715 1716
	 * This will allow it to perform the last merge pass on-the-fly, while in
	 * most cases not requiring the materialize to spill to disk.
1717 1718 1719 1720 1721 1722 1723 1724 1725 1726 1727
	 *
	 * XXX really, Sort oughta do this for itself, probably, to avoid the
	 * overhead of a separate plan node.
	 */
	if (IsA(inner_plan, Sort) &&
		sort_exceeds_work_mem((Sort *) inner_plan))
	{
		Plan	   *matplan = (Plan *) make_material(inner_plan);

		/*
		 * We assume the materialize will not spill to disk, and therefore
1728 1729
		 * charge just cpu_tuple_cost per tuple.  (Keep this estimate in sync
		 * with similar ones in cost_mergejoin and create_mergejoin_path.)
1730 1731 1732 1733 1734 1735 1736
		 */
		copy_plan_costsize(matplan, inner_plan);
		matplan->total_cost += cpu_tuple_cost * matplan->plan_rows;

		inner_plan = matplan;
	}

1737 1738 1739 1740 1741 1742 1743 1744 1745 1746 1747 1748 1749 1750 1751 1752 1753 1754 1755 1756 1757
	/*
	 * Compute the opfamily/strategy/nullsfirst arrays needed by the executor.
	 * The information is in the pathkeys for the two inputs, but we need to
	 * be careful about the possibility of mergeclauses sharing a pathkey
	 * (compare find_mergeclauses_for_pathkeys()).
	 */
	nClauses = list_length(mergeclauses);
	Assert(nClauses == list_length(best_path->path_mergeclauses));
	mergefamilies = (Oid *) palloc(nClauses * sizeof(Oid));
	mergestrategies = (int *) palloc(nClauses * sizeof(int));
	mergenullsfirst = (bool *) palloc(nClauses * sizeof(bool));

	lastoeclass = NULL;
	lastieclass = NULL;
	opathkey = NULL;
	ipathkey = NULL;
	lop = list_head(outerpathkeys);
	lip = list_head(innerpathkeys);
	i = 0;
	foreach(lc, best_path->path_mergeclauses)
	{
Bruce Momjian's avatar
Bruce Momjian committed
1758
		RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1759 1760 1761 1762 1763 1764 1765 1766 1767 1768 1769 1770 1771 1772 1773 1774 1775 1776 1777 1778 1779 1780 1781 1782 1783 1784 1785 1786 1787 1788 1789 1790 1791 1792 1793 1794 1795 1796 1797 1798 1799 1800 1801 1802 1803 1804 1805 1806 1807 1808 1809
		EquivalenceClass *oeclass;
		EquivalenceClass *ieclass;

		/* fetch outer/inner eclass from mergeclause */
		Assert(IsA(rinfo, RestrictInfo));
		if (rinfo->outer_is_left)
		{
			oeclass = rinfo->left_ec;
			ieclass = rinfo->right_ec;
		}
		else
		{
			oeclass = rinfo->right_ec;
			ieclass = rinfo->left_ec;
		}
		Assert(oeclass != NULL);
		Assert(ieclass != NULL);

		/* should match current or next pathkeys */
		/* we check this carefully for debugging reasons */
		if (oeclass != lastoeclass)
		{
			if (!lop)
				elog(ERROR, "too few pathkeys for mergeclauses");
			opathkey = (PathKey *) lfirst(lop);
			lop = lnext(lop);
			lastoeclass = opathkey->pk_eclass;
			if (oeclass != lastoeclass)
				elog(ERROR, "outer pathkeys do not match mergeclause");
		}
		if (ieclass != lastieclass)
		{
			if (!lip)
				elog(ERROR, "too few pathkeys for mergeclauses");
			ipathkey = (PathKey *) lfirst(lip);
			lip = lnext(lip);
			lastieclass = ipathkey->pk_eclass;
			if (ieclass != lastieclass)
				elog(ERROR, "inner pathkeys do not match mergeclause");
		}
		/* pathkeys should match each other too (more debugging) */
		if (opathkey->pk_opfamily != ipathkey->pk_opfamily ||
			opathkey->pk_strategy != ipathkey->pk_strategy ||
			opathkey->pk_nulls_first != ipathkey->pk_nulls_first)
			elog(ERROR, "left and right pathkeys do not match in mergejoin");

		/* OK, save info for executor */
		mergefamilies[i] = opathkey->pk_opfamily;
		mergestrategies[i] = opathkey->pk_strategy;
		mergenullsfirst[i] = opathkey->pk_nulls_first;
		i++;
1810
	}
1811

1812

1813 1814 1815
	/*
	 * Now we can build the mergejoin node.
	 */
1816
	join_plan = make_mergejoin(tlist,
1817 1818
							   joinclauses,
							   otherclauses,
1819
							   mergeclauses,
1820 1821 1822
							   mergefamilies,
							   mergestrategies,
							   mergenullsfirst,
1823 1824
							   outer_plan,
							   inner_plan,
1825
							   best_path->jpath.jointype);
1826

1827
	copy_path_costsize(&join_plan->join.plan, &best_path->jpath.path);
1828

1829
	return join_plan;
1830 1831 1832
}

static HashJoin *
1833
create_hashjoin_plan(PlannerInfo *root,
1834
					 HashPath *best_path,
1835
					 Plan *outer_plan,
1836
					 Plan *inner_plan)
1837
{
1838
	List	   *tlist = build_relation_tlist(best_path->jpath.path.parent);
1839 1840
	List	   *joinclauses;
	List	   *otherclauses;
1841
	List	   *hashclauses;
1842 1843
	HashJoin   *join_plan;
	Hash	   *hash_plan;
1844

1845 1846 1847 1848
	/* Sort join qual clauses into best execution order */
	joinclauses = order_qual_clauses(root, best_path->jpath.joinrestrictinfo);
	/* There's no point in sorting the hash clauses ... */

1849
	/* Get the join qual clauses (in plain expression form) */
1850
	/* Any pseudoconstant clauses are ignored here */
1851 1852
	if (IS_OUTER_JOIN(best_path->jpath.jointype))
	{
1853
		extract_actual_join_clauses(joinclauses,
1854
									&joinclauses, &otherclauses);
1855 1856 1857 1858
	}
	else
	{
		/* We can treat all clauses alike for an inner join */
1859
		joinclauses = extract_actual_clauses(joinclauses, false);
1860 1861 1862
		otherclauses = NIL;
	}

1863
	/*
1864 1865
	 * Remove the hashclauses from the list of join qual clauses, leaving the
	 * list of quals that must be checked as qpquals.
1866
	 */
1867
	hashclauses = get_actual_clauses(best_path->path_hashclauses);
1868
	joinclauses = list_difference(joinclauses, hashclauses);
1869 1870

	/*
1871 1872
	 * Rearrange hashclauses, if needed, so that the outer variable is always
	 * on the left.
1873 1874
	 */
	hashclauses = get_switched_clauses(best_path->path_hashclauses,
1875
							 best_path->jpath.outerjoinpath->parent->relids);
1876

1877 1878 1879
	/* We don't want any excess columns in the hashed tuples */
	disuse_physical_tlist(inner_plan, best_path->jpath.innerjoinpath);

1880 1881 1882
	/*
	 * Build the hash node and hash join node.
	 */
1883
	hash_plan = make_hash(inner_plan);
1884
	join_plan = make_hashjoin(tlist,
1885 1886
							  joinclauses,
							  otherclauses,
1887
							  hashclauses,
1888 1889
							  outer_plan,
							  (Plan *) hash_plan,
1890
							  best_path->jpath.jointype);
1891

1892
	copy_path_costsize(&join_plan->join.plan, &best_path->jpath.path);
1893

1894
	return join_plan;
1895 1896 1897 1898 1899
}


/*****************************************************************************
 *
1900
 *	SUPPORTING ROUTINES
1901 1902 1903
 *
 *****************************************************************************/

1904
/*
1905
 * fix_indexqual_references
1906
 *	  Adjust indexqual clauses to the form the executor's indexqual
1907
 *	  machinery needs.
1908
 *
1909
 * We have three tasks here:
1910
 *	* Remove RestrictInfo nodes from the input clauses.
1911
 *	* Index keys must be represented by Var nodes with varattno set to the
1912 1913
 *	  index's attribute number, not the attribute number in the original rel.
 *	* If the index key is on the right, commute the clause to put it on the
1914
 *	  left.
1915
 *
1916
 * The result is a modified copy of the indexquals list --- the
1917 1918
 * original is not changed.  Note also that the copy shares no substructure
 * with the original; this is needed in case there is a subplan in it (we need
1919
 * two separate copies of the subplan tree, or things will go awry).
1920
 */
1921 1922
static List *
fix_indexqual_references(List *indexquals, IndexPath *index_path)
1923
{
1924
	IndexOptInfo *index = index_path->indexinfo;
1925
	List	   *fixed_indexquals;
1926
	ListCell   *l;
1927

1928
	fixed_indexquals = NIL;
1929 1930 1931 1932

	/*
	 * For each qual clause, commute if needed to put the indexkey operand on
	 * the left, and then fix its varattno.  (We do not need to change the
1933
	 * other side of the clause.)
1934 1935
	 */
	foreach(l, indexquals)
1936
	{
1937
		RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
1938
		Expr	   *clause;
1939

1940
		Assert(IsA(rinfo, RestrictInfo));
1941

1942 1943
		/*
		 * Make a copy that will become the fixed clause.
1944
		 *
1945 1946 1947
		 * We used to try to do a shallow copy here, but that fails if there
		 * is a subplan in the arguments of the opclause.  So just do a full
		 * copy.
1948
		 */
1949
		clause = (Expr *) copyObject((Node *) rinfo->clause);
1950

1951 1952
		if (IsA(clause, OpExpr))
		{
Bruce Momjian's avatar
Bruce Momjian committed
1953
			OpExpr	   *op = (OpExpr *) clause;
1954 1955 1956 1957 1958 1959 1960 1961 1962 1963

			if (list_length(op->args) != 2)
				elog(ERROR, "indexqual clause is not binary opclause");

			/*
			 * Check to see if the indexkey is on the right; if so, commute
			 * the clause. The indexkey should be the side that refers to
			 * (only) the base relation.
			 */
			if (!bms_equal(rinfo->left_relids, index->rel->relids))
1964
				CommuteOpExpr(op);
1965 1966

			/*
1967 1968
			 * Now, determine which index attribute this is and change the
			 * indexkey operand as needed.
1969 1970
			 */
			linitial(op->args) = fix_indexqual_operand(linitial(op->args),
1971
													   index);
1972
		}
1973 1974 1975
		else if (IsA(clause, RowCompareExpr))
		{
			RowCompareExpr *rc = (RowCompareExpr *) clause;
Bruce Momjian's avatar
Bruce Momjian committed
1976
			ListCell   *lc;
1977 1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 1991 1992 1993

			/*
			 * Check to see if the indexkey is on the right; if so, commute
			 * the clause. The indexkey should be the side that refers to
			 * (only) the base relation.
			 */
			if (!bms_overlap(pull_varnos(linitial(rc->largs)),
							 index->rel->relids))
				CommuteRowCompareExpr(rc);

			/*
			 * For each column in the row comparison, determine which index
			 * attribute this is and change the indexkey operand as needed.
			 */
			foreach(lc, rc->largs)
			{
				lfirst(lc) = fix_indexqual_operand(lfirst(lc),
1994
												   index);
1995 1996
			}
		}
1997 1998 1999 2000 2001 2002 2003
		else if (IsA(clause, ScalarArrayOpExpr))
		{
			ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause;

			/* Never need to commute... */

			/*
2004 2005
			 * Determine which index attribute this is and change the
			 * indexkey operand as needed.
2006 2007
			 */
			linitial(saop->args) = fix_indexqual_operand(linitial(saop->args),
2008
														 index);
2009
		}
2010 2011
		else if (IsA(clause, NullTest))
		{
Bruce Momjian's avatar
Bruce Momjian committed
2012
			NullTest   *nt = (NullTest *) clause;
2013 2014 2015

			Assert(nt->nulltesttype == IS_NULL);
			nt->arg = (Expr *) fix_indexqual_operand((Node *) nt->arg,
2016
													 index);
2017
		}
2018 2019 2020
		else
			elog(ERROR, "unsupported indexqual type: %d",
				 (int) nodeTag(clause));
2021

2022
		fixed_indexquals = lappend(fixed_indexquals, clause);
2023
	}
2024 2025

	return fixed_indexquals;
2026
}
2027

2028
static Node *
2029
fix_indexqual_operand(Node *node, IndexOptInfo *index)
2030
{
2031
	/*
2032 2033 2034 2035 2036
	 * We represent index keys by Var nodes having the varno of the base table
	 * but varattno equal to the index's attribute number (index column
	 * position).  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.
2037
	 */
2038 2039
	Var		   *result;
	int			pos;
2040
	ListCell   *indexpr_item;
2041 2042 2043 2044 2045 2046 2047 2048

	/*
	 * Remove any binary-compatible relabeling of the indexkey
	 */
	if (IsA(node, RelabelType))
		node = (Node *) ((RelabelType *) node)->arg;

	if (IsA(node, Var) &&
2049
		((Var *) node)->varno == index->rel->relid)
2050
	{
2051 2052
		/* Try to match against simple index columns */
		int			varatt = ((Var *) node)->varattno;
2053

2054
		if (varatt != 0)
2055
		{
2056
			for (pos = 0; pos < index->ncolumns; pos++)
2057
			{
2058
				if (index->indexkeys[pos] == varatt)
2059
				{
2060 2061 2062
					result = (Var *) copyObject(node);
					result->varattno = pos + 1;
					return (Node *) result;
2063 2064
				}
			}
2065
		}
2066 2067
	}

2068
	/* Try to match against index expressions */
2069
	indexpr_item = list_head(index->indexprs);
2070 2071 2072 2073 2074 2075
	for (pos = 0; pos < index->ncolumns; pos++)
	{
		if (index->indexkeys[pos] == 0)
		{
			Node	   *indexkey;

2076
			if (indexpr_item == NULL)
2077
				elog(ERROR, "too few entries in indexprs list");
2078
			indexkey = (Node *) lfirst(indexpr_item);
2079 2080 2081 2082 2083
			if (indexkey && IsA(indexkey, RelabelType))
				indexkey = (Node *) ((RelabelType *) indexkey)->arg;
			if (equal(node, indexkey))
			{
				/* Found a match */
2084
				result = makeVar(index->rel->relid, pos + 1,
2085
								 exprType(lfirst(indexpr_item)), -1,
2086 2087 2088
								 0);
				return (Node *) result;
			}
2089
			indexpr_item = lnext(indexpr_item);
2090 2091
		}
	}
2092

2093
	/* Ooops... */
2094
	elog(ERROR, "node is not an index attribute");
2095
	return NULL;				/* keep compiler quiet */
2096 2097
}

2098
/*
2099 2100 2101 2102
 * get_switched_clauses
 *	  Given a list of merge or hash joinclauses (as RestrictInfo nodes),
 *	  extract the bare clauses, and rearrange the elements within the
 *	  clauses, if needed, so the outer join variable is on the left and
2103 2104 2105
 *	  the inner is on the right.  The original clause data structure is not
 *	  touched; a modified list is returned.  We do, however, set the transient
 *	  outer_is_left field in each RestrictInfo to show which side was which.
2106
 */
2107
static List *
2108
get_switched_clauses(List *clauses, Relids outerrelids)
2109
{
2110
	List	   *t_list = NIL;
2111
	ListCell   *l;
2112

2113
	foreach(l, clauses)
Vadim B. Mikheev's avatar
Vadim B. Mikheev committed
2114
	{
2115
		RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
2116
		OpExpr	   *clause = (OpExpr *) restrictinfo->clause;
2117

2118
		Assert(is_opclause(clause));
2119
		if (bms_is_subset(restrictinfo->right_relids, outerrelids))
2120
		{
Bruce Momjian's avatar
Bruce Momjian committed
2121
			/*
2122 2123
			 * Duplicate just enough of the structure to allow commuting the
			 * clause without changing the original list.  Could use
2124 2125
			 * copyObject, but a complete deep copy is overkill.
			 */
2126
			OpExpr	   *temp = makeNode(OpExpr);
2127

2128 2129 2130 2131
			temp->opno = clause->opno;
			temp->opfuncid = InvalidOid;
			temp->opresulttype = clause->opresulttype;
			temp->opretset = clause->opretset;
2132
			temp->args = list_copy(clause->args);
2133
			temp->location = clause->location;
2134
			/* Commute it --- note this modifies the temp node in-place. */
2135
			CommuteOpExpr(temp);
2136
			t_list = lappend(t_list, temp);
2137
			restrictinfo->outer_is_left = false;
2138 2139
		}
		else
2140 2141
		{
			Assert(bms_is_subset(restrictinfo->left_relids, outerrelids));
2142
			t_list = lappend(t_list, clause);
2143 2144
			restrictinfo->outer_is_left = true;
		}
2145
	}
2146
	return t_list;
2147 2148
}

2149 2150 2151 2152 2153 2154 2155
/*
 * order_qual_clauses
 *		Given a list of qual clauses that will all be evaluated at the same
 *		plan node, sort the list into the order we want to check the quals
 *		in at runtime.
 *
 * Ideally the order should be driven by a combination of execution cost and
2156 2157 2158 2159 2160 2161 2162 2163 2164 2165 2166 2167 2168 2169
 * selectivity, but it's not immediately clear how to account for both,
 * and given the uncertainty of the estimates the reliability of the decisions
 * would be doubtful anyway.  So we just order by estimated per-tuple cost,
 * being careful not to change the order when (as is often the case) the
 * estimates are identical.
 *
 * Although this will work on either bare clauses or RestrictInfos, it's
 * much faster to apply it to RestrictInfos, since it can re-use cost
 * information that is cached in RestrictInfos.
 *
 * Note: some callers pass lists that contain entries that will later be
 * removed; this is the easiest way to let this routine see RestrictInfos
 * instead of bare clauses.  It's OK because we only sort by cost, but
 * a cost/selectivity combination would likely do the wrong thing.
2170
 */
2171
static List *
2172
order_qual_clauses(PlannerInfo *root, List *clauses)
2173
{
2174 2175
	typedef struct
	{
Bruce Momjian's avatar
Bruce Momjian committed
2176 2177
		Node	   *clause;
		Cost		cost;
2178
	} QualItem;
2179 2180 2181 2182 2183
	int			nitems = list_length(clauses);
	QualItem   *items;
	ListCell   *lc;
	int			i;
	List	   *result;
2184

2185 2186
	/* No need to work hard for 0 or 1 clause */
	if (nitems <= 1)
2187 2188
		return clauses;

2189 2190 2191 2192 2193 2194 2195
	/*
	 * Collect the items and costs into an array.  This is to avoid repeated
	 * cost_qual_eval work if the inputs aren't RestrictInfos.
	 */
	items = (QualItem *) palloc(nitems * sizeof(QualItem));
	i = 0;
	foreach(lc, clauses)
2196
	{
2197 2198
		Node	   *clause = (Node *) lfirst(lc);
		QualCost	qcost;
2199

2200
		cost_qual_eval_node(&qcost, clause, root);
2201 2202 2203
		items[i].clause = clause;
		items[i].cost = qcost.per_tuple;
		i++;
2204 2205
	}

2206 2207
	/*
	 * Sort.  We don't use qsort() because it's not guaranteed stable for
Bruce Momjian's avatar
Bruce Momjian committed
2208 2209
	 * equal keys.	The expected number of entries is small enough that a
	 * simple insertion sort should be good enough.
2210 2211 2212 2213 2214 2215 2216 2217 2218
	 */
	for (i = 1; i < nitems; i++)
	{
		QualItem	newitem = items[i];
		int			j;

		/* insert newitem into the already-sorted subarray */
		for (j = i; j > 0; j--)
		{
Bruce Momjian's avatar
Bruce Momjian committed
2219
			if (newitem.cost >= items[j - 1].cost)
2220
				break;
Bruce Momjian's avatar
Bruce Momjian committed
2221
			items[j] = items[j - 1];
2222 2223 2224 2225 2226 2227 2228 2229 2230 2231
		}
		items[j] = newitem;
	}

	/* Convert back to a list */
	result = NIL;
	for (i = 0; i < nitems; i++)
		result = lappend(result, items[i].clause);

	return result;
2232 2233
}

2234 2235 2236 2237 2238 2239 2240 2241 2242
/*
 * Copy cost and size info from a Path node to the Plan node created from it.
 * The executor won't use this info, but it's needed by EXPLAIN.
 */
static void
copy_path_costsize(Plan *dest, Path *src)
{
	if (src)
	{
2243 2244
		dest->startup_cost = src->startup_cost;
		dest->total_cost = src->total_cost;
2245 2246 2247 2248 2249
		dest->plan_rows = src->parent->rows;
		dest->plan_width = src->parent->width;
	}
	else
	{
2250 2251
		dest->startup_cost = 0;
		dest->total_cost = 0;
2252 2253 2254 2255 2256
		dest->plan_rows = 0;
		dest->plan_width = 0;
	}
}

2257 2258 2259 2260
/*
 * Copy cost and size info from a lower plan node to an inserted node.
 * This is not critical, since the decisions have already been made,
 * but it helps produce more reasonable-looking EXPLAIN output.
2261
 * (Some callers alter the info after copying it.)
2262
 */
2263
static void
2264
copy_plan_costsize(Plan *dest, Plan *src)
2265 2266 2267
{
	if (src)
	{
2268 2269
		dest->startup_cost = src->startup_cost;
		dest->total_cost = src->total_cost;
2270
		dest->plan_rows = src->plan_rows;
2271 2272 2273 2274
		dest->plan_width = src->plan_width;
	}
	else
	{
2275 2276
		dest->startup_cost = 0;
		dest->total_cost = 0;
2277
		dest->plan_rows = 0;
2278 2279 2280 2281 2282
		dest->plan_width = 0;
	}
}


2283 2284
/*****************************************************************************
 *
2285 2286 2287 2288
 *	PLAN NODE BUILDING ROUTINES
 *
 * Some of these are exported because they are called to build plan nodes
 * in contexts where we're not deriving the plan node from a path node.
2289 2290 2291
 *
 *****************************************************************************/

2292
static SeqScan *
2293 2294
make_seqscan(List *qptlist,
			 List *qpqual,
2295
			 Index scanrelid)
2296
{
2297 2298
	SeqScan    *node = makeNode(SeqScan);
	Plan	   *plan = &node->plan;
2299

2300
	/* cost should be inserted by caller */
2301 2302
	plan->targetlist = qptlist;
	plan->qual = qpqual;
2303
	plan->lefttree = NULL;
2304 2305 2306
	plan->righttree = NULL;
	node->scanrelid = scanrelid;

2307
	return node;
2308 2309 2310
}

static IndexScan *
2311 2312
make_indexscan(List *qptlist,
			   List *qpqual,
2313
			   Index scanrelid,
2314 2315 2316
			   Oid indexid,
			   List *indexqual,
			   List *indexqualorig,
2317
			   ScanDirection indexscandir)
2318
{
2319 2320
	IndexScan  *node = makeNode(IndexScan);
	Plan	   *plan = &node->scan.plan;
2321

2322
	/* cost should be inserted by caller */
2323 2324 2325 2326 2327
	plan->targetlist = qptlist;
	plan->qual = qpqual;
	plan->lefttree = NULL;
	plan->righttree = NULL;
	node->scan.scanrelid = scanrelid;
2328 2329 2330 2331
	node->indexid = indexid;
	node->indexqual = indexqual;
	node->indexqualorig = indexqualorig;
	node->indexorderdir = indexscandir;
2332

2333
	return node;
2334 2335
}

2336 2337
static BitmapIndexScan *
make_bitmap_indexscan(Index scanrelid,
2338 2339
					  Oid indexid,
					  List *indexqual,
2340
					  List *indexqualorig)
2341 2342 2343 2344 2345 2346 2347 2348 2349 2350
{
	BitmapIndexScan *node = makeNode(BitmapIndexScan);
	Plan	   *plan = &node->scan.plan;

	/* cost should be inserted by caller */
	plan->targetlist = NIL;		/* not used */
	plan->qual = NIL;			/* not used */
	plan->lefttree = NULL;
	plan->righttree = NULL;
	node->scan.scanrelid = scanrelid;
2351 2352 2353
	node->indexid = indexid;
	node->indexqual = indexqual;
	node->indexqualorig = indexqualorig;
2354 2355 2356 2357 2358 2359 2360 2361 2362 2363 2364 2365 2366 2367 2368 2369 2370 2371 2372 2373 2374 2375 2376 2377 2378

	return node;
}

static BitmapHeapScan *
make_bitmap_heapscan(List *qptlist,
					 List *qpqual,
					 Plan *lefttree,
					 List *bitmapqualorig,
					 Index scanrelid)
{
	BitmapHeapScan *node = makeNode(BitmapHeapScan);
	Plan	   *plan = &node->scan.plan;

	/* cost should be inserted by caller */
	plan->targetlist = qptlist;
	plan->qual = qpqual;
	plan->lefttree = lefttree;
	plan->righttree = NULL;
	node->scan.scanrelid = scanrelid;
	node->bitmapqualorig = bitmapqualorig;

	return node;
}

2379 2380 2381 2382
static TidScan *
make_tidscan(List *qptlist,
			 List *qpqual,
			 Index scanrelid,
2383
			 List *tidquals)
2384 2385 2386 2387 2388 2389 2390 2391 2392 2393
{
	TidScan    *node = makeNode(TidScan);
	Plan	   *plan = &node->scan.plan;

	/* cost should be inserted by caller */
	plan->targetlist = qptlist;
	plan->qual = qpqual;
	plan->lefttree = NULL;
	plan->righttree = NULL;
	node->scan.scanrelid = scanrelid;
2394
	node->tidquals = tidquals;
2395 2396 2397 2398

	return node;
}

2399
SubqueryScan *
2400 2401 2402
make_subqueryscan(List *qptlist,
				  List *qpqual,
				  Index scanrelid,
2403 2404
				  Plan *subplan,
				  List *subrtable)
2405 2406 2407 2408
{
	SubqueryScan *node = makeNode(SubqueryScan);
	Plan	   *plan = &node->scan.plan;

2409
	/*
2410 2411 2412
	 * Cost is figured here for the convenience of prepunion.c.  Note this is
	 * only correct for the case where qpqual is empty; otherwise caller
	 * should overwrite cost with a better estimate.
2413
	 */
2414
	copy_plan_costsize(plan, subplan);
2415 2416
	plan->total_cost += cpu_tuple_cost * subplan->plan_rows;

2417 2418 2419 2420 2421 2422
	plan->targetlist = qptlist;
	plan->qual = qpqual;
	plan->lefttree = NULL;
	plan->righttree = NULL;
	node->scan.scanrelid = scanrelid;
	node->subplan = subplan;
2423
	node->subrtable = subrtable;
2424 2425 2426 2427 2428 2429 2430

	return node;
}

static FunctionScan *
make_functionscan(List *qptlist,
				  List *qpqual,
2431 2432 2433 2434 2435
				  Index scanrelid,
				  Node *funcexpr,
				  List *funccolnames,
				  List *funccoltypes,
				  List *funccoltypmods)
2436
{
Bruce Momjian's avatar
Bruce Momjian committed
2437 2438
	FunctionScan *node = makeNode(FunctionScan);
	Plan	   *plan = &node->scan.plan;
2439 2440 2441 2442 2443 2444 2445

	/* cost should be inserted by caller */
	plan->targetlist = qptlist;
	plan->qual = qpqual;
	plan->lefttree = NULL;
	plan->righttree = NULL;
	node->scan.scanrelid = scanrelid;
2446 2447 2448 2449
	node->funcexpr = funcexpr;
	node->funccolnames = funccolnames;
	node->funccoltypes = funccoltypes;
	node->funccoltypmods = funccoltypmods;
2450 2451 2452 2453 2454 2455 2456

	return node;
}

static ValuesScan *
make_valuesscan(List *qptlist,
				List *qpqual,
2457 2458
				Index scanrelid,
				List *values_lists)
2459 2460 2461
{
	ValuesScan *node = makeNode(ValuesScan);
	Plan	   *plan = &node->scan.plan;
2462 2463 2464 2465 2466 2467 2468

	/* cost should be inserted by caller */
	plan->targetlist = qptlist;
	plan->qual = qpqual;
	plan->lefttree = NULL;
	plan->righttree = NULL;
	node->scan.scanrelid = scanrelid;
2469
	node->values_lists = values_lists;
2470 2471 2472 2473

	return node;
}

2474 2475 2476 2477 2478 2479 2480 2481 2482 2483 2484 2485 2486 2487 2488 2489 2490 2491 2492 2493 2494 2495 2496 2497 2498 2499 2500 2501 2502 2503 2504 2505 2506 2507 2508 2509 2510 2511 2512 2513 2514 2515
static CteScan *
make_ctescan(List *qptlist,
			 List *qpqual,
			 Index scanrelid,
			 int ctePlanId,
			 int cteParam)
{
	CteScan *node = makeNode(CteScan);
	Plan	   *plan = &node->scan.plan;

	/* cost should be inserted by caller */
	plan->targetlist = qptlist;
	plan->qual = qpqual;
	plan->lefttree = NULL;
	plan->righttree = NULL;
	node->scan.scanrelid = scanrelid;
	node->ctePlanId = ctePlanId;
	node->cteParam = cteParam;

	return node;
}

static WorkTableScan *
make_worktablescan(List *qptlist,
				   List *qpqual,
				   Index scanrelid,
				   int wtParam)
{
	WorkTableScan *node = makeNode(WorkTableScan);
	Plan	   *plan = &node->scan.plan;

	/* cost should be inserted by caller */
	plan->targetlist = qptlist;
	plan->qual = qpqual;
	plan->lefttree = NULL;
	plan->righttree = NULL;
	node->scan.scanrelid = scanrelid;
	node->wtParam = wtParam;

	return node;
}

2516 2517 2518 2519 2520
Append *
make_append(List *appendplans, bool isTarget, List *tlist)
{
	Append	   *node = makeNode(Append);
	Plan	   *plan = &node->plan;
2521
	double		total_size;
2522
	ListCell   *subnode;
2523

2524
	/*
2525 2526 2527
	 * Compute cost as sum of subplan costs.  We charge nothing extra for the
	 * Append itself, which perhaps is too optimistic, but since it doesn't do
	 * any selection or projection, it is a pretty cheap node.
2528
	 */
2529 2530 2531
	plan->startup_cost = 0;
	plan->total_cost = 0;
	plan->plan_rows = 0;
2532
	total_size = 0;
2533 2534 2535 2536
	foreach(subnode, appendplans)
	{
		Plan	   *subplan = (Plan *) lfirst(subnode);

Bruce Momjian's avatar
Bruce Momjian committed
2537
		if (subnode == list_head(appendplans))	/* first node? */
2538 2539 2540
			plan->startup_cost = subplan->startup_cost;
		plan->total_cost += subplan->total_cost;
		plan->plan_rows += subplan->plan_rows;
2541
		total_size += subplan->plan_width * subplan->plan_rows;
2542
	}
2543 2544 2545 2546
	if (plan->plan_rows > 0)
		plan->plan_width = rint(total_size / plan->plan_rows);
	else
		plan->plan_width = 0;
2547

2548 2549 2550 2551 2552 2553 2554 2555 2556
	plan->targetlist = tlist;
	plan->qual = NIL;
	plan->lefttree = NULL;
	plan->righttree = NULL;
	node->appendplans = appendplans;
	node->isTarget = isTarget;

	return node;
}
2557

2558 2559 2560 2561
RecursiveUnion *
make_recursive_union(List *tlist,
					 Plan *lefttree,
					 Plan *righttree,
2562 2563 2564
					 int wtParam,
					 List *distinctList,
					 long numGroups)
2565 2566 2567
{
	RecursiveUnion *node = makeNode(RecursiveUnion);
	Plan	   *plan = &node->plan;
2568
	int			numCols = list_length(distinctList);
2569 2570 2571 2572 2573 2574 2575 2576 2577

	cost_recursive_union(plan, lefttree, righttree);

	plan->targetlist = tlist;
	plan->qual = NIL;
	plan->lefttree = lefttree;
	plan->righttree = righttree;
	node->wtParam = wtParam;

2578 2579 2580 2581 2582 2583 2584 2585 2586 2587 2588 2589 2590 2591 2592 2593 2594 2595 2596 2597 2598 2599 2600 2601 2602 2603 2604 2605 2606 2607 2608
	/*
	 * convert SortGroupClause list into arrays of attr indexes and equality
	 * operators, as wanted by executor
	 */
	node->numCols = numCols;
	if (numCols > 0)
	{
		int			keyno = 0;
		AttrNumber *dupColIdx;
		Oid		   *dupOperators;
		ListCell   *slitem;

		dupColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
		dupOperators = (Oid *) palloc(sizeof(Oid) * numCols);

		foreach(slitem, distinctList)
		{
			SortGroupClause *sortcl = (SortGroupClause *) lfirst(slitem);
			TargetEntry *tle = get_sortgroupclause_tle(sortcl,
													   plan->targetlist);

			dupColIdx[keyno] = tle->resno;
			dupOperators[keyno] = sortcl->eqop;
			Assert(OidIsValid(dupOperators[keyno]));
			keyno++;
		}
		node->dupColIdx = dupColIdx;
		node->dupOperators = dupOperators;
	}
	node->numGroups = numGroups;

2609 2610 2611
	return node;
}

2612 2613 2614 2615 2616 2617
static BitmapAnd *
make_bitmap_and(List *bitmapplans)
{
	BitmapAnd  *node = makeNode(BitmapAnd);
	Plan	   *plan = &node->plan;

2618
	/* cost should be inserted by caller */
2619 2620 2621 2622 2623 2624 2625 2626 2627 2628 2629 2630 2631 2632 2633
	plan->targetlist = NIL;
	plan->qual = NIL;
	plan->lefttree = NULL;
	plan->righttree = NULL;
	node->bitmapplans = bitmapplans;

	return node;
}

static BitmapOr *
make_bitmap_or(List *bitmapplans)
{
	BitmapOr   *node = makeNode(BitmapOr);
	Plan	   *plan = &node->plan;

2634
	/* cost should be inserted by caller */
2635 2636 2637 2638 2639 2640 2641 2642 2643
	plan->targetlist = NIL;
	plan->qual = NIL;
	plan->lefttree = NULL;
	plan->righttree = NULL;
	node->bitmapplans = bitmapplans;

	return node;
}

2644
static NestLoop *
2645 2646 2647
make_nestloop(List *tlist,
			  List *joinclauses,
			  List *otherclauses,
2648
			  Plan *lefttree,
2649
			  Plan *righttree,
2650
			  JoinType jointype)
2651
{
2652
	NestLoop   *node = makeNode(NestLoop);
2653
	Plan	   *plan = &node->join.plan;
2654

2655
	/* cost should be inserted by caller */
2656 2657
	plan->targetlist = tlist;
	plan->qual = otherclauses;
2658 2659
	plan->lefttree = lefttree;
	plan->righttree = righttree;
2660 2661
	node->join.jointype = jointype;
	node->join.joinqual = joinclauses;
2662

2663
	return node;
2664 2665 2666
}

static HashJoin *
2667
make_hashjoin(List *tlist,
2668 2669
			  List *joinclauses,
			  List *otherclauses,
2670 2671
			  List *hashclauses,
			  Plan *lefttree,
2672
			  Plan *righttree,
2673
			  JoinType jointype)
2674
{
2675
	HashJoin   *node = makeNode(HashJoin);
2676
	Plan	   *plan = &node->join.plan;
2677

2678
	/* cost should be inserted by caller */
2679
	plan->targetlist = tlist;
2680
	plan->qual = otherclauses;
2681 2682 2683
	plan->lefttree = lefttree;
	plan->righttree = righttree;
	node->hashclauses = hashclauses;
2684 2685
	node->join.jointype = jointype;
	node->join.joinqual = joinclauses;
2686

2687
	return node;
2688 2689
}

2690
static Hash *
2691
make_hash(Plan *lefttree)
2692
{
2693 2694
	Hash	   *node = makeNode(Hash);
	Plan	   *plan = &node->plan;
2695

2696
	copy_plan_costsize(plan, lefttree);
2697 2698

	/*
2699 2700
	 * For plausibility, make startup & total costs equal total cost of input
	 * plan; this only affects EXPLAIN display not decisions.
2701 2702
	 */
	plan->startup_cost = plan->total_cost;
2703
	plan->targetlist = lefttree->targetlist;
2704
	plan->qual = NIL;
2705 2706 2707
	plan->lefttree = lefttree;
	plan->righttree = NULL;

2708
	return node;
2709 2710 2711
}

static MergeJoin *
2712
make_mergejoin(List *tlist,
2713 2714
			   List *joinclauses,
			   List *otherclauses,
2715
			   List *mergeclauses,
2716 2717 2718
			   Oid *mergefamilies,
			   int *mergestrategies,
			   bool *mergenullsfirst,
2719
			   Plan *lefttree,
2720
			   Plan *righttree,
2721
			   JoinType jointype)
2722
{
2723
	MergeJoin  *node = makeNode(MergeJoin);
2724
	Plan	   *plan = &node->join.plan;
2725

2726
	/* cost should be inserted by caller */
2727
	plan->targetlist = tlist;
2728
	plan->qual = otherclauses;
2729 2730 2731
	plan->lefttree = lefttree;
	plan->righttree = righttree;
	node->mergeclauses = mergeclauses;
2732 2733 2734
	node->mergeFamilies = mergefamilies;
	node->mergeStrategies = mergestrategies;
	node->mergeNullsFirst = mergenullsfirst;
2735 2736
	node->join.jointype = jointype;
	node->join.joinqual = joinclauses;
2737

2738
	return node;
2739 2740
}

2741
/*
2742 2743
 * make_sort --- basic routine to build a Sort plan node
 *
2744
 * Caller must have built the sortColIdx, sortOperators, and nullsFirst
Bruce Momjian's avatar
Bruce Momjian committed
2745
 * arrays already.	limit_tuples is as for cost_sort (in particular, pass
2746
 * -1 if no limit)
2747
 */
2748
static Sort *
2749
make_sort(PlannerInfo *root, Plan *lefttree, int numCols,
2750 2751
		  AttrNumber *sortColIdx, Oid *sortOperators, bool *nullsFirst,
		  double limit_tuples)
2752
{
2753 2754
	Sort	   *node = makeNode(Sort);
	Plan	   *plan = &node->plan;
2755
	Path		sort_path;		/* dummy for result of cost_sort */
2756

2757
	copy_plan_costsize(plan, lefttree); /* only care about copying size */
2758
	cost_sort(&sort_path, root, NIL,
2759 2760
			  lefttree->total_cost,
			  lefttree->plan_rows,
2761 2762
			  lefttree->plan_width,
			  limit_tuples);
2763 2764
	plan->startup_cost = sort_path.startup_cost;
	plan->total_cost = sort_path.total_cost;
2765
	plan->targetlist = lefttree->targetlist;
2766 2767 2768
	plan->qual = NIL;
	plan->lefttree = lefttree;
	plan->righttree = NULL;
2769 2770 2771
	node->numCols = numCols;
	node->sortColIdx = sortColIdx;
	node->sortOperators = sortOperators;
2772
	node->nullsFirst = nullsFirst;
2773

2774
	return node;
2775 2776
}

2777 2778 2779 2780 2781 2782 2783
/*
 * add_sort_column --- utility subroutine for building sort info arrays
 *
 * We need this routine because the same column might be selected more than
 * once as a sort key column; if so, the extra mentions are redundant.
 *
 * Caller is assumed to have allocated the arrays large enough for the
Bruce Momjian's avatar
Bruce Momjian committed
2784
 * max possible number of columns.	Return value is the new column count.
2785 2786
 */
static int
2787 2788 2789
add_sort_column(AttrNumber colIdx, Oid sortOp, bool nulls_first,
				int numCols, AttrNumber *sortColIdx,
				Oid *sortOperators, bool *nullsFirst)
2790 2791 2792
{
	int			i;

2793 2794
	Assert(OidIsValid(sortOp));

2795 2796
	for (i = 0; i < numCols; i++)
	{
2797
		/*
Bruce Momjian's avatar
Bruce Momjian committed
2798 2799
		 * Note: we check sortOp because it's conceivable that "ORDER BY foo
		 * USING <, foo USING <<<" is not redundant, if <<< distinguishes
2800 2801 2802 2803 2804 2805
		 * values that < considers equal.  We need not check nulls_first
		 * however because a lower-order column with the same sortop but
		 * opposite nulls direction is redundant.
		 */
		if (sortColIdx[i] == colIdx &&
			sortOperators[numCols] == sortOp)
2806 2807 2808 2809 2810 2811 2812 2813 2814
		{
			/* Already sorting by this col, so extra sort key is useless */
			return numCols;
		}
	}

	/* Add the column */
	sortColIdx[numCols] = colIdx;
	sortOperators[numCols] = sortOp;
2815
	nullsFirst[numCols] = nulls_first;
2816 2817 2818
	return numCols + 1;
}

2819 2820 2821 2822 2823 2824
/*
 * make_sort_from_pathkeys
 *	  Create sort plan to sort according to given pathkeys
 *
 *	  'lefttree' is the node which yields input tuples
 *	  'pathkeys' is the list of pathkeys by which the result is to be sorted
2825 2826
 *	  'limit_tuples' is the bound on the number of output tuples;
 *				-1 if no bound
2827
 *
2828 2829
 * We must convert the pathkey information into arrays of sort key column
 * numbers and sort operator OIDs.
2830 2831 2832 2833 2834 2835
 *
 * If the pathkeys include expressions that aren't simple Vars, we will
 * usually need to add resjunk items to the input plan's targetlist to
 * compute these expressions (since the Sort node itself won't do it).
 * If the input plan type isn't one that can do projections, this means
 * adding a Result node just to do the projection.
2836
 */
2837
Sort *
2838 2839
make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys,
						double limit_tuples)
2840
{
2841
	List	   *tlist = lefttree->targetlist;
2842
	ListCell   *i;
2843 2844 2845
	int			numsortkeys;
	AttrNumber *sortColIdx;
	Oid		   *sortOperators;
2846
	bool	   *nullsFirst;
2847

Bruce Momjian's avatar
Bruce Momjian committed
2848
	/*
2849
	 * We will need at most list_length(pathkeys) sort columns; possibly less
Bruce Momjian's avatar
Bruce Momjian committed
2850
	 */
2851
	numsortkeys = list_length(pathkeys);
2852 2853
	sortColIdx = (AttrNumber *) palloc(numsortkeys * sizeof(AttrNumber));
	sortOperators = (Oid *) palloc(numsortkeys * sizeof(Oid));
2854
	nullsFirst = (bool *) palloc(numsortkeys * sizeof(bool));
2855 2856

	numsortkeys = 0;
2857 2858 2859

	foreach(i, pathkeys)
	{
Bruce Momjian's avatar
Bruce Momjian committed
2860
		PathKey    *pathkey = (PathKey *) lfirst(i);
2861
		EquivalenceClass *ec = pathkey->pk_eclass;
2862
		TargetEntry *tle = NULL;
2863 2864
		Oid			pk_datatype = InvalidOid;
		Oid			sortop;
2865
		ListCell   *j;
2866

2867
		if (ec->ec_has_volatile)
2868
		{
2869
			/*
2870 2871 2872
			 * If the pathkey's EquivalenceClass is volatile, then it must
			 * have come from an ORDER BY clause, and we have to match it to
			 * that same targetlist entry.
2873
			 */
Bruce Momjian's avatar
Bruce Momjian committed
2874
			if (ec->ec_sortref == 0)	/* can't happen */
2875 2876 2877 2878 2879
				elog(ERROR, "volatile EquivalenceClass has no sortref");
			tle = get_sortgroupref_tle(ec->ec_sortref, tlist);
			Assert(tle);
			Assert(list_length(ec->ec_members) == 1);
			pk_datatype = ((EquivalenceMember *) linitial(ec->ec_members))->em_datatype;
2880
		}
2881
		else
2882
		{
2883 2884 2885
			/*
			 * Otherwise, we can sort by any non-constant expression listed in
			 * the pathkey's EquivalenceClass.  For now, we take the first one
Bruce Momjian's avatar
Bruce Momjian committed
2886
			 * that corresponds to an available item in the tlist.	If there
2887 2888 2889 2890 2891 2892 2893 2894 2895 2896 2897 2898 2899
			 * isn't any, use the first one that is an expression in the
			 * input's vars.  (The non-const restriction only matters if the
			 * EC is below_outer_join; but if it isn't, it won't contain
			 * consts anyway, else we'd have discarded the pathkey as
			 * redundant.)
			 *
			 * XXX if we have a choice, is there any way of figuring out which
			 * might be cheapest to execute?  (For example, int4lt is likely
			 * much cheaper to execute than numericlt, but both might appear
			 * in the same equivalence class...)  Not clear that we ever will
			 * have an interesting choice in practice, so it may not matter.
			 */
			foreach(j, ec->ec_members)
2900
			{
2901
				EquivalenceMember *em = (EquivalenceMember *) lfirst(j);
2902

2903 2904
				if (em->em_is_const || em->em_is_child)
					continue;
2905 2906 2907

				tle = tlist_member((Node *) em->em_expr, tlist);
				if (tle)
2908
				{
2909
					pk_datatype = em->em_datatype;
Bruce Momjian's avatar
Bruce Momjian committed
2910
					break;		/* found expr already in tlist */
2911
				}
2912 2913 2914 2915 2916

				/*
				 * We can also use it if the pathkey expression is a relabel
				 * of the tlist entry, or vice versa.  This is needed for
				 * binary-compatible cases (cf. make_pathkey_from_sortinfo).
Bruce Momjian's avatar
Bruce Momjian committed
2917 2918
				 * We prefer an exact match, though, so we do the basic search
				 * first.
2919 2920 2921
				 */
				tle = tlist_member_ignore_relabel((Node *) em->em_expr, tlist);
				if (tle)
2922 2923
				{
					pk_datatype = em->em_datatype;
Bruce Momjian's avatar
Bruce Momjian committed
2924
					break;		/* found expr already in tlist */
2925
				}
2926
			}
Bruce Momjian's avatar
Bruce Momjian committed
2927

2928
			if (!tle)
2929
			{
2930
				/* No matching tlist item; look for a computable expression */
Bruce Momjian's avatar
Bruce Momjian committed
2931
				Expr	   *sortexpr = NULL;
Bruce Momjian's avatar
Bruce Momjian committed
2932

2933 2934 2935 2936 2937 2938 2939 2940 2941
				foreach(j, ec->ec_members)
				{
					EquivalenceMember *em = (EquivalenceMember *) lfirst(j);
					List	   *exprvars;
					ListCell   *k;

					if (em->em_is_const || em->em_is_child)
						continue;
					sortexpr = em->em_expr;
2942
					exprvars = pull_var_clause((Node *) sortexpr, true);
2943 2944 2945 2946 2947 2948 2949 2950 2951
					foreach(k, exprvars)
					{
						if (!tlist_member_ignore_relabel(lfirst(k), tlist))
							break;
					}
					list_free(exprvars);
					if (!k)
					{
						pk_datatype = em->em_datatype;
Bruce Momjian's avatar
Bruce Momjian committed
2952
						break;	/* found usable expression */
2953 2954 2955 2956 2957 2958 2959 2960 2961 2962 2963 2964 2965 2966 2967 2968 2969 2970 2971 2972 2973 2974 2975 2976 2977 2978
					}
				}
				if (!j)
					elog(ERROR, "could not find pathkey item to sort");

				/*
				 * Do we need to insert a Result node?
				 */
				if (!is_projection_capable_plan(lefttree))
				{
					/* copy needed so we don't modify input's tlist below */
					tlist = copyObject(tlist);
					lefttree = (Plan *) make_result(root, tlist, NULL,
													lefttree);
				}

				/*
				 * Add resjunk entry to input's tlist
				 */
				tle = makeTargetEntry(sortexpr,
									  list_length(tlist) + 1,
									  NULL,
									  true);
				tlist = lappend(tlist, tle);
				lefttree->targetlist = tlist;	/* just in case NIL before */
			}
2979
		}
Bruce Momjian's avatar
Bruce Momjian committed
2980

2981 2982 2983 2984 2985 2986 2987 2988 2989 2990 2991 2992 2993
		/*
		 * Look up the correct sort operator from the PathKey's slightly
		 * abstracted representation.
		 */
		sortop = get_opfamily_member(pathkey->pk_opfamily,
									 pk_datatype,
									 pk_datatype,
									 pathkey->pk_strategy);
		if (!OidIsValid(sortop))	/* should not happen */
			elog(ERROR, "could not find member %d(%u,%u) of opfamily %u",
				 pathkey->pk_strategy, pk_datatype, pk_datatype,
				 pathkey->pk_opfamily);

2994
		/*
2995 2996 2997 2998
		 * The column might already be selected as a sort key, if the pathkeys
		 * contain duplicate entries.  (This can happen in scenarios where
		 * multiple mergejoinable clauses mention the same var, for example.)
		 * So enter it only once in the sort arrays.
2999
		 */
3000 3001 3002
		numsortkeys = add_sort_column(tle->resno,
									  sortop,
									  pathkey->pk_nulls_first,
3003 3004
									  numsortkeys,
									  sortColIdx, sortOperators, nullsFirst);
3005 3006 3007 3008
	}

	Assert(numsortkeys > 0);

3009
	return make_sort(root, lefttree, numsortkeys,
3010
					 sortColIdx, sortOperators, nullsFirst, limit_tuples);
3011 3012
}

3013 3014 3015 3016
/*
 * make_sort_from_sortclauses
 *	  Create sort plan to sort according to given sortclauses
 *
3017
 *	  'sortcls' is a list of SortGroupClauses
3018
 *	  'lefttree' is the node which yields input tuples
3019 3020
 */
Sort *
3021
make_sort_from_sortclauses(PlannerInfo *root, List *sortcls, Plan *lefttree)
3022
{
3023
	List	   *sub_tlist = lefttree->targetlist;
3024
	ListCell   *l;
3025 3026 3027
	int			numsortkeys;
	AttrNumber *sortColIdx;
	Oid		   *sortOperators;
3028
	bool	   *nullsFirst;
3029

Bruce Momjian's avatar
Bruce Momjian committed
3030
	/*
3031
	 * We will need at most list_length(sortcls) sort columns; possibly less
Bruce Momjian's avatar
Bruce Momjian committed
3032
	 */
3033
	numsortkeys = list_length(sortcls);
3034 3035
	sortColIdx = (AttrNumber *) palloc(numsortkeys * sizeof(AttrNumber));
	sortOperators = (Oid *) palloc(numsortkeys * sizeof(Oid));
3036
	nullsFirst = (bool *) palloc(numsortkeys * sizeof(bool));
3037 3038

	numsortkeys = 0;
3039

3040
	foreach(l, sortcls)
3041
	{
3042
		SortGroupClause *sortcl = (SortGroupClause *) lfirst(l);
3043
		TargetEntry *tle = get_sortgroupclause_tle(sortcl, sub_tlist);
3044 3045 3046

		/*
		 * Check for the possibility of duplicate order-by clauses --- the
Bruce Momjian's avatar
Bruce Momjian committed
3047 3048
		 * parser should have removed 'em, but no point in sorting
		 * redundantly.
3049
		 */
3050
		numsortkeys = add_sort_column(tle->resno, sortcl->sortop,
3051 3052 3053
									  sortcl->nulls_first,
									  numsortkeys,
									  sortColIdx, sortOperators, nullsFirst);
3054 3055 3056 3057
	}

	Assert(numsortkeys > 0);

3058
	return make_sort(root, lefttree, numsortkeys,
3059
					 sortColIdx, sortOperators, nullsFirst, -1.0);
3060 3061 3062 3063 3064 3065
}

/*
 * make_sort_from_groupcols
 *	  Create sort plan to sort based on grouping columns
 *
3066
 * 'groupcls' is the list of SortGroupClauses
3067 3068 3069 3070 3071
 * 'grpColIdx' gives the column numbers to use
 *
 * This might look like it could be merged with make_sort_from_sortclauses,
 * but presently we *must* use the grpColIdx[] array to locate sort columns,
 * because the child plan's tlist is not marked with ressortgroupref info
3072
 * appropriate to the grouping node.  So, only the sort ordering info
3073
 * is used from the SortGroupClause entries.
3074 3075
 */
Sort *
3076
make_sort_from_groupcols(PlannerInfo *root,
3077 3078 3079 3080 3081 3082
						 List *groupcls,
						 AttrNumber *grpColIdx,
						 Plan *lefttree)
{
	List	   *sub_tlist = lefttree->targetlist;
	int			grpno = 0;
3083
	ListCell   *l;
3084 3085 3086
	int			numsortkeys;
	AttrNumber *sortColIdx;
	Oid		   *sortOperators;
3087
	bool	   *nullsFirst;
3088

Bruce Momjian's avatar
Bruce Momjian committed
3089
	/*
3090
	 * We will need at most list_length(groupcls) sort columns; possibly less
Bruce Momjian's avatar
Bruce Momjian committed
3091
	 */
3092
	numsortkeys = list_length(groupcls);
3093 3094
	sortColIdx = (AttrNumber *) palloc(numsortkeys * sizeof(AttrNumber));
	sortOperators = (Oid *) palloc(numsortkeys * sizeof(Oid));
3095
	nullsFirst = (bool *) palloc(numsortkeys * sizeof(bool));
3096 3097 3098

	numsortkeys = 0;

3099
	foreach(l, groupcls)
3100
	{
3101
		SortGroupClause *grpcl = (SortGroupClause *) lfirst(l);
3102
		TargetEntry *tle = get_tle_by_resno(sub_tlist, grpColIdx[grpno]);
3103 3104 3105

		/*
		 * Check for the possibility of duplicate group-by clauses --- the
Bruce Momjian's avatar
Bruce Momjian committed
3106 3107
		 * parser should have removed 'em, but no point in sorting
		 * redundantly.
3108
		 */
3109
		numsortkeys = add_sort_column(tle->resno, grpcl->sortop,
3110 3111 3112
									  grpcl->nulls_first,
									  numsortkeys,
									  sortColIdx, sortOperators, nullsFirst);
3113
		grpno++;
3114 3115
	}

3116 3117
	Assert(numsortkeys > 0);

3118
	return make_sort(root, lefttree, numsortkeys,
3119
					 sortColIdx, sortOperators, nullsFirst, -1.0);
3120 3121
}

3122
static Material *
3123
make_material(Plan *lefttree)
3124
{
3125 3126
	Material   *node = makeNode(Material);
	Plan	   *plan = &node->plan;
3127

3128
	/* cost should be inserted by caller */
3129
	plan->targetlist = lefttree->targetlist;
3130 3131 3132 3133
	plan->qual = NIL;
	plan->lefttree = lefttree;
	plan->righttree = NULL;

3134
	return node;
3135 3136
}

3137 3138 3139 3140
/*
 * materialize_finished_plan: stick a Material node atop a completed plan
 *
 * There are a couple of places where we want to attach a Material node
Bruce Momjian's avatar
Bruce Momjian committed
3141
 * after completion of subquery_planner().	This currently requires hackery.
3142 3143 3144 3145 3146 3147 3148 3149 3150 3151 3152
 * Since subquery_planner has already run SS_finalize_plan on the subplan
 * tree, we have to kluge up parameter lists for the Material node.
 * Possibly this could be fixed by postponing SS_finalize_plan processing
 * until setrefs.c is run?
 */
Plan *
materialize_finished_plan(Plan *subplan)
{
	Plan	   *matplan;
	Path		matpath;		/* dummy for result of cost_material */

3153
	matplan = (Plan *) make_material(subplan);
3154 3155 3156 3157 3158 3159 3160 3161 3162 3163 3164 3165 3166 3167 3168 3169 3170 3171

	/* Set cost data */
	cost_material(&matpath,
				  subplan->total_cost,
				  subplan->plan_rows,
				  subplan->plan_width);
	matplan->startup_cost = matpath.startup_cost;
	matplan->total_cost = matpath.total_cost;
	matplan->plan_rows = subplan->plan_rows;
	matplan->plan_width = subplan->plan_width;

	/* parameter kluge --- see comments above */
	matplan->extParam = bms_copy(subplan->extParam);
	matplan->allParam = bms_copy(subplan->allParam);

	return matplan;
}

3172
Agg *
3173
make_agg(PlannerInfo *root, List *tlist, List *qual,
3174
		 AggStrategy aggstrategy,
3175
		 int numGroupCols, AttrNumber *grpColIdx, Oid *grpOperators,
3176
		 long numGroups, int numAggs,
3177
		 Plan *lefttree)
3178
{
3179
	Agg		   *node = makeNode(Agg);
3180
	Plan	   *plan = &node->plan;
3181
	Path		agg_path;		/* dummy for result of cost_agg */
3182
	QualCost	qual_cost;
3183

3184
	node->aggstrategy = aggstrategy;
3185
	node->numCols = numGroupCols;
3186
	node->grpColIdx = grpColIdx;
3187
	node->grpOperators = grpOperators;
3188
	node->numGroups = numGroups;
3189

3190 3191 3192 3193 3194 3195 3196 3197 3198
	copy_plan_costsize(plan, lefttree); /* only care about copying size */
	cost_agg(&agg_path, root,
			 aggstrategy, numAggs,
			 numGroupCols, numGroups,
			 lefttree->startup_cost,
			 lefttree->total_cost,
			 lefttree->plan_rows);
	plan->startup_cost = agg_path.startup_cost;
	plan->total_cost = agg_path.total_cost;
3199

3200
	/*
3201 3202
	 * We will produce a single output tuple if not grouping, and a tuple per
	 * group otherwise.
3203
	 */
3204 3205
	if (aggstrategy == AGG_PLAIN)
		plan->plan_rows = 1;
3206
	else
3207
		plan->plan_rows = numGroups;
3208

3209
	/*
3210 3211 3212 3213
	 * We also need to account for the cost of evaluation of the qual (ie, the
	 * HAVING clause) and the tlist.  Note that cost_qual_eval doesn't charge
	 * anything for Aggref nodes; this is okay since they are really
	 * comparable to Vars.
3214
	 *
3215 3216
	 * See notes in grouping_planner about why this routine and make_group are
	 * the only ones in this file that worry about tlist eval cost.
3217 3218 3219
	 */
	if (qual)
	{
3220
		cost_qual_eval(&qual_cost, qual, root);
3221 3222 3223 3224
		plan->startup_cost += qual_cost.startup;
		plan->total_cost += qual_cost.startup;
		plan->total_cost += qual_cost.per_tuple * plan->plan_rows;
	}
3225
	cost_qual_eval(&qual_cost, tlist, root);
3226 3227 3228 3229
	plan->startup_cost += qual_cost.startup;
	plan->total_cost += qual_cost.startup;
	plan->total_cost += qual_cost.per_tuple * plan->plan_rows;

3230 3231 3232
	plan->qual = qual;
	plan->targetlist = tlist;
	plan->lefttree = lefttree;
3233
	plan->righttree = NULL;
3234

3235
	return node;
3236 3237
}

3238
Group *
3239
make_group(PlannerInfo *root,
3240
		   List *tlist,
3241
		   List *qual,
3242
		   int numGroupCols,
Bruce Momjian's avatar
Bruce Momjian committed
3243
		   AttrNumber *grpColIdx,
3244
		   Oid *grpOperators,
3245
		   double numGroups,
3246
		   Plan *lefttree)
3247
{
3248
	Group	   *node = makeNode(Group);
3249
	Plan	   *plan = &node->plan;
3250
	Path		group_path;		/* dummy for result of cost_group */
3251
	QualCost	qual_cost;
3252

3253 3254
	node->numCols = numGroupCols;
	node->grpColIdx = grpColIdx;
3255
	node->grpOperators = grpOperators;
3256

3257 3258 3259 3260 3261 3262 3263 3264
	copy_plan_costsize(plan, lefttree); /* only care about copying size */
	cost_group(&group_path, root,
			   numGroupCols, numGroups,
			   lefttree->startup_cost,
			   lefttree->total_cost,
			   lefttree->plan_rows);
	plan->startup_cost = group_path.startup_cost;
	plan->total_cost = group_path.total_cost;
3265

3266 3267
	/* One output tuple per estimated result group */
	plan->plan_rows = numGroups;
3268

3269
	/*
3270 3271
	 * We also need to account for the cost of evaluation of the qual (ie, the
	 * HAVING clause) and the tlist.
3272
	 *
3273 3274 3275 3276
	 * XXX this double-counts the cost of evaluation of any expressions used
	 * for grouping, since in reality those will have been evaluated at a
	 * lower plan level and will only be copied by the Group node. Worth
	 * fixing?
3277
	 *
3278 3279
	 * See notes in grouping_planner about why this routine and make_agg are
	 * the only ones in this file that worry about tlist eval cost.
3280
	 */
3281 3282
	if (qual)
	{
3283
		cost_qual_eval(&qual_cost, qual, root);
3284 3285 3286 3287
		plan->startup_cost += qual_cost.startup;
		plan->total_cost += qual_cost.startup;
		plan->total_cost += qual_cost.per_tuple * plan->plan_rows;
	}
3288
	cost_qual_eval(&qual_cost, tlist, root);
3289 3290 3291 3292
	plan->startup_cost += qual_cost.startup;
	plan->total_cost += qual_cost.startup;
	plan->total_cost += qual_cost.per_tuple * plan->plan_rows;

3293
	plan->qual = qual;
3294 3295
	plan->targetlist = tlist;
	plan->lefttree = lefttree;
3296
	plan->righttree = NULL;
3297

3298
	return node;
3299 3300 3301
}

/*
3302
 * distinctList is a list of SortGroupClauses, identifying the targetlist items
Bruce Momjian's avatar
Bruce Momjian committed
3303
 * that should be considered by the Unique filter.	The input path must
3304
 * already be sorted accordingly.
3305
 */
3306
Unique *
3307
make_unique(Plan *lefttree, List *distinctList)
3308
{
3309 3310
	Unique	   *node = makeNode(Unique);
	Plan	   *plan = &node->plan;
3311
	int			numCols = list_length(distinctList);
3312 3313
	int			keyno = 0;
	AttrNumber *uniqColIdx;
3314
	Oid		   *uniqOperators;
3315
	ListCell   *slitem;
3316

3317
	copy_plan_costsize(plan, lefttree);
3318

3319
	/*
3320 3321 3322
	 * Charge one cpu_operator_cost per comparison per input tuple. We assume
	 * all columns get compared at most of the tuples.	(XXX probably this is
	 * an overestimate.)
3323 3324
	 */
	plan->total_cost += cpu_operator_cost * plan->plan_rows * numCols;
3325

3326
	/*
3327 3328 3329
	 * plan->plan_rows is left as a copy of the input subplan's plan_rows; ie,
	 * we assume the filter removes nothing.  The caller must alter this if he
	 * has a better idea.
3330
	 */
3331

3332
	plan->targetlist = lefttree->targetlist;
3333 3334 3335
	plan->qual = NIL;
	plan->lefttree = lefttree;
	plan->righttree = NULL;
3336

3337
	/*
3338
	 * convert SortGroupClause list into arrays of attr indexes and equality
3339
	 * operators, as wanted by executor
3340
	 */
3341 3342
	Assert(numCols > 0);
	uniqColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
3343
	uniqOperators = (Oid *) palloc(sizeof(Oid) * numCols);
3344 3345 3346

	foreach(slitem, distinctList)
	{
3347
		SortGroupClause *sortcl = (SortGroupClause *) lfirst(slitem);
3348
		TargetEntry *tle = get_sortgroupclause_tle(sortcl, plan->targetlist);
3349

3350
		uniqColIdx[keyno] = tle->resno;
3351 3352
		uniqOperators[keyno] = sortcl->eqop;
		Assert(OidIsValid(uniqOperators[keyno]));
3353
		keyno++;
3354 3355 3356 3357
	}

	node->numCols = numCols;
	node->uniqColIdx = uniqColIdx;
3358
	node->uniqOperators = uniqOperators;
3359

3360
	return node;
3361 3362
}

3363
/*
3364 3365
 * distinctList is a list of SortGroupClauses, identifying the targetlist
 * items that should be considered by the SetOp filter.  The input path must
3366
 * already be sorted accordingly.
3367 3368
 */
SetOp *
3369
make_setop(SetOpCmd cmd, SetOpStrategy strategy, Plan *lefttree,
3370 3371
		   List *distinctList, AttrNumber flagColIdx, int firstFlag,
		   long numGroups, double outputRows)
3372 3373 3374
{
	SetOp	   *node = makeNode(SetOp);
	Plan	   *plan = &node->plan;
3375
	int			numCols = list_length(distinctList);
3376 3377
	int			keyno = 0;
	AttrNumber *dupColIdx;
3378
	Oid		   *dupOperators;
3379
	ListCell   *slitem;
3380 3381

	copy_plan_costsize(plan, lefttree);
3382
	plan->plan_rows = outputRows;
3383 3384

	/*
3385 3386
	 * Charge one cpu_operator_cost per comparison per input tuple. We assume
	 * all columns get compared at most of the tuples.
3387
	 */
3388
	plan->total_cost += cpu_operator_cost * lefttree->plan_rows * numCols;
3389

3390
	plan->targetlist = lefttree->targetlist;
3391 3392 3393 3394 3395
	plan->qual = NIL;
	plan->lefttree = lefttree;
	plan->righttree = NULL;

	/*
3396
	 * convert SortGroupClause list into arrays of attr indexes and equality
3397
	 * operators, as wanted by executor
3398 3399 3400
	 */
	Assert(numCols > 0);
	dupColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
3401
	dupOperators = (Oid *) palloc(sizeof(Oid) * numCols);
3402 3403 3404

	foreach(slitem, distinctList)
	{
3405
		SortGroupClause *sortcl = (SortGroupClause *) lfirst(slitem);
3406
		TargetEntry *tle = get_sortgroupclause_tle(sortcl, plan->targetlist);
3407

3408
		dupColIdx[keyno] = tle->resno;
3409 3410
		dupOperators[keyno] = sortcl->eqop;
		Assert(OidIsValid(dupOperators[keyno]));
3411
		keyno++;
3412 3413 3414
	}

	node->cmd = cmd;
3415
	node->strategy = strategy;
3416 3417
	node->numCols = numCols;
	node->dupColIdx = dupColIdx;
3418
	node->dupOperators = dupOperators;
3419
	node->flagColIdx = flagColIdx;
3420
	node->firstFlag = firstFlag;
3421
	node->numGroups = numGroups;
3422 3423 3424 3425

	return node;
}

3426 3427 3428 3429 3430 3431 3432
/*
 * Note: offset_est and count_est are passed in to save having to repeat
 * work already done to estimate the values of the limitOffset and limitCount
 * expressions.  Their values are as returned by preprocess_limit (0 means
 * "not relevant", -1 means "couldn't estimate").  Keep the code below in sync
 * with that function!
 */
3433
Limit *
3434
make_limit(Plan *lefttree, Node *limitOffset, Node *limitCount,
3435
		   int64 offset_est, int64 count_est)
3436 3437 3438 3439 3440 3441
{
	Limit	   *node = makeNode(Limit);
	Plan	   *plan = &node->plan;

	copy_plan_costsize(plan, lefttree);

3442
	/*
3443 3444 3445 3446 3447
	 * Adjust the output rows count and costs according to the offset/limit.
	 * This is only a cosmetic issue if we are at top level, but if we are
	 * building a subquery then it's important to report correct info to the
	 * outer planner.
	 *
3448 3449
	 * When the offset or count couldn't be estimated, use 10% of the
	 * estimated number of rows emitted from the subplan.
3450
	 */
3451
	if (offset_est != 0)
3452
	{
3453
		double		offset_rows;
3454

3455 3456 3457 3458 3459 3460 3461 3462 3463 3464 3465 3466 3467
		if (offset_est > 0)
			offset_rows = (double) offset_est;
		else
			offset_rows = clamp_row_est(lefttree->plan_rows * 0.10);
		if (offset_rows > plan->plan_rows)
			offset_rows = plan->plan_rows;
		if (plan->plan_rows > 0)
			plan->startup_cost +=
				(plan->total_cost - plan->startup_cost)
				* offset_rows / plan->plan_rows;
		plan->plan_rows -= offset_rows;
		if (plan->plan_rows < 1)
			plan->plan_rows = 1;
3468
	}
3469 3470

	if (count_est != 0)
3471
	{
3472
		double		count_rows;
3473

3474 3475 3476 3477 3478 3479 3480 3481 3482 3483 3484 3485 3486
		if (count_est > 0)
			count_rows = (double) count_est;
		else
			count_rows = clamp_row_est(lefttree->plan_rows * 0.10);
		if (count_rows > plan->plan_rows)
			count_rows = plan->plan_rows;
		if (plan->plan_rows > 0)
			plan->total_cost = plan->startup_cost +
				(plan->total_cost - plan->startup_cost)
				* count_rows / plan->plan_rows;
		plan->plan_rows = count_rows;
		if (plan->plan_rows < 1)
			plan->plan_rows = 1;
3487 3488
	}

3489
	plan->targetlist = lefttree->targetlist;
3490 3491 3492 3493 3494 3495 3496 3497 3498 3499
	plan->qual = NIL;
	plan->lefttree = lefttree;
	plan->righttree = NULL;

	node->limitOffset = limitOffset;
	node->limitCount = limitCount;

	return node;
}

3500 3501 3502 3503 3504 3505 3506 3507 3508
/*
 * make_result
 *	  Build a Result plan node
 *
 * If we have a subplan, assume that any evaluation costs for the gating qual
 * were already factored into the subplan's startup cost, and just copy the
 * subplan cost.  If there's no subplan, we should include the qual eval
 * cost.  In either case, tlist eval cost is not to be included here.
 */
3509
Result *
3510 3511
make_result(PlannerInfo *root,
			List *tlist,
3512 3513 3514 3515 3516 3517
			Node *resconstantqual,
			Plan *subplan)
{
	Result	   *node = makeNode(Result);
	Plan	   *plan = &node->plan;

3518 3519 3520 3521 3522 3523 3524
	if (subplan)
		copy_plan_costsize(plan, subplan);
	else
	{
		plan->startup_cost = 0;
		plan->total_cost = cpu_tuple_cost;
		plan->plan_rows = 1;	/* wrong if we have a set-valued function? */
3525 3526 3527 3528
		plan->plan_width = 0;	/* XXX is it worth being smarter? */
		if (resconstantqual)
		{
			QualCost	qual_cost;
3529

3530
			cost_qual_eval(&qual_cost, (List *) resconstantqual, root);
3531 3532 3533 3534
			/* resconstantqual is evaluated once at startup */
			plan->startup_cost += qual_cost.startup + qual_cost.per_tuple;
			plan->total_cost += qual_cost.startup + qual_cost.per_tuple;
		}
3535 3536
	}

3537 3538 3539 3540 3541 3542 3543 3544
	plan->targetlist = tlist;
	plan->qual = NIL;
	plan->lefttree = subplan;
	plan->righttree = NULL;
	node->resconstantqual = resconstantqual;

	return node;
}
3545 3546 3547 3548 3549 3550 3551 3552 3553 3554 3555 3556 3557 3558 3559 3560 3561 3562

/*
 * is_projection_capable_plan
 *		Check whether a given Plan node is able to do projection.
 */
bool
is_projection_capable_plan(Plan *plan)
{
	/* Most plan types can project, so just list the ones that can't */
	switch (nodeTag(plan))
	{
		case T_Hash:
		case T_Material:
		case T_Sort:
		case T_Unique:
		case T_SetOp:
		case T_Limit:
		case T_Append:
3563
		case T_RecursiveUnion:
3564 3565 3566 3567 3568 3569
			return false;
		default:
			break;
	}
	return true;
}