forked frompostgres/postgres
- Notifications
You must be signed in to change notification settings - Fork6
Commit5bec1d6
committed
Improve eviction algorithm in ReorderBuffer using max-heap for many subtransactions.
Previously, when selecting the transaction to evict during logicaldecoding, we check all transactions to find the largesttransaction. This could lead to a significant replication lagespecially in the case where there are many subtransactions.This commit improves the eviction algorithm in ReorderBuffer using themax-heap with transaction size as the key to efficiently find thelargest transaction.The max-heap starts with empty. While the max-heap is empty, we don'tdo anything for the max-heap when updating the memorycounter. Therefore, we get the largest transaction in O(N) time, whereN is the number of transactions including top-level transactions andsubtransactions.We build the max-heap just before selecting the largest transactionsif the number of transactions being decoded is higher than thethreshold, MAX_HEAP_TXN_COUNT_THRESHOLD. After building the max-heap,we also update the max-heap when updating the memory counter. Theintention is to efficiently find the largest transaction in O(1) timeinstead of incurring the cost of memory counter updates (O(logN)). Once the number of transactions got lower than the threshold, wereset the max-heap.The performance benchmark results showed significant speed up (morethan x30 speed up on my machine) in decoding a transaction with 100ksubtransactions, whereas there is no visible overhead in other cases.Reviewed-by: Amit Kapila, Hayato Kuroda, Vignesh C, Ajin Cherian,Tomas Vondra, Shubham Khanna, Peter Smith, Álvaro Herrera,Euler TaveiraDiscussion:https://postgr.es/m/CAD21AoAfKTgrBrLq96GcTv9d6k97zaQcDM-rxfKEt4GSe0qnaQ%40mail.gmail.com1 parent7487044 commit5bec1d6
File tree
2 files changed
+214
-27
lines changed- src
- backend/replication/logical
- include/replication
2 files changed
+214
-27
lines changed0 commit comments
Comments
(0)