On Tue, 2 Aug 2022 at 12:32, Andrey Borodin <x4...@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/
subx_optimize_KnownAssignedXidsRemoveTree.v2.patch
Description: Binary data
