Horton

Re: Improve eviction algorithm in ReorderBuffer

Masahiko Sawada <sawada.mshk@gmail.com>

View thread View on postgr.es
From: Masahiko Sawada <sawada.mshk@gmail.com>
To: Jeff Davis <pgsql@j-davis.com>
Cc: Amit Kapila <amit.kapila16@gmail.com>, vignesh C <vignesh21@gmail.com>, Peter Smith <smithpb2250@gmail.com>, Tomas Vondra <tomas.vondra@enterprisedb.com>, "Hayato Kuroda (Fujitsu)" <kuroda.hayato@fujitsu.com>, Shubham Khanna <khannashubham1197@gmail.com>, Dilip Kumar <dilipbalaut@gmail.com>, PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Date: 2024-04-04T08:28:27Z
Lists: pgsql-hackers 
On Thu, Apr 4, 2024 at 1:54 PM Jeff Davis <pgsql@j-davis.com> wrote:
>
> On Thu, 2024-04-04 at 09:31 +0900, Masahiko Sawada wrote:
> > IIUC, with your suggestion, sift_{up|down} needs to update the
> > heap_index field as well. Does it mean that the caller needs to pass
> > the address of heap_index down to sift_{up|down}?
>
> I'm not sure quite how binaryheap should be changed. Bringing the heap
> implementation into reorderbuffer.c would obviously work, but that
> would be more code.

Right.

>  Another option might be to make the API of
> binaryheap look a little more like simplehash, where some #defines
> control optional behavior and can tell the implementation where to find
> fields in the structure.

Interesting idea.

>
> Perhaps it's not worth the effort though, if performance is already
> good enough?

Yeah, it would be better to measure the overhead first. I'll do that.

Regards,

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

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.