initsplan.c 11.1 KB
Newer Older
1 2
/*-------------------------------------------------------------------------
 *
3
 * initsplan.c
4
 *	  Target list, qualification, joininfo initialization routines
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/plan/initsplan.c,v 1.28 1999/02/18 00:49:26 momjian Exp $
11 12 13
 *
 *-------------------------------------------------------------------------
 */
Marc G. Fournier's avatar
Marc G. Fournier committed
14 15
#include <sys/types.h>

16 17 18 19 20 21 22 23
#include "postgres.h"

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

24 25 26 27
#include "access/htup.h"

#include "catalog/pg_type.h"

28 29 30 31 32 33 34 35 36 37 38 39
#include "utils/lsyscache.h"
#include "utils/palloc.h"

#include "optimizer/internal.h"
#include "optimizer/planmain.h"
#include "optimizer/joininfo.h"
#include "optimizer/pathnode.h"
#include "optimizer/tlist.h"
#include "optimizer/var.h"
#include "optimizer/clauses.h"
#include "optimizer/cost.h"

40
extern int	Quiet;
41

42 43
static void add_restrict_and_join_to_rel(Query *root, List *clause);
static void add_join_info_to_rels(Query *root, RestrictInfo *restrictinfo,
Bruce Momjian's avatar
Bruce Momjian committed
44 45
					  Relids join_relids);
static void add_vars_to_targetlist(Query *root, List *vars, Relids join_relids);
46

47
static MergeOrder *mergejoinop(Expr *clause);
48
static Oid	hashjoinop(Expr *clause);
49 50 51 52


/*****************************************************************************
 *
53
 *	 TARGET LISTS
54 55 56
 *
 *****************************************************************************/

57
/*
58
 * make_var_only_tlist
59 60
 *	  Creates rel nodes for every relation mentioned in the target list
 *	  'tlist' (if a node hasn't already been created) and adds them to
61
 *	  *query_relation_list*.  Creates targetlist entries for each member of
62
 *	  'tlist' and adds them to the tlist field of the appropriate rel node.
63 64
 */
void
65
make_var_only_tlist(Query *root, List *tlist)
66
{
67 68 69
	List	   *tlist_vars = NIL;
	List	   *l = NIL;
	List	   *tvar = NIL;
70 71 72

	foreach(l, tlist)
	{
73
		TargetEntry *entry = (TargetEntry *) lfirst(l);
74 75 76 77 78 79 80

		tlist_vars = append(tlist_vars, pull_var_clause(entry->expr));
	}

	/* now, the target list only contains Var nodes */
	foreach(tvar, tlist_vars)
	{
81
		Var		   *var = (Var *) lfirst(tvar);
82
		Index		varno;
83
		RelOptInfo *result;
84 85 86 87

		varno = var->varno;
		result = get_base_rel(root, varno);

88
		add_var_to_tlist(result, var);
89
	}
90 91 92
}

/*
93
 * add_missing_vars_to_tlist
94 95 96 97 98
 *	  If we have range variable(s) in the FROM clause that does not appear
 *	  in the target list nor qualifications, we add it to the base relation
 *	  list. For instance, "select f.x from foo f, foo f2" is a join of f and
 *	  f2. Note that if we have "select foo.x from foo f", it also gets turned
 *	  into a join.
99 100
 */
void
101
add_missing_vars_to_tlist(Query *root, List *tlist)
102
{
103 104
	List	   *l;
	int			varno;
105 106 107 108

	varno = 1;
	foreach(l, root->rtable)
	{
109
		RangeTblEntry *rte = (RangeTblEntry *) lfirst(l);
Bruce Momjian's avatar
Bruce Momjian committed
110
		Relids		relids;
111
		RelOptInfo *result;
112
		Var		   *var;
113 114

		relids = lconsi(varno, NIL);
115
		if (rte->inFromCl && !rel_member(relids, root->base_rel_list))
116
		{
117 118 119
			var = makeVar(varno, ObjectIdAttributeNumber,
						  OIDOID, -1, 0, varno, ObjectIdAttributeNumber);
			/* add it to base_rel_list */
120
			result = get_base_rel(root, varno);
121
			add_var_to_tlist(result, var);
122 123 124
		}
		pfree(relids);
		varno++;
125 126
	}

127
	return;
128 129 130 131
}

/*****************************************************************************
 *
132
 *	  QUALIFICATIONS
133 134 135 136 137
 *
 *****************************************************************************/



138
/*
139
 * add_restrict_and_join_to_rels-
140
 *	  Initializes RestrictInfo and JoinInfo fields of relation entries for all
141
 *	  relations appearing within clauses.  Creates new relation entries if
142
 *	  necessary, adding them to *query_relation_list*.
143 144
 *
 *	  Returns nothing of interest.
145 146
 */
void
147
add_restrict_and_join_to_rels(Query *root, List *clauses)
148
{
149
	List	   *clause;
150

151
	foreach(clause, clauses)
152
		add_restrict_and_join_to_rel(root, lfirst(clause));
153
	return;
154 155
}

156
/*
157
 * add_restrict_and_join_to_rel-
158
 *	  Add clause information to either the 'RestrictInfo' or 'JoinInfo' field
159
 *	  of a relation entry(depending on whether or not the clause is a join)
160
 *	  by creating a new RestrictInfo node and setting appropriate fields
161 162 163
 *	  within the nodes.
 *
 *	  Returns nothing of interest.
164 165
 */
static void
166
add_restrict_and_join_to_rel(Query *root, List *clause)
167
{
Bruce Momjian's avatar
Bruce Momjian committed
168
	Relids		relids;
169
	List	   *vars;
170
	RestrictInfo *restrictinfo = makeNode(RestrictInfo);
171

172 173 174
	/*
	 * Retrieve all relids and vars contained within the clause.
	 */
Bruce Momjian's avatar
Bruce Momjian committed
175
	clause_get_relids_vars((Node *) clause, &relids, &vars);
176

177 178 179 180 181 182
	restrictinfo->clause = (Expr *) clause;
	restrictinfo->notclause = contains_not((Node *) clause);
	restrictinfo->selectivity = 0;
	restrictinfo->indexids = NIL;
	restrictinfo->mergejoinorder = (MergeOrder *) NULL;
	restrictinfo->hashjoinoperator = (Oid) 0;
183

184 185
	if (length(relids) == 1)
	{
186
		/*
187 188
		 * There is only one relation participating in 'clause', so
		 * 'clause' must be a restriction clause.
189
		 */
190
		RelOptInfo *rel = get_base_rel(root, lfirsti(relids));
191

192
		/*
193
		 * The selectivity of the clause must be computed regardless of
194
		 * whether it's a restriction or a join clause
195
		 */
196
		if (is_funcclause((Node *) clause))
197

198 199 200 201
			/*
			 * XXX If we have a func clause set selectivity to 1/3, really
			 * need a true selectivity function.
			 */
202
			restrictinfo->selectivity = (Cost) 0.3333333;
203
		else
204
			restrictinfo->selectivity = compute_clause_selec(root, (Node *) clause, NIL);
205

206
		rel->restrictinfo = lcons(restrictinfo, rel->restrictinfo);
207
	}
208
	else
209 210 211 212 213 214 215 216 217 218
	{
		/*
		 * 'clause' is a join clause, since there is more than one atom in
		 * the relid list.
		 */
		if (is_funcclause((Node *) clause))
			/*
			 * XXX If we have a func clause set selectivity to 1/3, really
			 * need a true selectivity function.
			 */
219
			restrictinfo->selectivity = (Cost) 0.3333333;
220
		else
221
			restrictinfo->selectivity = compute_clause_selec(root, (Node *) clause, NIL);
222

223
		add_join_info_to_rels(root, restrictinfo, relids);
224 225
		/* we are going to be doing a join, so add var to targetlist */
		add_vars_to_targetlist(root, vars, relids);
226
	}
227 228
}

