Re: Restructured Shared Buffer Hash Table

I am withdrawing my attempt on lock-free buffer mapping.

And I will try to address some of Andres questions.

On Tue, Aug 11, 2026 at 9:50 PM Andres Freund <andres(at)anarazel(dot)de> wrote:

>
> Agreed, it's quite terrible.
>
>
> > 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.
>
> Why did you choose a design that is effectively pointered? Pointered
> conflict
> handling tends to be a good bit slower due to the typically unprefetchable
> accesses. That's also - I suspect at least - part of what's pushing you
> towards having both buckets[] and entries[], which seems like an
> unnecessary
> indirection to me. Although admittedly the partition locking handling
> would
> be more complicated without the separate array.
>

Using pointers makes it easier to move a buffer from one bucket to another.
Having P partitions and N buffers, and no dynamic allocation we would need
to allocate N * P entries, because all the buffers can be mapped into one
partition.
Additionally, I would expect the memory copy to have a noticeable impact.

> I also suspect that it'd be better to store a hash value in the buckets,
> BufferTagsEqual() is decidedly not cheap, and you'll obviously get a lot of
> "false" matches from hashcode % num_buckets that would be much cheaper to
> detect with a stored hash value.
>

In the current implementation that is a modest gain. And that agrees with
theory
If num_buckets = NBuffers, about (1 - 1/e) of the buckets are
is expected to 63%, without hashcode we can expect
5*0.63 + 10*(1 - 0.63) = 6.85 comparisons per entry
with hashcode 6 * 0.63 + 7 * (1 - 0.63) = 6.37 comparisons
lower occupation ratios favours noo hashcode.

On a different implementation where one would read the tag from the
buffer descriptor instead of storing in the buffer mapping, this hash code
would
make more difference.

Additionally, one could store a different hashcode, not the one used to map
on the buckets, because at NBuffers = INT_MAX/2-1, the using the same
32-bit hash code leads to 25% false matches.

> My higher level problems with the current architecture of the buffer
> mapping
> infrastructure are the following:
>
> 1) We need a way to iterate over all buffers for a relation in an efficient
> way
>

A solution for this would be having an additional Map<Relation,
List<Buffer> >
To be conservative the same number of buckets as BufTable

Storage: ~16 bytes per buffer
Insert: 1 hash lookup, 1 list insertion.
Lookup: unchanged
Deletion: 1 list removal (two pointer dereferences, and two pointer updates)

2) I think any buffer mapping lookup datastructure with 20 byte keys is
> going
> to considerably not great for performance.
>

Will we relax the limits, it was proposed to reduce the number of databases.
I think we could reduce the number of tablespaces instead, I think that its
limit is not documented. What I like about 16 is that it could be copied and
compared as 2 x 64-bit, or a single simd vector.

3) We should have efficient ordered lookup, to make things like "are there
> any
> not-present blocks in the next N blocks" cheap. Today we need to do full
> buffer lookups for readahead, which requires us to be very minimal about
> lookahead when having a high cache hit ratio, to avoid performance
> regressions - but that also prevents us from avoiding synchronous
> misses in
> such cases.
>

This is an upgrade from 1, ordered data structures are very powerful, a
red-black
three in javascript works beautifully, but in C the cost of the pointer
lookups is
huge. In postgres world probably one would want an in-memory B-tree (as
everyone
is familiar with that algorithm). Probably pages aligned to cache lines
(currently declared as 128 bytes), reserving a few bytes for prev, parent,
next, and count
we would end up with 28 block numbers per page. Maybe one could use a
special encoding for N..N+k, but I don't have any good insight on how to do
that on fixed
32-bit entries.

> 4) Acquiring a lock for every lookup scales badly on larger machines, even
> if
> the lock itself is not contended, due to the cacheline contention it
> creates

You might be interested in [1]

This is unfortunate. Initially I saw this as a reason for the linked lists
bucket.
I tried a custom design, then I tried to go by the book with a Harris
wait-free
design. The problem is that under buffer reuse and a backend that can sleep
an arbitrarily long while walking the chain. If while one backend holds a
given
buffer, that buffer can be removed and then inserted again, in the same
bucket
with a larger hash code, ending up after of some buffer that were initially
after
it, e.g. if a bucket has a, -b-, c, d, and while a backend walks that list
on b, that
gets deleted and reinserted after c changes to a, c, -b-, d, the backend
holding
-b- doesn't notice that it was deleted.

> 5) The datastructure should benefit from spatial locality
>
> It's much more common for subsequent buffer mapping lookups to look up
> nearby blocks than blocks very far away. But with hash tables, the
> likelihood of finding blocks N and N+1 in the CPU cache is no better
> than
> looking up two entirely independent blocks.
>

How common? How much do you think is there to gain?
Once 3 is implemented this might be doable.
I have seen a lot in this list, when a new idea is proposed, someone will
have
questions about the worst case scenario. And if we apply that to this
feature
I think it is very hard to beat Dhruv's implementation.

The lion share of the gain comes from not using dynhash.

For 1-3), I think we should move towards a two-layer datastructure:
>
>
> a) a mapping from relation+fork to a per-"logical file" datastructure
>
> Keyed by database, tablespace, relfilenode, fork (although the fork
> could be handled differently).
>
> This lookup would be cached somewhere below Relation, so we only would
> need
> to occasionally do it, so the size of the key would not matter for
> performance.
>
> This addresses 1+2.
>

Below relation?

We would have to assign a global identifier to the relation, across all
backends.
So I think that is another hashmap
At a given moment we can have one buffer of each relation, so the lookup
of one single relation would be as complex as the buffer lookup today.

When scanning many buffers of one relation this could help. For one single
buffer it would be about twice as slow.

(there's plenty complexity here, don't get me wrong)
>
Exactly

> b) A block-number keyed lookup datastructure returning buffer IDs
>
> If this datastructure is ordered, it addresses 3).
>
> Due to the small key, something like a radix tree is viable (not a plain
> one, but something like what we have in radixtree.h, with the missing
> optimization from the referenced paper added).
>
> A radix tree would also address 5).
>

OK, a radix tree with blocks of size 16 would have deepth 8, and if it is
sparse
would require ~16x more memory. It might be a win for long sequential scans,
but would be much slower for random access (as mentioned before the hash
table does about 1.6 sequential pointer dereference on average, a 8GB table
here
would do 5)

To address 4) I think we should eventually allow to make lookups in b)
> lock-free, using something like RCU or EBR (arguably a form of RCU). I
> would
> definitely not tackle that at the same time, but I think it's worth
> keeping in
> mind.
>

I missed this suggestion when I tried to do my lock-free implementation.
One thing here is that it would drop the entry[id] => buffer[id] invariant,
but if we can do it lock-free that is totally worth it.

> I'm of a somewhat split mind about improving the efficiency of the current
> design without addressing any of the architectural problems. It's of
> course
> nice to make it faster, but it also takes bandwidth that can't be spent on
> the architectural problems...
>

Dhruv's patch is trivial, and gives a noticeable improvement compared to
the previous
dynhash based algorithm algorithm. The only potential downside is requiring
two
relatively large contiguous blocks of shared memory, one of 24GB and one of
4GB.
Buffer descriptors already allocate a 64GB continuous block at the
shared_buffers
GUC limit.

[1]
https://www.postgresql.org/message-id/flat/CAE8JnxOGU4pT19z6JRVW9W0inS1cXt_pRPpCN0dAdTueo_GVkg(at)mail(dot)gmail(dot)com