Horton

Re: Improve eviction algorithm in ReorderBuffer

Alvaro Herrera <alvherre@alvh.no-ip.org>

View thread View on postgr.es
From: Alvaro Herrera <alvherre@alvh.no-ip.org>
To: Masahiko Sawada <sawada.mshk@gmail.com>
Cc: PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Date: 2023-12-15T10:10:24Z
Lists: pgsql-hackers 
On 2023-Dec-12, Masahiko Sawada wrote:

> To deal with this problem, I initially thought of the idea (a)
> mentioned in the comment; use a binary heap to maintain the
> transactions sorted by the amount of changes or the size. But it seems
> not a good idea to try maintaining all transactions by  its size since
> the size of each transaction could be changed frequently.

Hmm, maybe you can just use binaryheap_add_unordered and just let the
sizes change, and do binaryheap_build() at the point where the eviction
is needed.

-- 
Álvaro Herrera        Breisgau, Deutschland  —  https://www.EnterpriseDB.com/
"No necesitamos banderas
 No reconocemos fronteras"                  (Jorge González)

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.