1 /*-------------------------------------------------------------------------
4 * Routines for preprocessing qualification expressions
6 * Portions Copyright (c) 1996-2003, PostgreSQL Global Development Group
7 * Portions Copyright (c) 1994, Regents of the University of California
11 * $PostgreSQL: pgsql/src/backend/optimizer/prep/prepqual.c,v 1.41 2003/12/30 21:49:19 tgl Exp $
13 *-------------------------------------------------------------------------
18 #include "nodes/makefuncs.h"
19 #include "optimizer/clauses.h"
20 #include "optimizer/prep.h"
21 #include "utils/lsyscache.h"
24 static Node *flatten_andors_mutator(Node *node, void *context);
25 static void flatten_andors_and_walker(FastList *out_list, List *andlist);
26 static void flatten_andors_or_walker(FastList *out_list, List *orlist);
27 static List *pull_ands(List *andlist);
28 static void pull_ands_walker(FastList *out_list, List *andlist);
29 static List *pull_ors(List *orlist);
30 static void pull_ors_walker(FastList *out_list, List *orlist);
31 static Expr *find_nots(Expr *qual);
32 static Expr *push_nots(Expr *qual);
33 static Expr *find_duplicate_ors(Expr *qual);
34 static Expr *process_duplicate_ors(List *orlist);
39 * Convert a qualification expression to the most useful form.
41 * The name of this routine is a holdover from a time when it would try to
42 * force the expression into canonical AND-of-ORs or OR-of-ANDs form.
43 * Eventually, we recognized that that had more theoretical purity than
44 * actual usefulness, and so now the transformation doesn't involve any
45 * notion of reaching a canonical form.
47 * Returns the modified qualification.
50 canonicalize_qual(Expr *qual)
54 /* Quick exit for empty qual */
59 * Flatten AND and OR groups throughout the expression tree.
61 newqual = (Expr *) flatten_andors((Node *) qual);
64 * Push down NOTs. We do this only in the top-level boolean
65 * expression, without examining arguments of operators/functions.
66 * The main reason for doing this is to expose as much top-level AND/OR
67 * structure as we can, so there's no point in descending further.
69 newqual = find_nots(newqual);
72 * Pull up redundant subclauses in OR-of-AND trees. Again, we do this
73 * only within the top-level AND/OR structure.
75 newqual = find_duplicate_ors(newqual);
81 /*--------------------
82 * The parser regards AND and OR as purely binary operators, so a qual like
83 * (A = 1) OR (A = 2) OR (A = 3) ...
84 * will produce a nested parsetree
85 * (OR (A = 1) (OR (A = 2) (OR (A = 3) ...)))
86 * In reality, the optimizer and executor regard AND and OR as n-argument
87 * operators, so this tree can be flattened to
88 * (OR (A = 1) (A = 2) (A = 3) ...)
89 * which is the responsibility of the routines below.
91 * flatten_andors() does the basic transformation with no initial assumptions.
92 * pull_ands() and pull_ors() are used to maintain flatness of the AND/OR
93 * tree after local transformations that might introduce nested AND/ORs.
99 * Given an expression tree, simplify nested AND/OR clauses into flat
100 * AND/OR clauses with more arguments. The entire tree is processed.
102 * Returns the rebuilt expr (note original structure is not touched).
104 * This is exported so that other modules can perform the part of
105 * canonicalize_qual processing that applies to entire trees, rather
106 * than just the top-level boolean expressions.
109 flatten_andors(Node *node)
111 return flatten_andors_mutator(node, NULL);
115 flatten_andors_mutator(Node *node, void *context)
119 if (IsA(node, BoolExpr))
121 BoolExpr *bexpr = (BoolExpr *) node;
123 if (bexpr->boolop == AND_EXPR)
127 FastListInit(&out_list);
128 flatten_andors_and_walker(&out_list, bexpr->args);
129 return (Node *) make_andclause(FastListValue(&out_list));
131 if (bexpr->boolop == OR_EXPR)
135 FastListInit(&out_list);
136 flatten_andors_or_walker(&out_list, bexpr->args);
137 return (Node *) make_orclause(FastListValue(&out_list));
139 /* else it's a NOT clause, fall through */
141 return expression_tree_mutator(node, flatten_andors_mutator, context);
145 flatten_andors_and_walker(FastList *out_list, List *andlist)
149 foreach(arg, andlist)
151 Node *subexpr = (Node *) lfirst(arg);
153 if (and_clause(subexpr))
154 flatten_andors_and_walker(out_list, ((BoolExpr *) subexpr)->args);
156 FastAppend(out_list, flatten_andors(subexpr));
161 flatten_andors_or_walker(FastList *out_list, List *orlist)
167 Node *subexpr = (Node *) lfirst(arg);
169 if (or_clause(subexpr))
170 flatten_andors_or_walker(out_list, ((BoolExpr *) subexpr)->args);
172 FastAppend(out_list, flatten_andors(subexpr));
178 * Recursively flatten nested AND clauses into a single and-clause list.
180 * Input is the arglist of an AND clause.
181 * Returns the rebuilt arglist (note original list structure is not touched).
184 pull_ands(List *andlist)
188 FastListInit(&out_list);
189 pull_ands_walker(&out_list, andlist);
190 return FastListValue(&out_list);
194 pull_ands_walker(FastList *out_list, List *andlist)
198 foreach(arg, andlist)
200 Node *subexpr = (Node *) lfirst(arg);
202 if (and_clause(subexpr))
203 pull_ands_walker(out_list, ((BoolExpr *) subexpr)->args);
205 FastAppend(out_list, subexpr);
211 * Recursively flatten nested OR clauses into a single or-clause list.
213 * Input is the arglist of an OR clause.
214 * Returns the rebuilt arglist (note original list structure is not touched).
217 pull_ors(List *orlist)
221 FastListInit(&out_list);
222 pull_ors_walker(&out_list, orlist);
223 return FastListValue(&out_list);
227 pull_ors_walker(FastList *out_list, List *orlist)
233 Node *subexpr = (Node *) lfirst(arg);
235 if (or_clause(subexpr))
236 pull_ors_walker(out_list, ((BoolExpr *) subexpr)->args);
238 FastAppend(out_list, subexpr);
245 * Traverse the qualification, looking for NOTs to take care of.
246 * For NOT clauses, apply push_nots() to try to push down the NOT.
247 * For AND and OR clause types, simply recurse. Otherwise stop
248 * recursing (we do not worry about structure below the top AND/OR tree).
250 * Returns the modified qualification. AND/OR flatness is preserved.
253 find_nots(Expr *qual)
258 if (and_clause((Node *) qual))
263 FastListInit(&t_list);
264 foreach(temp, ((BoolExpr *) qual)->args)
265 FastAppend(&t_list, find_nots(lfirst(temp)));
266 return make_andclause(pull_ands(FastListValue(&t_list)));
268 else if (or_clause((Node *) qual))
273 FastListInit(&t_list);
274 foreach(temp, ((BoolExpr *) qual)->args)
275 FastAppend(&t_list, find_nots(lfirst(temp)));
276 return make_orclause(pull_ors(FastListValue(&t_list)));
278 else if (not_clause((Node *) qual))
279 return push_nots(get_notclausearg(qual));
286 * Push down a NOT as far as possible.
288 * Input is an expression to be negated (e.g., the argument of a NOT clause).
289 * Returns a new qual equivalent to the negation of the given qual.
292 push_nots(Expr *qual)
295 return make_notclause(qual); /* XXX is this right? Or
299 * Negate an operator clause if possible: (NOT (< A B)) => (> A B)
300 * Otherwise, retain the clause as it is (the NOT can't be pushed
303 if (is_opclause(qual))
305 OpExpr *opexpr = (OpExpr *) qual;
306 Oid negator = get_negator(opexpr->opno);
309 return make_opclause(negator,
310 opexpr->opresulttype,
312 (Expr *) get_leftop(qual),
313 (Expr *) get_rightop(qual));
315 return make_notclause(qual);
317 else if (and_clause((Node *) qual))
319 /*--------------------
320 * Apply DeMorgan's Laws:
321 * (NOT (AND A B)) => (OR (NOT A) (NOT B))
322 * (NOT (OR A B)) => (AND (NOT A) (NOT B))
323 * i.e., swap AND for OR and negate all the subclauses.
324 *--------------------
329 FastListInit(&t_list);
330 foreach(temp, ((BoolExpr *) qual)->args)
331 FastAppend(&t_list, push_nots(lfirst(temp)));
332 return make_orclause(pull_ors(FastListValue(&t_list)));
334 else if (or_clause((Node *) qual))
339 FastListInit(&t_list);
340 foreach(temp, ((BoolExpr *) qual)->args)
341 FastAppend(&t_list, push_nots(lfirst(temp)));
342 return make_andclause(pull_ands(FastListValue(&t_list)));
344 else if (not_clause((Node *) qual))
347 * Another NOT cancels this NOT, so eliminate the NOT and
348 * stop negating this branch.
350 return get_notclausearg(qual);
355 * We don't know how to negate anything else, place a NOT at
358 return make_notclause(qual);
363 /*--------------------
364 * The following code attempts to apply the inverse OR distributive law:
365 * ((A AND B) OR (A AND C)) => (A AND (B OR C))
366 * That is, locate OR clauses in which every subclause contains an
367 * identical term, and pull out the duplicated terms.
369 * This may seem like a fairly useless activity, but it turns out to be
370 * applicable to many machine-generated queries, and there are also queries
371 * in some of the TPC benchmarks that need it. This was in fact almost the
372 * sole useful side-effect of the old prepqual code that tried to force
373 * the query into canonical AND-of-ORs form: the canonical equivalent of
374 * ((A AND B) OR (A AND C))
376 * ((A OR A) AND (A OR C) AND (B OR A) AND (B OR C))
377 * which the code was able to simplify to
378 * (A AND (A OR C) AND (B OR A) AND (B OR C))
379 * thus successfully extracting the common condition A --- but at the cost
380 * of cluttering the qual with many redundant clauses.
381 *--------------------
386 * Given a qualification tree with the NOTs pushed down, search for
387 * OR clauses to which the inverse OR distributive law might apply.
388 * Only the top-level AND/OR structure is searched.
390 * Returns the modified qualification. AND/OR flatness is preserved.
393 find_duplicate_ors(Expr *qual)
398 if (or_clause((Node *) qual))
404 foreach(temp, ((BoolExpr *) qual)->args)
405 orlist = lappend(orlist, find_duplicate_ors(lfirst(temp)));
407 * Don't need pull_ors() since this routine will never introduce
408 * an OR where there wasn't one before.
410 return process_duplicate_ors(orlist);
412 else if (and_clause((Node *) qual))
418 foreach(temp, ((BoolExpr *) qual)->args)
419 andlist = lappend(andlist, find_duplicate_ors(lfirst(temp)));
420 /* Flatten any ANDs introduced just below here */
421 andlist = pull_ands(andlist);
422 /* The AND list can't get shorter, so result is always an AND */
423 return make_andclause(andlist);
430 * process_duplicate_ors
431 * Given a list of exprs which are ORed together, try to apply
432 * the inverse OR distributive law.
434 * Returns the resulting expression (could be an AND clause, an OR
435 * clause, or maybe even a single subexpression).
438 process_duplicate_ors(List *orlist)
440 List *reference = NIL;
441 int num_subclauses = 0;
448 return NULL; /* probably can't happen */
449 if (lnext(orlist) == NIL)
450 return lfirst(orlist); /* single-expression OR (can this happen?) */
453 * Choose the shortest AND clause as the reference list --- obviously,
454 * any subclause not in this clause isn't in all the clauses.
455 * If we find a clause that's not an AND, we can treat it as a
456 * one-element AND clause, which necessarily wins as shortest.
458 foreach(temp, orlist)
460 Expr *clause = lfirst(temp);
462 if (and_clause((Node *) clause))
464 List *subclauses = ((BoolExpr *) clause)->args;
465 int nclauses = length(subclauses);
467 if (reference == NIL || nclauses < num_subclauses)
469 reference = subclauses;
470 num_subclauses = nclauses;
475 reference = makeList1(clause);
481 * Just in case, eliminate any duplicates in the reference list.
483 reference = set_union(NIL, reference);
486 * Check each element of the reference list to see if it's in all the
487 * OR clauses. Build a new list of winning clauses.
490 foreach(temp, reference)
492 Expr *refclause = lfirst(temp);
495 foreach(temp2, orlist)
497 Expr *clause = lfirst(temp2);
499 if (and_clause((Node *) clause))
501 if (!member(refclause, ((BoolExpr *) clause)->args))
509 if (!equal(refclause, clause))
518 winners = lappend(winners, refclause);
522 * If no winners, we can't transform the OR
525 return make_orclause(orlist);
528 * Generate new OR list consisting of the remaining sub-clauses.
530 * If any clause degenerates to empty, then we have a situation like
531 * (A AND B) OR (A), which can be reduced to just A --- that is, the
532 * additional conditions in other arms of the OR are irrelevant.
534 * Note that because we use set_difference, any multiple occurrences of
535 * a winning clause in an AND sub-clause will be removed automatically.
538 foreach(temp, orlist)
540 Expr *clause = lfirst(temp);
542 if (and_clause((Node *) clause))
544 List *subclauses = ((BoolExpr *) clause)->args;
546 subclauses = set_difference(subclauses, winners);
547 if (subclauses != NIL)
549 if (lnext(subclauses) == NIL)
550 neworlist = lappend(neworlist, lfirst(subclauses));
552 neworlist = lappend(neworlist, make_andclause(subclauses));
556 neworlist = NIL; /* degenerate case, see above */
562 if (!member(clause, winners))
563 neworlist = lappend(neworlist, clause);
566 neworlist = NIL; /* degenerate case, see above */
573 * Append reduced OR to the winners list, if it's not degenerate, handling
574 * the special case of one element correctly (can that really happen?).
575 * Also be careful to maintain AND/OR flatness in case we pulled up a
578 if (neworlist != NIL)
580 if (lnext(neworlist) == NIL)
581 winners = lappend(winners, lfirst(neworlist));
583 winners = lappend(winners, make_orclause(pull_ors(neworlist)));
587 * And return the constructed AND clause, again being wary of a single
588 * element and AND/OR flatness.
590 if (lnext(winners) == NIL)
591 return (Expr *) lfirst(winners);
593 return make_andclause(pull_ands(winners));