Slow query with joins

Hello!
Has anyone got any tips for speeding up this query? It currently
takes hours to start.

PostgreSQL v8.x on (SuSe Linux)
Thanks!

no_people=# explain SELECT r.id AS r_id, r.firstname || ' ' ||
r.lastname AS r_name, ad.id AS ad_id, ad.type AS ad_type, ad.address
AS ad_address, ad.postalcode AS ad_postalcode, ad.postalsite AS
ad_postalsite, ad.priority AS ad_priority, ad.position[0] AS ad_lat,
ad.position[1] AS ad_lon, ad.uncertainty AS ad_uncertainty, ad.extra
AS ad_extra, co.id AS co_id, co.type AS co_type, co.value AS
co_value, co.description AS co_description, co.priority AS
co_priority, co.visible AS co_visible, co.searchable AS co_searchable

FROM people r
LEFT OUTER JOIN addresses ad ON(r.id = ad.record)
LEFT OUTER JOIN contacts co ON(r.id = co.record)
WHERE r.deleted = false AND r.original IS NULL AND co.deleted =
false AND NOT ad.deleted
ORDER BY r.id;

QUERY PLAN
------------------------------------------------------------------------
-------------------------------------------------------
Sort (cost=1152540.74..1152988.20 rows=178983 width=585)
Sort Key: r.id
-> Hash Join (cost=313757.11..1005334.96 rows=178983 width=585)
Hash Cond: ("outer".record = "inner".id)
-> Seq Scan on addresses ad (cost=0.00..428541.29
rows=4952580 width=136)
Filter: (NOT deleted)
-> Hash (cost=312039.95..312039.95 rows=27664 width=457)
-> Hash Join (cost=94815.24..312039.95 rows=27664
width=457)
Hash Cond: ("outer".record = "inner".id)
-> Seq Scan on contacts co
(cost=0.00..147791.54 rows=5532523 width=430)
Filter: (deleted = false)
-> Hash (cost=94755.85..94755.85 rows=23755
width=27)
-> Index Scan using
people_original_is_null on people r (cost=0.00..94755.85 rows=23755
width=27)
Filter: ((deleted = false) AND
(original IS NULL))
(14 rows)

no_people=# \d contacts
Table "public.contacts"
Column | Type |
Modifiers
-------------+------------------------
+----------------------------------------------------------
id | integer | not null default nextval
('public.contacts_id_seq'::text)
record | integer |
type | integer |
value | character varying(128) |
description | character varying(255) |
priority | integer |
itescotype | integer |
original | integer |
source | integer |
reference | character varying(32) |
deleted | boolean | not null default false
quality | integer |
visible | boolean | not null default true
searchable | boolean | not null default true
Indexes:
"contacts_pkey" PRIMARY KEY, btree (id)
"contacts_deleted_idx" btree (deleted)
"contacts_record_idx" btree (record) CLUSTER
"contacts_source_reference_idx" btree (source, reference)

no_people=# \d addresses
Table "public.addresses"
Column | Type |
Modifiers
-------------+------------------------
+-----------------------------------------------------------
id | integer | not null default nextval
('public.addresses_id_seq'::text)
record | integer |
address | character varying(128) |
extra | character varying(32) |
postalcode | character varying(16) |
postalsite | character varying(64) |
description | character varying(255) |
position | point |
uncertainty | integer | default 99999999
priority | integer |
type | integer |
place | character varying(64) |
floor | integer |
side | character varying(8) |
housename | character varying(64) |
original | integer |
source | integer |
reference | character varying(32) |
deleted | boolean | not null default false
quality | integer |
visible | boolean | not null default true
searchable | boolean | not null default true
Indexes:
"addresses_pkey" PRIMARY KEY, btree (id)
"addresses_deleted_idx" btree (deleted)
"addresses_record_idx" btree (record) CLUSTER
"addresses_source_reference_idx" btree (source, reference)

no_people=# \d people
Table "public.people"
Column | Type |
Modifiers
------------+--------------------------
+--------------------------------------------------------
id | integer | not null default nextval
('public.people_id_seq'::text)
origid | integer |
firstname | character varying(128) | default ''::character varying
middlename | character varying(128) | default ''::character varying
lastname | character varying(128) | default ''::character varying
updated | timestamp with time zone | default
('now'::text)::timestamp(6) with time zone
updater | integer |
relevance | real | not null default 0
phonetic | text |
indexed | boolean | default false
record | text |
original | integer |
active | boolean | default true
title | character varying(128) |
deleted | boolean | not null default false
Indexes:
"people_pkey" PRIMARY KEY, btree (id)
"people_indexed_idx" btree (indexed)
"people_lower_lastname_firstname_idx" btree (lower
(lastname::text), lower(firstname::text))
"people_original_is_null" btree (original) WHERE original IS NULL
"people_relevance_idx" btree (relevance)
"person_updated_idx" btree (updated)

no_people=#