Deleting orphaned records to establish Ref Integrity

I have several large tables (10 million to 200 million rows) that have
foreign keys with each other by *convention*, but no actual FOREIGN KEY
constraints.

Over the course of years, orphaned records (children with no parent) have
accumulated and now I want to clean them up. I can't just create the FK
constraint because the orphans cause violations. Executing something like
the following statement would work, but even with indexes it takes an
insane amount of time to execute for each of the tables:

DELETE FROM child_table WHERE parentid NOT IN
(SELECT parentid FROM parent_table)

Are there any better ways to accomplish this task? I've brainstormed
extensively and searched the list archives to no avail. It goes without
saying that once the cleanup is done, FK constraints will be added so this
is never a mess again!

I am using PostgreSQL 7.4.6 on Linux, although I could restore these
tables on an 8.0.3 server if it would make things go faster!

Thanks,
Roman

_____________________________________
Check All Email Accounts Anywhere!
Check your POP3 and webmail account
from any PC. With no ads
http://www.fusemail.com

_____________________________________
Consolidate your email!
http://www.fusemail.com