From: | Claudio Freire <klaussfreire(at)gmail(dot)com> |
---|---|
To: | Andres Freund <andres(at)anarazel(dot)de> |
Cc: | Masahiko Sawada <sawada(dot)mshk(at)gmail(dot)com>, Anastasia Lubennikova <a(dot)lubennikova(at)postgrespro(dot)ru>, Anastasia Lubennikova <lubennikovaav(at)gmail(dot)com>, PostgreSQL-Dev <pgsql-hackers(at)postgresql(dot)org> |
Subject: | Re: Vacuum: allow usage of more than 1GB of work mem |
Date: | 2017-04-07 22:46:06 |
Message-ID: | CAGTBQpaQ1r+jo3akdSQ6vdt8aeO6oBn37KGVRjQ4KPBLqGuV3w@mail.gmail.com |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Thread: | |
Lists: | pgsql-hackers |
On Fri, Apr 7, 2017 at 7:43 PM, Claudio Freire <klaussfreire(at)gmail(dot)com> wrote:
>>> + * Lookup in that structure proceeds sequentially in the list of segments,
>>> + * and with a binary search within each segment. Since segment's size grows
>>> + * exponentially, this retains O(N log N) lookup complexity.
>>
>> N log N is a horrible lookup complexity. That's the complexity of
>> *sorting* an entire array. I think you might be trying to argue that
>> it's log(N) * log(N)? Once log(n) for the exponentially growing size of
>> segments, one for the binary search?
>>
>> Afaics you could quite easily make it O(2 log(N)) by simply also doing
>> binary search over the segments. Might not be worth it due to the small
>> constant involved normally.
>
> It's a typo, yes, I meant O(log N) (which is equivalent to O(2 log N))
To clarify, lookup over the segments is linear, so it's O(M) with M
the number of segments, then the binary search is O(log N) with N the
number of dead tuples.
So lookup is O(M + log N), but M < log N because of the segment's
exponential growth, therefore the lookup is O(2 log N)
From | Date | Subject | |
---|---|---|---|
Next Message | Alvaro Herrera | 2017-04-07 22:55:21 | Re: [COMMITTERS] pgsql: Improve 64bit atomics support. |
Previous Message | Claudio Freire | 2017-04-07 22:43:39 | Re: Vacuum: allow usage of more than 1GB of work mem |