Subject: Restructured Shared Buffer Hash Table

From: Dhruv Aron <[email-masked]>
Date: Tue, 7 Jul 2026 11:41:47 -0700

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/CAM1e6U5XDwKYZo6Jj3yD3xpCB4qkhRSQn8upauHt=[email-masked]>
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

---

From: Heikki Linnakangas <[email-masked]>
Date: Tue, 7 Jul 2026 22:13:48 +0300

On 07/07/2026 21:41, Dhruv Aron wrote:
> 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

---

From: Thom Brown <[email-masked]>
Date: Tue, 7 Jul 2026 22:08:03 +0100

>              name            |    off    |  size  | allocated_size

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

---

From: Heikki Linnakangas <[email-masked]>
Date: Wed, 8 Jul 2026 00:12:36 +0300

> 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

---

From: Ashutosh Bapat <[email-masked]>
Date: Wed, 8 Jul 2026 08:58:27 +0530

> 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