| From: | Simon Riggs <simon(dot)riggs(at)enterprisedb(dot)com> |
|---|---|
| To: | Andrey Borodin <x4mmm(at)yandex-team(dot)ru> |
| Cc: | Kyotaro Horiguchi <horikyota(dot)ntt(at)gmail(dot)com>, Michail Nikolaev <michail(dot)nikolaev(at)gmail(dot)com>, Alexander Korotkov <aekorotkov(at)gmail(dot)com>, Andres Freund <andres(at)anarazel(dot)de>, reshkekirill <reshkekirill(at)gmail(dot)com>, PostgreSQL Hackers <pgsql-hackers(at)postgresql(dot)org> |
| Subject: | Re: Slow standby snapshot |
| Date: | 2022-08-02 15:18:44 |
| Message-ID: | CANbhV-Ey8HRYPvnvQnsZAteCfzN3VHVhZVKfWMYcnjMnSzs4dQ@mail.gmail.com |
| Views: | Raw Message | Whole Thread | Download mbox | Resend email |
| Thread: | |
| Lists: | pgsql-hackers |
On Tue, 2 Aug 2022 at 12:32, Andrey Borodin <x4mmm(at)yandex-team(dot)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/
| Attachment | Content-Type | Size |
|---|---|---|
| subx_optimize_KnownAssignedXidsRemoveTree.v2.patch | application/octet-stream | 4.3 KB |
| From | Date | Subject | |
|---|---|---|---|
| Next Message | Andres Freund | 2022-08-02 15:37:04 | Re: Pluggable toaster |
| Previous Message | David Steele | 2022-08-02 15:01:19 | Re: Race between KeepFileRestoredFromArchive() and restartpoint |