restrictinfo.c 6.89 KB
Newer Older
1 2
/*-------------------------------------------------------------------------
 *
3
 * restrictinfo.c
4
 *	  RestrictInfo node manipulation routines.
5
 *
Bruce Momjian's avatar
Bruce Momjian committed
6
 * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
Bruce Momjian's avatar
Add:  
Bruce Momjian committed
7
 * Portions Copyright (c) 1994, Regents of the University of California
8 9 10
 *
 *
 * IDENTIFICATION
11
 *	  $Header: /cvsroot/pgsql/src/backend/optimizer/util/restrictinfo.c,v 1.17 2003/06/15 22:51:45 tgl Exp $
12 13 14 15 16 17
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "optimizer/clauses.h"
18
#include "optimizer/paths.h"
19
#include "optimizer/restrictinfo.h"
20
#include "optimizer/var.h"
21

22

23 24 25 26 27 28
static bool join_clause_is_redundant(Query *root,
									 RestrictInfo *rinfo,
									 List *reference_list,
									 JoinType jointype);


29
/*
30
 * restriction_is_or_clause
31
 *
32
 * Returns t iff the restrictinfo node contains an 'or' clause.
33 34
 */
bool
35
restriction_is_or_clause(RestrictInfo *restrictinfo)
36
{
37 38
	if (restrictinfo != NULL &&
		or_clause((Node *) restrictinfo->clause))
39
		return true;
40
	else
41
		return false;
42 43
}

44
/*
45
 * get_actual_clauses
46
 *
47
 * Returns a list containing the bare clauses from 'restrictinfo_list'.
48
 */
49
List *
50
get_actual_clauses(List *restrictinfo_list)
51
{
52 53
	List	   *result = NIL;
	List	   *temp;
54

55
	foreach(temp, restrictinfo_list)
56
	{
57
		RestrictInfo *clause = (RestrictInfo *) lfirst(temp);
58

59
		result = lappend(result, clause->clause);
60
	}
61
	return result;
62
}
63 64 65 66 67

/*
 * get_actual_join_clauses
 *
 * Extract clauses from 'restrictinfo_list', separating those that
68
 * syntactically match the join level from those that were pushed down.
69 70 71 72 73 74 75 76 77 78 79 80 81 82
 */
void
get_actual_join_clauses(List *restrictinfo_list,
						List **joinquals, List **otherquals)
{
	List	   *temp;

	*joinquals = NIL;
	*otherquals = NIL;

	foreach(temp, restrictinfo_list)
	{
		RestrictInfo *clause = (RestrictInfo *) lfirst(temp);

83
		if (clause->ispusheddown)
84
			*otherquals = lappend(*otherquals, clause->clause);
85 86
		else
			*joinquals = lappend(*joinquals, clause->clause);
87 88
	}
}
89 90 91 92 93 94 95 96 97 98 99 100 101 102

/*
 * remove_redundant_join_clauses
 *
 * Given a list of RestrictInfo clauses that are to be applied in a join,
 * remove any duplicate or redundant clauses.
 *
 * We must eliminate duplicates when forming the restrictlist for a joinrel,
 * since we will see many of the same clauses arriving from both input
 * relations. Also, if a clause is a mergejoinable clause, it's possible that
 * it is redundant with previous clauses (see optimizer/README for
 * discussion). We detect that case and omit the redundant clause from the
 * result list.
 *
103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172
 * The result is a fresh List, but it points to the same member nodes
 * as were in the input.
 */
List *
remove_redundant_join_clauses(Query *root, List *restrictinfo_list,
							  JoinType jointype)
{
	List	   *result = NIL;
	List	   *item;

	foreach(item, restrictinfo_list)
	{
		RestrictInfo *rinfo = (RestrictInfo *) lfirst(item);

		/* drop it if redundant with any prior clause */
		if (join_clause_is_redundant(root, rinfo, result, jointype))
			continue;

		/* otherwise, add it to result list */
		result = lappend(result, rinfo);
	}

	return result;
}

