Efficient "filter query" with positive and/or negative conditions

We have a database with contacts within lists, which can have any
number of tags associated with them. I would like to segment the
contacts based on any number of tag-based conditions, all of which
must be fulfilled (i.e. an ALL rule/filter). For instance, I want to
extract all contacts which have the tags "customer" AND "newsletter"
but NOT the "invited" tag. However, segments need not contain
"positive" predicates, so a segment defined as only NOT "invited" tag
should include ALL contacts except those with the "invited" tag. I
have found a working query using CTE, but it's way too slow when tens
of thousands of contacts are involved. Suggestions for an alternative
query and/or optimizations to this one?

Server:
-------
PostgreSQL 8.4.2 on a shared server running Apache/PHP/MySQL/PostgreSQL
shared_buffers: 128MB
work_mem: 8MB
effective_cache_size: 256MB

Current query:
--------------
WITH segments_contacts_tags AS (
SELECT segmentid, tagname, tagtype, email
FROM segments_tags st
LEFT JOIN contacts_tags ct USING (tagname)
WHERE segmentid = 93
), positive_segment_matches AS (
SELECT segmentid, email, COUNT(email) AS tags
FROM segments_contacts_tags
WHERE tagtype = 1
GROUP BY 1, 2
), positive_predicates_count AS (
SELECT segmentid, COUNT(*) AS count
FROM segments_tags
WHERE tagtype = 1
GROUP BY 1
)
SELECT s.segmentid, cl.email
FROM segments s
INNER JOIN contacts_lists cl USING (lid)
LEFT JOIN positive_segment_matches psm USING (segmentid, email)
LEFT JOIN positive_predicates_count ppc USING (segmentid)
WHERE segmentid = 93
AND ((psm.email IS NULL AND ppc.count IS NULL) OR psm.tags =
ppc.count)
EXCEPT
SELECT segmentid, email
FROM segments_contacts_tags st
WHERE st.tagtype = 0;

Explain analyze:
----------------
HashSetOp Except (cost=1817.12..5822.48 rows=200 width=36) (actual
time=5827.885..6051.771 rows=64672 loops=1)
CTE segments_contacts_tags
-> Nested Loop Left Join (cost=0.00..1323.86 rows=21819
width=61) (actual time=0.143..696.589 rows=64672 loops=1)
-> Seq Scan on segments_tags st (cost=0.00..1.05 rows=1
width=29) (actual time=0.014..0.025 rows=1 loops=1)
Filter: (segmentid = 93)
-> Index Scan using contacts_tags_tagname on
contacts_tags ct (cost=0.00..1050.07 rows=21819 width=49) (actual
time=0.110..265.453 rows=64672 loops=1)
Index Cond: (st.tagname = ct.tagname)
CTE positive_segment_matches
-> HashAggregate (cost=491.75..491.88 rows=11 width=36)
(actual time=1733.143..1995.489 rows=64672 loops=1)
-> CTE Scan on segments_contacts_tags (cost=0.00..490.93
rows=109 width=36) (actual time=0.161..1245.836 rows=64672 loops=1)
Filter: (tagtype = 1)
CTE positive_predicates_count
-> HashAggregate (cost=1.07..1.12 rows=4 width=4) (actual
time=0.069..0.088 rows=4 loops=1)
-> Seq Scan on segments_tags (cost=0.00..1.05 rows=4
width=4) (actual time=0.015..0.032 rows=4 loops=1)
Filter: (tagtype = 1)
-> Append (cost=0.26..3681.56 rows=64811 width=36) (actual
time=2734.790..5363.556 rows=64672 loops=1)
-> Subquery Scan "*SELECT* 1" (cost=0.26..3189.55
rows=64702 width=36) (actual time=2734.782..4923.849 rows=64672 loops=1)
-> Hash Left Join (cost=0.26..2542.53 rows=64702
width=36) (actual time=2734.773..4483.547 rows=64672 loops=1)
Hash Cond: ((s.segmentid = psm.segmentid) AND
((cl.email)::text = (psm.email)::text))
Filter: (((psm.email IS NULL) AND (ppc.count IS
NULL)) OR (psm.tags = ppc.count))
-> Nested Loop (cost=0.00..2052.95 rows=64702
width=44) (actual time=0.169..687.204 rows=64702 loops=1)
Join Filter: (s.lid = cl.lid)
-> Nested Loop Left Join
(cost=0.00..1.15 rows=1 width=16) (actual time=0.130..0.189 rows=1
loops=1)
Join Filter: (s.segmentid =
ppc.segmentid)
-> Seq Scan on segments s
(cost=0.00..1.05 rows=1 width=8) (actual time=0.025..0.032 rows=1
loops=1)
Filter: (segmentid = 93)
-> CTE Scan on
positive_predicates_count ppc (cost=0.00..0.09 rows=1 width=12)
(actual time=0.086..0.129 rows=1 loops=1)
Filter: (ppc.segmentid = 93)
-> Seq Scan on contacts_lists cl
(cost=0.00..1243.02 rows=64702 width=36) (actual time=0.014..231.331
rows=64702 loops=1)
-> Hash (cost=0.25..0.25 rows=1 width=44)
(actual time=2734.535..2734.535 rows=64672 loops=1)
-> CTE Scan on positive_segment_matches
psm (cost=0.00..0.25 rows=1 width=44) (actual time=1733.169..2481.359
rows=64672 loops=1)
Filter: (segmentid = 93)
-> Subquery Scan "*SELECT* 2" (cost=0.00..492.02 rows=109
width=36) (actual time=23.767..23.767 rows=0 loops=1)
-> CTE Scan on segments_contacts_tags st
(cost=0.00..490.93 rows=109 width=36) (actual time=23.758..23.758
rows=0 loops=1)
Filter: (tagtype = 0)
Total runtime: 6278.849 ms

