suboptimal query plan

I'm struggling with a query that seems to use a suboptimal query plan.

Schema: units reference a subjob reference a job. In other words: a job contains multiple subjobs. A subjob contains multiple units. (full schema below)

We're trying to select all subjobs that need to be reviewed and that contain units that aren't reviewed yet (either because validated is NULL or validated is 'N')

Notice the EXISTS with subquery which will turn out to be the problem:

(SELECT s0_m0_msubJobs."__id"
AS
s0_msubJobs_mid,
s0_m0_msubJobs."document_mflow"
AS s0_msubJobs_mdocument_mflow,
s0_m0_msubJobs."status"
AS s0_msubJobs_mstatus,
s0_m0_msubJobs."error_mmessage"
AS s0_msubJobs_merror_mmessage,
s0_m0_msubJobs."validation_mrequired"
AS s0_msubJobs_mvalidation_mrequired,
s0_m0_msubJobs."completion_mdate"
AS s0_msubJobs_mcompletion_mdate,
s0_m0_msubJobs."creation_mdate"
AS s0_msubJobs_mcreation_mdate,
s0_m0_msubJobs."file_mlocation"
AS s0_msubJobs_mfile_mlocation,
s0_m1_mjob."__id"
AS s0_mjob_mid,
s0_m1_mjob."xml_mname"
AS s0_mjob_mxml_mname,
( s0_m0_msubJobs."creation_mdate" )
AS e0_m4
FROM "subJobs" s0_m0_msubJobs,
"job" s0_m1_mjob
WHERE ( ( ( ( s0_m0_msubJobs."status" ) = ( 'IN_PROGRESS' ) )
AND ( ( s0_m0_msubJobs."validation_mrequired" ) = ( 'Y' ) ) )
AND ( EXISTS (((SELECT s1_m1_munit."__id" AS s1_munit_mid
FROM "subJobs" s1_m0_msubJobs,
"unit" s1_m1_munit
WHERE ( ( ( s0_m0_msubJobs."__id" ) =
( s1_m0_msubJobs."__id" ) )

AND
( s1_m0_msubJobs."__id" = s1_m1_munit."subJobs_mid" ) )
AND ( ( NOT ( s1_m1_munit."validated" IS NOT NULL ) )
OR ( ( s1_m1_munit."validated" ) = ( 'N'
) ) )))
)
) )
AND ( s0_m0_msubJobs."job_mid" = s0_m1_mjob."__id" ))
ORDER BY e0_m4 DESC,
s0_mjob_mid nulls first,
s0_msubjobs_mid nulls first

This generates the following query plan

Sort (cost=63242.75..63242.83 rows=30 width=503) (actual time=804.180..804.182 rows=49 loops=1)
Sort Key: s0_m0_msubjobs.creation_mdate, s0_m1_mjob.__id, s0_m0_msubjobs.__id
Sort Method: quicksort Memory: 31kB
Buffers: shared hit=3855 read=13852
-> Hash Join (cost=63087.27..63242.02 rows=30 width=503) (actual time=803.045..804.144 rows=49 loops=1)
Hash Cond: (s0_m0_msubjobs.job_mid = s0_m1_mjob.__id)
Buffers: shared hit=3855 read=13852
-> Hash Join (cost=63069.02..63223.35 rows=30 width=484) (actual time=802.875..803.953 rows=49 loops=1)
Hash Cond: (s1_m0_msubjobs.__id = s0_m0_msubjobs.__id)
Buffers: shared hit=3848 read=13852
-> HashAggregate (cost=63014.58..63060.13 rows=4555 width=16) (actual time=802.733..803.452 rows=4555 loops=1)
Buffers: shared hit=3808 read=13852
-> Hash Join (cost=149.49..59533.65 rows=1392372 width=16) (actual time=1.157..620.181 rows=1392372 loops=1)
Hash Cond: (s1_m1_munit."subJobs_mid" = s1_m0_msubjobs.__id)
Buffers: shared hit=3808 read=13852
-> Seq Scan on unit s1_m1_munit (cost=0.00..35017.65 rows=1392372 width=8) (actual time=0.004..211.780 rows=1392372 loops=1)
Filter: ((validated IS NULL) OR ((validated)::text = 'N'::text))
Buffers: shared hit=3761 read=13852
-> Hash (cost=92.55..92.55 rows=4555 width=8) (actual time=1.140..1.140 rows=4555 loops=1)
Buckets: 1024 Batches: 1 Memory Usage: 178kB
Buffers: shared hit=47
-> Seq Scan on "subJobs" s1_m0_msubjobs (cost=0.00..92.55 rows=4555 width=8) (actual time=0.004..0.551 rows=4555 loops=1)
Buffers: shared hit=47
-> Hash (cost=54.07..54.07 rows=30 width=484) (actual time=0.122..0.122 rows=49 loops=1)
Buckets: 1024 Batches: 1 Memory Usage: 5kB
Buffers: shared hit=40
-> Bitmap Heap Scan on "subJobs" s0_m0_msubjobs (cost=5.20..54.07 rows=30 width=484) (actual time=0.046..0.110 rows=49 loops=1)
Recheck Cond: ((status)::text = 'IN_PROGRESS'::text)
Filter: ((validation_mrequired)::text = 'Y'::text)
Buffers: shared hit=40
-> Bitmap Index Scan on subjob_status (cost=0.00..5.19 rows=125 width=0) (actual time=0.034..0.034 rows=125 loops=1)
Index Cond: ((status)::text = 'IN_PROGRESS'::text)
Buffers: shared hit=2
-> Hash (cost=12.00..12.00 rows=500 width=27) (actual time=0.165..0.165 rows=500 loops=1)
Buckets: 1024 Batches: 1 Memory Usage: 30kB
Buffers: shared hit=7
-> Seq Scan on job s0_m1_mjob (cost=0.00..12.00 rows=500 width=27) (actual time=0.005..0.085 rows=500 loops=1)
Buffers: shared hit=7
Total runtime: 804.382 ms

