title: Optimize Postgres deletion of orphaned records
body: <p>Take the following two tables:</p>
  
  <pre class="lang-sql prettyprint-override"><code>Table "public.contacts"
         Column       |            Type             |                       Modifiers                       | Storage  | Stats target | Description
  --------------------+-----------------------------+-------------------------------------------------------+----------+--------------+-------------
   id                 | integer                     | not null default nextval('contacts_id_seq'::regclass) | plain    |              |
   created_at         | timestamp without time zone | not null                                              | plain    |              |
   updated_at         | timestamp without time zone | not null                                              | plain    |              |
   external_id        | integer                     |                                                       | plain    |              |
   email_address      | character varying           |                                                       | extended |              |
   first_name         | character varying           |                                                       | extended |              |
   last_name          | character varying           |                                                       | extended |              |
   company            | character varying           |                                                       | extended |              |
   industry           | character varying           |                                                       | extended |              |
   country            | character varying           |                                                       | extended |              |
   region             | character varying           |                                                       | extended |              |
   ext_instance_id    | integer                     |                                                       | plain    |              |
   title              | character varying           |                                                       | extended |              |
  Indexes:
      "contacts_pkey" PRIMARY KEY, btree (id)
      "index_contacts_on_ext_instance_id_and_external_id" UNIQUE, btree (ext_instance_id, external_id)
  </code></pre>
  
  <p>and</p>
  
  <pre><code>Table "public.members"
          Column         |            Type             |                             Modifiers                              | Storage  | Stats target | Description
  -----------------------+-----------------------------+--------------------------------------------------------------------+----------+--------------+-------------
   id                    | integer                     | not null default nextval('members_id_seq'::regclass)               | plain    |              |
   step_id               | integer                     |                                                                    | plain    |              |
   contact_id            | integer                     |                                                                    | plain    |              |
   rule_id               | integer                     |                                                                    | plain    |              |
   request_id            | integer                     |                                                                    | plain    |              |
   sync_id               | integer                     |                                                                    | plain    |              |
   status                | integer                     | not null default 0                                                 | plain    |              |
   matched_targeted_rule | boolean                     | default false                                                      | plain    |              |
   external_fields       | jsonb                       |                                                                    | extended |              |
   imported_at           | timestamp without time zone |                                                                    | plain    |              |
   campaign_id           | integer                     |                                                                    | plain    |              |
   ext_instance_id       | integer                     |                                                                    | plain    |              |
   created_at            | timestamp without time zone |                                                                    | plain    |              |
  Indexes:
      "members_pkey" PRIMARY KEY, btree (id)
      "index_members_on_contact_id_and_step_id" UNIQUE, btree (contact_id, step_id)
      "index_members_on_campaign_id" btree (campaign_id)
      "index_members_on_step_id" btree (step_id)
      "index_members_on_sync_id" btree (sync_id)
      "index_members_on_request_id" btree (request_id)
      "index_members_on_status" btree (status)
  </code></pre>
  
  <p>Indices exist for both primary keys and <code>members.contact_id</code>.</p>
  
  <p>I need to delete any <code>contact</code> which has no related <code>members</code>. There are roughly 3MM <code>contact</code> and 25MM <code>member</code> records.</p>
  
  <p>I'm attempting the following two queries:</p>
  
  <h2>Query 1:</h2>
  
  <pre><code>DELETE FROM "contacts"
  WHERE  "contacts"."id" IN (SELECT "contacts"."id" 
                             FROM   "contacts" 
                                    LEFT OUTER JOIN members 
                                                 ON 
                                    members.contact_id = contacts.id 
                             WHERE  members.id IS NULL);
  
  DELETE 0
  Time: 173033.801 ms
  
  -----------------------------------------------------------------------------------------------------------------------------------------------------------------
   Delete on contacts  (cost=2654306.79..2654307.86 rows=1 width=18) (actual time=188717.354..188717.354 rows=0 loops=1)
     -&gt;  Nested Loop  (cost=2654306.79..2654307.86 rows=1 width=18) (actual time=188717.351..188717.351 rows=0 loops=1)
           -&gt;  HashAggregate  (cost=2654306.36..2654306.37 rows=1 width=16) (actual time=188717.349..188717.349 rows=0 loops=1)
                 Group Key: contacts_1.id
                 -&gt;  Hash Right Join  (cost=161177.46..2654306.36 rows=1 width=16) (actual time=188717.345..188717.345 rows=0 loops=1)
                       Hash Cond: (members.contact_id = contacts_1.id)
                       Filter: (members.id IS NULL)
                       Rows Removed by Filter: 26725870
                       -&gt;  Seq Scan on members  (cost=0.00..1818698.96 rows=25322396 width=14) (actual time=0.043..160226.686 rows=26725870 loops=1)
                       -&gt;  Hash  (cost=105460.65..105460.65 rows=3205265 width=10) (actual time=1962.612..1962.612 rows=3196180 loops=1)
                             Buckets: 262144  Batches: 4  Memory Usage: 34361kB
                             -&gt;  Seq Scan on contacts contacts_1  (cost=0.00..105460.65 rows=3205265 width=10) (actual time=0.011..950.657 rows=3196180 loops=1)
           -&gt;  Index Scan using contacts_pkey on contacts  (cost=0.43..1.48 rows=1 width=10) (never executed)
                 Index Cond: (id = contacts_1.id)
   Planning time: 0.488 ms
   Execution time: 188718.862 ms
  </code></pre>
  
  <h2>Query 2:</h2>
  
  <pre><code>DELETE FROM contacts 
  WHERE  NOT EXISTS (SELECT 1 
                     FROM   members c 
                     WHERE  c.contact_id = contacts.id); 
  
  DELETE 0
  Time: 170871.219 ms
  
  -------------------------------------------------------------------------------------------------------------------------------------------------------------
   Delete on contacts  (cost=2258873.91..2954594.50 rows=1895601 width=12) (actual time=177523.034..177523.034 rows=0 loops=1)
     -&gt;  Hash Anti Join  (cost=2258873.91..2954594.50 rows=1895601 width=12) (actual time=177523.029..177523.029 rows=0 loops=1)
           Hash Cond: (contacts.id = c.contact_id)
           -&gt;  Seq Scan on contacts  (cost=0.00..105460.65 rows=3205265 width=10) (actual time=0.018..1068.357 rows=3196180 loops=1)
           -&gt;  Hash  (cost=1818698.96..1818698.96 rows=25322396 width=10) (actual time=169587.802..169587.802 rows=26725870 loops=1)
                 Buckets: 262144  Batches: 32  Memory Usage: 36228kB
                 -&gt;  Seq Scan on members c  (cost=0.00..1818698.96 rows=25322396 width=10) (actual time=0.052..160081.880 rows=26725870 loops=1)
   Planning time: 0.901 ms
   Execution time: 177524.526 ms
  </code></pre>
  
  <p>As you can see that without even deleting any records both queries show similar performance taking ~3 minutes.</p>
  
  <p>The server disk I/O spikes to 100% so I'm assuming that data is being spilled out to the disk because a sequential scan is done on both <code>contacts</code> and <code>members</code>.</p>
  
  <p>The server is an EC2 r3.large (15GB RAM).</p>
  
  <p>Any ideas on what I can do to optimize this query?</p>
  
  <h2>Update #1:</h2>
  
  <p>After running <code>vacuum analyze</code> for both tables and ensuring <code>enable_mergejoin</code> is set to <code>on</code> there is no difference in the query time:</p>
  
  <pre><code>DELETE FROM contacts 
  WHERE  NOT EXISTS (SELECT 1 
                     FROM   members c 
                     WHERE  c.contact_id = contacts.id); 
  
  -------------------------------------------------------------------------------------------------------------------------------------------------------------
   Delete on contacts  (cost=2246088.17..2966677.08 rows=1875003 width=12) (actual time=209406.342..209406.342 rows=0 loops=1)
     -&gt;  Hash Anti Join  (cost=2246088.17..2966677.08 rows=1875003 width=12) (actual time=209406.338..209406.338 rows=0 loops=1)
           Hash Cond: (contacts.id = c.contact_id)
           -&gt;  Seq Scan on contacts  (cost=0.00..105683.28 rows=3227528 width=10) (actual time=0.008..1010.643 rows=3227462 loops=1)
           -&gt;  Hash  (cost=1814029.74..1814029.74 rows=24855474 width=10) (actual time=198054.302..198054.302 rows=27307060 loops=1)
                 Buckets: 262144  Batches: 32  Memory Usage: 37006kB
                 -&gt;  Seq Scan on members c  (cost=0.00..1814029.74 rows=24855474 width=10) (actual time=1.132..188654.555 rows=27307060 loops=1)
   Planning time: 0.328 ms
   Execution time: 209408.040 ms
  </code></pre>
  
  <h2>Update 2:</h2>
  
  <p>PG Version:</p>
  
  <pre><code>PostgreSQL 9.4.4 on x86_64-pc-linux-gnu, compiled by x86_64-pc-linux-gnu-gcc (Gentoo Hardened 4.5.4 p1.0, pie-0.4.7) 4.5.4, 64-bit
  </code></pre>
  
  <p>Relation size:</p>
  
  <pre><code>         Table         |  Size   | External Size
  -----------------------+---------+---------------
   members               | 23 GB   | 11 GB
   contacts              | 944 MB  | 371 MB
  </code></pre>
  
  <p>Settings:</p>
  
  <pre><code> work_mem
  ----------
   64MB
  
   random_page_cost
  ------------------
   4
  </code></pre>
  
  <h2>Update 3:</h2>
  
  <p>Experimenting with doing this in batches doesn't seem to help out on the I/O usage (still spikes to 100%) and doesn't seem to improve on time despite using index-based plans.</p>
  
  <pre><code>DO $do$ 
  BEGIN 
    FOR i IN 57..668 
    LOOP 
      DELETE 
      FROM   contacts 
      WHERE  contacts.id IN 
             ( 
                             SELECT          contacts.id 
                             FROM            contacts 
                             left outer join members 
                             ON              members.contact_id = contacts.id 
                             WHERE           members.id IS NULL 
                             AND             contacts.id &gt;= (i    * 10000) 
                             AND             contacts.id &lt; ((i+1) * 10000));
  END LOOP;END $do$;
  </code></pre>
  
  <p>I had to kill the query after <code>Time: 1203492.326 ms</code> and disk I/O stayed at 100% the entire time the query ran. I also experimented with 1,000 and 5,000 chunks but did not see any increase in performance.</p>
  
  <p>Note: The <code>57..668</code> range was used because I know those are existing contact IDs. (E.g. <code>min(id)</code> and <code>max(id)</code>)</p>