Horton

RE: Improve eviction algorithm in ReorderBuffer

Hayato Kuroda (Fujitsu) <kuroda.hayato@fujitsu.com>

View thread View on postgr.es
From: "Hayato Kuroda (Fujitsu)" <kuroda.hayato@fujitsu.com>
To: 'Masahiko Sawada' <sawada.mshk@gmail.com>, Shubham Khanna <khannashubham1197@gmail.com>
Cc: Amit Kapila <amit.kapila16@gmail.com>, Dilip Kumar <dilipbalaut@gmail.com>, PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Date: 2024-02-08T09:33:08Z
Lists: pgsql-hackers 
Dear Sawada-san,

Thanks for making v3 patchset. I have also benchmarked the case [1].
Below results are the average of 5th, there are almost the same result
even when median is used for the comparison. On my env, the regression
cannot be seen.

HEAD (1e285a5)	HEAD + v3 patches	difference
10910.722 ms		10714.540 ms		around 1.8%

Also, here are mino comments for v3 set.

01.
bh_nodeidx_entry and ReorderBufferMemTrackState is missing in typedefs.list.

02. ReorderBufferTXNSizeCompare
Should we assert {ta, tb} are not NULL?

[1]: https://www.postgresql.org/message-id/CAD21AoB-7mPpKnLmBNfzfavG8AiTwEgAdVMuv%3DjzmAp9ex7eyQ%40mail.gmail.com

Best Regards,
Hayato Kuroda
FUJITSU LIMITED
https://www.fujitsu.com/

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.