Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit5db2e83

Browse files
committed
Rethink the order of expression preprocessing: eval_const_expressions
really ought to run before canonicalize_qual, because it can now produceforms that canonicalize_qual knows how to improve (eg, NOT clauses).Also, because eval_const_expressions already knows about flatteningnested ANDs and ORs into N-argument form, the initial flatten_andorspass in canonicalize_qual is now completely redundant and can beremoved. This doesn't save a whole lot of code, but the time andpalloc traffic eliminated is a useful gain on large expression trees.
1 parentbf3dbb5 commit5db2e83

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 thatcanonicalize_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 thateval_const_expressions() has been applied and so there
754+
*areno 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/2800:58:23 tgl Exp $
1229
*
1330
*-------------------------------------------------------------------------
1431
*/
@@ -21,7 +38,6 @@
2138
#include"utils/lsyscache.h"
2239

2340

24-
staticNode*flatten_andors_mutator(Node*node,void*context);
2541
staticList*pull_ands(List*andlist);
2642
staticList*pull_ors(List*orlist);
2743
staticExpr*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
returnNULL;
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-
returnflatten_andors_mutator(node,NULL);
108-
}
109-
110-
staticNode*
111-
flatten_andors_mutator(Node*node,void*context)
112-
{
113-
if (node==NULL)
114-
returnNULL;
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-
returnexpression_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
* AUTHORDATEMAJOR 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, therebypreserving AND/OR flatness.
1877+
* into the upper OR clause, therebyensuring 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, therebypreserving AND/OR flatness.
1937+
* into the upper AND clause, therebyensuring 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/2800: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, elseflatten_andors messed up */
66+
/* Shouldn't be an AND clause, elseAND/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
externExpr*canonicalize_qual(Expr*qual);
40-
externNode*flatten_andors(Node*node);
4140

4241
/*
4342
* prototypes for preptlist.c

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp