allpaths.c 8.52 KB
Newer Older
1 2
/*-------------------------------------------------------------------------
 *
3
 * allpaths.c
4
 *	  Routines to find possible search paths for processing a query
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/path/allpaths.c,v 1.41 1999/02/18 00:49:17 momjian Exp $
11 12 13 14
 *
 *-------------------------------------------------------------------------
 */
#include <string.h>
Marc G. Fournier's avatar
Marc G. Fournier committed
15
#include <stdio.h>
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

#include "postgres.h"

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

#include "optimizer/internal.h"

#include "optimizer/paths.h"
#include "optimizer/pathnode.h"
#include "optimizer/clauses.h"
#include "optimizer/xfunc.h"
#include "optimizer/cost.h"

#include "commands/creatinh.h"

Marc G. Fournier's avatar
Marc G. Fournier committed
33 34 35
#include "optimizer/geqo_gene.h"
#include "optimizer/geqo.h"

Vadim B. Mikheev's avatar
Vadim B. Mikheev committed
36
#ifdef GEQO
37
bool		_use_geqo_ = true;
38

Vadim B. Mikheev's avatar
Vadim B. Mikheev committed
39
#else
40
bool		_use_geqo_ = false;
41

Vadim B. Mikheev's avatar
Vadim B. Mikheev committed
42
#endif
43
int32		_use_geqo_rels_ = GEQO_RELS;
Vadim B. Mikheev's avatar
Vadim B. Mikheev committed
44 45


46 47 48
static void set_base_rel_pathlist(Query *root, List *rels);
static RelOptInfo *make_one_rel_by_joins(Query *root, List *rels,
										 int levels_needed);
49

50
#ifdef OPTIMIZER_DEBUG
Bruce Momjian's avatar
Bruce Momjian committed
51
static void debug_print_rel(Query *root, RelOptInfo *rel);
52

53
#endif
54

55
/*
56 57 58
 * make_one_rel
 *	  Finds all possible access paths for executing a query, returning a
 *	  single rel.
59
 *
60 61
 * 'rels' is the list of single relation entries appearing in the query
 */
62 63
RelOptInfo *
make_one_rel(Query *root, List *rels)
64
{
65
	int			levels_needed;
66

67
	/*
68
	 * Set the number of join (not nesting) levels yet to be processed.
69
	 */
70
	levels_needed = length(rels);
71

72
	if (levels_needed <= 0)
73
		return NULL;
74

75
	set_base_rel_pathlist(root, rels);
76

77
	if (levels_needed <= 1)
78 79 80 81
	{
		/*
		 * Unsorted single relation, no more processing is required.
		 */
82
		return lfirst(rels);
83 84 85 86
	}
	else
	{
		/*
87
		 * This means that joins or sorts are required. set selectivities
88 89 90 91
		 * of clauses that have not been set by an index.
		 */
		set_rest_relselec(root, rels);

92
		return make_one_rel_by_joins(root, rels, levels_needed);
93
	}
94 95
}

96
/*
97
 * set_base_rel_pathlist
98 99 100 101 102 103
 *	  Finds all paths available for scanning each relation entry in
 *	  'rels'.  Sequential scan and any available indices are considered
 *	  if possible(indices are not considered for lower nesting levels).
 *	  All unique paths are attached to the relation's 'pathlist' field.
 *
 *	  MODIFIES: rels
104 105
 */
static void
106
set_base_rel_pathlist(Query *root, List *rels)
107
{
108
	List	   *temp;
109 110 111

	foreach(temp, rels)
	{
112 113 114
		List	   *sequential_scan_list;
		List	   *rel_index_scan_list;
		List	   *or_index_scan_list;
Bruce Momjian's avatar
Bruce Momjian committed
115
		RelOptInfo *rel = (RelOptInfo *) lfirst(temp);
116

117
		sequential_scan_list = lcons(create_seqscan_path(rel), NIL);
118

Bruce Momjian's avatar
Bruce Momjian committed
119
		rel_index_scan_list = create_index_paths(root,
120
											   rel,
121
											   find_relation_indices(root, rel),
122
											   rel->restrictinfo,
123
											   rel->joininfo);
124

125
		or_index_scan_list = create_or_index_paths(root, rel, rel->restrictinfo);
126 127 128 129 130 131

		rel->pathlist = add_pathlist(rel,
									 sequential_scan_list,
									 append(rel_index_scan_list,
											or_index_scan_list));

132
		set_cheapest(rel, rel->pathlist);
133 134 135 136 137

		/*
		 * if there is a qualification of sequential scan the selec. value
		 * is not set -- so set it explicitly -- Sunita
		 */
138
		set_rest_selec(root, rel->restrictinfo);
139 140 141 142
		rel->size = compute_rel_size(rel);
		rel->width = compute_rel_width(rel);
	}
	return;
143 144
}

