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

Commit2146f13

Browse files
committed
Avoid recursion when processing simple lists of AND'ed or OR'ed clauses.
Since most of the system thinks AND and OR are N-argument expressionsanyway, let's have the grammar generate a representation of that form whendealing with input like "x AND y AND z AND ...", rather than generatinga deeply-nested binary tree that just has to be flattened later by theplanner. This avoids stack overflow in parse analysis when dealing withqueries having more than a few thousand such clauses; and in any case itremoves some rather unsightly inconsistencies, since some parts of parseanalysis were generating N-argument ANDs/ORs already.It's still possible to get a stack overflow with weirdly parenthesizedinput, such as "x AND (y AND (z AND ( ... )))", but such cases are notmainstream usage. The maximum depth of parenthesization is alreadylimited by Bison's stack in such cases, anyway, so that the limit isprobably fairly platform-independent.Patch originally by Gurjeet Singh, heavily revised by me
1 parentac608fe commit2146f13

File tree

12 files changed

+155
-141
lines changed

12 files changed

+155
-141
lines changed

‎contrib/postgres_fdw/deparse.c

Lines changed: 0 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1716,9 +1716,6 @@ deparseRelabelType(RelabelType *node, deparse_expr_cxt *context)
17161716

17171717
/*
17181718
* Deparse a BoolExpr node.
1719-
*
1720-
* Note: by the time we get here, AND and OR expressions have been flattened
1721-
* into N-argument form, so we'd better be prepared to deal with that.
17221719
*/
17231720
staticvoid
17241721
deparseBoolExpr(BoolExpr*node,deparse_expr_cxt*context)

‎src/backend/nodes/nodeFuncs.c

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -3047,6 +3047,14 @@ raw_expression_tree_walker(Node *node,
30473047
/* operator name is deemed uninteresting */
30483048
}
30493049
break;
3050+
caseT_BoolExpr:
3051+
{
3052+
BoolExpr*expr= (BoolExpr*)node;
3053+
3054+
if (walker(expr->args,context))
3055+
return true;
3056+
}
3057+
break;
30503058
caseT_ColumnRef:
30513059
/* we assume the fields contain nothing interesting */
30523060
break;

‎src/backend/nodes/outfuncs.c

Lines changed: 0 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -2437,15 +2437,6 @@ _outAExpr(StringInfo str, const A_Expr *node)
24372437
appendStringInfoChar(str,' ');
24382438
WRITE_NODE_FIELD(name);
24392439
break;
2440-
caseAEXPR_AND:
2441-
appendStringInfoString(str," AND");
2442-
break;
2443-
caseAEXPR_OR:
2444-
appendStringInfoString(str," OR");
2445-
break;
2446-
caseAEXPR_NOT:
2447-
appendStringInfoString(str," NOT");
2448-
break;
24492440
caseAEXPR_OP_ANY:
24502441
appendStringInfoChar(str,' ');
24512442
WRITE_NODE_FIELD(name);

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

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -133,9 +133,9 @@ static Node *find_jointree_node_for_rel(Node *jtnode, int relid);
133133
* transformations if any are found.
134134
*
135135
* This routine has to run before preprocess_expression(), so the quals
136-
* clauses are not yet reduced to implicit-AND format. That means we need
137-
* torecursively search through explicit AND clauses, which are
138-
*probably only binary ANDs. We stop as soon as we hit a non-AND item.
136+
* clauses are not yet reduced to implicit-AND format, and are not guaranteed
137+
* tobe AND/OR-flat either. That means we need to recursively search through
138+
*explicit AND clauses. We stop as soon as we hit a non-AND item.
139139
*/
140140
void
141141
pull_up_sublinks(PlannerInfo*root)

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

Lines changed: 6 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -4,13 +4,12 @@
44
* Routines for preprocessing qualification expressions
55
*
66
*
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) ...)
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.
1413
*
1514
* Formerly, this module was responsible for doing the initial flattening,
1615
* but now we leave it to eval_const_expressions to do that since it has to

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

