BUG #2243: Postgresql fails to finish some queries

The following bug has been logged online:

Bug reference: 2243
Logged by: Matej Rizman
Email address: matej(dot)rizman(at)gmail(dot)com
PostgreSQL version: 8.0 and 8.1
Operating system: Linux Debian, kernel 2.6.12-1-k7
Description: Postgresql fails to finish some queries
Details:

Execute the following script:

CREATE TABLE a (
num int4
);

CREATE TABLE b (
num int4
);

CREATE UNIQUE INDEX ix_a_num ON a(num);
CREATE INDEX ix_b_num ON b(num);

COPY a FROM '/tmp/a_30000.txt';
COPY b FROM '/tmp/b_30000.txt';

SELECT * FROM b WHERE num NOT IN (SELECT num FROM a);

Files a_30000.txt and b_30000.txt contain 30000 numbers each.

The last query (SELECT) is executed on my machine in 125ms.

If I load data from files a_100000.txt and b_100000.txt that contain 100000
numbers each, the last SELECT does not finish in more than ten minutes (the
real-world sample hasn't finished in more than an hour).

The similar real-world sample does not even return the results of EXPLAIN
statement. However, this real-world sample is quite complex and I am not
posting it there. In the case I provided the EXPLAIN statement works fine.

This behaviour has been observed on postgresql 8.0 and on postgresql 8.1. It
has also been tested on two different computers, both running debian linux.

I can provide files a_* and b_* if you want. However, they are quite large
and unsuitable for mailing list attachments.

Best regards,
Matej Rizman