229
/*
230
 * add_join_info_to_rels
231
 *	  For every relation participating in a join clause, add 'restrictinfo' to
232 233 234
 *	  the appropriate joininfo node(creating a new one and adding it to the
 *	  appropriate rel node if necessary).
 *
235
 * 'restrictinfo' describes the join clause
236
 * 'join_relids' is the list of relations participating in the join clause
237
 *
238 239
 */
static void
Bruce Momjian's avatar
Bruce Momjian committed
240 241
add_join_info_to_rels(Query *root, RestrictInfo *restrictinfo,
						Relids join_relids)
242
{
243
	List	   *join_relid;
244

Bruce Momjian's avatar
Bruce Momjian committed
245
	/* For every relid, find the rel, and add the proper join entries */
246 247
	foreach(join_relid, join_relids)
	{
248
		JoinInfo   *joininfo;
Bruce Momjian's avatar
Bruce Momjian committed
249 250
		Relids		unjoined_relids = NIL;
		List 		*rel;
251

Bruce Momjian's avatar
Bruce Momjian committed
252
		/* Get the relids not equal to the current relid */
253 254 255
		foreach(rel, join_relids)
		{
			if (lfirsti(rel) != lfirsti(join_relid))
Bruce Momjian's avatar
Bruce Momjian committed
256
				unjoined_relids = lappendi(unjoined_relids, lfirsti(rel));
257 258
		}

259
		joininfo = find_joininfo_node(get_base_rel(root, lfirsti(join_relid)),
Bruce Momjian's avatar
Bruce Momjian committed
260
									  unjoined_relids);
261 262
		joininfo->jinfo_restrictinfo = lcons(copyObject((void *) restrictinfo),
											 joininfo->jinfo_restrictinfo);
263
	}
264 265
}

266
/*
267
 * add_vars_to_targetlist
268 269 270 271 272 273 274 275
 *	  For each variable appearing in a clause,
 *	  (1) If a targetlist entry for the variable is not already present in
 *		  the appropriate relation's target list, add one.
 *	  (2) If a targetlist entry is already present, but the var is part of a
 *		  join clause, add the relids of the join relations to the JoinList
 *		  entry of the targetlist entry.
 *
 *	  'vars' is the list of var nodes
276
 *	  'join_relids' is the list of relids appearing in the join clause
277 278 279
 *		(if this is a join clause)
 *
 *	  Returns nothing.
280 281
 */
static void
Bruce Momjian's avatar
Bruce Momjian committed
282
add_vars_to_targetlist(Query *root, List *vars, Relids join_relids)
283
{
284 285
	Var		   *var;
	List	   *temp = NIL;
286
	RelOptInfo *rel = (RelOptInfo *) NULL;
287
	TargetEntry *tlistentry;
288 289 290 291 292 293 294 295

	foreach(temp, vars)
	{
		var = (Var *) lfirst(temp);
		rel = get_base_rel(root, var->varno);
		tlistentry = tlistentry_member(var, rel->targetlist);
		if (tlistentry == NULL)
			/* add a new entry */
296
			add_var_to_tlist(rel, var);
297
	}
298 299 300 301
}

/*****************************************************************************
 *
302
 *	 JOININFO
303 304 305
 *
 *****************************************************************************/

306
/*
Bruce Momjian's avatar
Bruce Momjian committed
307
 * set_joininfo_mergeable_hashable
308
 *	  Set the MergeJoinable or HashJoinable field for every joininfo node
Bruce Momjian's avatar
Bruce Momjian committed
309
 *	  (within a rel node) and the mergejoinorder or hashjoinop field for
310
 *	  each restrictinfo node(within a joininfo node) for all relations in a
311 312 313
 *	  query.
 *
 *	  Returns nothing.
314 315
 */
