Re: Lazy snapshot distribution in logical decoding

Hi Rui,

I like this patch -- it applies cleanly on the current master, the test
suites pass here, and your benchmark numbers reproduce on my machine.
But I found one reproducible correctness bug.

The problem: with eager distribution a snapshot is queued at the
catalog commit's LSN, always earlier than the changes that need it.
With lazy distribution the snapshot is queued at the *same* LSN as
the change that triggers it. If that change is in a subtransaction,
the snapshot (toplevel queue) and the change (subxact queue) meet in
the k-way merges with same LSNs, and *binary*
* heap does not guaranteewhich one pops first.*

The commit message argues the eagerly distributed invalidations
preserve the order. But DML on a user_catalog_table makes a commit
catalog-modifying (via XLOG_HEAP2_NEW_CID) while emitting zero
invalidation messages, so SnapBuildDistributeInval() queues nothing
and that protection is gone.

Reproducer (tables created before the slot, autovacuum off):

CREATE TABLE t1(a int);
CREATE TABLE t2(b int);
CREATE TABLE cat_t(z int) WITH (user_catalog_table = true);

S1: BEGIN;
S1: SAVEPOINT a;
S1: INSERT INTO t1 VALUES (1);
S2: INSERT INTO cat_t VALUES (42); -- commits
S1: SAVEPOINT b;
S1: INSERT INTO t2 VALUES (1);
S1: COMMIT;

With a one-line elog printing each entry popped in the
ReorderBufferProcessTXN() loop (0=INSERT, 5=INTERNAL_SNAPSHOT), the
patched build replays S1's transaction as:

POP xid=698 lsn=0/017CCD38 action=0 <- INSERT t2
POP xid=695 lsn=0/017CCD38 action=5 <- snapshot, too late

Master, same schedule:

POP xid=695 lsn=0/017CCD48 action=5 <- snapshot first
POP xid=698 lsn=0/017CCD78 action=0 <- INSERT t2

So t2's INSERT is decoded under the previous catalog snapshot. The
test_decoding output is unchanged, which makes this easy to miss --
but a plugin that reads user catalog tables in its change callback
sees stale contents, the exact guarantee user_catalog_table exists
to provide, and under streaming the change has already been sent
downstream.

Two possible fixes:

a) In ReorderBufferIterCompare(), on equal LSN order
INTERNAL_SNAPSHOT first.

b) Queue the lazy snapshot into the triggering transaction's own
queue and track last_snapshot_generation there, so the tie
cannot happen across queues at all.

(a) is less invasive. Happy to share the repro script, or to turn
this schedule into an isolation test.

A few smaller comments:

- SnapBuildCommitTxn() still builds a snapshot on every catalog-
modifying commit, copying the ever-growing committed.xip array,
so a CPU-side N^2 term remains (20000 catalog commits:
1170 ms decode / 854 MB slot bytes here; 40000: 3812 ms /
3309 MB). Fine to leave for a follow-up patch, but the commit
message shouldn't read as if the O(N^2) is entirely gone.

- A transaction's first change sets the base snapshot and then
immediately queues the same snapshot again, because
last_snapshot_generation (0) is behind. Setting
txn->last_snapshot_generation = builder->snapshot_generation in
the base-snapshot branch removes the redundant copy.

- snapshot_generation is serialized (SnapBuildSerialize() copies
the whole struct, hence SNAPBUILD_VERSION 6 -> 7) but
SnapBuildRestore() never reads it back. Restarting from 0 is
semantically fine, which suggests the counter is ephemeral and
could live in ReorderBuffer instead -- no on-disk format change
and no version bump at all.

- 002_lazy_snapshot_spill.pl passes on unpatched master too: with
200 DDLs master stays under 1MB and also reports spill_bytes =
0. Around 1500 DDLs, or logical_decoding_work_mem = 64kB, makes
the test actually discriminate.

- Nits: the "single ReorderBufferTXNByXid() lookup" claim in the
commit message oversells it, since ReorderBufferSetBaseSnapshot()
re-resolves the txn internally; the lazy branch could use a
DEBUG2 message like the eager path had; last_snapshot_generation
is inserted before output_plugin_private, shifting
plugin-visible offsets (appending at the end is kinder to
out-of-tree plugins); and "Don't need to distribute a snapshot
in that case" in SnapBuildCommitTxn() reads as leftover
eager-world wording.

None of this changes my view that the approach is right -- the
disk-usage win is exactly as advertised, and with the ordering bug
fixed I think this is in good shape.

Also, there is a related thread 'logical decoding: skip unnecessary
snapshot distribution'([1])
from Boyu Yang solving the cross-database problem of the same issue.

Given these two patches touch the same code, so whichever goes in first,
the other needs a rebase.

[1]
https://www.postgresql.org/message-id/flat/312a1b4c-f341-40dc-b822-08e5b0cc1848.yangboyu.yby%40alibaba-inc.com
Thanks,
Shihao