pgsql-4721

Version:

8.3.4

How it is diagnosed:

Reproduced. They have the script available.

Links:

bug report: http://archives.postgresql.org/pgsql-general/2008-11/msg00446.php

Patch: http://anoncvs.postgresql.org/cvsweb.cgi/pgsql/src/backend/optimizer/util/predtest.c?r1=1.19&r2=1.19.2.1

Root cause explanation:

- In pgsql/src/backend/optimizer/util/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

Background:

Understanding the script:

1). create a table with constraint:

CREATE TABLE table1

 (

   table1_id serial,

   table1_fld integer,

   CONSTRAINT pk_table1 PRIMARY KEY (table1_id)

 );

This statement also sets the ‘table1_id’ as UNIQUE and NOT NULL.

2). Add data:

 i=1

 while [ "$i" -le 5000 ]; do

     $PSQL -q -c "INSERT INTO table1 (table1_fld) SELECT (random() * 1234567);"

     let "i += 1"

 done

This is to insert 5,000 rows into the table, with ‘table1_id’ automatically incremented, and ‘table1_fld’ being random number.

3). Analyze the table:

$PSQL -q -c "ANALYZE table1;"

ANALYZE collects statistics about the contents of tables in the database, and stores the results in the system table pg_statistic. Subsequently, the query planner uses these statistics to help determine the most efficient execution plans for queries.

4). Generate query plan:

EXPLAIN SELECT 1 FROM table1 WHERE table1_id NOT IN ($idsb);

$idsb here = 123456789000,123456789000,123456789000,123456789000,...

Configuration: constraint_exclusion=on.

Enables the query planner's use of table constraints to optimize queries. In the script, the constraint is:  CONSTRAINT pk_table1 PRIMARY KEY (table1_id), that table1_id is primary key (UNIQUE and NOT NULL).

Symptom:

Hang when generating the query plan. The query in step 4):

EXPLAIN SELECT 1 FROM table1 WHERE table1_id NOT IN ($idsb);

is extremely slow.

Root cause:
When generating the query plan for a very long IN list, postgres needs to process very long predicate list connected by AND or OR. The processing logic is O(N^2) to traverse the list using recursion, which takes a long time.

The fix is simply install a maximum threshold (100) when doing the query plan. Thus as long as we already processed 100 branches, they break the recursion and retur. Also, developers installed a couple of CHECK_FOR_INTERRUPTS calls to ensure that a long proof attempt can be interrupted (interrupte handler).

-------------- First: Patch for installing CHECK_FOR_INTERRUPTS ---------------------

 static bool
 predicate_refuted_by_simple_clause(Expr *predicate, Node *clause)
 {
+         /* Allow interrupting long proof attempts */
+         CHECK_FOR_INTERRUPTS();
+

#define CHECK_FOR_INTERRUPTS() \

  do { \

       if (InterruptPending) \

             ProcessInterrupts(); \

   } while(0)

-------------- Patch for setting the 100 depth threshold ---------------------

predtest.c

  /*
+  * 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
+

----------------------------------------------------------------------
  *
  * 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)
*************** predicate_classify(Node *clause, PredIte

*** 698,704 ****
          * 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)

               /* All these additional checks against MAX_BRANCHES_TO_TEST is to allow this

                    function: predicate_classify to return early. This function is used in recursive call.*/
         {
                 info->startup_fn = list_startup_fn;
                 info->next_fn = list_next_fn;
                   info->cleanup_fn = list_cleanup_fn;

                        return CLASS_AND;
         }
 
         /* 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;

                        info->cleanup_fn = list_cleanup_fn;

                        return CLASS_OR;

}


        if (IsA(clause, ScalarArrayOpExpr)) {
                 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;

                                    return saop->useOr ? CLASS_OR : CLASS_AND;

}

}

return CLASS_ATOM;

}

static bool predicate_refuted_by_recurse(Node *clause, Node *predicate) {

    … ...

    pclass = predicate_classify(predicate, &pred_info);

    switch (predicate_classify(clause, &clause_info))   {

        case CLASS_AND:

            switch (pclass)

            {

                case CLASS_AND:

                    result = false;

          /* if CLASS_AND or CLASS_OR, will enter this loop! This loop contains a recursive call, and this is where the O(N^2) is from*/

   iterate_begin(pitem, predicate, pred_info)

                    {

                        if (predicate_refuted_by_recurse(clause, pitem))

                        {

                            result = true;

                            break;

                        }

                    }

                    iterate_end(pred_info);

                    if (result)

                        return result;

           … …

        case CLASS_ATOM:

            switch (pclass)

            {

               … …

        case CLASS_ATOM:

           return predicate_refuted_by_simple_clause (...);

         }

}

Is there any log message?:

No.

Can ErrLog help?

No.