pathnode.c 17.1 KB
Newer Older
1 2 3
/*-------------------------------------------------------------------------
 *
 * pathnode.c--
4
 *	  Routines to manipulate pathlists and create path nodes
5 6 7 8 9
 *
 * Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
Bruce Momjian's avatar
Bruce Momjian committed
10
 *	  $Header: /cvsroot/pgsql/src/backend/optimizer/util/pathnode.c,v 1.27 1999/02/11 16:09:41 momjian Exp $
11 12 13 14 15 16 17 18 19 20 21 22
 *
 *-------------------------------------------------------------------------
 */
#include <math.h>

#include "postgres.h"

#include "nodes/relation.h"
#include "utils/elog.h"

#include "optimizer/internal.h"
#include "optimizer/pathnode.h"
23
#include "optimizer/restrictinfo.h"
24 25 26 27 28 29
#include "optimizer/plancat.h"
#include "optimizer/cost.h"
#include "optimizer/keys.h"
#include "optimizer/xfunc.h"
#include "optimizer/ordering.h"

30
#include "parser/parsetree.h"	/* for getrelid() */
31

32
static Path *better_path(Path *new_path, List *unique_paths, bool *isNew);
33 34 35


/*****************************************************************************
36
 *		MISC. PATH UTILITIES
37 38
 *****************************************************************************/

39
/*
40
 * path-is-cheaper--
41 42
 *	  Returns t iff 'path1' is cheaper than 'path2'.
 *
43 44
 */
bool
45
path_is_cheaper(Path *path1, Path *path2)
46
{
47 48
	Cost		cost1 = path1->path_cost;
	Cost		cost2 = path2->path_cost;
49

50
	return (bool) (cost1 < cost2);
51 52
}

53
/*
54
 * set_cheapest--
55 56
 *	  Finds the minimum cost path from among a relation's paths.
 *
57 58
 * 'parent-rel' is the parent relation
 * 'pathlist' is a list of path nodes corresponding to 'parent-rel'
59 60
 *
 * Returns and sets the relation entry field with the pathnode that
61
 * is minimum.
62
 *
63
 */
64
Path *
65
set_cheapest(RelOptInfo *parent_rel, List *pathlist)
66
{
67 68
	List	   *p;
	Path	   *cheapest_so_far;
69

70
	Assert(pathlist != NIL);
Bruce Momjian's avatar
Bruce Momjian committed
71
	Assert(IsA(parent_rel, RelOptInfo));
72

73
	cheapest_so_far = (Path *) lfirst(pathlist);
74

75 76
	foreach(p, lnext(pathlist))
	{
77
		Path	   *path = (Path *) lfirst(p);
78

79 80
		if (path_is_cheaper(path, cheapest_so_far))
			cheapest_so_far = path;
81 82
	}

83
	parent_rel->cheapestpath = cheapest_so_far;
84

85
	return cheapest_so_far;
86 87
}

88
/*
89
 * add_pathlist--
90 91 92 93 94 95
 *	  For each path in the list 'new-paths', add to the list 'unique-paths'
 *	  only those paths that are unique (i.e., unique ordering and ordering
 *	  keys).  Should a conflict arise, the more expensive path is thrown out,
 *	  thereby pruning the plan space.  But we don't prune if xfunc
 *	  told us not to.
 *
96
 * 'parent-rel' is the relation entry to which these paths correspond.
97
 *
98
 * Returns the list of unique pathnodes.
99
 *
100
 */
