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 question marks 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,