Re: Optimize SnapBuildPurgeOlderTxn: use in-place compaction instead of temporary array

Hi,

On Wed, Oct 29, 2025 at 8:17 PM Xuneng Zhou <xunengzhou(at)gmail(dot)com> wrote:
>
> Hi,
>
> On Sat, Oct 25, 2025 at 2:36 AM Masahiko Sawada <sawada(dot)mshk(at)gmail(dot)com> wrote:
> >
> > On Thu, Oct 23, 2025 at 1:17 AM Xuneng Zhou <xunengzhou(at)gmail(dot)com> wrote:
> > >
> > > Hi Sawada-san, Michael,
> > >
> > > Thanks for your comments on this patch.
> > >
> > > On Thu, Oct 23, 2025 at 8:28 AM Masahiko Sawada <sawada(dot)mshk(at)gmail(dot)com> wrote:
> > > >
> > > > On Mon, Oct 20, 2025 at 11:13 PM Xuneng Zhou <xunengzhou(at)gmail(dot)com> wrote:
> > > > >
> > > > > Hi,
> > > > >
> > > > > Thanks for looking into this.
> > > > >
> > > > > On Tue, Oct 21, 2025 at 1:05 PM Kirill Reshke <reshkekirill(at)gmail(dot)com> wrote:
> > > > > >
> > > > > > On Tue, 21 Oct 2025 at 04:31, Michael Paquier <michael(at)paquier(dot)xyz> wrote:
> > > > > > >
> > > > > > > On Sat, Oct 18, 2025 at 01:59:40PM +0500, Kirill Reshke wrote:
> > > > > > > > Indeed, these changes look correct.
> > > > > > > > I wonder why b89e151054a0 did this place this way, hope we do not miss
> > > > > > > > anything here.
> > > > > > >
> > > > > > > Perhaps a lack of time back in 2014? It feels like an item where we
> > > > > > > would need to research a bit some of the past threads, and see if this
> > > > > > > has been discussed, or if there were other potential alternatives
> > > > > > > discussed. This is not saying that what you are doing in this
> > > > > > > proposal is actually bad, but it's a bit hard to say what an
> > > > > > > "algorithm" should look like in this specific code path with XID
> > > > > > > manipulations. Perhaps since 2014, we may have other places in the
> > > > > > > tree that share similar characteristics as what's done here.
> > > > > > >
> > > > > > > So it feels like this needs a bit more historical investigation first,
> > > > > > > rather than saying that your proposal is the best choice on the table.
> > >
> > > Following these suggestions, I carefully searched the mailing list
> > > archives and found no reports of performance issues directly related
> > > to this code path. I also examined other parts of the codebase for
> > > similar patterns. Components like integerset might share some
> > > characteristics with SnapBuildPurgeOlderTxn, but they have constraints
> > > that make them not directly applicable here. I am not very familiar
> > > with the whole tree, so the investigation might not be exhaustive.
> >
> > Thank you for looking through the archives. In logical replication,
> > performance problems typically show up as replication delays. Since
> > logical replication involves many different components and processes,
> > it's quite rare for investigations to trace problems back to this
> > specific piece of code. However, I still believe it's important to
> > optimize the performance of logical decoding itself.
> >
> > >
> > > > >
> > > > > A comparable optimization exists in KnownAssignedXidsCompress() which
> > > > > uses the same algorithm to remove stale XIDs without workspace
> > > > > allocation. That implementation also adds a lazy compaction heuristic
> > > > > that delays compaction until a threshold of removed entries is
> > > > > reached, amortizing the O(N) cost across multiple operations.
> > > > >
> > > > > The comment above the data structure mentions the trade-off of keeping
> > > > > the committed.xip array sorted versus unsorted. If the array were
> > > > > sorted, we could use a binary search combined with memmove to compact
> > > > > it efficiently, achieving O(log n + n) complexity for purging.
> > > > > However, that design would increase the complexity of
> > > > > SnapBuildAddCommittedTxn from O(1) to O(n) and "more complicated wrt
> > > > > wraparound".
> > > > >
> > > > > /*
> > > > > * Array of committed transactions that have modified the catalog.
> > > > > *
> > > > > * As this array is frequently modified we do *not* keep it in
> > > > > * xidComparator order. Instead we sort the array when building &
> > > > > * distributing a snapshot.
> > > > > *
> > > > > * TODO: It's unclear whether that reasoning has much merit. Every
> > > > > * time we add something here after becoming consistent will also
> > > > > * require distributing a snapshot. Storing them sorted would
> > > > > * potentially also make it easier to purge (but more complicated wrt
> > > > > * wraparound?). Should be improved if sorting while building the
> > > > > * snapshot shows up in profiles.
> > > > > */
> > > > > TransactionId *xip;
> > > > > } committed;
> > > > >
> > > > > /*
> > > > > * Keep track of a new catalog changing transaction that has committed.
> > > > > */
> > > > > static void
> > > > > SnapBuildAddCommittedTxn(SnapBuild *builder, TransactionId xid)
> > > > > {
> > > > > Assert(TransactionIdIsValid(xid));
> > > > >
> > > > > if (builder->committed.xcnt == builder->committed.xcnt_space)
> > > > > {
> > > > > builder->committed.xcnt_space = builder->committed.xcnt_space * 2 + 1;
> > > > >
> > > > > elog(DEBUG1, "increasing space for committed transactions to %u",
> > > > > (uint32) builder->committed.xcnt_space);
> > > > >
> > > > > builder->committed.xip = repalloc(builder->committed.xip,
> > > > > builder->committed.xcnt_space * sizeof(TransactionId));
> > > > > }
> > > > >
> > > > > /*
> > > > > * TODO: It might make sense to keep the array sorted here instead of
> > > > > * doing it every time we build a new snapshot. On the other hand this
> > > > > * gets called repeatedly when a transaction with subtransactions commits.
> > > > > */
> > > > > builder->committed.xip[builder->committed.xcnt++] = xid;
> > > > > }
> > > > >
> > > > > It might be worth profiling this function to evaluate whether
> > > > > maintaining a sorted array could bring potential benefits, although
> > > > > accurately measuring its end-to-end impact could be difficult if it
> > > > > isn’t a known hotspot. I also did a brief search on the mailing list
> > > > > and found no reports of performance concerns or related proposals to
> > > > > optimize this part of the code.
> > > >
> > > > It might also be worth researching what kind of workloads would need a
> > > > better algorithm in terms of storing/updating xip and subxip arrays
> > > > since it would be the primary motivation. Also, otherwise we cannot
> > > > measure the real-world impact of a new algorithm. Having said that,
> > > > find that it would be discussed and developed separately from the
> > > > proposed patch on this thread.
> > >
> > > +1 for researching the workloads that might need a sorted array and
> > > more efficient algorithm. This exploration isn’t limited to the scope
> > > of SnapBuildPurgeOlderTxn but relates more broadly to the overall
> > > snapbuild process, which might be worth discussing in a separate
> > > thread as suggested.
> > >
> > > * TODO: It's unclear whether that reasoning has much merit. Every
> > > * time we add something here after becoming consistent will also
> > > * require distributing a snapshot. Storing them sorted would
> > > * potentially also make it easier to purge (but more complicated wrt
> > > * wraparound?). Should be improved if sorting while building the
> > > * snapshot shows up in profiles.
> > >
> > > I also constructed an artificial workload to try to surface the qsort
> > > call in SnapBuildBuildSnapshot, though such a scenario seems very
> > > unlikely to occur in production.
> > >
> > > for ((c=1; c<=DDL_CLIENTS; c++)); do
> > > (
> > > local seq=1
> > > while (( $(date +%s) < tB_end )); do
> > > local tbl="hp_ddl_${c}_$seq"
> > > "$psql" -h 127.0.0.1 -p "$PORT" -d postgres -c "
> > > BEGIN;
> > > CREATE TABLE ${tbl} (id int, data text);
> > > CREATE INDEX idx_${tbl} ON ${tbl} (id);
> > > INSERT INTO ${tbl} VALUES ($seq, 'd');
> > > DROP TABLE ${tbl};
> > > COMMIT;" >/dev/null 2>&1 || true
> > > seq=$((seq+1))
> > > done
> > > )
> >
> > Interesting. To be honest, I think this scenario might actually occur
> > in practice, especially in cases where users frequently use CREATE
> > TEMP TABLE ... ON COMMIT DROP.
>
> The attached file shows the flamegraph for this workload.
>
> for ((c=1; c<=CLIENTS_DDL; c++)); do
> (
> local seq=1
> while (( $(date +%s) < tB_end )); do
> local tbl="hp_temp_${c}_$seq"
> $psql_cmd -d postgres -c "
> BEGIN;
> CREATE TEMP TABLE ${tbl} (id int, data text) ON COMMIT DROP;
> CREATE INDEX idx_${tbl} ON ${tbl} (id);
> INSERT INTO ${tbl} VALUES ($seq, 'd');
> COMMIT;" >/dev/null 2>&1 || true
> seq=$((seq+1))
> done
> ) &
> pidsB+=($!)
> done
>
> I’ve been thinking about possible ways to maintain a sorted array to
> optimize this case and purge function. Below are some preliminary
> ideas. If any of them seem reasonable, I’d like to start a new thread
> and prepare a patch based on this direction.
>
> 1) Batch insertion with globally sorted array (raw uint32 order)
>
> Goal: Maintain committed.xip sorted and deduplicated to eliminate
> repeated qsorts.
>
> Mechanism:
> In SnapBuildCommitTxn, collect all XIDs/subxids to be tracked into a
> local vector (length m)
> Sort and deduplicate the batch: O(m log m)
> Reverse-merge the batch into the global array: O(N + m), deduplicating
> on the fly
> Invariant: committed.xip[0..xcnt) is always raw-sorted (xidComparator
> order) and deduplicated
>
> Complexity improvement:
> Before: O((N+m) log (N+m)) per build
> After: O(m log m + N) per commit; snapshot build can skip qsort entirely
>
> Purge:
> Remains O(N) linear scan. Raw sorting doesn't enable binary search
> because the purge predicate uses wraparound-aware semantics
> (NormalTransactionIdPrecedes), and committed.xip can span epochs, so
> numeric order ≠ logical XID order.
>
> 2) Adopt FullTransactionId for sublinear purge (theoretically possible)
>
> Rationale:
> To make purge O(log N), the array needs to be sorted under the same
> ordering relation as the purge predicate. Wraparound-aware comparison
> of 32-bit XIDs is not a total order when the set spans epochs.
> FullTransactionId (epoch<<32 | xid) could provide a true total order.
>
> Mechanism:
> Store FullTransactionId *fxip instead of TransactionId *xip
> struct
> {
> size_t xcnt;
> size_t xcnt_space;
> bool includes_all_transactions;
> FullTransactionId *fxip; /* Changed from TransactionId *xip */
> } committed;
>
> Insertion: Map each 32-bit XID to FullTransactionId using a snapshot
> of nextFullXid (same logic as hot standby feedback); sort/dedup batch;
> reverse-merge O(N + m)
>
> Purge: Compute xmin_full using the same snapshot; binary search for
> lower bound O(log N) + memmove suffix
>
> /*
> * xidLogicalComparator
> * qsort comparison function for XIDs
> *
> * This is used to compare only XIDs from the same epoch (e.g. for backends
> * running at the same time). So there must be only normal XIDs, so there's
> * no issue with triangle inequality.
> */
> int
> xidLogicalComparator(const void *arg1, const void *arg2)
>
> Trade-offs:
> Downcasting a logically sorted FullTransactionId array can break raw
> uint32 ordering if the set spans an epoch boundary. Still need a qsort
> on snapshot->xip after copying xids from committed.xip at worst case.
>
> Memory/I/O: 2× bytes for committed array (4→8 bytes per entry)
>
> Purge improves from O(N) to O(log N + move); merge complexity unchanged

I’ve implemented an experimental version that maintains the
committed.xip array in numeric sorted order and profiled it on the
previous workload. The overhead observed earlier has now been
eliminated.
Before starting a discussion thread and proposing the patch, I plan to
run additional pgbench workloads to verify that there are no
performance regressions. Once the results look stable, I’ll polish and
share the patch for review.

Best,
Xuneng