Most databases transform a NOT IN query to NOT EXISTS when possible, because the semantic is the same with NOT NULL resultsets (if they are not, see NOT IN vs. NOT EXISTS: often a data modeling issue). PostgreSQL doesn't and this leads to performance issues (see Recovering TPS After a Cross-Database Migration by Vinay Kumar Dumpa).
PostgreSQL 19 will fix that and transform NOT IN to NOT EXISTS, when NOT NULL is guaranteed, so that a SubPlan or hashed SubPlan becomes an anti-join that can benefit from all join methods: Nested Loop, Merge Join or Hash Join.
I'll demonstrate that at PostgreSQL Conference Europe 2026 (Postgres 19, 20, & Beyond: Live Demos of New Features & Tools) with the following example:
postgres=# explain (analyze OFF, buffers, verbose, costs ON)
select count(*) from demo
where key not in (
select key from demo
);
QUERY PLAN
------------------------------------------------------------------------ Aggregate (cost=18693858641.69..18693858641.70 rows=1 width=8)
Output: count(*)
-> Seq Scan on public.demo
(cost=0.42..18693857391.67 rows=500005 width=0)
Output: demo.key, demo.value
Filter: (NOT (ANY (demo.key = (SubPlan 1).col1)))
SubPlan 1
-> Materialize (cost=0.42..34887.62 rows=1000010 width=8)
Output: demo_1.key
-> Index Only Scan using demo_pkey on public.demo
(cost=0.42..25980.58 rows=1000010 width=8)
Output: demo_1.key
This was in PostgreSQL 18 and the EXPLAIN (ANALYZE ON) is still running.
The same in PostgreSQL 19 beta 3 runs in three seconds:
postgres=# explain (analyze on, buffers, verbose, costs off)
select count(*) from demo
where key not in (
select key from demo
);
QUERY PLAN
--------------------------------------------------------------------------
Aggregate (actual time=3258.030..3258.037 rows=1.00 loops=1)
Output: count(*)
Buffers: shared hit=5474
-> Merge Anti Join (actual time=3258.022..3258.026 rows=0.00 loops=1)
Inner Unique: true
Merge Cond: (demo.key = demo_1.key)
Buffers: shared hit=5474
-> Index Only Scan using demo_pkey on public.demo
(actual time=0.052..819.263 rows=1000000.00 loops=1)
Output: demo.key
Heap Fetches: 0
Index Searches: 1
Buffers: shared hit=2737
-> Index Only Scan using demo_pkey on public.demo demo_1
(actual time=0.030..815.955 rows=1000000.00 loops=1)
Output: demo_1.key
Heap Fetches: 0
Index Searches: 1
Buffers: shared hit=2737
I also reproduced the examples from Vinay blog post and got the following:
| Version | Index state | Query shape | Main plan node | Execution time |
|---|---|---|---|---|
| PG18 | no FK index | NOT IN | SubPlan 1 re-scan | 17444.689 ms |
| PG18 | no FK index | NOT EXISTS | Hash Right Anti Join | 2905.400 ms |
| PG18 | no FK index | LEFT JOIN IS NULL | Hash Right Anti Join | 3008.620 ms |
| PG18 | FK index | NOT IN | still SubPlan 1 | 17199.510 ms |
| PG18 | FK index | NOT EXISTS | Nested Loop Anti Join + Index Only Scan, Heap Fetches: 0 | 4.327 ms |
| PG18 | FK index | LEFT JOIN IS NULL | Nested Loop Anti Join + Index Only Scan, Heap Fetches: 0 | 2.207 ms |
| PG19 beta | no FK index | NOT IN | Hash Right Anti Join | 2862.253 ms |
| PG19 beta | no FK index | NOT EXISTS | Hash Right Anti Join | 2876.597 ms |
| PG19 beta | no FK index | LEFT JOIN IS NULL | Hash Right Anti Join | 3002.127 ms |
| PG19 beta | FK index | NOT IN | Nested Loop Anti Join + Index Only Scan, Heap Fetches: 0 | 3.246 ms |
| PG19 beta | FK index | NOT EXISTS | Nested Loop Anti Join + Index Only Scan, Heap Fetches: 0 | 2.459 ms |
| PG19 beta | FK index | LEFT JOIN IS NULL | Nested Loop Anti Join + Index Only Scan, Heap Fetches: 0 | 2.297 ms |
Here is the best plan for NOT IN in PostgreSQL 18:
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=5323187.53..5323187.54 rows=2 width=69) (actual time=17180.752..17180.795 rows=3.00 loops=1)
Buffers: shared hit=26390, temp read=12785 written=3360
-> Sort (cost=5323187.53..5323187.54 rows=2 width=69) (actual time=17003.001..17003.023 rows=3.00 loops=1)
Sort Key: o.order_date DESC
Sort Method: quicksort Memory: 25kB
Buffers: shared hit=26390, temp read=12785 written=3360
-> Nested Loop (cost=27625.18..5323187.52 rows=2 width=69) (actual time=16548.945..17002.862 rows=3.00 loops=1)
Join Filter: (p.product_id = o.product_id)
Rows Removed by Join Filter: 149997
Buffers: shared hit=26387, temp read=12785 written=3360
-> Seq Scan on products p (cost=0.00..902.00 rows=50000 width=27) (actual time=0.028..53.334 rows=50000.00 loops=1)
Buffers: shared hit=402
-> Materialize (cost=27625.18..5320785.53 rows=2 width=50) (actual time=0.118..0.334 rows=3.00 loops=50000)
Storage: Memory Maximum Storage: 17kB
Buffers: shared hit=25985, temp read=12785 written=3360
-> Nested Loop (cost=27625.18..5320785.52 rows=2 width=50) (actual time=5865.203..16536.107 rows=3.00 loops=1)
Buffers: shared hit=25985, temp read=12785 written=3360
-> Index Scan using customers_pkey on customers c (cost=0.29..8.30 rows=1 width=26) (actual time=0.020..0.032 rows=1.00 loops=1)
Index Cond: (customer_id = 42)
Index Searches: 1
Buffers: shared hit=3
-> Bitmap Heap Scan on orders o (cost=27624.90..5320777.19 rows=2 width=32) (actual time=5865.020..16535.894 rows=3.00 loops=1)
Recheck Cond: ((customer_id = 42) AND (order_id <= 1500000))
Filter: ((order_status <> 'CANCELLED'::text) AND (product_id >= 1000) AND (product_id <= 3000) AND (NOT (ANY (order_id = (SubPlan 1).col1))))
Rows Removed by Filter: 162
Heap Blocks: exact=164
Buffers: shared hit=25982, temp read=12785 written=3360
-> BitmapAnd (cost=27624.90..27624.90 rows=149 width=0) (actual time=58.263..58.267 rows=0.00 loops=1)
Buffers: shared hit=4104
-> Bitmap Index Scan on idx_orders_customer_id (cost=0.00..6.67 rows=299 width=0) (actual time=0.026..0.027 rows=308.00 loops=1)
Index Cond: (customer_id = 42)
Index Searches: 1
Buffers: shared hit=3
-> Bitmap Index Scan on orders_pkey (cost=0.00..27617.97 rows=1495139 width=0) (actual time=58.200..58.200 rows=1500000.00 loops=1)
Index Cond: (order_id <= 1500000)
Index Searches: 1
Buffers: shared hit=4101
SubPlan 1
-> Materialize (cost=0.00..67214.78 rows=1530659 width=8) (actual time=0.033..1095.621 rows=816222.33 loops=9)
Storage: Disk Maximum Storage: 26875kB
Buffers: shared hit=21714, temp read=12785 written=3360
-> Seq Scan on order_validations v (cost=0.00..53581.49 rows=1530659 width=8) (actual time=0.032..1653.223 rows=1528882.00 loops=1)
Filter: (validation_state = 'PASSED'::text)
Rows Removed by Filter: 1020517
Buffers: shared hit=21714
Planning:
Buffers: shared hit=326 read=1
Planning Time: 1.935 ms
JIT:
Functions: 22
Options: Inlining true, Optimization true, Expressions true, Deforming true
Timing: Generation 0.832 ms (Deform 0.434 ms), Inlining 60.858 ms, Optimization 60.745 ms, Emission 56.440 ms, Total 178.876 ms
Execution Time: 17199.510 ms
Here is the best plan for NOT IN in PostgreSQL 19:
QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=1152.11..1152.12 rows=2 width=68) (actual time=3.136..3.156 rows=2.00 loops=1)
Buffers: shared hit=327 read=8
-> Sort (cost=1152.11..1152.12 rows=2 width=68) (actual time=3.133..3.148 rows=2.00 loops=1)
Sort Key: o.order_date DESC
Sort Method: quicksort Memory: 25kB
Buffers: shared hit=327 read=8
-> Nested Loop (cost=7.68..1152.10 rows=2 width=68) (actual time=0.535..3.119 rows=2.00 loops=1)
Buffers: shared hit=324 read=8
-> Nested Loop (cost=7.39..1135.49 rows=2 width=50) (actual time=0.518..3.091 rows=2.00 loops=1)
Buffers: shared hit=318 read=8
-> Index Scan using customers_pkey on customers c (cost=0.29..8.30 rows=1 width=26) (actual time=0.020..0.023 rows=1.00 loops=1)
Index Cond: (customer_id = 42)
Index Searches: 1
Buffers: shared hit=3
-> Nested Loop Anti Join (cost=7.10..1127.16 rows=2 width=32) (actual time=0.494..3.058 rows=2.00 loops=1)
Buffers: shared hit=315 read=8
-> Bitmap Heap Scan on orders o (cost=6.67..1109.34 rows=4 width=32) (actual time=0.174..2.008 rows=4.00 loops=1)
Recheck Cond: (customer_id = 42)
Filter: ((order_status <> 'CANCELLED'::text) AND (product_id >= 1000) AND (product_id <= 3000) AND (order_id <= 1500000))
Rows Removed by Filter: 305
Heap Blocks: exact=307
Buffers: shared hit=310
-> Bitmap Index Scan on idx_orders_customer_id (cost=0.00..6.67 rows=299 width=0) (actual time=0.042..0.042 rows=309.00 loops=1)
Index Cond: (customer_id = 42)
Index Searches: 1
Buffers: shared hit=3
-> Index Only Scan using idx_order_validations_order_id on order_validations v (cost=0.43..4.45 rows=1 width=8) (actual time=0.257..0.257 rows=0.50 loops=4)
Index Cond: ((order_id = o.order_id) AND (validation_state = 'PASSED'::text))
Heap Fetches: 0
Index Searches: 4
Buffers: shared hit=5 read=8
-> Index Scan using products_pkey on products p (cost=0.29..8.31 rows=1 width=26) (actual time=0.008..0.009 rows=1.00 loops=2)
Index Cond: (product_id = o.product_id)
Index Searches: 2
Buffers: shared hit=6
Planning:
Buffers: shared hit=434 read=6
Planning Time: 2.824 ms
Execution Time: 3.246 ms
Conclusion
This reproduction confirms the performance issue is mainly a plan-shape problem, not just a missing index. On PostgreSQL 18, the NOT IN form is a materialized SubPlan that repeatedly scans the validation result. Adding a foreign-key index doesn't significantly improve this. Rewriting as NOT EXISTS or LEFT JOIN ... IS NULL allows the optimizer to optimize the anti-join. With a covering index, PostgreSQL switches to a Nested Loop Anti Join with index-only lookup, reducing execution time from seconds to milliseconds.
PostgreSQL 19 beta results differ: it transforms the NOT IN predicate into an anti-join in this workload, enabling effective FK index use. Behavior varies by version, so verify with EXPLAIN (ANALYZE, BUFFERS, SETTINGS) on the target release instead of relying on PostgreSQL 18 behavior.
Microsoft supports many Azure Database for PostgreSQL migrations, including large, critical databases. Feedback from these workloads not only guides customer improvements but also contributes to PostgreSQL core development. In PostgreSQL 19, Richard Guo's proposed patch resolves the NOT IN issue present in PostgreSQL 18. His work shows how feedback from enterprise workload migrations helps improve PostgreSQL optimizer's transformations in future versions
Planned for PostgreSQL 19:
- Convert
NOT INsublinks to anti-joins when safe - Eager aggregation below joins
- Improved semijoin planning
- Explicit incremental sort for
AppendandMergeAppend - Simplify
IS [NOT] DISTINCT FROMfor proven non-null values - Earlier folding of
Var IS [NOT] NULL
Proposed for PostgreSQL 20
Top comments (0)