PostgreSQL Source Code  git master
prepqual.c File Reference
#include "postgres.h"
#include "nodes/makefuncs.h"
#include "nodes/nodeFuncs.h"
#include "optimizer/optimizer.h"
#include "optimizer/prep.h"
#include "utils/lsyscache.h"
Include dependency graph for prepqual.c:

Go to the source code of this file.

Functions

static Listpull_ands (List *andlist)
 
static Listpull_ors (List *orlist)
 
static Exprfind_duplicate_ors (Expr *qual, bool is_check)
 
static Exprprocess_duplicate_ors (List *orlist)
 
Nodenegate_clause (Node *node)
 
Exprcanonicalize_qual (Expr *qual, bool is_check)
 

Function Documentation

◆ canonicalize_qual()

Expr* canonicalize_qual ( Expr qual,
bool  is_check 
)

Definition at line 292 of file prepqual.c.

References Assert, find_duplicate_ors(), and IsA.

Referenced by ConstraintImpliedByRelConstraint(), convert_EXISTS_to_ANY(), DoCopy(), get_proposed_default_constraint(), get_relation_constraints(), preprocess_expression(), and RelationGetIndexPredicate().

293 {
294  Expr *newqual;
295 
296  /* Quick exit for empty qual */
297  if (qual == NULL)
298  return NULL;
299 
300  /* This should not be invoked on quals in implicit-AND format */
301  Assert(!IsA(qual, List));
302 
303  /*
304  * Pull up redundant subclauses in OR-of-AND trees. We do this only
305  * within the top-level AND/OR structure; there's no point in looking
306  * deeper. Also remove any NULL constants in the top-level structure.
307  */
308  newqual = find_duplicate_ors(qual, is_check);
309 
310  return newqual;
311 }
#define IsA(nodeptr, _type_)
Definition: nodes.h:576
static Expr * find_duplicate_ors(Expr *qual, bool is_check)
Definition: prepqual.c:405
#define Assert(condition)
Definition: c.h:739
Definition: pg_list.h:50

◆ find_duplicate_ors()

static Expr * find_duplicate_ors ( Expr qual,
bool  is_check 
)
static

Definition at line 405 of file prepqual.c.

References arg, generate_unaccent_rules::args, Const::constisnull, Const::constvalue, DatumGetBool, is_andclause(), is_orclause(), IsA, lappend(), lfirst, linitial, list_length(), make_andclause(), makeBoolConst(), NIL, process_duplicate_ors(), pull_ands(), and pull_ors().

Referenced by canonicalize_qual().

