Re: Init connection time grows quadratically

On Wed, Sep 9, 2026 at 6:05 AM Matthias van de Meent
<boekewurm+postgres(at)gmail(dot)com> wrote:
>
> On Tue, 25 Aug 2026 at 08:45, Maksim.Melnikov <m(dot)melnikov(at)postgrespro(dot)ru> wrote:
> > On 8/12/26 23:19, Matthias van de Meent wrote:
> > > Attached are some copy-edits of comments on top of your v3, and a
> > > missed replacement of "GetNumberFromPGProc(MyProc)" with
> > > "MyProcNumber".
> > >
> > > This is an incremental patch on your v3, and doesn't fix the CFBot failures.
> >
> > Thanks. I've attached overall patch with your edits for commitfest too.
>
> Thanks!
>
> I think this is ready for a committer to take a look at, so I'll
> update the CF entry accordingly.
>
>
> Kind regards,
>
> Matthias van de Meent
> Databricks (https://www.databricks.com)
>
> PS. I attached v5 again, so that CFbot will pick up the patch, without
> the incremental patch that contains changes that conflict with those
> in the main patch of v5.
> In the future, it's useful to mark patches that you want the CFBot to
> ignore with 'nocfbot' in their file name, so that the bot can test the
> patches that you want it to include in automated testing.

Hi,

I dug a bit further into the startup scaling on Linux. I instrumented the
startup path with help from Codex, and the main O(N) cost I found in the
retained-connection case is:

heap_page_prune_opt()
-> GlobalVisTestIsRemovableXid()
-> GlobalVisUpdate()
-> ComputeXidHorizons()

ComputeXidHorizons() scans the live ProcArray. In my tests the horizon scan
cost about 18.75 ns per live backend.

The visibility check currently runs before the page-full/free-space check,
even when the latter would reject pruning anyway. For the pg_database page
seen during startup, there were about 7620 bytes free with an 819-byte
threshold. Master refreshed the horizon and then decided not to prune; the
pruning worker was never called.

I first tried avoiding the refresh and relying only on cached visibility state.
That removed most of the startup slope, but it also suppressed useful pruning:
HOT rates dropped and some update tests grew the heap by 33-142%. I dropped
that approach.

v6 only changes the order of the existing checks: do the page-local usefulness
check first, and only then do the refresh-capable visibility test.
allow_update = true, the cleanup lock, the locked recheck, and the pruning
worker are unchanged.

Five fresh-postmaster runs gave:

connections master v6
500 0.477s 0.467s
1000 0.958 0.933
2000 1.941 1.883
4000 3.960 3.776
8000 8.344 7.674
16000 18.061 15.509

Fitting the per-connection startup times gives about 21.70 ns/live backend on
master and 2.70 ns/live with v6. The independently measured horizon slope was
18.75 ns/live, close to the 19.00 ns/live reduction with v6.

Across 16000 retained connections, that horizon slope corresponds to about 2.4
seconds of cumulative work, close to the observed 2.55-second reduction in
total startup time.

I couldn’t reproduce the HOT/bloat problem from the cached-only experiment.
Fixed-update and 40000-update/20-VACUUM tests had the same heap sizes and HOT
rates as master, and catalog churn produced the same pruning-worker counts and
relation sizes.

There is a small concurrency difference: the unlocked page-local heuristic is
now evaluated earlier, so a concurrent page change can make v6 miss an
opportunistic prune that master might later have attempted. GlobalVisUpdate
itself does not affect the free-space predicate; the difference is only the
earlier observation relative to concurrent page changes. Pages that pass the
early check still follow the original visibility/cleanup-lock/recheck path.

v5 and this patch appear to address orthogonal costs. This patch removes the
retained-startup horizon scan, while v5 improves ProcArray renumbering locality
under backend churn. I haven’t benchmarked the combination.

For example, at 16000 retained connections in the churn workload, v5 reached
about 484 replacements/sec versus 373 with v6 and 355 on master.

One result remains unexplained: at 8000 connections, v6 reduced replacement
throughput by 4.9% versus master in all five paired runs, although it improved
again at 16000. I checked pruning-worker counts and the HOT/bloat workloads and
found no corresponding loss of useful pruning. I haven’t yet profiled that case
for CPU or lock-wait differences.

The assertion build passes make check and check-world with
xid_wraparound enabled.

Comments welcome, particularly on moving the unlocked usefulness check earlier.

Best,
Haibo