Re: [HACKERS] Fractal tree indexing

2016-11-16 Thread Andrew Borodin
Hi hackers! Here is prototype of procrastinating GiST. Or lazy GiST. Or buffered GiST. Indeed, there is nothing fractal about it. The concept is leaf tuples stall on internal pages. From time to time they are pushed down in batches. This code is far from perfect, I've coded this only for the

[HACKERS] Fractal tree indexing

2013-02-13 Thread Atri Sharma
Hi all, Just a curiosity I couldnt control. I was recently reading about Fractal tree indexing (http://www.tokutek.com/2012/12/fractal-tree-indexing-overview/) and how TokuDB engine for MySQL is really working nicely with big data. I was wondering, do we have support for fractal tree indexing? I

Re: [HACKERS] Fractal tree indexing

2013-02-13 Thread Heikki Linnakangas
On 13.02.2013 11:01, Atri Sharma wrote: Hi all, Just a curiosity I couldnt control. I was recently reading about Fractal tree indexing (http://www.tokutek.com/2012/12/fractal-tree-indexing-overview/) and how TokuDB engine for MySQL is really working nicely with big data. Hmm, sounds very

Re: [HACKERS] Fractal tree indexing

2013-02-13 Thread Atri Sharma
On Wed, Feb 13, 2013 at 3:08 PM, Heikki Linnakangas hlinnakan...@vmware.com wrote: On 13.02.2013 11:01, Atri Sharma wrote: Hi all, Just a curiosity I couldnt control. I was recently reading about Fractal tree indexing (http://www.tokutek.com/2012/12/fractal-tree-indexing-overview/) and how

Re: [HACKERS] Fractal tree indexing

2013-02-13 Thread Alexander Korotkov
On Wed, Feb 13, 2013 at 1:38 PM, Heikki Linnakangas hlinnakan...@vmware.com wrote: On 13.02.2013 11:01, Atri Sharma wrote: Hi all, Just a curiosity I couldnt control. I was recently reading about Fractal tree indexing

Re: [HACKERS] Fractal tree indexing

2013-02-13 Thread Atri Sharma
Wed: I remember we have already discussed fractal trees privately. Short conclusions are so: 1) Fractal tree indexes are patented. It is distributed as commercial extension to MySQL. So we can't include it into PostgreSQL core. 2) Tokutek can't provide full-fledged fractal tree indexes as

Re: [HACKERS] Fractal tree indexing

2013-02-13 Thread Greg Stark
On Wed, Feb 13, 2013 at 10:19 AM, Atri Sharma atri.j...@gmail.com wrote: 2) Tokutek can't provide full-fledged fractal tree indexes as PostgreSQL extension because lack of WAL extensibility. We could think about WAL extensibility which would help other applications as well. Sounds nice. WAL

Re: [HACKERS] Fractal tree indexing

2013-02-13 Thread Atri Sharma
Sent from my iPad On 13-Feb-2013, at 18:21, Greg Stark st...@mit.edu wrote Heikki was talking about a generic WAL record type that would just store a binary delta between the version of the block when it was locked and when it was unlocked. That would handle any extension cleanly as far

Re: [HACKERS] Fractal tree indexing

2013-02-13 Thread Alexander Korotkov
On Wed, Feb 13, 2013 at 4:51 PM, Greg Stark st...@mit.edu wrote: Heikki was talking about a generic WAL record type that would just store a binary delta between the version of the block when it was locked and when it was unlocked. That would handle any extension cleanly as far as data

Re: [HACKERS] Fractal tree indexing

2013-02-13 Thread Heikki Linnakangas
On 13.02.2013 15:31, Alexander Korotkov wrote: On Wed, Feb 13, 2013 at 4:51 PM, Greg Starkst...@mit.edu wrote: Heikki was talking about a generic WAL record type that would just store a binary delta between the version of the block when it was locked and when it was unlocked. That would

Re: [HACKERS] Fractal tree indexing

2013-02-13 Thread Atri Sharma
Sent from my iPad On 13-Feb-2013, at 19:05, Heikki Linnakangas hlinnakan...@vmware.com wrote: On 13.02.2013 15:31, Alexander Korotkov wrote: On Wed, Feb 13, 2013 at 4:51 PM, Greg Starkst...@mit.edu wrote: Heikki was talking about a generic WAL record type that would just store a binary

Re: [HACKERS] Fractal tree indexing

2013-02-13 Thread Simon Riggs
On 13 February 2013 13:35, Heikki Linnakangas hlinnakan...@vmware.com wrote: You could have a generic WAL record that applies changes to multiple pages atomically. I think its a good idea, the best idea even, but we still have no idea what the requirements are without a clear case for an

Re: [HACKERS] Fractal tree indexing

2013-02-13 Thread Atri Sharma
Sent from my iPad On 13-Feb-2013, at 19:31, Simon Riggs si...@2ndquadrant.com wrote: . I think its a good idea, the best idea even, but we still have no idea what the requirements are without a clear case for an external index. It could easily turn out that we invent a plausible API that's

Re: [HACKERS] Fractal tree indexing

2013-02-13 Thread Andrew Dunstan
On 02/13/2013 09:13 AM, Atri Sharma wrote: Sent from my iPad On 13-Feb-2013, at 19:31, Simon Riggs si...@2ndquadrant.com wrote: . I think its a good idea, the best idea even, but we still have no idea what the requirements are without a clear case for an external index. It could easily turn

Re: [HACKERS] Fractal tree indexing

2013-02-13 Thread Atri Sharma
If they are patented as Alexander says upthread, then surely the idea is dead in the water. True, I think so too. But,the generic WAL seems an awesome idea and I would love to help. Atri -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your

Re: [HACKERS] Fractal tree indexing

2013-02-13 Thread Craig Ringer
On 02/13/2013 10:43 PM, Andrew Dunstan wrote: On 02/13/2013 09:13 AM, Atri Sharma wrote: Sent from my iPad On 13-Feb-2013, at 19:31, Simon Riggs si...@2ndquadrant.com wrote: . I think its a good idea, the best idea even, but we still have no idea what the requirements are without a clear

Re: [HACKERS] Fractal tree indexing

2013-02-13 Thread Tom Lane
Atri Sharma atri.j...@gmail.com writes: Do you think building a new index in postgres with fractal trees as the basis would serve the purpose? or is there something else we should think of? First explain why you couldn't build it as an opclass for gist or spgist ...

Re: [HACKERS] Fractal tree indexing

2013-02-13 Thread Atri Sharma
Sent from my iPad On 13-Feb-2013, at 20:30, Tom Lane t...@sss.pgh.pa.us wrote: First explain why you couldn't build it as an opclass for gist or spgist ... That needs thinking about a bit.I was confused about the current indexes because they all build on BTrees.But,

Re: [HACKERS] Fractal tree indexing

2013-02-13 Thread Heikki Linnakangas
On 13.02.2013 17:49, Atri Sharma wrote: On 13-Feb-2013, at 20:30, Tom Lanet...@sss.pgh.pa.us wrote: First explain why you couldn't build it as an opclass for gist or spgist ... That needs thinking about a bit.I was confused about the current indexes because they all build on BTrees.But,

Re: [HACKERS] Fractal tree indexing

2013-02-13 Thread Atri Sharma
Sent from my iPad . That makes no sense. I don't see any way to implement this in an opclass, and it wouldn't make sense to re-implement this for every opclass anyway. The basic idea of a fractal tree index is to attach a buffer to every non-leaf page. On insertion, instead of

Re: [HACKERS] Fractal tree indexing

2013-02-13 Thread Tom Lane
Heikki Linnakangas hlinnakan...@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

Re: [HACKERS] Fractal tree indexing

2013-02-13 Thread Andrew Dunstan
On 02/13/2013 11:20 AM, Tom Lane wrote: Heikki Linnakangas hlinnakan...@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

Re: [HACKERS] Fractal tree indexing

2013-02-13 Thread Heikki Linnakangas
On 13.02.2013 18:20, Tom Lane wrote: Heikki Linnakangashlinnakan...@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

Re: [HACKERS] Fractal tree indexing

2013-02-13 Thread Heikki Linnakangas
On 13.02.2013 18:43, Andrew Dunstan wrote: On 02/13/2013 11:20 AM, Tom Lane wrote: Heikki Linnakangas hlinnakan...@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

Re: [HACKERS] Fractal tree indexing

2013-02-13 Thread Atri Sharma
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 mark with it. Will we be building the index

Re: [HACKERS] Fractal tree indexing

2013-02-13 Thread Atri Sharma
Sent from my iPad On 13-Feb-2013, at 22:21, Heikki Linnakangas hlinnakan...@vmware.com wrote: On 13.02.2013 18:43, Andrew Dunstan wrote: On 02/13/2013 11:20 AM, Tom Lane wrote: Heikki Linnakangas hlinnakan...@vmware.com writes: The basic fractal indexes is what I've read on some

Re: [HACKERS] Fractal tree indexing

2013-02-13 Thread Simon Riggs
On 13 February 2013 16:48, Heikki Linnakangas hlinnakan...@vmware.com wrote: On 13.02.2013 18:20, Tom Lane wrote: Heikki Linnakangashlinnakan...@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

Re: [HACKERS] Fractal tree indexing

2013-02-13 Thread Joshua D. Drake
On 02/13/2013 09:54 AM, Simon Riggs wrote: I'd call it out as a marketing name. I guess it's fractal in the sense that all levels of the tree can hold leaf tuples in the buffers; the structure looks the same no matter how deep you zoom, like a fractal.. But Buffered would be more appropriate

Re: [HACKERS] Fractal tree indexing

2013-02-13 Thread Josh Berkus
On 02/13/2013 01:01 AM, Atri Sharma wrote: Hi all, Just a curiosity I couldnt control. I was recently reading about Fractal tree indexing (http://www.tokutek.com/2012/12/fractal-tree-indexing-overview/) and how TokuDB engine for MySQL is really working nicely with big data. I was

Re: [HACKERS] Fractal tree indexing

2013-02-13 Thread Daniel Farina
On Wed, Feb 13, 2013 at 8:20 AM, Tom Lane t...@sss.pgh.pa.us wrote: Heikki Linnakangas hlinnakan...@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

Re: [HACKERS] Fractal tree indexing

2013-02-13 Thread Greg Stark
On Wed, Feb 13, 2013 at 1:31 PM, Alexander Korotkov aekorot...@gmail.com wrote: On Wed, Feb 13, 2013 at 4:51 PM, Greg Stark st...@mit.edu wrote: Heikki was talking about a generic WAL record type that would just store a binary delta between the version of the block when it was locked and when