406 {
407  if (is_orclause(qual))
408  {
409  List *orlist = NIL;
410  ListCell *temp;
411 
412  /* Recurse */
413  foreach(temp, ((BoolExpr *) qual)->args)
414  {
415  Expr *arg = (Expr *) lfirst(temp);
416 
417  arg = find_duplicate_ors(arg, is_check);
418 
419  /* Get rid of any constant inputs */
420  if (arg && IsA(arg, Const))
421  {
422  Const *carg = (Const *) arg;
423 
424  if (is_check)
425  {
426  /* Within OR in CHECK, drop constant FALSE */
427  if (!carg->constisnull && !DatumGetBool(carg->constvalue))
428  continue;
429  /* Constant TRUE or NULL, so OR reduces to TRUE */
430  return (Expr *) makeBoolConst(true, false);
431  }
432  else
433  {
434  /* Within OR in WHERE, drop constant FALSE or NULL */
435  if (carg->constisnull || !DatumGetBool(carg->constvalue))
436  continue;
437  /* Constant TRUE, so OR reduces to TRUE */
438  return arg;
439  }
440  }
441 
442  orlist = lappend(orlist, arg);
443  }
444 
445  /* Flatten any ORs pulled up to just below here */
446  orlist = pull_ors(orlist);
447 
448  /* Now we can look for duplicate ORs */
449  return process_duplicate_ors(orlist);
450  }
451  else if (is_andclause(qual))
452  {
453  List *andlist = NIL;
454  ListCell *temp;
455 
456  /* Recurse */
457  foreach(temp, ((BoolExpr *) qual)->args)
458  {
459  Expr *arg = (Expr *) lfirst(temp);
460 
461  arg = find_duplicate_ors(arg, is_check);
462 
463  /* Get rid of any constant inputs */
464  if (arg && IsA(arg, Const))
465  {
466  Const *carg = (Const *) arg;
467 
468  if (is_check)
469  {
470  /* Within AND in CHECK, drop constant TRUE or NULL */
471  if (carg->constisnull || DatumGetBool(carg->constvalue))
472  continue;
473  /* Constant FALSE, so AND reduces to FALSE */
474  return arg;
475  }
476  else
477  {
478  /* Within AND in WHERE, drop constant TRUE */
479  if (!carg->constisnull && DatumGetBool(carg->constvalue))
480  continue;
481  /* Constant FALSE or NULL, so AND reduces to FALSE */
482  return (Expr *) makeBoolConst(false, false);
483  }
484  }
485 
486  andlist = lappend(andlist, arg);
487  }
488 
489  /* Flatten any ANDs introduced just below here */
490  andlist = pull_ands(andlist);
491 
492  /* AND of no inputs reduces to TRUE */
493  if (andlist == NIL)
494  return (Expr *) makeBoolConst(true, false);
495 
496  /* Single-expression AND just reduces to that expression */
497  if (list_length(andlist) == 1)
498  return (Expr *) linitial(andlist);
499 
500  /* Else we still need an AND node */
501  return make_andclause(andlist);
502  }
503  else
504  return qual;
505 }
Datum constvalue
Definition: primnodes.h:200
#define NIL
Definition: pg_list.h:65
static List * pull_ands(List *andlist)
Definition: prepqual.c:322
#define IsA(nodeptr, _type_)
Definition: nodes.h:576
static bool is_orclause(const void *clause)
Definition: nodeFuncs.h:103
static bool is_andclause(const void *clause)
Definition: nodeFuncs.h:94
static Expr * find_duplicate_ors(Expr *qual, bool is_check)
Definition: prepqual.c:405
#define linitial(l)
Definition: pg_list.h:195
Node * makeBoolConst(bool value, bool isnull)
Definition: makefuncs.c:355
Expr * make_andclause(List *andclauses)
Definition: makefuncs.c:633
#define DatumGetBool(X)
Definition: postgres.h:393
List * lappend(List *list, void *datum)
Definition: list.c:322
#define lfirst(lc)
Definition: pg_list.h:190
static int list_length(const List *l)
Definition: pg_list.h:169
static List * pull_ors(List *orlist)
Definition: prepqual.c:348
static Expr * process_duplicate_ors(List *orlist)
Definition: prepqual.c:516
void * arg
Definition: pg_list.h:50
bool constisnull
Definition: primnodes.h:201

◆ negate_clause()

Node* negate_clause ( Node node)

Definition at line 74 of file prepqual.c.

References AND_EXPR, NullTest::arg, BooleanTest::arg, NullTest::argisrow, OpExpr::args, ScalarArrayOpExpr::args, BoolExpr::args, BoolExpr::boolop, BooleanTest::booltesttype, Const::constisnull, Const::constvalue, DatumGetBool, elog, ERROR, get_negator(), OpExpr::inputcollid, ScalarArrayOpExpr::inputcollid, InvalidOid, IS_FALSE, IS_NOT_FALSE, IS_NOT_NULL, IS_NOT_TRUE, IS_NOT_UNKNOWN, IS_NULL, IS_TRUE, IS_UNKNOWN, lappend(), lfirst, linitial, OpExpr::location, ScalarArrayOpExpr::location, NullTest::location, BooleanTest::location, make_andclause(), make_notclause(), make_orclause(), makeBoolConst(), makeNode, negate_clause(), NIL, nodeTag, NOT_EXPR, NullTest::nulltesttype, OpExpr::opcollid, OpExpr::opfuncid, ScalarArrayOpExpr::opfuncid, OpExpr::opno, ScalarArrayOpExpr::opno, OpExpr::opresulttype, OpExpr::opretset, OR_EXPR, T_BooleanTest, T_BoolExpr, T_Const, T_NullTest, T_OpExpr, T_ScalarArrayOpExpr, and ScalarArrayOpExpr::useOr.

Referenced by eval_const_expressions_mutator(), match_boolean_partition_clause(), negate_clause(), and simplify_boolean_equality().

75 {
76  if (node == NULL) /* should not happen */
77  elog(ERROR, "can't negate an empty subexpression");
78  switch (nodeTag(node))
79  {
80  case T_Const:
81  {
82  Const *c = (Const *) node;
83 
84  /* NOT NULL is still NULL */
85  if (c->constisnull)
86  return makeBoolConst(false, true);
87  /* otherwise pretty easy */
88  return makeBoolConst(!DatumGetBool(c->constvalue), false);
89  }
90  break;
91  case T_OpExpr:
92  {
93  /*
94  * Negate operator if possible: (NOT (< A B)) => (>= A B)
95  */
96  OpExpr *opexpr = (OpExpr *) node;
97  Oid negator = get_negator(opexpr->opno);
98 
99  if (negator)
100  {
101  OpExpr *newopexpr = makeNode(OpExpr);
102 
103  newopexpr->opno = negator;
104  newopexpr->opfuncid = InvalidOid;
105  newopexpr->opresulttype = opexpr->opresulttype;
106  newopexpr->opretset = opexpr->opretset;
107  newopexpr->opcollid = opexpr->opcollid;
108  newopexpr->inputcollid = opexpr->inputcollid;
109  newopexpr->args = opexpr->args;
110  newopexpr->location = opexpr->location;
111  return (Node *) newopexpr;
112  }
113  }
114  break;
115  case T_ScalarArrayOpExpr:
116  {
117  /*
118  * Negate a ScalarArrayOpExpr if its operator has a negator;
119  * for example x = ANY (list) becomes x <> ALL (list)
120  */
121  ScalarArrayOpExpr *saopexpr = (ScalarArrayOpExpr *) node;
122  Oid negator = get_negator(saopexpr->opno);
123 
124  if (negator)
125  {
127 
128  newopexpr->opno = negator;
129  newopexpr->opfuncid = InvalidOid;
130  newopexpr->useOr = !saopexpr->useOr;
131  newopexpr->inputcollid = saopexpr->inputcollid;
132  newopexpr->args = saopexpr->args;
133  newopexpr->location = saopexpr->location;
134  return (Node *) newopexpr;
135  }
136  }
137  break;
138  case T_BoolExpr:
139  {
140  BoolExpr *expr = (BoolExpr *) node;
141 
142  switch (expr->boolop)
143  {
144  /*--------------------
145  * Apply DeMorgan's Laws:
146  * (NOT (AND A B)) => (OR (NOT A) (NOT B))
147  * (NOT (OR A B)) => (AND (NOT A) (NOT B))
148  * i.e., swap AND for OR and negate each subclause.
149  *
150  * If the input is already AND/OR flat and has no NOT
151  * directly above AND or OR, this transformation preserves
152  * those properties. For example, if no direct child of
153  * the given AND clause is an AND or a NOT-above-OR, then
154  * the recursive calls of negate_clause() can't return any
155  * OR clauses. So we needn't call pull_ors() before
156  * building a new OR clause. Similarly for the OR case.
157  *--------------------
158  */
159  case AND_EXPR:
160  {
161  List *nargs = NIL;
162  ListCell *lc;
163 
164  foreach(lc, expr->args)
165  {
166  nargs = lappend(nargs,
167  negate_clause(lfirst(lc)));
168  }
169  return (Node *) make_orclause(nargs);
170  }
171  break;
172  case OR_EXPR:
173  {
174  List *nargs = NIL;
175  ListCell *lc;
176 
177  foreach(lc, expr->args)
178  {
179  nargs = lappend(nargs,
180  negate_clause(lfirst(lc)));
181  }
182  return (Node *) make_andclause(nargs);
183  }
184  break;
185  case NOT_EXPR:
186 
187  /*
188  * NOT underneath NOT: they cancel. We assume the
189  * input is already simplified, so no need to recurse.
190  */
191  return (Node *) linitial(expr->args);
192  default:
193  elog(ERROR, "unrecognized boolop: %d",
194  (int) expr->boolop);
195  break;
196  }
197  }
198  break;
199  case T_NullTest:
200  {
201  NullTest *expr = (NullTest *) node;
202 
203  /*
204  * In the rowtype case, the two flavors of NullTest are *not*
205  * logical inverses, so we can't simplify. But it does work
206  * for scalar datatypes.
207  */
208  if (!expr->argisrow)
209  {
210  NullTest *newexpr = makeNode(NullTest);
211 
212  newexpr->arg = expr->arg;
213  newexpr->nulltesttype = (expr->nulltesttype == IS_NULL ?
214  IS_NOT_NULL : IS_NULL);
215  newexpr->argisrow = expr->argisrow;
216  newexpr->location = expr->location;
217  return (Node *) newexpr;
218  }
219  }
220  break;
221  case T_BooleanTest:
222  {
223  BooleanTest *expr = (BooleanTest *) node;
224  BooleanTest *newexpr = makeNode(BooleanTest);
225 
226  newexpr->arg = expr->arg;
227  switch (expr->booltesttype)
228  {
229  case IS_TRUE:
230  newexpr->booltesttype = IS_NOT_TRUE;
231  break;
232  case IS_NOT_TRUE:
233  newexpr->booltesttype = IS_TRUE;
234  break;
235  case IS_FALSE:
236  newexpr->booltesttype = IS_NOT_FALSE;
237  break;
238  case IS_NOT_FALSE:
239  newexpr->booltesttype = IS_FALSE;
240  break;
241  case IS_UNKNOWN:
242  newexpr->booltesttype = IS_NOT_UNKNOWN;
243  break;
244  case IS_NOT_UNKNOWN:
245  newexpr->booltesttype = IS_UNKNOWN;
246  break;
247  default:
248  elog(ERROR, "unrecognized booltesttype: %d",
249  (int) expr->booltesttype);
250  break;
251  }
252  newexpr->location = expr->location;
253  return (Node *) newexpr;
254  }
255  break;
256  default:
257  /* else fall through */
258  break;
259  }
260 
261  /*
262  * Otherwise we don't know how to simplify this, so just tack on an
263  * explicit NOT node.
264  */
265  return (Node *) make_notclause((Expr *) node);
266 }
Datum constvalue
Definition: primnodes.h:200
#define NIL
Definition: pg_list.h:65
Expr * make_notclause(Expr *notclause)
Definition: makefuncs.c:665
Node * negate_clause(Node *node)
Definition: prepqual.c:74
Definition: nodes.h:525
unsigned int Oid
Definition: postgres_ext.h:31
Expr * make_orclause(List *orclauses)
Definition: makefuncs.c:649
Oid opresulttype
Definition: primnodes.h:504
#define linitial(l)
Definition: pg_list.h:195
#define ERROR
Definition: elog.h:43
BoolExprType boolop
Definition: primnodes.h:568
Node * makeBoolConst(bool value, bool isnull)
Definition: makefuncs.c:355
Expr * arg
Definition: primnodes.h:1205
char * c
Expr * make_andclause(List *andclauses)
Definition: makefuncs.c:633
int location
Definition: primnodes.h:509
Expr * arg
Definition: primnodes.h:1228
#define DatumGetBool(X)
Definition: postgres.h:393
Oid opcollid
Definition: primnodes.h:506
Definition: nodes.h:152
List * lappend(List *list, void *datum)
Definition: list.c:322
BoolTestType booltesttype
Definition: primnodes.h:1229
Oid opfuncid
Definition: primnodes.h:503
NullTestType nulltesttype
Definition: primnodes.h:1206
#define InvalidOid
Definition: postgres_ext.h:36
#define makeNode(_type_)
Definition: nodes.h:573
#define lfirst(lc)
Definition: pg_list.h:190
int location
Definition: primnodes.h:1208
Oid inputcollid
Definition: primnodes.h:507
List * args
Definition: primnodes.h:569
#define nodeTag(nodeptr)
Definition: nodes.h:530
#define elog(elevel,...)
Definition: elog.h:228
bool argisrow
Definition: primnodes.h:1207
Oid opno
Definition: primnodes.h:502
Oid get_negator(Oid opno)
Definition: lsyscache.c:1335
List * args
Definition: primnodes.h:508
Definition: pg_list.h:50
bool constisnull
Definition: primnodes.h:201
bool opretset
Definition: primnodes.h:505

