Re: Improve eviction algorithm in ReorderBuffer

On Thu, Apr 11, 2024 at 10:46 AM Hayato Kuroda (Fujitsu)
<kuroda.hayato@fujitsu.com> wrote:
>
> Dear Heikki,
>
> I also prototyped the idea, which has almost the same shape.
> I attached just in case, but we may not have to see.
>
> Few comments based on the experiment.

Thank you for reviewing the patch. I didn't include the following
suggestions since firstly I wanted to just fix binaryheap part while
keeping other parts. If we need these changes, we can do them in
separate commits as fixes.

>
> ```
> +       /* txn_heap is ordered by transaction size */
> +       buffer->txn_heap = pairingheap_allocate(ReorderBufferTXNSizeCompare, NULL);
> ```
>
> I think the pairing heap should be in the same MemoryContext with the buffer.
> Can we add MemoryContextSwithTo()?

The pairingheap_allocate() allocates a tiny amount of memory for
pairingheap and its memory usage doesn't grow even when adding more
data. And since it's allocated in logical decoding context its
lifetime is also fine. So I'm not sure it's worth including it in
rb->context for better memory accountability.

>
> ```
> +               /* Update the max-heap */
> +               if (oldsize != 0)
> +                       pairingheap_remove(rb->txn_heap, &txn->txn_node);
> +               pairingheap_add(rb->txn_heap, &txn->txn_node);
> ...
> +               /* Update the max-heap */
> +               pairingheap_remove(rb->txn_heap, &txn->txn_node);
> +               if (txn->size != 0)
> +                       pairingheap_add(rb->txn_heap, &txn->txn_node);
> ```
>
> Since the number of stored transactions does not affect to the insert operation, we may able
> to add the node while creating ReorederBufferTXN and remove while cleaning up it. This can
> reduce branches in ReorderBufferChangeMemoryUpdate().

I think it also means that we need to remove the entry while cleaning
up even if it doesn't have any changes, which is done in O(log n). I
feel the current approach that we don't store transactions with size 0
in the heap is better and I'm not sure that reducing these branches
really contributes to the performance improvements..


Regards,

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