joinpath.c 17.2 KB
Newer Older
1 2 3
/*-------------------------------------------------------------------------
 *
 * joinpath.c--
4
 *	  Routines to find all possible paths for processing a set of joins
5 6 7 8 9
 *
 * Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
10
 *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/joinpath.c,v 1.17 1999/02/10 03:52:40 momjian Exp $
11 12 13
 *
 *-------------------------------------------------------------------------
 */
Marc G. Fournier's avatar
Marc G. Fournier committed
14
#include <sys/types.h>
15 16
#include <math.h>

Marc G. Fournier's avatar
Marc G. Fournier committed
17 18
#include "postgres.h"

19 20 21 22 23 24 25 26 27 28
#include "storage/buf_internals.h"

#include "nodes/pg_list.h"
#include "nodes/relation.h"
#include "nodes/plannodes.h"

#include "optimizer/internal.h"
#include "optimizer/paths.h"
#include "optimizer/pathnode.h"
#include "optimizer/keys.h"
29
#include "optimizer/cost.h"		/* for _enable_{hashjoin,
30
								 * _enable_mergejoin} */
31

32
static Path *best_innerjoin(List *join_paths, List *outer_relid);
33
static List *sort_inner_and_outer(RelOptInfo * joinrel, RelOptInfo * outerrel, RelOptInfo * innerrel,
34
					 List *mergeinfo_list);
35
static List *match_unsorted_outer(RelOptInfo * joinrel, RelOptInfo * outerrel, RelOptInfo * innerrel,
36 37
		List *outerpath_list, Path *cheapest_inner, Path *best_innerjoin,
					 List *mergeinfo_list);
38
static List *match_unsorted_inner(RelOptInfo * joinrel, RelOptInfo * outerrel, RelOptInfo * innerrel,
39
					 List *innerpath_list, List *mergeinfo_list);
40 41
static bool EnoughMemoryForHashjoin(RelOptInfo * hashrel);
static List *hash_inner_and_outer(RelOptInfo * joinrel, RelOptInfo * outerrel, RelOptInfo * innerrel,
42
					 List *hashinfo_list);
43 44

/*
45
 * find-all-join-paths--
46 47 48 49 50 51 52 53
 *	  Creates all possible ways to process joins for each of the join
 *	  relations in the list 'joinrels.'  Each unique path will be included
 *	  in the join relation's 'pathlist' field.
 *
 *	  In postgres, n-way joins are handled left-only(permuting clauseless
 *	  joins doesn't usually win much).
 *
 *	  if BushyPlanFlag is true, bushy tree plans will be generated
54 55
 *
 * 'joinrels' is the list of relation entries to be joined
56
 *
57 58 59 60
 * Modifies the pathlist field of the appropriate rel node to contain
 * the unique join paths.
 * If bushy trees are considered, may modify the relid field of the
 * join rel nodes to flatten the lists.
61 62
 *
 * Returns nothing of interest. (?)
63 64 65
 * It does a destructive modification.
 */
void
66
find_all_join_paths(Query *root, List *joinrels)
67
{
68 69 70 71
	List	   *mergeinfo_list = NIL;
	List	   *hashinfo_list = NIL;
	List	   *temp_list = NIL;
	List	   *path = NIL;
72 73 74

	while (joinrels != NIL)
	{
75
		RelOptInfo *joinrel = (RelOptInfo *) lfirst(joinrels);
76 77
		List	   *innerrelids;
		List	   *outerrelids;
78 79
		RelOptInfo *innerrel;
		RelOptInfo *outerrel;
80 81
		Path	   *bestinnerjoin;
		List	   *pathlist = NIL;
82 83 84 85 86 87 88 89 90 91 92 93 94 95 96

		innerrelids = lsecond(joinrel->relids);
		outerrelids = lfirst(joinrel->relids);

		/*
		 * base relation id is an integer and join relation relid is a
		 * list of integers.
		 */
		innerrel = (length(innerrelids) == 1) ?
			get_base_rel(root, lfirsti(innerrelids)) : get_join_rel(root, innerrelids);
		outerrel = (length(outerrelids) == 1) ?
			get_base_rel(root, lfirsti(outerrelids)) : get_join_rel(root, outerrelids);

		bestinnerjoin = best_innerjoin(innerrel->innerjoin,
									   outerrel->relids);
97
		if (_enable_mergejoin_)
98
		{
99
			mergeinfo_list = group_clauses_by_order(joinrel->restrictinfo,
100 101 102 103 104
									   lfirsti(innerrel->relids));
		}

		if (_enable_hashjoin_)
		{
105
			hashinfo_list = group_clauses_by_hashop(joinrel->restrictinfo,
106 107 108 109 110 111 112
										lfirsti(innerrel->relids));
		}

		/* need to flatten the relids list */
		joinrel->relids = intAppend(outerrelids, innerrelids);

		/*
113
		 * 1. Consider mergejoin paths where both relations must be
114 115 116 117 118 119 120 121
		 * explicitly sorted.
		 */
		pathlist = sort_inner_and_outer(joinrel, outerrel,
										innerrel, mergeinfo_list);

		/*
		 * 2. Consider paths where the outer relation need not be
		 * explicitly sorted. This may include either nestloops and
122
		 * mergejoins where the outer path is already ordered.
123
		 */
124
		pathlist = add_pathlist(joinrel, pathlist,
125 126 127 128 129 130 131 132 133 134
						 match_unsorted_outer(joinrel,
											  outerrel,
											  innerrel,
											  outerrel->pathlist,
										 (Path *) innerrel->cheapestpath,
											  bestinnerjoin,
											  mergeinfo_list));

		/*
		 * 3. Consider paths where the inner relation need not be
135
		 * explicitly sorted.  This may include nestloops and mergejoins
136 137 138
		 * the actual nestloop nodes were constructed in
		 * (match-unsorted-outer).
		 */
139
		pathlist = add_pathlist(joinrel, pathlist,
140 141 142 143 144 145 146 147 148 149
						 match_unsorted_inner(joinrel, outerrel,
											  innerrel,
											  innerrel->pathlist,
											  mergeinfo_list));

		/*
		 * 4. Consider paths where both outer and inner relations must be
		 * hashed before being joined.
		 */

150
		pathlist = add_pathlist(joinrel, pathlist,
151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181
						 hash_inner_and_outer(joinrel, outerrel,
											  innerrel, hashinfo_list));

		joinrel->pathlist = pathlist;

		/*
		 * 'OuterJoinCost is only valid when calling
		 * (match-unsorted-inner) with the same arguments as the previous
		 * invokation of (match-unsorted-outer), so clear the field before
		 * going on.
		 */
		temp_list = innerrel->pathlist;
		foreach(path, temp_list)
		{
			/*
			 * XXX
			 *
			 * This gross hack is to get around an apparent optimizer bug on
			 * Sparc (or maybe it is a bug of ours?) that causes really
			 * wierd behavior.
			 */
			if (IsA_JoinPath(path))
				((Path *) lfirst(path))->outerjoincost = (Cost) 0;

			/*
			 * do it iff it is a join path, which is not always true, esp
			 * since the base level
			 */
		}

		joinrels = lnext(joinrels);
182 183 184
	}
}

185
/*
186
 * best-innerjoin--
187 188 189 190
 *	  Find the cheapest index path that has already been identified by
 *	  (indexable_joinclauses) as being a possible inner path for the given
 *	  outer relation in a nestloop join.
 *
191 192
 * 'join-paths' is a list of join nodes
 * 'outer-relid' is the relid of the outer join relation
193
 *
194 195
 * Returns the pathnode of the selected path.
 */
