joinrels.c 8.29 KB
Newer Older
1 2
/*-------------------------------------------------------------------------
 *
3
 * joinrels.c
4
 *	  Routines to determine which relations should be joined
5
 *
Bruce Momjian's avatar
Add:  
Bruce Momjian committed
6 7
 * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
 * Portions Copyright (c) 1994, Regents of the University of California
8 9 10
 *
 *
 * IDENTIFICATION
11
 *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/joinrels.c,v 1.43 2000/02/07 04:40:59 tgl Exp $
12 13 14 15 16 17 18 19
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "optimizer/cost.h"
#include "optimizer/joininfo.h"
#include "optimizer/pathnode.h"
Bruce Momjian's avatar
Bruce Momjian committed
20 21
#include "optimizer/paths.h"
#include "optimizer/tlist.h"
22

23 24 25 26

static RelOptInfo *make_join_rel(Query *root, RelOptInfo *rel1,
								 RelOptInfo *rel2);

27 28

/*
29
 * make_rels_by_joins
30 31 32 33 34 35
 *	  Consider ways to produce join relations containing exactly 'level'
 *	  base relations.  (This is one step of the dynamic-programming method
 *	  embodied in make_one_rel_by_joins.)  Join rel nodes for each feasible
 *	  combination of base rels are created and added to the front of the
 *	  query's join_rel_list.  Implementation paths are created for each
 *	  such joinrel, too.
36
 *
37
 * Returns nothing, but adds entries to root->join_rel_list.
38
 */
39 40
void
make_rels_by_joins(Query *root, int level)
41
{
42
	List	   *r;
43

44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65
	/*
	 * First, consider left-sided and right-sided plans, in which rels of
	 * exactly level-1 member relations are joined against base relations.
	 * We prefer to join using join clauses, but if we find a rel of level-1
	 * members that has no join clauses, we will generate Cartesian-product
	 * joins against all base rels not already contained in it.
	 *
	 * In the first pass (level == 2), we try to join each base rel to each
	 * base rel that appears later in base_rel_list.  (The mirror-image
	 * joins are handled automatically by make_join_rel.)  In later passes,
	 * we try to join rels of size level-1 from join_rel_list to each
	 * base rel in base_rel_list.
	 *
	 * We assume that the rels already present in join_rel_list appear in
	 * decreasing order of level (number of members).  This should be true
	 * since we always add new higher-level rels to the front of the list.
	 */
	if (level == 2)
		r = root->base_rel_list;	/* level-1 is base rels */
	else
		r = root->join_rel_list;
	for (; r != NIL; r = lnext(r))
66
	{
Bruce Momjian's avatar
Bruce Momjian committed
67
		RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);
68 69 70 71 72
		int			old_level = length(old_rel->relids);
		List	   *other_rels;

		if (old_level != level-1)
			break;
73

74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91
		if (level == 2)
			other_rels = lnext(r); /* only consider remaining base rels */
		else
			other_rels = root->base_rel_list; /* consider all base rels */

		if (old_rel->joininfo != NIL)
		{
			/*
			 * Note that if all available join clauses for this rel require
			 * more than one other rel, we will fail to make any joins against
			 * it here.  That's OK; it'll be considered by "bushy plan" join
			 * code in a higher-level pass.
			 */
			make_rels_by_clause_joins(root,
									  old_rel,
									  other_rels);
		}
		else
92
		{
Bruce Momjian's avatar
Bruce Momjian committed
93 94 95 96
			/*
			 * Oops, we have a relation that is not joined to any other
			 * relation.  Cartesian product time.
			 */
97 98 99
			make_rels_by_clauseless_joins(root,
										  old_rel,
										  other_rels);
100
		}
101 102
	}

103 104 105 106 107 108 109 110 111 112
	/*
	 * Now, consider "bushy plans" in which relations of k base rels are
	 * joined to relations of level-k base rels, for 2 <= k <= level-2.
	 * The previous loop left r pointing to the first rel of level level-2.
	 *
	 * We only consider bushy-plan joins for pairs of rels where there is
	 * a suitable join clause, in order to avoid unreasonable growth of
	 * planning time.
	 */
	for (; r != NIL; r = lnext(r))
Bruce Momjian's avatar
Bruce Momjian committed
113
	{
114 115 116
		RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);
		int			old_level = length(old_rel->relids);
		List	   *r2;
117

118 119 120 121 122
		/* We can quit once past the halfway point (make_join_rel took care
		 * of making the opposite-direction joins)
		 */
		if (old_level * 2 < level)
			break;
123

124 125
		if (old_rel->joininfo == NIL)
			continue;			/* we ignore clauseless joins here */
126

127
		foreach(r2, lnext(r))
128
		{
129 130 131 132 133 134 135 136
			RelOptInfo *new_rel = (RelOptInfo *) lfirst(r2);
			int			new_level = length(new_rel->relids);

			if (old_level + new_level > level)
				continue;		/* scan down to new_rels of right size */
			if (old_level + new_level < level)
				break;			/* no more new_rels of right size */
			if (nonoverlap_setsi(old_rel->relids, new_rel->relids))
Bruce Momjian's avatar
Bruce Momjian committed
137
			{
138
				List	   *i;
Bruce Momjian's avatar
Bruce Momjian committed
139

140 141 142 143
				/* OK, we can build a rel of the right level from this pair of
				 * rels.  Do so if there is at least one usable join clause.
				 */
				foreach(i, old_rel->joininfo)
Bruce Momjian's avatar
Bruce Momjian committed
144
				{
145 146 147 148 149 150 151
					JoinInfo   *joininfo = (JoinInfo *) lfirst(i);

					if (is_subseti(joininfo->unjoined_relids, new_rel->relids))
					{
						make_join_rel(root, old_rel, new_rel);
						break;
					}
152 153 154
				}
			}
		}
155 156 157
	}
}

158
/*
159 160 161 162 163 164 165 166 167 168 169 170 171 172
 * make_rels_by_clause_joins
 *	  Build joins between the given relation 'old_rel' and other relations
 *	  that are mentioned within old_rel's joininfo nodes (i.e., relations
 *	  that participate in join clauses that 'old_rel' also participates in).
 *	  The join rel nodes are added to root->join_rel_list.
 *
 * 'old_rel' is the relation entry for the relation to be joined
 * 'other_rels': other rels to be considered for joining
 *
 * Currently, this is only used with base rels in other_rels, but it would
 * work for joining to joinrels too, if the caller ensures there is no
 * membership overlap between old_rel and the rels in other_rels.  (We need
 * no extra test for overlap for base rels, since the is_subset test can
 * only succeed when other_rel is not already part of old_rel.)
173
 *
174 175 176 177
 * Returns NULL if no suitable joins were found, else the last suitable
 * joinrel processed.  (The only caller who checks the return value is
 * geqo_eval.c, and it sets things up so there can be no more than one
 * "suitable" joinrel; so we don't bother with returning a list.)
178
 */
179 180 181 182
RelOptInfo *
make_rels_by_clause_joins(Query *root,
						  RelOptInfo *old_rel,
						  List *other_rels)
183
{
184 185 186
	RelOptInfo *result = NULL;
	List	   *i,
			   *j;
187

188
	foreach(i, old_rel->joininfo)
189
	{
190 191
		JoinInfo   *joininfo = (JoinInfo *) lfirst(i);
		Relids		unjoined_relids = joininfo->unjoined_relids;
192

193
		foreach(j, other_rels)
194
		{
195 196 197 198
			RelOptInfo   *other_rel = (RelOptInfo *) lfirst(j);

			if (is_subseti(unjoined_relids, other_rel->relids))
				result = make_join_rel(root, old_rel, other_rel);
199 200 201
		}
	}

202
	return result;
203 204
}

205
/*
206 207 208 209
 * make_rels_by_clauseless_joins
 *	  Given a relation 'old_rel' and a list of other relations
 *	  'other_rels', create a join relation between 'old_rel' and each
 *	  member of 'other_rels' that isn't already included in 'old_rel'.
210
 *
211 212
 * 'old_rel' is the relation entry for the relation to be joined
 * 'other_rels': other rels to be considered for joining
213
 *
214 215
 * Currently, this is only used with base rels in other_rels, but it would
 * work for joining to joinrels too.
216
 *
217 218 219 220
 * Returns NULL if no suitable joins were found, else the last suitable
 * joinrel processed.  (The only caller who checks the return value is
 * geqo_eval.c, and it sets things up so there can be no more than one
 * "suitable" joinrel; so we don't bother with returning a list.)
221
 */
222 223 224 225
RelOptInfo *
make_rels_by_clauseless_joins(Query *root,
							  RelOptInfo *old_rel,
							  List *other_rels)
226
{
227
	RelOptInfo *result = NULL;
228
	List	   *i;
229

230
	foreach(i, other_rels)
231
	{
232
		RelOptInfo *other_rel = (RelOptInfo *) lfirst(i);
Bruce Momjian's avatar
Bruce Momjian committed
233

234 235
		if (nonoverlap_setsi(other_rel->relids, old_rel->relids))
			result = make_join_rel(root, old_rel, other_rel);
236 237
	}

238
	return result;
239 240 241 242
}


/*
243 244 245 246 247 248 249
 * make_join_rel
 *	   Find or create a join RelOptInfo that represents the join of
 *	   the two given rels, and add to it path information for paths
 *	   created with the two rels as outer and inner rel.
 *	   (The join rel may already contain paths generated from other
 *	   pairs of rels that add up to the same set of base rels.)
 *	   The join rel is stored in the query's join_rel_list.
250
 */
251 252
static RelOptInfo *
make_join_rel(Query *root, RelOptInfo *rel1, RelOptInfo *rel2)
253
{
254 255
	RelOptInfo	   *joinrel;
	List		   *restrictlist;
256 257

	/*
258 259
	 * Find or build the join RelOptInfo, and compute the restrictlist
	 * that goes with this particular joining.
260
	 */
261
	joinrel = get_join_rel(root, rel1, rel2, &restrictlist);
262

263 264 265 266 267
	/*
	 * We consider paths using each rel as both outer and inner.
	 */
	add_paths_to_joinrel(root, joinrel, rel1, rel2, restrictlist);
	add_paths_to_joinrel(root, joinrel, rel2, rel1, restrictlist);
268

269
	return joinrel;
270
}