Re: GSoC proposal: Fast GiST index build

Just to clarify situation a bit. I noticed buffer tree technique while reseaching
sp-gist and got an idea to use it for improving CREATE INDEX for GiST, which
is what we were looking many times. Alexander is working on his thesis and
this project suits ideally for him and community. Since I and Teodor are very
busy in the moment, it's very important to have one more gist developer
available, especially, keeping in mind the energy and motivation of Alexander.
He already did several contributions and I have no doubt his work will be
useful for us. So, I suggest support his work !

Oleg

On Wed, 6 Apr 2011, Alexander Korotkov wrote:

> On Mon, Apr 4, 2011 at 8:50 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
>
>> OK. Could you briefly describe the algorithm you propose to
>> implement, bearing in mind that I haven't read the paper?
>>
>
> The technique can be very briefly described in following rules.
> M = number of index keys fitting in RAM;
> B = number of index keys in one page;
> 1) Additional buffers of M/(2*B) pages each is attached to all nodes of some
> levels. Levels are selected with step floor(log(M/4B, B))), leaf nodes don't
> contain buffers. I.e. nodes in levels i*floor(log(M/4B, B))), i = 1,2,3,...
> contain buffers (numbering is going from down to up, level 0 contain leaf
> nodes).
> 2) When entry reaches node with buffer, it is placed into buffer.
> 3) When buffer is overflowed it runs down into lower buffers or leaf pages.
> 4) When split occurs in node with buffer, then this buffers splits into two
> buffers using penalty function.
>
> ----
> With best regards,
> Alexander Korotkov.
>

Regards,
Oleg
_____________________________________________________________
Oleg Bartunov, Research Scientist, Head of AstroNet (www.astronet.ru),
Sternberg Astronomical Institute, Moscow University, Russia
Internet: oleg(at)sai(dot)msu(dot)su, http://www.sai.msu.su/~megera/
phone: +007(495)939-16-83, +007(495)939-23-83