Hello, context switch was complete that time, sorry. There's multiple "target LET"s. So we need kth-largest LTEs.
At Wed, 7 Dec 2016 19:04:23 +0900, Michael Paquier <michael.paqu...@gmail.com> wrote in <CAB7nPqR10OnEL5XxW1DVYvAXmtpEVNCMi=v-6jb_9owfuy8...@mail.gmail.com> > On Wed, Dec 7, 2016 at 5:17 PM, Masahiko Sawada <sawada.m...@gmail.com> wrote: > > Sorry, I could not understand this algorithm. Could you elaborate > > this? It takes only O(n) times? > > Nah, please forget that, that was a random useless thought. There is > no way to be able to select the k-th element without knowing the > hierarchy induced by the others, which is what the partial sort would > help with here. So, let's consider for some cases, - needing 3-quorum among 5 standbys. There's no problem whatever make kth-largest we choose. Of course qsorts are fine. - needing 10 quorums among 100 standbys. I'm not sure if there's any difference with 3/5. - needing 10 quorums among 1000 standbys. Obviously qsorts are doing too much. Any kind of kth-largest algorithm should be involved. For instance quickselect with O(n long n) - O(n) seems better in comparison to O(n log n) - O(n^2) of qsort. - needing 700 quorums among 1000 standbys. I don't think this case is worth consider but kth-largest is better even for this case. If we don't 700/1000 is out of at least the current scope, I also recommend to use kth-largest selection. If not, the quorum calculation is triggered by every standby reply message and the frequency of the calculation seems near to the frequency of WAL-insertion for the worst case. (Right?) Even the kth-largest takes too long time to have 1000 standys. Maintining kth-largest in shared memory needs less CPU but leads to more bad contention on the shared memory. Inversely, we already have waiting LSNs of backends in procarray. If we have another array in the order of waiting LSNs and having a condition varialble on the number of comforming walsenders. Every walsender can individually looking up it and count it up. It might performs better but I'm not sure. regards, -- Kyotaro Horiguchi NTT Open Source Software Center -- Sent via pgsql-hackers mailing list (firstname.lastname@example.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers