1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
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
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
|
/*-------------------------------------------------------------------------
*
* prepqual.c
* Routines for preprocessing qualification expressions
*
*
* While the parser will produce flattened (N-argument) AND/OR trees from
* simple sequences of AND'ed or OR'ed clauses, there might be an AND clause
* directly underneath another AND, or OR underneath OR, if the input was
* oddly parenthesized. Also, rule expansion and subquery flattening could
* produce such parsetrees. The planner wants to flatten all such cases
* to ensure consistent optimization behavior.
*
* Formerly, this module was responsible for doing the initial flattening,
* but now we leave it to eval_const_expressions to do that since it has to
* make a complete pass over the expression tree anyway. Instead, we just
* have to ensure that our manipulations preserve AND/OR flatness.
* pull_ands() and pull_ors() are used to maintain flatness of the AND/OR
* tree after local transformations that might introduce nested AND/ORs.
*
*
* Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
* Portions Copyright (c) 1994, Regents of the University of California
*
*
* IDENTIFICATION
* src/backend/optimizer/prep/prepqual.c
*
*-------------------------------------------------------------------------
*/
#include "postgres.h"
#include "nodes/makefuncs.h"
#include "nodes/nodeFuncs.h"
#include "optimizer/optimizer.h"
#include "optimizer/prep.h"
#include "utils/lsyscache.h"
static List *pull_ands(List *andlist);
static List *pull_ors(List *orlist);
static Expr *find_duplicate_ors(Expr *qual, bool is_check);
static Expr *process_duplicate_ors(List *orlist);
/*
* negate_clause
* Negate a Boolean expression.
*
* Input is a clause to be negated (e.g., the argument of a NOT clause).
* Returns a new clause equivalent to the negation of the given clause.
*
* Although this can be invoked on its own, it's mainly intended as a helper
* for eval_const_expressions(), and that context drives several design
* decisions. In particular, if the input is already AND/OR flat, we must
* preserve that property. We also don't bother to recurse in situations
* where we can assume that lower-level executions of eval_const_expressions
* would already have simplified sub-clauses of the input.
*
* The difference between this and a simple make_notclause() is that this
* tries to get rid of the NOT node by logical simplification. It's clearly
* always a win if the NOT node can be eliminated altogether. However, our
* use of DeMorgan's laws could result in having more NOT nodes rather than
* fewer. We do that unconditionally anyway, because in WHERE clauses it's
* important to expose as much top-level AND/OR structure as possible.
* Also, eliminating an intermediate NOT may allow us to flatten two levels
* of AND or OR together that we couldn't have otherwise. Finally, one of
* the motivations for doing this is to ensure that logically equivalent
* expressions will be seen as physically equal(), so we should always apply
* the same transformations.
*/
Node *
negate_clause(Node *node)
{
if (node == NULL) /* should not happen */
elog(ERROR, "can't negate an empty subexpression");
switch (nodeTag(node))
{
case T_Const:
{
Const *c = (Const *) node;
/* NOT NULL is still NULL */
if (c->constisnull)
return makeBoolConst(false, true);
/* otherwise pretty easy */
return makeBoolConst(!DatumGetBool(c->constvalue), false);
}
break;
case T_OpExpr:
{
/*
* Negate operator if possible: (NOT (< A B)) => (>= A B)
*/
OpExpr *opexpr = (OpExpr *) node;
Oid negator = get_negator(opexpr->opno);
if (negator)
{
OpExpr *newopexpr = makeNode(OpExpr);
newopexpr->opno = negator;
newopexpr->opfuncid = InvalidOid;
newopexpr->opresulttype = opexpr->opresulttype;
newopexpr->opretset = opexpr->opretset;
newopexpr->opcollid = opexpr->opcollid;
newopexpr->inputcollid = opexpr->inputcollid;
newopexpr->args = opexpr->args;
newopexpr->location = opexpr->location;
return (Node *) newopexpr;
}
}
break;
case T_ScalarArrayOpExpr:
{
/*
* Negate a ScalarArrayOpExpr if its operator has a negator;
* for example x = ANY (list) becomes x <> ALL (list)
*/
ScalarArrayOpExpr *saopexpr = (ScalarArrayOpExpr *) node;
Oid negator = get_negator(saopexpr->opno);
if (negator)
{
ScalarArrayOpExpr *newopexpr = makeNode(ScalarArrayOpExpr);
newopexpr->opno = negator;
newopexpr->opfuncid = InvalidOid;
newopexpr->hashfuncid = InvalidOid;
newopexpr->negfuncid = InvalidOid;
newopexpr->useOr = !saopexpr->useOr;
newopexpr->inputcollid = saopexpr->inputcollid;
newopexpr->args = saopexpr->args;
newopexpr->location = saopexpr->location;
return (Node *) newopexpr;
}
}
break;
case T_BoolExpr:
{
BoolExpr *expr = (BoolExpr *) node;
switch (expr->boolop)
{
/*--------------------
* Apply DeMorgan's Laws:
* (NOT (AND A B)) => (OR (NOT A) (NOT B))
* (NOT (OR A B)) => (AND (NOT A) (NOT B))
* i.e., swap AND for OR and negate each subclause.
*
* If the input is already AND/OR flat and has no NOT
* directly above AND or OR, this transformation preserves
* those properties. For example, if no direct child of
* the given AND clause is an AND or a NOT-above-OR, then
* the recursive calls of negate_clause() can't return any
* OR clauses. So we needn't call pull_ors() before
* building a new OR clause. Similarly for the OR case.
*--------------------
*/
case AND_EXPR:
{
List *nargs = NIL;
ListCell *lc;
foreach(lc, expr->args)
{
nargs = lappend(nargs,
negate_clause(lfirst(lc)));
}
return (Node *) make_orclause(nargs);
}
break;
case OR_EXPR:
{
List *nargs = NIL;
ListCell *lc;
foreach(lc, expr->args)
{
nargs = lappend(nargs,
negate_clause(lfirst(lc)));
}
return (Node *) make_andclause(nargs);
}
break;
case NOT_EXPR:
/*
* NOT underneath NOT: they cancel. We assume the
* input is already simplified, so no need to recurse.
*/
return (Node *) linitial(expr->args);
default:
elog(ERROR, "unrecognized boolop: %d",
(int) expr->boolop);
break;
}
}
break;
case T_NullTest:
{
NullTest *expr = (NullTest *) node;
/*
* In the rowtype case, the two flavors of NullTest are *not*
* logical inverses, so we can't simplify. But it does work
* for scalar datatypes.
*/
if (!expr->argisrow)
{
NullTest *newexpr = makeNode(NullTest);
newexpr->arg = expr->arg;
newexpr->nulltesttype = (expr->nulltesttype == IS_NULL ?
IS_NOT_NULL : IS_NULL);
newexpr->argisrow = expr->argisrow;
newexpr->location = expr->location;
return (Node *) newexpr;
}
}
break;
case T_BooleanTest:
{
BooleanTest *expr = (BooleanTest *) node;
BooleanTest *newexpr = makeNode(BooleanTest);
newexpr->arg = expr->arg;
switch (expr->booltesttype)
{
case IS_TRUE:
newexpr->booltesttype = IS_NOT_TRUE;
break;
case IS_NOT_TRUE:
newexpr->booltesttype = IS_TRUE;
break;
case IS_FALSE:
newexpr->booltesttype = IS_NOT_FALSE;
break;
case IS_NOT_FALSE:
newexpr->booltesttype = IS_FALSE;
break;
case IS_UNKNOWN:
newexpr->booltesttype = IS_NOT_UNKNOWN;
break;
case IS_NOT_UNKNOWN:
newexpr->booltesttype = IS_UNKNOWN;
break;
default:
elog(ERROR, "unrecognized booltesttype: %d",
(int) expr->booltesttype);
break;
}
newexpr->location = expr->location;
return (Node *) newexpr;
}
break;
default:
/* else fall through */
break;
}
/*
* Otherwise we don't know how to simplify this, so just tack on an
* explicit NOT node.
*/
return (Node *) make_notclause((Expr *) node);
}
/*
* canonicalize_qual
* Convert a qualification expression to the most useful form.
*
* This is primarily intended to be used on top-level WHERE (or JOIN/ON)
* clauses. It can also be used on top-level CHECK constraints, for which
* pass is_check = true. DO NOT call it on any expression that is not known
* to be one or the other, as it might apply inappropriate simplifications.
*
* The name of this routine is a holdover from a time when it would try to
* force the expression into canonical AND-of-ORs or OR-of-ANDs form.
* Eventually, we recognized that that had more theoretical purity than
* actual usefulness, and so now the transformation doesn't involve any
* notion of reaching a canonical form.
*
* NOTE: we assume the input has already been through eval_const_expressions
* and therefore possesses AND/OR flatness. Formerly this function included
* its own flattening logic, but that requires a useless extra pass over the
* tree.
*
* Returns the modified qualification.
*/
Expr *
canonicalize_qual(Expr *qual, bool is_check)
{
Expr *newqual;
/* Quick exit for empty qual */
if (qual == NULL)
return NULL;
/* This should not be invoked on quals in implicit-AND format */
Assert(!IsA(qual, List));
/*
* Pull up redundant subclauses in OR-of-AND trees. We do this only
* within the top-level AND/OR structure; there's no point in looking
* deeper. Also remove any NULL constants in the top-level structure.
*/
newqual = find_duplicate_ors(qual, is_check);
return newqual;
}
/*
* pull_ands
* Recursively flatten nested AND clauses into a single and-clause list.
*
* Input is the arglist of an AND clause.
* Returns the rebuilt arglist (note original list structure is not touched).
*/
static List *
pull_ands(List *andlist)
{
List *out_list = NIL;
ListCell *arg;
foreach(arg, andlist)
{
Node *subexpr = (Node *) lfirst(arg);
if (is_andclause(subexpr))
out_list = list_concat(out_list,
pull_ands(((BoolExpr *) subexpr)->args));
else
out_list = lappend(out_list, subexpr);
}
return out_list;
}
/*
* pull_ors
* Recursively flatten nested OR clauses into a single or-clause list.
*
* Input is the arglist of an OR clause.
* Returns the rebuilt arglist (note original list structure is not touched).
*/
static List *
pull_ors(List *orlist)
{
List *out_list = NIL;
ListCell *arg;
foreach(arg, orlist)
{
Node *subexpr = (Node *) lfirst(arg);
if (is_orclause(subexpr))
out_list = list_concat(out_list,
pull_ors(((BoolExpr *) subexpr)->args));
else
out_list = lappend(out_list, subexpr);
}
return out_list;
}
/*--------------------
* The following code attempts to apply the inverse OR distributive law:
* ((A AND B) OR (A AND C)) => (A AND (B OR C))
* That is, locate OR clauses in which every subclause contains an
* identical term, and pull out the duplicated terms.
*
* This may seem like a fairly useless activity, but it turns out to be
* applicable to many machine-generated queries, and there are also queries
* in some of the TPC benchmarks that need it. This was in fact almost the
* sole useful side-effect of the old prepqual code that tried to force
* the query into canonical AND-of-ORs form: the canonical equivalent of
* ((A AND B) OR (A AND C))
* is
* ((A OR A) AND (A OR C) AND (B OR A) AND (B OR C))
* which the code was able to simplify to
* (A AND (A OR C) AND (B OR A) AND (B OR C))
* thus successfully extracting the common condition A --- but at the cost
* of cluttering the qual with many redundant clauses.
*--------------------
*/
/*
* find_duplicate_ors
* Given a qualification tree with the NOTs pushed down, search for
* OR clauses to which the inverse OR distributive law might apply.
* Only the top-level AND/OR structure is searched.
*
* While at it, we remove any NULL constants within the top-level AND/OR
* structure, eg in a WHERE clause, "x OR NULL::boolean" is reduced to "x".
* In general that would change the result, so eval_const_expressions can't
* do it; but at top level of WHERE, we don't need to distinguish between
* FALSE and NULL results, so it's valid to treat NULL::boolean the same
* as FALSE and then simplify AND/OR accordingly. Conversely, in a top-level
* CHECK constraint, we may treat a NULL the same as TRUE.
*
* Returns the modified qualification. AND/OR flatness is preserved.
*/
static Expr *
find_duplicate_ors(Expr *qual, bool is_check)
{
if (is_orclause(qual))
{
List *orlist = NIL;
ListCell *temp;
/* Recurse */
foreach(temp, ((BoolExpr *) qual)->args)
{
Expr *arg = (Expr *) lfirst(temp);
arg = find_duplicate_ors(arg, is_check);
/* Get rid of any constant inputs */
if (arg && IsA(arg, Const))
{
Const *carg = (Const *) arg;
if (is_check)
{
/* Within OR in CHECK, drop constant FALSE */
if (!carg->constisnull && !DatumGetBool(carg->constvalue))
continue;
/* Constant TRUE or NULL, so OR reduces to TRUE */
return (Expr *) makeBoolConst(true, false);
}
else
{
/* Within OR in WHERE, drop constant FALSE or NULL */
if (carg->constisnull || !DatumGetBool(carg->constvalue))
continue;
/* Constant TRUE, so OR reduces to TRUE */
return arg;
}
}
orlist = lappend(orlist, arg);
}
/* Flatten any ORs pulled up to just below here */
orlist = pull_ors(orlist);
/* Now we can look for duplicate ORs */
return process_duplicate_ors(orlist);
}
else if (is_andclause(qual))
{
List *andlist = NIL;
ListCell *temp;
/* Recurse */
foreach(temp, ((BoolExpr *) qual)->args)
{
Expr *arg = (Expr *) lfirst(temp);
arg = find_duplicate_ors(arg, is_check);
/* Get rid of any constant inputs */
if (arg && IsA(arg, Const))
{
Const *carg = (Const *) arg;
if (is_check)
{
/* Within AND in CHECK, drop constant TRUE or NULL */
if (carg->constisnull || DatumGetBool(carg->constvalue))
continue;
/* Constant FALSE, so AND reduces to FALSE */
return arg;
}
else
{
/* Within AND in WHERE, drop constant TRUE */
if (!carg->constisnull && DatumGetBool(carg->constvalue))
continue;
/* Constant FALSE or NULL, so AND reduces to FALSE */
return (Expr *) makeBoolConst(false, false);
}
}
andlist = lappend(andlist, arg);
}
/* Flatten any ANDs introduced just below here */
andlist = pull_ands(andlist);
/* AND of no inputs reduces to TRUE */
if (andlist == NIL)
return (Expr *) makeBoolConst(true, false);
/* Single-expression AND just reduces to that expression */
if (list_length(andlist) == 1)
return (Expr *) linitial(andlist);
/* Else we still need an AND node */
return make_andclause(andlist);
}
else
return qual;
}
/*
* process_duplicate_ors
* Given a list of exprs which are ORed together, try to apply
* the inverse OR distributive law.
*
* Returns the resulting expression (could be an AND clause, an OR
* clause, or maybe even a single subexpression).
*/
static Expr *
process_duplicate_ors(List *orlist)
{
List *reference = NIL;
int num_subclauses = 0;
List *winners;
List *neworlist;
ListCell *temp;
/* OR of no inputs reduces to FALSE */
if (orlist == NIL)
return (Expr *) makeBoolConst(false, false);
/* Single-expression OR just reduces to that expression */
if (list_length(orlist) == 1)
return (Expr *) linitial(orlist);
/*
* Choose the shortest AND clause as the reference list --- obviously, any
* subclause not in this clause isn't in all the clauses. If we find a
* clause that's not an AND, we can treat it as a one-element AND clause,
* which necessarily wins as shortest.
*/
foreach(temp, orlist)
{
Expr *clause = (Expr *) lfirst(temp);
if (is_andclause(clause))
{
List *subclauses = ((BoolExpr *) clause)->args;
int nclauses = list_length(subclauses);
if (reference == NIL || nclauses < num_subclauses)
{
reference = subclauses;
num_subclauses = nclauses;
}
}
else
{
reference = list_make1(clause);
break;
}
}
/*
* Just in case, eliminate any duplicates in the reference list.
*/
reference = list_union(NIL, reference);
/*
* Check each element of the reference list to see if it's in all the OR
* clauses. Build a new list of winning clauses.
*/
winners = NIL;
foreach(temp, reference)
{
Expr *refclause = (Expr *) lfirst(temp);
bool win = true;
ListCell *temp2;
foreach(temp2, orlist)
{
Expr *clause = (Expr *) lfirst(temp2);
if (is_andclause(clause))
{
if (!list_member(((BoolExpr *) clause)->args, refclause))
{
win = false;
break;
}
}
else
{
if (!equal(refclause, clause))
{
win = false;
break;
}
}
}
if (win)
winners = lappend(winners, refclause);
}
/*
* If no winners, we can't transform the OR
*/
if (winners == NIL)
return make_orclause(orlist);
/*
* Generate new OR list consisting of the remaining sub-clauses.
*
* If any clause degenerates to empty, then we have a situation like (A
* AND B) OR (A), which can be reduced to just A --- that is, the
* additional conditions in other arms of the OR are irrelevant.
*
* Note that because we use list_difference, any multiple occurrences of a
* winning clause in an AND sub-clause will be removed automatically.
*/
neworlist = NIL;
foreach(temp, orlist)
{
Expr *clause = (Expr *) lfirst(temp);
if (is_andclause(clause))
{
List *subclauses = ((BoolExpr *) clause)->args;
subclauses = list_difference(subclauses, winners);
if (subclauses != NIL)
{
if (list_length(subclauses) == 1)
neworlist = lappend(neworlist, linitial(subclauses));
else
neworlist = lappend(neworlist, make_andclause(subclauses));
}
else
{
neworlist = NIL; /* degenerate case, see above */
break;
}
}
else
{
if (!list_member(winners, clause))
neworlist = lappend(neworlist, clause);
else
{
neworlist = NIL; /* degenerate case, see above */
break;
}
}
}
/*
* Append reduced OR to the winners list, if it's not degenerate, handling
* the special case of one element correctly (can that really happen?).
* Also be careful to maintain AND/OR flatness in case we pulled up a
* sub-sub-OR-clause.
*/
if (neworlist != NIL)
{
if (list_length(neworlist) == 1)
winners = lappend(winners, linitial(neworlist));
else
winners = lappend(winners, make_orclause(pull_ors(neworlist)));
}
/*
* And return the constructed AND clause, again being wary of a single
* element and AND/OR flatness.
*/
if (list_length(winners) == 1)
return (Expr *) linitial(winners);
else
return make_andclause(pull_ands(winners));
}
|