Now, if we add OFFSET 0 to the EXISTS subquery (which shouldn't alter the query's meaning - correct?)

EXPLAIN (ANALYZE, BUFFERS) (SELECT s0_m0_msubJobs."__id"
AS
s0_msubJobs_mid,
s0_m0_msubJobs."document_mflow"
AS s0_msubJobs_mdocument_mflow,
s0_m0_msubJobs."status"
AS s0_msubJobs_mstatus,
s0_m0_msubJobs."error_mmessage"
AS s0_msubJobs_merror_mmessage,
s0_m0_msubJobs."validation_mrequired"
AS s0_msubJobs_mvalidation_mrequired,
s0_m0_msubJobs."completion_mdate"
AS s0_msubJobs_mcompletion_mdate,
s0_m0_msubJobs."creation_mdate"
AS s0_msubJobs_mcreation_mdate,
s0_m0_msubJobs."file_mlocation"
AS s0_msubJobs_mfile_mlocation,
s0_m1_mjob."__id"
AS s0_mjob_mid,
s0_m1_mjob."xml_mname"
AS s0_mjob_mxml_mname,
( s0_m0_msubJobs."creation_mdate" )
AS e0_m4
FROM "subJobs" s0_m0_msubJobs,
"job" s0_m1_mjob
WHERE ( ( ( ( s0_m0_msubJobs."status" ) = ( 'IN_PROGRESS' ) )
AND ( ( s0_m0_msubJobs."validation_mrequired" ) = ( 'Y' ) ) )
AND ( EXISTS (((SELECT s1_m1_munit."__id" AS s1_munit_mid
FROM "subJobs" s1_m0_msubJobs,
"unit" s1_m1_munit
WHERE ( ( ( s0_m0_msubJobs."__id" ) =
( s1_m0_msubJobs."__id" ) )

AND
( s1_m0_msubJobs."__id" = s1_m1_munit."subJobs_mid" ) )
AND ( ( NOT ( s1_m1_munit."validated" IS NOT NULL ) )
OR ( ( s1_m1_munit."validated" ) = ( 'N'
) ) )
OFFSET 0))
)
) )
AND ( s0_m0_msubJobs."job_mid" = s0_m1_mjob."__id" ))
ORDER BY e0_m4 DESC,
s0_mjob_mid nulls first,
s0_msubjobs_mid nulls first

we get the following query plan

Sort (cost=556.27..556.30 rows=15 width=503) (actual time=0.828..0.829 rows=49 loops=1)
Sort Key: s0_m0_msubjobs.creation_mdate, s0_m1_mjob.__id, s0_m0_msubjobs.__id
Sort Method: quicksort Memory: 31kB
Buffers: shared hit=390
-> Hash Join (cost=23.44..555.97 rows=15 width=503) (actual time=0.229..0.788 rows=49 loops=1)
Hash Cond: (s0_m0_msubjobs.job_mid = s0_m1_mjob.__id)
Buffers: shared hit=390
-> Bitmap Heap Scan on "subJobs" s0_m0_msubjobs (cost=5.19..537.52 rows=15 width=484) (actual time=0.057..0.591 rows=49 loops=1)
Recheck Cond: ((status)::text = 'IN_PROGRESS'::text)
Filter: (((validation_mrequired)::text = 'Y'::text) AND (SubPlan 1))
Buffers: shared hit=383
-> Bitmap Index Scan on subjob_status (cost=0.00..5.19 rows=125 width=0) (actual time=0.031..0.031 rows=125 loops=1)
Index Cond: ((status)::text = 'IN_PROGRESS'::text)
Buffers: shared hit=2
SubPlan 1
-> Limit (cost=0.00..1187.36 rows=307 width=8) (actual time=0.009..0.009 rows=1 loops=49)
Buffers: shared hit=343
-> Nested Loop (cost=0.00..1187.36 rows=307 width=8) (actual time=0.009..0.009 rows=1 loops=49)
Buffers: shared hit=343
-> Index Scan using "subJobs_mid_mindex" on "subJobs" s1_m0_msubjobs (cost=0.00..8.27 rows=1 width=8) (actual time=0.002..0.002 rows=1 loops=49)
Index Cond: (__id = s0_m0_msubjobs.__id)
Buffers: shared hit=147
-> Index Scan using "unit_msubJobs_mid_mindex" on unit s1_m1_munit (cost=0.00..1176.02 rows=307 width=16) (actual time=0.006..0.006 rows=1 loops=49)
Index Cond: ("subJobs_mid" = s0_m0_msubjobs.__id)
Filter: ((validated IS NULL) OR ((validated)::text = 'N'::text))
Buffers: shared hit=196
-> Hash (cost=12.00..12.00 rows=500 width=27) (actual time=0.164..0.164 rows=500 loops=1)
Buckets: 1024 Batches: 1 Memory Usage: 30kB
Buffers: shared hit=7
-> Seq Scan on job s0_m1_mjob (cost=0.00..12.00 rows=500 width=27) (actual time=0.003..0.082 rows=500 loops=1)
Buffers: shared hit=7
Total runtime: 0.899 ms

