On Fri, Dec 15, 2023 at 7:10 PM Alvaro Herrera <alvhe...@alvh.no-ip.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
