#!/usr/bin/env perl
#
# t/010_vacuum_delete_heavy.pl -- VACUUM must MAKE PROGRESS on a delete-heavy index.
#
# Regression test for the 1.6.1 P0: VACUUM never completed on an index with many
# tombstones.  On 2.19M docs, deleting 312k rows and running VACUUM burned 4h39m of
# CPU without finishing, 99.75% of samples in __sm_get_chunk_offset.  Two sites tested
# every posting against the tombstone bitmap in a way that defeated sparsemap's
# acceleration: the merge walks TERMS in sorted order, so the docid sequence resets at
# every term boundary and each lookup restarted a chunk-chain walk from the head.
# Cost was O(terms x chunks).
#
# WHY THE EXISTING SUITE MISSED IT, and what this test does differently:
#
#   * t/008_vacuum_reclaim.pl has the scale (120k docs) and the vocabulary, but never
#     DELETES -- it only builds and vacuums, so no tombstones ever exist.
#   * The other delete-touching tests (001/002/003/005/006) delete only a handful of
#     rows, far too few tombstones to make the quadratic term visible.
#
# So the bug needed all three at once: MANY DISTINCT TERMS (to get term-boundary
# resets), MANY TOMBSTONES (to make the chunk chain long), and a VACUUM that reaches
# the merge/compaction path.  This test supplies all three, sized so it completes in
# seconds when correct while the broken code does not finish within the timeout.
#
# The assertion is deliberately a WALL-CLOCK BOUND, not a correctness check: the broken
# code returned correct answers, it simply never returned.  A test that only compared
# counts would have passed on the bug.
#
# HONEST LIMITATION -- verified, do not assume otherwise.  This test does NOT reproduce
# the original P0.  It was run against the reverted (broken) merge lookup and PASSED:
# 60k docs / ~20k tombstones is not enough to make the O(terms x chunks) term dominate,
# because sparsemap only allocates chunks where bits exist, so the chain stays short.
# The production repro needed 2.19M docs / 312k tombstones spread over a ~63M docid
# space -- a chain roughly an order of magnitude longer -- and that is not affordable in
# CI (the build alone took ~500 s).
#
# So what is this test for?  Three things it genuinely does:
#   1. It is the ONLY test that exercises delete -> tombstone -> VACUUM -> merge/compact
#      at all.  t/008 has the scale and vocabulary but never deletes; the other
#      delete-touching tests delete a handful of rows.  That combination being untested
#      is precisely how the P0 shipped.
#   2. It catches any regression that makes this path fail, error, or return WRONG
#      counts after vacuuming -- the failure mode a future "make it fast" change is
#      most likely to introduce.
#   3. The timeout catches a catastrophic slowdown (orders of magnitude), just not the
#      specific ~1,000x one that needed production scale.
# Detecting that class properly needs a scale run outside CI; see
# bench/P0_VACUUM_HANG_2026-09-10.md for the reproduction that does work.

use strict;
use warnings;
use PostgreSQL::Test::Cluster;
use PostgreSQL::Test::Utils;
use Test::More;

my $node = PostgreSQL::Test::Cluster->new('vac_delheavy');
$node->init;
# Keep autovacuum out of the way so the timed VACUUM below is the only one running,
# and give the merge a realistic budget.
$node->append_conf('postgresql.conf', q{
autovacuum = off
maintenance_work_mem = 64MB
});
$node->start;
$node->safe_psql('postgres', 'CREATE EXTENSION pg_fts');

# 60k docs x ~30 words, each doc carrying a unique term (uid$g) so the vocabulary is
# ~60k+ distinct terms.  High term count is the load-bearing property here: the bug's
# cost scaled with the number of TERM BOUNDARIES, not with document count.
note("building corpus");
$node->safe_psql('postgres', q{
    CREATE TABLE docs (id bigserial PRIMARY KEY, body text);
    INSERT INTO docs(body)
      SELECT (SELECT string_agg('w'||((g*13+s)%3000), ' ') FROM generate_series(1,30) s)
             || ' uid'||g
      FROM generate_series(1, 60000) g;
    CREATE INDEX docs_fts ON docs USING fts (to_ftsdoc('simple', body));
});

