relnode.c 16.8 KB
Newer Older
1 2
/*-------------------------------------------------------------------------
 *
3
 * relnode.c
4
 *	  Relation-node lookup/construction routines
5
 *
6
 * Portions Copyright (c) 1996-2006, PostgreSQL Global Development Group
Bruce Momjian's avatar
Add:  
Bruce Momjian committed
7
 * Portions Copyright (c) 1994, Regents of the University of California
8 9 10
 *
 *
 * IDENTIFICATION
11
 *	  $PostgreSQL: pgsql/src/backend/optimizer/util/relnode.c,v 1.82 2006/09/19 22:49:53 tgl Exp $
12 13 14 15 16
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

17
#include "optimizer/cost.h"
Bruce Momjian's avatar
Bruce Momjian committed
18
#include "optimizer/pathnode.h"
19
#include "optimizer/plancat.h"
20
#include "optimizer/restrictinfo.h"
21
#include "parser/parsetree.h"
22
#include "utils/hsearch.h"
23 24


25 26 27 28 29 30
typedef struct JoinHashEntry
{
	Relids		join_relids;	/* hash key --- MUST BE FIRST */
	RelOptInfo *join_rel;
} JoinHashEntry;

31
static void build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel,
32
					RelOptInfo *input_rel);
33
static List *build_joinrel_restrictlist(PlannerInfo *root,
34 35
						   RelOptInfo *joinrel,
						   RelOptInfo *outer_rel,
36 37
						   RelOptInfo *inner_rel,
						   JoinType jointype);
38
static void build_joinrel_joinlist(RelOptInfo *joinrel,
39 40
					   RelOptInfo *outer_rel,
					   RelOptInfo *inner_rel);
41
static List *subbuild_joinrel_restrictlist(RelOptInfo *joinrel,
42
							  List *joininfo_list);
43
static void subbuild_joinrel_joinlist(RelOptInfo *joinrel,
44
						  List *joininfo_list);
45

46

47
/*
48 49
 * build_simple_rel
 *	  Construct a new RelOptInfo for a base relation or 'other' relation.
50 51
 */
RelOptInfo *
52
build_simple_rel(PlannerInfo *root, int relid, RelOptKind reloptkind)
53 54
{
	RelOptInfo *rel;
55
	RangeTblEntry *rte;
56

57 58 59
	/* Fetch RTE for relation */
	Assert(relid > 0 && relid <= list_length(root->parse->rtable));
	rte = rt_fetch(relid, root->parse->rtable);
60

61 62 63 64
	/* Rel should not exist already */
	Assert(relid < root->simple_rel_array_size);
	if (root->simple_rel_array[relid] != NULL)
		elog(ERROR, "rel %d already exists", relid);
65

66
	rel = makeNode(RelOptInfo);
67
	rel->reloptkind = reloptkind;
68
	rel->relids = bms_make_singleton(relid);
69 70
	rel->rows = 0;
	rel->width = 0;
71
	rel->reltargetlist = NIL;
72
	rel->pathlist = NIL;
73 74
	rel->cheapest_startup_path = NULL;
	rel->cheapest_total_path = NULL;
75
	rel->cheapest_unique_path = NULL;
76
	rel->relid = relid;
77
	rel->rtekind = rte->rtekind;
78
	/* min_attr, max_attr, attr_needed, attr_widths are set below */
79
	rel->indexlist = NIL;
80 81
	rel->pages = 0;
	rel->tuples = 0;
82
	rel->subplan = NULL;
83
	rel->baserestrictinfo = NIL;
84 85
	rel->baserestrictcost.startup = 0;
	rel->baserestrictcost.per_tuple = 0;
86
	rel->joininfo = NIL;
87
	rel->index_outer_relids = NULL;
88
	rel->index_inner_paths = NIL;
89

90 91
	/* Check type of rtable entry */
	switch (rte->rtekind)
92
	{
93
		case RTE_RELATION:
94
			/* Table --- retrieve statistics from the system catalogs */
95
			get_relation_info(root, rte->relid, rte->inh, rel);
96
			break;
97
		case RTE_SUBQUERY:
98
		case RTE_FUNCTION:
99 100 101 102 103 104 105
		case RTE_VALUES:
			/*
			 * Subquery, function, or values list --- set up attr range
			 * and arrays
			 *
			 * Note: 0 is included in range to support whole-row Vars
			 */
106
			rel->min_attr = 0;
107
			rel->max_attr = list_length(rte->eref->colnames);
108 109 110 111
			rel->attr_needed = (Relids *)
				palloc0((rel->max_attr - rel->min_attr + 1) * sizeof(Relids));
			rel->attr_widths = (int32 *)
				palloc0((rel->max_attr - rel->min_attr + 1) * sizeof(int32));
112 113
			break;
		default:
114
			elog(ERROR, "unrecognized RTE kind: %d",
115 116
				 (int) rte->rtekind);
			break;
117
	}
118

119 120
	/* Save the finished struct in the query's simple_rel_array */
	root->simple_rel_array[relid] = rel;
121

122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144
	/*
	 * If this rel is an appendrel parent, recurse to build "other rel"
	 * RelOptInfos for its children.  They are "other rels" because they are
	 * not in the main join tree, but we will need RelOptInfos to plan access
	 * to them.
	 */
	if (rte->inh)
	{
		ListCell   *l;

		foreach(l, root->append_rel_list)
		{
			AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(l);

			/* append_rel_list contains all append rels; ignore others */
			if (appinfo->parent_relid != relid)
				continue;

			(void) build_simple_rel(root, appinfo->child_relid,
									RELOPT_OTHER_MEMBER_REL);
		}
	}

145
	return rel;
146 147
}

148 149
/*
 * find_base_rel
150
 *	  Find a base or other relation entry, which must already exist.
151 152
 */
RelOptInfo *
153
find_base_rel(PlannerInfo *root, int relid)
154 155 156
{
	RelOptInfo *rel;

157
	Assert(relid > 0);
158

159
	if (relid < root->simple_rel_array_size)
160
	{
161
		rel = root->simple_rel_array[relid];
162
		if (rel)
163 164 165
			return rel;
	}

166
	elog(ERROR, "no relation entry for relid %d", relid);
167 168 169 170

	return NULL;				/* keep compiler quiet */
}

171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191
/*
 * build_join_rel_hash
 *	  Construct the auxiliary hash table for join relations.
 */
static void
build_join_rel_hash(PlannerInfo *root)
{
	HTAB	   *hashtab;
	HASHCTL		hash_ctl;
	ListCell   *l;

	/* Create the hash table */
	MemSet(&hash_ctl, 0, sizeof(hash_ctl));
	hash_ctl.keysize = sizeof(Relids);
	hash_ctl.entrysize = sizeof(JoinHashEntry);
	hash_ctl.hash = bitmap_hash;
	hash_ctl.match = bitmap_match;
	hash_ctl.hcxt = CurrentMemoryContext;
	hashtab = hash_create("JoinRelHashTable",
						  256L,
						  &hash_ctl,
192
					HASH_ELEM | HASH_FUNCTION | HASH_COMPARE | HASH_CONTEXT);
193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211

	/* Insert all the already-existing joinrels */
	foreach(l, root->join_rel_list)
	{
		RelOptInfo *rel = (RelOptInfo *) lfirst(l);
		JoinHashEntry *hentry;
		bool		found;

		hentry = (JoinHashEntry *) hash_search(hashtab,
											   &(rel->relids),
											   HASH_ENTER,
											   &found);
		Assert(!found);
		hentry->join_rel = rel;
	}

	root->join_rel_hash = hashtab;
}

212 213
/*
 * find_join_rel
214
 *	  Returns relation entry corresponding to 'relids' (a set of RT indexes),
215 216
 *	  or NULL if none exists.  This is for join relations.
 */
217
RelOptInfo *
218
find_join_rel(PlannerInfo *root, Relids relids)
219
{
220
	/*
221
	 * Switch to using hash lookup when list grows "too long".	The threshold
222 223 224 225
	 * is arbitrary and is known only here.
	 */
	if (!root->join_rel_hash && list_length(root->join_rel_list) > 32)
		build_join_rel_hash(root);
226

227 228 229
	/*
	 * Use either hashtable lookup or linear search, as appropriate.
	 *
230 231 232
	 * Note: the seemingly redundant hashkey variable is used to avoid taking
	 * the address of relids; unless the compiler is exceedingly smart, doing
	 * so would force relids out of a register and thus probably slow down the
233
	 * list-search case.
234 235
	 */
	if (root->join_rel_hash)
236
	{
237 238 239 240 241 242 243 244 245 246 247 248 249
		Relids		hashkey = relids;
		JoinHashEntry *hentry;

		hentry = (JoinHashEntry *) hash_search(root->join_rel_hash,
											   &hashkey,
											   HASH_FIND,
											   NULL);
		if (hentry)
			return hentry->join_rel;
	}
	else
	{
		ListCell   *l;
250

251 252 253 254 255 256 257
		foreach(l, root->join_rel_list)
		{
			RelOptInfo *rel = (RelOptInfo *) lfirst(l);

			if (bms_equal(rel->relids, relids))
				return rel;
		}
258 259 260 261 262
	}

	return NULL;
}

263
/*
264
 * build_join_rel
265 266 267
 *	  Returns relation entry corresponding to the union of two given rels,
 *	  creating a new relation entry if none already exists.
 *
268
 * 'joinrelids' is the Relids set that uniquely identifies the join
269 270
 * 'outer_rel' and 'inner_rel' are relation nodes for the relations to be
 *		joined
271
 * 'jointype': type of join (inner/outer)
272 273 274 275 276 277
 * 'restrictlist_ptr': result variable.  If not NULL, *restrictlist_ptr
 *		receives the list of RestrictInfo nodes that apply to this
 *		particular pair of joinable relations.
 *
 * restrictlist_ptr makes the routine's API a little grotty, but it saves
 * duplicated calculation of the restrictlist...
278
 */
Bruce Momjian's avatar
Bruce Momjian committed
279
RelOptInfo *
280
build_join_rel(PlannerInfo *root,
281
			   Relids joinrelids,
282 283 284 285
			   RelOptInfo *outer_rel,
			   RelOptInfo *inner_rel,
			   JoinType jointype,
			   List **restrictlist_ptr)
286
{
287 288 289 290 291 292 293 294 295 296 297
	RelOptInfo *joinrel;
	List	   *restrictlist;

	/*
	 * See if we already have a joinrel for this set of base rels.
	 */
	joinrel = find_join_rel(root, joinrelids);

	if (joinrel)
	{
		/*
298 299
		 * Yes, so we only need to figure the restrictlist for this particular
		 * pair of component relations.
300 301
		 */
		if (restrictlist_ptr)
302 303
			*restrictlist_ptr = build_joinrel_restrictlist(root,
														   joinrel,
304
														   outer_rel,
305 306
														   inner_rel,
														   jointype);
307 308 309 310 311 312 313
		return joinrel;
	}

	/*
	 * Nope, so make one.
	 */
	joinrel = makeNode(RelOptInfo);
314
	joinrel->reloptkind = RELOPT_JOINREL;
315
	joinrel->relids = bms_copy(joinrelids);
316 317
	joinrel->rows = 0;
	joinrel->width = 0;
318
	joinrel->reltargetlist = NIL;
319
	joinrel->pathlist = NIL;
320 321
	joinrel->cheapest_startup_path = NULL;
	joinrel->cheapest_total_path = NULL;
322
	joinrel->cheapest_unique_path = NULL;
323
	joinrel->relid = 0;			/* indicates not a baserel */
324
	joinrel->rtekind = RTE_JOIN;
325 326 327 328
	joinrel->min_attr = 0;
	joinrel->max_attr = 0;
	joinrel->attr_needed = NULL;
	joinrel->attr_widths = NULL;
329
	joinrel->indexlist = NIL;
330 331
	joinrel->pages = 0;
	joinrel->tuples = 0;
332
	joinrel->subplan = NULL;
333
	joinrel->baserestrictinfo = NIL;
334 335
	joinrel->baserestrictcost.startup = 0;
	joinrel->baserestrictcost.per_tuple = 0;
336
	joinrel->joininfo = NIL;
337
	joinrel->index_outer_relids = NULL;
338
	joinrel->index_inner_paths = NIL;
339 340

	/*
341 342
	 * Create a new tlist containing just the vars that need to be output from
	 * this join (ie, are needed for higher joinclauses or final output).
343
	 *
344 345 346
	 * NOTE: the tlist order for a join rel will depend on which pair of outer
	 * and inner rels we first try to build it from.  But the contents should
	 * be the same regardless.
347
	 */
348 349
	build_joinrel_tlist(root, joinrel, outer_rel);
	build_joinrel_tlist(root, joinrel, inner_rel);
350 351

	/*
352
	 * Construct restrict and join clause lists for the new joinrel. (The
353 354
	 * caller might or might not need the restrictlist, but I need it anyway
	 * for set_joinrel_size_estimates().)
355
	 */
356 357 358
	restrictlist = build_joinrel_restrictlist(root,
											  joinrel,
											  outer_rel,
359 360
											  inner_rel,
											  jointype);
361 362 363 364 365 366 367 368
	if (restrictlist_ptr)
		*restrictlist_ptr = restrictlist;
	build_joinrel_joinlist(joinrel, outer_rel, inner_rel);

	/*
	 * Set estimates of the joinrel's size.
	 */
	set_joinrel_size_estimates(root, joinrel, outer_rel, inner_rel,
369
							   jointype, restrictlist);
370 371

	/*
372 373 374
	 * Add the joinrel to the query's joinrel list, and store it into the
	 * auxiliary hashtable if there is one.  NB: GEQO requires us to append
	 * the new joinrel to the end of the list!
375
	 */
376 377 378 379 380 381 382 383 384 385 386 387 388 389
	root->join_rel_list = lappend(root->join_rel_list, joinrel);

	if (root->join_rel_hash)
	{
		JoinHashEntry *hentry;
		bool		found;

		hentry = (JoinHashEntry *) hash_search(root->join_rel_hash,
											   &(joinrel->relids),
											   HASH_ENTER,
											   &found);
		Assert(!found);
		hentry->join_rel = joinrel;
	}
390 391

	return joinrel;
392 393
}

394
/*
395 396
 * build_joinrel_tlist
 *	  Builds a join relation's target list.
397
 *
398
 * The join's targetlist includes all Vars of its member relations that
399 400
 * will still be needed above the join.  This subroutine adds all such
 * Vars from the specified input rel's tlist to the join rel's tlist.
401
 *
402 403
 * We also compute the expected width of the join's output, making use
 * of data that was cached at the baserel level by set_rel_width().
404
 */
405
static void
406 407
build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel,
					RelOptInfo *input_rel)
408
{
409
	Relids		relids = joinrel->relids;
410
	ListCell   *vars;
411

412
	foreach(vars, input_rel->reltargetlist)
413
	{
414 415
		Var		   *origvar = (Var *) lfirst(vars);
		Var		   *var;
416 417 418
		RelOptInfo *baserel;
		int			ndx;

419 420 421 422 423 424 425 426 427 428 429 430 431
		/*
		 * We can't run into any child RowExprs here, but we could find
		 * a whole-row Var with a ConvertRowtypeExpr atop it.
		 */
		var = origvar;
		while (!IsA(var, Var))
		{
			if (IsA(var, ConvertRowtypeExpr))
				var = (Var *) ((ConvertRowtypeExpr *) var)->arg;
			else
				elog(ERROR, "unexpected node type in reltargetlist: %d",
					 (int) nodeTag(var));
		}
432

433 434
		/* Get the Var's original base rel */
		baserel = find_base_rel(root, var->varno);
435

436 437 438
		/* Is it still needed above this joinrel? */
		ndx = var->varattno - baserel->min_attr;
		if (bms_nonempty_difference(baserel->attr_needed[ndx], relids))
439
		{
440
			/* Yup, add it to the output */
441
			joinrel->reltargetlist = lappend(joinrel->reltargetlist, origvar);
442
			joinrel->width += baserel->attr_widths[ndx];
443
		}
444 445 446 447 448 449 450 451 452 453 454
	}
}

/*
 * build_joinrel_restrictlist
 * build_joinrel_joinlist
 *	  These routines build lists of restriction and join clauses for a
 *	  join relation from the joininfo lists of the relations it joins.
 *
 *	  These routines are separate because the restriction list must be
 *	  built afresh for each pair of input sub-relations we consider, whereas
455 456
 *	  the join list need only be computed once for any join RelOptInfo.
 *	  The join list is fully determined by the set of rels making up the
457
 *	  joinrel, so we should get the same results (up to ordering) from any
458
 *	  candidate pair of sub-relations.	But the restriction list is whatever
459 460 461 462 463
 *	  is not handled in the sub-relations, so it depends on which
 *	  sub-relations are considered.
 *
 *	  If a join clause from an input relation refers to base rels still not
 *	  present in the joinrel, then it is still a join clause for the joinrel;
464
 *	  we put it into the joininfo list for the joinrel.  Otherwise,
465 466
 *	  the clause is now a restrict clause for the joined relation, and we
 *	  return it to the caller of build_joinrel_restrictlist() to be stored in
467
 *	  join paths made from this pair of sub-relations.	(It will not need to
468 469
 *	  be considered further up the join tree.)
 *
470 471 472 473 474
 *	  When building a restriction list, we eliminate redundant clauses.
 *	  We don't try to do that for join clause lists, since the join clauses
 *	  aren't really doing anything, just waiting to become part of higher
 *	  levels' restriction lists.
 *
475 476 477
 * 'joinrel' is a join relation node
 * 'outer_rel' and 'inner_rel' are a pair of relations that can be joined
 *		to form joinrel.
478
 * 'jointype' is the type of join used.
479 480 481
 *
 * build_joinrel_restrictlist() returns a list of relevant restrictinfos,
 * whereas build_joinrel_joinlist() stores its results in the joinrel's
482
 * joininfo list.  One or the other must accept each given clause!
483 484 485
 *
 * NB: Formerly, we made deep(!) copies of each input RestrictInfo to pass
 * up to the join relation.  I believe this is no longer necessary, because
486
 * RestrictInfo nodes are no longer context-dependent.	Instead, just include
487 488 489
 * the original nodes in the lists made for the join relation.
 */
