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: Masahiko Sawada <sawada.mshk@gmail.com>, Amit Kapila <amit.kapila16@gmail.com>
Cc: 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-03T17:32:29Z
Lists: pgsql-hackers 
On Wed, 2024-04-03 at 01:45 -0700, Jeff Davis wrote:
> I suggest that you add a "heap_index" field to ReorderBufferTXN that
> would point to the index into the heap's array (the same as
> bh_nodeidx_entry.index in your patch). Each time an element moves
> within the heap array, just follow the pointer to the
> ReorderBufferTXN
> object and update the heap_index -- no hash lookup required.

It looks like my email was slightly too late, as the work was already
committed.

My suggestion is not required for 17, and so it's fine if this waits
until the next CF. If it turns out to be a win we can consider
backporting to 17 just to keep the code consistent, otherwise it can go
in 18.

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.