101
List *
102
add_pathlist(RelOptInfo *parent_rel, List *unique_paths, List *new_paths)
103
{
Bruce Momjian's avatar
Bruce Momjian committed
104
	List	   *p1;
105

Bruce Momjian's avatar
Bruce Momjian committed
106
	foreach(p1, new_paths)
107
	{
Bruce Momjian's avatar
Bruce Momjian committed
108 109
		Path	   *new_path = (Path *) lfirst(p1);
 		Path	   *old_path;
110
		bool		is_new;
Bruce Momjian's avatar
Bruce Momjian committed
111 112

		/* Is this new path already in unique_paths? */
113 114
		if (member(new_path, unique_paths))
			continue;
Bruce Momjian's avatar
Bruce Momjian committed
115 116

		/* Find best matching path */
117
		old_path = better_path(new_path, unique_paths, &is_new);
118

119
		if (is_new)
120
		{
Bruce Momjian's avatar
Bruce Momjian committed
121
			/* This is a brand new path.  */
122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137
			new_path->parent = parent_rel;
			unique_paths = lcons(new_path, unique_paths);
		}
		else if (old_path == NULL)
		{
			;					/* do nothing if path is not cheaper */
		}
		else if (old_path != NULL)
		{						/* (IsA(old_path,Path)) { */
			new_path->parent = parent_rel;
			if (!parent_rel->pruneable)
				unique_paths = lcons(new_path, unique_paths);
			else
				unique_paths = lcons(new_path,
									 LispRemove(old_path, unique_paths));
		}
138
	}
139
	return unique_paths;
140 141
}

142
/*
143
 * better_path--
144 145 146 147
 *	  Determines whether 'new-path' has the same ordering and keys as some
 *	  path in the list 'unique-paths'.	If there is a redundant path,
 *	  eliminate the more expensive path.
 *
148
 * Returns:
149 150 151 152 153
 *	  The old path - if 'new-path' matches some path in 'unique-paths' and is
 *				cheaper
 *	  nil - if 'new-path' matches but isn't cheaper
 *	  t - if there is no path in the list with the same ordering and keys
 *
154
 */
155
static Path *
156
better_path(Path *new_path, List *unique_paths, bool *is_new)
157
{
158 159
	Path	   *path = (Path *) NULL;
	List	   *temp = NIL;
160
	int			longer_key;
Bruce Momjian's avatar
Bruce Momjian committed
161 162
	int			more_sort;
	
163 164 165 166
	foreach(temp, unique_paths)
	{
		path = (Path *) lfirst(temp);

167
#ifdef OPTDUP_DEBUG
168 169
		if (!pathkeys_match(new_path->pathkeys, path->pathkeys, &longer_key) ||
		    longer_key != 0)
170 171
		{
			printf("oldpath\n");
172
			pprint(path->pathkeys);
173
			printf("newpath\n");
174 175 176 177
			pprint(new_path->pathkeys);
			if (path->pathkeys && new_path->pathkeys &&
				length(lfirst(path->pathkeys)) >= 2 &&
				length(lfirst(path->pathkeys)) < length(lfirst(new_path->pathkeys)))
178 179
				sleep(0); /* set breakpoint here */
		}
Bruce Momjian's avatar
Bruce Momjian committed
180
		if (!pathorder_match(new_path->pathorder, path->pathorder, &more_sort))
181 182
		{
			printf("oldord\n");
Bruce Momjian's avatar
Bruce Momjian committed
183
			pprint(path->pathorder);
184
			printf("neword\n");
Bruce Momjian's avatar
Bruce Momjian committed
185
			pprint(new_path->pathorder);
186 187
		}
#endif
188 189

		if (pathkeys_match(new_path->pathkeys, path->pathkeys, &longer_key))
190
		{
Bruce Momjian's avatar
Bruce Momjian committed
191
			if (pathorder_match(new_path->pathorder, path->pathorder, &more_sort))
192 193 194 195 196
			{
				/*
				 * Replace pathkeys that match exactly, (1,2), (1,2).
				 * Replace pathkeys (1,2) with (1,2,3) if the latter is not
				 * more expensive and replace unordered path with ordered
Bruce Momjian's avatar
Bruce Momjian committed
197 198
				 * path if it is not more expensive.  Favor sorted keys
				 * over unsorted keys in the same way.
199
				 */
Bruce Momjian's avatar
Bruce Momjian committed
200 201 202 203 204 205 206 207
								/* same keys, and new is cheaper, use it */
			    if ((longer_key == 0 && more_sort == 0 &&
					new_path->path_cost <  path->path_cost) ||

								/* new is better, and cheaper, use it */
					((longer_key == 1 && more_sort != 2) ||
					 (longer_key != 2 && more_sort == 1)) &&
					 new_path->path_cost <= path->path_cost)
208 209 210 211
				{
					*is_new = false;
					return new_path;
				}
Bruce Momjian's avatar
Bruce Momjian committed
212 213 214 215 216 217 218 219 220 221

								/* same keys, new is more expensive, stop */
			    else if
					((longer_key == 0 && more_sort == 0 &&
					 new_path->path_cost >= path->path_cost) ||

								/* old is better, and less expensive, stop */
					((longer_key == 2 && more_sort != 1) ||
					 (longer_key != 1 && more_sort == 2)) &&
					  new_path->path_cost >= path->path_cost)
222 223 224 225 226
				{
					*is_new = false;
					return NULL;
				}
			}
227
		}
228
	}
229

230 231
	*is_new = true;
	return NULL;
232 233 234 235 236
}



/*****************************************************************************
237
 *		PATH NODE CREATION ROUTINES
238 239
 *****************************************************************************/

240
/*
241
 * create_seqscan_path--
242 243 244
 *	  Creates a path corresponding to a sequential scan, returning the
 *	  pathnode.
 *
245
 */
246
Path *
Bruce Momjian's avatar
Bruce Momjian committed
247
create_seqscan_path(RelOptInfo *rel)
248
{
249
	int			relid = 0;
250

251
	Path	   *pathnode = makeNode(Path);
252 253 254 255

	pathnode->pathtype = T_SeqScan;
	pathnode->parent = rel;
	pathnode->path_cost = 0.0;
Bruce Momjian's avatar
Bruce Momjian committed
256 257 258
	pathnode->pathorder = makeNode(PathOrder);
	pathnode->pathorder->ordtype = SORTOP_ORDER;
	pathnode->pathorder->ord.sortop = NULL;
259
	pathnode->pathkeys = NIL;
260 261

	/*
262
	 * copy restrictinfo list into path for expensive function processing --
263 264
	 * JMH, 7/7/92
	 */
265
	pathnode->loc_restrictinfo = (List *) copyObject((Node *) rel->restrictinfo);
266 267 268 269 270 271 272

	if (rel->relids != NULL)
		relid = lfirsti(rel->relids);

	pathnode->path_cost = cost_seqscan(relid,
									   rel->pages, rel->tuples);
	/* add in expensive functions cost!  -- JMH, 7/7/92 */
273
#if 0
274 275
	if (XfuncMode != XFUNC_OFF)
	{
276
		pathnode->path_cost += xfunc_get_path_cost(pathnode);
277
	}
278
#endif
279
	return pathnode;
280 281
}

282
/*
283
 * create_index_path--
284 285
 *	  Creates a single path node for an index scan.
 *
286 287 288 289
 * 'rel' is the parent rel
 * 'index' is the pathnode for the index on 'rel'
 * 'restriction-clauses' is a list of restriction clause nodes.
 * 'is-join-scan' is a flag indicating whether or not the index is being
290 291
 *		considered because of its sort order.
 *
292
 * Returns the new path node.
293
 *
294
 */
295
IndexPath  *
296
create_index_path(Query *root,
Bruce Momjian's avatar
Bruce Momjian committed
297 298
				  RelOptInfo *rel,
				  RelOptInfo *index,
299
				  List *restriction_clauses,
300
				  bool is_join_scan)
