pathnode.c 10.3 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
10
 *	  $Header: /cvsroot/pgsql/src/backend/optimizer/util/pathnode.c,v 1.57 2000/01/22 23:50:17 tgl Exp $
11 12 13 14 15 16 17 18
 *
 *-------------------------------------------------------------------------
 */
#include <math.h>

#include "postgres.h"

#include "optimizer/cost.h"
Bruce Momjian's avatar
Bruce Momjian committed
19
#include "optimizer/pathnode.h"
20
#include "optimizer/paths.h"
Bruce Momjian's avatar
Bruce Momjian committed
21 22
#include "optimizer/plancat.h"
#include "optimizer/restrictinfo.h"
Bruce Momjian's avatar
Bruce Momjian committed
23
#include "parser/parsetree.h"
24 25 26


/*****************************************************************************
27
 *		MISC. PATH UTILITIES
28 29
 *****************************************************************************/

30
/*
31
 * path_is_cheaper
32 33
 *	  Returns t iff 'path1' is cheaper than 'path2'.
 *
34 35
 */
bool
36
path_is_cheaper(Path *path1, Path *path2)
37
{
38
	return (bool) (path1->path_cost < path2->path_cost);
39 40
}

41
/*
42
 * set_cheapest
43 44
 *	  Finds the minimum cost path from among a relation's paths.
 *
45 46
 * 'parent_rel' is the parent relation
 * 'pathlist' is a list of path nodes corresponding to 'parent_rel'
47 48
 *
 * Returns and sets the relation entry field with the pathnode that
49
 * is minimum.
50
 *
51
 */
52
Path *
53
set_cheapest(RelOptInfo *parent_rel, List *pathlist)
54
{
55 56
	List	   *p;
	Path	   *cheapest_so_far;
57

Bruce Momjian's avatar
Bruce Momjian committed
58
	Assert(IsA(parent_rel, RelOptInfo));
59
	Assert(pathlist != NIL);
60

61
	cheapest_so_far = (Path *) lfirst(pathlist);
62

63 64
	foreach(p, lnext(pathlist))
	{
65
		Path	   *path = (Path *) lfirst(p);
66

67 68
		if (path_is_cheaper(path, cheapest_so_far))
			cheapest_so_far = path;
69 70
	}

71
	parent_rel->cheapestpath = cheapest_so_far;
72

73
	return cheapest_so_far;
74 75
}

76
/*
77
 * add_pathlist
78 79 80 81
 *	  Construct an output path list by adding to old_paths each path in
 *	  new_paths that is worth considering --- that is, it has either a
 *	  better sort order (better pathkeys) or cheaper cost than any of the
 *	  existing old paths.
82
 *
83 84 85
 *	  Unless parent_rel->pruneable is false, we also remove from the output
 *	  pathlist any old paths that are dominated by added path(s) --- that is,
 *	  some new path is both cheaper and at least as well ordered.
86
 *
87 88
 *	  Note: the list old_paths is destructively modified, and in fact is
 *	  turned into the output list.
89
 *
90 91 92 93 94
 * 'parent_rel' is the relation entry to which these paths correspond.
 * 'old_paths' is the list of previously accepted paths for parent_rel.
 * 'new_paths' is a list of potential new paths.
 *
 * Returns the updated list of interesting pathnodes.
95
 */
