title: DELETE records which do not have a match in another table
body: <p>There are two tables linked by an id:</p>
  
  <pre><code>item_tbl (id)
  link_tbl (item_id)
  </code></pre>
  
  <p>There are some records in <code>item_tbl</code> that don't have matching rows in <code>link_tbl</code>. A select which would count their amount would be:</p>
  
  <pre><code>SELECT COUNT(*)
  FROM link_tbl lnk LEFT JOIN item_tbl itm ON lnk.item_id=itm.id
  WHERE itm.id IS NULL
  </code></pre>
  
  <p>I would like to delete those orphan records (those which don't have match in the other table) from <code>link_tbl</code> but the only way I could think of was:</p>
  
  <pre><code>DELETE FROM link_tbl lnk
  WHERE lnk.item_id NOT IN (SELECT itm.id FROM item_tbl itm)
  </code></pre>
  
  <p>There are<br>
  <strong>262,086,253</strong> records in <code>link_tbl</code><br>
  <strong>3,033,811</strong> in <code>item_tbl</code><br>
  <strong>16,844,347</strong> orphan records in <code>link_tbl</code>.<br>
  The server has 4GB RAM and 8 core CPU.</p>
  
  <pre><code>EXPLAIN DELETE FROM link_tbl lnk
  WHERE lnk.item_id NOT IN (SELECT itm.id FROM item_tbl itm)
  </code></pre>
  
  <p>Returns:</p>
  
  <pre><code>Delete on link lnk  (cost=0.00..11395249378057.98 rows=131045918 width=6)
  -&gt;  Seq Scan on link lnk  (cost=0.00..11395249378057.98 rows=131045918 width=6)
       Filter: (NOT (SubPlan 1))
       SubPlan 1
         -&gt;  Materialize  (cost=0.00..79298.10 rows=3063207 width=4)
               -&gt;  Seq Scan on item itm  (cost=0.00..52016.07 rows=3063207 width=4)
  </code></pre>
  
  <p>The questions are:</p>
  
  <ol>
  <li>Is there any better way how to delete orphan records from <code>link_tbl</code>?</li>
  <li><p>How accurate is the explain above, or how long it could take to delete those records?</p>
  
  <ul>
  <li>Edit: fixed according to Erwin Brandstetter comment.<br></li>
  <li>Edit: PostgreSql version is 9.1</li>
  <li>Edit: some parts of postgresql.config
  
  <ol>
  <li>shared_buffers = 368MB</li>
  <li>temp_buffers = 32MB</li>
  <li>work_mem = 32MB</li>
  <li>maintenance_work_mem = 64MB</li>
  <li>max_stack_depth = 6MB </li>
  <li>fsync = off</li>
  <li>synchronous_commit = off</li>
  <li>full_page_writes = off</li>
  <li>wal_buffers = 16MB</li>
  <li>wal_writer_delay = 5000ms</li>
  <li>commit_delay = 10</li>
  <li>commit_siblings = 10</li>
  <li>effective_cache_size = 1600MB</li>
  </ol></li>
  </ul></li>
  </ol>
  
  <p><strong>Resolution:</strong></p>
  
  <p>Thank you all for your advices, it was very helpful. I finally used the delete advised by Erwin Brandstetter <a href="https://stackoverflow.com/a/15959896/1331340">https://stackoverflow.com/a/15959896/1331340</a> but I tweaked it a little:</p>
  
  <pre><code>DELETE FROM link_tbl lnk
  WHERE lnk.item_id BETWEEN 0 AND 10000
    AND lnk.item_id NOT IN (SELECT itm.id FROM item itm
                            WHERE itm.id BETWEEN 0 AND 10000)
  </code></pre>
  
  <p>I compared results for NOT IN and NOT EXISTS and the output is below, although I used COUNT instead of DELETE which I think should be the same (I mean in sake of relative comparison):</p>
  
  <pre><code>EXPLAIN ANALYZE SELECT COUNT(*) 
  FROM link_tbl lnk
  WHERE lnk.item_id BETWEEN 0 AND 20000
    AND lnk.item_id NOT IN (SELECT itm.id
                            FROM item_tbl itm
                            WHERE itm.id BETWEEN 0 AND 20000);
  
  QUERY PLAN
  Aggregate  (cost=6002667.56..6002667.57 rows=1 width=0) (actual time=226817.086..226817.088 rows=1 loops=1)
  -&gt;  Seq Scan on link_tbl lnk  (cost=1592.50..5747898.65 rows=101907564 width=0) (actual time=206.029..225289.570 rows=566625 loops=1)
       Filter: ((item_id &gt;= 0) AND (item_id &lt;= 20000) AND (NOT (hashed SubPlan 1)))
       SubPlan 1
         -&gt;  Index Scan using item_tbl_pkey on item_tbl itm  (cost=0.00..1501.95 rows=36221 width=4) (actual time=0.056..99.266 rows=17560 loops=1)
               Index Cond: ((id &gt;= 0) AND (id &lt;= 20000))
  Total runtime: 226817.211 ms
  
  
  EXPLAIN ANALYZE SELECT COUNT(*)
  FROM link_tbl lnk WHERE lnk.item_id&gt;0 AND lnk.item_id&lt;20000
    AND NOT EXISTS (SELECT 1 FROM item_tbl itm WHERE itm.id=lnk.item_id);
  
  QUERY PLAN
  Aggregate  (cost=8835772.00..8835772.01 rows=1 width=0)
     (actual time=1209235.133..1209235.135 rows=1 loops=1)
  -&gt;  Hash Anti Join  (cost=102272.16..8835771.99 rows=1 width=0)
     (actual time=19315.170..1207900.612 rows=566534 loops=1)
       Hash Cond: (lnk.item_id = itm.id)
       -&gt;  Seq Scan on link_tbl lnk  (cost=0.00..5091076.55 rows=203815128 width=4) (actual time=0.016..599147.604 rows=200301872 loops=1)
             Filter: ((item_id &gt; 0) AND (item_id &lt; 20000))
       -&gt;  Hash  (cost=52016.07..52016.07 rows=3063207 width=4) (actual time=19313.976..19313.976 rows=3033811 loops=1)
             Buckets: 131072  Batches: 4  Memory Usage: 26672kB
             -&gt;  Seq Scan on item_tbl itm  (cost=0.00..52016.07 rows=3063207 width=4) (actual time=0.013..9274.158 rows=3033811 loops=1)
  Total runtime: 1209260.228 ms
  </code></pre>
  
  <p>NOT EXISTS was 5 times slower.</p>
  
  <p>The actual delete of the data didn't take so long as I was worried, I was able to delete it in 5 batches (10000-20000,20000-100000,100000-200000,200000-1000000 and 1000000-1755441). At first I found out max item_id and I only had to went through half of the table.</p>
  
  <p>When I tried NOT IN or EXISTS without the range (with select count) it didn't even finish, I let it run during the night and it was still running in the morning.</p>
  
  <p>I think I was looking for DELETE with USING from wildplasser's answer <a href="https://stackoverflow.com/a/15988033/1331340">https://stackoverflow.com/a/15988033/1331340</a> but it came too late.</p>
  
  <pre><code>DELETE FROM one o
  USING (
      SELECT o2.id
      FROM one o2
      LEFT JOIN two t ON t.one_id = o2.id
      WHERE t.one_id IS NULL
      ) sq
  WHERE sq.id = o.id
      ;
  </code></pre>