Re: Improve eviction algorithm in ReorderBuffer

Amit Kapila <amit.kapila16@gmail.com>

From: Amit Kapila <amit.kapila16@gmail.com>
To: Masahiko Sawada <sawada.mshk@gmail.com>
Cc: Dilip Kumar <dilipbalaut@gmail.com>, PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Date: 2023-12-19T11:02:01Z
Lists: pgsql-hackers
On Tue, Dec 19, 2023 at 8:31 AM Masahiko Sawada <sawada.mshk@gmail.com> wrote:
>
> On Sun, Dec 17, 2023 at 11:40 AM Amit Kapila <amit.kapila16@gmail.com> wrote:
> >
> >
> > The individual transactions shouldn't cross
> > 'logical_decoding_work_mem'. I got a bit confused by your proposal to
> > maintain the lists: "...splitting it into two lists: transactions
> > consuming 5% < and 5% >=  of the memory limit, and checking the 5% >=
> > list preferably.". In the previous sentence, what did you mean by
> > transactions consuming 5% >= of the memory limit? I got the impression
> > that you are saying to maintain them in a separate transaction list
> > which doesn't seems to be the case.
>
> I wanted to mean that there are three lists in total: the first one
> maintain the transactions consuming more than 10% of
> logical_decoding_work_mem,
>

How can we have multiple transactions in the list consuming more than
10% of logical_decoding_work_mem? Shouldn't we perform serialization
before any xact reaches logical_decoding_work_mem?

-- 
With Regards,
Amit Kapila.



Commits

  1. Revert indexed and enlargable binary heap implementation.

  2. Replace binaryheap + index with pairingheap in reorderbuffer.c

  3. Improve eviction algorithm in ReorderBuffer using max-heap for many subtransactions.

  4. Add functions to binaryheap for efficient key removal and update.

  5. Make binaryheap enlargeable.