Horton

Re: Improve eviction algorithm in ReorderBuffer

Jeff Davis <pgsql@j-davis.com>

View thread View on postgr.es
From: Jeff Davis <pgsql@j-davis.com>
To: Michael Paquier <michael@paquier.xyz>
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:16:53Z
Lists: pgsql-hackers 
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?

That's a reasonable conclusion. Also consider commits b840508644 and
bcb14f4abc.

I had tried to come up with a narrower fix, and I think it's already
been implemented here in approach 2:

https://www.postgresql.org/message-id/CAD21AoAtf12e9Z9NLBuaO1GjHMMo16_8R-yBu9Q9jrk2QLqMEA%40mail.gmail.com

but it does feel wrong to introduce an unnecessary hash table in 17
when we know it's not the right solution.

Regards,
	Jeff Davis

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.