Re: [SQL] problem with OR'ed AND queriess

Michael McCarthy wrote:

> Using PQexec from libpq in postgresql 6.5.3, I submit a query of the
> following form, which has 13 OR'ed AND expressions:
>
>     DECLARE my_cursor CURSOR FOR SELECT col1 FROM testCNF where
>     ( ( col1=0  and col2=1  ) OR ( col1=1  and col2=2  ) OR
>       ( col1=2  and col2=3  ) OR ( col1=3  and col2=4  ) OR
>       ( col1=4  and col2=5  ) OR ( col1=5  and col2=6  ) OR
>       ( col1=6  and col2=7  ) OR ( col1=7  and col2=8  ) OR
>       ( col1=8  and col2=9  ) OR ( col1=9  and col2=10 ) OR
>       ( col1=10 and col2=11 ) OR ( col1=11 and col2=12 ) OR
>       ( col1=12 and col2=13 ) )
>
> After 265 seconds, my test client gets back a NULL response from PQexec.
> During the 265 seconds, the backend server machine (Sparc Ultra 2) slows
> to a crawl. In the postmaster log, I see the following:
>
>     FATAL 1:  Memory exhausted in AllocSetAlloc()
>
> A similar query with 12 OR'ed AND expresions is successful, but only after
> 123 seconds. Queries with fewer OR'ed AND expresions get faster; 6 OR'ed
> ANDS takes around one second. With other query types, I encounter no such
> limitation; AND'ed ORs, all ANDs and all ORs can be as large a query as
> the internal buffer can support (around 16k), with no problem.
>
> I have traced the backend server in a debugger; a stack trace is attached
> below. What I see in examining the code is a recursive normalization of
> the query; postgres is running out of memory trying to convert the OR'ed
> ANDs query to conjunctive normal form (CNF).
>
> So, some questions for all you postgres gurus:
>
> 1. Has anyone else encountered this problem?

Yes, its on the todo list.   I do not know if it is being actively persued.

>
>
> 2. Has anyone patched the query optimizer to get around this problem, and
>    if so, where can I find the patch?
>

There is a work around feature that works for queries that gererate a parse tree similar to yours.
ODBC tools generate these kinds of queries all the time.    Keyset queries.   To acivate the
feature:    SET ksqo TO 'on';    It rewrites the parse tree into a series of UNIONs.   Not optimal but
it works for rectangular where clauses.   (n ANDs) x  (m ORs)

--   Here is an example using a 3 part key    select ... from foo where        (v1 = "?" AND v2 = "?" AND v3 ="?") OR
    -- line 1        (v1 = "?" AND v2 = "?" AND v3 ="?") OR        -- line 2                ...        (v1 = "?" AND v2
="?" AND v3 ="?") OR        --  line 9        (v1 = "?" AND v2 = "?" AND v3 ="?");              --  line 10    --  The
questionmarks are replaced with the constant key values
 


>
> 3. If I am truly the first to encounter this (which I doubt), how would I
>    go about altering the query optimizer to not fail on this valid query?
>
> Thanks,