96
List *
97
add_pathlist(RelOptInfo *parent_rel, List *old_paths, List *new_paths)
98
{
Bruce Momjian's avatar
Bruce Momjian committed
99
	List	   *p1;
100

Bruce Momjian's avatar
Bruce Momjian committed
101
	foreach(p1, new_paths)
102
	{
Bruce Momjian's avatar
Bruce Momjian committed
103
		Path	   *new_path = (Path *) lfirst(p1);
104 105 106
		bool		accept_new = true; /* unless we find a superior old path */
		List	   *p2_prev = NIL;
		List	   *p2;
107

108 109 110 111 112 113
		/*
		 * Loop to check proposed new path against old paths.  Note it is
		 * possible for more than one old path to be tossed out because
		 * new_path dominates it.
		 */
		foreach(p2, old_paths)
114
		{
115 116
			Path	   *old_path = (Path *) lfirst(p2);
			bool		remove_old = false;	/* unless new proves superior */
117

118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137
			switch (compare_pathkeys(new_path->pathkeys, old_path->pathkeys))
			{
				case PATHKEYS_EQUAL:
					if (new_path->path_cost < old_path->path_cost)
						remove_old = true; /* new dominates old */
					else
						accept_new = false;	/* old equals or dominates new */
					break;
				case PATHKEYS_BETTER1:
					if (new_path->path_cost <= old_path->path_cost)
						remove_old = true; /* new dominates old */
					break;
				case PATHKEYS_BETTER2:
					if (new_path->path_cost >= old_path->path_cost)
						accept_new = false;	/* old dominates new */
					break;
				case PATHKEYS_DIFFERENT:
					/* keep both paths, since they have different ordering */
					break;
			}
Bruce Momjian's avatar
Bruce Momjian committed
138

Bruce Momjian's avatar
Bruce Momjian committed
139
			/*
140 141
			 * Remove current element from old_list if dominated by new,
			 * unless xfunc told us not to remove any paths.
Bruce Momjian's avatar
Bruce Momjian committed
142
			 */
143
			if (remove_old && parent_rel->pruneable)
144
			{
145 146 147 148
				if (p2_prev)
					lnext(p2_prev) = lnext(p2);
				else
					old_paths = lnext(p2);
Bruce Momjian's avatar
Bruce Momjian committed
149
			}
150 151
			else
				p2_prev = p2;
Bruce Momjian's avatar
Bruce Momjian committed
152

153 154 155 156 157 158 159 160
			/*
			 * If we found an old path that dominates new_path, we can quit
			 * scanning old_paths; we will not add new_path, and we assume
			 * new_path cannot dominate any other elements of old_paths.
			 */
			if (! accept_new)
				break;
		}
Bruce Momjian's avatar
Bruce Momjian committed
161

162 163 164 165 166 167 168
		if (accept_new)
		{
			/* Accept the path.  Note that it will now be eligible to be
			 * compared against the additional elements of new_paths...
			 */
			new_path->parent = parent_rel; /* not redundant, see prune.c */
			old_paths = lcons(new_path, old_paths);
169
		}
170
	}
171

172
	return old_paths;
173 174 175 176
}


/*****************************************************************************
177
 *		PATH NODE CREATION ROUTINES
178 179
 *****************************************************************************/

180
/*
181
 * create_seqscan_path
182 183 184
 *	  Creates a path corresponding to a sequential scan, returning the
 *	  pathnode.
 *
185
 */
186
Path *
187
create_seqscan_path(RelOptInfo *rel)
188
{
189
	Path	   *pathnode = makeNode(Path);
190 191 192

	pathnode->pathtype = T_SeqScan;
	pathnode->parent = rel;
193
	pathnode->pathkeys = NIL;	/* seqscan has unordered result */
194
	pathnode->path_cost = cost_seqscan(rel);
195

196
	return pathnode;
197 198
}

199
/*
200
 * create_index_path
201
 *	  Creates a path node for an index scan.
202
 *
203
 * 'rel' is the parent rel
204 205 206
 * 'index' is an index on 'rel'
 * 'restriction_clauses' is a list of RestrictInfo nodes
 *			to be used as index qual conditions in the scan.
207
 *
208 209
 * Returns the new path node.
 */
210
IndexPath  *
211
create_index_path(Query *root,
212
				  RelOptInfo *rel,
213
				  IndexOptInfo *index,
214
				  List *restriction_clauses)
215
{
216
	IndexPath  *pathnode = makeNode(IndexPath);
217
	List	   *indexquals;
218 219 220

	pathnode->path.pathtype = T_IndexScan;
	pathnode->path.parent = rel;
221
	pathnode->path.pathkeys = build_index_pathkeys(root, rel, index);
222

223 224 225 226
	indexquals = get_actual_clauses(restriction_clauses);
	/* expand special operators to indexquals the executor can handle */
	indexquals = expand_indexqual_conditions(indexquals);

227
	/*
228 229
	 * We are making a pathnode for a single-scan indexscan; therefore,
	 * both indexid and indexqual should be single-element lists.
230
	 */
231
	pathnode->indexid = lconsi(index->indexoid, NIL);
232
	pathnode->indexqual = lcons(indexquals, NIL);
233
	pathnode->joinrelids = NIL;	/* no join clauses here */
234

235 236
	pathnode->path.path_cost = cost_index(root, rel, index, indexquals,
										  false);
237

238
	return pathnode;
239 240
}

241 242 243 244 245 246 247 248 249 250 251 252 253 254
/*
 * create_tidscan_path
 *	  Creates a path corresponding to a tid_direct scan, returning the
 *	  pathnode.
 *
 */
TidPath *
create_tidscan_path(RelOptInfo *rel, List *tideval)
{
	TidPath	*pathnode = makeNode(TidPath);

	pathnode->path.pathtype = T_TidScan;
	pathnode->path.parent = rel;
	pathnode->path.pathkeys = NIL;
255
	pathnode->path.path_cost = cost_tidscan(rel, tideval);
256 257 258
	/* divide selectivity for each clause to get an equal selectivity
	 * as IndexScan does OK ? 
	*/
259
	pathnode->tideval = copyObject(tideval); /* is copy really necessary? */
260 261 262 263 264
	pathnode->unjoined_relids = NIL;

	return pathnode;
}

