Hash index inserts serialise on the metapage tuple counter

While looking at hash index behaviour under concurrency I found that
single-row insert throughput stops scaling at a fairly low client count
and then goes backwards, where an equivalent btree keeps scaling. The
cause is the metapage, and I'd like to float a fix before writing a
finished patch.

The problem is that _hash_doinsert() takes an exclusive buffer lock on
the metapage for every insert, solely to run:

metap->hashm_ntuples += 1;
do_expand = metap->hashm_ntuples >
(double) metap->hashm_ffactor * (metap->hashm_maxbucket + 1);

and to register the metapage in the insert's WAL record. Every inserter
into the index therefore serialises on that one buffer. The v10
metapage cache (293e24e5078) removed the metapage read from the lookup
path, but the write on insert was left in place; Mithun Cy noted at the
time that inserts still touch the metapage every time [1], and it
doesn't seem to have been revisited.

I wanted to be sure, so I did some measurements on a c7i.8xlarge (32
vCPU, one NUMA node), data on tmpfs, synchronous_commit off,
shared_buffers 16GB. pgbench, one single-row INSERT of a random int8
per transaction, index pre-loaded with 2M rows, 20s per point, three
runs averaged:

clients 1 16 32 64
btree 44k 514k 547k 597k
hash 44k 364k 299k 273k

Hash peaks around 16 clients and declines from there. Sampling
pg_stat_activity at 32 clients, ~68% of hash inserter samples are in the
buffer-content-lock wait; btree shows none.

Timing LockBuffer(EXCLUSIVE) per buffer with a uprobe, one buffer
accounts for 99.9% of the exclusive- lock wait time, and pg_buffercache
maps it to block 0 of the index, the metapage.

+1 on fixing this.

So here's what I propose to do, don't touch the metapage on most
inserts. Each backend accumulates its own insert count for a given
index and only takes the metapage lock once every N inserts, adding the
batch and testing the split threshold then. hashm_ntuples only drives
split timing, and VACUUM already recomputes it from scratch
(hashbulkdelete -> hashm_ntuples = num_index_tuples), so a slightly
stale counter costs at most a somewhat delayed split, never correctness.

The recomputed count is only used if no split or insert has occurred
since VACUUM started its scan. If there's constant churn on the table,
it can happen that hashm_ntuples is not recomputed for many VACUUM runs.

Beyond that, the batching benefit degrades as concurrency increases: to
maintain the same bound on the aggregate counting error, the batch size
must decrease inversely with the number of inserting backends, forcing
more frequent metapage updates precisely when contention is highest.
Keeping the batch size fixed instead allows more inserts to accumulate
unreported across backends, leaving the metapage count increasingly
stale as concurrency grows.

With a proof-of-concept doing exactly this (batch size 64, attached),
the hash numbers become:

clients 1 16 32 64
hash 44k 533k 557k 604k

with that change hash now scales like btree (btree was 597k at 64).
Regression and isolation tests pass; a streaming standby with 16
concurrent inserters and splits replayed to the same hashm_ntuples and
maxbucket as the primary, and index probes on the standby found every
row.

Nice speedup!

I was chasing something else when I found this, so the attached patch is
a proof of concept, not a finished submission. It makes the point and
the numbers are real, but it cuts corners I'd want the list's opinion on
before building the real thing:

- Where should the pending per-backend count live? The POC uses a
fixed-size backend-local array keyed by relid, and simply loses the
pending count when the backend exits (VACUUM fixes hashm_ntuples
later). A cleaner home might be the relcache entry, flushed on
relcache invalidation and at transaction end, but that has its own
edge cases (invalidation dropping the count, subxact abort).

- How stale may the split trigger be? With per-backend batching the
index can run up to batch_size * nbackends tuples past the fill
factor before anyone splits. That is self-correcting (every
inserter that crosses the threshold tries to split), but it does
mean the index can briefly carry more overflow pages than today.

I don't like the batched counting too much because:

1. It's involved to do properly as you pointed out yourself already.
2. If we don't care about the details such as flushing residual counter
increments, the splitting behavior is workload dependent and by that
non-deterministic. Which makes it hard to reason about when
investigating problems.
3. It has the inverse scaling problem as described above.

