diff options
| author | Masahiko Sawada | 2024-04-11 08:04:38 +0000 |
|---|---|---|
| committer | Masahiko Sawada | 2024-04-11 08:04:38 +0000 |
| commit | efb8acc0d05894e0c6c20dfc00513b53098780f0 (patch) | |
| tree | 471ec23d9ce6731b931527e6fe56ad67b2568590 /src/include/replication | |
| parent | 942219996c632ae9e66c2c4a759e93abc92014ff (diff) | |
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
Diffstat (limited to 'src/include/replication')
| -rw-r--r-- | src/include/replication/reorderbuffer.h | 9 |
1 files changed, 7 insertions, 2 deletions
diff --git a/src/include/replication/reorderbuffer.h b/src/include/replication/reorderbuffer.h index a5aec01c2f0..851a001c8bb 100644 --- a/src/include/replication/reorderbuffer.h +++ b/src/include/replication/reorderbuffer.h @@ -10,8 +10,8 @@ #define REORDERBUFFER_H #include "access/htup_details.h" -#include "lib/binaryheap.h" #include "lib/ilist.h" +#include "lib/pairingheap.h" #include "storage/sinval.h" #include "utils/hsearch.h" #include "utils/relcache.h" @@ -403,6 +403,11 @@ typedef struct ReorderBufferTXN dlist_node catchange_node; /* + * A node in txn_heap + */ + pairingheap_node txn_node; + + /* * Size of this transaction (changes currently in memory, in bytes). */ Size size; @@ -633,7 +638,7 @@ struct ReorderBuffer Size size; /* Max-heap for sizes of all top-level and sub transactions */ - binaryheap *txn_heap; + pairingheap *txn_heap; /* * Statistics about transactions spilled to disk. |