The original design: delete from watch_list_element where watch_list_element.element_id = 633 and watch_list_element.watch_list_id = 541; - when 1 row to delete: Index Scan using watch_list_element_pkey on watch_list_element (cost=0.00..6.01 rows=1 width=6) (actual time=0.27..0.28 rows=1 loops=1) Total runtime: 0.45 msec - when nothing to delete: Index Scan using watch_list_element_pkey on watch_list_element (cost=0.00..6.01 rows=1 width=6) (actual time=0.25..0.25 rows=0 loops=1) Total runtime: 0.39 msec This selects the row I want to delete: SELECT WLE.* FROM watch_list_element WLE, watch_list WL WHERE WLE.element_id = 633 AND WLE.watch_list_id = 541 AND WLE.watch_list_id = WL.id AND WL.user_id = 1336; Nested Loop (cost=0.00..11.35 rows=1 width=12) (actual time=0.56..0.60 rows=1 loops=1) -> Index Scan using watch_list_element_pkey on watch_list_element wle (cost=0.00..6.01 rows=1 width=8) (actual time=0.28..0.30 rows=1 loops=1) -> Index Scan using watch_list_pkey on watch_list wl (cost=0.00..5.33 rows=1 width=4) (actual time=0.25..0.26 rows=1 loops=1) Total runtime: 0.79 msec - when nothing to select: Nested Loop (cost=0.00..11.35 rows=1 width=12) (actual time=0.23..0.23 rows=0 loops=1) -> Index Scan using watch_list_element_pkey on watch_list_element wle (cost=0.00..6.01 rows=1 width=8) (actual time=0.21..0.21 rows=0 loops=1) -> Index Scan using watch_list_pkey on watch_list wl (cost=0.00..5.33 rows=1 width=4) Total runtime: 0.40 msec This deletes it. Odd, I couldn't use "watch_list_element WLE" here: DELETE FROM watch_list_element WHERE EXISTS ( SELECT watch_list_element.* FROM watch_list WL WHERE watch_list_element.element_id = 633 AND watch_list_element.watch_list_id = 541 AND WL.user_id = 1336 AND watch_list_element.watch_list_id = WL.id ); - when 1 row to delete: Seq Scan on watch_list_element (cost=0.00..336680.44 rows=31500 width=6) (actual time=406.85..955.33 rows=1 loops=1) SubPlan -> Result (cost=0.00..5.33 rows=1 width=0) (actual time=0.01..0.01 rows=0 loops=62999) -> Index Scan using watch_list_pkey on watch_list wl (cost=0.00..5.33 rows=1 width=0) (actual time=0.32..0.32 rows=1 loops=1) Total runtime: 955.88 msec - when nothing to delete: Seq Scan on watch_list_element (cost=0.00..336680.44 rows=31500 width=6) (actual time=778.56..778.56 rows=0 loops=1) SubPlan -> Result (cost=0.00..5.33 rows=1 width=0) (actual time=0.01..0.01 rows=0 loops=62998) -> Index Scan using watch_list_pkey on watch_list wl (cost=0.00..5.33 rows=1 width=0) Total runtime: 778.76 msec I also tried SELECT * instead of watch_list_element.*: DELETE FROM watch_list_element WHERE watch_list_element.element_id = 633 AND watch_list.id = 541 AND watch_list.user_id = 1336 AND watch_list_element.watch_list_id = watch_list.id; - when 1 row to delete: Nested Loop (cost=0.00..11.35 rows=1 width=14) (actual time=0.61..0.65 rows=1 loops=1) -> Index Scan using watch_list_pkey on watch_list (cost=0.00..5.33 rows=1 width=4) (actual time=0.30..0.32 rows=1 loops=1) -> Index Scan using watch_list_element_pkey on watch_list_element (cost=0.00..6.01 rows=1 width=10) (actual time=0.27..0.29 rows=1 loops=1) Total runtime: 1.09 msec - when nothing to delete: Nested Loop (cost=0.00..11.35 rows=1 width=14) (actual time=0.55..0.55 rows=0 loops=1) -> Index Scan using watch_list_pkey on watch_list (cost=0.00..5.33 rows=1 width=4) (actual time=0.26..0.27 rows=1 loops=1) -> Index Scan using watch_list_element_pkey on watch_list_element (cost=0.00..6.01 rows=1 width=10) (actual time=0.25..0.25 rows=0 loops=1) Total runtime: 0.75 msec