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 294 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().

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

◆ find_duplicate_ors()

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

Definition at line 407 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().

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

◆ 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(), ScalarArrayOpExpr::hashfuncid, 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(), ScalarArrayOpExpr::negfuncid, 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->hashfuncid = InvalidOid;
131  newopexpr->negfuncid = InvalidOid;
132  newopexpr->useOr = !saopexpr->useOr;
133  newopexpr->inputcollid = saopexpr->inputcollid;
134  newopexpr->args = saopexpr->args;
135  newopexpr->location = saopexpr->location;
136  return (Node *) newopexpr;
137  }
138  }
139  break;
140  case T_BoolExpr:
141  {
142  BoolExpr *expr = (BoolExpr *) node;
143 
144  switch (expr->boolop)
145  {
146  /*--------------------
147  * Apply DeMorgan's Laws:
148  * (NOT (AND A B)) => (OR (NOT A) (NOT B))
149  * (NOT (OR A B)) => (AND (NOT A) (NOT B))
150  * i.e., swap AND for OR and negate each subclause.
151  *
152  * If the input is already AND/OR flat and has no NOT
153  * directly above AND or OR, this transformation preserves
154  * those properties. For example, if no direct child of
155  * the given AND clause is an AND or a NOT-above-OR, then
156  * the recursive calls of negate_clause() can't return any
157  * OR clauses. So we needn't call pull_ors() before
158  * building a new OR clause. Similarly for the OR case.
159  *--------------------
160  */
161  case AND_EXPR:
162  {
163  List *nargs = NIL;
164  ListCell *lc;
165 
166  foreach(lc, expr->args)
167  {
168  nargs = lappend(nargs,
169  negate_clause(lfirst(lc)));
170  }
171  return (Node *) make_orclause(nargs);
172  }
173  break;
174  case OR_EXPR:
175  {
176  List *nargs = NIL;
177  ListCell *lc;
178 
179  foreach(lc, expr->args)
180  {
181  nargs = lappend(nargs,
182  negate_clause(lfirst(lc)));
183  }
184  return (Node *) make_andclause(nargs);
185  }
186  break;
187  case NOT_EXPR:
188 
189  /*
190  * NOT underneath NOT: they cancel. We assume the
191  * input is already simplified, so no need to recurse.
192  */
193  return (Node *) linitial(expr->args);
194  default:
195  elog(ERROR, "unrecognized boolop: %d",
196  (int) expr->boolop);
197  break;
198  }
199  }
200  break;
201  case T_NullTest:
202  {
203  NullTest *expr = (NullTest *) node;
204 
205  /*
206  * In the rowtype case, the two flavors of NullTest are *not*
207  * logical inverses, so we can't simplify. But it does work
208  * for scalar datatypes.
209  */
210  if (!expr->argisrow)
211  {
212  NullTest *newexpr = makeNode(NullTest);
213 
214  newexpr->arg = expr->arg;
215  newexpr->nulltesttype = (expr->nulltesttype == IS_NULL ?
216  IS_NOT_NULL : IS_NULL);
217  newexpr->argisrow = expr->argisrow;
218  newexpr->location = expr->location;
219  return (Node *) newexpr;
220  }
221  }
222  break;
223  case T_BooleanTest:
224  {
225  BooleanTest *expr = (BooleanTest *) node;
226  BooleanTest *newexpr = makeNode(BooleanTest);
227 
228  newexpr->arg = expr->arg;
229  switch (expr->booltesttype)
230  {
231  case IS_TRUE:
232  newexpr->booltesttype = IS_NOT_TRUE;
233  break;
234  case IS_NOT_TRUE:
235  newexpr->booltesttype = IS_TRUE;
236  break;
237  case IS_FALSE:
238  newexpr->booltesttype = IS_NOT_FALSE;
239  break;
240  case IS_NOT_FALSE:
241  newexpr->booltesttype = IS_FALSE;
242  break;
243  case IS_UNKNOWN:
244  newexpr->booltesttype = IS_NOT_UNKNOWN;
245  break;
246  case IS_NOT_UNKNOWN:
247  newexpr->booltesttype = IS_UNKNOWN;
248  break;
249  default:
250  elog(ERROR, "unrecognized booltesttype: %d",
251  (int) expr->booltesttype);
252  break;
253  }
254  newexpr->location = expr->location;
255  return (Node *) newexpr;
256  }
257  break;
258  default:
259  /* else fall through */
260  break;
261  }
262 
263  /*
264  * Otherwise we don't know how to simplify this, so just tack on an
265  * explicit NOT node.
266  */
267  return (Node *) make_notclause((Expr *) node);
268 }
Datum constvalue
Definition: primnodes.h:219
#define NIL
Definition: pg_list.h:65
Expr * make_notclause(Expr *notclause)
Definition: makefuncs.c:668
Node * negate_clause(Node *node)
Definition: prepqual.c:74
Definition: nodes.h:536
unsigned int Oid
Definition: postgres_ext.h:31
Expr * make_orclause(List *orclauses)
Definition: makefuncs.c:652
Oid opresulttype
Definition: primnodes.h:544
#define linitial(l)
Definition: pg_list.h:174
#define ERROR
Definition: elog.h:46
BoolExprType boolop
Definition: primnodes.h:625
Node * makeBoolConst(bool value, bool isnull)
Definition: makefuncs.c:357
Expr * arg
Definition: primnodes.h:1265
char * c
Expr * make_andclause(List *andclauses)
Definition: makefuncs.c:636
int location
Definition: primnodes.h:549
Expr * arg
Definition: primnodes.h:1288
#define DatumGetBool(X)
Definition: postgres.h:437
Oid opcollid
Definition: primnodes.h:546
Definition: nodes.h:157
List * lappend(List *list, void *datum)
Definition: list.c:336
BoolTestType booltesttype
Definition: primnodes.h:1289
Oid opfuncid
Definition: primnodes.h:543
NullTestType nulltesttype
Definition: primnodes.h:1266
#define InvalidOid
Definition: postgres_ext.h:36
#define makeNode(_type_)
Definition: nodes.h:584
#define lfirst(lc)
Definition: pg_list.h:169
int location
Definition: primnodes.h:1268
Oid inputcollid
Definition: primnodes.h:547
List * args
Definition: primnodes.h:626
#define nodeTag(nodeptr)
Definition: nodes.h:541
#define elog(elevel,...)
Definition: elog.h:232
bool argisrow
Definition: primnodes.h:1267
Oid opno
Definition: primnodes.h:542
Oid get_negator(Oid opno)
Definition: lsyscache.c:1504
List * args
Definition: primnodes.h:548
Definition: pg_list.h:50
bool constisnull
Definition: primnodes.h:220
bool opretset
Definition: primnodes.h:545

◆ process_duplicate_ors()

static Expr * process_duplicate_ors ( List orlist)
static

Definition at line 518 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().

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

◆ pull_ands()

static List * pull_ands ( List andlist)
static

Definition at line 324 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().

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

◆ pull_ors()

static List * pull_ors ( List orlist)
static

Definition at line 350 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().

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