1/*-------------------------------------------------------------------------
4 * Routines for preprocessing qualification expressions
7 * While the parser will produce flattened (N-argument) AND/OR trees from
8 * simple sequences of AND'ed or OR'ed clauses, there might be an AND clause
9 * directly underneath another AND, or OR underneath OR, if the input was
10 * oddly parenthesized. Also, rule expansion and subquery flattening could
11 * produce such parsetrees. The planner wants to flatten all such cases
12 * to ensure consistent optimization behavior.
14 * Formerly, this module was responsible for doing the initial flattening,
15 * but now we leave it to eval_const_expressions to do that since it has to
16 * make a complete pass over the expression tree anyway. Instead, we just
17 * have to ensure that our manipulations preserve AND/OR flatness.
18 * pull_ands() and pull_ors() are used to maintain flatness of the AND/OR
19 * tree after local transformations that might introduce nested AND/ORs.
22 * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
23 * Portions Copyright (c) 1994, Regents of the University of California
27 * src/backend/optimizer/prep/prepqual.c
29 *-------------------------------------------------------------------------
48 * Negate a Boolean expression.
50 * Input is a clause to be negated (e.g., the argument of a NOT clause).
51 * Returns a new clause equivalent to the negation of the given clause.
53 * Although this can be invoked on its own, it's mainly intended as a helper
54 * for eval_const_expressions(), and that context drives several design
55 * decisions. In particular, if the input is already AND/OR flat, we must
56 * preserve that property. We also don't bother to recurse in situations
57 * where we can assume that lower-level executions of eval_const_expressions
58 * would already have simplified sub-clauses of the input.
60 * The difference between this and a simple make_notclause() is that this
61 * tries to get rid of the NOT node by logical simplification. It's clearly
62 * always a win if the NOT node can be eliminated altogether. However, our
63 * use of DeMorgan's laws could result in having more NOT nodes rather than
64 * fewer. We do that unconditionally anyway, because in WHERE clauses it's
65 * important to expose as much top-level AND/OR structure as possible.
66 * Also, eliminating an intermediate NOT may allow us to flatten two levels
67 * of AND or OR together that we couldn't have otherwise. Finally, one of
68 * the motivations for doing this is to ensure that logically equivalent
69 * expressions will be seen as physically equal(), so we should always apply
70 * the same transformations.
75 if (node == NULL)
/* should not happen */
76 elog(
ERROR,
"can't negate an empty subexpression");
83 /* NOT NULL is still NULL */
86 /* otherwise pretty easy */
93 * Negate operator if possible: (NOT (< A B)) => (>= A B)
102 newopexpr->
opno = negator;
104 newopexpr->opresulttype = opexpr->opresulttype;
105 newopexpr->opretset = opexpr->opretset;
106 newopexpr->opcollid = opexpr->opcollid;
107 newopexpr->inputcollid = opexpr->inputcollid;
110 return (
Node *) newopexpr;
114 case T_ScalarArrayOpExpr:
117 * Negate a ScalarArrayOpExpr if its operator has a negator;
118 * for example x = ANY (list) becomes x <> ALL (list)
127 newopexpr->
opno = negator;
132 newopexpr->inputcollid = saopexpr->inputcollid;
135 return (
Node *) newopexpr;
145 /*--------------------
146 * Apply DeMorgan's Laws:
147 * (NOT (AND A B)) => (OR (NOT A) (NOT B))
148 * (NOT (OR A B)) => (AND (NOT A) (NOT B))
149 * i.e., swap AND for OR and negate each subclause.
151 * If the input is already AND/OR flat and has no NOT
152 * directly above AND or OR, this transformation preserves
153 * those properties. For example, if no direct child of
154 * the given AND clause is an AND or a NOT-above-OR, then
155 * the recursive calls of negate_clause() can't return any
156 * OR clauses. So we needn't call pull_ors() before
157 * building a new OR clause. Similarly for the OR case.
158 *--------------------
165 foreach(lc, expr->
args)
178 foreach(lc, expr->
args)
189 * NOT underneath NOT: they cancel. We assume the
190 * input is already simplified, so no need to recurse.
205 * In the rowtype case, the two flavors of NullTest are *not*
206 * logical inverses, so we can't simplify. But it does work
207 * for scalar datatypes.
216 newexpr->argisrow = expr->argisrow;
218 return (
Node *) newexpr;
249 elog(
ERROR,
"unrecognized booltesttype: %d",
254 return (
Node *) newexpr;
258 /* else fall through */
263 * Otherwise we don't know how to simplify this, so just tack on an
272 * Convert a qualification expression to the most useful form.
274 * This is primarily intended to be used on top-level WHERE (or JOIN/ON)
275 * clauses. It can also be used on top-level CHECK constraints, for which
276 * pass is_check = true. DO NOT call it on any expression that is not known
277 * to be one or the other, as it might apply inappropriate simplifications.
279 * The name of this routine is a holdover from a time when it would try to
280 * force the expression into canonical AND-of-ORs or OR-of-ANDs form.
281 * Eventually, we recognized that that had more theoretical purity than
282 * actual usefulness, and so now the transformation doesn't involve any
283 * notion of reaching a canonical form.
285 * NOTE: we assume the input has already been through eval_const_expressions
286 * and therefore possesses AND/OR flatness. Formerly this function included
287 * its own flattening logic, but that requires a useless extra pass over the
290 * Returns the modified qualification.
297 /* Quick exit for empty qual */
301 /* This should not be invoked on quals in implicit-AND format */
305 * Pull up redundant subclauses in OR-of-AND trees. We do this only
306 * within the top-level AND/OR structure; there's no point in looking
307 * deeper. Also remove any NULL constants in the top-level structure.
317 * Recursively flatten nested AND clauses into a single and-clause list.
319 * Input is the arglist of an AND clause.
320 * Returns the rebuilt arglist (note original list structure is not touched).
328 foreach(
arg, andlist)
336 out_list =
lappend(out_list, subexpr);
343 * Recursively flatten nested OR clauses into a single or-clause list.
345 * Input is the arglist of an OR clause.
346 * Returns the rebuilt arglist (note original list structure is not touched).
362 out_list =
lappend(out_list, subexpr);
368/*--------------------
369 * The following code attempts to apply the inverse OR distributive law:
370 * ((A AND B) OR (A AND C)) => (A AND (B OR C))
371 * That is, locate OR clauses in which every subclause contains an
372 * identical term, and pull out the duplicated terms.
374 * This may seem like a fairly useless activity, but it turns out to be
375 * applicable to many machine-generated queries, and there are also queries
376 * in some of the TPC benchmarks that need it. This was in fact almost the
377 * sole useful side-effect of the old prepqual code that tried to force
378 * the query into canonical AND-of-ORs form: the canonical equivalent of
379 * ((A AND B) OR (A AND C))
381 * ((A OR A) AND (A OR C) AND (B OR A) AND (B OR C))
382 * which the code was able to simplify to
383 * (A AND (A OR C) AND (B OR A) AND (B OR C))
384 * thus successfully extracting the common condition A --- but at the cost
385 * of cluttering the qual with many redundant clauses.
386 *--------------------
391 * Given a qualification tree with the NOTs pushed down, search for
392 * OR clauses to which the inverse OR distributive law might apply.
393 * Only the top-level AND/OR structure is searched.
395 * While at it, we remove any NULL constants within the top-level AND/OR
396 * structure, eg in a WHERE clause, "x OR NULL::boolean" is reduced to "x".
397 * In general that would change the result, so eval_const_expressions can't
398 * do it; but at top level of WHERE, we don't need to distinguish between
399 * FALSE and NULL results, so it's valid to treat NULL::boolean the same
400 * as FALSE and then simplify AND/OR accordingly. Conversely, in a top-level
401 * CHECK constraint, we may treat a NULL the same as TRUE.
403 * Returns the modified qualification. AND/OR flatness is preserved.
420 /* Get rid of any constant inputs */
427 /* Within OR in CHECK, drop constant FALSE */
428 if (!carg->constisnull && !
DatumGetBool(carg->constvalue))
430 /* Constant TRUE or NULL, so OR reduces to TRUE */
435 /* Within OR in WHERE, drop constant FALSE or NULL */
436 if (carg->constisnull || !
DatumGetBool(carg->constvalue))
438 /* Constant TRUE, so OR reduces to TRUE */
446 /* Flatten any ORs pulled up to just below here */
449 /* Now we can look for duplicate ORs */
464 /* Get rid of any constant inputs */
471 /* Within AND in CHECK, drop constant TRUE or NULL */
472 if (carg->constisnull ||
DatumGetBool(carg->constvalue))
474 /* Constant FALSE, so AND reduces to FALSE */
479 /* Within AND in WHERE, drop constant TRUE */
480 if (!carg->constisnull &&
DatumGetBool(carg->constvalue))
482 /* Constant FALSE or NULL, so AND reduces to FALSE */
490 /* Flatten any ANDs introduced just below here */
493 /* AND of no inputs reduces to TRUE */
497 /* Single-expression AND just reduces to that expression */
501 /* Else we still need an AND node */
509 * process_duplicate_ors
510 * Given a list of exprs which are ORed together, try to apply
511 * the inverse OR distributive law.
513 * Returns the resulting expression (could be an AND clause, an OR
514 * clause, or maybe even a single subexpression).
520 int num_subclauses = 0;
525 /* OR of no inputs reduces to FALSE */
529 /* Single-expression OR just reduces to that expression */
534 * Choose the shortest AND clause as the reference list --- obviously, any
535 * subclause not in this clause isn't in all the clauses. If we find a
536 * clause that's not an AND, we can treat it as a one-element AND clause,
537 * which necessarily wins as shortest.
539 foreach(temp, orlist)
548 if (reference ==
NIL || nclauses < num_subclauses)
550 reference = subclauses;
551 num_subclauses = nclauses;
562 * Just in case, eliminate any duplicates in the reference list.
567 * Check each element of the reference list to see if it's in all the OR
568 * clauses. Build a new list of winning clauses.
571 foreach(temp, reference)
577 foreach(temp2, orlist)
591 if (!
equal(refclause, clause))
600 winners =
lappend(winners, refclause);
604 * If no winners, we can't transform the OR
610 * Generate new OR list consisting of the remaining sub-clauses.
612 * If any clause degenerates to empty, then we have a situation like (A
613 * AND B) OR (A), which can be reduced to just A --- that is, the
614 * additional conditions in other arms of the OR are irrelevant.
616 * Note that because we use list_difference, any multiple occurrences of a
617 * winning clause in an AND sub-clause will be removed automatically.
620 foreach(temp, orlist)
629 if (subclauses !=
NIL)
638 neworlist =
NIL;
/* degenerate case, see above */
645 neworlist =
lappend(neworlist, clause);
648 neworlist =
NIL;
/* degenerate case, see above */
655 * Append reduced OR to the winners list, if it's not degenerate, handling
656 * the special case of one element correctly (can that really happen?).
657 * Also be careful to maintain AND/OR flatness in case we pulled up a
660 if (neworlist !=
NIL)
669 * And return the constructed AND clause, again being wary of a single
670 * element and AND/OR flatness.
bool equal(const void *a, const void *b)
Assert(PointerIsAligned(start, uint64))
List * list_difference(const List *list1, const List *list2)
List * lappend(List *list, void *datum)
List * list_concat(List *list1, const List *list2)
bool list_member(const List *list, const void *datum)
List * list_union(const List *list1, const List *list2)
Oid get_negator(Oid opno)
Expr * make_orclause(List *orclauses)
Node * makeBoolConst(bool value, bool isnull)
Expr * make_andclause(List *andclauses)
Expr * make_notclause(Expr *notclause)
static bool is_andclause(const void *clause)
static bool is_orclause(const void *clause)
#define IsA(nodeptr, _type_)
static int list_length(const List *l)
static bool DatumGetBool(Datum X)
Expr * canonicalize_qual(Expr *qual, bool is_check)
static Expr * process_duplicate_ors(List *orlist)
static List * pull_ors(List *orlist)
Node * negate_clause(Node *node)
static List * pull_ands(List *andlist)
static Expr * find_duplicate_ors(Expr *qual, bool is_check)
BoolTestType booltesttype
NullTestType nulltesttype