Horton

Re: Improve eviction algorithm in ReorderBuffer

Ajin Cherian <itsajin@gmail.com>

View thread View on postgr.es
From: Ajin Cherian <itsajin@gmail.com>
To: Masahiko Sawada <sawada.mshk@gmail.com>
Cc: Shubham Khanna <khannashubham1197@gmail.com>, Amit Kapila <amit.kapila16@gmail.com>, Dilip Kumar <dilipbalaut@gmail.com>, PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Date: 2024-02-09T10:35:42Z
Lists: pgsql-hackers 
On Tue, Feb 6, 2024 at 5:06 PM Masahiko Sawada <sawada.mshk@gmail.com>
wrote:

>
> I've attached the new version patch set.
>
> Regards,
>
>
> --
> Masahiko Sawada
> Amazon Web Services: https://aws.amazon.com


Thanks for the patch. I reviewed that patch and did minimal testing and it
seems to show the speed up as claimed. Some minor comments:
patch 0001:

+static void
+bh_enlarge_node_array(binaryheap *heap)
+{
+ if (heap->bh_size < heap->bh_space)
+ return;

why not check "if (heap->bh_size >= heap->bh_space)" outside this function
to avoid calling this function when not necessary? This check was there in
code before the patch.

patch 0003:

+/*
+ * The threshold of the number of transactions in the max-heap
(rb->txn_heap)
+ * to switch the state.
+ */
+#define REORDE_BUFFER_MEM_TRACK_THRESHOLD 1024

Typo: I think you meant REORDER_ and not REORDE_

regards,
Ajin Cherian
Fujitsu Australia

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.