From: | Alexander Korotkov <aekorotkov(at)gmail(dot)com> |
---|---|
To: | Heikki Linnakangas <heikki(dot)linnakangas(at)enterprisedb(dot)com> |
Cc: | pgsql-hackers <pgsql-hackers(at)postgresql(dot)org> |
Subject: | Re: WIP: Fast GiST index build |
Date: | 2011-06-28 07:47:43 |
Message-ID: | BANLkTi=Ue7SNbDzM+PkRdje=zuwmNRhoBA@mail.gmail.com |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Thread: | |
Lists: | pgsql-hackers |
On Mon, Jun 27, 2011 at 10:32 PM, Alexander Korotkov
<aekorotkov(at)gmail(dot)com>wrote:
> I didn't have an estimate yet, but I'm working on it.
>
Now, it seems that I have an estimate.
N - total number of itups
B - avg. number of itups in page
H - height of tree
K - avg. number of itups fitting in node buffer
step - level step of buffers
K = 2 * B^step
avg. number of internal pages with buffers = 2*N/((2*B)^step - 1) (assume
pages to be half-filled)
avg. itups in node buffer = K / 2 (assume node buffers to be half-filled)
Each internal page with buffers can be produces by split of another internal
page with buffers.
So, number of additional penalty calls = 2*N/((2*B)^step - 1) * K / 2
=(approximately)= 2*N*(1/2)^step
While number of regular penalty calls is H*N
Seems that fraction of additional penalty calls should decrease with
increase of level step (while I didn't do experiments with level step != 1).
Also, we can try to broke K = 2 * B^step equation. This can increase number
of IOs, but decrease number of additional penalty calls and, probably,
increase tree quality in some cases.
------
With best regards,
Alexander Korotkov.
From | Date | Subject | |
---|---|---|---|
Next Message | Reinhard Max | 2011-06-28 07:55:20 | Re: silent_mode and LINUX_OOM_ADJ |
Previous Message | Heikki Linnakangas | 2011-06-28 07:40:17 | Re: silent_mode and LINUX_OOM_ADJ |