my $nterms = $node->safe_psql('postgres',
    q{SELECT (fts_index_stats('docs_fts')).nterms});
note("distinct terms in index: $nterms");
cmp_ok($nterms, '>', 20000,
    'corpus has a high enough term count to exercise the per-term path');

# Delete a large fraction so the tombstone bitmap is dense and its chunk chain long.
my $deleted = $node->safe_psql('postgres',
    q{WITH d AS (DELETE FROM docs WHERE id % 3 = 0 RETURNING 1) SELECT count(*) FROM d});
note("deleted rows: $deleted");
cmp_ok($deleted, '>', 15000, 'deleted enough rows to build a dense tombstone map');

# THE TEST: VACUUM must finish.  On the broken code this never returns; the timeout is
# what fails.  Generous enough not to be flaky on a slow CI box, tight enough that a
# reintroduced O(terms x chunks) walk cannot slip under it.
my $timeout = 300;
my $t0 = time();
my ($rc, $stdout, $stderr) = $node->psql('postgres', 'VACUUM docs',
                                         timeout => $timeout);
my $elapsed = time() - $t0;
note("VACUUM rc=$rc elapsed=${elapsed}s");

is($rc, 0, "VACUUM completes on a delete-heavy index (rc=0)")
    or diag("stderr: $stderr");
cmp_ok($elapsed, '<', $timeout,
    "VACUUM finished within ${timeout}s (the P0 was non-termination, so this bound IS the test)");

# And the results must still be right -- the broken code was correct-but-hanging, so
# this guards the opposite failure mode: a fix that returns fast by dropping data.
my $idx = $node->safe_psql('postgres',
    q{SELECT count(*) FROM docs WHERE to_ftsdoc('simple', body) @@@ to_ftsquery('simple','w13')});
my $seq = $node->safe_psql('postgres',
    q{SET enable_indexscan=off; SET enable_bitmapscan=off;
      SELECT count(*) FROM docs WHERE to_ftsdoc('simple', body) @@@ to_ftsquery('simple','w13')});
is($idx, $seq, "index count matches sequential-scan ground truth after vacuum ($idx)");

# A second round: tombstones accumulate on an already-merged index, which is the shape
# a long-lived production index actually reaches.
$node->safe_psql('postgres', q{DELETE FROM docs WHERE id % 5 = 0});
$t0 = time();
($rc, $stdout, $stderr) = $node->psql('postgres', 'VACUUM docs', timeout => $timeout);
$elapsed = time() - $t0;
note("second VACUUM rc=$rc elapsed=${elapsed}s");
is($rc, 0, 'a second delete+VACUUM round also completes')
    or diag("stderr: $stderr");

my $idx2 = $node->safe_psql('postgres',
    q{SELECT count(*) FROM docs WHERE to_ftsdoc('simple', body) @@@ to_ftsquery('simple','w13')});
my $seq2 = $node->safe_psql('postgres',
    q{SET enable_indexscan=off; SET enable_bitmapscan=off;
      SELECT count(*) FROM docs WHERE to_ftsdoc('simple', body) @@@ to_ftsquery('simple','w13')});
is($idx2, $seq2, "counts still exact after the second round ($idx2)");


# --- Regression for the P1 fix (2026-09-12): a merge must never leave the index
# --- bigger than it found it, so repeated plain VACUUMs cannot grow it without bound.
#
# Before the fix, three consecutive VACUUMs on an insert-heavy index went
# 7,021 -> 7,734 -> 8,423 -> 9,111 MB, reclaiming nothing: cleanup's merge wrote a
# fresh extend-only copy and the reclaim half was cancelled ("canceling autovacuum
# task"), so every pass added ~690 MB.  This asserts the invariant directly: repeated
# VACUUMs on an unchanged table must not keep growing the index.
note("P1: repeated VACUUM must not grow the index");
$node->safe_psql('postgres', q{
    INSERT INTO docs(id, body)
      SELECT 5000000+g, (SELECT string_agg('w'||((g*13+s)%3000), ' ') FROM generate_series(1,30) s) || ' uid'||(5000000+g)
      FROM generate_series(1, 15000) g;
});
sub idxmb {
    return $node->safe_psql('postgres',
        q{SELECT (pg_relation_size('docs_fts')/1024/1024)::bigint});
}
# INDEX_CLEANUP=on forces amvacuumcleanup to run.  With the default (AUTO) and no dead
# tuples, PostgreSQL may SKIP index cleanup entirely -- in which case pg_fts's own
# reclaim code never executes and this would test nothing.
$node->safe_psql('postgres', 'VACUUM (INDEX_CLEANUP on) docs');
my $m1 = idxmb();
$node->safe_psql('postgres', 'VACUUM (INDEX_CLEANUP on) docs');
my $m2 = idxmb();
$node->safe_psql('postgres', 'VACUUM (INDEX_CLEANUP on) docs');
my $m3 = idxmb();
diag("index MB after three VACUUMs: $m1, $m2, $m3");

# The deferral must not become a permanent skip: an index that has real reclaimable
# bloat must still SHRINK.  Delete most of the corpus, then let repeated cleanup work.
# This is the other half of the requirement -- bounded AND still able to reclaim.
$node->safe_psql('postgres', q{DELETE FROM docs WHERE id >= 5000000 AND id % 4 <> 0});
my $mb_del = idxmb();
for (1 .. 4) { $node->safe_psql('postgres', 'VACUUM (INDEX_CLEANUP on) docs'); }
my $mb_rec = idxmb();
diag("after delete=${mb_del}MB, after 4 cleanups=${mb_rec}MB");
# Does it CONVERGE, or keep climbing?  Run four more cleanups and compare.  Also burn a
# few transactions in between: pages freed by an earlier cleanup only become recyclable
# once the global visibility horizon advances past the freeing xid, which back-to-back
# VACUUMs in a quiet test cluster may not do but a live system does continuously.
for (1 .. 6) { $node->safe_psql('postgres', 'SELECT txid_current()'); }
for (1 .. 4) { $node->safe_psql('postgres', 'VACUUM (INDEX_CLEANUP on) docs'); }
my $mb_rec2 = idxmb();
diag("after delete=${mb_del}MB, +4 cleanups=${mb_rec}MB, +6 txns +4 more=${mb_rec2}MB");
cmp_ok($mb_rec2, '<=', $mb_rec,
    "cleanup converges after deletes (${mb_rec}MB -> ${mb_rec2}MB, no further growth)");
# NO GROWTH.  This is the requirement: an index must stay bounded under repeated
# cleanup, online, with no operator scheduling and no downtime.
#
# What used to happen here, measured: 35 -> 52 -> 69 MB, ~17 MB per pass, unbounded.
# bm25_vacuum_compact can only shrink by REUSING free pages, and
# bm25_page_recyclable() gates each candidate on GlobalVisCheckRemovableXid() -- so
# pages freed by the merge that cleanup itself just ran are all still visible to our
# own transaction, every candidate is rejected, the allocator extends instead, and the
# pass copies the live data to fresh blocks while reclaiming nothing:
#   nblocks=2366 freeblks=1500 gate=1 -> 4553 -> 6740 -> 8927  (+2187 = ~3x live, each pass)
# while a pass whose free pages came from an OLDER transaction shrank 1908 -> 615 fine.
#
# The fix asks the second question (bm25_have_recyclable_room) and defers the pass when
# the space is not reusable yet; the next cycle, in a new transaction, reclaims properly.
#
# 2 MB of tolerance covers page-level rounding, not a per-pass extension.
cmp_ok($m2, '<=', $m1 + 2,
    "a second cleanup does not grow the index (${m1}MB -> ${m2}MB)");
cmp_ok($m3, '<=', $m1 + 2,
    "a third cleanup does not grow the index (${m1}MB -> ${m3}MB)");

# And results stay exact through all of it.
my $i3 = $node->safe_psql('postgres',
    q{SELECT count(*) FROM docs WHERE to_ftsdoc('simple', body) @@@ to_ftsquery('simple','w13')});
my $s3 = $node->safe_psql('postgres',
    q{SET enable_indexscan=off; SET enable_bitmapscan=off;
      SELECT count(*) FROM docs WHERE to_ftsdoc('simple', body) @@@ to_ftsquery('simple','w13')});
is($i3, $s3, "counts exact after repeated VACUUMs ($i3)");

$node->stop;
done_testing();