Received: from smtp-out2.bellatlantic.net (smtp-out2.bellatlantic.net [199.45.39.157]) by hub.org (8.9.3/8.9.3) with ESMTP id RAA49203 for ; Tue, 21 Dec 1999 17:49:35 -0500 (EST) (envelope-from daybee@bellatlantic.net) Received: from bellatlantic.net (client-151-196-125-6.bellatlantic.net [151.196.125.6]) by smtp-out2.bellatlantic.net (8.9.1/8.9.1) with ESMTP id RAA21709; Tue, 21 Dec 1999 17:55:29 -0500 (EST) Sender: dchartwig@bellatlantic.net Message-ID: <386004E0.75B3AF8E@bellatlantic.net> Date: Tue, 21 Dec 1999 17:53:20 -0500 From: David C Hartwig Jr Organization: Sonnet Software, Inc. X-Mailer: Mozilla 4.51C-Caldera [en] (X11; I; Linux 2.2.5 i686) X-Accept-Language: en MIME-Version: 1.0 To: Michael McCarthy CC: pgsql-sql@postgresql.org Subject: Re: [SQL] problem with OR'ed AND queriess References: Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit 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,