Re: Fractal tree indexing - Mailing list pgsql-hackers

From Atri Sharma
Subject Re: Fractal tree indexing
Date
Msg-id EA7E8C03-7C58-4F85-8F55-24DDD9F6322B@gmail.com
Whole thread Raw
In response to Re: Fractal tree indexing  (Heikki Linnakangas <hlinnakangas@vmware.com>)
List pgsql-hackers
Yeah,it is just a fancy name for something that has nothing to do with fractals.I guess everything suave these days is
fractal!

That said,the buffered concept itself looks really cool and should help us in large data sets.I am eager to get off the
markwith it. 

Will we be building the index from scratch? And how would we go about it?

We will need to be careful about the buffer size per node, in order to ensure that the pushing of tuples from nodes in
largedata sets does not become a substantial overhead. 

Atri
Sent from my iPad

On 13-Feb-2013, at 22:21, Heikki Linnakangas <hlinnakangas@vmware.com> wrote:

> On 13.02.2013 18:43, Andrew Dunstan wrote:
>>
>> On 02/13/2013 11:20 AM, Tom Lane wrote:
>>> Heikki Linnakangas <hlinnakangas@vmware.com> writes:
>>>> The basic idea of a fractal tree index is to attach a buffer to every
>>>> non-leaf page. On insertion, instead of descending all the way down to
>>>> the correct leaf page, the new tuple is put on the buffer at the root
>>>> page. When that buffer fills up, all the tuples in the buffer are
>>>> cascaded down to the buffers on the next level pages. And recursively,
>>>> whenever a buffer fills up at any level, it's flushed to the next level.
>>> [ scratches head... ] What's "fractal" about that? Or is that just a
>>> content-free marketing name for this technique?
>>
>> And if that's all it is then I have some doubt about its patentability.
>> For one thing I'd be mildly surprised if there weren't prior art. But of
>> course, IANAL :-)
>
> Agreed, but IANAL either. The papers the GiST buffering build algorithm was based pre-dates Tokutek's fractal
indexes,for starters. Of course, all I know about fractal indexes is what I've read on some presentation slides on the
'net,so I might be missing something. 
>
> - Heikki



pgsql-hackers by date:

Previous
From: Heikki Linnakangas
Date:
Subject: Re: Fractal tree indexing
Next
From: Tom Lane
Date:
Subject: Re: JSON Function Bike Shedding