Thread

1. Restructured Shared Buffer Hash Table

   Dhruv Aron <dhruv.aron@gmail.com> — 2026-07-07T18:41:47Z

   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=WhEbK9VZA@mail.gmail.com>
   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
   

2. Re: Restructured Shared Buffer Hash Table

   Heikki Linnakangas <hlinnaka@iki.fi> — 2026-07-07T19:13:48Z

   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
   
   
   
   

3. Re: Restructured Shared Buffer Hash Table

   Thom Brown <thom@linux.com> — 2026-07-07T21:08:03Z

   On Tue, 7 Jul 2026 at 20:14, Heikki Linnakangas <hlinnaka@iki.fi> 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
   
   
   
   

4. Re: Restructured Shared Buffer Hash Table

   Heikki Linnakangas <hlinnaka@iki.fi> — 2026-07-07T21:12:36Z

   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
   
   
   
   
   

5. Re: Restructured Shared Buffer Hash Table

   Ashutosh Bapat <ashutosh.bapat.oss@gmail.com> — 2026-07-08T03:28:27Z

   On Wed, Jul 8, 2026 at 12:44 AM Heikki Linnakangas <hlinnaka@iki.fi> 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