Horton

Re: Improve eviction algorithm in ReorderBuffer

Heikki Linnakangas <hlinnaka@iki.fi>

View thread View on postgr.es
From: Heikki Linnakangas <hlinnaka@iki.fi>
To: Masahiko Sawada <sawada.mshk@gmail.com>
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-11T12:55:21Z
Lists: pgsql-hackers 
On 11/04/2024 11:20, Masahiko Sawada wrote:
> 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.

Thank you!

-- 
Heikki Linnakangas
Neon (https://neon.tech)

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.