Otimize a exclusão do Postgres de registros órfãos

Uma abordagem para problemas como esse pode ser fazê-lo em partes menores.

DELETE FROM "contacts"
WHERE  "contacts"."id" IN (
    SELECT id
    FROM contacts
    LEFT OUTER JOIN members ON members.contact_id = contacts.id 
    WHERE members.id IS NULL
        AND id >= 1 AND id < 1000
);
DELETE FROM "contacts"
WHERE  "contacts"."id" IN (
    SELECT id
    FROM contacts
    LEFT OUTER JOIN members ON members.contact_id = contacts.id 
    WHERE members.id IS NULL
        AND id >= 1001 AND id < 2000
);

Enxaguar, repetir. Experimente diferentes tamanhos de blocos para encontrar um ideal para seu conjunto de dados, que use o menor número de consultas, mantendo todas elas na memória.

Naturalmente, você gostaria de criar um script, possivelmente em plpgsql, ou em qualquer linguagem de script de sua preferência.