Horton

Re: Improve eviction algorithm in ReorderBuffer

Euler Taveira <euler@eulerto.com>

View thread View on postgr.es
From: "Euler Taveira" <euler@eulerto.com>
To: "Masahiko Sawada" <sawada.mshk@gmail.com>, "Alvaro Herrera" <alvherre@alvh.no-ip.org>
Cc: "PostgreSQL Hackers" <pgsql-hackers@lists.postgresql.org>
Date: 2023-12-15T16:36:27Z
Lists: pgsql-hackers 
On Fri, Dec 15, 2023, at 9:11 AM, Masahiko Sawada wrote:
> 
> I assume you mean to add ReorderBufferTXN entries to the binaryheap
> and then build it by comparing their sizes (i.e. txn->size). But
> ReorderBufferTXN entries are removed and deallocated once the
> transaction finished. How can we efficiently remove these entries from
> binaryheap? I guess it would be O(n) to find the entry among the
> unordered entries, where n is the number of transactions in the
> reorderbuffer.

O(log n) for both functions: binaryheap_remove_first() and
binaryheap_remove_node(). I didn't read your patch but do you really need to
free entries one by one? If not, binaryheap_free().


--
Euler Taveira
EDB   https://www.enterprisedb.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.