Skip to content

Commit 5db2e83

Browse files
tglsfdctglsfdc
committed
Rethink the order of expression preprocessing: eval_const_expressions
really ought to run before canonicalize_qual, because it can now produce forms that canonicalize_qual knows how to improve (eg, NOT clauses). Also, because eval_const_expressions already knows about flattening nested ANDs and ORs into N-argument form, the initial flatten_andors pass in canonicalize_qual is now completely redundant and can be removed. This doesn't save a whole lot of code, but the time and palloc traffic eliminated is a useful gain on large expression trees.
1 parent bf3dbb5 commit 5db2e83

File tree

7 files changed

+61
-140
lines changed

7 files changed

+61
-140
lines changed

‎src/backend/optimizer/path/indxpath.c

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,7 @@
99
*
1010
*
1111
* IDENTIFICATION
12-
* $PostgreSQL: pgsql/src/backend/optimizer/path/indxpath.c,v 1.171 2005/03/27 06:29:36 tgl Exp $
12+
* $PostgreSQL: pgsql/src/backend/optimizer/path/indxpath.c,v 1.172 2005/03/28 00:58:22 tgl Exp $
1313
*
1414
*-------------------------------------------------------------------------
1515
*/
@@ -750,8 +750,8 @@ check_partial_indexes(Query *root, RelOptInfo *rel)
750750
* that the given predicate is true.
751751
*
752752
* The top-level List structure of each list corresponds to an AND list.
753-
* We assume that canonicalize_qual() has been applied and so there are
754-
* no un-flattened ANDs or ORs (e.g., no AND immediately within an AND,
753+
* We assume that eval_const_expressions() has been applied and so there
754+
* are no un-flattened ANDs or ORs (e.g., no AND immediately within an AND,
755755
* including AND just below the top-level List structure).
756756
* If this is not true we might fail to prove an implication that is
757757
* valid, but no worse consequences will ensue.

‎src/backend/optimizer/plan/planner.c

Lines changed: 11 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $PostgreSQL: pgsql/src/backend/optimizer/plan/planner.c,v 1.180 2005/03/17 23:44:26 neilc Exp $
11+
* $PostgreSQL: pgsql/src/backend/optimizer/plan/planner.c,v 1.181 2005/03/28 00:58:23 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -422,13 +422,17 @@ preprocess_expression(Query *parse, Node *expr, int kind)
422422
expr = flatten_join_alias_vars(parse, expr);
423423

424424
/*
425-
* If it's a qual or havingQual, canonicalize it. It seems most
426-
* useful to do this before applying eval_const_expressions, since the
427-
* latter can optimize flattened AND/ORs better than unflattened ones.
425+
* Simplify constant expressions.
428426
*
429-
* Note: all processing of a qual expression after this point must be
430-
* careful to maintain AND/OR flatness --- that is, do not generate a
431-
* tree with AND directly under AND, nor OR directly under OR.
427+
* Note: this also flattens nested AND and OR expressions into N-argument
428+
* form. All processing of a qual expression after this point must be
429+
* careful to maintain AND/OR flatness --- that is, do not generate a tree
430+
* with AND directly under AND, nor OR directly under OR.
431+
*/
432+
expr = eval_const_expressions(expr);
433+
434+
/*
435+
* If it's a qual or havingQual, canonicalize it.
432436
*/
433437
if (kind == EXPRKIND_QUAL)
434438
{
@@ -440,11 +444,6 @@ preprocess_expression(Query *parse, Node *expr, int kind)
440444
#endif
441445
}
442446

443-
/*
444-
* Simplify constant expressions.
445-
*/
446-
expr = eval_const_expressions(expr);
447-
448447
/* Expand SubLinks to SubPlans */
449448
if (parse->hasSubLinks)
450449
expr = SS_process_sublinks(expr, (kind == EXPRKIND_QUAL));

‎src/backend/optimizer/prep/prepqual.c

Lines changed: 24 additions & 103 deletions
Original file line numberDiff line numberDiff line change
@@ -3,12 +3,29 @@
33
* prepqual.c
44
* Routines for preprocessing qualification expressions
55
*
6+
*
7+
* The parser regards AND and OR as purely binary operators, so a qual like
8+
* (A = 1) OR (A = 2) OR (A = 3) ...
9+
* will produce a nested parsetree
10+
* (OR (A = 1) (OR (A = 2) (OR (A = 3) ...)))
11+
* In reality, the optimizer and executor regard AND and OR as N-argument
12+
* operators, so this tree can be flattened to
13+
* (OR (A = 1) (A = 2) (A = 3) ...)
14+
*
15+
* Formerly, this module was responsible for doing the initial flattening,
16+
* but now we leave it to eval_const_expressions to do that since it has to
17+
* make a complete pass over the expression tree anyway. Instead, we just
18+
* have to ensure that our manipulations preserve AND/OR flatness.
19+
* pull_ands() and pull_ors() are used to maintain flatness of the AND/OR
20+
* tree after local transformations that might introduce nested AND/ORs.
21+
*
22+
*
623
* Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
724
* Portions Copyright (c) 1994, Regents of the University of California
825
*
926
*
1027
* IDENTIFICATION
11-
* $PostgreSQL: pgsql/src/backend/optimizer/prep/prepqual.c,v 1.48 2004/12/31 22:00:20 pgsql Exp $
28+
* $PostgreSQL: pgsql/src/backend/optimizer/prep/prepqual.c,v 1.49 2005/03/28 00:58:23 tgl Exp $
1229
*
1330
*-------------------------------------------------------------------------
1431
*/
@@ -21,7 +38,6 @@
2138
#include "utils/lsyscache.h"
2239

2340

24-
static Node *flatten_andors_mutator(Node *node, void *context);
2541
static List *pull_ands(List *andlist);
2642
static List *pull_ors(List *orlist);
2743
static Expr *find_nots(Expr *qual);
@@ -40,6 +56,11 @@ static Expr *process_duplicate_ors(List *orlist);
4056
* actual usefulness, and so now the transformation doesn't involve any
4157
* notion of reaching a canonical form.
4258
*
59+
* NOTE: we assume the input has already been through eval_const_expressions
60+
* and therefore possesses AND/OR flatness. Formerly this function included
61+
* its own flattening logic, but that requires a useless extra pass over the
62+
* tree.
63+
*
4364
* Returns the modified qualification.
4465
*/
4566
Expr *
@@ -51,18 +72,13 @@ canonicalize_qual(Expr *qual)
5172
if (qual == NULL)
5273
return NULL;
5374

54-
/*
55-
* Flatten AND and OR groups throughout the expression tree.
56-
*/
57-
newqual = (Expr *) flatten_andors((Node *) qual);
58-
5975
/*
6076
* Push down NOTs. We do this only in the top-level boolean
6177
* expression, without examining arguments of operators/functions. The
6278
* main reason for doing this is to expose as much top-level AND/OR
6379
* structure as we can, so there's no point in descending further.
6480
*/
65-
newqual = find_nots(newqual);
81+
newqual = find_nots(qual);
6682

6783
/*
6884
* Pull up redundant subclauses in OR-of-AND trees. Again, we do this
@@ -74,101 +90,6 @@ canonicalize_qual(Expr *qual)
7490
}
7591

7692

77-
/*--------------------
78-
* The parser regards AND and OR as purely binary operators, so a qual like
79-
* (A = 1) OR (A = 2) OR (A = 3) ...
80-
* will produce a nested parsetree
81-
* (OR (A = 1) (OR (A = 2) (OR (A = 3) ...)))
82-
* In reality, the optimizer and executor regard AND and OR as n-argument
83-
* operators, so this tree can be flattened to
84-
* (OR (A = 1) (A = 2) (A = 3) ...)
85-
* which is the responsibility of the routines below.
86-
*
87-
* flatten_andors() does the basic transformation with no initial assumptions.
88-
* pull_ands() and pull_ors() are used to maintain flatness of the AND/OR
89-
* tree after local transformations that might introduce nested AND/ORs.
90-
*--------------------
91-
*/
92-
93-
/*
94-
* flatten_andors
95-
* Given an expression tree, simplify nested AND/OR clauses into flat
96-
* AND/OR clauses with more arguments. The entire tree is processed.
97-
*
98-
* Returns the rebuilt expr (note original structure is not touched).
99-
*
100-
* This is exported so that other modules can perform the part of
101-
* canonicalize_qual processing that applies to entire trees, rather
102-
* than just the top-level boolean expressions.
103-
*/
104-
Node *
105-
flatten_andors(Node *node)
106-
{
107-
return flatten_andors_mutator(node, NULL);
108-
}
109-
110-
static Node *
111-
flatten_andors_mutator(Node *node, void *context)
112-
{
113-
if (node == NULL)
114-
return NULL;
115-
if (IsA(node, BoolExpr))
116-
{
117-
BoolExpr *bexpr = (BoolExpr *) node;
118-
119-
if (bexpr->boolop == AND_EXPR)
120-
{
121-
List *out_list = NIL;
122-
ListCell *arg;
123-
124-
foreach(arg, bexpr->args)
125-
{
126-
Node *subexpr = flatten_andors((Node *) lfirst(arg));
127-
128-
/*
129-
* Note: we can destructively concat the subexpression's
130-
* arglist because we know the recursive invocation of
131-
* flatten_andors will have built a new arglist not shared
132-
* with any other expr. Otherwise we'd need a list_copy
133-
* here.
134-
*/
135-
if (and_clause(subexpr))
136-
out_list = list_concat(out_list,
137-
((BoolExpr *) subexpr)->args);
138-
else
139-
out_list = lappend(out_list, subexpr);
140-
}
141-
return (Node *) make_andclause(out_list);
142-
}
143-
if (bexpr->boolop == OR_EXPR)
144-
{
145-
List *out_list = NIL;
146-
ListCell *arg;
147-
148-
foreach(arg, bexpr->args)
149-
{
150-
Node *subexpr = flatten_andors((Node *) lfirst(arg));
151-
152-
/*
153-
* Note: we can destructively concat the subexpression's
154-
* arglist because we know the recursive invocation of
155-
* flatten_andors will have built a new arglist not shared
156-
* with any other expr. Otherwise we'd need a list_copy
157-
* here.
158-
*/
159-
if (or_clause(subexpr))
160-
out_list = list_concat(out_list,
161-
((BoolExpr *) subexpr)->args);
162-
else
163-
out_list = lappend(out_list, subexpr);
164-
}
165-
return (Node *) make_orclause(out_list);
166-
}
167-
/* else it's a NOT clause, fall through */
168-
}
169-
return expression_tree_mutator(node, flatten_andors_mutator, context);
170-
}
171-
17293
/*
17394
* pull_ands
17495
* Recursively flatten nested AND clauses into a single and-clause list.

‎src/backend/optimizer/util/clauses.c

Lines changed: 6 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $PostgreSQL: pgsql/src/backend/optimizer/util/clauses.c,v 1.189 2005/03/27 19:18:02 tgl Exp $
11+
* $PostgreSQL: pgsql/src/backend/optimizer/util/clauses.c,v 1.190 2005/03/28 00:58:24 tgl Exp $
1212
*
1313
* HISTORY
1414
* AUTHOR DATE MAJOR EVENT
@@ -1190,6 +1190,9 @@ rowtype_field_matches(Oid rowtypeid, int fieldnum,
11901190
*
11911191
* We assume that the tree has already been type-checked and contains
11921192
* only operators and functions that are reasonable to try to execute.
1193+
*
1194+
* NOTE: the planner assumes that this will always flatten nested AND and
1195+
* OR clauses into N-argument form. See comments in prepqual.c.
11931196
*--------------------
11941197
*/
11951198
Node *
@@ -1871,7 +1874,7 @@ eval_const_expressions_mutator(Node *node,
18711874
* is TRUE and at least one is NULL.
18721875
*
18731876
* This is split out as a subroutine so that we can recurse to fold sub-ORs
1874-
* into the upper OR clause, thereby preserving AND/OR flatness.
1877+
* into the upper OR clause, thereby ensuring that nested ORs are flattened.
18751878
*
18761879
* The output arguments *haveNull and *forceTrue must be initialized FALSE
18771880
* by the caller. They will be set TRUE if a null constant or true constant,
@@ -1931,7 +1934,7 @@ simplify_or_arguments(List *args, bool *haveNull, bool *forceTrue)
19311934
* is FALSE and at least one is NULL.
19321935
*
19331936
* This is split out as a subroutine so that we can recurse to fold sub-ANDs
1934-
* into the upper AND clause, thereby preserving AND/OR flatness.
1937+
* into the upper AND clause, thereby ensuring that nested ANDs are flattened.
19351938
*
19361939
* The output arguments *haveNull and *forceFalse must be initialized FALSE
19371940
* by the caller. They will be set TRUE if a null constant or false constant,

‎src/backend/optimizer/util/restrictinfo.c

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $PostgreSQL: pgsql/src/backend/optimizer/util/restrictinfo.c,v 1.31 2004/12/31 22:00:23 pgsql Exp $
11+
* $PostgreSQL: pgsql/src/backend/optimizer/util/restrictinfo.c,v 1.32 2005/03/28 00:58:24 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -63,7 +63,7 @@ make_restrictinfo(Expr *clause, bool is_pushed_down, bool valid_everywhere)
6363
}
6464
else
6565
{
66-
/* Shouldn't be an AND clause, else flatten_andors messed up */
66+
/* Shouldn't be an AND clause, else AND/OR flattening messed up */
6767
Assert(!and_clause((Node *) clause));
6868

6969
orclause = NULL;

‎src/backend/utils/cache/relcache.c

Lines changed: 14 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $PostgreSQL: pgsql/src/backend/utils/cache/relcache.c,v 1.216 2005/03/07 04:42:16 tgl Exp $
11+
* $PostgreSQL: pgsql/src/backend/utils/cache/relcache.c,v 1.217 2005/03/28 00:58:26 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -2788,14 +2788,11 @@ RelationGetIndexExpressions(Relation relation)
27882788
pfree(exprsString);
27892789

27902790
/*
2791-
* Run the expressions through flatten_andors and
2792-
* eval_const_expressions. This is not just an optimization, but is
2793-
* necessary, because the planner will be comparing them to
2794-
* similarly-processed qual clauses, and may fail to detect valid
2795-
* matches without this.
2791+
* Run the expressions through eval_const_expressions. This is not just an
2792+
* optimization, but is necessary, because the planner will be comparing
2793+
* them to similarly-processed qual clauses, and may fail to detect valid
2794+
* matches without this. We don't bother with canonicalize_qual, however.
27962795
*/
2797-
result = (List *) flatten_andors((Node *) result);
2798-
27992796
result = (List *) eval_const_expressions((Node *) result);
28002797

28012798
/*
@@ -2863,16 +2860,18 @@ RelationGetIndexPredicate(Relation relation)
28632860
pfree(predString);
28642861

28652862
/*
2866-
* Run the expression through canonicalize_qual and
2867-
* eval_const_expressions. This is not just an optimization, but is
2868-
* necessary, because the planner will be comparing it to
2869-
* similarly-processed qual clauses, and may fail to detect valid
2870-
* matches without this.
2863+
* Run the expression through const-simplification and canonicalization.
2864+
* This is not just an optimization, but is necessary, because the planner
2865+
* will be comparing it to similarly-processed qual clauses, and may fail
2866+
* to detect valid matches without this. This must match the processing
2867+
* done to qual clauses in preprocess_expression()! (We can skip the
2868+
* stuff involving subqueries, however, since we don't allow any in
2869+
* index predicates.)
28712870
*/
2872-
result = (List *) canonicalize_qual((Expr *) result);
2873-
28742871
result = (List *) eval_const_expressions((Node *) result);
28752872

2873+
result = (List *) canonicalize_qual((Expr *) result);
2874+
28762875
/*
28772876
* Also mark any coercion format fields as "don't care", so that the
28782877
* planner can match to both explicit and implicit coercions.

‎src/include/optimizer/prep.h

Lines changed: 1 addition & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,7 @@
77
* Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
88
* Portions Copyright (c) 1994, Regents of the University of California
99
*
10-
* $PostgreSQL: pgsql/src/include/optimizer/prep.h,v 1.48 2005/03/17 23:45:09 neilc Exp $
10+
* $PostgreSQL: pgsql/src/include/optimizer/prep.h,v 1.49 2005/03/28 00:58:26 tgl Exp $
1111
*
1212
*-------------------------------------------------------------------------
1313
*/
@@ -37,7 +37,6 @@ extern Relids get_relids_for_join(Query *parse, int joinrelid);
3737
* prototypes for prepqual.c
3838
*/
3939
extern Expr *canonicalize_qual(Expr *qual);
40-
extern Node *flatten_andors(Node *node);
4140

4241
/*
4342
* prototypes for preptlist.c

0 commit comments

Comments
 (0)