Re: Improve eviction algorithm in ReorderBuffer

On Fri, Dec 15, 2023 at 7:10 PM Alvaro Herrera <alvherre(at)alvh(dot)no-ip(dot)org> wrote:
>
> On 2023-Dec-12, Masahiko Sawada wrote:
>
> > To deal with this problem, I initially thought of the idea (a)
> > mentioned in the comment; use a binary heap to maintain the
> > transactions sorted by the amount of changes or the size. But it seems
> > not a good idea to try maintaining all transactions by its size since
> > the size of each transaction could be changed frequently.
>
> Hmm, maybe you can just use binaryheap_add_unordered and just let the
> sizes change, and do binaryheap_build() at the point where the eviction
> is needed.

I assume you mean to add ReorderBufferTXN entries to the binaryheap
and then build it by comparing their sizes (i.e. txn->size). But
ReorderBufferTXN entries are removed and deallocated once the
transaction finished. How can we efficiently remove these entries from
binaryheap? I guess it would be O(n) to find the entry among the
unordered entries, where n is the number of transactions in the
reorderbuffer.

Regards,

--
Masahiko Sawada
Amazon Web Services: https://aws.amazon.com