pg.ddx.io  pgsql-sql@postgresql.org mailing list archive  
help / color / mirror / Atom feed
From: David C Hartwig Jr <daybee@bellatlantic.net>
To: Michael McCarthy <michael@tcsi.com>
Cc: pgsql-sql@postgresql.org
Subject: Re: [SQL] problem with OR'ed AND queriess
Date: Tue, 21 Dec 1999 17:53:20 -0500
Message-ID: <386004E0.75B3AF8E@bellatlantic.net> (raw)
References: <Pine.GSO.3.96.991221112043.9161G-100000@sanmarino.tcsi.com>

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,




view thread (7+ messages)  latest in thread

Message-ID: <386004E0.75B3AF8E@bellatlantic.net>
Permalink:  ../386004E0.75B3AF8E@bellatlantic.net/
Also on:    postgresql.org/message-id/386004E0.75B3AF8E@bellatlantic.net

 · 

reply

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Reply to all the recipients from your mail client; the link fills in
  the headers below: reply via email
  Some clients, webmail especially, drop In-Reply-To and References from
  a link, and the reply then starts a new thread: use the mbox below.

  To: pgsql-sql@postgresql.org
  Cc: daybee@bellatlantic.net, michael@tcsi.com
  Subject: Re: [SQL] problem with OR'ed AND queriess
  In-Reply-To: <386004E0.75B3AF8E@bellatlantic.net>
  References: <Pine.GSO.3.96.991221112043.9161G-100000@sanmarino.tcsi.com> <386004E0.75B3AF8E@bellatlantic.net>

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox