Here is a bug report that outlines out cnf-ify problem.  Looks like we
need a general solution, not just for subselects.

---------------------------------------------------------------------------

Forwarded message:
> From daveh@insightdist.com Wed Jan 14 10:20:16 1998
> X-Authentication-Warning: u1.abs.net: nobody set sender to insightdist.com!daveh using -f
> Message-Id: <34BA82BE.D10BFEEA@insightdist.com>
> Date: Mon, 12 Jan 1998 15:53:18 -0500
> From: David Hartwig <daveh@insightdist.com>
> Organization: Insight Distribution Systems
> X-Mailer: Mozilla 4.04 [en] (Win95; I)
> Mime-Version: 1.0
> To: Bruce Momjian <maillist@candle.pha.pa.us>
> Subject: Re: [BUGS] General Bug Report: palloc fails with lots of ANDs and ORs
> References: <199801121635.LAA05002@candle.pha.pa.us>
> Content-Type: multipart/mixed; boundary="------------20C7AC27E8BCA117B23354BE"
> 
> This is a multi-part message in MIME format.
> --------------20C7AC27E8BCA117B23354BE
> Content-Type: text/plain; charset=us-ascii
> Content-Transfer-Encoding: 7bit
> 
> Bruce,
> 
> I did some homework.   Here is what I have.   The default max data segment size on our (AIX 4.1.4) box is around 130000 kbytes.
> 
> I put together a query which put me just past the threshold of the palloc "out of memory error".  It is as follows:
> 
> create table outlet (
>     number int,
>     name varchar(30),
>     ...
> }
> 
> create unique index outlet_key on outlet using btree (number);
> 
> select count(*) from outlet
> where
>     (number = 1 and number = 1 and number = 1) or
>     (number = 1 and number = 1 and number = 1) or
>     (number = 1 and number = 1 and number = 1) or
>     (number = 1 and number = 1 and number = 1) or
>     (number = 1 and number = 1 and number = 1) or
>     (number = 1 and number = 1 and number = 1) or
>     (number = 1 and number = 1 and number = 1) or
>     (number = 1 and number = 1 and number = 1) or
>     (number = 1 and number = 1 and number = 1);
> 
> Not pretty but it makes the point.   Take out two OR clauses and the query works fine (but a bit slow).
> 
> The above query is all it takes to use up all 130000 Kbytes of memory.    And, since the query takes a long time to finally fail, I was able to
> observe the memory consumption.
> 
> I extended the max data segment to 300000.  And tried again.   I could observer the memory consumption up to about 280000 when the system
> suddenly got sick.   I was getting all kinds of messages like "cant fork"; bad stuff.  The system did finally recover on its own.   I am not
> sure happened there.   I know that ulimit puts us right around the physical memory limits of out system.
> 
> Using 300 meg for the above query seems like a bit of a problem.   It is difficult to imagine where all that memory is being used.   I will
> research the problem further if you need more information.
> 
> Bruce Momjian wrote:
> 
> > Try changing your OS default memory size.  Unsure how to do this under
> > AIX.
> >
> > >
> > >
> > > ============================================================================
> > >                         POSTGRESQL BUG REPORT TEMPLATE
> > > ============================================================================
> > >
> > >
> > > Your name             : David Hartwig
> > > Your email address    : daveh@insightdist.com
> > >
> > > Category              : runtime: back-end: SQL
> > > Severity              : serious
> > >
> > > Summary: palloc fails with lots of ANDs and ORs
> > >
> > > System Configuration
> > > --------------------
> > >   Operating System   : AIX 4.1
> > >
> > >   PostgreSQL version : 6.2
> > >
> > >   Compiler used      : native CC
> > >
> > > Hardware:
> > > ---------
> > > RS 6000
> > >
> > > Versions of other tools:
> > > ------------------------
> > > NA
> > >
> > > --------------------------------------------------------------------------
> > >
> > > Problem Description:
> > > --------------------
> > > The follow is a mail message describing the problem on the PostODBC mailing list:
> > >
> > >
> > > I have run across this also.   We traced it down to a failure in the PostgreSQL server.   This occurs under the following conditions.
> > >
> > >     1.  MS Access
> > >     2.  Specify a multi-part key in the link time setup with postgresql
> > >     3.  Click on table view.
> > >
> > > What happens is MS Access takes the following steps.   First it selects all possible key values for the table being viewed.   I
> > > suspect it maps the key values to the relative row position in the display.   Then it uses the mapping to generate future queries based
> > > on the mapping and the rows showing on the screen.   The queries take the following form:
> > >
> > >     SELECT  keypart1, keypart2, keypart3, col4, col5, col6 ... FROM example_table
> > >     WHERE
> > >         (keypart1 = row1keypartval1 AND  keypart2 = row1keypartval2 AND  keypart3 = row1keypartval3) OR
> > >         (keypart1 = row2keypartval1 AND  keypart2 = row2keypartval2 AND  keypart3 = row2keypartval3) OR
> > >             .
> > >             .      --  28 lines of this stuff.   Why 28... Why not 28
> > >             .
> > >         (keypart1 = row27keypartval1 AND  keypart2 = row27keypartval2 AND  keypart3 = row27keypartval3) OR
> > >         (keypart1 = row28keypartval1 AND  keypart2 = row28keypartval2 AND  keypart3 = row28keypartval3);
> > >
> > >
> > > The PostgreSQL sever chokes on this statement claiming it is out of memory.  (palloc)  In this example I used a three part key.  I
> > > do not recall if a three part key is enough to trash the backend.  It has been a while.    I have tried sending these kinds of statements
> > > directly through the psql monitor and get the same result.
> > >
> > >
> > > --------------------------------------------------------------------------
> > >
> > > Test Case:
> > > ----------
> > > select c1, c1 c3, c4, c5 ... from example_table
> > > where
> > > (c1 = something and c2 = something and c3 = something and c4 = something) or
> > > (c1 = something and c2 = something and c3 = something and c4 = something) or
> > > (c1 = something and c2 = something and c3 = something and c4 = something) or
> > > (c1 = something and c2 = something and c3 = something and c4 = something) or
> > > (c1 = something and c2 = something and c3 = something and c4 = something) or
> > > (c1 = something and c2 = something and c3 = something and c4 = something) or
> > > (c1 = something and c2 = something and c3 = something and c4 = something) or
> > > (c1 = something and c2 = something and c3 = something and c4 = something) or
> > > (c1 = something and c2 = something and c3 = something and c4 = something) or
> > > (c1 = something and c2 = something and c3 = something and c4 = something) or
> > > (c1 = something and c2 = something and c3 = something and c4 = something) or
> > > (c1 = something and c2 = something and c3 = something and c4 = something) or
> > > (c1 = something and c2 = something and c3 = something and c4 = something) or
> > > (c1 = something and c2 = something and c3 = something and c4 = something) or
> > > (c1 = something and c2 = something and c3 = something and c4 = something) or
> > > (c1 = something and c2 = something and c3 = something and c4 = something) or
> > > (c1 = something and c2 = something and c3 = something and c4 = something) or
> > > (c1 = something and c2 = something and c3 = something and c4 = something) or
> > > (c1 = something and c2 = something and c3 = something and c4 = something) or
> > > (c1 = something and c2 = something and c3 = something and c4 = something) or
> > > (c1 = something and c2 = something and c3 = something and c4 = something) or
> > > (c1 = something and c2 = something and c3 = something and c4 = something) or
> > > (c1 = something and c2 = something and c3 = something and c4 = something) or
> > > (c1 = something and c2 = something and c3 = something and c4 = something) or
> > > (c1 = something and c2 = something and c3 = something and c4 = something) or
> > > (c1 = something and c2 = something and c3 = something and c4 = something) or
> > > (c1 = something and c2 = something and c3 = something and c4 = something) or
> > > (c1 = something and c2 = something and c3 = something and c4 = something) or
> > > (c1 = something and c2 = something and c3 = something and c4 = something);
> > >
> > >
> > > --------------------------------------------------------------------------
> > >
> > > Solution:
> > > ---------
> > >
> > >
> > > --------------------------------------------------------------------------
> > >
> > >
> > >
> >
> > --
> > Bruce Momjian
> > maillist@candle.pha.pa.us
> 
> 
> 
> --------------20C7AC27E8BCA117B23354BE
> Content-Type: text/x-vcard; charset=us-ascii; name="vcard.vcf"
> Content-Transfer-Encoding: 7bit
> Content-Description: Card for David Hartwig
> Content-Disposition: attachment; filename="vcard.vcf"
> 
> begin:          vcard
> fn:             David Hartwig
> n:              Hartwig;David
> org:            Insight Distribution Systems
> adr:            222 Shilling Circle;;;Hunt Valley ;MD;21030;USA
> email;internet: daveh@insightdist.com
> title:          Manager Research & Development
> tel;work:       (410)403-2308
> x-mozilla-cpt:  ;0
> x-mozilla-html: TRUE
> version:        2.1
> end:            vcard
> 
> 
> --------------20C7AC27E8BCA117B23354BE--
> 
> 


-- 
Bruce Momjian
maillist@candle.pha.pa.us

Mon, 9 Feb 1998 12:49:58 -0500 (EST)
Bruce Momjian <maillist@candle.pha.pa.us>
cnf-ify problem