From fdf8d0624a9881e8ff6efcd60e20290291cc4c6c Mon Sep 17 00:00:00 2001 From: Tom Lane Date: Wed, 12 Nov 2008 23:08:37 +0000 Subject: [PATCH] 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) just exit without proving anything. This ensures that we don't spend O(N^2) time trying (and most likely failing) to prove anything about very long IN lists and similar cases. Also, install a couple of CHECK_FOR_INTERRUPTS calls to ensure that a long proof attempt can be interrupted. Per gripe from Sergey Konoplev. Back-patch the whole patch to 8.2 and just the CHECK_FOR_INTERRUPTS addition to 8.1. (The rest of the patch doesn't apply cleanly, and since 8.1 doesn't show the complained-of behavior anyway, it doesn't seem necessary to work hard on it.) --- src/backend/optimizer/util/predtest.c | 55 ++++++++++++++++++++++++++++------- 1 file changed, 45 insertions(+), 10 deletions(-) diff --git a/src/backend/optimizer/util/predtest.c b/src/backend/optimizer/util/predtest.c index 6d9934b578..f4a84e1072 100644 --- a/src/backend/optimizer/util/predtest.c +++ b/src/backend/optimizer/util/predtest.c @@ -9,7 +9,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/optimizer/util/predtest.c,v 1.20 2008/08/25 22:42:33 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/util/predtest.c,v 1.21 2008/11/12 23:08:37 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -19,6 +19,7 @@ #include "catalog/pg_proc.h" #include "catalog/pg_type.h" #include "executor/executor.h" +#include "miscadmin.h" #include "nodes/nodeFuncs.h" #include "optimizer/clauses.h" #include "optimizer/predtest.h" @@ -28,6 +29,15 @@ /* + * Proof attempts involving many AND or OR branches are likely to require + * O(N^2) time, and more often than not fail anyway. So we set an arbitrary + * limit on the number of branches that we will allow at any one level of + * clause. (Note that this is only effective because the trees have been + * AND/OR flattened!) XXX is it worth exposing this as a GUC knob? + */ +#define MAX_BRANCHES_TO_TEST 100 + +/* * To avoid redundant coding in predicate_implied_by_recurse and * predicate_refuted_by_recurse, we need to abstract out the notion of * iterating over the components of an expression that is logically an AND @@ -686,6 +696,13 @@ predicate_refuted_by_recurse(Node *clause, Node *predicate) * * If the expression is classified as AND- or OR-type, then *info is filled * in with the functions needed to iterate over its components. + * + * This function also implements enforcement of MAX_BRANCHES_TO_TEST: if an + * AND/OR expression has too many branches, we just classify it as an atom. + * (This will result in its being passed as-is to the simple_clause functions, + * which will fail to prove anything about it.) Note that we cannot just stop + * after considering MAX_BRANCHES_TO_TEST branches; in general that would + * result in wrong proofs rather than failing to prove anything. */ static PredClass predicate_classify(Node *clause, PredIterInfo info) @@ -698,7 +715,8 @@ predicate_classify(Node *clause, PredIterInfo info) * If we see a List, assume it's an implicit-AND list; this is the correct * semantics for lists of RestrictInfo nodes. */ - if (IsA(clause, List)) + if (IsA(clause, List) && + list_length((List *) clause) <= MAX_BRANCHES_TO_TEST) { info->startup_fn = list_startup_fn; info->next_fn = list_next_fn; @@ -707,14 +725,16 @@ predicate_classify(Node *clause, PredIterInfo info) } /* Handle normal AND and OR boolean clauses */ - if (and_clause(clause)) + if (and_clause(clause) && + list_length(((BoolExpr *) clause)->args) <= MAX_BRANCHES_TO_TEST) { info->startup_fn = boolexpr_startup_fn; info->next_fn = list_next_fn; info->cleanup_fn = list_cleanup_fn; return CLASS_AND; } - if (or_clause(clause)) + if (or_clause(clause) && + list_length(((BoolExpr *) clause)->args) <= MAX_BRANCHES_TO_TEST) { info->startup_fn = boolexpr_startup_fn; info->next_fn = list_next_fn; @@ -737,13 +757,22 @@ predicate_classify(Node *clause, PredIterInfo info) if (arraynode && IsA(arraynode, Const) && !((Const *) arraynode)->constisnull) { - info->startup_fn = arrayconst_startup_fn; - info->next_fn = arrayconst_next_fn; - info->cleanup_fn = arrayconst_cleanup_fn; - return saop->useOr ? CLASS_OR : CLASS_AND; + ArrayType *arrayval; + int nelems; + + arrayval = DatumGetArrayTypeP(((Const *) arraynode)->constvalue); + nelems = ArrayGetNItems(ARR_NDIM(arrayval), ARR_DIMS(arrayval)); + if (nelems <= MAX_BRANCHES_TO_TEST) + { + info->startup_fn = arrayconst_startup_fn; + info->next_fn = arrayconst_next_fn; + info->cleanup_fn = arrayconst_cleanup_fn; + return saop->useOr ? CLASS_OR : CLASS_AND; + } } - if (arraynode && IsA(arraynode, ArrayExpr) && - !((ArrayExpr *) arraynode)->multidims) + else if (arraynode && IsA(arraynode, ArrayExpr) && + !((ArrayExpr *) arraynode)->multidims && + list_length(((ArrayExpr *) arraynode)->elements) <= MAX_BRANCHES_TO_TEST) { info->startup_fn = arrayexpr_startup_fn; info->next_fn = arrayexpr_next_fn; @@ -964,6 +993,9 @@ arrayexpr_cleanup_fn(PredIterInfo info) static bool predicate_implied_by_simple_clause(Expr *predicate, Node *clause) { + /* Allow interrupting long proof attempts */ + CHECK_FOR_INTERRUPTS(); + /* First try the equal() test */ if (equal((Node *) predicate, clause)) return true; @@ -1019,6 +1051,9 @@ predicate_implied_by_simple_clause(Expr *predicate, Node *clause) static bool predicate_refuted_by_simple_clause(Expr *predicate, Node *clause) { + /* Allow interrupting long proof attempts */ + CHECK_FOR_INTERRUPTS(); + /* A simple clause can't refute itself */ /* Worth checking because of relation_excluded_by_constraints() */ if ((Node *) predicate == clause) -- 2.11.0