301
{
302
	IndexPath  *pathnode = makeNode(IndexPath);
303 304 305

	pathnode->path.pathtype = T_IndexScan;
	pathnode->path.parent = rel;
Bruce Momjian's avatar
Bruce Momjian committed
306 307 308
	pathnode->path.pathorder = makeNode(PathOrder);
	pathnode->path.pathorder->ordtype = SORTOP_ORDER;
	pathnode->path.pathorder->ord.sortop = index->ordering;
309 310 311 312 313

	pathnode->indexid = index->relids;
	pathnode->indexkeys = index->indexkeys;
	pathnode->indexqual = NIL;

314
	/*
315
	 * copy restrictinfo list into path for expensive function processing --
316
	 * JMH, 7/7/92
317
	 */
318
	pathnode->path.loc_restrictinfo = set_difference((List *) copyObject((Node *) rel->restrictinfo),
319
					   (List *) restriction_clauses);
320 321

	/*
322 323
	 * The index must have an ordering for the path to have (ordering)
	 * keys, and vice versa.
324
	 */
Bruce Momjian's avatar
Bruce Momjian committed
325
	if (pathnode->path.pathorder->ord.sortop)
326
	{
327
		pathnode->path.pathkeys = collect_index_pathkeys(index->indexkeys,
328 329 330 331 332 333 334 335
													 rel->targetlist);

		/*
		 * Check that the keys haven't 'disappeared', since they may no
		 * longer be in the target list (i.e., index keys that are not
		 * relevant to the scan are not applied to the scan path node, so
		 * if no index keys were found, we can't order the path).
		 */
336
		if (pathnode->path.pathkeys == NULL)
Bruce Momjian's avatar
Bruce Momjian committed
337
			pathnode->path.pathorder->ord.sortop = NULL;
338 339
	}
	else
340
		pathnode->path.pathkeys = NULL;
341 342 343 344 345 346 347 348 349 350

	if (is_join_scan || restriction_clauses == NULL)
	{

		/*
		 * Indices used for joins or sorting result nodes don't restrict
		 * the result at all, they simply order it, so compute the scan
		 * cost accordingly -- use a selectivity of 1.0.
		 */
/* is the statement above really true?	what about IndexScan as the
351
   inner of a join? */
352
		pathnode->path.path_cost = cost_index(lfirsti(index->relids),
353 354 355 356 357 358 359 360
					   index->pages,
					   1.0,
					   rel->pages,
					   rel->tuples,
					   index->pages,
					   index->tuples,
					   false);
		/* add in expensive functions cost!  -- JMH, 7/7/92 */
361
#if 0
362 363
		if (XfuncMode != XFUNC_OFF)
		{
364
			pathnode->path_cost = (pathnode->path_cost +
365 366
				 xfunc_get_path_cost((Path *) pathnode));
		}
367
#endif
368 369 370 371 372 373 374 375
	}
	else
	{

		/*
		 * Compute scan cost for the case when 'index' is used with a
		 * restriction clause.
		 */
376 377 378 379 380 381
		List	   *attnos;
		List	   *values;
		List	   *flags;
		float		npages;
		float		selec;
		Cost		clausesel;
382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398

		get_relattvals(restriction_clauses,
					   &attnos,
					   &values,
					   &flags);
		index_selectivity(lfirsti(index->relids),
						  index->classlist,
						  get_opnos(restriction_clauses),
						  getrelid(lfirsti(rel->relids),
								   root->rtable),
						  attnos,
						  values,
						  flags,
						  length(restriction_clauses),
						  &npages,
						  &selec);
		/* each clause gets an equal selectivity */
Bruce Momjian's avatar
Bruce Momjian committed
399
		clausesel =	pow(selec, 1.0 / (double) length(restriction_clauses));
400 401

		pathnode->indexqual = restriction_clauses;
Bruce Momjian's avatar
Bruce Momjian committed
402 403 404 405 406 407 408 409
		pathnode->path.path_cost = cost_index(lfirsti(index->relids),
											   (int) npages,
											   selec,
											   rel->pages,
											   rel->tuples,
											   index->pages,
											   index->tuples,
											   false);
410 411

#if 0
412 413 414
		/* add in expensive functions cost!  -- JMH, 7/7/92 */
		if (XfuncMode != XFUNC_OFF)
		{
415
			pathnode->path_cost += xfunc_get_path_cost((Path *) pathnode);
416
		}
417 418
#endif

419 420 421 422 423 424 425 426 427
		/*
		 * Set selectivities of clauses used with index to the selectivity
		 * of this index, subdividing the selectivity equally over each of
		 * the clauses.
		 */

		/* XXX Can this divide the selectivities in a better way? */
		set_clause_selectivities(restriction_clauses, clausesel);
	}
428
	return pathnode;
429 430
}

431
/*
432
 * create_nestloop_path--
433 434 435
 *	  Creates a pathnode corresponding to a nestloop join between two
 *	  relations.
 *
436 437 438 439
 * 'joinrel' is the join relation.
 * 'outer_rel' is the outer join relation
 * 'outer_path' is the outer join path.
 * 'inner_path' is the inner join path.
440
 * 'pathkeys' are the keys of the path
441
 *
442
 * Returns the resulting path node.
443
 *
444
 */
445
JoinPath   *
Bruce Momjian's avatar
Bruce Momjian committed
446 447
create_nestloop_path(RelOptInfo *joinrel,
					 RelOptInfo *outer_rel,
448 449
					 Path *outer_path,
					 Path *inner_path,
450
					 List *pathkeys)
