Re: Improve eviction algorithm in ReorderBuffer

On Thu, 2024-04-04 at 17:28 +0900, Masahiko Sawada wrote:
> > Perhaps it's not worth the effort though, if performance is already
> > good enough?
>
> Yeah, it would be better to measure the overhead first. I'll do that.

I have some further comments and I believe changes are required for
v17.

An indexed binary heap API requires both a comparator and a hash
function to be specified, and has two different kinds of keys: the heap
key (mutable) and the hash key (immutable). It provides heap methods
and hashtable methods, and keep the two internal structures (heap and
HT) in sync.

The implementation in b840508644 uses the bh_node_type as the hash key,
which is just a Datum, and it just hashes the bytes. I believe the
implicit assumption is that the Datum is a pointer -- I'm not sure how
one would use that API if the Datum were a value. Hashing a pointer
seems strange to me and, while I see why you did it that way, I think
it reflects that the API boundaries are not quite right.

One consequence of using the pointer as the hash key is that you need
to find the pointer first: you can't change or remove elements based on
the transaction ID, you have to get the ReorderBufferTXN pointer by
finding it in another structure, first. Currently, that's being done by
searching ReorderBuffer->by_txn. So we actually have two hash tables
for essentially the same purpose: one with xid as the key, and the
other with the pointer as the key. That makes no sense -- let's have a
proper indexed binary heap to look things up by xid (the internal HT)
or by transaction size (using the internal heap).

I suggest:

* Make a proper indexed binary heap API that accepts a hash function
and provides both heap methods and HT methods that operate based on
values (transaction size and transaction ID, respectively).
* Get rid of ReorderBuffer->by_txn and use the indexed binary heap
instead.

This will be a net simplification in reorderbuffer.c, which is good,
because that file makes use of a *lot* of data strucutres.

Regards
Jeff Davis