Hi,
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.
Bucket splits themselves are not the problem: measured against btree
page splits they cost the same (16-32us typical, ~8ms worst case for
both, dominated by relation extension).
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.
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.
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.
- 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 the general direction is acceptable I'll turn this into a proper
patch with the pending-count storage settled.
best.
-greg
[1]
https://postgr.es/m/cad__ouiajlg_3mdchgy193s5-hhtjo6b8e4jvupggsv_taz...@mail.gmail.com
From 3c7b694ae8bc97e704a6faea43309ecc43f7d80f Mon Sep 17 00:00:00 2001
From: Greg Burd <[email protected]>
Date: Thu, 22 Oct 2026 11:11:52 -0400
Subject: [PATCH] POC: batch the hash index metapage tuple counter per backend
_hash_doinsert() exclusive-locks the metapage on every single insert, only
to do "hashm_ntuples += 1" and test the split threshold. Under concurrent
single-row inserts this serialises all inserters on the metapage buffer and
is the dominant cost: on a 32-vCPU box, hash-index insert throughput peaks
at ~16 clients and then declines, while an equivalent btree keeps scaling.
This is a proof of concept, not a finished patch. Each backend accumulates
its inserts for a given index locally and only takes the metapage lock once
per HASH_NTUPLES_BATCH inserts, adding the batch and testing for a split
then. The metapage is registered in the insert's WAL record only on those
flushes, with the batch delta as block data; redo adds the delta when the
metapage block is present.
Known rough edges, discussed in the proposal thread:
- pending counts are held in a fixed-size backend-local array and are lost
at backend exit (VACUUM recomputes hashm_ntuples, so this only delays a
split, never corrupts the index);
- the split trigger therefore lags by up to HASH_NTUPLES_BATCH per backend.
Author: Greg Burd <[email protected]>
---
src/backend/access/hash/hash_xlog.c | 14 ++++-
src/backend/access/hash/hashinsert.c | 77 +++++++++++++++++++++++-----
2 files changed, 76 insertions(+), 15 deletions(-)
diff --git a/src/backend/access/hash/hash_xlog.c
b/src/backend/access/hash/hash_xlog.c
index e9a2b9aa9a7..5d94def4079 100644
--- a/src/backend/access/hash/hash_xlog.c
+++ b/src/backend/access/hash/hash_xlog.c
@@ -123,8 +123,18 @@ hash_xlog_insert(XLogReaderState *record)
if (BufferIsValid(buffer))
UnlockReleaseBuffer(buffer);
- if (XLogReadBufferForRedo(record, 1, &buffer) == BLK_NEEDS_REDO)
+ /* PROTOTYPE: the metapage is only registered when a batched count is
flushed */
+ buffer = InvalidBuffer;
+ if (XLogRecHasBlockRef(record, 1) &&
+ XLogReadBufferForRedo(record, 1, &buffer) == BLK_NEEDS_REDO)
{
+ Size dlen;
+ char *d = XLogRecGetBlockData(record, 1, &dlen);
+ uint32 delta = 1;
+
+ if (dlen == sizeof(uint32))
+ memcpy(&delta, d, sizeof(uint32));
+
/*
* Note: in normal operation, we'd update the metapage while
still
* holding lock on the page we inserted into. But during
replay it's
@@ -133,7 +143,7 @@ hash_xlog_insert(XLogReaderState *record)
*/
page = BufferGetPage(buffer);
metap = HashPageGetMeta(page);
- metap->hashm_ntuples += 1;
+ metap->hashm_ntuples += delta;
PageSetLSN(page, lsn);
MarkBufferDirty(buffer);
diff --git a/src/backend/access/hash/hashinsert.c
b/src/backend/access/hash/hashinsert.c
index 3395bbc13f8..c83a8356aeb 100644
--- a/src/backend/access/hash/hashinsert.c
+++ b/src/backend/access/hash/hashinsert.c
@@ -22,6 +22,37 @@
#include "storage/predicate.h"
#include "utils/rel.h"
+/*
+ * PROTOTYPE: batch the metapage tuple count. Each backend accumulates up to
+ * HASH_NTUPLES_BATCH inserts per index locally and only then takes the
+ * metapage exclusive lock to add them and check whether to split.
+ *
+ * shortcut: fixed 8-slot backend-local table, counts lost at backend exit
+ * (VACUUM recomputes hashm_ntuples); upgrade to a proper per-relation cache
+ * entry with flush at end of xact if this goes anywhere.
+ */
+#define HASH_NTUPLES_BATCH 64
+#define HASH_PENDING_SLOTS 8
+static Oid hash_pending_relid[HASH_PENDING_SLOTS];
+static uint32 hash_pending_count[HASH_PENDING_SLOTS];
+
+static uint32 *
+hash_pending_slot(Relation rel)
+{
+ for (int i = 0; i < HASH_PENDING_SLOTS; i++)
+ {
+ if (hash_pending_relid[i] == RelationGetRelid(rel))
+ return &hash_pending_count[i];
+ if (hash_pending_relid[i] == InvalidOid)
+ {
+ hash_pending_relid[i] = RelationGetRelid(rel);
+ hash_pending_count[i] = 0;
+ return &hash_pending_count[i];
+ }
+ }
+ return NULL; /* full: fall back to
per-insert update */
+}
+
static void _hash_vacuum_one_page(Relation rel, Relation hrel,
Buffer
metabuf, Buffer buf);
@@ -47,6 +78,9 @@ _hash_doinsert(Relation rel, IndexTuple itup, Relation
heapRel, bool sorted)
HashPageOpaque pageopaque;
Size itemsz;
bool do_expand;
+ bool flush_count;
+ uint32 *pending;
+ uint32 delta = 1;
uint32 hashkey;
Bucket bucket;
OffsetNumber itup_off;
@@ -191,10 +225,18 @@ restart_insert:
}
/*
- * Write-lock the metapage so we can increment the tuple count. After
- * incrementing it, check to see if it's time for a split.
+ * Only every HASH_NTUPLES_BATCH'th insert by this backend write-locks
the
+ * metapage to publish the tuple count and check for a split.
*/
- LockBuffer(metabuf, BUFFER_LOCK_EXCLUSIVE);
+ pending = hash_pending_slot(rel);
+ flush_count = (pending == NULL || ++(*pending) >= HASH_NTUPLES_BATCH);
+ if (flush_count && pending != NULL)
+ {
+ delta = *pending;
+ *pending = 0;
+ }
+ if (flush_count)
+ LockBuffer(metabuf, BUFFER_LOCK_EXCLUSIVE);
/* Do the update. No ereport(ERROR) until changes are logged */
START_CRIT_SECTION();
@@ -203,15 +245,18 @@ restart_insert:
itup_off = _hash_pgaddtup(rel, buf, itemsz, itup, sorted);
MarkBufferDirty(buf);
- /* metapage operations */
- metap = HashPageGetMeta(metapage);
- metap->hashm_ntuples += 1;
+ do_expand = false;
+ if (flush_count)
+ {
+ metap = HashPageGetMeta(metapage);
+ metap->hashm_ntuples += delta;
- /* Make sure this stays in sync with _hash_expandtable() */
- do_expand = metap->hashm_ntuples >
- (double) metap->hashm_ffactor * (metap->hashm_maxbucket + 1);
+ /* Make sure this stays in sync with _hash_expandtable() */
+ do_expand = metap->hashm_ntuples >
+ (double) metap->hashm_ffactor * (metap->hashm_maxbucket
+ 1);
- MarkBufferDirty(metabuf);
+ MarkBufferDirty(metabuf);
+ }
/* XLOG stuff */
if (RelationNeedsWAL(rel))
@@ -223,7 +268,11 @@ restart_insert:
XLogBeginInsert();
XLogRegisterData(&xlrec, SizeOfHashInsert);
- XLogRegisterBuffer(1, metabuf, REGBUF_STANDARD);
+ if (flush_count)
+ {
+ XLogRegisterBuffer(1, metabuf, REGBUF_STANDARD);
+ XLogRegisterBufData(1, &delta, sizeof(delta));
+ }
XLogRegisterBuffer(0, buf, REGBUF_STANDARD);
XLogRegisterBufData(0, itup, IndexTupleSize(itup));
@@ -234,12 +283,14 @@ restart_insert:
recptr = XLogGetFakeLSN(rel);
PageSetLSN(BufferGetPage(buf), recptr);
- PageSetLSN(BufferGetPage(metabuf), recptr);
+ if (flush_count)
+ PageSetLSN(BufferGetPage(metabuf), recptr);
END_CRIT_SECTION();
/* drop lock on metapage, but keep pin */
- LockBuffer(metabuf, BUFFER_LOCK_UNLOCK);
+ if (flush_count)
+ LockBuffer(metabuf, BUFFER_LOCK_UNLOCK);
/*
* Release the modified page and ensure to release the pin on primary
--
2.54.0
