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
</messages/by-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