Re: Improve eviction algorithm in ReorderBuffer

On Fri, Dec 15, 2023 at 11:29 AM Masahiko Sawada <sawada.mshk@gmail.com> wrote:
>
> On Fri, Dec 15, 2023 at 12:37 PM Amit Kapila <amit.kapila16@gmail.com> wrote:
> >
> > On Wed, Dec 13, 2023 at 6:01 AM Masahiko Sawada <sawada.mshk@gmail.com> wrote:
> > >
> >
> > IIUC, you are giving preference to multiple list ideas as compared to
> > (a) because you don't need to adjust the list each time the
> > transaction size changes, is that right?
>
> Right.
>
> >  If so, I think there is a
> > cost to keep that data structure up-to-date but it can help in
> > reducing the number of times we need to serialize.
>
> Yes, there is a trade-off.
>
> What I don't want to do is to keep all transactions ordered since it's
> too costly. The proposed idea uses multiple lists to keep all
> transactions roughly ordered. The maintenance cost would be cheap
> since each list is unordered.
>
> It might be a good idea to have a threshold to switch how to pick the
> largest transaction based on the number of transactions in the
> reorderbuffer. If there are many transactions, we can use the proposed
> algorithm to find a possibly-largest transaction, otherwise use the
> current way.
>

Yeah, that makes sense.

> >
> > >
> > > > 1) A scenario where suppose you have one very large transaction that
> > > > is consuming ~40% of the memory and 5-6 comparatively smaller
> > > > transactions that are just above 10% of the memory limit.  And now for
> > > > coming under the memory limit instead of getting 1 large transaction
> > > > evicted out, we are evicting out multiple times.
> > >
> > > Given the large transaction list will have up to 10 transactions, I
> > > think it's cheap to pick the largest transaction among them. It's O(N)
> > > but N won't be large.
> > >
> > > > 2) Another scenario where all the transactions are under 10% of the
> > > > memory limit but let's say there are some transactions are consuming
> > > > around 8-9% of the memory limit each but those are not very old
> > > > transactions whereas there are certain old transactions which are
> > > > fairly small and consuming under 1% of memory limit and there are many
> > > > such transactions.  So how it would affect if we frequently select
> > > > many of these transactions to come under memory limit instead of
> > > > selecting a couple of large transactions which are consuming 8-9%?
> > >
> > > Yeah, probably we can do something for small transactions (i.e. small
> > > and on-memory transactions). One idea is to pick the largest
> > > transaction among them by iterating over all of them. Given that the
> > > more transactions are evicted, the less transactions the on-memory
> > > transaction list has, unlike the current algorithm, we would still
> > > win. Or we could even split it into several sub-lists in order to
> > > reduce the number of transactions to check. For example, splitting it
> > > into two lists: transactions consuming 5% < and 5% >=  of the memory
> > > limit, and checking the 5% >= list preferably.
> > >
> >
> > Which memory limit are you referring to here? Is it logical_decoding_work_mem?
>
> logical_decoding_work_mem.
>
> >
> > > The cost for
> > > maintaining these lists could increase, though.
> > >
> >
> > Yeah, can't we maintain a single list of all xacts that are consuming
> > equal to or greater than the memory limit? Considering that the memory
> > limit is logical_decoding_work_mem, then I think just picking one
> > transaction to serialize would be sufficient.
>
> IIUC we serialize a transaction when the sum of all transactions'
> memory usage in the reorderbuffer exceeds logical_decoding_work_mem.
> In what cases are multiple transactions consuming equal to or greater
> than the logical_decoding_work_mem?
>

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.

--
With Regards,
Amit Kapila.