From: Masahiko Sawada <msawada@postgresql.org>
To: pgsql-committers@lists.postgresql.org
Subject: pgsql: Add functions to binaryheap for efficient key removal and update
Date: Wed, 03 Apr 2024 01:44:39 +0000
Message-ID: <E1rrpg7-000DSM-9F@gemulon.postgresql.org> (raw)
Add functions to binaryheap for efficient key removal and update.
Previously, binaryheap didn't support updating a key and removing a
node in an efficient way. For example, in order to remove a node from
the binaryheap, the caller had to pass the node's position within the
array that the binaryheap internally has. Removing a node from the
binaryheap is done in O(log n) but searching for the key's position is
done in O(n).
This commit adds a hash table to binaryheap in order to track the
position of each nodes in the binaryheap. That way, by using newly
added functions such as binaryheap_update_up() etc., both updating a
key and removing a node can be done in O(1) on an average and O(log n)
in worst case. This is known as the indexed binary heap. The caller
can specify to use the indexed binaryheap by passing indexed = true.
The current code does not use the new indexing logic, but it will be
used by an upcoming patch.
Reviewed-by: Vignesh C, Peter Smith, Hayato Kuroda, Ajin Cherian,
Tomas Vondra, Shubham Khanna
Discussion: https://postgr.es/m/CAD21AoDffo37RC-eUuyHJKVEr017V2YYDLyn1xF_00ofptWbkg%40mail.gmail.com
Branch
------
master
Details
-------
https://git.postgresql.org/pg/commitdiff/b840508644151232b6ca1287dde617ed00ba2bdf
Modified Files
--------------
src/backend/executor/nodeGatherMerge.c | 1 +
src/backend/executor/nodeMergeAppend.c | 2 +-
src/backend/postmaster/pgarch.c | 3 +-
src/backend/replication/logical/reorderbuffer.c | 1 +
src/backend/storage/buffer/bufmgr.c | 1 +
src/bin/pg_dump/pg_backup_archiver.c | 1 +
src/bin/pg_dump/pg_dump_sort.c | 2 +-
src/common/binaryheap.c | 198 ++++++++++++++++++++++--
src/include/lib/binaryheap.h | 36 ++++-
src/tools/pgindent/typedefs.list | 1 +
10 files changed, 232 insertions(+), 14 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: Add functions to binaryheap for efficient key removal and update
In-Reply-To: <E1rrpg7-000DSM-9F@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