On Tue, 2 Aug 2022 at 12:32, Andrey Borodin <x4mmm@yandex-team.ru> wrote:
> KnownAssignedXidsRemoveTree() only compress with probability 1/8, but it is still O(N*N).
Currently it is O(NlogS), not quite as bad as O(N^2).
Since each xid in the tree is always stored to the right, it should be
possible to make that significantly better by starting each binary
search from the next element, rather than the start of the array.
Something like the attached might help, but we can probably make that
cache conscious to improve things even more.
--
Simon Riggs http://www.EnterpriseDB.com/