The original design: delete from watch_list_element where watch_list_element.element_id = 4405 and watch_list_element.watch_list_id = 31; - when nothing to delete: Seq Scan on watch_list_element (cost=0.00..0.00 rows=1 width=6) (actual time=0.10..0.10 rows=0 loops=1) Total runtime: 0.20 msec - when 1 row to delete: Seq Scan on watch_list_element (cost=0.00..0.00 rows=1 width=6) (actual time=0.10..0.11 rows=1 loops=1) Total runtime: 0.25 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 = 4405 AND watch_list_element.watch_list_id = 31 AND WL.user_id = 2 AND watch_list_element.watch_list_id = WL.id ); - when 1 row to delete: Seq Scan on watch_list_element (cost=0.00..0.00 rows=1 width=6) (actual time=0.23..0.27 rows=1 loops=1) SubPlan -> Result (cost=0.00..1.01 rows=1 width=0) (actual time=0.02..0.02 rows=0 loops=6) -> Seq Scan on watch_list wl (cost=0.00..1.01 rows=1 width=0) (actual time=0.07..0.07 rows=1 loops=1) Total runtime: 0.43 msec - when nothing to delete: Seq Scan on watch_list_element (cost=0.00..0.00 rows=1 width=6) (actual time=0.10..0.10 rows=0 loops=1) SubPlan -> Result (cost=0.00..1.01 rows=1 width=0) (actual time=0.01..0.01 rows=0 loops=5) -> Seq Scan on watch_list wl (cost=0.00..1.01 rows=1 width=0) Total runtime: 0.23 msec I also tried SELECT * instead of watch_list_element.*: