From: Euler Taveira <euler@eulerto.com>
To: Masahiko Sawada <sawada.mshk@gmail.com>
To: Alvaro Herrera <alvherre@alvh.no-ip.org>
Cc: PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Subject: Re: Improve eviction algorithm in ReorderBuffer
Date: Fri, 15 Dec 2023 13:36:27 -0300
Message-ID: <6c4c606f-dcec-4b26-a232-44e1a93d9046@app.fastmail.com> (raw)
In-Reply-To: <CAD21AoC_xHnfQnrt_8g+sHaJYNJUYbV3hA5vAabf4QPdQtimKA@mail.gmail.com>
References: <CAD21AoAfKTgrBrLq96GcTv9d6k97zaQcDM-rxfKEt4GSe0qnaQ@mail.gmail.com>
<202312151010.y64axdxuzcvi@alvherre.pgsql>
<CAD21AoC_xHnfQnrt_8g+sHaJYNJUYbV3hA5vAabf4QPdQtimKA@mail.gmail.com>
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/
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-hackers@postgresql.org
Cc: euler@eulerto.com, sawada.mshk@gmail.com, alvherre@alvh.no-ip.org, pgsql-hackers@lists.postgresql.org
Subject: Re: Improve eviction algorithm in ReorderBuffer
In-Reply-To: <6c4c606f-dcec-4b26-a232-44e1a93d9046@app.fastmail.com>
* 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