196
static Path *
197
best_innerjoin(List *join_paths, List *outer_relids)
198
{
199 200
	Path	   *cheapest = (Path *) NULL;
	List	   *join_path;
201 202 203

	foreach(join_path, join_paths)
	{
204
		Path	   *path = (Path *) lfirst(join_path);
205

206 207 208 209
		if (intMember(lfirsti(path->joinid), outer_relids)
			&& ((cheapest == NULL ||
				 path_is_cheaper((Path *) lfirst(join_path), cheapest))))
		{
210

211 212
			cheapest = (Path *) lfirst(join_path);
		}
213
	}
214
	return cheapest;
215 216
}

217
/*
218
 * sort-inner-and-outer--
219
 *	  Create mergejoin join paths by explicitly sorting both the outer and
220 221
 *	  inner join relations on each available merge ordering.
 *
222 223 224
 * 'joinrel' is the join relation
 * 'outerrel' is the outer join relation
 * 'innerrel' is the inner join relation
225
 * 'mergeinfo-list' is a list of nodes containing info on(mergejoinable)
226 227
 *				clauses for joining the relations
 *
228
 * Returns a list of mergejoin paths.
229
 */
230
static List *
231 232 233
sort_inner_and_outer(RelOptInfo * joinrel,
					 RelOptInfo * outerrel,
					 RelOptInfo * innerrel,
234
					 List *mergeinfo_list)
235
{
236
	List	   *ms_list = NIL;
Bruce Momjian's avatar
Bruce Momjian committed
237
	MergeInfo	   *xmergeinfo = (MergeInfo *) NULL;
238 239 240 241 242
	MergePath  *temp_node = (MergePath *) NULL;
	List	   *i;
	List	   *outerkeys = NIL;
	List	   *innerkeys = NIL;
	List	   *merge_pathkeys = NIL;
243 244 245

	foreach(i, mergeinfo_list)
	{
Bruce Momjian's avatar
Bruce Momjian committed
246
		xmergeinfo = (MergeInfo *) lfirst(i);
247

248
		outerkeys = extract_path_keys(xmergeinfo->jmethod.jmkeys,
249 250 251
							  outerrel->targetlist,
							  OUTER);

252
		innerkeys = extract_path_keys(xmergeinfo->jmethod.jmkeys,
253 254 255
							  innerrel->targetlist,
							  INNER);

256
		merge_pathkeys = new_join_pathkeys(outerkeys, joinrel->targetlist,
257 258
							  xmergeinfo->jmethod.clauses);

259
		temp_node = create_mergejoin_path(joinrel,
260 261 262 263 264 265 266 267 268 269 270 271 272 273
								  outerrel->size,
								  innerrel->size,
								  outerrel->width,
								  innerrel->width,
								  (Path *) outerrel->cheapestpath,
								  (Path *) innerrel->cheapestpath,
								  merge_pathkeys,
								  xmergeinfo->m_ordering,
								  xmergeinfo->jmethod.clauses,
								  outerkeys,
								  innerkeys);

		ms_list = lappend(ms_list, temp_node);
	}
274
	return ms_list;
275 276
}

277
/*
278
 * match-unsorted-outer--
279 280
 *	  Creates possible join paths for processing a single join relation
 *	  'joinrel' by employing either iterative substitution or
281
 *	  mergejoining on each of its possible outer paths(assuming that the
282 283 284
 *	  outer relation need not be explicitly sorted).
 *
 *	  1. The inner path is the cheapest available inner path.
285 286
 *	  2. Mergejoin wherever possible.  Mergejoin are considered if there
 *		 are mergejoinable join clauses between the outer and inner join
287 288 289 290 291 292
 *		 relations such that the outer path is keyed on the variables
 *		 appearing in the clauses.	The corresponding inner merge path is
 *		 either a path whose keys match those of the outer path(if such a
 *		 path is available) or an explicit sort on the appropriate inner
 *		 join keys, whichever is cheaper.
 *
293 294 295 296 297 298
 * 'joinrel' is the join relation
 * 'outerrel' is the outer join relation
 * 'innerrel' is the inner join relation
 * 'outerpath-list' is the list of possible outer paths
 * 'cheapest-inner' is the cheapest inner path
 * 'best-innerjoin' is the best inner index path(if any)
299
 * 'mergeinfo-list' is a list of nodes containing info on mergejoinable
300 301
 *		clauses
 *
302 303
 * Returns a list of possible join path nodes.
 */
304
static List *
305 306 307
match_unsorted_outer(RelOptInfo * joinrel,
					 RelOptInfo * outerrel,
					 RelOptInfo * innerrel,
308 309 310 311
					 List *outerpath_list,
					 Path *cheapest_inner,
					 Path *best_innerjoin,
					 List *mergeinfo_list)
312
{
313 314 315 316 317 318 319 320
	Path	   *outerpath = (Path *) NULL;
	List	   *jp_list = NIL;
	List	   *temp_node = NIL;
	List	   *merge_pathkeys = NIL;
	Path	   *nestinnerpath = (Path *) NULL;
	List	   *paths = NIL;
	List	   *i = NIL;
	PathOrder  *outerpath_ordering = NULL;
321 322 323

	foreach(i, outerpath_list)
	{
324 325 326
		List	   *clauses = NIL;
		List	   *matchedJoinKeys = NIL;
		List	   *matchedJoinClauses = NIL;
327
		MergeInfo  *xmergeinfo = (MergeInfo *) NULL;
328 329 330

		outerpath = (Path *) lfirst(i);

331
		outerpath_ordering = outerpath->path_order;
332 333 334

		if (outerpath_ordering)
		{
335
			xmergeinfo = match_order_mergeinfo(outerpath_ordering,
336 337 338 339 340 341 342 343
									  mergeinfo_list);
		}

		if (xmergeinfo)
			clauses = xmergeinfo->jmethod.clauses;

		if (clauses)
		{
344
			List	   *jmkeys = xmergeinfo->jmethod.jmkeys;
345
			List	   *clauses = xmergeinfo->jmethod.clauses;
346

347 348
			matchedJoinKeys = match_pathkeys_joinkeys(outerpath->pathkeys,
										jmkeys,
349 350 351
										clauses,
										OUTER,
										&matchedJoinClauses);
352
			merge_pathkeys = new_join_pathkeys(outerpath->pathkeys,
353 354 355
								  joinrel->targetlist, clauses);
		}
		else
356
			merge_pathkeys = outerpath->pathkeys;
357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372

		if (best_innerjoin &&
			path_is_cheaper(best_innerjoin, cheapest_inner))
			nestinnerpath = best_innerjoin;
		else
			nestinnerpath = cheapest_inner;

		paths = lcons(create_nestloop_path(joinrel,
										   outerrel,
										   outerpath,
										   nestinnerpath,
										   merge_pathkeys),
					  NIL);

		if (clauses && matchedJoinKeys)
		{
373 374
			bool		path_is_cheaper_than_sort;
			List	   *varkeys = NIL;
375
			Path	   *mergeinnerpath = match_paths_joinkeys(matchedJoinKeys,
376 377 378 379
								 outerpath_ordering,
								 innerrel->pathlist,
								 INNER);

380
			path_is_cheaper_than_sort = (bool) (mergeinnerpath &&
381 382 383 384 385 386 387 388
						(mergeinnerpath->path_cost <
						 (cheapest_inner->path_cost +
						  cost_sort(matchedJoinKeys,
									innerrel->size,
									innerrel->width,
									false))));
			if (!path_is_cheaper_than_sort)
			{
389
				varkeys = extract_path_keys(matchedJoinKeys,
390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405
									  innerrel->targetlist,
									  INNER);
			}


			/*
			 * Keep track of the cost of the outer path used with this
			 * ordered inner path for later processing in
			 * (match-unsorted-inner), since it isn't a sort and thus
			 * wouldn't otherwise be considered.
			 */
			if (path_is_cheaper_than_sort)
				mergeinnerpath->outerjoincost = outerpath->path_cost;
			else
				mergeinnerpath = cheapest_inner;

406
			temp_node = lcons(create_mergejoin_path(joinrel,
407 408 409 410 411 412 413 414 415 416 417
											outerrel->size,
											innerrel->size,
											outerrel->width,
											innerrel->width,
											outerpath,
											mergeinnerpath,
											merge_pathkeys,
											xmergeinfo->m_ordering,
											matchedJoinClauses,
											NIL,
											varkeys),
418
									  paths);
419 420 421 422 423
		}
		else
			temp_node = paths;
		jp_list = nconc(jp_list, temp_node);
	}
424
	return jp_list;
425 426
}

427
/*
428
 * match-unsorted-inner --
429 430 431 432 433 434 435 436 437 438 439 440
 *	  Find the cheapest ordered join path for a given(ordered, unsorted)
 *	  inner join path.
 *
 *	  Scans through each path available on an inner join relation and tries
 *	  matching its ordering keys against those of mergejoin clauses.
 *	  If 1. an appropriately-ordered inner path and matching mergeclause are
 *			found, and
 *		 2. sorting the cheapest outer path is cheaper than using an ordered
 *			  but unsorted outer path(as was considered in
 *			  (match-unsorted-outer)),
 *	  then this merge path is considered.
 *
441 442 443 444
 * 'joinrel' is the join result relation
 * 'outerrel' is the outer join relation
 * 'innerrel' is the inner join relation
 * 'innerpath-list' is the list of possible inner join paths
445
 * 'mergeinfo-list' is a list of nodes containing info on mergejoinable
446 447
 *				clauses
 *
448 449
 * Returns a list of possible merge paths.
 */
450
static List *
451 452 453
match_unsorted_inner(RelOptInfo * joinrel,
					 RelOptInfo * outerrel,
					 RelOptInfo * innerrel,
454 455
					 List *innerpath_list,
					 List *mergeinfo_list)
456
{
457 458 459 460 461 462 463
	Path	   *innerpath = (Path *) NULL;
	List	   *mp_list = NIL;
	List	   *temp_node = NIL;
	PathOrder  *innerpath_ordering = NULL;
	Cost		temp1 = 0.0;
	bool		temp2 = false;
	List	   *i = NIL;
464 465 466

	foreach(i, innerpath_list)
	{
467
		MergeInfo  *xmergeinfo = (MergeInfo *) NULL;
468 469 470
		List	   *clauses = NIL;
		List	   *matchedJoinKeys = NIL;
		List	   *matchedJoinClauses = NIL;
471 472 473

		innerpath = (Path *) lfirst(i);

474
		innerpath_ordering = innerpath->path_order;
475 476 477

		if (innerpath_ordering)
		{
478
			xmergeinfo = match_order_mergeinfo(innerpath_ordering,
479 480 481 482 483 484 485 486
									  mergeinfo_list);
		}

		if (xmergeinfo)
			clauses = ((JoinMethod *) xmergeinfo)->clauses;

		if (clauses)
		{
487
			List	   *jmkeys = xmergeinfo->jmethod.jmkeys;
488
			List	   *cls = xmergeinfo->jmethod.clauses;
489

490 491
			matchedJoinKeys = match_pathkeys_joinkeys(innerpath->pathkeys,
										jmkeys,
492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511
										cls,
										INNER,
										&matchedJoinClauses);
		}

		/*
		 * (match-unsorted-outer) if it is applicable. 'OuterJoinCost was
		 * set above in
		 */
		if (clauses && matchedJoinKeys)
		{
			temp1 = outerrel->cheapestpath->path_cost +
				cost_sort(matchedJoinKeys, outerrel->size, outerrel->width,
						  false);

			temp2 = (bool) (FLOAT_IS_ZERO(innerpath->outerjoincost)
							|| (innerpath->outerjoincost > temp1));

			if (temp2)
			{
512
				List	   *outerkeys = extract_path_keys(matchedJoinKeys,
513 514
								  outerrel->targetlist,
								  OUTER);
515
				List	   *merge_pathkeys = new_join_pathkeys(outerkeys,
516 517 518
								  joinrel->targetlist,
								  clauses);

519
				temp_node = lcons(create_mergejoin_path(joinrel,
520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535
												outerrel->size,
												innerrel->size,
												outerrel->width,
												innerrel->width,
										 (Path *) outerrel->cheapestpath,
												innerpath,
												merge_pathkeys,
												xmergeinfo->m_ordering,
												matchedJoinClauses,
												outerkeys,
												NIL),
						  NIL);

				mp_list = nconc(mp_list, temp_node);
			}
		}
536
	}
537
	return mp_list;
538

539 540
}

