> On 2 Aug 2022, at 20:18, Simon Riggs <simon.ri...@enterprisedb.com> wrote:
>
> 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).
Consider workload when we have a big number of simultaneously active xids.
Number of calls to KnownAssignedXidsRemoveTree() is proportional to number of
these xids.
And the complexity of KnownAssignedXidsRemoveTree() is proportional to the
number of these xids, because each call to KnownAssignedXidsRemoveTree() might
evenly run compression (which will not compress much).
Compression is not an answer to performance problems - because it might be
burden itself. Instead we can make compression unneeded to make a snapshot's
xids-in-progress list.
> 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.
As Kyotaro-san correctly mentioned - performance degradation happened in
KnownAssignedXidsGetAndSetXmin() which does not do binary search.
> On 3 Aug 2022, at 06:04, Kyotaro Horiguchi <horikyota....@gmail.com> wrote:
>
> The original complaint is KnownAssignedXidsGetAndSetXmin can get very
> slow for large max_connections. I'm not sure what was happening on the
> KAXidsArray at the time precisely, but if the array starts with a
> large number of invalid entries (I guess it is likely), and the
> variable "start" were available to the function (that is, it were
> placed in procArray), that strategy seems to work for this case. With
> this strategy we can avoid compression if only the relatively narrow
> range in the array is occupied.
This applies to only one workload - all transactions are very short. If we have
a tiny fraction of mid or long transactions - this heuristics does not help
anymore.
Thank you!
Best regards, Andrey Borodin.