void
Bruce Momjian's avatar
Bruce Momjian committed
316
set_joininfo_mergeable_hashable(List *rel_list)
317
{
318 319 320
	List	   *x,
			   *y,
			   *z;
321
	RelOptInfo *rel;
322
	JoinInfo   *joininfo;
323
	RestrictInfo *restrictinfo;
324
	Expr	   *clause;
325 326 327

	foreach(x, rel_list)
	{
Bruce Momjian's avatar
Bruce Momjian committed
328
		rel = (RelOptInfo *) lfirst(x);
329 330
		foreach(y, rel->joininfo)
		{
331
			joininfo = (JoinInfo *) lfirst(y);
332
			foreach(z, joininfo->jinfo_restrictinfo)
333
			{
334 335
				restrictinfo = (RestrictInfo *) lfirst(z);
				clause = restrictinfo->clause;
336
				if (is_joinable((Node *) clause))
337
				{
338 339
					MergeOrder *sortop = (MergeOrder *) NULL;
					Oid			hashop = (Oid) NULL;
340

341 342
					if (_enable_mergejoin_)
						sortop = mergejoinop(clause);
343 344
					if (sortop)
					{
345
						restrictinfo->mergejoinorder = sortop;
346
						joininfo->mergejoinable = true;
347
					}
348 349 350

					if (_enable_hashjoin_)
						hashop = hashjoinop(clause);
351 352
					if (hashop)
					{
353
						restrictinfo->hashjoinoperator = hashop;
354 355 356 357
						joininfo->hashjoinable = true;
					}
				}
			}
358 359 360 361
		}
	}
}

362
/*
363
 * mergejoinop
364 365 366
 *	  Returns the mergejoin operator of an operator iff 'clause' is
 *	  mergejoinable, i.e., both operands are single vars and the operator is
 *	  a mergejoinable operator.
367 368
 */
static MergeOrder *
369
mergejoinop(Expr *clause)
370
{
371 372 373 374
	Var		   *left,
			   *right;
	Oid			opno,
				leftOp,
375 376
				rightOp;
	bool		sortable;
377

378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394
	if (!is_opclause((Node*) clause))
		return NULL;

	left = get_leftop(clause);
	right = get_rightop(clause);

	/* caution: is_opclause accepts more than I do, so check it */
	if (!right)
		return NULL;			/* unary opclauses need not apply */
	if (!IsA(left, Var) || !IsA(right, Var))
		return NULL;

	opno = ((Oper *) clause->oper)->opno;

	sortable = op_mergejoinable(opno,
								left->vartype,
								right->vartype,
395 396 397 398 399
								&leftOp,
								&rightOp);

	if (sortable)
	{
400
		MergeOrder *morder = makeNode(MergeOrder);
401

402
		morder->join_operator = opno;
403 404
		morder->left_operator = leftOp;
		morder->right_operator = rightOp;
405 406
		morder->left_type = left->vartype;
		morder->right_type = right->vartype;
407
		return morder;
408 409
	}
	else
410
		return NULL;
411 412
}

413
/*
414
 * hashjoinop
415 416 417
 *	  Returns the hashjoin operator of an operator iff 'clause' is
 *	  hashjoinable, i.e., both operands are single vars and the operator is
 *	  a hashjoinable operator.
418
 */
419
static Oid
420
hashjoinop(Expr *clause)
421
{
422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439
	Var		   *left,
			   *right;

	if (!is_opclause((Node*) clause))
		return InvalidOid;

	left = get_leftop(clause);
	right = get_rightop(clause);

	/* caution: is_opclause accepts more than I do, so check it */
	if (!right)
		return InvalidOid;		/* unary opclauses need not apply */
	if (!IsA(left, Var) || !IsA(right, Var))
		return InvalidOid;

	return op_hashjoinable(((Oper *) clause->oper)->opno,
						   left->vartype,
						   right->vartype);
440
}