NOT EXISTS vs EXISTS with partial indexes — 26x speedup benchmark (PG18, 50M rows)

Summary

Benchmark: NOT EXISTS(deleted) vs EXISTS(NOT deleted) on a soft-delete pattern.

Blog post MR: postgres-ai/docs!885 (merged)

Environment

  • PG18, CCX33 (8 vCPU, 32 GiB RAM), Hetzner NBG1
  • shared_buffers=8GB, effective_cache_size=24GB, work_mem=64MB, maintenance_work_mem=1GB
  • 50M rows, 13 GiB heap, 2% deleted (1,001,091 rows)
  • autovacuum_enabled=false — VM state fully deterministic
  • Correct setup sequence:
    1. INSERT 50M rows
    2. CREATE INDEX (both partial indexes)
    3. vacuum analyze posts — fills visibility map cleanly
    4. vacuum analyze post_tags
    5. update posts set content = repeat('y', 200) where post_id % 10 = 0 — dirties 10% of pages
    6. analyze posts — refresh stats only, VM stays dirty
    7. Verify: last_autovacuum IS NULL
  • Cold cache: systemctl stop postgresql && echo 3 > /proc/sys/vm/drop_caches && systemctl start postgresql before each query
  • Hot cache: pg_prewarm on both indexes + heap

Schema 

create table posts (
    post_id  bigint primary key,
    deleted  boolean not null default false,
    content  text not null default repeat('x', 200)
) with (autovacuum_enabled = false);

-- 98% of rows — 1,050 MB:
create unique index posts_not_deleted_id_key on posts (post_id) where not deleted;
-- 2% of rows — 22 MB:
create unique index posts_deleted_id_key     on posts (post_id) where deleted;

create table post_tags (
    tag_id   int not null,
    post_id  bigint not null,
    primary key (tag_id, post_id)
) with (autovacuum_enabled = false);

Results Summary

Cold cache

scale Q1: EXISTS(NOT deleted) Q2: NOT EXISTS(deleted) speedup Q1 reads Q2 reads read ratio Q1 heap fetches Q2 heap fetches
50 tag_ids 5,587 ms 385 ms 15x 50,862 4,134 12x 26,978 551
250 tag_ids 23,016 ms 758 ms 30x 210,517 7,343 29x 132,278 2,717
1,000 tag_ids 63,928 ms 2,183 ms 29x 588,174 18,820 31x 526,785 10,826

Hot cache (pg_prewarm indexes + heap, 250 tag_ids)

query time reads heap fetches
Q1: EXISTS(NOT deleted) 896 ms 132,189 122,510
Q2: NOT EXISTS(deleted) 123 ms 0 2,563
ratio 7.3x ∞ 48x

Q2 reads = 0 because all index pages fit in shared_buffers after prewarm. Q1 still reads 132k pages — those are heap fetches into the 13 GiB table, which doesn't fully fit in shared_buffers.

Raw EXPLAIN (ANALYZE, BUFFERS) output

Q1 EXISTS(NOT deleted) — 50 tag_ids — COLD 

Nested Loop
  Buffers: shared hit=101292 read=50862 dirtied=29170
  Index Only Scan using posts_not_deleted_id_key
    Heap Fetches: 26978
    Buffers: shared hit=101272 read=50093 dirtied=26711
Execution Time: 5586.628 ms

Q2 NOT EXISTS(deleted) — 50 tag_ids — COLD 

Nested Loop Anti Join
  Buffers: shared hit=72716 read=4134 dirtied=574
  Index Only Scan using posts_deleted_id_key
    Heap Fetches: 551
    Buffers: shared hit=72696 read=3365 dirtied=544
Execution Time: 384.821 ms

Q1 EXISTS(NOT deleted) — 250 tag_ids — COLD 

Nested Loop
  Buffers: shared hit=542935 read=210517 dirtied=111920
  Index Only Scan using posts_not_deleted_id_key
    Heap Fetches: 132278
    Buffers: shared hit=542915 read=208704 dirtied=102498
Execution Time: 23016.329 ms

Q2 NOT EXISTS(deleted) — 250 tag_ids — COLD 

Nested Loop Anti Join
  Buffers: shared hit=374644 read=7343 dirtied=2176
  Index Only Scan using posts_deleted_id_key
    Heap Fetches: 2717
    Buffers: shared hit=374624 read=5530 dirtied=2025
Execution Time: 757.716 ms

Q1 EXISTS(NOT deleted) — 1,000 tag_ids — COLD 

Nested Loop
  Buffers: shared hit=2418745 read=588174 dirtied=369863
  Index Only Scan using posts_not_deleted_id_key
    Heap Fetches: 526785
    Buffers: shared hit=2418725 read=582908 dirtied=335044
Execution Time: 63928.086 ms

Q2 NOT EXISTS(deleted) — 1,000 tag_ids — COLD 

Nested Loop Anti Join
  Buffers: shared hit=1507060 read=18820 dirtied=6579
  Index Only Scan using posts_deleted_id_key
    Heap Fetches: 10826
    Buffers: shared hit=1507040 read=13554 dirtied=6103
Execution Time: 2211.279 ms (2183.073 ms wall)

Q1 EXISTS(NOT deleted) — 250 tag_ids — HOT (pg_prewarm all) 

Nested Loop
  Buffers: shared hit=601895 read=132189
  Index Only Scan using posts_not_deleted_id_key
    Heap Fetches: 122510
    Buffers: shared hit=601875 read=130376
Execution Time: 895.874 ms

Q2 NOT EXISTS(deleted) — 250 tag_ids — HOT (pg_prewarm all) 

Nested Loop Anti Join
  Buffers: shared hit=381690 read=0
  Index Only Scan using posts_deleted_id_key
    Heap Fetches: 2563
    Buffers: shared hit=379857 read=0
Execution Time: 122.661 ms

Authors

Maxim Boguk (original production discovery on 400 GiB table, ~50x speedup), Nikolay Samokhvalov

Edited by Nikolay Samokhvalov