public inbox for [email protected]
help / color / mirror / Atom feedFrom: Dhruv Aron <[email protected]>
To: [email protected]
Cc: [email protected]
Cc: [email protected] <[email protected]>
Subject: Restructured Shared Buffer Hash Table
Date: Tue, 7 Jul 2026 11:41:47 -0700
Message-ID: <CAAStW3JX_7LcCD1U+89vyMmLreDs0XsBU-JDdFf5PD_Woy1pag@mail.gmail.com> (raw)
Hi,
At Databricks, we’ve found that the existing dynahash table structure is
leaving performance gains on the table when it comes to shared buffer
lookups: the multi-level structure (directory, segment, bucket chain,
freelist) appears excessive for the shared buffers and could be simplified
to boost performance and lower memory overhead. As such, we are proposing a
specialized hash table just for this purpose and would appreciate feedback
on this approach.
To give a brief overview, our new table operates primarily on two arrays,
one for the entries and one for the bucket heads, and it enforces the
invariant that *entries[x]* describes the page in buffer *x*. Each entry
stores only a BufferTag and a ‘next’ index (representing the next entry in
the same bucket chain), with each bucket head only storing a ‘head’ index
(representing the first entry in the bucket chain). At a high-level, the
table essentially creates a logical linked list for each bucket on top of
the flat physical arrays.
The attached patch implements this functionality and passes the existing
regression tests; the buf_table.c functions were modified directly, with
bufmgr.c also changed slightly to prevent a race condition. My testing
(helper script also attached) indicates that all three standard hash table
operations (insert, lookup, and delete) generally execute significantly
faster than the existing PG18 dynahash counterparts:
4 GB
Operation
Average Dynahash Execution Time (ns)
Average New Table Execution Time (ns)
Speedup (Dynahash / New Table)
Lookup
77.33
46.50
1.66x
Insert
111.78
86.33
1.29x
Delete
148.73
104.13
1.43x
16 GB
Operation
Average Dynahash Execution Time (ns)
Average New Table Execution Time (ns)
Speedup (Dynahash / New Table)
Lookup
98.18
83.01
1.18x
Insert
198.58
195.30
1.02x
Delete
279.48
274.77
1.02x
I would like to note, however, that this patch is part of a larger effort
around dynamic shared buffers alongside this patch
<https://www.postgresql.org/message-id/[email protected]...;
and additional internal functionality to dynamically resize this new shared
buffer table, i.e. adding *and* removing the number of buckets and entry
slots without requiring a restart or total table rehash; I believe the
table should be resized to prevent it from consuming a disproportionate
amount of memory (or being too slow) relative to the size of the shared
buffers, and I would be happy to create a follow-up patch demonstrating
those resizing capabilities. That being said, I would like to emphasize
that I think the changes here offer enough standalone benefits to merit
their own patch.
Thanks,
Dhruv Aron
Attachments:
[application/octet-stream] restructured_shared_buffer_table.patch (10.4K, ../CAAStW3JX_7LcCD1U+89vyMmLreDs0XsBU-JDdFf5PD_Woy1pag@mail.gmail.com/3-restructured_shared_buffer_table.patch)
download | inline diff:
diff --git a/src/backend/storage/buffer/buf_table.c b/src/backend/storage/buffer/buf_table.c
index 347bf267d73..570957e6357 100644
--- a/src/backend/storage/buffer/buf_table.c
+++ b/src/backend/storage/buffer/buf_table.c
@@ -3,6 +3,27 @@
* buf_table.c
* routines for mapping BufferTags to buffer indexes.
*
+ * The shared buffer mapping table is a flat, index-linked hash table (an
+ * open-chaining replacement for the former dynahash-based table). It is made
+ * of two shared-memory arrays:
+ *
+ * buckets[num_buckets] - one chain head per hash bucket
+ * entries[NBuffers] - one entry per buffer, indexed by buf_id
+ *
+ * Each buffer slot i permanently owns entry slot i, so no freelist is needed:
+ * bufmgr always removes a buffer's old mapping (BufTableDelete, called from
+ * InvalidateVictimBuffer) before inserting a new tag for that same buf_id (see
+ * GetVictimBuffer / BufferAlloc in bufmgr.c). Empty entry slots are marked by
+ * tag.blockNum == P_NEW; chains are linked by int index and terminated by
+ * BUF_TABLE_CHAIN_END.
+ *
+ * num_buckets is a power of two and a multiple of NUM_BUFFER_PARTITIONS, so the
+ * bucket index (hashcode % num_buckets) shares its low bits with the partition
+ * index (hashcode % NUM_BUFFER_PARTITIONS). Every tag that maps to a given
+ * bucket therefore maps to a single partition, and the caller's BufMappingLock
+ * fully serializes each chain -- the same guarantee the dynahash table relied
+ * on.
+ *
* Note: the routines in this file do no locking of their own. The caller
* must hold a suitable lock on the appropriate BufMappingLock, as specified
* in the comments. We can't do the locking inside these functions because
@@ -21,56 +42,114 @@
*/
#include "postgres.h"
+#include "common/hashfn.h"
+#include "miscadmin.h"
+#include "port/pg_bitutils.h"
#include "storage/buf_internals.h"
+#include "storage/bufmgr.h"
+#include "storage/shmem.h"
#include "storage/subsystems.h"
+#define BUF_TABLE_CHAIN_END (-1)
+
+/* bucket for buffer lookup hashtable */
+typedef struct
+{
+ int head; /* head of hash chain, or BUF_TABLE_CHAIN_END */
+} BufferLookupBucket;
+
/* entry for buffer lookup hashtable */
typedef struct
{
- BufferTag key; /* Tag of a disk page */
- int id; /* Associated buffer ID */
+ BufferTag tag; /* Tag of a disk page, or P_NEW if empty */
+ int next; /* next entry in hash chain */
} BufferLookupEnt;
-static HTAB *SharedBufHash;
+/* bucket and entry arrays for buffer lookup hashtable (in shared memory) */
+static BufferLookupBucket *buckets;
+static BufferLookupEnt *entries;
+
+/* number of hash buckets; power of two and multiple of NUM_BUFFER_PARTITIONS */
+static int num_buckets;
static void BufTableShmemRequest(void *arg);
+static void BufTableShmemInit(void *arg);
+static void BufTableShmemAttach(void *arg);
const ShmemCallbacks BufTableShmemCallbacks = {
.request_fn = BufTableShmemRequest,
- /* no special initialization needed, the hash table will start empty */
+ .init_fn = BufTableShmemInit,
+ .attach_fn = BufTableShmemAttach,
};
/*
- * Register shmem hash table for mapping buffers.
- * size is the desired hash table size (possibly more than NBuffers)
+ * Number of hash buckets for the current NBuffers.
+ *
+ * Must be a power of two (so hashcode % num_buckets == hashcode & (num_buckets
+ * - 1)) and a multiple of NUM_BUFFER_PARTITIONS, so that every tag in a bucket
+ * maps to a single buffer partition (see file header).
+ */
+static inline int
+BufTableNumBuckets(void)
+{
+ return Max(NUM_BUFFER_PARTITIONS, pg_nextpower2_32(NBuffers));
+}
+
+/*
+ * Register shared memory arrays for mapping buffers.
*/
void
BufTableShmemRequest(void *arg)
{
- int size;
+ num_buckets = BufTableNumBuckets();
+ Assert(num_buckets % NUM_BUFFER_PARTITIONS == 0);
- /*
- * Request the shared buffer lookup hashtable.
- *
- * Since we can't tolerate running out of lookup table entries, we must be
- * sure to specify an adequate table size here. The maximum steady-state
- * usage is of course NBuffers entries, but BufferAlloc() tries to insert
- * a new entry before deleting the old. In principle this could be
- * happening in each partition concurrently, so we could need as many as
- * NBuffers + NUM_BUFFER_PARTITIONS entries.
- */
- size = NBuffers + NUM_BUFFER_PARTITIONS;
-
- ShmemRequestHash(.name = "Shared Buffer Lookup Table",
- .nelems = size,
- .ptr = &SharedBufHash,
- .hash_info.keysize = sizeof(BufferTag),
- .hash_info.entrysize = sizeof(BufferLookupEnt),
- .hash_info.num_partitions = NUM_BUFFER_PARTITIONS,
- .hash_flags = HASH_ELEM | HASH_BLOBS | HASH_PARTITION | HASH_FIXED_SIZE,
+ ShmemRequestStruct(.name = "Shared Buffer Lookup Buckets",
+ .size = (Size) num_buckets * sizeof(BufferLookupBucket),
+ .ptr = (void **) &buckets,
+ );
+
+ ShmemRequestStruct(.name = "Shared Buffer Lookup Entries",
+ .size = (Size) NBuffers * sizeof(BufferLookupEnt),
+ .ptr = (void **) &entries,
);
}
+/*
+ * Initialize the shared buffer lookup table. Called once during shared-memory
+ * initialization (in the postmaster, or in a standalone backend).
+ *
+ * Shared memory is zeroed, but zero is a valid buf_id and block 0 is a valid
+ * block number, so we must explicitly mark every bucket empty
+ * (BUF_TABLE_CHAIN_END) and every entry empty (tag.blockNum == P_NEW).
+ */
+void
+BufTableShmemInit(void *arg)
+{
+ num_buckets = BufTableNumBuckets();
+
+ for (int i = 0; i < num_buckets; i++)
+ buckets[i].head = BUF_TABLE_CHAIN_END;
+
+ for (int i = 0; i < NBuffers; i++)
+ {
+ entries[i].tag.blockNum = P_NEW;
+ entries[i].next = BUF_TABLE_CHAIN_END;
+ }
+}
+
+/*
+ * Per-backend attach. The buckets/entries pointers are restored by the shmem
+ * framework, but num_buckets is a process-local scalar that must be recomputed
+ * in each backend. Forked children inherit it, but EXEC_BACKEND children run
+ * only the attach callback, so set it here too.
+ */
+void
+BufTableShmemAttach(void *arg)
+{
+ num_buckets = BufTableNumBuckets();
+}
+
/*
* BufTableHashCode
* Compute the hash code associated with a BufferTag
@@ -83,7 +162,7 @@ BufTableShmemRequest(void *arg)
uint32
BufTableHashCode(BufferTag *tagPtr)
{
- return get_hash_value(SharedBufHash, tagPtr);
+ return tag_hash(tagPtr, sizeof(BufferTag));
}
/*
@@ -95,19 +174,15 @@ BufTableHashCode(BufferTag *tagPtr)
int
BufTableLookup(BufferTag *tagPtr, uint32 hashcode)
{
- BufferLookupEnt *result;
-
- result = (BufferLookupEnt *)
- hash_search_with_hash_value(SharedBufHash,
- tagPtr,
- hashcode,
- HASH_FIND,
- NULL);
-
- if (!result)
- return -1;
+ int id = buckets[hashcode % num_buckets].head;
- return result->id;
+ while (id != BUF_TABLE_CHAIN_END)
+ {
+ if (BufferTagsEqual(&entries[id].tag, tagPtr))
+ return id;
+ id = entries[id].next;
+ }
+ return -1;
}
/*
@@ -123,23 +198,35 @@ BufTableLookup(BufferTag *tagPtr, uint32 hashcode)
int
BufTableInsert(BufferTag *tagPtr, uint32 hashcode, int buf_id)
{
- BufferLookupEnt *result;
- bool found;
+ int bucket_id = hashcode % num_buckets;
+ int head = buckets[bucket_id].head;
+ int id = head;
- Assert(buf_id >= 0); /* -1 is reserved for not-in-table */
+ Assert(buf_id >= 0 && buf_id < NBuffers);
Assert(tagPtr->blockNum != P_NEW); /* invalid tag */
- result = (BufferLookupEnt *)
- hash_search_with_hash_value(SharedBufHash,
- tagPtr,
- hashcode,
- HASH_ENTER,
- &found);
+ /* If the tag is already in the chain, surface the existing buf_id. */
+ while (id != BUF_TABLE_CHAIN_END)
+ {
+ if (BufferTagsEqual(&entries[id].tag, tagPtr))
+ return id;
+ id = entries[id].next;
+ }
- if (found) /* found something already in the table */
- return result->id;
+ /*
+ * Not present. entry[buf_id] must be empty: bufmgr always deletes a
+ * buffer's old mapping before inserting a new tag for that buf_id.
+ */
+ Assert(entries[buf_id].tag.blockNum == P_NEW);
- result->id = buf_id;
+ /*
+ * Link entry[buf_id] at the chain head, keeping the prior head as its
+ * successor. (Use the saved `head`, not `id`, which the loop above has
+ * advanced to BUF_TABLE_CHAIN_END.)
+ */
+ entries[buf_id].tag = *tagPtr;
+ entries[buf_id].next = head;
+ buckets[bucket_id].head = buf_id;
return -1;
}
@@ -153,15 +240,32 @@ BufTableInsert(BufferTag *tagPtr, uint32 hashcode, int buf_id)
void
BufTableDelete(BufferTag *tagPtr, uint32 hashcode)
{
- BufferLookupEnt *result;
+ int bucket_id = hashcode % num_buckets;
+ int prev = BUF_TABLE_CHAIN_END;
+ int id = buckets[bucket_id].head;
- result = (BufferLookupEnt *)
- hash_search_with_hash_value(SharedBufHash,
- tagPtr,
- hashcode,
- HASH_REMOVE,
- NULL);
+ while (id != BUF_TABLE_CHAIN_END)
+ {
+ if (BufferTagsEqual(&entries[id].tag, tagPtr))
+ {
+ /* unlink from the chain */
+ if (prev == BUF_TABLE_CHAIN_END)
+ buckets[bucket_id].head = entries[id].next;
+ else
+ entries[prev].next = entries[id].next;
+ /* mark the entry empty */
+ entries[id].tag.blockNum = P_NEW;
+ entries[id].next = BUF_TABLE_CHAIN_END;
+ return;
+ }
+ prev = id;
+ id = entries[id].next;
+ }
- if (!result) /* shouldn't happen */
- elog(ERROR, "shared buffer hash table corrupted");
+ /*
+ * Entry not in table. Callers never double-delete (deletion is gated by
+ * BM_TAG_VALID on the buffer header), so this indicates corruption.
+ */
+ Assert(false);
+ elog(ERROR, "shared buffer hash table corrupted");
}
diff --git a/src/backend/storage/buffer/bufmgr.c b/src/backend/storage/buffer/bufmgr.c
index d6c0cc1f6d4..f173eaf765b 100644
--- a/src/backend/storage/buffer/bufmgr.c
+++ b/src/backend/storage/buffer/bufmgr.c
@@ -2441,17 +2441,21 @@ retry:
oldFlags = buf_state & BUF_FLAG_MASK;
ClearBufferTag(&buf->tag);
- UnlockBufHdrExt(buf, buf_state,
- 0,
- BUF_FLAG_MASK | BUF_USAGECOUNT_MASK,
- 0);
-
/*
* Remove the buffer from the lookup hashtable, if it was in there.
*/
if (oldFlags & BM_TAG_VALID)
BufTableDelete(&oldTag, oldHash);
+ /* Unlock buffer header after the entry is deleted to avoid a race condition:
+ * If unlocked prior, a concurrent GetVictimBuffer() could insert a new entry
+ * for the same buffer and overwrite the entry slot. Then, the BufTableDelete()
+ * would be unable to find the entry and would corrupt the hashtable. */
+ UnlockBufHdrExt(buf, buf_state,
+ 0,
+ BUF_FLAG_MASK | BUF_USAGECOUNT_MASK,
+ 0);
+
/*
* Done with mapping lock.
*/
[application/octet-stream] test.diff (24.3K, ../CAAStW3JX_7LcCD1U+89vyMmLreDs0XsBU-JDdFf5PD_Woy1pag@mail.gmail.com/4-test.diff)
download | inline diff:
diff --git a/buftable_bench/.gitignore b/buftable_bench/.gitignore
new file mode 100644
index 00000000000..2988e8c3b49
--- /dev/null
+++ b/buftable_bench/.gitignore
@@ -0,0 +1,2 @@
+_work/
+.builds/
diff --git a/buftable_bench/README.md b/buftable_bench/README.md
new file mode 100644
index 00000000000..b3b92a38a35
--- /dev/null
+++ b/buftable_bench/README.md
@@ -0,0 +1,57 @@
+# buftable_bench
+
+A micro-benchmark of PostgreSQL's shared **buffer mapping table** ops. The SQL function
+`buftable_bench_probe(n, rounds, random)` calls `BufTableLookup` / `BufTableInsert` /
+`BufTableDelete` **directly** on the live shared table and **bulk-times** each op (one rdtsc pair ÷
+N) — no `ReadBuffer`, no page copy, no per-op rdtsc. It operates on free buffer slots + synthetic
+tags and restores the table afterward.
+
+The whole thing is one self-contained test-module extension — the **only change vs stock
+PostgreSQL**. x86_64 only (uses `rdtsc`).
+
+## Files
+
+```
+buftable_bench/
+├── run.sh # build the current branch (release) + run + print numbers
+├── instrumentation/buftable_bench_module/ # the extension (drop into src/test/modules/)
+│ ├── buftable_bench.c # buftable_bench_probe() — the probe
+│ ├── buftable_bench--1.0.sql # CREATE FUNCTION buftable_bench_probe(...)
+│ ├── buftable_bench.control
+│ ├── Makefile
+│ └── meson.build
+├── scripts/
+│ ├── bench_probe.sh <prefix> <size> # run the probe against one explicit install
+│ └── compare_probe.sh [sizes...] # flat-vs-dynahash A/B (needs two builds)
+└── results/
+ ├── probe_summary.txt # recorded A/B numbers
+ └── compare_probe.results.txt
+```
+(`.builds/` and `_work/` are local build/scratch caches — gitignored.)
+
+## How to run
+
+**The current branch** (builds this repo's `HEAD` as a release, caches it per commit, runs, and
+prints the per-op numbers):
+
+```sh
+buftable_bench/run.sh # default shared_buffers = 1GB
+buftable_bench/run.sh 256MB 4GB 16GB # any sizes
+```
+First run for a commit builds (~30 s–few min); later runs are instant. Output (to stdout), labeled
+`branch@commit`:
+```
+-- shared_buffers=1GB (n=104857 keys) --
+ op | avg_ns | count
+ insert | 18.555 | 1048570
+ lookup_hit | 23.064 | 1048570
+ lookup_miss | 21.902 | 1048570
+ delete | 24.569 | 1048570
+```
+Knobs: `BUFTABLE_PROBE_ROUNDS` (default 10); `PG_CONFIG=/path/bin/pg_config` to skip the build and
+use an existing install. (`run.sh` is **single-arm** — it measures the current branch only.)
+
+**Flat-vs-dynahash A/B** (optional; needs two installs at `~/pg-bench/{flat,dyna}`):
+```sh
+buftable_bench/scripts/compare_probe.sh 256MB 4GB 16GB
+```
diff --git a/buftable_bench/instrumentation/buftable_bench_module/Makefile b/buftable_bench/instrumentation/buftable_bench_module/Makefile
new file mode 100644
index 00000000000..75ca30c79fe
--- /dev/null
+++ b/buftable_bench/instrumentation/buftable_bench_module/Makefile
@@ -0,0 +1,22 @@
+# src/test/modules/buftable_bench/Makefile
+
+PGFILEDESC = "buftable_bench - rdtsc micro-benchmark for the buffer mapping table"
+
+MODULE_big = buftable_bench
+OBJS = \
+ $(WIN32RES) \
+ buftable_bench.o
+
+EXTENSION = buftable_bench
+DATA = buftable_bench--1.0.sql
+
+ifdef USE_PGXS
+PG_CONFIG = pg_config
+PGXS := $(shell $(PG_CONFIG) --pgxs)
+include $(PGXS)
+else
+subdir = src/test/modules/buftable_bench
+top_builddir = ../../../..
+include $(top_builddir)/src/Makefile.global
+include $(top_srcdir)/contrib/contrib-global.mk
+endif
diff --git a/buftable_bench/instrumentation/buftable_bench_module/buftable_bench--1.0.sql b/buftable_bench/instrumentation/buftable_bench_module/buftable_bench--1.0.sql
new file mode 100644
index 00000000000..f81c0e60d5d
--- /dev/null
+++ b/buftable_bench/instrumentation/buftable_bench_module/buftable_bench--1.0.sql
@@ -0,0 +1,17 @@
+/* src/test/modules/buftable_bench/buftable_bench--1.0.sql */
+
+-- complain if script is sourced in psql, rather than via CREATE EXTENSION
+\echo Use "CREATE EXTENSION buftable_bench" to load this file. \quit
+
+CREATE FUNCTION buftable_bench_probe(
+ IN n int8,
+ IN rounds int8 DEFAULT 1,
+ IN random bool DEFAULT true,
+ OUT op text,
+ OUT avg_ns float8,
+ OUT count int8)
+RETURNS SETOF record
+AS 'MODULE_PATHNAME', 'buftable_bench_probe'
+LANGUAGE C;
+
+REVOKE ALL ON FUNCTION buftable_bench_probe(int8, int8, bool) FROM PUBLIC;
diff --git a/buftable_bench/instrumentation/buftable_bench_module/buftable_bench.c b/buftable_bench/instrumentation/buftable_bench_module/buftable_bench.c
new file mode 100644
index 00000000000..67d09b3579c
--- /dev/null
+++ b/buftable_bench/instrumentation/buftable_bench_module/buftable_bench.c
@@ -0,0 +1,255 @@
+/*-------------------------------------------------------------------------
+ *
+ * buftable_bench.c
+ * Pollution-free in-place benchmark of the shared buffer mapping table.
+ *
+ * Throwaway micro-benchmark module (NOT for upstream). One SQL function,
+ * buftable_bench_probe(n, rounds), times lookup (hit+miss), insert, and delete
+ * by calling BufTable{Insert,Lookup,Delete} DIRECTLY on the real shared table
+ * -- no ReadBuffer, no 8 KB page copy, no per-op rdtsc. Each op's loop is
+ * bulk-timed with a single rdtsc pair, so the measurement isn't polluted by
+ * page-copy cache traffic or per-op timer overhead.
+ *
+ * It works against STOCK PostgreSQL: it only calls the existing public
+ * BufTable* / BufTableHashCode functions, so no core changes are needed -- the
+ * two arms being compared are just two stock builds (flat table vs dynahash).
+ *
+ * Insert/delete mutate the live table, so we only use FREE buffer slots (their
+ * mapping entry is guaranteed empty) and restore the table afterward.
+ *
+ * x86_64 only (rdtsc).
+ *
+ * IDENTIFICATION
+ * src/test/modules/buftable_bench/buftable_bench.c
+ *
+ *-------------------------------------------------------------------------
+ */
+#include "postgres.h"
+
+#include "fmgr.h"
+#include "funcapi.h"
+#include "miscadmin.h"
+#include "portability/instr_time.h"
+#include "storage/buf_internals.h"
+#include "storage/bufmgr.h"
+#include "utils/builtins.h"
+#include "utils/tuplestore.h"
+
+PG_MODULE_MAGIC;
+
+PG_FUNCTION_INFO_V1(buftable_bench_probe);
+
+#define BUFTABLE_BENCH_PROBE_COLS 3
+
+/* synthetic relfilenodes for bench tags — unlikely to collide with anything real */
+#define BENCH_SPC_OID 0xB0B0
+#define BENCH_DB_OID 0xB1B1
+#define BENCH_REL_PRESENT ((RelFileNumber) 0x7E570001)
+#define BENCH_REL_ABSENT ((RelFileNumber) 0x7E570002)
+
+static inline uint64
+bench_rdtsc(void)
+{
+ uint32 lo,
+ hi;
+
+ __asm__ __volatile__("rdtsc" : "=a"(lo), "=d"(hi)::"memory");
+ return ((uint64) hi << 32) | lo;
+}
+
+/* cycles per nanosecond, measured over a ~2 ms wall-clock window */
+static double
+probe_calibrate(void)
+{
+ instr_time w0,
+ w1,
+ d;
+ uint64 c0,
+ c1;
+ double ns;
+
+ INSTR_TIME_SET_CURRENT(w0);
+ c0 = bench_rdtsc();
+ do
+ {
+ INSTR_TIME_SET_CURRENT(w1);
+ d = w1;
+ INSTR_TIME_SUBTRACT(d, w0);
+ } while (INSTR_TIME_GET_DOUBLE(d) < 0.002);
+ c1 = bench_rdtsc();
+ ns = INSTR_TIME_GET_DOUBLE(d) * 1e9;
+ return (ns > 0.0) ? (double) (c1 - c0) / ns : 0.0;
+}
+
+/*
+ * buftable_bench_probe(n, rounds) -> SETOF (op text, avg_ns float8, count int8)
+ *
+ * Rows: insert, lookup_hit, lookup_miss, delete. See file header.
+ */
+Datum
+buftable_bench_probe(PG_FUNCTION_ARGS)
+{
+ int64 n = PG_GETARG_INT64(0);
+ int64 rounds = PG_ARGISNULL(1) ? 1 : PG_GETARG_INT64(1);
+ bool randomize = PG_ARGISNULL(2) ? true : PG_GETARG_BOOL(2);
+ ReturnSetInfo *rsinfo = (ReturnSetInfo *) fcinfo->resultinfo;
+ int *bufids;
+ int64 *ord;
+ BufferTag *ptag,
+ *atag;
+ uint32 *phash,
+ *ahash;
+ int64 nfree = 0;
+ double cyc_per_ns,
+ denom;
+ uint64 ins = 0,
+ lkh = 0,
+ lkm = 0,
+ del = 0;
+ volatile int64 sink = 0;
+ RelFileLocator rp = {.spcOid = BENCH_SPC_OID,.dbOid = BENCH_DB_OID,.relNumber = BENCH_REL_PRESENT};
+ RelFileLocator ra = {.spcOid = BENCH_SPC_OID,.dbOid = BENCH_DB_OID,.relNumber = BENCH_REL_ABSENT};
+ const char *names[4] = {"insert", "lookup_hit", "lookup_miss", "delete"};
+ double avg[4];
+
+ if (n <= 0 || rounds <= 0)
+ ereport(ERROR, (errmsg("n and rounds must be positive")));
+
+ InitMaterializedSRF(fcinfo, 0);
+
+ /* collect up to n FREE buffer slots (mapping entry guaranteed empty) */
+ bufids = palloc(sizeof(int) * n);
+ for (int i = 0; i < NBuffers && nfree < n; i++)
+ {
+ BufferDesc *desc = GetBufferDescriptor(i);
+ uint64 state = pg_atomic_read_u64(&desc->state);
+
+ if (!(state & BM_TAG_VALID))
+ bufids[nfree++] = i;
+ }
+ n = nfree;
+ if (n == 0)
+ ereport(ERROR, (errmsg("no free buffers to probe with")));
+
+ /* build present + absent tags and their hashes */
+ ptag = palloc(sizeof(BufferTag) * n);
+ atag = palloc(sizeof(BufferTag) * n);
+ phash = palloc(sizeof(uint32) * n);
+ ahash = palloc(sizeof(uint32) * n);
+ for (int64 j = 0; j < n; j++)
+ {
+ InitBufferTag(&ptag[j], &rp, MAIN_FORKNUM, (BlockNumber) j);
+ InitBufferTag(&atag[j], &ra, MAIN_FORKNUM, (BlockNumber) j);
+ phash[j] = BufTableHashCode(&ptag[j]);
+ ahash[j] = BufTableHashCode(&atag[j]);
+ }
+
+ /*
+ * Iteration order over the keys: identity (sequential) or a Fisher-Yates
+ * shuffle (random). A shuffled order makes the timed loops visit keys in
+ * an order uncorrelated with where their entries/elements live, so BOTH
+ * arms' entry/element access is random (not just the bucket access, which
+ * the hash already scatters). Done once in setup (untimed).
+ */
+ ord = palloc(sizeof(int64) * n);
+ for (int64 i = 0; i < n; i++)
+ ord[i] = i;
+ if (randomize)
+ {
+ uint64 rng = 0x9E3779B97F4A7C15ULL; /* fixed seed -> reproducible */
+
+ for (int64 i = n - 1; i > 0; i--)
+ {
+ int64 k,
+ tmp;
+
+ rng ^= rng << 13;
+ rng ^= rng >> 7;
+ rng ^= rng << 17;
+ k = (int64) (rng % (uint64) (i + 1));
+ tmp = ord[i];
+ ord[i] = ord[k];
+ ord[k] = tmp;
+ }
+ }
+
+ cyc_per_ns = probe_calibrate();
+
+ PG_TRY();
+ {
+ for (int64 r = 0; r < rounds; r++)
+ {
+ uint64 t0,
+ t1;
+
+ t0 = bench_rdtsc();
+ for (int64 i = 0; i < n; i++)
+ {
+ int64 j = ord[i];
+
+ BufTableInsert(&ptag[j], phash[j], bufids[j]);
+ }
+ t1 = bench_rdtsc();
+ ins += t1 - t0;
+
+ t0 = bench_rdtsc();
+ for (int64 i = 0; i < n; i++)
+ {
+ int64 j = ord[i];
+
+ sink += BufTableLookup(&ptag[j], phash[j]);
+ }
+ t1 = bench_rdtsc();
+ lkh += t1 - t0;
+
+ t0 = bench_rdtsc();
+ for (int64 i = 0; i < n; i++)
+ {
+ int64 j = ord[i];
+
+ sink += BufTableLookup(&atag[j], ahash[j]);
+ }
+ t1 = bench_rdtsc();
+ lkm += t1 - t0;
+
+ t0 = bench_rdtsc();
+ for (int64 i = 0; i < n; i++)
+ {
+ int64 j = ord[i];
+
+ BufTableDelete(&ptag[j], phash[j]);
+ }
+ t1 = bench_rdtsc();
+ del += t1 - t0;
+ }
+ }
+ PG_CATCH();
+ {
+ /* best-effort restore: remove any present tag still mapped */
+ for (int64 j = 0; j < n; j++)
+ if (BufTableLookup(&ptag[j], phash[j]) >= 0)
+ BufTableDelete(&ptag[j], phash[j]);
+ PG_RE_THROW();
+ }
+ PG_END_TRY();
+
+ denom = (double) n * (double) rounds * cyc_per_ns;
+ avg[0] = ins / denom;
+ avg[1] = lkh / denom;
+ avg[2] = lkm / denom;
+ avg[3] = del / denom;
+
+ for (int i = 0; i < 4; i++)
+ {
+ Datum values[BUFTABLE_BENCH_PROBE_COLS];
+ bool nulls[BUFTABLE_BENCH_PROBE_COLS] = {0};
+
+ values[0] = CStringGetTextDatum(names[i]);
+ values[1] = Float8GetDatum(avg[i]);
+ values[2] = Int64GetDatum(n * rounds);
+ tuplestore_putvalues(rsinfo->setResult, rsinfo->setDesc, values, nulls);
+ }
+
+ (void) sink;
+ return (Datum) 0;
+}
diff --git a/buftable_bench/instrumentation/buftable_bench_module/buftable_bench.control b/buftable_bench/instrumentation/buftable_bench_module/buftable_bench.control
new file mode 100644
index 00000000000..aae6cb1810f
--- /dev/null
+++ b/buftable_bench/instrumentation/buftable_bench_module/buftable_bench.control
@@ -0,0 +1,4 @@
+comment = 'rdtsc micro-benchmark for the shared buffer mapping table'
+default_version = '1.0'
+module_pathname = '$libdir/buftable_bench'
+relocatable = true
diff --git a/buftable_bench/instrumentation/buftable_bench_module/meson.build b/buftable_bench/instrumentation/buftable_bench_module/meson.build
new file mode 100644
index 00000000000..752773841b2
--- /dev/null
+++ b/buftable_bench/instrumentation/buftable_bench_module/meson.build
@@ -0,0 +1,22 @@
+# Copyright (c) 2024-2026, PostgreSQL Global Development Group
+
+buftable_bench_sources = files(
+ 'buftable_bench.c',
+)
+
+if host_system == 'windows'
+ buftable_bench_sources += rc_lib_gen.process(win32ver_rc, extra_args: [
+ '--NAME', 'buftable_bench',
+ '--FILEDESC', 'buftable_bench - rdtsc micro-benchmark for the buffer mapping table',])
+endif
+
+buftable_bench = shared_module('buftable_bench',
+ buftable_bench_sources,
+ kwargs: pg_test_mod_args,
+)
+test_install_libs += buftable_bench
+
+test_install_data += files(
+ 'buftable_bench.control',
+ 'buftable_bench--1.0.sql',
+)
diff --git a/buftable_bench/results/compare_probe.results.txt b/buftable_bench/results/compare_probe.results.txt
new file mode 100644
index 00000000000..c55903132b8
--- /dev/null
+++ b/buftable_bench/results/compare_probe.results.txt
@@ -0,0 +1,24 @@
+RESULT dyna 256MB insert 28.995 262140
+RESULT dyna 256MB lookup_hit 21.134 262140
+RESULT dyna 256MB lookup_miss 21.257 262140
+RESULT dyna 256MB delete 21.798 262140
+RESULT flat 256MB insert 13.245 262140
+RESULT flat 256MB lookup_hit 16.222 262140
+RESULT flat 256MB lookup_miss 17.498 262140
+RESULT flat 256MB delete 17.805 262140
+RESULT dyna 4GB insert 66.845 4194300
+RESULT dyna 4GB lookup_hit 49.673 4194300
+RESULT dyna 4GB lookup_miss 39.825 4194300
+RESULT dyna 4GB delete 56.704 4194300
+RESULT flat 4GB insert 30.506 4194300
+RESULT flat 4GB lookup_hit 31.717 4194300
+RESULT flat 4GB lookup_miss 28.786 4194300
+RESULT flat 4GB delete 34.971 4194300
+RESULT dyna 16GB insert 104.300 16777210
+RESULT dyna 16GB lookup_hit 82.074 16777210
+RESULT dyna 16GB lookup_miss 62.069 16777210
+RESULT dyna 16GB delete 88.639 16777210
+RESULT flat 16GB insert 55.068 16777210
+RESULT flat 16GB lookup_hit 62.942 16777210
+RESULT flat 16GB lookup_miss 47.260 16777210
+RESULT flat 16GB delete 69.308 16777210
diff --git a/buftable_bench/results/probe_summary.txt b/buftable_bench/results/probe_summary.txt
new file mode 100644
index 00000000000..a6ac9ba855d
--- /dev/null
+++ b/buftable_bench/results/probe_summary.txt
@@ -0,0 +1,29 @@
+# Pollution-free in-place A/B of the REAL shared buffer mapping table.
+# buftable_bench_probe(n, rounds, random): direct BufTable{Insert,Lookup,Delete}
+# calls, bulk-timed (one rdtsc pair per phase), NO ReadBuffer/page-copy, NO
+# per-op rdtsc. random=true (DEFAULT): keys visited in a shuffled order so the
+# bucket AND entry/element accesses are random for both arms.
+# speedup = dynahash/flat (>1 = flat faster). n ~ 0.8*NBuffers, rounds=10.
+#
+# === RANDOM access (default) ===
+# sb op dynahash_ns flat_ns speedup
+# 256MB insert 28.99 13.25 2.19x
+# 256MB lookup_hit 21.13 16.22 1.30x
+# 256MB lookup_miss 21.26 17.50 1.21x
+# 256MB delete 21.80 17.81 1.22x
+# 4GB insert 66.85 30.51 2.19x
+# 4GB lookup_hit 49.67 31.72 1.57x
+# 4GB lookup_miss 39.83 28.79 1.38x
+# 4GB delete 56.70 34.97 1.62x
+# 16GB insert 104.30 55.07 1.89x
+# 16GB lookup_hit 82.07 62.94 1.30x
+# 16GB lookup_miss 62.07 47.26 1.31x
+# 16GB delete 88.64 69.31 1.28x
+#
+# Flat is FASTER on EVERY op at EVERY size (1.2-2.2x). Random access raises
+# absolute ns and compresses the ratio vs sequential (a common-mode key-fetch
+# cost, equal for both arms) -- the more conservative, realistic number.
+#
+# For reference, the earlier SEQUENTIAL order (random=false) gave larger ratios:
+# insert 2.4/2.8/3.5x, lookup_hit 1.6/1.7/2.3x, lookup_miss 1.3/1.3/1.7x,
+# delete 1.4/1.6/2.2x @256MB/4GB/16GB (entry/element access was prefetch-friendly).
diff --git a/buftable_bench/run.sh b/buftable_bench/run.sh
new file mode 100755
index 00000000000..5ac38801863
--- /dev/null
+++ b/buftable_bench/run.sh
@@ -0,0 +1,97 @@
+#!/usr/bin/env bash
+#
+# run.sh [size ...]
+#
+# Build the CURRENTLY CHECKED-OUT BRANCH of this repo (its HEAD) as a release,
+# then run the buffer-mapping-table probe and print the per-op numbers for it.
+# Single arm (just this branch's buf_table.c) — for the flat-vs-dynahash A/B
+# use scripts/compare_probe.sh.
+#
+# The build is cached per commit under buftable_bench/.builds/<commit>, so the
+# first run for a commit takes a few minutes and later runs are instant.
+# It exports the committed tree (git archive) into a temp dir to build, so your
+# working checkout is never touched.
+#
+# Env: PG_CONFIG (use this prebuilt install instead of building),
+# BUFTABLE_PROBE_ROUNDS (default 10), BUFTABLE_BENCH_WORK.
+set -euo pipefail
+
+HERE="$(cd "$(dirname "${BASH_SOURCE[0]}")" && pwd)"
+MODSRC="$HERE/instrumentation/buftable_bench_module"
+WORK="${BUFTABLE_BENCH_WORK:-$HERE/_work}"; mkdir -p "$WORK"
+ROUNDS="${BUFTABLE_PROBE_ROUNDS:-10}"
+SIZES="${*:-1GB}"
+
+repo="$(git -C "$HERE" rev-parse --show-toplevel)"
+commit="$(git -C "$repo" rev-parse --short HEAD)"
+branch="$(git -C "$repo" rev-parse --abbrev-ref HEAD)"
+label="$branch@$commit"
+
+# ---- locate or build a release install of the current HEAD ------------------
+if [[ -n "${PG_CONFIG:-}" ]]; then
+ BIN="$("$PG_CONFIG" --bindir)"
+ echo "==> using PG_CONFIG build: $("$PG_CONFIG" --version) [$BIN]" >&2
+else
+ prefix="$HERE/.builds/$commit"
+ if [[ -x "$prefix/bin/pg_config" ]] && \
+ [[ -e "$("$prefix/bin/pg_config" --pkglibdir)/buftable_bench.so" ]]; then
+ echo "==> reusing cached release build of $label [$prefix]" >&2
+ else
+ echo "==> building $label as release (first run for this commit, ~2-4 min)..." >&2
+ src="$(mktemp -d "$WORK/src.$commit.XXXX")"
+ git -C "$repo" archive HEAD | tar -x -C "$src"
+ mkdir -p "$src/src/test/modules/buftable_bench"
+ cp "$MODSRC"/* "$src/src/test/modules/buftable_bench"/
+ (
+ cd "$src"
+ ./configure --prefix="$prefix" --without-icu --without-zlib --without-readline >/dev/null
+ make -s -j"$(nproc)" install >/dev/null
+ make -s -C src/test/modules/buftable_bench install >/dev/null
+ ) || { echo "build failed; see $src" >&2; exit 1; }
+ rm -rf "$src"
+ echo "==> built $label" >&2
+ fi
+ BIN="$prefix/bin"
+fi
+
+# ---- run the probe per size -------------------------------------------------
+size_to_bytes() {
+ local s="${1^^}"
+ case "$s" in
+ *GB) echo $(( ${s%GB} * 1024 * 1024 * 1024 ));;
+ *MB) echo $(( ${s%MB} * 1024 * 1024 ));;
+ *KB) echo $(( ${s%KB} * 1024 ));;
+ *) echo "$s";;
+ esac
+}
+
+echo
+echo "===== buftable_bench: $label (random access, rounds=$ROUNDS) ====="
+for SIZE in $SIZES; do
+ DATADIR="$(mktemp -d "$WORK/pgdata.${SIZE}.XXXX")"
+ SOCKDIR="$(mktemp -d /tmp/pgb.XXXXXX)"
+ N="$(awk -v b="$(size_to_bytes "$SIZE")" 'BEGIN{printf "%d", 0.8*b/8192}')"
+
+ "$BIN/initdb" -D "$DATADIR" --no-sync -A trust >/dev/null 2>&1
+ cat >> "$DATADIR/postgresql.conf" <<CONF
+shared_buffers = '$SIZE'
+jit = off
+autovacuum = off
+fsync = off
+bgwriter_lru_maxpages = 0
+listen_addresses = ''
+unix_socket_directories = '$SOCKDIR'
+CONF
+ "$BIN/pg_ctl" -D "$DATADIR" -l "$DATADIR/log" -w start >/dev/null
+
+ echo "-- shared_buffers=$SIZE (n=$N keys) --"
+ "$BIN/psql" -h "$SOCKDIR" -d postgres -q -P pager=off \
+ -c "CREATE EXTENSION buftable_bench;" \
+ -c "SELECT op, round(avg_ns::numeric,3) AS avg_ns, count
+ FROM buftable_bench_probe($N, $ROUNDS)
+ ORDER BY array_position(ARRAY['insert','lookup_hit','lookup_miss','delete'], op);"
+
+ "$BIN/pg_ctl" -D "$DATADIR" -m immediate stop >/dev/null 2>&1 || true
+ rm -rf "$DATADIR" "$SOCKDIR"
+done
+echo "================================================================"
diff --git a/buftable_bench/scripts/bench_probe.sh b/buftable_bench/scripts/bench_probe.sh
new file mode 100755
index 00000000000..fde619911b2
--- /dev/null
+++ b/buftable_bench/scripts/bench_probe.sh
@@ -0,0 +1,63 @@
+#!/usr/bin/env bash
+#
+# bench_probe.sh <pg_install_prefix> <shared_buffers_size>
+#
+# Pollution-free, in-place benchmark of the REAL shared buffer mapping table for
+# lookup (hit+miss), insert, and delete, via buftable_bench_probe() — which calls
+# BufTable{Insert,Lookup,Delete} directly (no ReadBuffer, no 8 KB page copy, no
+# per-op rdtsc; each op's loop is bulk-timed). No table/prewarm needed: it uses
+# free buffer slots + synthetic tags and restores the table afterward.
+#
+# Emits "RESULT <arm> <size> <op> <avg_ns> <count>".
+# Env: BUFTABLE_PROBE_ROUNDS (default 10).
+set -euo pipefail
+
+PREFIX="${1:?usage: bench_probe.sh <prefix> <size>}"
+SIZE="${2:?usage: bench_probe.sh <prefix> <size>}"
+ROUNDS="${BUFTABLE_PROBE_ROUNDS:-10}"
+ARM="$(basename "$PREFIX")"
+BIN="$PREFIX/bin"
+
+HERE="$(cd "$(dirname "${BASH_SOURCE[0]}")" && pwd)"
+SCRATCH="${BUFTABLE_BENCH_WORK:-$HERE/_work}"; mkdir -p "$SCRATCH"
+DATADIR="$(mktemp -d "$SCRATCH/pgdata.${ARM}.${SIZE}.pr.XXXX")"
+SOCKDIR="$(mktemp -d /tmp/pgb.XXXXXX)"
+LOG="$DATADIR/server.log"
+
+log() { echo "[$ARM $SIZE probe] $*" >&2; }
+cleanup() { "$BIN/pg_ctl" -D "$DATADIR" -m immediate stop >/dev/null 2>&1 || true; rm -rf "$DATADIR" "$SOCKDIR"; }
+trap cleanup EXIT
+
+size_to_bytes() {
+ local s="${1^^}"
+ case "$s" in
+ *GB) echo $(( ${s%GB} * 1024 * 1024 * 1024 ));;
+ *MB) echo $(( ${s%MB} * 1024 * 1024 ));;
+ *) echo "$s";;
+ esac
+}
+SB="$(size_to_bytes "$SIZE")"
+N="$(awk -v b="$SB" 'BEGIN{printf "%d", 0.8*b/8192}')" # ~0.8x NBuffers -> load factor ~1
+
+"$BIN/initdb" -D "$DATADIR" --no-sync -A trust >/dev/null 2>&1
+cat >> "$DATADIR/postgresql.conf" <<CONF
+shared_buffers = '$SIZE'
+jit = off
+autovacuum = off
+fsync = off
+bgwriter_lru_maxpages = 0
+listen_addresses = ''
+unix_socket_directories = '$SOCKDIR'
+CONF
+
+log "start (shared_buffers=$SIZE, n=$N, rounds=$ROUNDS)"
+"$BIN/pg_ctl" -D "$DATADIR" -l "$LOG" -w start >/dev/null
+
+OUT="$("$BIN/psql" -h "$SOCKDIR" -d postgres -q -X -At -F' ' -v ON_ERROR_STOP=1 \
+ -c "CREATE EXTENSION buftable_bench;" \
+ -c "SELECT 'R', op, round(avg_ns::numeric,3), count FROM buftable_bench_probe($N, $ROUNDS);" 2>&1)" || {
+ log "psql failed:"; echo "$OUT" >&2; exit 1;
+}
+
+echo "$OUT" | awk -v arm="$ARM" -v sz="$SIZE" '$1=="R"{printf "RESULT %s %s %s %s %s\n", arm, sz, $2, $3, $4}'
+log "done"
diff --git a/buftable_bench/scripts/compare_probe.sh b/buftable_bench/scripts/compare_probe.sh
new file mode 100755
index 00000000000..fe98a8ab149
--- /dev/null
+++ b/buftable_bench/scripts/compare_probe.sh
@@ -0,0 +1,44 @@
+#!/usr/bin/env bash
+#
+# compare_probe.sh [size ...]
+#
+# Pollution-free in-place A/B of the shared buffer mapping table for all three
+# ops (insert / lookup_hit / lookup_miss / delete), via buftable_bench_probe().
+# Prints, per size, dynahash vs flat avg_ns and speedup = dynahash/flat (>1 =
+# flat faster). Sizes default "256MB 4GB 16GB" or $BUFTABLE_CAPI_SIZES or args.
+set -euo pipefail
+
+HERE="$(cd "$(dirname "${BASH_SOURCE[0]}")" && pwd)"
+BENCH="$HERE/bench_probe.sh"
+FLAT=/home/dhruv.aron/pg-bench/flat
+DYNA=/home/dhruv.aron/pg-bench/dyna
+SCRATCH="${BUFTABLE_BENCH_WORK:-$HERE/_work}"; mkdir -p "$SCRATCH"
+RESULTS="$SCRATCH/compare_probe.results.txt"; : > "$RESULTS"
+
+if [[ $# -gt 0 ]]; then SIZES="$*"; else SIZES="${BUFTABLE_CAPI_SIZES:-256MB 4GB 16GB}"; fi
+
+for size in $SIZES; do
+ for prefix in "$DYNA" "$FLAT"; do
+ echo ">>> $(basename "$prefix") @ $size" >&2
+ bash "$BENCH" "$prefix" "$size" | grep '^RESULT ' >> "$RESULTS"
+ done
+done
+
+echo
+echo "===== pollution-free direct-probe A/B (real shared table) ====="
+awk '
+{ arm=$2; size=$3; op=$4; v[size,op,arm]=$5; cnt[size,op,arm]=$6;
+ if(!(size in seen)){seen[size]=1; order[++ni]=size} }
+END{
+ split("insert lookup_hit lookup_miss delete", ops, " ");
+ for(i=1;i<=ni;i++){ s=order[i];
+ printf "\n=== shared_buffers = %s (samples/op %s) ===\n", s, cnt[s,"insert","flat"];
+ printf "%-12s %12s %12s %14s\n","op","dynahash ns","flat ns","speedup(dh/ft)";
+ for(j=1;j<=4;j++){ o=ops[j];
+ dh=v[s,o,"dyna"]; ft=v[s,o,"flat"];
+ if(dh==""||ft==""){ printf "%-12s %12s %12s %14s\n",o,(dh==""?"-":dh),(ft==""?"-":ft),"n/a"; continue }
+ printf "%-12s %12.3f %12.3f %13.2fx\n", o, dh, ft, (ft>0?dh/ft:0);
+ }
+ }
+}' "$RESULTS"
+echo "==============================================================="
view thread (5+ messages) latest in thread
reply
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: [email protected]
Cc: [email protected], [email protected], [email protected]
Subject: Re: Restructured Shared Buffer Hash Table
In-Reply-To: <CAAStW3JX_7LcCD1U+89vyMmLreDs0XsBU-JDdFf5PD_Woy1pag@mail.gmail.com>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox