Re: [BUGS] General Bug Report: palloc fails with lots of ANDs and ORs

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.

Wow, looks like a bug. Vadim, why would this happen? I got the same
palloc failure message here, and there is NO data in the table.

Original messages attached.

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

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

Bruce Momjian wrote:

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);

...

Wow, looks like a bug. Vadim, why would this happen? I got the same
palloc failure message here, and there is NO data in the table.

This is bug in optimizer - try to EXPLAIN query...
I have no time to fix it now - could return to this after Feb 1.

Vadim

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.

Optimizator tries to transform qual above into AND clause with
3 (# of and-ed clauses) ^ 9 (# of OR-s) = 19683 args (each arg
is OR clause with 9 op. expressions. My estimation for current
cnfify() code is that this will require =~ 500Mb of memory :)
I made little changes - just to free memory when it's possible:

current code with free-ing

6 ORs 14.3 Mb 4.3 Mb
7 ORs 53 Mb 10.3 Mb
8 ORs estimation: ~ 160 Mb 30.6 MB

I'm not sure should I aplly my changes or not - it doesn't fix
problem, just reduces memory impact. It obviously can't help you,
David, in your real example (3 ^ 28 = 22876792454961 clauses - he he :).

Resume: cnfify() makes mathematically strong but in some cases
practically unwise work. I can't fix this for 6.3

Vadim

Added to TODO list.

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.

Optimizator tries to transform qual above into AND clause with
3 (# of and-ed clauses) ^ 9 (# of OR-s) = 19683 args (each arg
is OR clause with 9 op. expressions. My estimation for current
cnfify() code is that this will require =~ 500Mb of memory :)
I made little changes - just to free memory when it's possible:

current code with free-ing

6 ORs 14.3 Mb 4.3 Mb
7 ORs 53 Mb 10.3 Mb
8 ORs estimation: ~ 160 Mb 30.6 MB

I'm not sure should I aplly my changes or not - it doesn't fix
problem, just reduces memory impact. It obviously can't help you,
David, in your real example (3 ^ 28 = 22876792454961 clauses - he he :).

Resume: cnfify() makes mathematically strong but in some cases
practically unwise work. I can't fix this for 6.3

Vadim

-- 
Bruce Momjian                          |  830 Blythe Avenue
maillist@candle.pha.pa.us              |  Drexel Hill, Pennsylvania 19026
  +  If your life is a hard drive,     |  (610) 353-9879(w)
  +  Christ can be your backup.        |  (610) 853-3000(h)