static List *
490
build_joinrel_restrictlist(PlannerInfo *root,
491
						   RelOptInfo *joinrel,
492
						   RelOptInfo *outer_rel,
493 494
						   RelOptInfo *inner_rel,
						   JoinType jointype)
495
{
496
	List	   *result;
497
	List	   *rlist;
498 499 500 501

	/*
	 * Collect all the clauses that syntactically belong at this level.
	 */
502
	rlist = list_concat(subbuild_joinrel_restrictlist(joinrel,
503
													  outer_rel->joininfo),
504
						subbuild_joinrel_restrictlist(joinrel,
505
													  inner_rel->joininfo));
506

507
	/*
508 509
	 * Eliminate duplicate and redundant clauses.
	 *
510 511
	 * We must eliminate duplicates, since we will see many of the same
	 * clauses arriving from both input relations.	Also, if a clause is a
512 513 514
	 * mergejoinable clause, it's possible that it is redundant with previous
	 * clauses (see optimizer/README for discussion).  We detect that case and
	 * omit the redundant clause from the result list.
515
	 */
516 517
	result = remove_redundant_join_clauses(root, rlist,
										   IS_OUTER_JOIN(jointype));
518

519
	list_free(rlist);
520 521

	return result;
522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537
}

static void
build_joinrel_joinlist(RelOptInfo *joinrel,
					   RelOptInfo *outer_rel,
					   RelOptInfo *inner_rel)
{
	subbuild_joinrel_joinlist(joinrel, outer_rel->joininfo);
	subbuild_joinrel_joinlist(joinrel, inner_rel->joininfo);
}

static List *
subbuild_joinrel_restrictlist(RelOptInfo *joinrel,
							  List *joininfo_list)
{
	List	   *restrictlist = NIL;
538
	ListCell   *l;
539

540
	foreach(l, joininfo_list)
541
	{
542
		RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
543

544
		if (bms_is_subset(rinfo->required_relids, joinrel->relids))
545 546
		{
			/*
547 548 549
			 * This clause becomes a restriction clause for the joinrel, since
			 * it refers to no outside rels.  We don't bother to check for
			 * duplicates here --- build_joinrel_restrictlist will do that.
550
			 */
551
			restrictlist = lappend(restrictlist, rinfo);
552 553 554 555
		}
		else
		{
			/*
556 557
			 * This clause is still a join clause at this level, so we ignore
			 * it in this routine.
558 559 560 561 562 563 564 565 566 567 568
			 */
		}
	}

	return restrictlist;
}

static void
subbuild_joinrel_joinlist(RelOptInfo *joinrel,
						  List *joininfo_list)
{
569
	ListCell   *l;
570

571
	foreach(l, joininfo_list)
572
	{
573
		RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
574

575
		if (bms_is_subset(rinfo->required_relids, joinrel->relids))
576 577
		{
			/*
578 579 580
			 * This clause becomes a restriction clause for the joinrel, since
			 * it refers to no outside rels.  So we can ignore it in this
			 * routine.
581 582 583 584 585
			 */
		}
		else
		{
			/*
586 587 588
			 * This clause is still a join clause at this level, so add it to
			 * the joininfo list for the joinrel, being careful to eliminate
			 * duplicates.	(Since RestrictInfo nodes are normally
589 590 591 592
			 * multiply-linked rather than copied, pointer equality should be
			 * a sufficient test.  If two equal() nodes should happen to sneak
			 * in, no great harm is done --- they'll be detected by
			 * redundant-clause testing when they reach a restriction list.)
593
			 */
594 595
			joinrel->joininfo = list_append_unique_ptr(joinrel->joininfo,
													   rinfo);
596
		}
597 598
	}
}