| From: | "Euler Taveira" <euler(at)eulerto(dot)com> |
|---|---|
| To: | "Masahiko Sawada" <sawada(dot)mshk(at)gmail(dot)com>, "Alvaro Herrera" <alvherre(at)alvh(dot)no-ip(dot)org> |
| Cc: | "PostgreSQL Hackers" <pgsql-hackers(at)lists(dot)postgresql(dot)org> |
| Subject: | Re: Improve eviction algorithm in ReorderBuffer |
| Date: | 2023-12-15 16:36:27 |
| Message-ID: | 6c4c606f-dcec-4b26-a232-44e1a93d9046@app.fastmail.com |
| Views: | Raw Message | Whole Thread | Download mbox | Resend email |
| Thread: | |
| 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/
| From | Date | Subject | |
|---|---|---|---|
| Next Message | Andrew Dunstan | 2023-12-15 17:11:38 | Re: Clean up find_typedefs and add support for Mac |
| Previous Message | Tristan Partin | 2023-12-15 16:10:14 | Re: Clean up find_typedefs and add support for Mac |