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>
Cc: 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-09T18:04:49Z
Lists: pgsql-hackers

Attachments

On Fri, 2024-04-05 at 16:58 +0900, Masahiko Sawada wrote:
> > I have some further comments and I believe changes are required for
> > v17.

I also noticed that the simplehash is declared in binaryheap.h with
"SH_SCOPE extern", which seems wrong. Attached is a rough patch to
bring the declarations into binaryheap.c.

Note that the attached patch uses "SH_SCOPE static", which makes sense
to me in this case, but causes a bunch of warnings in gcc. I will post
separately about silencing that warning, but for now you can either
use:

   SH_SCOPE static inline

which is probably fine, but will encourage the compiler to inline more
code, when not all callers even use the hash table. Alternatively, you
can do:

   SH_SCOPE static pg_attribute_unused()

which looks a bit wrong to me, but seems to silence the warnings, and
lets the compiler decide whether or not to inline.

Also probably needs comment updates, etc.

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.