Re: Restructured Shared Buffer Hash Table

+Andres Freund <andres(at)anarazel(dot)de>, I quote you below

Hi Dhruv,

On 07/07/2026 21:41, Dhruv Aron wrote:
> I would like to emphasize that I think the changes
> here offer enough standalone benefits to merit their own patch.

Agreed, I am looking forward to the patch.

LOCKING

Heikki Linnakangas hlinnaka(at)iki(dot)fi wrote at Jul 7, 2026, 8:14 PM
> 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.

Is that paraphrasing storage/buffer/README?

* Each buffer header contains a spinlock that must be taken when examining
or changing fields of that buffer header. This allows operations such as
ReleaseBuffer to make local state changes without taking any system-wide
lock. We use a spinlock, not an LWLock, since there are no cases where
the lock needs to be held for more than a few instructions.

The problem with long locks is that it will keep other processes busy during
contention, but since this is locking a single buffer, contention should be
unlikely, and thus the effect should be small.

DELETION OPTIMISATION OPPORTUNITY

On 07/07/2026 21:41, Dhruv Aron wrote:
> it enforces the invariant that *entries[x]* describes the page in buffer
*x*.

so this leads to two potential optimisations

The first being using the buffer id to delete.
void
- BufTableDelete(BufferTag *tagPtr, uint32 hashcode)
+ BufferTableDeleteId(BufferTa , uint32 hashcode)
while(id != BUF_TABLE_CHAIN_END)
- if (BufferTagsEqual(&entries[id].tag, tagPtr))
+ if (id == del_id))

The other would be to use a doubly linked list, increasing the entry
memory footprint from 24 to 28 bytes, the deletion would require
no iteration.

+ if(entries[id].prev != BUF_TABLE_CHAIN_END)
+ entries[entries[id].prev].next = entries[id].next
+ else buckets[bucket].head = entries[id].next

MEMORY USAGE ANALYSIS

On Jul 7, 2026 at 10:12 PM Heikki Linnakangas wrote
> unpatched master, with shared_buffers='128 MB':
> name | off | size | allocated_size
> Shared Buffer Lookup Table | 141607040 | 926000 | 926108
> With this patch:
> Shared Buffer Lookup Buckets | 141607040 | 65536 | 65644
> Shared Buffer Lookup Entries | 141672576 | 393216 | 393216
>
> So the new hash table takes much less memory. That's nice because you
> can then fit more in CPU caches.

with 128MB the master uses 0x8000 buckets, patched
uses 0x4000. Because 128MB = 0x4000 * 8192 master
passes .nelems = 0x4000 + NUM_BUFFER_PARTITIONS
increasing to the next power of two 0x8000.

+static inline int
+BufTableNumBuckets(void)
+{
+ return Max(NUM_BUFFER_PARTITIONS, pg_nextpower2_32(NBuffers));
+}
+ num_buckets = BufTableNumBuckets();
- 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,Element size on 64-bit
machines

This slight misalignment might have played against the patched
speed. Because for the master a power of two is at ~0.5 entry/bucket
rate, and the patched version is at ~1 entry/bucket.

BENCHMARK

+ int64 j = ord[i];
+ BufTableInsert(&ptag[j], phash[j], bufids[j]);
...
+ sink += BufTableLookup(&ptag[j], phash[j]);
...
+ sink += BufTableLookup(&atag[j], ahash[j]);
...
+ BufTableDelete(&ptag[j], phash[j]);

The benchmark covers a very particular case. The indices
are shuffled but insert, lookup and delete, all use the same permutation.

As a consequence of this. The lookup_hit test is always going to find
each entry before its next entry in the bucket. The delete will always
find the entry being deleted at bucket head. For lookup_miss it doesn't
matter. It might seem hypocritical of me as I did exactly that when I
worked on buffer pinning [1]. But in that case I was simulating
prefetching, where pins follow roughly a fifo (or fpfu) order.

MEMORY USAGE ANALYSIS

+ elementSize = MAXALIGN(sizeof(HASHELEMENT)) + MAXALIGN(hctl->entrysize);
With .hash_info.keysize = sizeof(BufferTag) = 20
And MAXALIGN defined as the minimum multiple of 8 not smaller than the
input.
it was MAXALIGN(12) + MAXALIGN(20) = 16 + 24 = 40
assuming buckets = entries we would have another 8 bytes per bucket head
and 8 bytes per segment, assuming buckets = 2 * entries we would have
something like
56 + 2*8/256, not too far from allocated size.

128MB = 16384 entries, 926108 / 16384 = 56.52

Entries in the dynhash account for up to
dir 0x8000 / 0x100 pointers = 1024
bucket heads 0x8000 pointers = 262144
and for the entries 0x4000 * 40 = 655360
918528 bytes close enough from the number quoted at the top

In the patched version
0x4000 * 4 for indices = 65536
0x4000 * 24 for entries = 39216

THE REPLACED CODE

Here I try to summarise what is being removed, it makes
a lot of sense that it is faster.

1. external call hash_search_with_hash_value
2. freelist_idx: always computed, not used for lookup,
pointer dereference+branch
(((hctl)->num_partitions != 0) ? (hashvalue) % 32 : 0)
3. if (action ~ HASH_ENTER_*)
branch and unlikely split
4. hash_initial_lookup:
4.1 calc_bucket: a branch and one or two pointer dereferences.
4.2 hashp->dir[bucket >> 8].?[bucket & 255]: two pointer dereferences
and a branch (null check)
5. match function pointer, and keysize pointer references.
6 loop
5.1 currBucket->hashvalue == hashvalue possibly skipping 5.2
5.2 call match function by pointer (new version uses inline
BufferTagsEqual).
6. update *foundPtr
7. switch (multiple branches?)
8. for insert/delete again pointer dereference + branch twice
around SpinLock(Acquire/Release)

The only bit of performance that was dropped is checking the hash code
before the tag comparison. That could be a win if we think of comparing
32-bit then branching, successively.
But if it is implemented with vector optimisation, the BufferTagEqual
alone will probably be faster than trying to branch over it, not to mention
the need to store the hash.

[1]
https://www.postgresql.org/message-id/flat/rfjyce5hmfkp2pbgjaxvmc76zy33kpokigbkwnounxfmz6uyd5%40vt7yxibmfy6n#e91277dae42b6774d8a65f7ac7480fc7

>