- Is there any appetite for removing the global counter from the hot
path entirely instead, and triggering a split from local information
the inserter already has (e.g. having had to add or walk an overflow
page)? That would also make inserts that don't split read-only on
the metapage. It's a bigger change and I haven't prototyped it yet.

If we cannot come up with an alternative signal, the batched counting is
better than dying from lock contention. But I'm hoping we can do
something else.

Maybe using the number of overflow pages vs the number of bucket pages
would work okay enough? Of course, deletes will leave partially filled
pages and splitting overflow pages full of unique values won't cut down
on the number of overflow pages when splitting.

--
David Geier

On 2026-10-26 David Geier wrote:

+1 on fixing this.

Hello David,

Thanks for looking at this so quickly, I really appreciate it.

The recomputed count is only used if no split or insert has occurred
since VACUUM started its scan. If there's constant churn on the table,
it can happen that hashm_ntuples is not recomputed for many VACUUM runs.

Right, stated plainly: hashm_ntuples is already allowed to drift from the true
tuple count between VACUUMs, batching or not. What VACUUM guarantees is a
recompute at the end of a scan that saw no concurrent split/insert, not a bound
on staleness under churn. So the counter is not a reliable tuple count today;
its only consumer is the fill-factor test that decides when to split. My
change makes it drift a bit more, in a direction that only delays splits. It
doesn't introduce a new correctness dependency, because there isn't one to
break.

Beyond that, the batching benefit degrades as concurrency increases: to
maintain the same bound on the aggregate counting error, the batch size
must decrease inversely with the number of inserting backends [...]

This is a fair hit, but I think it rests on wanting a bounded counting error,
and I'm not sure we need one. The count exists to time a split. A split is
not a deadline; it's "the buckets are getting full, add more". If the index
runs batch_size * nbackends tuples past the fill factor before someone splits,
the cost is some extra overflow pages until the next inserter crosses the
threshold and splits so self-correcting, and the fill factor is a soft target
anyway. So I'd rather keep the batch fixed and accept a staleness that grows
with concurrency than shrink the batch and reintroduce the contention at high
client counts, which is the whole thing we're trying to remove.

Where I do agree with you is the determinism point:

2. [...] the splitting behavior is workload dependent and by that
non-deterministic. Which makes it hard to reason about [...]

Yes. Split timing becoming a function of how many backends happened to be
inserting is the part of batched counting I like least, more than the storage
mess. It makes a reproduction depend on client count, which is exactly the
kind of thing that turns a bug report into a week of "works here".

Maybe using the number of overflow pages vs the number of bucket pages
would work okay enough?

I tend to agree with this because it replaces a global counter with information
the inserter already has in hand. An inserter that has to allocate or walk
onto an overflow page for its bucket already knows that bucket is over-full;
that's a local, lock-free signal that this bucket (hence, on average, the
index) wants more buckets. No metapage write on the common path at all.

Your two objections to it are the real ones, though:

deletes will leave partially filled pages

So overflow-page count lags downward after deletes: the index can look
over-full and keep splitting when it isn't. But a hash index already doesn't
reclaim buckets on delete (maxbucket never decreases) so "splits a bit eagerly
after a delete-heavy phase" is closer to today's behaviour than the tuple
counter is. I'd want to measure this first.

splitting overflow pages full of unique values won't cut down on the
number of overflow pages when splitting

This is the one that actually worries me: if a bucket's overflow is caused by
many duplicate keys (all hashing to the same bucket), splitting won't relieve
it (the dups stay together) so an overflow-triggered split loops, splitting
again and again without reducing overflow. The current code has the same
pathology in slower motion (ntuples keeps rising, it keeps splitting), but a
local overflow trigger could make it tighter. A guard would be needed: don't
re-trigger on a bucket that didn't actually shed overflow across its last
split, or cap splits-per-insert.

So I think the plan is:

1. Settle that the counter's only job is approximate split timing (above).
2. Prototype the overflow-vs-bucket signal and measure it on the same
workload, specifically the delete-heavy and high-duplicate cases, which
are where it can misbehave.
3. Keep the batched counter in my back pocket as the fallback if the
overflow signal can't be made to behave, it's not elegant but it does
remove the contention.

I'll build (2) and report numbers, including the two adversarial cases, so
we're comparing measured behaviour rather than intuitions. If the overflow
signal holds up it's the better answer for the reasons you give.

best,

-greg

The recomputed count is only used if no split or insert has occurred
since VACUUM started its scan. If there's constant churn on the table,
it can happen that hashm_ntuples is not recomputed for many VACUUM runs.

Right, stated plainly: hashm_ntuples is already allowed to drift from the true
tuple count between VACUUMs, batching or not. What VACUUM guarantees is a
recompute at the end of a scan that saw no concurrent split/insert, not a bound
on staleness under churn. So the counter is not a reliable tuple count today;
its only consumer is the fill-factor test that decides when to split. My
change makes it drift a bit more, in a direction that only delays splits. It
doesn't introduce a new correctness dependency, because there isn't one to
break.

Agreed, that this cannot cause any incorrectness issues.

Beyond that, the batching benefit degrades as concurrency increases: to
maintain the same bound on the aggregate counting error, the batch size
must decrease inversely with the number of inserting backends [...]

This is a fair hit, but I think it rests on wanting a bounded counting error,
and I'm not sure we need one. The count exists to time a split. A split is
not a deadline; it's "the buckets are getting full, add more". If the index
runs batch_size * nbackends tuples past the fill factor before someone splits,
the cost is some extra overflow pages until the next inserter crosses the
threshold and splits so self-correcting, and the fill factor is a soft target
anyway. So I'd rather keep the batch fixed and accept a staleness that grows
with concurrency than shrink the batch and reintroduce the contention at high
client counts, which is the whole thing we're trying to remove.

I guess the question is if with too few / too many backends you're not
splitting too frequently / too infrequently or you're back to contention
problems.

Where I do agree with you is the determinism point:

2. [...] the splitting behavior is workload dependent and by that
non-deterministic. Which makes it hard to reason about [...]

Yes. Split timing becoming a function of how many backends happened to be
inserting is the part of batched counting I like least, more than the storage
mess. It makes a reproduction depend on client count, which is exactly the
kind of thing that turns a bug report into a week of "works here".

Exactly. Any alternative solution we come up with should be checked
against not having that problem.

Maybe using the number of overflow pages vs the number of bucket pages
would work okay enough?

I tend to agree with this because it replaces a global counter with information
the inserter already has in hand. An inserter that has to allocate or walk
onto an overflow page for its bucket already knows that bucket is over-full;
that's a local, lock-free signal that this bucket (hence, on average, the
index) wants more buckets. No metapage write on the common path at all.

I thought about the total number of overflow pages. So we would need a
counter but one that changes less frequently than the row count.

Your two objections to it are the real ones, though:

deletes will leave partially filled pages

So overflow-page count lags downward after deletes: the index can look
over-full and keep splitting when it isn't. But a hash index already doesn't
reclaim buckets on delete (maxbucket never decreases) so "splits a bit eagerly
after a delete-heavy phase" is closer to today's behaviour than the tuple
counter is. I'd want to measure this first.

splitting overflow pages full of unique values won't cut down on the
number of overflow pages when splitting

This is the one that actually worries me: if a bucket's overflow is caused by
many duplicate keys (all hashing to the same bucket), splitting won't relieve
it (the dups stay together) so an overflow-triggered split loops, splitting
again and again without reducing overflow. The current code has the same
pathology in slower motion (ntuples keeps rising, it keeps splitting), but a
local overflow trigger could make it tighter. A guard would be needed: don't
re-trigger on a bucket that didn't actually shed overflow across its last
split, or cap splits-per-insert.

How about excluding the number of overflow pages that exists because of
duplicates? For non-duplicates, skew cannot realistically occur (thanks
to the uniform hashing). So the duplicate case is the only case to consider.

We could keep a counter for the duplicates-only overflow pages in the
meta page. Such counter would only change very infrequently. On delete,
we would consider duplicates-only overflow pages normal overflow pages
again and decrement the counter.

So I think the plan is:

1. Settle that the counter's only job is approximate split timing (above).

Yes.

2. Prototype the overflow-vs-bucket signal and measure it on the same
workload, specifically the delete-heavy and high-duplicate cases, which
are where it can misbehave.

Which workload are you planning to test with?

3. Keep the batched counter in my back pocket as the fallback if the
overflow signal can't be made to behave, it's not elegant but it does
remove the contention.

Yes.

I'll build (2) and report numbers, including the two adversarial cases, so
we're comparing measured behaviour rather than intuitions. If the overflow
signal holds up it's the better answer for the reasons you give.