◆ process_duplicate_ors()

static Expr * process_duplicate_ors ( List orlist)
static

Definition at line 516 of file prepqual.c.

References equal(), is_andclause(), lappend(), lfirst, linitial, list_difference(), list_length(), list_make1, list_member(), list_union(), make_andclause(), make_orclause(), makeBoolConst(), NIL, pull_ands(), and pull_ors().

Referenced by find_duplicate_ors().

517 {
518  List *reference = NIL;
519  int num_subclauses = 0;
520  List *winners;
521  List *neworlist;
522  ListCell *temp;
523 
524  /* OR of no inputs reduces to FALSE */
525  if (orlist == NIL)
526  return (Expr *) makeBoolConst(false, false);
527 
528  /* Single-expression OR just reduces to that expression */
529  if (list_length(orlist) == 1)
530  return (Expr *) linitial(orlist);
531 
532  /*
533  * Choose the shortest AND clause as the reference list --- obviously, any
534  * subclause not in this clause isn't in all the clauses. If we find a
535  * clause that's not an AND, we can treat it as a one-element AND clause,
536  * which necessarily wins as shortest.
537  */
538  foreach(temp, orlist)
539  {
540  Expr *clause = (Expr *) lfirst(temp);
541 
542  if (is_andclause(clause))
543  {
544  List *subclauses = ((BoolExpr *) clause)->args;
545  int nclauses = list_length(subclauses);
546 
547  if (reference == NIL || nclauses < num_subclauses)
548  {
549  reference = subclauses;
550  num_subclauses = nclauses;
551  }
552  }
553  else
554  {
555  reference = list_make1(clause);
556  break;
557  }
558  }
559 
560  /*
561  * Just in case, eliminate any duplicates in the reference list.
562  */
563  reference = list_union(NIL, reference);
564 
565  /*
566  * Check each element of the reference list to see if it's in all the OR
567  * clauses. Build a new list of winning clauses.
568  */
569  winners = NIL;
570  foreach(temp, reference)
571  {
572  Expr *refclause = (Expr *) lfirst(temp);
573  bool win = true;
574  ListCell *temp2;
575 
576  foreach(temp2, orlist)
577  {
578  Expr *clause = (Expr *) lfirst(temp2);
579 
580  if (is_andclause(clause))
581  {
582  if (!list_member(((BoolExpr *) clause)->args, refclause))
583  {
584  win = false;
585  break;
586  }
587  }
588  else
589  {
590  if (!equal(refclause, clause))
591  {
592  win = false;
593  break;
594  }
595  }
596  }
597 
598  if (win)
599  winners = lappend(winners, refclause);
600  }
601 
602  /*
603  * If no winners, we can't transform the OR
604  */
605  if (winners == NIL)
606  return make_orclause(orlist);
607 
608  /*
609  * Generate new OR list consisting of the remaining sub-clauses.
610  *
611  * If any clause degenerates to empty, then we have a situation like (A
612  * AND B) OR (A), which can be reduced to just A --- that is, the
613  * additional conditions in other arms of the OR are irrelevant.
614  *
615  * Note that because we use list_difference, any multiple occurrences of a
616  * winning clause in an AND sub-clause will be removed automatically.
617  */
618  neworlist = NIL;
619  foreach(temp, orlist)
620  {
621  Expr *clause = (Expr *) lfirst(temp);
622 
623  if (is_andclause(clause))
624  {
625  List *subclauses = ((BoolExpr *) clause)->args;
626 
627  subclauses = list_difference(subclauses, winners);
628  if (subclauses != NIL)
629  {
630  if (list_length(subclauses) == 1)
631  neworlist = lappend(neworlist, linitial(subclauses));
632  else
633  neworlist = lappend(neworlist, make_andclause(subclauses));
634  }
635  else
636  {
637  neworlist = NIL; /* degenerate case, see above */
638  break;
639  }
640  }
641  else
642  {
643  if (!list_member(winners, clause))
644  neworlist = lappend(neworlist, clause);
645  else
646  {
647  neworlist = NIL; /* degenerate case, see above */
648  break;
649  }
650  }
651  }
652 
653  /*
654  * Append reduced OR to the winners list, if it's not degenerate, handling
655  * the special case of one element correctly (can that really happen?).
656  * Also be careful to maintain AND/OR flatness in case we pulled up a
657  * sub-sub-OR-clause.
658  */
659  if (neworlist != NIL)
660  {
661  if (list_length(neworlist) == 1)
662  winners = lappend(winners, linitial(neworlist));
663  else
664  winners = lappend(winners, make_orclause(pull_ors(neworlist)));
665  }
666 
667  /*
668  * And return the constructed AND clause, again being wary of a single
669  * element and AND/OR flatness.
670  */
671  if (list_length(winners) == 1)
672  return (Expr *) linitial(winners);
673  else
674  return make_andclause(pull_ands(winners));
675 }
#define NIL
Definition: pg_list.h:65
static List * pull_ands(List *andlist)
Definition: prepqual.c:322
bool equal(const void *a, const void *b)
Definition: equalfuncs.c:3011
static bool is_andclause(const void *clause)
Definition: nodeFuncs.h:94
List * list_union(const List *list1, const List *list2)
Definition: list.c:916
Expr * make_orclause(List *orclauses)
Definition: makefuncs.c:649
#define list_make1(x1)
Definition: pg_list.h:227
#define linitial(l)
Definition: pg_list.h:195
bool list_member(const List *list, const void *datum)
Definition: list.c:614
Node * makeBoolConst(bool value, bool isnull)
Definition: makefuncs.c:355
Expr * make_andclause(List *andclauses)
Definition: makefuncs.c:633
List * lappend(List *list, void *datum)
Definition: list.c:322
#define lfirst(lc)
Definition: pg_list.h:190
static int list_length(const List *l)
Definition: pg_list.h:169
static List * pull_ors(List *orlist)
Definition: prepqual.c:348
List * list_difference(const List *list1, const List *list2)
Definition: list.c:1077
Definition: pg_list.h:50

◆ pull_ands()

static List * pull_ands ( List andlist)
static

Definition at line 322 of file prepqual.c.

References arg, generate_unaccent_rules::args, is_andclause(), lappend(), lfirst, list_concat(), and NIL.

Referenced by find_duplicate_ors(), and process_duplicate_ors().

323 {
324  List *out_list = NIL;
325  ListCell *arg;
326 
327  foreach(arg, andlist)
328  {
329  Node *subexpr = (Node *) lfirst(arg);
330 
331  if (is_andclause(subexpr))
332  out_list = list_concat(out_list,
333  pull_ands(((BoolExpr *) subexpr)->args));
334  else
335  out_list = lappend(out_list, subexpr);
336  }
337  return out_list;
338 }
#define NIL
Definition: pg_list.h:65
static List * pull_ands(List *andlist)
Definition: prepqual.c:322
static bool is_andclause(const void *clause)
Definition: nodeFuncs.h:94
Definition: nodes.h:525
List * list_concat(List *list1, const List *list2)
Definition: list.c:516
List * lappend(List *list, void *datum)
Definition: list.c:322
#define lfirst(lc)
Definition: pg_list.h:190
void * arg
Definition: pg_list.h:50

◆ pull_ors()

static List * pull_ors ( List orlist)
static

Definition at line 348 of file prepqual.c.

References arg, generate_unaccent_rules::args, is_orclause(), lappend(), lfirst, list_concat(), and NIL.

Referenced by find_duplicate_ors(), and process_duplicate_ors().

349 {
350  List *out_list = NIL;
351  ListCell *arg;
352 
353  foreach(arg, orlist)
354  {
355  Node *subexpr = (Node *) lfirst(arg);
356 
357  if (is_orclause(subexpr))
358  out_list = list_concat(out_list,
359  pull_ors(((BoolExpr *) subexpr)->args));
360  else
361  out_list = lappend(out_list, subexpr);
362  }
363  return out_list;
364 }
#define NIL
Definition: pg_list.h:65
static bool is_orclause(const void *clause)
Definition: nodeFuncs.h:103
Definition: nodes.h:525
List * list_concat(List *list1, const List *list2)
Definition: list.c:516
List * lappend(List *list, void *datum)
Definition: list.c:322
#define lfirst(lc)
Definition: pg_list.h:190
static List * pull_ors(List *orlist)
Definition: prepqual.c:348
void * arg
Definition: pg_list.h:50