Re: Improve eviction algorithm in ReorderBuffer

On Sun, Dec 17, 2023 at 11:40 AM Amit Kapila <amit.kapila16@gmail.com> wrote:
>
> 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.

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, the second one maintains other transactions
consuming more than or equal to 5% of logical_decoding_work_mem, and
the third one maintains other transactions consuming more than 0 and
less than 5% of logical_decoding_work_mem.

Regards,

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