Restructured Shared Buffer Hash Table

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