145
/*
146
 * make_one_rel_by_joins
147 148
 *	  Find all possible joinpaths for a query by successively finding ways
 *	  to join single relations into join relations.
149
 *
150 151 152 153
 *	  if BushyPlanFlag is set, bushy tree plans will be generated:
 *	  Find all possible joinpaths(bushy trees) for a query by systematically
 *	  finding ways to join relations(both original and derived) together.
 *
154
 * 'rels' is the current list of relations for which join paths
Bruce Momjian's avatar
Bruce Momjian committed
155
 *				are to be found, i.e., the current list of relations that
156
 *				have already been derived.
157
 * 'levels_needed' is the number of iterations needed
158
 *
159
 * Returns the final level of join relations, i.e., the relation that is
160
 * the result of joining all the original relations together.
161
 */
162
static RelOptInfo *
163
make_one_rel_by_joins(Query *root, List *rels, int levels_needed)
164
{
165
	List	   *x;
Bruce Momjian's avatar
Bruce Momjian committed
166
	List	   *joined_rels = NIL;
Bruce Momjian's avatar
Bruce Momjian committed
167
	RelOptInfo *rel;
168

169 170 171 172
	/*******************************************
	 * genetic query optimizer entry point	   *
	 *	  <utesch@aut.tu-freiberg.de>		   *
	 *******************************************/
Bruce Momjian's avatar
Bruce Momjian committed
173
	if ((_use_geqo_) && length(root->base_rel_list) >= _use_geqo_rels_)
174
		return geqo(root);
175
	
176 177 178
	/*******************************************
	 * rest will be deprecated in case of GEQO *
	 *******************************************/
179

180 181
	while (--levels_needed)
	{
182 183
		/*
		 * Determine all possible pairs of relations to be joined at this
184
		 * level.  Determine paths for joining these relation pairs and
Bruce Momjian's avatar
Bruce Momjian committed
185
		 * modify 'joined_rels' accordingly, then eliminate redundant join
186
		 * relations.
187
		 */
188
		joined_rels = make_rels_by_joins(root, rels);
189

Bruce Momjian's avatar
Bruce Momjian committed
190
		update_rels_pathlist_for_joins(root, joined_rels);
191

Bruce Momjian's avatar
Bruce Momjian committed
192
		merge_rels_with_same_relids(joined_rels);
193

Bruce Momjian's avatar
Bruce Momjian committed
194 195
		root->join_rel_list = rels = joined_rels;

196 197
#if 0
		/*
198 199
		 * * for each expensive predicate in each path in each distinct
		 * rel, * consider doing pullup  -- JMH
200
		 */
201
		if (XfuncMode != XFUNC_NOPULL && XfuncMode != XFUNC_OFF)
Bruce Momjian's avatar
Bruce Momjian committed
202
			foreach(x, joined_rels)
Bruce Momjian's avatar
Bruce Momjian committed
203
				xfunc_trypullup((RelOptInfo *) lfirst(x));
204
#endif
205

Bruce Momjian's avatar
Bruce Momjian committed
206
		rels_set_cheapest(joined_rels);
207

Bruce Momjian's avatar
Bruce Momjian committed
208
		foreach(x, joined_rels)
209
		{
Bruce Momjian's avatar
Bruce Momjian committed
210
			rel = (RelOptInfo *) lfirst(x);
Bruce Momjian's avatar
Bruce Momjian committed
211

212 213 214
			if (rel->size <= 0)
				rel->size = compute_rel_size(rel);
			rel->width = compute_rel_width(rel);
215

216
#ifdef OPTIMIZER_DEBUG
Bruce Momjian's avatar
Bruce Momjian committed
217
			printf("levels left: %d\n", levels_needed);
218
			debug_print_rel(root, rel);
219
#endif
220
		}
221

222
	}
223

224
	Assert(BushyPlanFlag || length(rels) == 1);
225

226 227
	if (!BushyPlanFlag)
		return lfirst(rels);
228
	else
229
		return get_cheapest_complete_rel(rels);
230 231 232 233 234 235
}

