Re: WIP: Fast GiST index build

On Tue, Aug 16, 2011 at 4:04 PM, Heikki Linnakangas <
heikki(dot)linnakangas(at)enterprisedb(dot)com> wrote:

> I can see that that's equal to the formula given in the paper, log_B(M/4B),
> but I couldn't see any explanation for that formula in the paper. Your
> explanation makes sense, but where did it come from?
>
I didn't find it too. But it has to reservse memory for both sub-tree and
active buffers. While we'are reserving memory for sub-tree in
effective_cache_size and memory for last pages of buffers in
maintenance_work_mem.

> It seems a bit pessimistic: while it's true that the a subtree can't be
> larger than 2 * maxIndexTuplesPerPage ^ levelStep, you can put a tighter
> upper bound on it. The max size of a subtree of depth n can be calculated as
> the geometric series:
>
> r^0 + r^1 + r^2 + ... + r^n = (1 - r^(n + 1)) / (1 - r)
>
> where r = maxIndexTuplesPerPage. For r=2 those formulas are equal, but for
> a large r and small n (which is typical), the 2 * maxIndexTuplesPerPage^**levelStep
> formula gives a value that's almost twice as large as the real max size of a
> subtree.
>
Thus, we can calculate:
levelstep = min(log_r(1 + effective_cache_size_in_pages*(r - 1)) - 1,
log_r(maintenance_work_mem_in_pages - 1))
and get more precise result. But also we need at least very rough estimate
of memory occupied by node buffers hash tab and path items.

------
With best regards,
Alexander Korotkov.