451
{
452
	JoinPath   *pathnode = makeNode(JoinPath);
453 454 455 456 457

	pathnode->path.pathtype = T_NestLoop;
	pathnode->path.parent = joinrel;
	pathnode->outerjoinpath = outer_path;
	pathnode->innerjoinpath = inner_path;
458
	pathnode->pathinfo = joinrel->restrictinfo;
459
	pathnode->path.pathkeys = pathkeys;
460 461
	pathnode->path.joinid = NIL;
	pathnode->path.outerjoincost = (Cost) 0.0;
462
	pathnode->path.loc_restrictinfo = NIL;
Bruce Momjian's avatar
Bruce Momjian committed
463
	pathnode->path.pathorder = makeNode(PathOrder);
464
	
465
	if (pathkeys)
466
	{
Bruce Momjian's avatar
Bruce Momjian committed
467 468 469
		pathnode->path.pathorder->ordtype = outer_path->pathorder->ordtype;
		if (outer_path->pathorder->ordtype == SORTOP_ORDER)
			pathnode->path.pathorder->ord.sortop = outer_path->pathorder->ord.sortop;
470
		else
Bruce Momjian's avatar
Bruce Momjian committed
471
			pathnode->path.pathorder->ord.merge = outer_path->pathorder->ord.merge;
472
	}
473 474
	else
	{
Bruce Momjian's avatar
Bruce Momjian committed
475 476
		pathnode->path.pathorder->ordtype = SORTOP_ORDER;
		pathnode->path.pathorder->ord.sortop = NULL;
477 478
	}

479
	pathnode->path.path_cost = cost_nestloop(outer_path->path_cost,
480 481 482 483 484 485 486
					  inner_path->path_cost,
					  outer_rel->size,
					  inner_path->parent->size,
					  page_size(outer_rel->size,
								outer_rel->width),
					  IsA(inner_path, IndexPath));
	/* add in expensive function costs -- JMH 7/7/92 */
487
#if 0
488 489
	if (XfuncMode != XFUNC_OFF)
		pathnode->path_cost += xfunc_get_path_cost((Path *) pathnode);
490
#endif
491
	return pathnode;
492 493
}

494
/*
495 496
 * create_mergejoin_path--
 *	  Creates a pathnode corresponding to a mergejoin join between
497 498
 *	  two relations
 *
499 500 501 502 503 504 505
 * 'joinrel' is the join relation
 * 'outersize' is the number of tuples in the outer relation
 * 'innersize' is the number of tuples in the inner relation
 * 'outerwidth' is the number of bytes per tuple in the outer relation
 * 'innerwidth' is the number of bytes per tuple in the inner relation
 * 'outer_path' is the outer path
 * 'inner_path' is the inner path
506
 * 'pathkeys' are the new keys of the join relation
507 508 509 510
 * 'order' is the sort order required for the merge
 * 'mergeclauses' are the applicable join/restriction clauses
 * 'outersortkeys' are the sort varkeys for the outer relation
 * 'innersortkeys' are the sort varkeys for the inner relation
511
 *
512
 */
513
MergePath  *
Bruce Momjian's avatar
Bruce Momjian committed
514
create_mergejoin_path(RelOptInfo *joinrel,
515 516 517 518
					  int outersize,
					  int innersize,
					  int outerwidth,
					  int innerwidth,
519 520
					  Path *outer_path,
					  Path *inner_path,
521
					  List *pathkeys,
522 523 524 525
					  MergeOrder *order,
					  List *mergeclauses,
					  List *outersortkeys,
					  List *innersortkeys)
