public inbox for [email protected]
help / color / mirror / Atom feedRestructured Shared Buffer Hash Table
5+ messages / 4 participants
[nested] [flat]
* Restructured Shared Buffer Hash Table
@ 2026-07-07 18:41 Dhruv Aron <[email protected]>
2026-07-07 19:13 ` Re: Restructured Shared Buffer Hash Table Heikki Linnakangas <[email protected]>
0 siblings, 1 reply; 5+ messages in thread
From: Dhruv Aron @ 2026-07-07 18:41 UTC (permalink / raw)
To: pgsql-hackers; +Cc: [email protected]; [email protected] <[email protected]>
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 "==============================================================="
^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: Restructured Shared Buffer Hash Table
2026-07-07 18:41 Restructured Shared Buffer Hash Table Dhruv Aron <[email protected]>
@ 2026-07-07 19:13 ` Heikki Linnakangas <[email protected]>
2026-07-07 21:08 ` Re: Restructured Shared Buffer Hash Table Thom Brown <[email protected]>
2026-07-08 03:28 ` Re: Restructured Shared Buffer Hash Table Ashutosh Bapat <[email protected]>
0 siblings, 2 replies; 5+ messages in thread
From: Heikki Linnakangas @ 2026-07-07 19:13 UTC (permalink / raw)
To: Dhruv Aron <[email protected]>; pgsql-hackers; +Cc: [email protected]
On 07/07/2026 21:41, Dhruv Aron wrote:
> 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.
Yeah, the dynahash has features that we just don't need in the buffer
lookup table...
The indirection with the directory is actually unnecessary for all the
shared memory hash tables, since none of them can be resized. I've
wondered if we should try to eliminate that from dynahash for all shmem
hash tables. But the buffer lookup table is very performance-critical,
so if there are any performance gains to be had, it's indeed probably
worthwhile to have a separate implementation just for it.
> bufmgr.c also changed slightly to prevent a race condition.
Hmm, we're now holding the buffer header lock much longer than before,
in InvalidateBuffer(). It's a spinlock, it really should not be held for
more than a few instructions. BufTableDelete() is very fast in the new
implementation, but still. Could we perhaps do some of
BufTableDelete()'s work ahead of time, before we acquire the buffer
header lock? Or maybe it's not a problem, in which case some kind of a
worst case scenario benchmark to show that would be nice. Maybe test how
it behaves when you have a lot of hash collisions, I think that'd make
BufTableDelete() more expensive.
> 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:
Nice!
I wonder how big the impact is with real world workloads. I've certainly
seen the buffer table lookups consume a fair share of CPU time, so I'd
assume that it shows up.
Another data point:
unpatched master, with shared_buffers='128 MB':
postgres=# select * from pg_shmem_allocations where name like 'Shared
Buffer%' order by name ;
name | off | size | allocated_size
----------------------------+-----------+--------+----------------
Shared Buffer Lookup Table | 141607040 | 926000 | 926108
(1 row)
With this patch:
postgres=# select * from pg_shmem_allocations where name like 'Shared
Buffer%' order by name ;
name | off | size | allocated_size
------------------------------+-----------+--------+----------------
Shared Buffer Lookup Buckets | 141607040 | 65536 | 65644
Shared Buffer Lookup Entries | 141672576 | 393216 | 393216
(2 rows)
So the new hash table takes much less memory. That's nice because you
can then fit more in CPU caches.
- Heikki
^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: Restructured Shared Buffer Hash Table
2026-07-07 18:41 Restructured Shared Buffer Hash Table Dhruv Aron <[email protected]>
2026-07-07 19:13 ` Re: Restructured Shared Buffer Hash Table Heikki Linnakangas <[email protected]>
@ 2026-07-07 21:08 ` Thom Brown <[email protected]>
2026-07-07 21:12 ` Re: Restructured Shared Buffer Hash Table Heikki Linnakangas <[email protected]>
1 sibling, 1 reply; 5+ messages in thread
From: Thom Brown @ 2026-07-07 21:08 UTC (permalink / raw)
To: Heikki Linnakangas <[email protected]>; +Cc: Dhruv Aron <[email protected]>; pgsql-hackers; [email protected]
On Tue, 7 Jul 2026 at 20:14, Heikki Linnakangas <[email protected]> wrote:
>
> On 07/07/2026 21:41, Dhruv Aron wrote:
> > 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.
>
> Yeah, the dynahash has features that we just don't need in the buffer
> lookup table...
>
> The indirection with the directory is actually unnecessary for all the
> shared memory hash tables, since none of them can be resized. I've
> wondered if we should try to eliminate that from dynahash for all shmem
> hash tables. But the buffer lookup table is very performance-critical,
> so if there are any performance gains to be had, it's indeed probably
> worthwhile to have a separate implementation just for it.
>
> > bufmgr.c also changed slightly to prevent a race condition.
>
> Hmm, we're now holding the buffer header lock much longer than before,
> in InvalidateBuffer(). It's a spinlock, it really should not be held for
> more than a few instructions. BufTableDelete() is very fast in the new
> implementation, but still. Could we perhaps do some of
> BufTableDelete()'s work ahead of time, before we acquire the buffer
> header lock? Or maybe it's not a problem, in which case some kind of a
> worst case scenario benchmark to show that would be nice. Maybe test how
> it behaves when you have a lot of hash collisions, I think that'd make
> BufTableDelete() more expensive.
>
> > 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:
>
> Nice!
>
> I wonder how big the impact is with real world workloads. I've certainly
> seen the buffer table lookups consume a fair share of CPU time, so I'd
> assume that it shows up.
>
>
> Another data point:
>
> unpatched master, with shared_buffers='128 MB':
>
> postgres=# select * from pg_shmem_allocations where name like 'Shared
> Buffer%' order by name ;
> name | off | size | allocated_size
> ----------------------------+-----------+--------+----------------
> Shared Buffer Lookup Table | 141607040 | 926000 | 926108
> (1 row)
>
> With this patch:
>
> postgres=# select * from pg_shmem_allocations where name like 'Shared
> Buffer%' order by name ;
> name | off | size | allocated_size
> ------------------------------+-----------+--------+----------------
> Shared Buffer Lookup Buckets | 141607040 | 65536 | 65644
> Shared Buffer Lookup Entries | 141672576 | 393216 | 393216
> (2 rows)
>
> So the new hash table takes much less memory. That's nice because you
> can then fit more in CPU caches.
Where did this thread come from? I can't see any conversation beyond
this single email, and as such, can't see any patch either.
Thom
^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: Restructured Shared Buffer Hash Table
2026-07-07 18:41 Restructured Shared Buffer Hash Table Dhruv Aron <[email protected]>
2026-07-07 19:13 ` Re: Restructured Shared Buffer Hash Table Heikki Linnakangas <[email protected]>
2026-07-07 21:08 ` Re: Restructured Shared Buffer Hash Table Thom Brown <[email protected]>
@ 2026-07-07 21:12 ` Heikki Linnakangas <[email protected]>
0 siblings, 0 replies; 5+ messages in thread
From: Heikki Linnakangas @ 2026-07-07 21:12 UTC (permalink / raw)
To: Thom Brown <[email protected]>; +Cc: Dhruv Aron <[email protected]>; pgsql-hackers; [email protected]
On 08/07/2026 00:08, Thom Brown wrote:
> Where did this thread come from? I can't see any conversation beyond
> this single email, and as such, can't see any patch either.
Huh, maybe it got stuck in moderation? Dhruv CC'd me directly, but
you're right, I don't see it in the archives yet.
- Heikki
^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: Restructured Shared Buffer Hash Table
2026-07-07 18:41 Restructured Shared Buffer Hash Table Dhruv Aron <[email protected]>
2026-07-07 19:13 ` Re: Restructured Shared Buffer Hash Table Heikki Linnakangas <[email protected]>
@ 2026-07-08 03:28 ` Ashutosh Bapat <[email protected]>
1 sibling, 0 replies; 5+ messages in thread
From: Ashutosh Bapat @ 2026-07-08 03:28 UTC (permalink / raw)
To: Heikki Linnakangas <[email protected]>; +Cc: Dhruv Aron <[email protected]>; pgsql-hackers; [email protected]
On Wed, Jul 8, 2026 at 12:44 AM Heikki Linnakangas <[email protected]> wrote:
>
> On 07/07/2026 21:41, Dhruv Aron wrote:
> > 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.
>
> Yeah, the dynahash has features that we just don't need in the buffer
> lookup table...
>
> The indirection with the directory is actually unnecessary for all the
> shared memory hash tables, since none of them can be resized. I've
> wondered if we should try to eliminate that from dynahash for all shmem
> hash tables. But the buffer lookup table is very performance-critical,
> so if there are any performance gains to be had, it's indeed probably
> worthwhile to have a separate implementation just for it.
For very large buffer pools, the buffer lookup table spans multiple
memory pages. With buffer resizing capability it will be good to be
able to resize the buffer lookup table as well. Right now the patch
does not resize buffer look up table because of its memory layout and
complexity involved in that operation. If we are using a different
data structure for buffer lookup, it will be good to consider ease of
resizing as well.
--
Best Wishes,
Ashutosh Bapat
^ permalink raw reply [nested|flat] 5+ messages in thread
end of thread, other threads:[~2026-07-08 03:28 UTC | newest]
Thread overview: 5+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2026-07-07 18:41 Restructured Shared Buffer Hash Table Dhruv Aron <[email protected]>
2026-07-07 19:13 ` Heikki Linnakangas <[email protected]>
2026-07-07 21:08 ` Thom Brown <[email protected]>
2026-07-07 21:12 ` Heikki Linnakangas <[email protected]>
2026-07-08 03:28 ` Ashutosh Bapat <[email protected]>
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox