Optimizing NOT IN plans / verify rewrite

Hi,

I'm running PostgreSQL 8.3 and I have a query with a couple of NOT IN
subqueries:

DELETE FROM foo WHERE type = 'o' AND b NOT IN (SELECT cqc.b FROM bar
cqc) AND b NOT IN (SELECT car.b FROM foo car WHERE car.type != 'o');

The plan produced for this is:

QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------
Index Scan using foo_type_index on foo (cost=17851.93..1271633830.75
rows=66410 width=6)
Index Cond: (type = 'o'::bpchar)
Filter: ((NOT (subplan)) AND (NOT (subplan)))
SubPlan
-> Materialize (cost=6077.87..10238.57 rows=299170 width=8)
-> Seq Scan on bar cqc (cost=0.00..4609.70 rows=299170 width=8)
-> Materialize (cost=11774.06..15728.45 rows=284339 width=8)
-> Seq Scan on foo car (cost=0.00..10378.73 rows=284339 width=8)
Filter: (type <> 'o'::bpchar)
(9 rows)

Unfortunately, when these tables get large-ish, the materilzations get
really expensive to re-scan for every tuple (see cost above). At the
moment, I have ~500k rows in foo and ~300k rows in bar. The
selectivity of type = 'o' is ~50%. I've tried to re-write the query as
follows:

DELETE FROM foo WHERE b IN (SELECT candidate_run.type_o_run as b FROM
(SELECT cqar1.b AS type_o_run, cqar2.b AS non_type_o_run FROM foo
cqar1 LEFT OUTER JOIN foo cqar2 ON (cqar1.b = cqar2.b AND cqar2.type
!= 'o') WHERE cqar1.type = 'o') candidate_run LEFT OUTER JOIN bar ON
(candidate_run.type_o_run = bar.b) WHERE non_type_o_run IS NULL AND
bar.b IS NULL);

This gives the more sensible plan:

QUERY PLAN
-----------------------------------------------------------------------------------------------------------------
Hash IN Join (cost=48999.81..71174.41 rows=66410 width=6)
Hash Cond: (foo.b = cqar1.b)
-> Seq Scan on foo (cost=0.00..9003.78 rows=549978 width=14)
-> Hash (cost=47909.68..47909.68 rows=66410 width=8)
-> Hash Left Join (cost=24562.29..47909.68 rows=66410 width=8)
Hash Cond: (cqar1.b = bar.b)
Filter: (bar.b IS NULL)
-> Hash Left Join (cost=15043.96..33635.58 rows=132820 width=8)
Hash Cond: (cqar1.b = cqar2.b)
Filter: (cqar2.b IS NULL)
-> Seq Scan on foo cqar1 (cost=0.00..10378.73
rows=265639 width=8)
Filter: (type = 'o'::bpchar)
-> Hash (cost=10378.73..10378.73 rows=284339 width=8)
-> Seq Scan on foo cqar2
(cost=0.00..10378.73 rows=284339 width=8)
Filter: (type <> 'o'::bpchar)
-> Hash (cost=4609.70..4609.70 rows=299170 width=8)
-> Seq Scan on bar (cost=0.00..4609.70
rows=299170 width=8)
(17 rows)

As far as I can tell, the results are identical.

My questions

1. Is my rewrite valid?
2. Any way to reliably achieve the second plan (or really, any plan
that doesn't rescan ~~500k tuples per each of ~250k tuples) by
tweaking (per-session) planner constants? I've played with this a
little, but without much success. As with any rewrite situation, I'd
prefer to stick with the simpler, more explicit original query.

Here is a SQL script to reproduce the problem:

\set ON_ERROR_STOP

drop schema if exists not_in_test cascade;
create schema not_in_test;

set search_path to not_in_test;

create table foo (
a oid not null,
b bigint not null,
type char not null,
ts timestamp without time zone not null
);
create index "foo_b_a_type_index" on foo (b, a, type);
create index "foo_a_index" on foo (a);
create index "foo_type_index" on foo(type);

create table bar (
b bigint unique not null,
c timestamp with time zone not null
);
create index "bar_b_index" on bar(b);

insert into foo select (random()*10)::integer,
generate_series(1,550000), case when random() > 0.5 then 'o' else 'x'
end, now();
insert into bar select val, now() from generate_series(1,1200000) as
vals(val) where random() > 0.75;

analyze foo;
analyze bar;

EXPLAIN DELETE FROM foo WHERE type = 'o' AND b NOT IN (SELECT cqc.b
FROM bar cqc) AND b NOT IN (SELECT car.b FROM foo car WHERE car.type
!= 'o');
EXPLAIN DELETE FROM foo WHERE b IN (SELECT candidate_run.type_o_run as
b FROM (SELECT cqar1.b AS type_o_run, cqar2.b AS non_type_o_run FROM
foo cqar1 LEFT OUTER JOIN foo cqar2 ON (cqar1.b = cqar2.b AND
cqar2.type != 'o') WHERE cqar1.type = 'o') candidate_run LEFT OUTER
JOIN bar ON (candidate_run.type_o_run = bar.b) WHERE non_type_o_run IS
NULL AND bar.b IS NULL);

Thanks,
---
Maciek Sakrejda | System Architect | Truviso

1065 E. Hillsdale Blvd., Suite 215
Foster City, CA 94404
(650) 242-3500 Main
www.truviso.com