526
{
527
	MergePath  *pathnode = makeNode(MergePath);
528 529 530 531 532

	pathnode->jpath.path.pathtype = T_MergeJoin;
	pathnode->jpath.path.parent = joinrel;
	pathnode->jpath.outerjoinpath = outer_path;
	pathnode->jpath.innerjoinpath = inner_path;
533
	pathnode->jpath.pathinfo = joinrel->restrictinfo;
534
	pathnode->jpath.path.pathkeys = pathkeys;
Bruce Momjian's avatar
Bruce Momjian committed
535 536 537
	pathnode->jpath.path.pathorder = makeNode(PathOrder);
	pathnode->jpath.path.pathorder->ordtype = MERGE_ORDER;
	pathnode->jpath.path.pathorder->ord.merge = order;
538
	pathnode->path_mergeclauses = mergeclauses;
539
	pathnode->jpath.path.loc_restrictinfo = NIL;
540 541
	pathnode->outersortkeys = outersortkeys;
	pathnode->innersortkeys = innersortkeys;
542
	pathnode->jpath.path.path_cost = cost_mergejoin(outer_path->path_cost,
543 544 545 546 547 548 549 550
					   inner_path->path_cost,
					   outersortkeys,
					   innersortkeys,
					   outersize,
					   innersize,
					   outerwidth,
					   innerwidth);
	/* add in expensive function costs -- JMH 7/7/92 */
551
#if 0
552 553
	if (XfuncMode != XFUNC_OFF)
	{
554
		pathnode->path_cost += xfunc_get_path_cost((Path *) pathnode);
555
	}
556
#endif
557
	return pathnode;
558 559
}

560 561 562 563
/*
 * create_hashjoin_path--						XXX HASH
 *	  Creates a pathnode corresponding to a hash join between two relations.
 *
564 565 566 567 568 569 570
 * 'joinrel' is the join relation
 * 'outersize' is the number of tuples in the outer relation
 * 'innersize' is the number of tuples in the inner relation
 * 'outerwidth' is the number of bytes per tuple in the outer relation
 * 'innerwidth' is the number of bytes per tuple in the inner relation
 * 'outer_path' is the outer path
 * 'inner_path' is the inner path
571
 * 'pathkeys' are the new keys of the join relation
572 573 574 575
 * 'operator' is the hashjoin operator
 * 'hashclauses' are the applicable join/restriction clauses
 * 'outerkeys' are the sort varkeys for the outer relation
 * 'innerkeys' are the sort varkeys for the inner relation
576
 *
577
 */
578
HashPath   *
Bruce Momjian's avatar
Bruce Momjian committed
579
create_hashjoin_path(RelOptInfo *joinrel,
580 581 582 583
					 int outersize,
					 int innersize,
					 int outerwidth,
					 int innerwidth,
584 585
					 Path *outer_path,
					 Path *inner_path,
586
					 List *pathkeys,
587
					 Oid operator,
588 589 590
					 List *hashclauses,
					 List *outerkeys,
					 List *innerkeys)
591
{
592
	HashPath   *pathnode = makeNode(HashPath);
593 594 595 596 597

	pathnode->jpath.path.pathtype = T_HashJoin;
	pathnode->jpath.path.parent = joinrel;
	pathnode->jpath.outerjoinpath = outer_path;
	pathnode->jpath.innerjoinpath = inner_path;
598 599
	pathnode->jpath.pathinfo = joinrel->restrictinfo;
	pathnode->jpath.path.loc_restrictinfo = NIL;
600
	pathnode->jpath.path.pathkeys = pathkeys;
Bruce Momjian's avatar
Bruce Momjian committed
601 602 603
	pathnode->jpath.path.pathorder = makeNode(PathOrder);
	pathnode->jpath.path.pathorder->ordtype = SORTOP_ORDER;
	pathnode->jpath.path.pathorder->ord.sortop = NULL;
604 605 606 607 608 609
	pathnode->jpath.path.outerjoincost = (Cost) 0.0;
	pathnode->jpath.path.joinid = (Relid) NULL;
	/* pathnode->hashjoinoperator = operator;  */
	pathnode->path_hashclauses = hashclauses;
	pathnode->outerhashkeys = outerkeys;
	pathnode->innerhashkeys = innerkeys;
610
	pathnode->jpath.path.path_cost = cost_hashjoin(outer_path->path_cost,
611 612 613 614 615 616
					  inner_path->path_cost,
					  outerkeys,
					  innerkeys,
					  outersize, innersize,
					  outerwidth, innerwidth);
	/* add in expensive function costs -- JMH 7/7/92 */
617
#if 0
618 619
	if (XfuncMode != XFUNC_OFF)
	{
620
		pathnode->path_cost += xfunc_get_path_cost((Path *) pathnode);
621
	}
622
#endif
623
	return pathnode;
624
}