Lines changed: 9 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -3447,12 +3447,15 @@ simplify_or_arguments(List *args,
34473447
List*unprocessed_args;
34483448

34493449
/*
3450-
* Since the parser considers OR to be a binary operator, long OR lists
3451-
* become deeply nested expressions. We must flatten these into long
3452-
* argument lists of a single OR operator. To avoid blowing out the stack
3453-
* with recursion of eval_const_expressions, we resort to some tenseness
3454-
* here: we keep a list of not-yet-processed inputs, and handle flattening
3455-
* of nested ORs by prepending to the to-do list instead of recursing.
3450+
* We want to ensure that any OR immediately beneath another OR gets
3451+
* flattened into a single OR-list, so as to simplify later reasoning.
3452+
*
3453+
* To avoid stack overflow from recursion of eval_const_expressions, we
3454+
* resort to some tenseness here: we keep a list of not-yet-processed
3455+
* inputs, and handle flattening of nested ORs by prepending to the to-do
3456+
* list instead of recursing. Now that the parser generates N-argument
3457+
* ORs from simple lists, this complexity is probably less necessary than
3458+
* it once was, but we might as well keep the logic.
34563459
*/
34573460
unprocessed_args=list_copy(args);
34583461
while (unprocessed_args)

‎src/backend/parser/gram.y

Lines changed: 75 additions & 35 deletions
Original file line numberDiff line numberDiff line change
@@ -151,6 +151,9 @@ static void insertSelectOptions(SelectStmt *stmt,
151151
static Node *makeSetOp(SetOperation op,bool all, Node *larg, Node *rarg);
152152
static Node *doNegate(Node *n,int location);
153153
staticvoiddoNegateFloat(Value *v);
154+
static Node *makeAndExpr(Node *lexpr, Node *rexpr,int location);
155+
static Node *makeOrExpr(Node *lexpr, Node *rexpr,int location);
156+
static Node *makeNotExpr(Node *expr,int location);
154157
static Node *makeAArrayExpr(List *elements,int location);
155158
static Node *makeXmlExpr(XmlExprOp op,char *name, List *named_args,
156159
List *args,int location);
@@ -10849,11 +10852,11 @@ a_expr:c_expr{ $$ = $1; }
1084910852
{$$ = (Node *) makeA_Expr(AEXPR_OP,$2,$1,NULL,@2); }
1085010853

1085110854
|a_exprANDa_expr
10852-
{$$ =(Node *) makeA_Expr(AEXPR_AND, NIL,$1,$3,@2); }
10855+
{$$ =makeAndExpr($1,$3,@2); }
1085310856
|a_exprORa_expr
10854-
{$$ =(Node *) makeA_Expr(AEXPR_OR, NIL,$1,$3,@2); }
10857+
{$$ =makeOrExpr($1,$3,@2); }
1085510858
|NOTa_expr
10856-
{$$ =(Node *) makeA_Expr(AEXPR_NOT, NIL,NULL,$2,@1); }
10859+
{$$ =makeNotExpr($2,@1); }
1085710860

1085810861
|a_exprLIKEa_expr
1085910862
{$$ = (Node *) makeSimpleA_Expr(AEXPR_OP,"~~",$1,$3,@2); }
@@ -11022,11 +11025,9 @@ a_expr:c_expr{ $$ = $1; }
1102211025
}
1102311026
|a_exprISNOTDISTINCTFROMa_expr%precIS
1102411027
{
11025-
$$ = (Node *) makeA_Expr(AEXPR_NOT, NIL,NULL,
11026-
(Node *) makeSimpleA_Expr(AEXPR_DISTINCT,
11027-
"=",$1,$6,@2),
11028-
@2);
11029-
11028+
$$ = makeNotExpr((Node *) makeSimpleA_Expr(AEXPR_DISTINCT,
11029+
"=",$1,$6,@2),
11030+
@2);
1103011031
}
1103111032
|a_exprISOF'('type_list')'%precIS
1103211033
{
@@ -11044,43 +11045,43 @@ a_expr:c_expr{ $$ = $1; }
1104411045
*/
1104511046
|a_exprBETWEENopt_asymmetricb_exprANDb_expr%precBETWEEN
1104611047
{
11047-
$$ =(Node *) makeA_Expr(AEXPR_AND, NIL,
11048+
$$ =makeAndExpr(
1104811049
(Node *) makeSimpleA_Expr(AEXPR_OP,">=",$1,$4,@2),
1104911050
(Node *) makeSimpleA_Expr(AEXPR_OP,"<=",$1,$6,@2),
11050-
@2);
11051+
@2);
1105111052
}
1105211053
|a_exprNOTBETWEENopt_asymmetricb_exprANDb_expr%precBETWEEN
1105311054
{
11054-
$$ =(Node *) makeA_Expr(AEXPR_OR, NIL,
11055+
$$ =makeOrExpr(
1105511056
(Node *) makeSimpleA_Expr(AEXPR_OP,"<",$1,$5,@2),
1105611057
(Node *) makeSimpleA_Expr(AEXPR_OP,">",$1,$7,@2),
11057-
@2);
11058+
@2);
1105811059
}
1105911060
|a_exprBETWEENSYMMETRICb_exprANDb_expr%precBETWEEN
1106011061
{
11061-
$$ =(Node *) makeA_Expr(AEXPR_OR, NIL,
11062-
(Node *) makeA_Expr(AEXPR_AND, NIL,
11062+
$$ =makeOrExpr(
11063+
makeAndExpr(
1106311064
(Node *) makeSimpleA_Expr(AEXPR_OP,">=", $1, $4, @2),
1106411065
(Node *) makeSimpleA_Expr(AEXPR_OP,"<=", $1, $6, @2),
11065-
@2),
11066-
(Node *) makeA_Expr(AEXPR_AND, NIL,
11066+
@2),
11067+
makeAndExpr(
1106711068
(Node *) makeSimpleA_Expr(AEXPR_OP,">=", $1, $6, @2),
1106811069
(Node *) makeSimpleA_Expr(AEXPR_OP,"<=", $1, $4, @2),
11069-
@2),
11070-
@2);
11070+
@2),
11071+
@2);
1107111072
}
1107211073
|a_exprNOTBETWEENSYMMETRICb_exprANDb_expr%precBETWEEN
1107311074
{
11074-
$$ =(Node *) makeA_Expr(AEXPR_AND, NIL,
11075-
(Node *) makeA_Expr(AEXPR_OR, NIL,
11075+
$$ =makeAndExpr(
11076+
makeOrExpr(
1107611077
(Node *) makeSimpleA_Expr(AEXPR_OP,"<", $1, $5, @2),
1107711078
(Node *) makeSimpleA_Expr(AEXPR_OP,">", $1, $7, @2),
11078-
@2),
11079-
(Node *) makeA_Expr(AEXPR_OR, NIL,
11079+
@2),
11080+
makeOrExpr(
1108011081
(Node *) makeSimpleA_Expr(AEXPR_OP,"<", $1, $7, @2),
1108111082
(Node *) makeSimpleA_Expr(AEXPR_OP,">", $1, $5, @2),
11082-
@2),
11083-
@2);
11083+
@2),
11084+
@2);
1108411085
}
1108511086
|a_exprIN_Pin_expr
1108611087
{
@@ -11114,7 +11115,7 @@ a_expr:c_expr{ $$ = $1; }
1111411115
n->operName = list_make1(makeString("="));
1111511116
n->location =@3;
1111611117
/* Stick a NOT on top*/
11117-
$$ =(Node *) makeA_Expr(AEXPR_NOT, NIL,NULL,(Node *) n,@2);
11118+
$$ =makeNotExpr((Node *) n,@2);
1111811119
}
1111911120
else
1112011121
{
@@ -11162,10 +11163,9 @@ a_expr:c_expr{ $$ = $1; }
1116211163
}
1116311164
|a_exprISNOTDOCUMENT_P%precIS
1116411165
{
11165-
$$ = (Node *) makeA_Expr(AEXPR_NOT, NIL,NULL,
11166-
makeXmlExpr(IS_DOCUMENT,NULL, NIL,
11167-
list_make1($1), @2),
11168-
@2);
11166+
$$ = makeNotExpr(makeXmlExpr(IS_DOCUMENT,NULL, NIL,
11167+
list_make1($1), @2),
11168+
@2);
1116911169
}
1117011170
;
1117111171

@@ -11216,8 +11216,9 @@ b_expr:c_expr
1121611216
}
1121711217
|b_exprISNOTDISTINCTFROMb_expr%precIS
1121811218
{
11219-
$$ = (Node *)makeA_Expr(AEXPR_NOT, NIL,
11220-
NULL, (Node *)makeSimpleA_Expr(AEXPR_DISTINCT,"=", $1, $6, @2), @2);
11219+
$$ = makeNotExpr((Node *) makeSimpleA_Expr(AEXPR_DISTINCT,
11220+
"=",$1,$6,@2),
11221+
@2);
1122111222
}
1122211223
|b_exprISOF'('type_list')'%precIS
1122311224
{
@@ -11234,10 +11235,9 @@ b_expr:c_expr
1123411235
}
1123511236
|b_exprISNOTDOCUMENT_P%precIS
1123611237
{
11237-
$$ = (Node *)makeA_Expr(AEXPR_NOT, NIL,NULL,
11238-
makeXmlExpr(IS_DOCUMENT,NULL, NIL,
11239-
list_make1($1), @2),
11240-
@2);
11238+
$$ = makeNotExpr(makeXmlExpr(IS_DOCUMENT,NULL, NIL,
11239+
list_make1($1), @2),
11240+
@2);
1124111241
}
1124211242
;
1124311243

@@ -13692,6 +13692,46 @@ doNegateFloat(Value *v)
1369213692
v->val.str = psprintf("-%s", oldval);
1369313693
}
1369413694