541
static bool
542
EnoughMemoryForHashjoin(RelOptInfo * hashrel)
543
{
544 545 546
	int			ntuples;
	int			tupsize;
	int			pages;
547 548 549 550 551 552 553 554 555 556 557 558 559

	ntuples = hashrel->size;
	if (ntuples == 0)
		ntuples = 1000;
	tupsize = hashrel->width + sizeof(HeapTupleData);
	pages = page_size(ntuples, tupsize);

	/*
	 * if amount of buffer space below hashjoin threshold, return false
	 */
	if (ceil(sqrt((double) pages)) > NBuffers)
		return false;
	return true;
560 561
}

562 563 564 565 566
/*
 * hash-inner-and-outer--				XXX HASH
 *	  Create hashjoin join paths by explicitly hashing both the outer and
 *	  inner join relations on each available hash op.
 *
567 568 569 570
 * 'joinrel' is the join relation
 * 'outerrel' is the outer join relation
 * 'innerrel' is the inner join relation
 * 'hashinfo-list' is a list of nodes containing info on(hashjoinable)
571 572
 *		clauses for joining the relations
 *
573 574
 * Returns a list of hashjoin paths.
 */
575
static List *
576 577 578
hash_inner_and_outer(RelOptInfo * joinrel,
					 RelOptInfo * outerrel,
					 RelOptInfo * innerrel,
579
					 List *hashinfo_list)
580
{
Bruce Momjian's avatar
Bruce Momjian committed
581
	HashInfo   *xhashinfo = (HashInfo *) NULL;
582 583 584 585 586 587
	List	   *hjoin_list = NIL;
	HashPath   *temp_node = (HashPath *) NULL;
	List	   *i = NIL;
	List	   *outerkeys = NIL;
	List	   *innerkeys = NIL;
	List	   *hash_pathkeys = NIL;
588 589 590

	foreach(i, hashinfo_list)
	{
591
		xhashinfo = (HashInfo *) lfirst(i);
592
		outerkeys = extract_path_keys(((JoinMethod *) xhashinfo)->jmkeys,
593 594
							  outerrel->targetlist,
							  OUTER);
595
		innerkeys = extract_path_keys(((JoinMethod *) xhashinfo)->jmkeys,
596 597
							  innerrel->targetlist,
							  INNER);
598
		hash_pathkeys = new_join_pathkeys(outerkeys,
599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617
							  joinrel->targetlist,
							  ((JoinMethod *) xhashinfo)->clauses);

		if (EnoughMemoryForHashjoin(innerrel))
		{
			temp_node = create_hashjoin_path(joinrel,
											 outerrel->size,
											 innerrel->size,
											 outerrel->width,
											 innerrel->width,
										 (Path *) outerrel->cheapestpath,
										 (Path *) innerrel->cheapestpath,
											 hash_pathkeys,
											 xhashinfo->hashop,
									 ((JoinMethod *) xhashinfo)->clauses,
											 outerkeys,
											 innerkeys);
			hjoin_list = lappend(hjoin_list, temp_node);
		}
618
	}
619
	return hjoin_list;
620
}