Horton

Re: Improve eviction algorithm in ReorderBuffer

Michael Paquier <michael@paquier.xyz>

View thread View on postgr.es
From: Michael Paquier <michael@paquier.xyz>
To: Jeff Davis <pgsql@j-davis.com>
Cc: Heikki Linnakangas <hlinnaka@iki.fi>, Masahiko Sawada <sawada.mshk@gmail.com>, 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-10T04:45:40Z
Lists: pgsql-hackers 
On Tue, Apr 09, 2024 at 09:16:53PM -0700, Jeff Davis wrote:
> On Wed, 2024-04-10 at 12:13 +0900, Michael Paquier wrote:
>> Wouldn't the best way forward be to revert
>> 5bec1d6bc5e3 and revisit the whole in v18?
> 
> Also consider commits b840508644 and bcb14f4abc.

Indeed.  These are also linked.
--
Michael

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.