265
/*
266
 * create_nestloop_path
267 268 269
 *	  Creates a pathnode corresponding to a nestloop join between two
 *	  relations.
 *
270
 * 'joinrel' is the join relation.
271 272 273
 * 'outer_path' is the outer path
 * 'inner_path' is the inner path
 * 'pathkeys' are the path keys of the new join path
274
 *
275
 * Returns the resulting path node.
276
 *
277
 */
278
NestPath   *
279
create_nestloop_path(RelOptInfo *joinrel,
280 281
					 Path *outer_path,
					 Path *inner_path,
282
					 List *pathkeys)
283
{
284
	NestPath   *pathnode = makeNode(NestPath);
285 286 287 288 289

	pathnode->path.pathtype = T_NestLoop;
	pathnode->path.parent = joinrel;
	pathnode->outerjoinpath = outer_path;
	pathnode->innerjoinpath = inner_path;
290
	pathnode->path.pathkeys = pathkeys;
291

292 293
	pathnode->path.path_cost = cost_nestloop(outer_path,
											 inner_path,
Bruce Momjian's avatar
Bruce Momjian committed
294
											 IsA(inner_path, IndexPath));
295

296
	return pathnode;
297 298
}

299
/*
300
 * create_mergejoin_path
301
 *	  Creates a pathnode corresponding to a mergejoin join between
302 303
 *	  two relations
 *
304 305 306
 * 'joinrel' is the join relation
 * 'outer_path' is the outer path
 * 'inner_path' is the inner path
307
 * 'pathkeys' are the path keys of the new join path
308 309 310
 * '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
311
 *
312
 */
313
MergePath  *
314
create_mergejoin_path(RelOptInfo *joinrel,
315 316
					  Path *outer_path,
					  Path *inner_path,
317
					  List *pathkeys,
318 319 320
					  List *mergeclauses,
					  List *outersortkeys,
					  List *innersortkeys)
321
{
322
	MergePath  *pathnode = makeNode(MergePath);
323

324 325 326 327 328 329 330 331 332 333 334
	/*
	 * If the given paths are already well enough ordered, we can skip
	 * doing an explicit sort.
	 */
	if (outersortkeys &&
		pathkeys_contained_in(outersortkeys, outer_path->pathkeys))
		outersortkeys = NIL;
	if (innersortkeys &&
		pathkeys_contained_in(innersortkeys, inner_path->pathkeys))
		innersortkeys = NIL;

335 336 337 338
	pathnode->jpath.path.pathtype = T_MergeJoin;
	pathnode->jpath.path.parent = joinrel;
	pathnode->jpath.outerjoinpath = outer_path;
	pathnode->jpath.innerjoinpath = inner_path;
339
	pathnode->jpath.path.pathkeys = pathkeys;
340 341 342
	pathnode->path_mergeclauses = mergeclauses;
	pathnode->outersortkeys = outersortkeys;
	pathnode->innersortkeys = innersortkeys;
343 344
	pathnode->jpath.path.path_cost = cost_mergejoin(outer_path,
													inner_path,
Bruce Momjian's avatar
Bruce Momjian committed
345
													outersortkeys,
346
													innersortkeys);
347

348
	return pathnode;
349 350
}

351
/*
352
 * create_hashjoin_path
353 354
 *	  Creates a pathnode corresponding to a hash join between two relations.
 *
355
 * 'joinrel' is the join relation
356 357 358 359
 * 'outer_path' is the cheapest outer path
 * 'inner_path' is the cheapest inner path
 * 'hashclauses' is a list of the hash join clause (always a 1-element list)
 * 'innerdisbursion' is an estimate of the disbursion of the inner hash key
360
 *
361
 */
362
HashPath *
363
create_hashjoin_path(RelOptInfo *joinrel,
364 365 366
					 Path *outer_path,
					 Path *inner_path,
					 List *hashclauses,
367
					 Selectivity innerdisbursion)
368
{
369
	HashPath   *pathnode = makeNode(HashPath);
370 371 372 373 374

	pathnode->jpath.path.pathtype = T_HashJoin;
	pathnode->jpath.path.parent = joinrel;
	pathnode->jpath.outerjoinpath = outer_path;
	pathnode->jpath.innerjoinpath = inner_path;
375 376
	/* A hashjoin never has pathkeys, since its ordering is unpredictable */
	pathnode->jpath.path.pathkeys = NIL;
377
	pathnode->path_hashclauses = hashclauses;
378 379
	pathnode->jpath.path.path_cost = cost_hashjoin(outer_path,
												   inner_path,
380
												   innerdisbursion);
381

382
	return pathnode;
383
}