/*****************************************************************************
 *
 *****************************************************************************/

236
#ifdef OPTIMIZER_DEBUG
237
static void
238
print_joinclauses(Query *root, List *clauses)
239
{
240
	List	   *l;
241
	extern void print_expr(Node *expr, List *rtable);	/* in print.c */
242

243 244
	foreach(l, clauses)
	{
245
		RestrictInfo *c = lfirst(l);
246

247 248 249 250
		print_expr((Node *) c->clause, root->rtable);
		if (lnext(l))
			printf(" ");
	}
251 252
}

253
static void
254
print_path(Query *root, Path *path, int indent)
255
{
256
	char	   *ptype = NULL;
Bruce Momjian's avatar
Bruce Momjian committed
257
	JoinPath   *jp;
258 259
	bool		join = false;
	int			i;
260 261 262 263 264 265

	for (i = 0; i < indent; i++)
		printf("\t");

	switch (nodeTag(path))
	{
266 267 268 269 270 271 272 273
		case T_Path:
			ptype = "SeqScan";
			join = false;
			break;
		case T_IndexPath:
			ptype = "IdxScan";
			join = false;
			break;
274
		case T_NestPath:
275 276 277 278 279 280 281 282 283 284 285 286 287
			ptype = "Nestloop";
			join = true;
			break;
		case T_MergePath:
			ptype = "MergeJoin";
			join = true;
			break;
		case T_HashPath:
			ptype = "HashJoin";
			join = true;
			break;
		default:
			break;
288
	}
289 290
	if (join)
	{
291
		int			size = path->parent->size;
292

Bruce Momjian's avatar
Bruce Momjian committed
293
		jp = (JoinPath *) path;
294 295 296
		printf("%s size=%d cost=%f\n", ptype, size, path->path_cost);
		switch (nodeTag(path))
		{
297 298 299 300 301
			case T_MergePath:
			case T_HashPath:
				for (i = 0; i < indent + 1; i++)
					printf("\t");
				printf("   clauses=(");
Bruce Momjian's avatar
Bruce Momjian committed
302
				print_joinclauses(root, ((JoinPath *) path)->pathinfo);
303 304 305
				printf(")\n");

				if (nodeTag(path) == T_MergePath)
306
				{
307 308 309 310 311 312 313 314 315 316
					MergePath  *mp = (MergePath *) path;

					if (mp->outersortkeys || mp->innersortkeys)
					{
						for (i = 0; i < indent + 1; i++)
							printf("\t");
						printf("   sortouter=%d sortinner=%d\n",
							   ((mp->outersortkeys) ? 1 : 0),
							   ((mp->innersortkeys) ? 1 : 0));
					}
317
				}
318 319 320
				break;
			default:
				break;
321
		}
322 323 324 325 326
		print_path(root, jp->outerjoinpath, indent + 1);
		print_path(root, jp->innerjoinpath, indent + 1);
	}
	else
	{
327 328
		int			size = path->parent->size;
		int			relid = lfirsti(path->parent->relids);
329 330 331 332 333 334

		printf("%s(%d) size=%d cost=%f",
			   ptype, relid, size, path->path_cost);

		if (nodeTag(path) == T_IndexPath)
		{
335 336
			List	   *k,
					   *l;
337

338 339
			printf(" pathkeys=");
			foreach(k, path->pathkeys)
340 341 342 343
			{
				printf("(");
				foreach(l, lfirst(k))
				{
344
					Var		   *var = lfirst(l);
345 346 347 348 349 350 351 352 353 354 355

					printf("%d.%d", var->varnoold, var->varoattno);
					if (lnext(l))
						printf(", ");
				}
				printf(")");
				if (lnext(k))
					printf(", ");
			}
		}
		printf("\n");
356 357 358
	}
}

359
static void
Bruce Momjian's avatar
Bruce Momjian committed
360
debug_print_rel(Query *root, RelOptInfo *rel)
361
{
362
	List	   *l;
363 364 365 366 367 368 369 370 371 372 373

	printf("(");
	foreach(l, rel->relids)
		printf("%d ", lfirsti(l));
	printf("): size=%d width=%d\n", rel->size, rel->width);

	printf("\tpath list:\n");
	foreach(l, rel->pathlist)
		print_path(root, lfirst(l), 1);
	printf("\tcheapest path:\n");
	print_path(root, rel->cheapestpath, 1);
374
}
375

376
#endif	 /* OPTIMIZER_DEBUG */