which is a few orders of magnitude faster.

Is there a reason why the more optimal query plan isn't chosen without the OFFSET 0 clause?
Shouldn't the optimizer evaluate the option where the EXISTS query is JOINED as well as the option where the EXISTS query isn't and choose the plan with the lowest cost?

Any light you could shed on this is appreciated.

Potentially useful information:
Version: PostgreSQL 9.1.1, compiled by Visual C++ build 1500, 64-bit

Data: Most units have validated set to NULL, 500 jobs, 4555 subJobs, 1392372 units.

Schema:

-- Table: job
CREATE TABLE job
(
__id bigint NOT NULL,
parent_mjob bigint,
status character varying(32),
priority integer,
creation_mdate timestamp without time zone,
completion_mdate timestamp without time zone,
description character varying(200),
xml_mname character varying(200),
__source character varying(200),
__label character varying(200),
error_mmessage character varying(200),
last_mchange_mdate timestamp without time zone,
__size numeric(19,0),
CONSTRAINT job_pkey PRIMARY KEY (__id ),
CONSTRAINT job_parent_mjob_fkey FOREIGN KEY (parent_mjob)
REFERENCES job (__id) MATCH SIMPLE
ON UPDATE NO ACTION ON DELETE SET NULL
)
WITH (
OIDS=FALSE
);

CREATE INDEX job_mdescription_mindex
ON job
USING gin
(to_tsvector('english'::regconfig, description::text) );

CREATE INDEX job_mid_mindex
ON job
USING btree
(__id );

-- Table: "subJobs"
CREATE TABLE "subJobs"
(
__id bigint NOT NULL,
document_mflow character varying(200),
status character varying(200),
error_mmessage character varying(200),
validation_mrequired character varying(200),
completion_mdate timestamp without time zone,
creation_mdate timestamp without time zone,
job_mid bigint NOT NULL,
file_mlocation character varying(200),
CONSTRAINT "subJobs_pkey" PRIMARY KEY (__id ),
CONSTRAINT "subJobs_job_mid_fkey" FOREIGN KEY (job_mid)
REFERENCES job (__id) MATCH SIMPLE
ON UPDATE NO ACTION ON DELETE CASCADE
)
WITH (
OIDS=FALSE
);

CREATE INDEX "subJobs_mid_mindex"
ON "subJobs"
USING btree
(__id );

CREATE INDEX "subJobs_mjob_mid_mindex"
ON "subJobs"
USING btree
(job_mid );

CREATE INDEX subjob_status
ON "subJobs"
USING btree
(status COLLATE pg_catalog."default" );

-- Table: unit
CREATE TABLE unit
(
__id bigint NOT NULL,
client_mnumber character varying(200) NOT NULL,
source_mid character varying(200),
delivery_mformat character varying(200),
delivery_mtype character varying(200),
client_memailaddress character varying(200),
client_mcollectivity character varying(200),
client_mcommunication_mpreference character varying(200),
validated character varying(200),
status character varying(200),
error_mmessage character varying(200),
completion_mdate timestamp without time zone,
creation_mdate timestamp without time zone,
file_mlocation character varying(200),
delivery_mfeedback character varying(200),
"subJobs_mid" bigint NOT NULL,
__type character varying(200),
CONSTRAINT unit_pkey PRIMARY KEY (__id ),
CONSTRAINT "unit_subJobs_mid_fkey" FOREIGN KEY ("subJobs_mid")
REFERENCES "subJobs" (__id) MATCH SIMPLE
ON UPDATE NO ACTION ON DELETE CASCADE
)
WITH (
OIDS=FALSE
);

CREATE INDEX unit_mid_mindex
ON unit
USING btree
(__id );

CREATE INDEX "unit_msubJobs_mid_mindex"
ON unit
USING btree
("subJobs_mid" );

CREATE INDEX unit_validated
ON unit
USING btree
(validated COLLATE pg_catalog."default" );

With kind regards,

Nick Hofstede

________________________________

Inventive Designers' Email Disclaimer:
http://www.inventivedesigners.com/email-disclaimer