Sounds good.

Consider doing something about the duplicates-only pages. It would be
interesting to contrast such a variant against one that simply ignores
the fact that duplicates-only pages cannot be split.

A workload that creates duplicates for every entry will be the
worst-case. Duplicates for a single entry would probably not matter much.

--
David Geier

Hey David,

I built the overflow-signal prototype and measured it, including the two
adversarial cases you flagged. Short version: it recovers the scaling,
and the delete-heavy and high-duplicate cases behave better than either
of us feared, not worse.

Design: an insert that fits without allocating a new overflow page
doesn't touch the metapage at all, it just bumps a per-backend pending
count. Only an insert that adds an overflow page flushes that pending
count into hashm_ntuples and asks for a split. The flush path already
holds the metapage exclusive lock (that's where _hash_addovflpage
allocated the page), so it costs nothing extra there.
_hash_expandtable()'s own threshold re-check stays as the split
decision, which turns out to matter (see the duplicate case below). The
batched delta rides in the insert WAL record so a standby advances
hashm_ntuples in the same steps.

Box: c7i.8xlarge, 32 vCPU, one NUMA node, data on tmpfs, master built -O2.

Scaling (pgbench, single-row INSERT, 2M preload, synchronous_commit off, 20s,
best of 3):

clients 1 16 32 64
master 38810 361819 288961 262614
overflow 40743 487632 558926 588115

Same shape as the batched POC: master peaks at 16 clients and declines,
overflow keeps scaling, 2.24x at 64 and no decline.

deletes will leave partially filled pages

Delete-heavy (insert 2M, delete 90%, insert 2M more):

master: 18692 pages, 13030 buckets, ntuples 4000000
overflow: 16695 pages, 11980 buckets, ntuples 3898197

It doesn't over-split after deletes, it splits *less*, because a split
only fires when a bucket actually overflows, and deletes that free space
mean fewer overflow events. So the direction of the concern is
backwards: the local signal reacts to real fullness, where the global
counter keeps climbing across deletes until VACUUM corrects it.
(ntuples runs ~2.5% low from the unflushed pending counts; harmless, it
only times splits and VACUUM recomputes it.)

splitting overflow pages full of unique values won't cut down on the number
of overflow pages when splitting

This was the one I thought could loop, and it doesn't. High-duplicate
load, 2M rows in 50 distinct keys:

master: 12070 pages, 6515 buckets
overflow: 10044 pages, 4931 buckets

and as a direct split-loop check, 500k inserts of a *single* key:

overflow: maxbucket = 1229

1229 is the normal bucket count for 500k tuples at the fill factor, not
an explosion. If an overflow-triggered split were looping on the
duplicates, maxbucket would run away. It doesn't, because
_hash_expandtable() re-checks hashm_ntuples against the threshold and
declines a split the count doesn't warrant. A bucket that overflows
purely on duplicate keys asks for a split and gets told no. Master
actually over-splits more here, testing the threshold on every insert.

Correctness: mixed unique/duplicate/delete load gives identical row
counts to master (596572), and index probes match seqscan on both unique
and heavy- duplicate values. A streaming standby replays clean and ends
at the same row count as the primary, with index probes matching.

