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: Heikki Linnakangas <hlinnaka@iki.fi>
Cc: Michael Paquier <michael@paquier.xyz>, Jeff Davis <pgsql@j-davis.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>, Amit Kapila <amit.kapila16@gmail.com>
Date: 2024-04-11T08:20:33Z
Lists: pgsql-hackers 
On Thu, Apr 11, 2024 at 11:52 AM Masahiko Sawada <sawada.mshk@gmail.com> wrote:
>
> We can see 2% ~ 3% performance regressions compared to the current
> HEAD, but it's much smaller than I expected. Given that we can make
> the code simple, I think we can go with this direction.

Pushed the patch and reverted binaryheap changes.


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.