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
From 3ce1e84c87d05057f99c260ce42307c029f11a9f Mon Sep 17 00:00:00 2001
From: Greg Burd <[email protected]>
Date: Mon, 2 Nov 2026 17:49:06 -0500
Subject: [PATCH v3 1/2] Don't make hash index inserts serialize on the
metapage
Every hash index insert took the metapage's exclusive content lock to
increment hashm_ntuples and test whether a bucket split is due. With
concurrent inserters that one buffer lock serializes them all: on a
48-core machine, single-row INSERT throughput into a hash-indexed table
peaks at 16 clients and falls to 50k tps at 256, while btree reaches
720k.
hashm_ntuples only decides when to split. So when an insert finds the
metapage lock taken, don't wait. Leave the tuple uncounted, as a
pending count in a backend-local hash table keyed by index OID, and let
a later insert by the same backend that gets the lock add it to the
metapage. An insert that defers its count does not register the
metapage in its WAL record. When an insert counts more than its own
tuple, the increment goes in the metapage's block data, and redo
applies it.
Even a failed ConditionalLockBuffer() writes the buffer header, as does
a pin, so with many inserters the metapage's cache line still moves
between CPUs on every insert. So pin the metapage only when needed,
and once a backend has done 1024 inserts into the index and then found
the lock taken, have it try the lock only on every 32nd insert, or when
it added an overflow page. It waits for the lock once 256 tuples would
be pending. Shorter sessions try on every insert, because tuples
pending at backend exit are never counted.
Without concurrent inserters the lock is always free and the count is
exact, as before. Under concurrency the count lags by less than 256
tuples per backend, which only delays a split slightly; a VACUUM that
removes tuples recounts them. Since the count can now be low, don't
let the subtraction in _hash_vacuum_one_page() and its redo take it
below zero.
This changes the XLOG_HASH_INSERT record: the metapage block reference
is now optional and may carry data. Older servers cannot replay the
new records, so this is for master only, and XLOG_PAGE_MAGIC needs a
bump.
Discussion: https://postgr.es/m/ats7u1ISmgZaWcge@floki
---
src/backend/access/hash/README | 51 ++++-
src/backend/access/hash/hash_xlog.c | 17 +-
src/backend/access/hash/hashinsert.c | 181 ++++++++++++++---
src/backend/access/rmgrdesc/hashdesc.c | 12 ++
src/include/access/hash_xlog.h | 3 +-
src/test/modules/hash/Makefile | 6 +-
.../hash/expected/hash_deferred_count.out | 183 ++++++++++++++++++
src/test/modules/hash/meson.build | 6 +
.../modules/hash/sql/hash_deferred_count.sql | 84 ++++++++
.../modules/hash/t/001_concurrent_inserts.pl | 96 +++++++++
src/tools/pgindent/typedefs.list | 1 +
11 files changed, 597 insertions(+), 43 deletions(-)
create mode 100644 src/test/modules/hash/expected/hash_deferred_count.out
create mode 100644 src/test/modules/hash/sql/hash_deferred_count.sql
create mode 100644 src/test/modules/hash/t/001_concurrent_inserts.pl
diff --git a/src/backend/access/hash/README b/src/backend/access/hash/README
index fc9031117c9..8575a883530 100644
--- a/src/backend/access/hash/README
+++ b/src/backend/access/hash/README
@@ -304,17 +304,25 @@ The insertion algorithm is rather similar:
release lock but not pin, read/exclusive-lock
next page; repeat as needed
>> see below if no space in any page of bucket
- take buffer content lock in exclusive mode on metapage
+ if this backend has done 1024 inserts into the index, has since seen the
+ metapage lock taken, this is not its 32nd insert since, and we did not
+ add an overflow page, don't touch the metapage
+ else pin the metapage and try to take the lock without waiting; if that
+ fails and 255 tuples are pending, wait for it
insert tuple at appropriate place in page
mark current page dirty
- increment tuple count, decide if split needed
- mark meta page dirty
+ if we got the metapage lock
+ add this tuple and any pending ones to the tuple count, decide
if
+ split needed
+ mark meta page dirty
+ else
+ remember the tuple as pending
write WAL for insertion of tuple
- release the buffer content lock on metapage
+ release the buffer content lock on metapage, if we hold it
release buffer content lock on current page
if current page is not a bucket page, release the pin on bucket page
if split is needed, enter Split algorithm below
- release the pin on metapage
+ release the pin on metapage, if we hold one
To speed searches, the index entries within any individual index page are
kept sorted by hash code; the insertion code must take care to insert new
@@ -326,10 +334,31 @@ that readers do not see a partially-updated page.
To avoid deadlock between readers and inserters, whenever there is a need
to lock multiple buckets, we always take in the order suggested in Lock
Definitions above. This algorithm allows them a very high degree of
-concurrency. (The exclusive metapage lock taken to update the tuple count
-is stronger than necessary, since readers do not care about the tuple count,
-but the lock is held for such a short time that this is probably not an
-issue.)
+concurrency.
+
+The tuple count in the metapage (hashm_ntuples) only decides when to split
+a bucket. Taking the metapage lock on every insert just to bump it
+serializes concurrent inserters on that one buffer, so an inserter that
+finds the lock taken does not wait for it. It leaves its tuple uncounted,
+as a per-backend pending count for that index. Even a failed attempt to
+take the lock, or a pin, writes to the buffer header, and with many
+inserters that cache line moves between CPUs on every insert. So once a
+backend has done 1024 inserts into the index and then found the lock
+taken, it only looks at the metapage on every 32nd insert: it tries the
+lock, and if it gets it adds the pending tuples to the count. Shorter
+sessions try the lock on every insert, because tuples still pending when a
+backend exits are never counted, and batching would leave a large share of
+a short session's tuples uncounted. An insert that had to add an overflow
+page tries the lock too, because a full bucket is the sign that a split
+may be due. The backend waits for the lock if 256 tuples would otherwise
+be pending. Without concurrent inserters the lock is always free, and the
+count is exact.
+
+Tuples still pending when a backend exits are never counted. That costs
+at most a slightly late split, since a backend leaves fewer than 256
+tuples per index uncounted. A VACUUM that removes tuples recounts them
+(see below), and the code that subtracts from the count does not let it go
+negative.
When an inserter cannot find space in any existing page of a bucket, it
must obtain an overflow page and add that page to the bucket's chain.
@@ -423,7 +452,9 @@ buckets did *not* change at any time during the scan. This
provides a way of
correcting the stored tuple count if it gets out of sync for some reason. But
if a split or insertion does occur concurrently, the scan count is
untrustworthy; instead, subtract the number of tuples deleted from the stored
-tuple count and use that.
+tuple count and use that. (An insertion that left its tuple pending goes
+unnoticed here, but the error that causes is bounded by the cap on pending
+tuples.)
Interlocking Between Scans and VACUUM
-------------------------------------
diff --git a/src/backend/access/hash/hash_xlog.c
b/src/backend/access/hash/hash_xlog.c
index e9a2b9aa9a7..63ae2cc0108 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);
+ /* The metapage is included only if the insert updated the tuple count
*/
+ if (!XLogRecHasBlockRef(record, 1))
+ return;
+
if (XLogReadBufferForRedo(record, 1, &buffer) == BLK_NEEDS_REDO)
{
+ uint32 ntup_delta = 1;
+
+ if (XLogRecHasBlockData(record, 1))
+ memcpy(&ntup_delta, XLogRecGetBlockData(record, 1,
NULL),
+ 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 += ntup_delta;
PageSetLSN(page, lsn);
MarkBufferDirty(buffer);
@@ -1027,7 +1037,10 @@ hash_xlog_vacuum_one_page(XLogReaderState *record)
metapage = BufferGetPage(metabuf);
metap = HashPageGetMeta(metapage);
- metap->hashm_ntuples -= xldata->ntuples;
+ if (metap->hashm_ntuples > xldata->ntuples)
+ metap->hashm_ntuples -= xldata->ntuples;
+ else
+ metap->hashm_ntuples = 0;
PageSetLSN(metapage, lsn);
MarkBufferDirty(metabuf);
diff --git a/src/backend/access/hash/hashinsert.c
b/src/backend/access/hash/hashinsert.c
index 3395bbc13f8..e42213ed939 100644
--- a/src/backend/access/hash/hashinsert.c
+++ b/src/backend/access/hash/hashinsert.c
@@ -20,8 +20,40 @@
#include "access/xloginsert.h"
#include "miscadmin.h"
#include "storage/predicate.h"
+#include "utils/injection_point.h"
+#include "utils/memutils.h"
#include "utils/rel.h"
+/*
+ * Per-index insert state of this backend, mainly the tuples it inserted
+ * without adding them to the metapage's hashm_ntuples. See the description
+ * of the insertion algorithm in the README. Entries are keyed by index OID
+ * and never removed; a stale count left by a dropped or truncated index is
+ * less than HASH_MAX_PENDING_TUPLES, which is harmless.
+ */
+typedef struct HashPendingTuples
+{
+ Oid indexrelid; /* hash key */
+ uint32 ntuples; /* tuples not yet in
hashm_ntuples */
+ uint32 ninserted; /* inserts, counting up to
HASH_BATCH_AFTER */
+ bool batching; /* seen the metapage lock
taken? */
+} HashPendingTuples;
+
+static HTAB *hash_pending_tuples = NULL;
+
+/*
+ * Once this backend has inserted HASH_BATCH_AFTER tuples into the index and
+ * then found the metapage lock taken, its inserts stop looking at the
+ * metapage. Every HASH_PENDING_BATCH inserts it tries the lock again, and
+ * counts what is pending if it gets it. If HASH_MAX_PENDING_TUPLES are
+ * pending it waits for the lock. The tuples left pending when a backend
+ * exits are lost, so short sessions, whose share of those would be large,
+ * never batch.
+ */
+#define HASH_BATCH_AFTER 1024
+#define HASH_PENDING_BATCH 32
+#define HASH_MAX_PENDING_TUPLES 256
+
static void _hash_vacuum_one_page(Relation rel, Relation hrel,
Buffer
metabuf, Buffer buf);
@@ -39,14 +71,17 @@ _hash_doinsert(Relation rel, IndexTuple itup, Relation
heapRel, bool sorted)
{
Buffer buf = InvalidBuffer;
Buffer bucket_buf;
- Buffer metabuf;
+ Buffer metabuf = InvalidBuffer;
HashMetaPage metap;
HashMetaPage usedmetap = NULL;
- Page metapage;
Page page;
HashPageOpaque pageopaque;
Size itemsz;
bool do_expand;
+ bool added_ovfl = false;
+ bool metalocked;
+ HashPendingTuples *pending = NULL;
+ uint32 ntup_delta = 0;
uint32 hashkey;
Bucket bucket;
OffsetNumber itup_off;
@@ -65,12 +100,14 @@ _hash_doinsert(Relation rel, IndexTuple itup, Relation
heapRel, bool sorted)
restart_insert:
/*
- * Read the metapage. We don't lock it yet; HashMaxItemSize() will
- * examine pd_pagesize_version, but that can't change so we can examine
it
- * without a lock.
+ * Lock the primary bucket page for the target bucket. Most inserts
never
+ * touch the metapage, not even to pin it, because under concurrency
every
+ * pin and lock attempt on that one buffer moves its header between
CPUs.
+ * We pin it only when we need it.
*/
- metabuf = _hash_getbuf(rel, HASH_METAPAGE, HASH_NOLOCK, LH_META_PAGE);
- metapage = BufferGetPage(metabuf);
+ buf = _hash_getbucketbuf_from_hashkey(rel, hashkey, HASH_WRITE,
+
&usedmetap);
+ Assert(usedmetap != NULL);
/*
* Check whether the item can fit on a hash page at all. (Eventually, we
@@ -79,18 +116,13 @@ restart_insert:
*
* XXX this is useless code if we are only storing hash keys.
*/
- if (itemsz > HashMaxItemSize(metapage))
+ if (itemsz > HashMaxItemSize(BufferGetPage(buf)))
ereport(ERROR,
(errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
errmsg("index row size %zu exceeds hash
maximum %zu",
- itemsz,
HashMaxItemSize(metapage)),
+ itemsz,
HashMaxItemSize(BufferGetPage(buf))),
errhint("Values larger than a buffer page
cannot be indexed.")));
- /* Lock the primary bucket page for the target bucket. */
- buf = _hash_getbucketbuf_from_hashkey(rel, hashkey, HASH_WRITE,
-
&usedmetap);
- Assert(usedmetap != NULL);
-
CheckForSerializableConflictIn(rel, NULL, BufferGetBlockNumber(buf));
/* remember the primary bucket buffer to release the pin on it at end.
*/
@@ -114,6 +146,7 @@ restart_insert:
/* release the lock on bucket buffer, before completing the
split. */
LockBuffer(buf, BUFFER_LOCK_UNLOCK);
+ metabuf = _hash_getbuf(rel, HASH_METAPAGE, HASH_NOLOCK,
LH_META_PAGE);
_hash_finish_split(rel, metabuf, buf, bucket,
usedmetap->hashm_maxbucket,
usedmetap->hashm_highmask,
@@ -122,6 +155,7 @@ restart_insert:
/* release the pin on old and meta buffer. retry for insert. */
_hash_dropbuf(rel, buf);
_hash_dropbuf(rel, metabuf);
+ metabuf = InvalidBuffer;
goto restart_insert;
}
@@ -140,6 +174,9 @@ restart_insert:
if (IsBufferCleanupOK(buf))
{
+ if (!BufferIsValid(metabuf))
+ metabuf = _hash_getbuf(rel,
HASH_METAPAGE, HASH_NOLOCK,
+
LH_META_PAGE);
_hash_vacuum_one_page(rel, heapRel, metabuf,
buf);
if (PageGetFreeSpace(page) >= itemsz)
@@ -179,8 +216,12 @@ restart_insert:
LockBuffer(buf, BUFFER_LOCK_UNLOCK);
/* chain to a new overflow page */
+ if (!BufferIsValid(metabuf))
+ metabuf = _hash_getbuf(rel, HASH_METAPAGE,
HASH_NOLOCK,
+
LH_META_PAGE);
buf = _hash_addovflpage(rel, metabuf, buf, (buf ==
bucket_buf));
page = BufferGetPage(buf);
+ added_ovfl = true;
/* should fit now, given test above */
Assert(PageGetFreeSpace(page) >= itemsz);
@@ -193,8 +234,71 @@ 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.
+ *
+ * Every insert wants this lock, so under concurrency it serializes the
+ * inserters. If someone else holds it, don't wait: leave the tuple
+ * pending. Once this backend has done HASH_BATCH_AFTER inserts into
the
+ * index, a failed try also makes it start batching: it only tries the
+ * lock on every HASH_PENDING_BATCH'th insert, since even a failed try
+ * writes to the buffer header and moves that cache line between CPUs.
An
+ * insert that added an overflow page tries anyway, since the bucket may
+ * be due for a split. Wait for the lock if HASH_MAX_PENDING_TUPLES are
+ * pending.
*/
- LockBuffer(metabuf, BUFFER_LOCK_EXCLUSIVE);
+ {
+ Oid indexrelid = RelationGetRelid(rel);
+ bool found;
+
+ if (hash_pending_tuples == NULL)
+ {
+ HASHCTL ctl;
+
+ ctl.keysize = sizeof(Oid);
+ ctl.entrysize = sizeof(HashPendingTuples);
+ ctl.hcxt = TopMemoryContext;
+ hash_pending_tuples = hash_create("hash index pending
tuples",
+
16, &ctl,
+
HASH_ELEM | HASH_BLOBS |
+
HASH_CONTEXT);
+ }
+ pending = hash_search(hash_pending_tuples, &indexrelid,
HASH_ENTER,
+ &found);
+ if (!found)
+ {
+ pending->ntuples = 0;
+ pending->ninserted = 0;
+ pending->batching = false;
+ }
+ if (pending->ninserted < HASH_BATCH_AFTER)
+ pending->ninserted++;
+ }
+
+ if (!added_ovfl && pending->batching &&
+ pending->ntuples % HASH_PENDING_BATCH != HASH_PENDING_BATCH - 1)
+ metalocked = false;
+ else
+ {
+ if (!BufferIsValid(metabuf))
+ metabuf = _hash_getbuf(rel, HASH_METAPAGE, HASH_NOLOCK,
+
LH_META_PAGE);
+
+#ifdef USE_INJECTION_POINTS
+ /* let tests act as if the lock was taken */
+ if (IS_INJECTION_POINT_ATTACHED("hash-insert-defer-count"))
+ metalocked = false;
+ else
+#endif
+ metalocked = ConditionalLockBuffer(metabuf);
+
+ if (!metalocked && pending->ntuples >= HASH_MAX_PENDING_TUPLES
- 1)
+ {
+ LockBuffer(metabuf, BUFFER_LOCK_EXCLUSIVE);
+ metalocked = true;
+ }
+ }
+
+ if (!metalocked && pending->ninserted >= HASH_BATCH_AFTER)
+ pending->batching = true;
/* Do the update. No ereport(ERROR) until changes are logged */
START_CRIT_SECTION();
@@ -203,15 +307,24 @@ 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 (metalocked)
+ {
+ /* metapage operations */
+ ntup_delta = 1 + pending->ntuples;
+ pending->ntuples = 0;
- /* Make sure this stays in sync with _hash_expandtable() */
- do_expand = metap->hashm_ntuples >
- (double) metap->hashm_ffactor * (metap->hashm_maxbucket + 1);
+ metap = HashPageGetMeta(BufferGetPage(metabuf));
+ metap->hashm_ntuples += ntup_delta;
- MarkBufferDirty(metabuf);
+ /* Make sure this stays in sync with _hash_expandtable() */
+ do_expand = metap->hashm_ntuples >
+ (double) metap->hashm_ffactor * (metap->hashm_maxbucket
+ 1);
+
+ MarkBufferDirty(metabuf);
+ }
+ else
+ pending->ntuples++;
/* XLOG stuff */
if (RelationNeedsWAL(rel))
@@ -223,7 +336,12 @@ restart_insert:
XLogBeginInsert();
XLogRegisterData(&xlrec, SizeOfHashInsert);
- XLogRegisterBuffer(1, metabuf, REGBUF_STANDARD);
+ if (metalocked)
+ {
+ XLogRegisterBuffer(1, metabuf, REGBUF_STANDARD);
+ if (ntup_delta > 1)
+ XLogRegisterBufData(1, &ntup_delta,
sizeof(uint32));
+ }
XLogRegisterBuffer(0, buf, REGBUF_STANDARD);
XLogRegisterBufData(0, itup, IndexTupleSize(itup));
@@ -234,12 +352,14 @@ restart_insert:
recptr = XLogGetFakeLSN(rel);
PageSetLSN(BufferGetPage(buf), recptr);
- PageSetLSN(BufferGetPage(metabuf), recptr);
+ if (metalocked)
+ PageSetLSN(BufferGetPage(metabuf), recptr);
END_CRIT_SECTION();
/* drop lock on metapage, but keep pin */
- LockBuffer(metabuf, BUFFER_LOCK_UNLOCK);
+ if (metalocked)
+ LockBuffer(metabuf, BUFFER_LOCK_UNLOCK);
/*
* Release the modified page and ensure to release the pin on primary
@@ -253,8 +373,9 @@ restart_insert:
if (do_expand)
_hash_expandtable(rel, metabuf);
- /* Finally drop our pin on the metapage */
- _hash_dropbuf(rel, metabuf);
+ /* Finally drop our pin on the metapage, if we took one */
+ if (BufferIsValid(metabuf))
+ _hash_dropbuf(rel, metabuf);
}
/*
@@ -417,8 +538,12 @@ _hash_vacuum_one_page(Relation rel, Relation hrel, Buffer
metabuf, Buffer buf)
pageopaque = HashPageGetOpaque(page);
pageopaque->hasho_flag &= ~LH_PAGE_HAS_DEAD_TUPLES;
+ /* the count can be low by pending tuples; don't let it go
negative */
metap = HashPageGetMeta(BufferGetPage(metabuf));
- metap->hashm_ntuples -= ndeletable;
+ if (metap->hashm_ntuples > ndeletable)
+ metap->hashm_ntuples -= ndeletable;
+ else
+ metap->hashm_ntuples = 0;
MarkBufferDirty(buf);
MarkBufferDirty(metabuf);
diff --git a/src/backend/access/rmgrdesc/hashdesc.c
b/src/backend/access/rmgrdesc/hashdesc.c
index 593013afe9c..6b410b80638 100644
--- a/src/backend/access/rmgrdesc/hashdesc.c
+++ b/src/backend/access/rmgrdesc/hashdesc.c
@@ -46,6 +46,18 @@ hash_desc(StringInfo buf, XLogReaderState *record)
xl_hash_insert *xlrec = (xl_hash_insert *) rec;
appendStringInfo(buf, "off %u", xlrec->offnum);
+ /* a full-page image of the metapage drops the
increment */
+ if (XLogRecHasBlockRef(record, 1) &&
+ (XLogRecHasBlockData(record, 1) ||
+ !XLogRecHasBlockImage(record, 1)))
+ {
+ uint32 ntup_delta = 1;
+
+ if (XLogRecHasBlockData(record, 1))
+ memcpy(&ntup_delta,
XLogRecGetBlockData(record, 1, NULL),
+ sizeof(uint32));
+ appendStringInfo(buf, ", ntuples +%u",
ntup_delta);
+ }
break;
}
case XLOG_HASH_ADD_OVFL_PAGE:
diff --git a/src/include/access/hash_xlog.h b/src/include/access/hash_xlog.h
index 149aed69dc5..af65e5b5ce3 100644
--- a/src/include/access/hash_xlog.h
+++ b/src/include/access/hash_xlog.h
@@ -57,7 +57,8 @@
* This data record is used for XLOG_HASH_INSERT
*
* Backup Blk 0: original page (data contains the inserted tuple)
- * Backup Blk 1: metapage (HashMetaPageData)
+ * Backup Blk 1: metapage, present only if the tuple count was updated (data
+ * is the uint32 count increment if it is not 1)
*/
typedef struct xl_hash_insert
{
diff --git a/src/test/modules/hash/Makefile b/src/test/modules/hash/Makefile
index 977c05ef4d2..8d8b798ebac 100644
--- a/src/test/modules/hash/Makefile
+++ b/src/test/modules/hash/Makefile
@@ -1,8 +1,10 @@
# src/test/modules/hash/Makefile
-EXTRA_INSTALL = src/test/modules/injection_points
+EXTRA_INSTALL = src/test/modules/injection_points contrib/pageinspect
-REGRESS = hash_incomplete_splits
+REGRESS = hash_deferred_count hash_incomplete_splits
+
+TAP_TESTS = 1
ifdef USE_PGXS
PG_CONFIG = pg_config
diff --git a/src/test/modules/hash/expected/hash_deferred_count.out
b/src/test/modules/hash/expected/hash_deferred_count.out
new file mode 100644
index 00000000000..26bcc326136
--- /dev/null
+++ b/src/test/modules/hash/expected/hash_deferred_count.out
@@ -0,0 +1,183 @@
+-- Test the deferred tuple count of hash index inserts.
+--
+-- An insert that finds the metapage locked leaves its tuple pending instead
+-- of waiting for the lock. Once a backend has done 1024 inserts into the
+-- index, a failed try also makes it start batching: it only tries the lock
+-- on every 32nd insert. It waits for the lock once 256 tuples would be
+-- pending. The hash-insert-defer-count injection point makes every try act
+-- as if the lock was taken.
+CREATE EXTENSION injection_points;
+CREATE EXTENSION pageinspect;
+SELECT injection_points_set_local();
+ injection_points_set_local
+----------------------------
+
+(1 row)
+
+CREATE TABLE hash_count_test (v int4) WITH (autovacuum_enabled = false);
+CREATE INDEX hash_count_index ON hash_count_test USING hash (v);
+-- Without contention, the count is exact
+INSERT INTO hash_count_test SELECT g FROM generate_series(1, 10) g;
+SELECT ntuples FROM hash_metapage_info(get_raw_page('hash_count_index', 0));
+ ntuples
+---------
+ 10
+(1 row)
+
+-- Deferred inserts leave the count alone
+SELECT injection_points_attach('hash-insert-defer-count', 'notice');
+ injection_points_attach
+-------------------------
+
+(1 row)
+
+INSERT INTO hash_count_test SELECT g FROM generate_series(1, 20) g;
+SELECT ntuples FROM hash_metapage_info(get_raw_page('hash_count_index', 0));
+ ntuples
+---------
+ 10
+(1 row)
+
+-- Before 1024 inserts, every insert tries the lock; the next one that gets
+-- it counts what is pending
+SELECT injection_points_detach('hash-insert-defer-count');
+ injection_points_detach
+-------------------------
+
+(1 row)
+
+INSERT INTO hash_count_test VALUES (1);
+SELECT ntuples FROM hash_metapage_info(get_raw_page('hash_count_index', 0));
+ ntuples
+---------
+ 31
+(1 row)
+
+-- After 1024 inserts, a failed try starts batching
+INSERT INTO hash_count_test SELECT g FROM generate_series(1, 1000) g;
+SELECT ntuples FROM hash_metapage_info(get_raw_page('hash_count_index', 0));
+ ntuples
+---------
+ 1031
+(1 row)
+
+SELECT injection_points_attach('hash-insert-defer-count', 'notice');
+ injection_points_attach
+-------------------------
+
+(1 row)
+
+INSERT INTO hash_count_test SELECT g FROM generate_series(1, 20) g;
+SELECT ntuples FROM hash_metapage_info(get_raw_page('hash_count_index', 0));
+ ntuples
+---------
+ 1031
+(1 row)
+
+-- The insert that would leave 256 pending waits for the lock and counts
+-- them all, leaving 64 of these 300 pending
+INSERT INTO hash_count_test SELECT g FROM generate_series(1, 300) g;
+SELECT ntuples FROM hash_metapage_info(get_raw_page('hash_count_index', 0));
+ ntuples
+---------
+ 1287
+(1 row)
+
+-- With the lock free again, the backend still only tries it on every 32nd
+-- insert: 31 more leave 95 pending, and the next one counts all 96
+SELECT injection_points_detach('hash-insert-defer-count');
+ injection_points_detach
+-------------------------
+
+(1 row)
+
+INSERT INTO hash_count_test SELECT g FROM generate_series(1, 31) g;
+SELECT ntuples FROM hash_metapage_info(get_raw_page('hash_count_index', 0));
+ ntuples
+---------
+ 1287
+(1 row)
+
+INSERT INTO hash_count_test VALUES (1);
+SELECT ntuples FROM hash_metapage_info(get_raw_page('hash_count_index', 0));
+ ntuples
+---------
+ 1383
+(1 row)
+
+SELECT count(*) FROM hash_count_test;
+ count
+-------
+ 1383
+(1 row)
+
+-- Each index has its own pending count: a new index counts every insert
+CREATE INDEX hash_count_index2 ON hash_count_test USING hash (v);
+INSERT INTO hash_count_test SELECT g FROM generate_series(1, 5) g;
+SELECT ntuples FROM hash_metapage_info(get_raw_page('hash_count_index', 0));
+ ntuples
+---------
+ 1383
+(1 row)
+
+SELECT ntuples FROM hash_metapage_info(get_raw_page('hash_count_index2', 0));
+ ntuples
+---------
+ 1388
+(1 row)
+
+-- A deferred count cannot stop the index from splitting, because at most
+-- 255 tuples stay pending. Build a 2-bucket index, then insert with every
+-- try of the lock failing.
+DROP INDEX hash_count_index, hash_count_index2;
+TRUNCATE hash_count_test;
+INSERT INTO hash_count_test SELECT 1 FROM generate_series(1, 10);
+ANALYZE hash_count_test;
+CREATE INDEX hash_count_index ON hash_count_test USING hash (v);
+SELECT maxbucket FROM hash_metapage_info(get_raw_page('hash_count_index', 0));
+ maxbucket
+-----------
+ 1
+(1 row)
+
+SELECT injection_points_attach('hash-insert-defer-count', 'notice');
+ injection_points_attach
+-------------------------
+
+(1 row)
+
+INSERT INTO hash_count_test SELECT g FROM generate_series(1, 10000) g;
+SELECT injection_points_detach('hash-insert-defer-count');
+ injection_points_detach
+-------------------------
+
+(1 row)
+
+SELECT maxbucket > 16 AS split,
+ ntuples >= 10010 - 255 AND ntuples <= 10010 AS count_ok
+ FROM hash_metapage_info(get_raw_page('hash_count_index', 0));
+ split | count_ok
+-------+----------
+ t | t
+(1 row)
+
+-- Index scans see the deferred tuples
+SET enable_seqscan = off;
+SET enable_bitmapscan = off;
+SELECT count(*) FROM hash_count_test WHERE v = 1;
+ count
+-------
+ 11
+(1 row)
+
+SELECT count(*) FROM hash_count_test WHERE v = 9999;
+ count
+-------
+ 1
+(1 row)
+
+RESET enable_seqscan;
+RESET enable_bitmapscan;
+DROP TABLE hash_count_test;
+DROP EXTENSION pageinspect;
+DROP EXTENSION injection_points;
diff --git a/src/test/modules/hash/meson.build
b/src/test/modules/hash/meson.build
index 284ebab70ff..9b009607396 100644
--- a/src/test/modules/hash/meson.build
+++ b/src/test/modules/hash/meson.build
@@ -10,7 +10,13 @@ tests += {
'bd': meson.current_build_dir(),
'regress': {
'sql': [
+ 'hash_deferred_count',
'hash_incomplete_splits',
],
},
+ 'tap': {
+ 'tests': [
+ 't/001_concurrent_inserts.pl',
+ ],
+ },
}
diff --git a/src/test/modules/hash/sql/hash_deferred_count.sql
b/src/test/modules/hash/sql/hash_deferred_count.sql
new file mode 100644
index 00000000000..d89e98b080b
--- /dev/null
+++ b/src/test/modules/hash/sql/hash_deferred_count.sql
@@ -0,0 +1,84 @@
+-- Test the deferred tuple count of hash index inserts.
+--
+-- An insert that finds the metapage locked leaves its tuple pending instead
+-- of waiting for the lock. Once a backend has done 1024 inserts into the
+-- index, a failed try also makes it start batching: it only tries the lock
+-- on every 32nd insert. It waits for the lock once 256 tuples would be
+-- pending. The hash-insert-defer-count injection point makes every try act
+-- as if the lock was taken.
+CREATE EXTENSION injection_points;
+CREATE EXTENSION pageinspect;
+SELECT injection_points_set_local();
+
+CREATE TABLE hash_count_test (v int4) WITH (autovacuum_enabled = false);
+CREATE INDEX hash_count_index ON hash_count_test USING hash (v);
+
+-- Without contention, the count is exact
+INSERT INTO hash_count_test SELECT g FROM generate_series(1, 10) g;
+SELECT ntuples FROM hash_metapage_info(get_raw_page('hash_count_index', 0));
+
+-- Deferred inserts leave the count alone
+SELECT injection_points_attach('hash-insert-defer-count', 'notice');
+INSERT INTO hash_count_test SELECT g FROM generate_series(1, 20) g;
+SELECT ntuples FROM hash_metapage_info(get_raw_page('hash_count_index', 0));
+
+-- Before 1024 inserts, every insert tries the lock; the next one that gets
+-- it counts what is pending
+SELECT injection_points_detach('hash-insert-defer-count');
+INSERT INTO hash_count_test VALUES (1);
+SELECT ntuples FROM hash_metapage_info(get_raw_page('hash_count_index', 0));
+
+-- After 1024 inserts, a failed try starts batching
+INSERT INTO hash_count_test SELECT g FROM generate_series(1, 1000) g;
+SELECT ntuples FROM hash_metapage_info(get_raw_page('hash_count_index', 0));
+SELECT injection_points_attach('hash-insert-defer-count', 'notice');
+INSERT INTO hash_count_test SELECT g FROM generate_series(1, 20) g;
+SELECT ntuples FROM hash_metapage_info(get_raw_page('hash_count_index', 0));
+
+-- The insert that would leave 256 pending waits for the lock and counts
+-- them all, leaving 64 of these 300 pending
+INSERT INTO hash_count_test SELECT g FROM generate_series(1, 300) g;
+SELECT ntuples FROM hash_metapage_info(get_raw_page('hash_count_index', 0));
+
+-- With the lock free again, the backend still only tries it on every 32nd
+-- insert: 31 more leave 95 pending, and the next one counts all 96
+SELECT injection_points_detach('hash-insert-defer-count');
+INSERT INTO hash_count_test SELECT g FROM generate_series(1, 31) g;
+SELECT ntuples FROM hash_metapage_info(get_raw_page('hash_count_index', 0));
+INSERT INTO hash_count_test VALUES (1);
+SELECT ntuples FROM hash_metapage_info(get_raw_page('hash_count_index', 0));
+SELECT count(*) FROM hash_count_test;
+
+-- Each index has its own pending count: a new index counts every insert
+CREATE INDEX hash_count_index2 ON hash_count_test USING hash (v);
+INSERT INTO hash_count_test SELECT g FROM generate_series(1, 5) g;
+SELECT ntuples FROM hash_metapage_info(get_raw_page('hash_count_index', 0));
+SELECT ntuples FROM hash_metapage_info(get_raw_page('hash_count_index2', 0));
+
+-- A deferred count cannot stop the index from splitting, because at most
+-- 255 tuples stay pending. Build a 2-bucket index, then insert with every
+-- try of the lock failing.
+DROP INDEX hash_count_index, hash_count_index2;
+TRUNCATE hash_count_test;
+INSERT INTO hash_count_test SELECT 1 FROM generate_series(1, 10);
+ANALYZE hash_count_test;
+CREATE INDEX hash_count_index ON hash_count_test USING hash (v);
+SELECT maxbucket FROM hash_metapage_info(get_raw_page('hash_count_index', 0));
+SELECT injection_points_attach('hash-insert-defer-count', 'notice');
+INSERT INTO hash_count_test SELECT g FROM generate_series(1, 10000) g;
+SELECT injection_points_detach('hash-insert-defer-count');
+SELECT maxbucket > 16 AS split,
+ ntuples >= 10010 - 255 AND ntuples <= 10010 AS count_ok
+ FROM hash_metapage_info(get_raw_page('hash_count_index', 0));
+
+-- Index scans see the deferred tuples
+SET enable_seqscan = off;
+SET enable_bitmapscan = off;
+SELECT count(*) FROM hash_count_test WHERE v = 1;
+SELECT count(*) FROM hash_count_test WHERE v = 9999;
+RESET enable_seqscan;
+RESET enable_bitmapscan;
+
+DROP TABLE hash_count_test;
+DROP EXTENSION pageinspect;
+DROP EXTENSION injection_points;
diff --git a/src/test/modules/hash/t/001_concurrent_inserts.pl
b/src/test/modules/hash/t/001_concurrent_inserts.pl
new file mode 100644
index 00000000000..ba865cc2031
--- /dev/null
+++ b/src/test/modules/hash/t/001_concurrent_inserts.pl
@@ -0,0 +1,96 @@
+# Copyright (c) 2026, PostgreSQL Global Development Group
+
+# Concurrent hash index inserts defer their tuple count when they find the
+# metapage locked. Check that such inserts replay correctly on a standby,
+# that the index still splits as it grows, and that the deferred count stays
+# close to the real one even when sessions are short.
+
+use strict;
+use warnings FATAL => 'all';
+
+use PostgreSQL::Test::Utils;
+use PostgreSQL::Test::Cluster;
+use Test::More;
+
+my $primary = PostgreSQL::Test::Cluster->new('primary');
+$primary->init(allows_streaming => 1);
+$primary->append_conf('postgresql.conf', 'autovacuum = off');
+$primary->start;
+$primary->safe_psql('postgres', 'CREATE EXTENSION pageinspect');
+
+$primary->backup('bkp');
+my $standby = PostgreSQL::Test::Cluster->new('standby');
+$standby->init_from_backup($primary, 'bkp', has_streaming => 1);
+$standby->start;
+
+$primary->safe_psql(
+ 'postgres', q{
+CREATE TABLE hash_conc (v int4);
+CREATE INDEX hash_conc_idx ON hash_conc USING hash (v);
+});
+
+my $meta = q{SELECT ntuples, maxbucket
+ FROM hash_metapage_info(get_raw_page('hash_conc_idx', 0))};
+my (undef, $maxbucket0) = split /\|/, $primary->safe_psql('postgres', $meta);
+
+# Long sessions, and short ones that exit with tuples pending
+$primary->pgbench(
+ '--no-vacuum --client=8 --jobs=8 --transactions=2000',
+ 0,
+ [qr{actually processed}],
+ [qr{^$}],
+ 'concurrent inserts',
+ {
+ 'hash_conc_long' => q{
+\set v random(1, 1000000000)
+INSERT INTO hash_conc VALUES (:v);
+INSERT INTO hash_conc VALUES (:v + 1);
+}
+ });
+$primary->pgbench(
+ '--no-vacuum --client=8 --jobs=8 --transactions=200 --connect',
+ 0,
+ [qr{actually processed}],
+ [qr{^$}],
+ 'concurrent short sessions',
+ {
+ 'hash_conc_short' => q{
+\set v random(1, 1000000000)
+INSERT INTO hash_conc VALUES (:v);
+}
+ });
+
+my $nrows = $primary->safe_psql('postgres', 'SELECT count(*) FROM hash_conc');
+is($nrows, 8 * 2000 * 2 + 8 * 200, 'all rows inserted');
+
+my ($ntuples, $maxbucket) =
+ split /\|/, $primary->safe_psql('postgres', $meta);
+cmp_ok($maxbucket, '>', $maxbucket0, 'index split');
+cmp_ok($ntuples, '<=', $nrows, 'tuple count not too high');
+# A session leaves fewer than 256 tuples uncounted, and a single-insert
+# session at most one
+cmp_ok(
+ $ntuples, '>=',
+ $nrows - (8 * 256 + 8 * 200),
+ 'tuple count not too low');
+
+$primary->wait_for_replay_catchup($standby);
+
+is($standby->safe_psql('postgres', $meta),
+ "$ntuples|$maxbucket", 'standby metapage matches primary');
+
+my $probe = q{
+SET enable_seqscan = off;
+SET enable_bitmapscan = off;
+SELECT count(*) FROM hash_conc h
+ WHERE (SELECT count(*) FROM hash_conc i WHERE i.v = h.v) =
+ (SELECT count(*) FROM hash_conc s WHERE s.v + 0 = h.v)
+ AND h.v % 97 = 0};
+my $expected = $primary->safe_psql('postgres',
+ 'SELECT count(*) FROM hash_conc WHERE v % 97 = 0');
+is($primary->safe_psql('postgres', $probe),
+ $expected, 'index probes match heap on primary');
+is($standby->safe_psql('postgres', $probe),
+ $expected, 'index probes match heap on standby');
+
+done_testing();
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index b964e5ee907..7a470985e96 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -1229,6 +1229,7 @@ HashPageOpaque
HashPageOpaqueData
HashPageStat
HashPath
+HashPendingTuples
HashScanOpaque
HashScanOpaqueData
HashScanPosData
--
2.50.1
From c8513fc2233a05b69ef839b51ea8dba894d7b16e Mon Sep 17 00:00:00 2001
From: Greg Burd <[email protected]>
Date: Mon, 2 Nov 2026 17:50:53 -0500
Subject: [PATCH v3 2/2] Allocate and free hash overflow pages without the
metapage lock
Allocating an overflow page took the metapage's exclusive lock twice,
and searched the bitmap page while holding its exclusive lock; freeing
one took the metapage lock to lower hashm_firstfree. A growing hash
index allocates and frees overflow pages about as often as it splits
buckets: 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. With the tuple counter off the
insert path, those locks were where concurrent inserters waited.
Search the bitmap pages using our cached copy of the metapage, under a
share lock, and lock a bitmap page exclusively only to claim a bit. A
free bit always stands for an existing page, since bits for pages not
yet added are set, but our copy may not know the splitpoint a recently
added page is in, so refresh the copy before claiming a bit past the
range it knows. Lock the metapage only when no free page is found:
search all bitmap pages again, from the first, and if there is still
none, extend the index by 64 overflow pages at once, all but the first
left free in the bitmap. The XLOG_HASH_ADD_OVFL_PAGE record says how
many pages were added and registers the metapage only when it changes.
Freeing a page no longer lowers hashm_firstfree, so it does not lock
the metapage either. hashm_firstfree now only tells searches which
bitmap page to start at; a page freed in an earlier bitmap page is
found by the search under the metapage lock, before the index is
extended.
The metapage is now only locked before a bitmap page, never while one
is held.
This changes XLOG_HASH_ADD_OVFL_PAGE, so it is for master only, and
XLOG_PAGE_MAGIC needs a bump.
Discussion: https://postgr.es/m/ats7u1ISmgZaWcge@floki
---
src/backend/access/hash/README | 93 +++--
src/backend/access/hash/hash_xlog.c | 15 +-
src/backend/access/hash/hashovfl.c | 393 ++++++++++++------
src/backend/access/hash/hashpage.c | 6 +-
src/backend/access/rmgrdesc/hashdesc.c | 5 +-
src/include/access/hash.h | 2 +
src/include/access/hash_xlog.h | 11 +-
src/test/modules/hash/Makefile | 2 +-
.../hash/expected/hash_overflow_pages.out | 108 +++++
src/test/modules/hash/meson.build | 1 +
.../modules/hash/sql/hash_overflow_pages.sql | 65 +++
11 files changed, 516 insertions(+), 185 deletions(-)
create mode 100644 src/test/modules/hash/expected/hash_overflow_pages.out
create mode 100644 src/test/modules/hash/sql/hash_overflow_pages.sql
diff --git a/src/backend/access/hash/README b/src/backend/access/hash/README
index 8575a883530..6a084378853 100644
--- a/src/backend/access/hash/README
+++ b/src/backend/access/hash/README
@@ -495,36 +495,56 @@ overflow page to the free pool.
Obtaining an overflow page:
+ using our cached copy of the metapage, start at the bitmap page that
+ first-free-bit is in
+ for each bitmap page:
+ pin bitmap page and take content lock in shared mode
+ search for a free page (zero bit in bitmap)
+ if found:
+ retake the content lock in exclusive mode, and search
again
+ if the bit is past the overflow pages our copy knows of,
+ release the bitmap page, refresh our copy,
retry the page
+ set bit in bitmap
+ mark bitmap page dirty
+ return page number
+ release bitmap page buffer content lock
+-- here when none found
take metapage content lock in exclusive mode
- determine next bitmap page number; if none, exit loop
- release meta page content lock
- pin bitmap page and take content lock in exclusive mode
- search for a free page (zero bit in bitmap)
- if found:
- set bit in bitmap
- mark bitmap page dirty
- take metapage buffer content lock in exclusive mode
- if first-free-bit value did not change,
- update it and mark meta page dirty
- else (not found):
- release bitmap page buffer content lock
- loop back to try next bitmap page, if any
--- here when we have checked all bitmap pages; we hold meta excl. lock
- extend index to add another overflow page; update meta information
+ search all bitmap pages again as above, from the first one
+ if found, lower first-free-bit to it if it's higher, and return it
+ extend index to add a batch of overflow pages; update meta information
+ mark all but the first of the new pages free in the bitmap
+ set first-free-bit to the second new page
mark meta page dirty
return page number
-It is slightly annoying to release and reacquire the metapage lock
-multiple times, but it seems best to do it that way to minimize loss of
-concurrency against processes just entering the index. We don't want
-to hold the metapage exclusive lock while reading in a bitmap page.
-(We can at least avoid repeated buffer pin/unpin here.)
+Most overflow pages are allocated and freed while the index grows. Linear
+hashing splits buckets in order, so the buckets not yet split in the
+current round fill past a page and get an overflow page each, which they
+give back when they are split. Taking the metapage lock for each of those,
+as was done before, serialized concurrent inserters behind it, and holding
+the bitmap page lock in exclusive mode while searching it serialized them
+again. So the metapage is locked only to add pages, and then pages are
+added 64 at a time.
+
+A bit is always set for a page that does not exist yet, and set for a page
+in use, so a free bit always stands for an existing page. But a cached copy
+of the metapage can be older than the splitpoint the page was added in, and
+then would compute the wrong block number for it; hence the refresh. The
+search under the metapage lock, from the first bitmap page, also finds
+pages freed in bitmap pages before the one first-free-bit is in; see below.
+
+Lock order: the metapage is only ever locked before a bitmap page, never
+while one is held.
The normal path for extending the index does not require doing I/O while
holding the metapage lock. We do have to do I/O when the extension
requires adding a new bitmap page as well as the required overflow page
... but that is an infrequent case, so the loss of concurrency seems
-acceptable.
+acceptable. A batch of pages is added by writing the last of them, as for
+a splitpoint's bucket pages; the pages in between read as zeroes until
+they are used. A batch never crosses into a new bitmap page; when one is
+needed, a single page is added along with it, as before.
The portion of tuple insertion that calls the above subroutine looks
like this:
@@ -564,27 +584,24 @@ accessors of pages in the bucket. The algorithm is:
delink overflow page from bucket chain
(this requires read/update/write/release of fore and aft siblings)
- pin meta page and take buffer content lock in shared mode
- determine which bitmap page contains the free space bit for page
- release meta page buffer content lock
+ using our cached copy of the metapage (refreshed if it doesn't know
+ the page), determine which bitmap page contains the free space bit
pin bitmap page and take buffer content lock in exclusive mode
- retake meta page buffer content lock in exclusive mode
move (insert) tuples that belong to the overflow page being freed
update bitmap bit
mark bitmap page dirty
- if page number is still less than first-free-bit,
- update first-free-bit field and mark meta page dirty
write WAL for delinking overflow page operation
release buffer content lock and pin
- release meta page buffer content lock and pin
-We have to do it this way because we must clear the bitmap bit before
-changing the first-free-bit field (hashm_firstfree). It is possible that
-we set first-free-bit too small (because someone has already reused the
-page we just freed), but that is okay; the only cost is the next overflow
-page acquirer will scan more bitmap bits than he needs to. What must be
-avoided is having first-free-bit greater than the actual first free bit,
-because then that free page would never be found by searchers.
+Freeing a page does not lower first-free-bit (hashm_firstfree), so it does
+not lock the metapage. First-free-bit only says which bitmap page searches
+start at; within a bitmap page, a search looks at all its bits. A page
+freed in an earlier bitmap page is found by the search under the metapage
+lock, which starts at the first bitmap page, before the index is extended.
+So a free page is never lost, though one in an earlier bitmap page may wait
+until the next time the index would otherwise be extended. Only indexes
+with more than one bitmap page (more than 32768 overflow pages, with 8kB
+pages) are affected.
The reason of moving tuples from overflow page while delinking the later is
to make that as an atomic operation. Not doing so could lead to spurious reads
@@ -609,9 +626,9 @@ write-ahead log record anyway, because we can log only a
fixed number of
pages, as given by XLR_MAX_BLOCK_ID (32), with current XLog machinery.
Ordinary item insertions (that don't force a page split or need a new overflow
-page) are single WAL entries. They touch a single bucket page and the
-metapage. The metapage is updated during replay as it is updated during
-original operation.
+page) are single WAL entries. They touch a single bucket page, and the
+metapage if they update the tuple count. The metapage is updated during
+replay as it is updated during original operation.
If an insertion causes the addition of an overflow page, there will be one
WAL entry for the new overflow page and second entry for insert itself.
diff --git a/src/backend/access/hash/hash_xlog.c
b/src/backend/access/hash/hash_xlog.c
index 63ae2cc0108..308c3a0290d 100644
--- a/src/backend/access/hash/hash_xlog.c
+++ b/src/backend/access/hash/hash_xlog.c
@@ -230,7 +230,14 @@ hash_xlog_add_ovfl_page(XLogReaderState *record)
data = XLogRecGetBlockData(record, 2, &datalen);
bitmap_page_bit = (uint32 *) data;
- SETBIT(freep, *bitmap_page_bit);
+ if (xlrec->bmpage_found)
+ SETBIT(freep, *bitmap_page_bit);
+ else
+ {
+ /* added pages left free */
+ for (uint32 k = 0; k < xlrec->nadded - 1; k++)
+ CLRBIT(freep, *bitmap_page_bit + k);
+ }
PageSetLSN(mappage, lsn);
MarkBufferDirty(mapbuffer);
@@ -256,6 +263,10 @@ hash_xlog_add_ovfl_page(XLogReaderState *record)
UnlockReleaseBuffer(newmapbuf);
}
+ /* The metapage is present only if it was modified */
+ if (!XLogRecHasBlockRef(record, 4))
+ return;
+
if (XLogReadBufferForRedo(record, 4, &metabuf) == BLK_NEEDS_REDO)
{
HashMetaPage metap;
@@ -271,7 +282,7 @@ hash_xlog_add_ovfl_page(XLogReaderState *record)
if (!xlrec->bmpage_found)
{
- metap->hashm_spares[metap->hashm_ovflpoint]++;
+ metap->hashm_spares[metap->hashm_ovflpoint] +=
xlrec->nadded;
if (new_bmpage)
{
diff --git a/src/backend/access/hash/hashovfl.c
b/src/backend/access/hash/hashovfl.c
index dbc57ef958c..d864dc02a0c 100644
--- a/src/backend/access/hash/hashovfl.c
+++ b/src/backend/access/hash/hashovfl.c
@@ -25,6 +25,19 @@
static uint32 _hash_firstfreebit(uint32 map);
+static Buffer _hash_findfreeovflpage(Relation rel, Buffer *metabuf,
+
HashMetaPage *metapp, Buffer *mapbufp,
+ uint32
*bitmap_page_bit, uint32 *bitp,
+ bool
metalocked);
+static bool _hash_ovflblkno_to_bitno_internal(HashMetaPage metap,
+
BlockNumber ovflblkno,
+
uint32 *bitno);
+
+/*
+ * When an overflow page has to be added at the end of the index, add this
+ * many, and mark the ones we don't use yet as free.
+ */
+#define HASH_OVFL_EXTEND_BATCH 64
/*
@@ -60,6 +73,23 @@ bitno_to_blkno(HashMetaPage metap, uint32 ovflbitnum)
*/
uint32
_hash_ovflblkno_to_bitno(HashMetaPage metap, BlockNumber ovflblkno)
+{
+ uint32 bitnum;
+
+ if (!_hash_ovflblkno_to_bitno_internal(metap, ovflblkno, &bitnum))
+ ereport(ERROR,
+ (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
+ errmsg("invalid overflow block number %u",
ovflblkno)));
+ return bitnum;
+}
+
+/*
+ * Workhorse for _hash_ovflblkno_to_bitno; returns false instead of raising an
+ * error if ovflblkno isn't an overflow page according to metap.
+ */
+static bool
+_hash_ovflblkno_to_bitno_internal(HashMetaPage metap, BlockNumber ovflblkno,
+ uint32 *bitno)
{
uint32 splitnum = metap->hashm_ovflpoint;
uint32 i;
@@ -80,13 +110,13 @@ _hash_ovflblkno_to_bitno(HashMetaPage metap, BlockNumber
ovflblkno)
*/
if (bitnum > metap->hashm_spares[i - 1] &&
bitnum <= metap->hashm_spares[i])
- return bitnum - 1; /* -1 to convert 1-based to
0-based */
+ {
+ *bitno = bitnum - 1; /* -1 to convert 1-based to
0-based */
+ return true;
+ }
}
- ereport(ERROR,
- (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
- errmsg("invalid overflow block number %u",
ovflblkno)));
- return 0; /* keep compiler quiet
*/
+ return false;
}
/*
@@ -117,21 +147,20 @@ _hash_addovflpage(Relation rel, Buffer metabuf, Buffer
buf, bool retain_pin)
HashPageOpaque pageopaque;
HashPageOpaque ovflopaque;
HashMetaPage metap;
+ HashMetaPage cachedmetap;
Buffer mapbuf = InvalidBuffer;
Buffer newmapbuf = InvalidBuffer;
BlockNumber blkno;
- uint32 orig_firstfree;
- uint32 splitnum;
+ uint32 splitnum = 0;
uint32 *freep = NULL;
uint32 max_ovflpg;
uint32 bit;
- uint32 bitmap_page_bit;
- uint32 first_page;
+ uint32 bitmap_page_bit = 0;
uint32 last_bit;
- uint32 last_page;
- uint32 i,
- j;
+ uint16 nadded = 1;
bool page_found = false;
+ bool metalocked = false;
+ bool metamodified = false;
XLogRecPtr recptr;
/*
@@ -181,91 +210,53 @@ _hash_addovflpage(Relation rel, Buffer metabuf, Buffer
buf, bool retain_pin)
buf = _hash_getbuf(rel, nextblkno, HASH_WRITE,
LH_OVERFLOW_PAGE);
}
- /* Get exclusive lock on the meta page */
+ /*
+ * Look for a free overflow page in the bitmap pages, without the
metapage
+ * lock. The bitmap pages' locations and the range of existing overflow
+ * pages come from our cached copy of the metapage. A bitmap page is
+ * searched under a share lock, and exclusive-locked only to claim a
bit.
+ * Bits for pages beyond the last existing overflow page are always set,
+ * so a free bit always stands for a real page, but a page added since
our
+ * copy was taken might be in a splitpoint the copy doesn't know of; so
+ * refresh the copy before claiming a bit beyond its range.
+ */
+ cachedmetap = _hash_getcachedmetap(rel, &metabuf, false);
+ ovflbuf = _hash_findfreeovflpage(rel, &metabuf, &cachedmetap, &mapbuf,
+
&bitmap_page_bit, &bit, false);
+ if (BufferIsValid(ovflbuf))
+ {
+ page_found = true;
+ metap = cachedmetap;
+ goto found;
+ }
+
+ /*
+ * None found. Lock the metapage, and search again with its current
+ * contents, from the first bitmap page: this also finds pages freed in
+ * bitmap pages before the one hashm_firstfree points into.
+ */
LockBuffer(metabuf, BUFFER_LOCK_EXCLUSIVE);
+ metalocked = true;
_hash_checkpage(rel, metabuf, LH_META_PAGE);
metap = HashPageGetMeta(BufferGetPage(metabuf));
- /* start search at hashm_firstfree */
- orig_firstfree = metap->hashm_firstfree;
- first_page = orig_firstfree >> BMPG_SHIFT(metap);
- bit = orig_firstfree & BMPG_MASK(metap);
- i = first_page;
- j = bit / BITS_PER_MAP;
- bit &= ~(BITS_PER_MAP - 1);
-
- /* outer loop iterates once per bitmap page */
- for (;;)
+ ovflbuf = _hash_findfreeovflpage(rel, &metabuf, &metap, &mapbuf,
+
&bitmap_page_bit, &bit, true);
+ if (BufferIsValid(ovflbuf))
{
- BlockNumber mapblkno;
- Page mappage;
- uint32 last_inpage;
-
- /* want to end search with the last existing overflow page */
- splitnum = metap->hashm_ovflpoint;
- max_ovflpg = metap->hashm_spares[splitnum] - 1;
- last_page = max_ovflpg >> BMPG_SHIFT(metap);
- last_bit = max_ovflpg & BMPG_MASK(metap);
-
- if (i > last_page)
- break;
-
- Assert(i < metap->hashm_nmaps);
- mapblkno = metap->hashm_mapp[i];
-
- if (i == last_page)
- last_inpage = last_bit;
- else
- last_inpage = BMPGSZ_BIT(metap) - 1;
-
- /* Release exclusive lock on metapage while reading bitmap page
*/
- LockBuffer(metabuf, BUFFER_LOCK_UNLOCK);
-
- mapbuf = _hash_getbuf(rel, mapblkno, HASH_WRITE,
LH_BITMAP_PAGE);
- mappage = BufferGetPage(mapbuf);
- freep = HashPageGetBitmap(mappage);
-
- for (; bit <= last_inpage; j++, bit += BITS_PER_MAP)
- {
- if (freep[j] != ALL_SET)
- {
- page_found = true;
-
- /* Reacquire exclusive lock on the meta page */
- LockBuffer(metabuf, BUFFER_LOCK_EXCLUSIVE);
-
- /* convert bit to bit number within page */
- bit += _hash_firstfreebit(freep[j]);
- bitmap_page_bit = bit;
-
- /* convert bit to absolute bit number */
- bit += (i << BMPG_SHIFT(metap));
- /* Calculate address of the recycled overflow
page */
- blkno = bitno_to_blkno(metap, bit);
-
- /* Fetch and init the recycled page */
- ovflbuf = _hash_getinitbuf(rel, blkno);
-
- goto found;
- }
- }
-
- /* No free space here, try to advance to next map page */
- _hash_relbuf(rel, mapbuf);
- mapbuf = InvalidBuffer;
- i++;
- j = 0; /* scan from start of
next map page */
- bit = 0;
-
- /* Reacquire exclusive lock on the meta page */
- LockBuffer(metabuf, BUFFER_LOCK_EXCLUSIVE);
+ page_found = true;
+ goto found;
}
/*
* No free pages --- have to extend the relation to add an overflow
page.
* First, check to see if we have to add a new bitmap page too.
*/
+ splitnum = metap->hashm_ovflpoint;
+ max_ovflpg = metap->hashm_spares[splitnum] - 1;
+ last_bit = max_ovflpg & BMPG_MASK(metap);
+
if (last_bit == (uint32) (BMPGSZ_BIT(metap) - 1))
{
/*
@@ -290,9 +281,38 @@ _hash_addovflpage(Relation rel, Buffer metabuf, Buffer
buf, bool retain_pin)
else
{
/*
- * Nothing to do here; since the page will be past the last
used page,
- * we know its bitmap bit was preinitialized to "in use".
+ * Add a batch of pages, so that the next overflow pages can be
found
+ * in the bitmap without the metapage lock. All the pages'
bits must
+ * be on the last bitmap page. Their bits are set, since they
are
+ * past the last used page; clear all but the first, which we
return.
*/
+ nadded = Min(HASH_OVFL_EXTEND_BATCH,
+ BMPGSZ_BIT(metap) - 1 - last_bit);
+
+ if (nadded > 1)
+ {
+ BlockNumber firstblk = bitno_to_blkno(metap, max_ovflpg
+ 1);
+
+ /*
+ * Extend the relation to cover the whole batch. The
pages after
+ * the first are left as zero pages, to be initialized
when used.
+ * If a previous attempt crashed after extending, they
may exist
+ * already.
+ */
+ if (RelationGetNumberOfBlocks(rel) < firstblk + nadded
&&
+ !_hash_alloc_buckets(rel, firstblk + 1, nadded
- 1))
+ nadded = 1;
+ }
+
+ if (nadded > 1)
+ {
+ mapbuf = _hash_getbuf(rel,
metap->hashm_mapp[metap->hashm_nmaps - 1],
+ HASH_WRITE,
LH_BITMAP_PAGE);
+ freep = HashPageGetBitmap(BufferGetPage(mapbuf));
+ bitmap_page_bit = last_bit + 2;
+ }
+ else
+ nadded = 1;
}
/* Calculate address of the new overflow page */
@@ -314,6 +334,9 @@ _hash_addovflpage(Relation rel, Buffer metabuf, Buffer buf,
bool retain_pin)
found:
+ if (page_found)
+ freep = HashPageGetBitmap(BufferGetPage(mapbuf));
+
/*
* Do the update. No ereport(ERROR) until changes are logged. We want
to
* log the changes for bitmap page and overflow page together to avoid
@@ -328,11 +351,28 @@ found:
/* mark page "in use" in the bitmap */
SETBIT(freep, bitmap_page_bit);
MarkBufferDirty(mapbuf);
+
+ /*
+ * If we searched with the metapage locked, start the next
searches at
+ * this page's bitmap page.
+ */
+ if (metalocked && bit < metap->hashm_firstfree)
+ {
+ metap->hashm_firstfree = bit;
+ MarkBufferDirty(metabuf);
+ metamodified = true;
+ }
}
else
{
- /* update the count to indicate new overflow page is added */
- metap->hashm_spares[splitnum]++;
+ /* update the count to indicate new overflow pages are added */
+ metap->hashm_spares[splitnum] += nadded;
+
+ /* the pages after the first are free */
+ for (uint32 k = 0; k < nadded - 1; k++)
+ CLRBIT(freep, bitmap_page_bit + k);
+ if (nadded > 1)
+ MarkBufferDirty(mapbuf);
if (BufferIsValid(newmapbuf))
{
@@ -345,7 +385,11 @@ found:
metap->hashm_spares[splitnum]++;
}
+ /* start the next searches after this page */
+ metap->hashm_firstfree = bit + 1;
+
MarkBufferDirty(metabuf);
+ metamodified = true;
/*
* for new overflow page, we don't need to explicitly set the
bit in
@@ -353,16 +397,6 @@ found:
*/
}
- /*
- * Adjust hashm_firstfree to avoid redundant searches. But don't risk
- * changing it if someone moved it while we were searching bitmap pages.
- */
- if (metap->hashm_firstfree == orig_firstfree)
- {
- metap->hashm_firstfree = bit + 1;
- MarkBufferDirty(metabuf);
- }
-
/* initialize new overflow page */
ovflpage = BufferGetPage(ovflbuf);
ovflopaque = HashPageGetOpaque(ovflpage);
@@ -386,6 +420,7 @@ found:
xlrec.bmpage_found = page_found;
xlrec.bmsize = metap->hashm_bmsize;
+ xlrec.nadded = page_found ? 0 : nadded;
XLogBeginInsert();
XLogRegisterData(&xlrec, SizeOfHashAddOvflPage);
@@ -404,8 +439,11 @@ found:
if (BufferIsValid(newmapbuf))
XLogRegisterBuffer(3, newmapbuf, REGBUF_WILL_INIT);
- XLogRegisterBuffer(4, metabuf, REGBUF_STANDARD);
- XLogRegisterBufData(4, &metap->hashm_firstfree, sizeof(uint32));
+ if (metamodified)
+ {
+ XLogRegisterBuffer(4, metabuf, REGBUF_STANDARD);
+ XLogRegisterBufData(4, &metap->hashm_firstfree,
sizeof(uint32));
+ }
recptr = XLogInsert(RM_HASH_ID, XLOG_HASH_ADD_OVFL_PAGE);
}
@@ -421,7 +459,8 @@ found:
if (BufferIsValid(newmapbuf))
PageSetLSN(BufferGetPage(newmapbuf), recptr);
- PageSetLSN(BufferGetPage(metabuf), recptr);
+ if (metamodified)
+ PageSetLSN(BufferGetPage(metabuf), recptr);
END_CRIT_SECTION();
@@ -433,7 +472,8 @@ found:
if (BufferIsValid(mapbuf))
_hash_relbuf(rel, mapbuf);
- LockBuffer(metabuf, BUFFER_LOCK_UNLOCK);
+ if (metalocked)
+ LockBuffer(metabuf, BUFFER_LOCK_UNLOCK);
if (BufferIsValid(newmapbuf))
_hash_relbuf(rel, newmapbuf);
@@ -441,6 +481,104 @@ found:
return ovflbuf;
}
+/*
+ * _hash_findfreeovflpage()
+ *
+ * Find a free overflow page in the bitmap pages, and return it pinned,
+ * write-locked and initialized, with the bitmap page that has its bit
+ * write-locked in *mapbufp. The bit is not set yet: the caller does that
+ * in its critical section. *bitmap_page_bit is the bit's number within
its
+ * bitmap page, and *bitp the overflow page's bit number. Returns
+ * InvalidBuffer if there is no free page.
+ *
+ * If metalocked, *metapp points to the metapage, which the caller holds
+ * write-locked, and we search all the bitmap pages. Otherwise *metapp is
+ * our cached copy of the metapage, and we search from the bitmap page that
+ * hashm_firstfree is in. A bit beyond the range of overflow pages the
copy
+ * knows of can stand for a page in a splitpoint added since, so we refresh
+ * the copy before using such a bit. Bits for pages that don't exist yet
+ * are set, so a free bit always stands for an existing page.
+ *
+ * Lock order: we lock the metapage only if no bitmap page lock is held.
+ */
+static Buffer
+_hash_findfreeovflpage(Relation rel, Buffer *metabuf, HashMetaPage *metapp,
+ Buffer *mapbufp, uint32
*bitmap_page_bit, uint32 *bitp,
+ bool metalocked)
+{
+ HashMetaPage metap = *metapp;
+ uint32 i;
+
+ i = metalocked ? 0 : metap->hashm_firstfree >> BMPG_SHIFT(metap);
+
+ while (i < metap->hashm_nmaps)
+ {
+ Buffer mapbuf;
+ uint32 *freep;
+ uint32 nwords = metap->hashm_bmsize / sizeof(uint32);
+ uint32 j;
+ bool exclusive = false;
+
+ mapbuf = _hash_getbuf(rel, metap->hashm_mapp[i], HASH_READ,
+ LH_BITMAP_PAGE);
+ freep = HashPageGetBitmap(BufferGetPage(mapbuf));
+
+ for (j = 0; j < nwords; j++)
+ {
+ uint32 bit;
+
+ if (freep[j] == ALL_SET)
+ continue;
+
+ if (!exclusive)
+ {
+ /* lock it exclusively and look at this word
again */
+ LockBuffer(mapbuf, BUFFER_LOCK_UNLOCK);
+ LockBuffer(mapbuf, BUFFER_LOCK_EXCLUSIVE);
+ exclusive = true;
+ if (freep[j] == ALL_SET)
+ continue;
+ }
+
+ bit = (i << BMPG_SHIFT(metap)) + j * BITS_PER_MAP +
+ _hash_firstfreebit(freep[j]);
+
+ if (metalocked &&
+ bit >=
metap->hashm_spares[metap->hashm_ovflpoint])
+ elog(ERROR, "free bit %u past the last overflow
page in hash index \"%s\"",
+ bit, RelationGetRelationName(rel));
+
+ if (!metalocked &&
+ bit >=
metap->hashm_spares[metap->hashm_ovflpoint])
+ {
+ /* refresh our copy of the metapage, and retry
this page */
+ _hash_relbuf(rel, mapbuf);
+ metap = _hash_getcachedmetap(rel, metabuf,
true);
+ *metapp = metap;
+ if (bit >=
metap->hashm_spares[metap->hashm_ovflpoint])
+ elog(ERROR, "free bit %u past the last
overflow page in hash index \"%s\"",
+ bit,
RelationGetRelationName(rel));
+ break;
+ }
+
+ *mapbufp = mapbuf;
+ *bitmap_page_bit = bit & BMPG_MASK(metap);
+ *bitp = bit;
+
+ /* Fetch and init the recycled page */
+ return _hash_getinitbuf(rel, bitno_to_blkno(metap,
bit));
+ }
+
+ if (j < nwords)
+ continue; /* refreshed the
metapage copy; retry page */
+
+ _hash_relbuf(rel, mapbuf);
+ i++;
+ }
+
+ return InvalidBuffer;
+}
+
/*
* _hash_firstfreebit()
*
@@ -495,7 +633,7 @@ _hash_freeovflpage(Relation rel, Buffer bucketbuf, Buffer
ovflbuf,
BufferAccessStrategy bstrategy)
{
HashMetaPage metap;
- Buffer metabuf;
+ Buffer metabuf = InvalidBuffer;
Buffer mapbuf;
BlockNumber ovflblkno;
BlockNumber prevblkno;
@@ -512,8 +650,7 @@ _hash_freeovflpage(Relation rel, Buffer bucketbuf, Buffer
ovflbuf,
Bucket bucket PG_USED_FOR_ASSERTS_ONLY;
Buffer prevbuf = InvalidBuffer;
Buffer nextbuf = InvalidBuffer;
- bool update_metap = false,
- mod_wbuf,
+ bool mod_wbuf,
is_prim_bucket_same_wrt,
is_prev_bucket_same_wrt;
XLogRecPtr recptr;
@@ -554,12 +691,18 @@ _hash_freeovflpage(Relation rel, Buffer bucketbuf, Buffer
ovflbuf,
/* Note: bstrategy is intentionally not used for metapage and bitmap */
- /* Read the metapage so we can determine which bitmap page to use */
- metabuf = _hash_getbuf(rel, HASH_METAPAGE, HASH_READ, LH_META_PAGE);
- metap = HashPageGetMeta(BufferGetPage(metabuf));
-
- /* Identify which bit to set */
- ovflbitno = _hash_ovflblkno_to_bitno(metap, ovflblkno);
+ /*
+ * Determine which bitmap page to use from our cached copy of the
+ * metapage. If the page was added after the copy was taken, refresh
it.
+ * We don't update hashm_firstfree, so we don't lock the metapage; see
+ * "Free Space Management" in the README.
+ */
+ metap = _hash_getcachedmetap(rel, &metabuf, false);
+ if (!_hash_ovflblkno_to_bitno_internal(metap, ovflblkno, &ovflbitno))
+ {
+ metap = _hash_getcachedmetap(rel, &metabuf, true);
+ ovflbitno = _hash_ovflblkno_to_bitno(metap, ovflblkno);
+ }
bitmappage = ovflbitno >> BMPG_SHIFT(metap);
bitmapbit = ovflbitno & BMPG_MASK(metap);
@@ -568,18 +711,12 @@ _hash_freeovflpage(Relation rel, Buffer bucketbuf, Buffer
ovflbuf,
elog(ERROR, "invalid overflow bit number %u", ovflbitno);
blkno = metap->hashm_mapp[bitmappage];
- /* Release metapage lock while we access the bitmap page */
- LockBuffer(metabuf, BUFFER_LOCK_UNLOCK);
-
/* read the bitmap page to clear the bitmap bit */
mapbuf = _hash_getbuf(rel, blkno, HASH_WRITE, LH_BITMAP_PAGE);
mappage = BufferGetPage(mapbuf);
freep = HashPageGetBitmap(mappage);
Assert(ISSET(freep, bitmapbit));
- /* Get write-lock on metapage to update firstfree */
- LockBuffer(metabuf, BUFFER_LOCK_EXCLUSIVE);
-
/* This operation needs to log multiple tuples, prepare WAL for that */
if (RelationNeedsWAL(rel))
XLogEnsureRecordSpace(HASH_XLOG_FREE_OVFL_BUFS, 4 + nitups);
@@ -639,14 +776,6 @@ _hash_freeovflpage(Relation rel, Buffer bucketbuf, Buffer
ovflbuf,
CLRBIT(freep, bitmapbit);
MarkBufferDirty(mapbuf);
- /* if this is now the first free page, update hashm_firstfree */
- if (ovflbitno < metap->hashm_firstfree)
- {
- metap->hashm_firstfree = ovflbitno;
- update_metap = true;
- MarkBufferDirty(metabuf);
- }
-
/* Determine which pages are modified */
is_prim_bucket_same_wrt = (wbuf == bucketbuf);
is_prev_bucket_same_wrt = (wbuf == prevbuf);
@@ -722,12 +851,6 @@ _hash_freeovflpage(Relation rel, Buffer bucketbuf, Buffer
ovflbuf,
XLogRegisterBuffer(5, mapbuf, REGBUF_STANDARD);
XLogRegisterBufData(5, &bitmapbit, sizeof(uint32));
- if (update_metap)
- {
- XLogRegisterBuffer(6, metabuf, REGBUF_STANDARD);
- XLogRegisterBufData(6, &metap->hashm_firstfree,
sizeof(uint32));
- }
-
recptr = XLogInsert(RM_HASH_ID, XLOG_HASH_SQUEEZE_PAGE);
}
else /*
!RelationNeedsWAL(rel) */
@@ -746,9 +869,6 @@ _hash_freeovflpage(Relation rel, Buffer bucketbuf, Buffer
ovflbuf,
PageSetLSN(BufferGetPage(mapbuf), recptr);
- if (update_metap)
- PageSetLSN(BufferGetPage(metabuf), recptr);
-
END_CRIT_SECTION();
/* release previous bucket if it is not same as write bucket */
@@ -762,7 +882,8 @@ _hash_freeovflpage(Relation rel, Buffer bucketbuf, Buffer
ovflbuf,
_hash_relbuf(rel, nextbuf);
_hash_relbuf(rel, mapbuf);
- _hash_relbuf(rel, metabuf);
+ if (BufferIsValid(metabuf))
+ _hash_dropbuf(rel, metabuf);
return nextblkno;
}
diff --git a/src/backend/access/hash/hashpage.c
b/src/backend/access/hash/hashpage.c
index a0ab2528167..429d668cb58 100644
--- a/src/backend/access/hash/hashpage.c
+++ b/src/backend/access/hash/hashpage.c
@@ -38,8 +38,6 @@
#include "utils/injection_point.h"
#include "utils/rel.h"
-static bool _hash_alloc_buckets(Relation rel, BlockNumber firstblock,
- uint32 nblocks);
static void _hash_splitbucket(Relation rel, Buffer metabuf,
Bucket obucket,
Bucket nbucket,
Buffer obuf,
@@ -975,6 +973,8 @@ fail:
* EOF to the end of the splitpoint; this keeps smgr's idea of the EOF in
* sync with ours, so that we don't get complaints from smgr.
*
+ * _hash_addovflpage() uses this too, to add a batch of overflow pages.
+ *
* We do this by writing a page of zeroes at the end of the splitpoint range.
* We expect that the filesystem will ensure that the intervening pages read
* as zeroes too. On many filesystems this "hole" will not be allocated
@@ -991,7 +991,7 @@ fail:
* Returns true if successful, or false if allocation failed due to
* BlockNumber overflow.
*/
-static bool
+bool
_hash_alloc_buckets(Relation rel, BlockNumber firstblock, uint32 nblocks)
{
BlockNumber lastblock;
diff --git a/src/backend/access/rmgrdesc/hashdesc.c
b/src/backend/access/rmgrdesc/hashdesc.c
index 6b410b80638..5c69006d732 100644
--- a/src/backend/access/rmgrdesc/hashdesc.c
+++ b/src/backend/access/rmgrdesc/hashdesc.c
@@ -64,8 +64,9 @@ hash_desc(StringInfo buf, XLogReaderState *record)
{
xl_hash_add_ovfl_page *xlrec =
(xl_hash_add_ovfl_page *) rec;
- appendStringInfo(buf, "bmsize %d, bmpage_found
%c",
- xlrec->bmsize,
(xlrec->bmpage_found) ? 'T' : 'F');
+ appendStringInfo(buf, "bmsize %d, bmpage_found
%c, nadded %u",
+ xlrec->bmsize,
(xlrec->bmpage_found) ? 'T' : 'F',
+ xlrec->nadded);
break;
}
case XLOG_HASH_SPLIT_ALLOCATE_PAGE:
diff --git a/src/include/access/hash.h b/src/include/access/hash.h
index a8702f0e5ea..6b90ec5d98b 100644
--- a/src/include/access/hash.h
+++ b/src/include/access/hash.h
@@ -440,6 +440,8 @@ extern void _hash_init_metabuffer(Buffer buf, double
num_tuples,
RegProcedure
procid, uint16 ffactor, bool initpage);
extern void _hash_pageinit(Page page, Size size);
extern void _hash_expandtable(Relation rel, Buffer metabuf);
+extern bool _hash_alloc_buckets(Relation rel, BlockNumber firstblock,
+ uint32 nblocks);
extern void _hash_finish_split(Relation rel, Buffer metabuf, Buffer obuf,
Bucket obucket,
uint32 maxbucket, uint32 highmask,
uint32 lowmask);
diff --git a/src/include/access/hash_xlog.h b/src/include/access/hash_xlog.h
index af65e5b5ce3..b0ce31cd0ce 100644
--- a/src/include/access/hash_xlog.h
+++ b/src/include/access/hash_xlog.h
@@ -74,13 +74,18 @@ typedef struct xl_hash_insert
*
* Backup Blk 0: newly allocated overflow page
* Backup Blk 1: page before new overflow page in the bucket chain
- * Backup Blk 2: bitmap page
+ * Backup Blk 2: bitmap page. If bmpage_found, data is the bit to set for
+ * the reused page; otherwise data is the first
of the
+ * nadded - 1 bits to clear for the added pages
left free
* Backup Blk 3: new bitmap page
- * Backup Blk 4: metapage
+ * Backup Blk 4: metapage, present only if it was modified (data is
+ * hashm_firstfree)
*/
typedef struct xl_hash_add_ovfl_page
{
uint16 bmsize;
+ uint16 nadded; /* pages added to the overflow
area, if
+ *
!bmpage_found */
bool bmpage_found;
} xl_hash_add_ovfl_page;
@@ -156,7 +161,7 @@ typedef struct xl_hash_move_page_contents
* Backup Blk 3: page previous to the freed overflow page
* Backup Blk 4: page next to the freed overflow page
* Backup Blk 5: bitmap page containing info of freed overflow page
- * Backup Blk 6: meta page
+ * Backup Blk 6: meta page (not written by current servers)
*/
typedef struct xl_hash_squeeze_page
{
diff --git a/src/test/modules/hash/Makefile b/src/test/modules/hash/Makefile
index 8d8b798ebac..7d9302b1d25 100644
--- a/src/test/modules/hash/Makefile
+++ b/src/test/modules/hash/Makefile
@@ -2,7 +2,7 @@
EXTRA_INSTALL = src/test/modules/injection_points contrib/pageinspect
-REGRESS = hash_deferred_count hash_incomplete_splits
+REGRESS = hash_deferred_count hash_incomplete_splits hash_overflow_pages
TAP_TESTS = 1
diff --git a/src/test/modules/hash/expected/hash_overflow_pages.out
b/src/test/modules/hash/expected/hash_overflow_pages.out
new file mode 100644
index 00000000000..e4868f70c02
--- /dev/null
+++ b/src/test/modules/hash/expected/hash_overflow_pages.out
@@ -0,0 +1,108 @@
+-- Test allocation and freeing of hash index overflow pages.
+--
+-- Searching for a free overflow page and freeing one don't lock the
+-- metapage. When there is no free page, the index is extended by a batch
+-- of 64 overflow pages, all but the first left free in the bitmap.
+CREATE EXTENSION pageinspect;
+-- Size the index for 6000 rows, so the rows added below don't split it
+CREATE TABLE hash_ovfl_test (v int4) WITH (autovacuum_enabled = false);
+INSERT INTO hash_ovfl_test SELECT g FROM generate_series(1, 6000) g;
+ANALYZE hash_ovfl_test;
+CREATE INDEX hash_ovfl_index ON hash_ovfl_test USING hash (v);
+-- The pages after the bitmap page are all overflow pages: their type, and
+-- whether their bit is set
+CREATE FUNCTION hash_ovfl_pages(OUT type text, OUT bit_set bool, OUT pages
int8)
+RETURNS SETOF record LANGUAGE sql AS $$
+ SELECT hash_page_type(get_raw_page('hash_ovfl_index', b::int)),
+ (hash_bitmap_info('hash_ovfl_index', b)).bitstatus,
+ count(*)
+ FROM generate_series(
+ (SELECT mapp[1] FROM hash_metapage_info(get_raw_page('hash_ovfl_index',
0))) + 1,
+ pg_relation_size('hash_ovfl_index') / current_setting('block_size')::int
- 1) b
+ GROUP BY 1, 2 ORDER BY 1, 2
+$$;
+CREATE FUNCTION hash_ovfl_meta(OUT maxbucket int8, OUT firstfree int8,
+ OUT ovflpages int8, OUT index_pages int8)
+LANGUAGE sql AS $$
+ SELECT maxbucket, firstfree, spares[ovflpoint + 1],
+ pg_relation_size('hash_ovfl_index') /
current_setting('block_size')::int
+ FROM hash_metapage_info(get_raw_page('hash_ovfl_index', 0))
+$$;
+-- Only the bitmap page counts as an overflow page so far
+SELECT * FROM hash_ovfl_meta();
+ maxbucket | firstfree | ovflpages | index_pages
+-----------+-----------+-----------+-------------
+ 31 | 0 | 1 | 34
+(1 row)
+
+SELECT * FROM hash_ovfl_pages();
+ type | bit_set | pages
+------+---------+-------
+(0 rows)
+
+-- Fill one bucket past its primary page. The first overflow page extends
+-- the index by 64 pages, and the others come from that batch.
+INSERT INTO hash_ovfl_test SELECT 1 FROM generate_series(1, 2000);
+SELECT * FROM hash_ovfl_meta();
+ maxbucket | firstfree | ovflpages | index_pages
+-----------+-----------+-----------+-------------
+ 31 | 2 | 65 | 98
+(1 row)
+
+SELECT * FROM hash_ovfl_pages();
+ type | bit_set | pages
+----------+---------+-------
+ overflow | t | 5
+ unused | f | 59
+(2 rows)
+
+-- Freeing overflow pages clears their bits, and leaves firstfree alone
+DELETE FROM hash_ovfl_test WHERE v = 1;
+VACUUM hash_ovfl_test;
+SELECT * FROM hash_ovfl_meta();
+ maxbucket | firstfree | ovflpages | index_pages
+-----------+-----------+-----------+-------------
+ 31 | 2 | 65 | 98
+(1 row)
+
+SELECT * FROM hash_ovfl_pages();
+ type | bit_set | pages
+--------+---------+-------
+ unused | f | 64
+(1 row)
+
+-- New overflow pages reuse free ones, so the index does not grow
+INSERT INTO hash_ovfl_test SELECT 1 FROM generate_series(1, 1500);
+SELECT * FROM hash_ovfl_meta();
+ maxbucket | firstfree | ovflpages | index_pages
+-----------+-----------+-----------+-------------
+ 31 | 2 | 65 | 98
+(1 row)
+
+SELECT * FROM hash_ovfl_pages();
+ type | bit_set | pages
+----------+---------+-------
+ overflow | t | 4
+ unused | f | 60
+(2 rows)
+
+-- The index still finds every row
+SET enable_seqscan = off;
+SET enable_bitmapscan = off;
+SELECT count(*) FROM hash_ovfl_test WHERE v = 1;
+ count
+-------
+ 1500
+(1 row)
+
+RESET enable_seqscan;
+RESET enable_bitmapscan;
+SELECT count(*) FROM hash_ovfl_test WHERE v = 1;
+ count
+-------
+ 1500
+(1 row)
+
+DROP TABLE hash_ovfl_test;
+DROP FUNCTION hash_ovfl_pages, hash_ovfl_meta;
+DROP EXTENSION pageinspect;
diff --git a/src/test/modules/hash/meson.build
b/src/test/modules/hash/meson.build
index 9b009607396..d46eb5a035e 100644
--- a/src/test/modules/hash/meson.build
+++ b/src/test/modules/hash/meson.build
@@ -12,6 +12,7 @@ tests += {
'sql': [
'hash_deferred_count',
'hash_incomplete_splits',
+ 'hash_overflow_pages',
],
},
'tap': {
diff --git a/src/test/modules/hash/sql/hash_overflow_pages.sql
b/src/test/modules/hash/sql/hash_overflow_pages.sql
new file mode 100644
index 00000000000..553b5aaf5b3
--- /dev/null
+++ b/src/test/modules/hash/sql/hash_overflow_pages.sql
@@ -0,0 +1,65 @@
+-- Test allocation and freeing of hash index overflow pages.
+--
+-- Searching for a free overflow page and freeing one don't lock the
+-- metapage. When there is no free page, the index is extended by a batch
+-- of 64 overflow pages, all but the first left free in the bitmap.
+CREATE EXTENSION pageinspect;
+
+-- Size the index for 6000 rows, so the rows added below don't split it
+CREATE TABLE hash_ovfl_test (v int4) WITH (autovacuum_enabled = false);
+INSERT INTO hash_ovfl_test SELECT g FROM generate_series(1, 6000) g;
+ANALYZE hash_ovfl_test;
+CREATE INDEX hash_ovfl_index ON hash_ovfl_test USING hash (v);
+
+-- The pages after the bitmap page are all overflow pages: their type, and
+-- whether their bit is set
+CREATE FUNCTION hash_ovfl_pages(OUT type text, OUT bit_set bool, OUT pages
int8)
+RETURNS SETOF record LANGUAGE sql AS $$
+ SELECT hash_page_type(get_raw_page('hash_ovfl_index', b::int)),
+ (hash_bitmap_info('hash_ovfl_index', b)).bitstatus,
+ count(*)
+ FROM generate_series(
+ (SELECT mapp[1] FROM hash_metapage_info(get_raw_page('hash_ovfl_index',
0))) + 1,
+ pg_relation_size('hash_ovfl_index') / current_setting('block_size')::int
- 1) b
+ GROUP BY 1, 2 ORDER BY 1, 2
+$$;
+CREATE FUNCTION hash_ovfl_meta(OUT maxbucket int8, OUT firstfree int8,
+ OUT ovflpages int8, OUT index_pages int8)
+LANGUAGE sql AS $$
+ SELECT maxbucket, firstfree, spares[ovflpoint + 1],
+ pg_relation_size('hash_ovfl_index') /
current_setting('block_size')::int
+ FROM hash_metapage_info(get_raw_page('hash_ovfl_index', 0))
+$$;
+
+-- Only the bitmap page counts as an overflow page so far
+SELECT * FROM hash_ovfl_meta();
+SELECT * FROM hash_ovfl_pages();
+
+-- Fill one bucket past its primary page. The first overflow page extends
+-- the index by 64 pages, and the others come from that batch.
+INSERT INTO hash_ovfl_test SELECT 1 FROM generate_series(1, 2000);
+SELECT * FROM hash_ovfl_meta();
+SELECT * FROM hash_ovfl_pages();
+
+-- Freeing overflow pages clears their bits, and leaves firstfree alone
+DELETE FROM hash_ovfl_test WHERE v = 1;
+VACUUM hash_ovfl_test;
+SELECT * FROM hash_ovfl_meta();
+SELECT * FROM hash_ovfl_pages();
+
+-- New overflow pages reuse free ones, so the index does not grow
+INSERT INTO hash_ovfl_test SELECT 1 FROM generate_series(1, 1500);
+SELECT * FROM hash_ovfl_meta();
+SELECT * FROM hash_ovfl_pages();
+
+-- The index still finds every row
+SET enable_seqscan = off;
+SET enable_bitmapscan = off;
+SELECT count(*) FROM hash_ovfl_test WHERE v = 1;
+RESET enable_seqscan;
+RESET enable_bitmapscan;
+SELECT count(*) FROM hash_ovfl_test WHERE v = 1;
+
+DROP TABLE hash_ovfl_test;
+DROP FUNCTION hash_ovfl_pages, hash_ovfl_meta;
+DROP EXTENSION pageinspect;
--
2.50.1