One thing worth separating out: with wal_consistency_checking='hash' the
standby fails with "incorrect resource manager data checksum". That is
*not* this change, unpatched master fails the same way under the same
setting. It's the REGBUF_NO_CHANGE full-page-image bug from the other
thread ("WAL record CRC calculated incorrectly because of underlying
buffer modification") [0]/messages/by-id/ats4pi-RM0Uom0T9@floki. The two are orthogonal; with consistency
checking off, this change replays cleanly.

So I think the overflow signal is the better answer, for the reason you
gave: it replaces a global counter on the hot path with a local signal
the inserter already has, and the threshold re-check in
_hash_expandtable() is a natural guard against the duplicate-key
pathology.

I'll clean the prototype into a real patch, the pending-count storage is
still a fixed backend-local array that loses its count on backend exit,
which is fine for correctness but I want to look at whether a relcache
home is worth it. Prototype diff attached for reference (not submission
quality yet).

best,

-greg

[0]: /messages/by-id/ats4pi-RM0Uom0T9@floki

On Monday, October 26th, 2026 at 11:49 AM, Greg Burd <greg@burd.me> wrote:

Hey David,

I built the overflow-signal prototype and measured it, including the two
adversarial cases you flagged. Short version: it recovers the scaling,
and the delete-heavy and high-duplicate cases behave better than either
of us feared, not worse.

Design: an insert that fits without allocating a new overflow page
doesn't touch the metapage at all, it just bumps a per-backend pending
count. Only an insert that adds an overflow page flushes that pending
count into hashm_ntuples and asks for a split. The flush path already
holds the metapage exclusive lock (that's where _hash_addovflpage
allocated the page), so it costs nothing extra there.
_hash_expandtable()'s own threshold re-check stays as the split
decision, which turns out to matter (see the duplicate case below). The
batched delta rides in the insert WAL record so a standby advances
hashm_ntuples in the same steps.

Box: c7i.8xlarge, 32 vCPU, one NUMA node, data on tmpfs, master built -O2.

Scaling (pgbench, single-row INSERT, 2M preload, synchronous_commit off, 20s,
best of 3):

clients 1 16 32 64
master 38810 361819 288961 262614
overflow 40743 487632 558926 588115

Same shape as the batched POC: master peaks at 16 clients and declines,
overflow keeps scaling, 2.24x at 64 and no decline.

deletes will leave partially filled pages

Delete-heavy (insert 2M, delete 90%, insert 2M more):

master: 18692 pages, 13030 buckets, ntuples 4000000
overflow: 16695 pages, 11980 buckets, ntuples 3898197

It doesn't over-split after deletes, it splits *less*, because a split
only fires when a bucket actually overflows, and deletes that free space
mean fewer overflow events. So the direction of the concern is
backwards: the local signal reacts to real fullness, where the global
counter keeps climbing across deletes until VACUUM corrects it.
(ntuples runs ~2.5% low from the unflushed pending counts; harmless, it
only times splits and VACUUM recomputes it.)

splitting overflow pages full of unique values won't cut down on the number
of overflow pages when splitting

This was the one I thought could loop, and it doesn't. High-duplicate
load, 2M rows in 50 distinct keys:

master: 12070 pages, 6515 buckets
overflow: 10044 pages, 4931 buckets

and as a direct split-loop check, 500k inserts of a *single* key:

overflow: maxbucket = 1229

1229 is the normal bucket count for 500k tuples at the fill factor, not
an explosion. If an overflow-triggered split were looping on the
duplicates, maxbucket would run away. It doesn't, because
_hash_expandtable() re-checks hashm_ntuples against the threshold and
declines a split the count doesn't warrant. A bucket that overflows
purely on duplicate keys asks for a split and gets told no. Master
actually over-splits more here, testing the threshold on every insert.

Correctness: mixed unique/duplicate/delete load gives identical row
counts to master (596572), and index probes match seqscan on both unique
and heavy- duplicate values. A streaming standby replays clean and ends
at the same row count as the primary, with index probes matching.

One thing worth separating out: with wal_consistency_checking='hash' the
standby fails with "incorrect resource manager data checksum". That is
*not* this change, unpatched master fails the same way under the same
setting. It's the REGBUF_NO_CHANGE full-page-image bug from the other
thread ("WAL record CRC calculated incorrectly because of underlying
buffer modification") [0]. The two are orthogonal; with consistency
checking off, this change replays cleanly.

So I think the overflow signal is the better answer, for the reason you
gave: it replaces a global counter on the hot path with a local signal
the inserter already has, and the threshold re-check in
_hash_expandtable() is a natural guard against the duplicate-key
pathology.

I'll clean the prototype into a real patch, the pending-count storage is
still a fixed backend-local array that loses its count on backend exit,
which is fine for correctness but I want to look at whether a relcache
home is worth it. Prototype diff attached for reference (not submission
quality yet).

best,

-greg

[0] /messages/by-id/ats4pi-RM0Uom0T9@floki

I forgot to attach it, lol. :)

-greg

Hi David, all,

v1 attached. It is not the overflow-signal prototype I posted
earlier today, because that prototype had a hole.

The prototype only added to hashm_ntuples when an insert allocated an
overflow page, and kept every other insert's count in a per-backend
slot. Those slots die with the backend. A VACUUM that removes no
tuples never calls hashbulkdelete, so on an insert-only table nothing
puts the lost counts back. pgbench with long-lived connections never
exits, which is why the earlier numbers looked fine. With a new
connection per insert (pgbench -C, 8 clients, 200k rows):

master: ntuples 200000, maxbucket 651, 77 overflow pages
prototype: ntuples 487, maxbucket 7, 487 overflow pages

Once the count is that far off, _hash_expandtable() turns down every
split, and the chains just keep growing. CREATE INDEX had the same
problem, since the build inserts through _hash_doinsert().

v1 keeps today's rule for when to split and only stops waiting for the
lock:

- Try the metapage lock with ConditionalLockBuffer(). If we get it,
add this tuple plus anything pending to hashm_ntuples and test the
split threshold, exactly as now. Without concurrent inserters the
lock is always free, so the count is exact and split timing is the
same as master's.

- If someone else holds it, don't wait. Add 1 to a backend-local
pending count for that index (a dynahash keyed by index OID), and
leave the metapage out of the WAL record.

- Wait for the lock anyway if this insert added an overflow page, or
if 32 tuples are already pending.

- When an insert counts more than its own tuple, the increment goes
in the metapage's block data in XLOG_HASH_INSERT, and redo adds it.
pg_waldump prints "ntuples +N".

At any moment the count lags by at most 32 tuples per inserting
backend, and only by tuples that found the lock taken. That bound
grows with the number of backends, as you said it would for batching.
The difference is that a pending count only builds up while the lock
is actually contended, and the backend's next insert that finds the
lock free flushes it.

The worst case I could build was 64 concurrent short sessions
(pgbench -C, 64 clients, 40s), where the count ended 1.04% low and the
index had 3819 buckets against master's 3872. Since splits are
decided by the same count test as before, nothing new happens with
duplicates, so the duplicates-only overflow counter shouldn't be
needed. The duplicate and delete-heavy runs below come out the
same as master.

Same c7i.8xlarge (32 vCPU, one NUMA node, tmpfs, -O2, no asserts),
single-row INSERT, 2M preload, 20s per point, best of 3:

clients 1 16 32 64 128
master 39963 373439 295513 275827 251213
v1 39967 510042 569896 562110 561281

Measured against master on identical data:

- Mixed load (8 concurrent writers, unique keys plus a heavy
duplicate, delete a third, VACUUM, insert more): same row count,
same ntuples and maxbucket, index probes match seqscan for both
the unique and the duplicate key.
- 500k inserts of one key: maxbucket 1628 on both.
- Delete-heavy (2M, delete 90%, VACUUM, 2M more): 9369 pages and
7167 buckets on both.
- High-duplicate (2M rows, 50 keys, 8 writers): 6515 buckets on
both, 4902 overflow pages against 4900.
- Single-client INSERT ... SELECT of 2M rows: median 2729 ms against
2723 ms over 7 interleaved runs, which is within noise.
- WAL per insert at 32 clients: 204.5 bytes against 215.9.
- Index probes after a 64-client insert load: 935k against 942k tps,
on an index with twice the rows.

A streaming standby replaying 8 concurrent insert-ers (long and short
sessions, plus a delete and VACUUM) ends with the same row count and
the same metapage ntuples and maxbucket as the primary, and probes
match. The wal_consistency_checking=hash checksum failure I mentioned
still happens on unpatched upstream master, with or without this
patch.

Tests in src/test/modules/hash gets a regression test that forces the
deferred path through a new injection point, hash-insert-defer-count,
and checks the count, the cap, the per-index entries and that the
index still splits. It also gets a TAP test with concurrent inserts
on a primary and standby. meson test passes.

This changes the XLOG_HASH_INSERT record: the metapage block is now
optional and can carry data. So it's master-only, and whoever commits
it should bump XLOG_PAGE_MAGIC.

best.

-greg

Hi David, all,

v2 attached (d2adf339b06). TL;DR: ~parity with btree performance.

Changes since v1:

- No metapage pin on the common path. Every insert used to pin the
metapage, and a failed try-lock also writes to its buffer header.
Either way the metapage's cache line moved between CPUs on every
insert.

- Batching once contended. After a backend has done 1024 inserts into an
index and then finds the lock taken, it tries the lock only every 32nd
insert, or when it added an overflow page. It waits for the lock if
256 tuples are pending. Sweeps showed that waiting at 256 beats
waiting at 32 by about 25%.

- Short sessions keep v1 behaviour. That's what the 1024-insert
threshold is for. Without it, sessions of 10 inserts left 30% of the
count uncounted. With it, the worst case is 1.4% low.

Numbers are from a c7i.24xlarge (48 cores, one socket), with the
server pinned to 64 vCPUs and pgbench to the other 32, tmpfs, -O2, best
of 3. Single-row INSERT into a table with a 2M-row index:

clients 16 32 64 128 256
master 388045 139803 81312 60753 49640
v2 528484 638372 684513 674565 686102
btree 514299 648486 681106 733686 719012

Here v2 is level with btree; across runs it varied by about 5% at 128
and 256 clients (700-716k). With 10 rows per INSERT the index work
dominates:

clients 16 32 64 128 256
master 14552 13312 11665 10206 8732
v2 202884 227378 194543 215502 206641
btree 174719 243469 241316 237434 219777

Most of what's left between v2 and btree is the index growing during
the run, at about 6400 bucket splits a second. Every split, and every
overflow page allocated or freed, still takes the metapage and the
bitmap page exclusively, and in the profile those waits are what's
left; the tuple counter no longer shows up. On an index that already
has its buckets (built on 64M rows, all but 1/64 deleted, vacuumed),
10-row inserts give v2 240k/218k/168k TPS at 32/64/128 clients, against
244k/194k/173k for btree - within "spitting distance" even before
targeting this latest point of contention identified.

Reducing the split and overflow allocation traffic on the metapage would
be a separate patch. Wait for v3 with that before deep review please.

Against master on identical data:

- Mixed load (8 writers, unique keys plus a heavy duplicate, delete a
third, VACUUM, insert more): same row count, index probes match
seqscan for the unique and the duplicate key, maxbucket 3039
against 3040.
- 500k inserts of one key: maxbucket 1628 on both.
- Delete-heavy (2M, delete 90%, VACUUM, 2M more): 9369 pages and
7167 buckets on both.
- High-duplicate (2M rows, 50 keys, 8 writers): 6515 buckets on both.
- A streaming standby replaying 8 concurrent inserters into two hash
indexes ends with the same rows, the same metapage ntuples and
maxbucket, and matching probes.

The wal_consistency_checking=hash checksum failure I mentioned earlier
still happens on unpatched master, with or without this patch. That's
covered by [0]/messages/by-id/055bb33c-bccc-bc1d-c2f8-8598534448ac@gmail.com, we can't overlook the importance of that fix.

In addition, I've added a new regression test in src/test/modules/hash
that drives the deferred path through a new injection point,
hash-insert-defer-count, and checks the counting rules, the cap, the
per-index state, and that the index still splits. It also gets a TAP
test with concurrent long and short sessions on a primary and a standby.
meson test passes on current master.

This changes the XLOG_HASH_INSERT record: the metapage block is now
optional and can carry data. So it's master-only, and whoever commits
it should bump XLOG_PAGE_MAGIC.

Correctness:
- The mixed-load, single-key, delete-heavy and high-duplicate
adversarial runs give the same results as master.
- The standby's metapage and row counts are identical to the primary's.
- The full meson test suite passes (387 ok, 0 fail), including on
current upstream (d2adf339b06).

more to come, best.

-greg

[0]: /messages/by-id/055bb33c-bccc-bc1d-c2f8-8598534448ac@gmail.com

Hi all,

v3 attached, on 8628df8891a. 0001 is v2's patch, rebased and otherwise
unchanged. 0002 is the split and overflow work I said v2 was waiting
for.

With the counter off the insert path, the waits left in a growing index
were on overflow pages.

Linear hashing splits buckets in order, so the buckets not yet split in
a round fill past a page and each get an overflow page, which they give
back when they are split. That's about one overflow allocation and one
free per split. Allocating took the metapage lock twice and searched
the bitmap page under an exclusive lock; freeing took the metapage lock
to lower hashm_firstfree.

0002:

- Searches the bitmap pages using the cached metapage, under a share
lock, and locks a bitmap page exclusively only to claim a bit. Bits
for pages not yet added are set, so a free bit always stands for an
existing page, but the cached copy may not know the splitpoint a new
page is in; it is refreshed before claiming a bit past what it knows.

- Locks the metapage only when nothing is free: it searches all bitmap
pages again from the first, then extends the index by 64 overflow
pages at once, leaving 63 free in the bitmap. XLOG_HASH_ADD_OVFL_PAGE
gains a page count, and registers the metapage only when it changes.

- Frees without the metapage. hashm_firstfree now only says which
bitmap page a search starts at. A page freed in an earlier bitmap
page is found by the search under the metapage lock before the index
grows, so it waits, but is not lost. That only matters past 32768
overflow pages.

- Locks the metapage only before a bitmap page, never while holding one.

Lock wait time summed over all backends, 10-row inserts at 64 clients
for 20s (1280 backend-seconds), mean of two runs:

v2 v3
bitmap page, allocate 78 s 9 s
metapage, allocate 23 s 2 s
bitmap page, free 15 s 2 s
metapage, free 6 s 0
metapage, refresh cached copy - 3 s

The metapage is now taken for allocation about 3500 times in that run,
against 88000.

Throughput moved less than that I'd expected. Testing on the same
c7i.24xlarge as before (64 vCPUs), pgbench on the other 32, median of 3
runs interleaved across builds:

10 rows per INSERT
clients 16 32 64 128 256
master 14471 13156 11493 9916 8569
v2 194268 223750 200518 207735 192457
v3 201624 227470 208918 218516 200836
btree 173797 237869 237800 227532 215764

1 row per INSERT
clients 16 64 128 256
v2 529010 665727 687972 694518
v3 519737 669429 708545 700054
btree 513265 666375 711535 722497

0002 is worth 2-5% at 10 rows, and single-row inserts are level with
btree as before. At 64 clients hash is still 12% behind btree, and the
index isn't what limits it any more.

As an experiment, I took WAL out with an UNLOGGED table and index, and
0002 shows what it removed:

10 rows per INSERT, UNLOGGED, growing index
clients 32 64 128
v2 418742 487044 421342
v3 436612 563457 502093
btree 321013 309160 325910

With WAL, both are waiting on WAL insertion (58% of hash backends in
LWLock:WALInsert, 45% for btree), and hash writes about 5% more WAL per
row, mostly split page images. On an index that doesn't split during
the run (built on 64M rows, all but 1/64 deleted, vacuumed) hash and
btree are level and 0002 makes no difference: 242k/193k/165k TPS at
32/64/128 clients for v3, 239k/180k/168k for btree. Hash also loses
more than btree as wal_buffers grows (16MB: 206k vs 241k; 256MB: 140k vs
222k), with or without 0002.

I haven't chased that; it's not in the code these patches touch but this
might become a target for exploration in the future.

I also tried keeping the count in the metapage as an unlogged hint, with
splits carrying it to the standby. That gained 0-2% on top of 0002, and
a standby's count could fall behind by every insert since the last split
or VACUUM, so I dropped that idea.

The cost of 0002 is a little space: up to 63 overflow pages from the
last batch that aren't used yet. In the delete-heavy run I measured
that as an additional 41 pages (9410 against 9369); the other runs match
master.

With 27caf4ca5ae in, wal_consistency_checking=hash now passes on master,
so I ran v3 that way: a standby replaying 16 writers into two hash
indexes, a delete and VACUUM, more inserts and a CREATE INDEX reports no
inconsistency, and its rows, metapages and probes match the primary's.

0002 also adds a regression test, hash_overflow_pages, covering the
batch, reuse without growing, frees and reuse of freed pages.

0002 changes XLOG_HASH_ADD_OVFL_PAGE, so like 0001 it's master-only and
needs an XLOG_PAGE_MAGIC bump at some point.

best.

-greg

v4 attached, on eaa5961efc6. Only the tests changed; cfbot failed v3
on two of them.

0001: 001_concurrent_inserts.pl runs eight pgbench --connect clients
against a node set up with allows_streaming, which sets
max_connections = 10. A client can open its next backend before the
last one has exited, so on the slower Autoconf and 32-bit tasks some
connections failed with "too many clients already". The test now sets
max_connections = 30.

0002: with 4-byte MAXALIGN a hash index tuple is 12 bytes, not 16, so
the fill factor is 384 instead of 307. The 6000-row table then got 16
buckets instead of 32, the inserts split the index, and the function
that walks the overflow pages ran into bucket pages ("invalid overflow
block number"). The test now uses 6600 rows, which gives 32 buckets
with either alignment, and prints whether a group of pages has more
than one page rather than its exact size, which depends on how many
tuples fit on a page.

-greg