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

Commitfdf8d06

Browse files
committed
In predtest.c, install a limit on the number of branches we will process in
AND, OR, or equivalent clauses: if there are too many (more than 100) justexit without proving anything. This ensures that we don't spend O(N^2) timetrying (and most likely failing) to prove anything about very long IN listsand similar cases.Also, install a couple of CHECK_FOR_INTERRUPTS calls to ensure that a longproof attempt can be interrupted.Per gripe from Sergey Konoplev.Back-patch the whole patch to 8.2 and just the CHECK_FOR_INTERRUPTS additionto 8.1. (The rest of the patch doesn't apply cleanly, and since 8.1 doesn'tshow the complained-of behavior anyway, it doesn't seem necessary to workhard on it.)
1 parent249b224 commitfdf8d06

File tree

1 file changed

+45
-10
lines changed

1 file changed

+45
-10
lines changed

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

Lines changed: 45 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,7 @@
99
*
1010
*
1111
* IDENTIFICATION
12-
* $PostgreSQL: pgsql/src/backend/optimizer/util/predtest.c,v 1.20 2008/08/25 22:42:33 tgl Exp $
12+
* $PostgreSQL: pgsql/src/backend/optimizer/util/predtest.c,v 1.21 2008/11/12 23:08:37 tgl Exp $
1313
*
1414
*-------------------------------------------------------------------------
1515
*/
@@ -19,6 +19,7 @@
1919
#include"catalog/pg_proc.h"
2020
#include"catalog/pg_type.h"
2121
#include"executor/executor.h"
22+
#include"miscadmin.h"
2223
#include"nodes/nodeFuncs.h"
2324
#include"optimizer/clauses.h"
2425
#include"optimizer/predtest.h"
@@ -27,6 +28,15 @@
2728
#include"utils/syscache.h"
2829

2930

31+
/*
32+
* Proof attempts involving many AND or OR branches are likely to require
33+
* O(N^2) time, and more often than not fail anyway. So we set an arbitrary
34+
* limit on the number of branches that we will allow at any one level of
35+
* clause. (Note that this is only effective because the trees have been
36+
* AND/OR flattened!) XXX is it worth exposing this as a GUC knob?
37+
*/
38+
#defineMAX_BRANCHES_TO_TEST100
39+
3040
/*
3141
* To avoid redundant coding in predicate_implied_by_recurse and
3242
* predicate_refuted_by_recurse, we need to abstract out the notion of
@@ -686,6 +696,13 @@ predicate_refuted_by_recurse(Node *clause, Node *predicate)
686696
*
687697
* If the expression is classified as AND- or OR-type, then *info is filled
688698
* in with the functions needed to iterate over its components.
699+
*
700+
* This function also implements enforcement of MAX_BRANCHES_TO_TEST: if an
701+
* AND/OR expression has too many branches, we just classify it as an atom.
702+
* (This will result in its being passed as-is to the simple_clause functions,
703+
* which will fail to prove anything about it.) Note that we cannot just stop
704+
* after considering MAX_BRANCHES_TO_TEST branches; in general that would
705+
* result in wrong proofs rather than failing to prove anything.
689706
*/
690707
staticPredClass
691708
predicate_classify(Node*clause,PredIterInfoinfo)
@@ -698,7 +715,8 @@ predicate_classify(Node *clause, PredIterInfo info)
698715
* If we see a List, assume it's an implicit-AND list; this is the correct
699716
* semantics for lists of RestrictInfo nodes.
700717
*/
701-
if (IsA(clause,List))
718+
if (IsA(clause,List)&&
719+
list_length((List*)clause) <=MAX_BRANCHES_TO_TEST)
702720
{
703721
info->startup_fn=list_startup_fn;
704722
info->next_fn=list_next_fn;
@@ -707,14 +725,16 @@ predicate_classify(Node *clause, PredIterInfo info)
707725
}
708726

709727
/* Handle normal AND and OR boolean clauses */
710-
if (and_clause(clause))
728+
if (and_clause(clause)&&
729+
list_length(((BoolExpr*)clause)->args) <=MAX_BRANCHES_TO_TEST)
711730
{
712731
info->startup_fn=boolexpr_startup_fn;
713732
info->next_fn=list_next_fn;
714733
info->cleanup_fn=list_cleanup_fn;
715734
returnCLASS_AND;
716735
}
717-
if (or_clause(clause))
736+
if (or_clause(clause)&&
737+
list_length(((BoolExpr*)clause)->args) <=MAX_BRANCHES_TO_TEST)
718738
{
719739
info->startup_fn=boolexpr_startup_fn;
720740
info->next_fn=list_next_fn;
@@ -737,13 +757,22 @@ predicate_classify(Node *clause, PredIterInfo info)
737757
if (arraynode&&IsA(arraynode,Const)&&
738758
!((Const*)arraynode)->constisnull)
739759
{
740-
info->startup_fn=arrayconst_startup_fn;
741-
info->next_fn=arrayconst_next_fn;
742-
info->cleanup_fn=arrayconst_cleanup_fn;
743-
returnsaop->useOr ?CLASS_OR :CLASS_AND;
760+
ArrayType*arrayval;
761+
intnelems;
762+
763+
arrayval=DatumGetArrayTypeP(((Const*)arraynode)->constvalue);
764+
nelems=ArrayGetNItems(ARR_NDIM(arrayval),ARR_DIMS(arrayval));
765+
if (nelems <=MAX_BRANCHES_TO_TEST)
766+
{
767+
info->startup_fn=arrayconst_startup_fn;
768+
info->next_fn=arrayconst_next_fn;
769+
info->cleanup_fn=arrayconst_cleanup_fn;
770+
returnsaop->useOr ?CLASS_OR :CLASS_AND;
771+
}
744772
}
745-
if (arraynode&&IsA(arraynode,ArrayExpr)&&
746-
!((ArrayExpr*)arraynode)->multidims)
773+
elseif (arraynode&&IsA(arraynode,ArrayExpr)&&
774+
!((ArrayExpr*)arraynode)->multidims&&
775+
list_length(((ArrayExpr*)arraynode)->elements) <=MAX_BRANCHES_TO_TEST)
747776
{
748777
info->startup_fn=arrayexpr_startup_fn;
749778
info->next_fn=arrayexpr_next_fn;
@@ -964,6 +993,9 @@ arrayexpr_cleanup_fn(PredIterInfo info)
964993
staticbool
965994
predicate_implied_by_simple_clause(Expr*predicate,Node*clause)
966995
{
996+
/* Allow interrupting long proof attempts */
997+
CHECK_FOR_INTERRUPTS();
998+
967999
/* First try the equal() test */
9681000
if (equal((Node*)predicate,clause))
9691001
return true;
@@ -1019,6 +1051,9 @@ predicate_implied_by_simple_clause(Expr *predicate, Node *clause)
10191051
staticbool
10201052
predicate_refuted_by_simple_clause(Expr*predicate,Node*clause)
10211053
{
1054+
/* Allow interrupting long proof attempts */
1055+
CHECK_FOR_INTERRUPTS();
1056+
10221057
/* A simple clause can't refute itself */
10231058
/* Worth checking because of relation_excluded_by_constraints() */
10241059
if ((Node*)predicate==clause)

0 commit comments

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