Involved tables:
----------------

Table "public.contacts_lists"
Column | Type | Modifiers
----------------+-----------------------------
+------------------------------
email | email | not null
lid | integer | not null
lstatus | character(1) | not null default
'a'::bpchar
ladded | timestamp without time zone | not null default now()
lstatuschanged | timestamp without time zone | not null default now()
Indexes:
"contacts_lists_pkey" PRIMARY KEY, btree (email, lid)
"contacts_lists_statchanged" btree (lstatuschanged)
"contacts_lists_status" btree (lstatus)
Check constraints:
"status_check" CHECK (lstatus = 'a'::bpchar OR lstatus =
'b'::bpchar OR lstatus = 'u'::bpchar)
Foreign-key constraints:
"contacts_lists_email_fkey" FOREIGN KEY (email) REFERENCES
contacts(email) ON UPDATE CASCADE ON DELETE CASCADE
"contacts_lists_lid_fkey" FOREIGN KEY (lid) REFERENCES lists(lid)
ON UPDATE RESTRICT ON DELETE CASCADE

Table "public.contacts_tags"
Column | Type | Modifiers
---------+-------+-----------
email | email | not null
tagname | text | not null
Indexes:
"contacts_tags_pkey" PRIMARY KEY, btree (email, tagname)
"contacts_tags_tagname" btree (tagname)
Foreign-key constraints:
"contacts_tags_email_fkey" FOREIGN KEY (email) REFERENCES
contacts(email) ON UPDATE CASCADE ON DELETE CASCADE
"contacts_tags_tagname_fkey" FOREIGN KEY (tagname) REFERENCES
tags(tagname) ON UPDATE CASCADE ON DELETE CASCADE

Table "public.tags"
Column | Type | Modifiers
-----------+-----------------------------+------------------------
tagname | text | not null
createdat | timestamp without time zone | not null default now()
Indexes:
"tags_pkey" PRIMARY KEY, btree (tagname)
Referenced by:
TABLE "contacts_tags" CONSTRAINT "contacts_tags_tagname_fkey"
FOREIGN KEY (tagname) REFERENCES tags(tagname) ON UPDATE CASCADE ON
DELETE CASCADE
TABLE "segments_tags" CONSTRAINT "segments_tags_tagname_fkey"
FOREIGN KEY (tagname) REFERENCES tags(tagname) ON UPDATE CASCADE ON
DELETE CASCADE

Table "public.segments"
Column | Type |
Modifiers
-------------+-----------------------------
+--------------------------------------------------------------
segmentid | integer | not null default
nextval('segments_segmentid_seq'::regclass)
lid | integer | not null
segmentname | text | not null
createdat | timestamp without time zone | not null default now()
Indexes:
"segments_pkey" PRIMARY KEY, btree (segmentid)
Foreign-key constraints:
"segments_lid_fkey" FOREIGN KEY (lid) REFERENCES lists(lid) ON
UPDATE RESTRICT ON DELETE CASCADE
Referenced by:
TABLE "segments_tags" CONSTRAINT "segments_tags_segmentid_fkey"
FOREIGN KEY (segmentid) REFERENCES segments(segmentid) ON UPDATE
RESTRICT ON DELETE CASCADE

Table "public.segments_tags"
Column | Type | Modifiers
-----------+---------+-----------
segmentid | integer | not null
tagname | text | not null
tagtype | integer | not null
Indexes:
"segments_tags_pkey" PRIMARY KEY, btree (segmentid, tagname)
Foreign-key constraints:
"segments_tags_segmentid_fkey" FOREIGN KEY (segmentid) REFERENCES
segments(segmentid) ON UPDATE RESTRICT ON DELETE CASCADE
"segments_tags_tagname_fkey" FOREIGN KEY (tagname) REFERENCES
tags(tagname) ON UPDATE CASCADE ON DELETE CASCADE

-- anders