13695+
static Node *
13696+
makeAndExpr(Node *lexpr, Node *rexpr, int location)
13697+
{
13698+
/* Flatten "a AND b AND c ..." to a single BoolExpr on sight*/
13699+
if (IsA(lexpr, BoolExpr))
13700+
{
13701+
BoolExpr *blexpr = (BoolExpr *) lexpr;
13702+
13703+
if (blexpr->boolop == AND_EXPR)
13704+
{
13705+
blexpr->args = lappend(blexpr->args, rexpr);
13706+
return (Node *) blexpr;
13707+
}
13708+
}
13709+
return (Node *) makeBoolExpr(AND_EXPR, list_make2(lexpr, rexpr), location);
13710+
}
13711+
13712+
static Node *
13713+
makeOrExpr(Node *lexpr, Node *rexpr, int location)
13714+
{
13715+
/* Flatten "a OR b OR c ..." to a single BoolExpr on sight*/
13716+
if (IsA(lexpr, BoolExpr))
13717+
{
13718+
BoolExpr *blexpr = (BoolExpr *) lexpr;
13719+
13720+
if (blexpr->boolop == OR_EXPR)
13721+
{
13722+
blexpr->args = lappend(blexpr->args, rexpr);
13723+
return (Node *) blexpr;
13724+
}
13725+
}
13726+
return (Node *) makeBoolExpr(OR_EXPR, list_make2(lexpr, rexpr), location);
13727+
}
13728+
13729+
static Node *
13730+
makeNotExpr(Node *expr, int location)
13731+
{
13732+
return (Node *) makeBoolExpr(NOT_EXPR, list_make1(expr), location);
13733+
}
13734+
1369513735
static Node *
1369613736
makeAArrayExpr(List *elements, int location)
1369713737
{

‎src/backend/parser/parse_clause.c

Lines changed: 10 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -332,7 +332,8 @@ transformJoinUsingClause(ParseState *pstate,
332332
RangeTblEntry*leftRTE,RangeTblEntry*rightRTE,
333333
List*leftVars,List*rightVars)
334334
{
335-
Node*result=NULL;
335+
Node*result;
336+
List*andargs=NIL;
336337
ListCell*lvars,
337338
*rvars;
338339

@@ -358,18 +359,16 @@ transformJoinUsingClause(ParseState *pstate,
358359
copyObject(lvar),copyObject(rvar),
359360
-1);
360361

361-
/* And combine into an AND clause, if multiple join columns */
362-
if (result==NULL)
363-
result= (Node*)e;
364-
else
365-
{
366-
A_Expr*a;
367-
368-
a=makeA_Expr(AEXPR_AND,NIL,result, (Node*)e,-1);
369-
result= (Node*)a;
370-
}
362+
/* Prepare to combine into an AND clause, if multiple join columns */
363+
andargs=lappend(andargs,e);
371364
}
372365

366+
/* Only need an AND if there's more than one join column */
367+
if (list_length(andargs)==1)
368+
result= (Node*)linitial(andargs);
369+
else
370+
result= (Node*)makeBoolExpr(AND_EXPR,andargs,-1);
371+
373372
/*
374373
* Since the references are already Vars, and are certainly from the input
375374
* relations, we don't have to go through the same pushups that

0 commit comments

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