/*
 * select_nonredundant_join_clauses
 *
 * Given a list of RestrictInfo clauses that are to be applied in a join,
 * select the ones that are not redundant with any clause in the
 * reference_list.
 *
 * This is similar to remove_redundant_join_clauses, but we are looking for
 * redundancies with a separate list of clauses (i.e., clauses that have
 * already been applied below the join itself).
 *
 * Note that we assume the given restrictinfo_list has already been checked
 * for local redundancies, so we don't check again.
 */
List *
select_nonredundant_join_clauses(Query *root,
								 List *restrictinfo_list,
								 List *reference_list,
								 JoinType jointype)
{
	List	   *result = NIL;
	List	   *item;

	foreach(item, restrictinfo_list)
	{
		RestrictInfo *rinfo = (RestrictInfo *) lfirst(item);

		/* drop it if redundant with any reference clause */
		if (join_clause_is_redundant(root, rinfo, reference_list, jointype))
			continue;

		/* otherwise, add it to result list */
		result = lappend(result, rinfo);
	}

	return result;
}

/*
 * join_clause_is_redundant
 *		Returns true if rinfo is redundant with any clause in reference_list.
 *
 * This is the guts of both remove_redundant_join_clauses and
 * select_nonredundant_join_clauses.  See the docs above for motivation.
 *
173 174 175 176 177 178 179 180
 * We can detect redundant mergejoinable clauses very cheaply by using their
 * left and right pathkeys, which uniquely identify the sets of equijoined
 * variables in question.  All the members of a pathkey set that are in the
 * left relation have already been forced to be equal; likewise for those in
 * the right relation.  So, we need to have only one clause that checks
 * equality between any set member on the left and any member on the right;
 * by transitivity, all the rest are then equal.
 *
181 182 183 184 185 186 187
 * However, clauses that are of the form "var expr = const expr" cannot be
 * eliminated as redundant.  This is because when there are const expressions
 * in a pathkey set, generate_implied_equalities() suppresses "var = var"
 * clauses in favor of "var = const" clauses.  We cannot afford to drop any
 * of the latter, even though they might seem redundant by the pathkey
 * membership test.
 *
188 189 190 191 192
 * Weird special case: if we have two clauses that seem redundant
 * except one is pushed down into an outer join and the other isn't,
 * then they're not really redundant, because one constrains the
 * joined rows after addition of null fill rows, and the other doesn't.
 */
193 194 195 196 197
static bool
join_clause_is_redundant(Query *root,
						 RestrictInfo *rinfo,
						 List *reference_list,
						 JoinType jointype)
198
{
199 200 201 202
	/* always consider exact duplicates redundant */
	/* XXX would it be sufficient to use ptrMember here? */
	if (member(rinfo, reference_list))
		return true;
203

204 205
	/* check for redundant merge clauses */
	if (rinfo->mergejoinoperator != InvalidOid)
206
	{
207 208
		bool		redundant = false;
		List	   *refitem;
209

210
		cache_mergeclause_pathkeys(root, rinfo);
211

212 213
		/* do the cheap tests first */
		foreach(refitem, reference_list)
214
		{
215
			RestrictInfo *refrinfo = (RestrictInfo *) lfirst(refitem);
216

217 218 219 220 221
			if (refrinfo->mergejoinoperator != InvalidOid &&
				rinfo->left_pathkey == refrinfo->left_pathkey &&
				rinfo->right_pathkey == refrinfo->right_pathkey &&
				(rinfo->ispusheddown == refrinfo->ispusheddown ||
				 !IS_OUTER_JOIN(jointype)))
222
			{
223 224
				redundant = true;
				break;
225
			}
226 227
		}

228 229 230 231 232 233 234 235 236 237 238 239 240 241 242
		if (redundant)
		{
			/*
			 * It looks redundant, now check for "var = const" case.
			 * If left_relids/right_relids are set, then there are
			 * definitely vars on both sides; else we must check the
			 * hard way.
			 */
			if (rinfo->left_relids)
				return true;	/* var = var, so redundant */
			if (contain_var_clause(get_leftop(rinfo->clause)) &&
				contain_var_clause(get_rightop(rinfo->clause)))
				return true;	/* var = var, so redundant */
			/* else var = const, not redundant */
		}
243 244
	}

245 246
	/* otherwise, not redundant */
	return false;
247
}