From: Masahiko Sawada <msawada@postgresql.org>
To: pgsql-committers@lists.postgresql.org
Subject: pgsql: Replace binaryheap + index with pairingheap in reorderbuffer.c
Date: Thu, 11 Apr 2024 08:05:17 +0000
Message-ID: <E1rupQq-001ZCJ-Fq@gemulon.postgresql.org> (raw)
Replace binaryheap + index with pairingheap in reorderbuffer.c
A pairing heap can perform the same operations as the binary heap +
index, with as good or better algorithmic complexity, and that's an
existing data structure so that we don't need to invent anything new
compared to v16. This commit makes the new binaryheap functionality
that was added in commits b840508644 and bcb14f4abc unnecessary, but
they will be reverted separately.
Remove the optimization to only build and maintain the heap when the
amount of memory used is close to the limit, becuase the bookkeeping
overhead with the pairing heap seems to be small enough that it
doesn't matter in practice.
Reported-by: Jeff Davis
Author: Heikki Linnakangas
Reviewed-by: Michael Paquier, Hayato Kuroda, Masahiko Sawada
Discussion: https://postgr.es/m/12747c15811d94efcc5cda72d6b35c80d7bf3443.camel%40j-davis.com
Branch
------
master
Details
-------
https://git.postgresql.org/pg/commitdiff/efb8acc0d05894e0c6c20dfc00513b53098780f0
Modified Files
--------------
src/backend/replication/logical/reorderbuffer.c | 191 +++---------------------
src/include/replication/reorderbuffer.h | 9 +-
2 files changed, 30 insertions(+), 170 deletions(-)
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-committers@postgresql.org
Cc: msawada@postgresql.org, pgsql-committers@lists.postgresql.org
Subject: Re: pgsql: Replace binaryheap + index with pairingheap in reorderbuffer.c
In-Reply-To: <E1rupQq-001ZCJ-Fq@gemulon.postgresql.org>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox