Age Owner Branch data TLA Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * prepqual.c
4 : : * Routines for preprocessing qualification expressions
5 : : *
6 : : *
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.
13 : : *
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.
20 : : *
21 : : *
22 : : * Portions Copyright (c) 1996-2024, PostgreSQL Global Development Group
23 : : * Portions Copyright (c) 1994, Regents of the University of California
24 : : *
25 : : *
26 : : * IDENTIFICATION
27 : : * src/backend/optimizer/prep/prepqual.c
28 : : *
29 : : *-------------------------------------------------------------------------
30 : : */
31 : :
32 : : #include "postgres.h"
33 : :
34 : : #include "nodes/makefuncs.h"
35 : : #include "nodes/nodeFuncs.h"
36 : : #include "optimizer/optimizer.h"
37 : : #include "utils/lsyscache.h"
38 : :
39 : :
40 : : static List *pull_ands(List *andlist);
41 : : static List *pull_ors(List *orlist);
42 : : static Expr *find_duplicate_ors(Expr *qual, bool is_check);
43 : : static Expr *process_duplicate_ors(List *orlist);
44 : :
45 : :
46 : : /*
47 : : * negate_clause
48 : : * Negate a Boolean expression.
49 : : *
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.
52 : : *
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.
59 : : *
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.
71 : : */
72 : : Node *
4935 tgl@sss.pgh.pa.us 73 :CBC 12013 : negate_clause(Node *node)
74 : : {
75 [ - + ]: 12013 : if (node == NULL) /* should not happen */
4935 tgl@sss.pgh.pa.us 76 [ # # ]:UBC 0 : elog(ERROR, "can't negate an empty subexpression");
4935 tgl@sss.pgh.pa.us 77 [ + + + + :CBC 12013 : switch (nodeTag(node))
+ - + ]
78 : : {
79 : 45 : case T_Const:
80 : : {
81 : 45 : Const *c = (Const *) node;
82 : :
83 : : /* NOT NULL is still NULL */
84 [ - + ]: 45 : if (c->constisnull)
4935 tgl@sss.pgh.pa.us 85 :UBC 0 : return makeBoolConst(false, true);
86 : : /* otherwise pretty easy */
4935 tgl@sss.pgh.pa.us 87 :CBC 45 : return makeBoolConst(!DatumGetBool(c->constvalue), false);
88 : : }
89 : : break;
90 : 3618 : case T_OpExpr:
91 : : {
92 : : /*
93 : : * Negate operator if possible: (NOT (< A B)) => (>= A B)
94 : : */
95 : 3618 : OpExpr *opexpr = (OpExpr *) node;
96 : 3618 : Oid negator = get_negator(opexpr->opno);
97 : :
98 [ + + ]: 3618 : if (negator)
99 : : {
100 : 3495 : OpExpr *newopexpr = makeNode(OpExpr);
101 : :
102 : 3495 : newopexpr->opno = negator;
103 : 3495 : newopexpr->opfuncid = InvalidOid;
104 : 3495 : newopexpr->opresulttype = opexpr->opresulttype;
105 : 3495 : newopexpr->opretset = opexpr->opretset;
4769 106 : 3495 : newopexpr->opcollid = opexpr->opcollid;
107 : 3495 : newopexpr->inputcollid = opexpr->inputcollid;
4935 108 : 3495 : newopexpr->args = opexpr->args;
109 : 3495 : newopexpr->location = opexpr->location;
110 : 3495 : return (Node *) newopexpr;
111 : : }
112 : : }
113 : 123 : break;
114 : 239 : case T_ScalarArrayOpExpr:
115 : : {
116 : : /*
117 : : * Negate a ScalarArrayOpExpr if its operator has a negator;
118 : : * for example x = ANY (list) becomes x <> ALL (list)
119 : : */
120 : 239 : ScalarArrayOpExpr *saopexpr = (ScalarArrayOpExpr *) node;
121 : 239 : Oid negator = get_negator(saopexpr->opno);
122 : :
123 [ + - ]: 239 : if (negator)
124 : : {
125 : 239 : ScalarArrayOpExpr *newopexpr = makeNode(ScalarArrayOpExpr);
126 : :
127 : 239 : newopexpr->opno = negator;
128 : 239 : newopexpr->opfuncid = InvalidOid;
1102 drowley@postgresql.o 129 : 239 : newopexpr->hashfuncid = InvalidOid;
1012 130 : 239 : newopexpr->negfuncid = InvalidOid;
4935 tgl@sss.pgh.pa.us 131 : 239 : newopexpr->useOr = !saopexpr->useOr;
4769 132 : 239 : newopexpr->inputcollid = saopexpr->inputcollid;
4935 133 : 239 : newopexpr->args = saopexpr->args;
134 : 239 : newopexpr->location = saopexpr->location;
135 : 239 : return (Node *) newopexpr;
136 : : }
137 : : }
4935 tgl@sss.pgh.pa.us 138 :UBC 0 : break;
4935 tgl@sss.pgh.pa.us 139 :CBC 2248 : case T_BoolExpr:
140 : : {
141 : 2248 : BoolExpr *expr = (BoolExpr *) node;
142 : :
143 [ + + + - ]: 2248 : switch (expr->boolop)
144 : : {
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.
150 : : *
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 : : *--------------------
159 : : */
160 : 1855 : case AND_EXPR:
161 : : {
162 : 1855 : List *nargs = NIL;
163 : : ListCell *lc;
164 : :
165 [ + - + + : 6422 : foreach(lc, expr->args)
+ + ]
166 : : {
167 : 4567 : nargs = lappend(nargs,
168 : 4567 : negate_clause(lfirst(lc)));
169 : : }
170 : 1855 : return (Node *) make_orclause(nargs);
171 : : }
172 : : break;
173 : 345 : case OR_EXPR:
174 : : {
175 : 345 : List *nargs = NIL;
176 : : ListCell *lc;
177 : :
178 [ + - + + : 1466 : foreach(lc, expr->args)
+ + ]
179 : : {
180 : 1121 : nargs = lappend(nargs,
181 : 1121 : negate_clause(lfirst(lc)));
182 : : }
183 : 345 : return (Node *) make_andclause(nargs);
184 : : }
185 : : break;
186 : 48 : case NOT_EXPR:
187 : :
188 : : /*
189 : : * NOT underneath NOT: they cancel. We assume the
190 : : * input is already simplified, so no need to recurse.
191 : : */
192 : 48 : return (Node *) linitial(expr->args);
4935 tgl@sss.pgh.pa.us 193 :UBC 0 : default:
194 [ # # ]: 0 : elog(ERROR, "unrecognized boolop: %d",
195 : : (int) expr->boolop);
196 : : break;
197 : : }
198 : : }
199 : : break;
4935 tgl@sss.pgh.pa.us 200 :CBC 995 : case T_NullTest:
201 : : {
202 : 995 : NullTest *expr = (NullTest *) node;
203 : :
204 : : /*
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.
208 : : */
209 [ + - ]: 995 : if (!expr->argisrow)
210 : : {
211 : 995 : NullTest *newexpr = makeNode(NullTest);
212 : :
213 : 995 : newexpr->arg = expr->arg;
214 : 995 : newexpr->nulltesttype = (expr->nulltesttype == IS_NULL ?
215 : 995 : IS_NOT_NULL : IS_NULL);
216 : 995 : newexpr->argisrow = expr->argisrow;
3339 217 : 995 : newexpr->location = expr->location;
4935 218 : 995 : return (Node *) newexpr;
219 : : }
220 : : }
4935 tgl@sss.pgh.pa.us 221 :UBC 0 : break;
222 : 0 : case T_BooleanTest:
223 : : {
4753 bruce@momjian.us 224 : 0 : BooleanTest *expr = (BooleanTest *) node;
225 : 0 : BooleanTest *newexpr = makeNode(BooleanTest);
226 : :
4935 tgl@sss.pgh.pa.us 227 : 0 : newexpr->arg = expr->arg;
228 [ # # # # : 0 : switch (expr->booltesttype)
# # # ]
229 : : {
230 : 0 : case IS_TRUE:
231 : 0 : newexpr->booltesttype = IS_NOT_TRUE;
232 : 0 : break;
233 : 0 : case IS_NOT_TRUE:
234 : 0 : newexpr->booltesttype = IS_TRUE;
235 : 0 : break;
236 : 0 : case IS_FALSE:
237 : 0 : newexpr->booltesttype = IS_NOT_FALSE;
238 : 0 : break;
239 : 0 : case IS_NOT_FALSE:
240 : 0 : newexpr->booltesttype = IS_FALSE;
241 : 0 : break;
242 : 0 : case IS_UNKNOWN:
243 : 0 : newexpr->booltesttype = IS_NOT_UNKNOWN;
244 : 0 : break;
245 : 0 : case IS_NOT_UNKNOWN:
246 : 0 : newexpr->booltesttype = IS_UNKNOWN;
247 : 0 : break;
248 : 0 : default:
249 [ # # ]: 0 : elog(ERROR, "unrecognized booltesttype: %d",
250 : : (int) expr->booltesttype);
251 : : break;
252 : : }
3339 253 : 0 : newexpr->location = expr->location;
4935 254 : 0 : return (Node *) newexpr;
255 : : }
256 : : break;
4935 tgl@sss.pgh.pa.us 257 :CBC 4868 : default:
258 : : /* else fall through */
259 : 4868 : break;
260 : : }
261 : :
262 : : /*
263 : : * Otherwise we don't know how to simplify this, so just tack on an
264 : : * explicit NOT node.
265 : : */
266 : 4991 : return (Node *) make_notclause((Expr *) node);
267 : : }
268 : :
269 : :
270 : : /*
271 : : * canonicalize_qual
272 : : * Convert a qualification expression to the most useful form.
273 : : *
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.
278 : : *
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.
284 : : *
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
288 : : * tree.
289 : : *
290 : : * Returns the modified qualification.
291 : : */
292 : : Expr *
2226 293 : 142225 : canonicalize_qual(Expr *qual, bool is_check)
294 : : {
295 : : Expr *newqual;
296 : :
297 : : /* Quick exit for empty qual */
8980 298 [ - + ]: 142225 : if (qual == NULL)
7413 tgl@sss.pgh.pa.us 299 :UBC 0 : return NULL;
300 : :
301 : : /* This should not be invoked on quals in implicit-AND format */
2226 tgl@sss.pgh.pa.us 302 [ - + ]:CBC 142225 : Assert(!IsA(qual, List));
303 : :
304 : : /*
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.
308 : : */
309 : 142225 : newqual = find_duplicate_ors(qual, is_check);
310 : :
7413 311 : 142225 : return newqual;
312 : : }
313 : :
314 : :
315 : : /*
316 : : * pull_ands
317 : : * Recursively flatten nested AND clauses into a single and-clause list.
318 : : *
319 : : * Input is the arglist of an AND clause.
320 : : * Returns the rebuilt arglist (note original list structure is not touched).
321 : : */
322 : : static List *
8981 323 : 51080 : pull_ands(List *andlist)
324 : : {
7257 325 : 51080 : List *out_list = NIL;
326 : : ListCell *arg;
327 : :
8981 328 [ + - + + : 192671 : foreach(arg, andlist)
+ + ]
329 : : {
7413 330 : 141591 : Node *subexpr = (Node *) lfirst(arg);
331 : :
1902 332 [ - + ]: 141591 : if (is_andclause(subexpr))
7257 tgl@sss.pgh.pa.us 333 :UBC 0 : out_list = list_concat(out_list,
6756 bruce@momjian.us 334 : 0 : pull_ands(((BoolExpr *) subexpr)->args));
335 : : else
7257 tgl@sss.pgh.pa.us 336 :CBC 141591 : out_list = lappend(out_list, subexpr);
337 : : }
338 : 51080 : return out_list;
339 : : }
340 : :
341 : : /*
342 : : * pull_ors
343 : : * Recursively flatten nested OR clauses into a single or-clause list.
344 : : *
345 : : * Input is the arglist of an OR clause.
346 : : * Returns the rebuilt arglist (note original list structure is not touched).
347 : : */
348 : : static List *
7627 349 : 3924 : pull_ors(List *orlist)
350 : : {
7257 351 : 3924 : List *out_list = NIL;
352 : : ListCell *arg;
353 : :
7627 354 [ + - + + : 13280 : foreach(arg, orlist)
+ + ]
355 : : {
7413 356 : 9356 : Node *subexpr = (Node *) lfirst(arg);
357 : :
1902 358 [ - + ]: 9356 : if (is_orclause(subexpr))
7257 tgl@sss.pgh.pa.us 359 :UBC 0 : out_list = list_concat(out_list,
6756 bruce@momjian.us 360 : 0 : pull_ors(((BoolExpr *) subexpr)->args));
361 : : else
7257 tgl@sss.pgh.pa.us 362 :CBC 9356 : out_list = lappend(out_list, subexpr);
363 : : }
364 : 3924 : return out_list;
365 : : }
366 : :
367 : :
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.
373 : : *
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))
380 : : * is
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 : : *--------------------
387 : : */
388 : :
389 : : /*
390 : : * find_duplicate_ors
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.
394 : : *
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.
402 : : *
403 : : * Returns the modified qualification. AND/OR flatness is preserved.
404 : : */
405 : : static Expr *
2226 406 : 293181 : find_duplicate_ors(Expr *qual, bool is_check)
407 : : {
1902 408 [ + + ]: 293181 : if (is_orclause(qual))
409 : : {
7411 410 : 3927 : List *orlist = NIL;
411 : : ListCell *temp;
412 : :
413 : : /* Recurse */
7794 414 [ + - + + : 13289 : foreach(temp, ((BoolExpr *) qual)->args)
+ + ]
415 : : {
3638 416 : 9365 : Expr *arg = (Expr *) lfirst(temp);
417 : :
2226 418 : 9365 : arg = find_duplicate_ors(arg, is_check);
419 : :
420 : : /* Get rid of any constant inputs */
3638 421 [ + - + + ]: 9365 : if (arg && IsA(arg, Const))
422 : : {
423 : 6 : Const *carg = (Const *) arg;
424 : :
2226 425 [ + + ]: 6 : if (is_check)
426 : : {
427 : : /* Within OR in CHECK, drop constant FALSE */
428 [ - + - - ]: 3 : if (!carg->constisnull && !DatumGetBool(carg->constvalue))
2226 tgl@sss.pgh.pa.us 429 :UBC 0 : continue;
430 : : /* Constant TRUE or NULL, so OR reduces to TRUE */
2226 tgl@sss.pgh.pa.us 431 :CBC 3 : return (Expr *) makeBoolConst(true, false);
432 : : }
433 : : else
434 : : {
435 : : /* Within OR in WHERE, drop constant FALSE or NULL */
436 [ - + - - ]: 3 : if (carg->constisnull || !DatumGetBool(carg->constvalue))
437 : 3 : continue;
438 : : /* Constant TRUE, so OR reduces to TRUE */
2226 tgl@sss.pgh.pa.us 439 :UBC 0 : return arg;
440 : : }
441 : : }
442 : :
3638 tgl@sss.pgh.pa.us 443 :CBC 9359 : orlist = lappend(orlist, arg);
444 : : }
445 : :
446 : : /* Flatten any ORs pulled up to just below here */
447 : 3924 : orlist = pull_ors(orlist);
448 : :
449 : : /* Now we can look for duplicate ORs */
7411 450 : 3924 : return process_duplicate_ors(orlist);
451 : : }
1902 452 [ + + ]: 289254 : else if (is_andclause(qual))
453 : : {
7411 454 : 51080 : List *andlist = NIL;
455 : : ListCell *temp;
456 : :
457 : : /* Recurse */
7794 458 [ + - + + : 192671 : foreach(temp, ((BoolExpr *) qual)->args)
+ + ]
459 : : {
3638 460 : 141591 : Expr *arg = (Expr *) lfirst(temp);
461 : :
2226 462 : 141591 : arg = find_duplicate_ors(arg, is_check);
463 : :
464 : : /* Get rid of any constant inputs */
3638 465 [ + - - + ]: 141591 : if (arg && IsA(arg, Const))
466 : : {
3638 tgl@sss.pgh.pa.us 467 :UBC 0 : Const *carg = (Const *) arg;
468 : :
2226 469 [ # # ]: 0 : if (is_check)
470 : : {
471 : : /* Within AND in CHECK, drop constant TRUE or NULL */
472 [ # # # # ]: 0 : if (carg->constisnull || DatumGetBool(carg->constvalue))
473 : 0 : continue;
474 : : /* Constant FALSE, so AND reduces to FALSE */
475 : 0 : return arg;
476 : : }
477 : : else
478 : : {
479 : : /* Within AND in WHERE, drop constant TRUE */
480 [ # # # # ]: 0 : if (!carg->constisnull && DatumGetBool(carg->constvalue))
481 : 0 : continue;
482 : : /* Constant FALSE or NULL, so AND reduces to FALSE */
483 : 0 : return (Expr *) makeBoolConst(false, false);
484 : : }
485 : : }
486 : :
3638 tgl@sss.pgh.pa.us 487 :CBC 141591 : andlist = lappend(andlist, arg);
488 : : }
489 : :
490 : : /* Flatten any ANDs introduced just below here */
7411 491 : 51080 : andlist = pull_ands(andlist);
492 : :
493 : : /* AND of no inputs reduces to TRUE */
3638 494 [ - + ]: 51080 : if (andlist == NIL)
3638 tgl@sss.pgh.pa.us 495 :UBC 0 : return (Expr *) makeBoolConst(true, false);
496 : :
497 : : /* Single-expression AND just reduces to that expression */
3638 tgl@sss.pgh.pa.us 498 [ - + ]:CBC 51080 : if (list_length(andlist) == 1)
3638 tgl@sss.pgh.pa.us 499 :UBC 0 : return (Expr *) linitial(andlist);
500 : :
501 : : /* Else we still need an AND node */
7411 tgl@sss.pgh.pa.us 502 :CBC 51080 : return make_andclause(andlist);
503 : : }
504 : : else
9324 bruce@momjian.us 505 : 238174 : return qual;
506 : : }
507 : :
508 : : /*
509 : : * process_duplicate_ors
510 : : * Given a list of exprs which are ORed together, try to apply
511 : : * the inverse OR distributive law.
512 : : *
513 : : * Returns the resulting expression (could be an AND clause, an OR
514 : : * clause, or maybe even a single subexpression).
515 : : */
516 : : static Expr *
7411 tgl@sss.pgh.pa.us 517 : 3924 : process_duplicate_ors(List *orlist)
518 : : {
519 : 3924 : List *reference = NIL;
520 : 3924 : int num_subclauses = 0;
521 : : List *winners;
522 : : List *neworlist;
523 : : ListCell *temp;
524 : :
525 : : /* OR of no inputs reduces to FALSE */
8981 526 [ - + ]: 3924 : if (orlist == NIL)
3638 tgl@sss.pgh.pa.us 527 :UBC 0 : return (Expr *) makeBoolConst(false, false);
528 : :
529 : : /* Single-expression OR just reduces to that expression */
3638 tgl@sss.pgh.pa.us 530 [ + + ]:CBC 3924 : if (list_length(orlist) == 1)
531 : 3 : return (Expr *) linitial(orlist);
532 : :
533 : : /*
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.
538 : : */
8981 539 [ + - + + : 4482 : foreach(temp, orlist)
+ + ]
540 : : {
7263 neilc@samurai.com 541 : 4310 : Expr *clause = (Expr *) lfirst(temp);
542 : :
1902 tgl@sss.pgh.pa.us 543 [ + + ]: 4310 : if (is_andclause(clause))
544 : : {
7411 545 : 561 : List *subclauses = ((BoolExpr *) clause)->args;
7259 neilc@samurai.com 546 : 561 : int nclauses = list_length(subclauses);
547 : :
7411 tgl@sss.pgh.pa.us 548 [ + + + + ]: 561 : if (reference == NIL || nclauses < num_subclauses)
549 : : {
550 : 417 : reference = subclauses;
8981 551 : 417 : num_subclauses = nclauses;
552 : : }
553 : : }
554 : : else
555 : : {
7259 neilc@samurai.com 556 : 3749 : reference = list_make1(clause);
7411 tgl@sss.pgh.pa.us 557 : 3749 : break;
558 : : }
559 : : }
560 : :
561 : : /*
562 : : * Just in case, eliminate any duplicates in the reference list.
563 : : */
7259 neilc@samurai.com 564 : 3921 : reference = list_union(NIL, reference);
565 : :
566 : : /*
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.
569 : : */
7411 tgl@sss.pgh.pa.us 570 : 3921 : winners = NIL;
571 [ + - + + : 8020 : foreach(temp, reference)
+ + ]
572 : : {
7263 neilc@samurai.com 573 : 4099 : Expr *refclause = (Expr *) lfirst(temp);
7411 tgl@sss.pgh.pa.us 574 : 4099 : bool win = true;
575 : : ListCell *temp2;
576 : :
577 [ + - + - : 7910 : foreach(temp2, orlist)
+ - ]
578 : : {
7263 neilc@samurai.com 579 : 7910 : Expr *clause = (Expr *) lfirst(temp2);
580 : :
1902 tgl@sss.pgh.pa.us 581 [ + + ]: 7910 : if (is_andclause(clause))
582 : : {
7259 neilc@samurai.com 583 [ + + ]: 964 : if (!list_member(((BoolExpr *) clause)->args, refclause))
584 : : {
7411 tgl@sss.pgh.pa.us 585 : 718 : win = false;
586 : 718 : break;
587 : : }
588 : : }
589 : : else
590 : : {
591 [ + + ]: 6946 : if (!equal(refclause, clause))
592 : : {
593 : 3381 : win = false;
594 : 3381 : break;
595 : : }
596 : : }
597 : : }
598 : :
599 [ - + ]: 4099 : if (win)
7411 tgl@sss.pgh.pa.us 600 :UBC 0 : winners = lappend(winners, refclause);
601 : : }
602 : :
603 : : /*
604 : : * If no winners, we can't transform the OR
605 : : */
7411 tgl@sss.pgh.pa.us 606 [ + - ]:CBC 3921 : if (winners == NIL)
4 akorotkov@postgresql 607 : 3921 : return make_orclause(orlist);
608 : :
609 : : /*
610 : : * Generate new OR list consisting of the remaining sub-clauses.
611 : : *
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.
615 : : *
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.
618 : : */
7411 tgl@sss.pgh.pa.us 619 :UBC 0 : neworlist = NIL;
620 [ # # # # : 0 : foreach(temp, orlist)
# # ]
621 : : {
7263 neilc@samurai.com 622 : 0 : Expr *clause = (Expr *) lfirst(temp);
623 : :
1902 tgl@sss.pgh.pa.us 624 [ # # ]: 0 : if (is_andclause(clause))
625 : : {
7411 626 : 0 : List *subclauses = ((BoolExpr *) clause)->args;
627 : :
7259 neilc@samurai.com 628 : 0 : subclauses = list_difference(subclauses, winners);
7411 tgl@sss.pgh.pa.us 629 [ # # ]: 0 : if (subclauses != NIL)
630 : : {
7259 neilc@samurai.com 631 [ # # ]: 0 : if (list_length(subclauses) == 1)
7263 632 : 0 : neworlist = lappend(neworlist, linitial(subclauses));
633 : : else
7411 tgl@sss.pgh.pa.us 634 : 0 : neworlist = lappend(neworlist, make_andclause(subclauses));
635 : : }
636 : : else
637 : : {
7168 bruce@momjian.us 638 : 0 : neworlist = NIL; /* degenerate case, see above */
7411 tgl@sss.pgh.pa.us 639 : 0 : break;
640 : : }
641 : : }
642 : : else
643 : : {
7259 neilc@samurai.com 644 [ # # ]: 0 : if (!list_member(winners, clause))
7411 tgl@sss.pgh.pa.us 645 : 0 : neworlist = lappend(neworlist, clause);
646 : : else
647 : : {
7168 bruce@momjian.us 648 : 0 : neworlist = NIL; /* degenerate case, see above */
7411 tgl@sss.pgh.pa.us 649 : 0 : break;
650 : : }
651 : : }
652 : : }
653 : :
654 : : /*
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
658 : : * sub-sub-OR-clause.
659 : : */
660 [ # # ]: 0 : if (neworlist != NIL)
661 : : {
7259 neilc@samurai.com 662 [ # # ]: 0 : if (list_length(neworlist) == 1)
7263 663 : 0 : winners = lappend(winners, linitial(neworlist));
664 : : else
7411 tgl@sss.pgh.pa.us 665 : 0 : winners = lappend(winners, make_orclause(pull_ors(neworlist)));
666 : : }
667 : :
668 : : /*
669 : : * And return the constructed AND clause, again being wary of a single
670 : : * element and AND/OR flatness.
671 : : */
7259 neilc@samurai.com 672 [ # # ]: 0 : if (list_length(winners) == 1)
7263 673 : 0 : return (Expr *) linitial(winners);
674 : : else
7411 tgl@sss.pgh.pa.us 675 : 0 : return make_andclause(pull_ands(winners));
676 : : }
|
