Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

532x Performance Increase for MongoDB with fractal tree indexes

tokutek.com

Post reply on HN
Print view View original

11–20 of 27 posts

Re: 532x Performance Increase for MongoDB with fractal tree indexes

#11

Post by leif »

joe_the_user wrote: post #10
leif wrote: post #6

Earlier quoted context omitted.

Hi, I'm one of the authors (I'm an engineer, not an author of the original papers, though I can discuss those too)! What would you like to know? First, the structure you described is called a cache oblivious lookahead array (COLA), and is not what we implement. It betrays a lot of the concepts that make up a fractal tree and is a good educational tool, which is why you'll find lots of Tokutek material that describes…

The nice thing would be a paper describing the algorithm formally and in enough detail for someone else to implement it.

The cache oblivious streaming b-tree paper is the one to read. We would like to write more papers about some of the things we have discovered while implementing it, but haven't really found the time.

Re: 532x Performance Increase for MongoDB with fractal tree indexes

#12

Post by robrenaud »

leif wrote: post #6
imperio59 wrote: post #5

I read the presentation here: http://tokutek.com/downloads/mysqluc-2010-fractal-trees.pdf The math looks a bit hand-wavy to me but I get the basic data structure, you basically have sorted arrays whose lengths are each a power of two, so 1, 2, 4, 8, etc... When you insert a set of values, you can either fill an entire array or leave it empty. So for example if you have 5 values, you'd have an array of 1 element, an e…

Hi, I'm one of the authors (I'm an engineer, not an author of the original papers, though I can discuss those too)! What would you like to know? First, the structure you described is called a cache oblivious lookahead array (COLA), and is not what we implement. It betrays a lot of the concepts that make up a fractal tree and is a good educational tool, which is why you'll find lots of Tokutek material that describes…

Where are the read benchmarks?

Re: 532x Performance Increase for MongoDB with fractal tree indexes

#13

Post by leif »

robrenaud wrote: post #12
leif wrote: post #6

Earlier quoted context omitted.

Hi, I'm one of the authors (I'm an engineer, not an author of the original papers, though I can discuss those too)! What would you like to know? First, the structure you described is called a cache oblivious lookahead array (COLA), and is not what we implement. It betrays a lot of the concepts that make up a fractal tree and is a good educational tool, which is why you'll find lots of Tokutek material that describes…

Where are the read benchmarks?

There's a link at the top of the article.

Re: 532x Performance Increase for MongoDB with fractal tree indexes

#15

Post by Groxx »

>At 3.5 million inserted documents, the exit velocity of standard MongoDB was 2.11 inserts per second...

That's terrifying - do people expect performance like this? Or was this crafted to be a pathological case? 100 element arrays don't seem too common, but that only makes this 300 million entries in e.g. a SQL table - I suspect my laptop running MySQL could outdo that kind of performance (but have no proof. I could be very wrong).

Re: 532x Performance Increase for MongoDB with fractal tree indexes

#16

Post by carterschonwald »

carterschonwald wrote: post #2

Please note that the actual name for a "fractal tree" in the research literature is "Streaming (cache oblivious) B-Tree" (or at least they've very very closely related). Writing good code wrt memory locality is SUPER important for writing high performance code, whether its in memory work, or larger than ram (eg for the DB). Also a fun exercise to try to understand how!

What is also especially interesting is that a lot of the same ideas are also really important in writing HPC grade numerical code!

admission: i'm presently having a go at trying to write some high level + good locality numerical code! :-) , partly for fun, and partly as part of my little business! :-)

Re: 532x Performance Increase for MongoDB with fractal tree indexes

#18

Post by krmmalik »

X4 wrote: post #14

Nobody believes me when I say Fractals solve literally everything efficiency related. Even though it's true. Nobody believed me when I introduced on-demand script injection for javascript, today it's IT etiquette. The power of popularity I guess.

Did you blog about it? give examples? What else can be solved with fractals?

Re: 532x Performance Increase for MongoDB with fractal tree indexes

#20

Post by tmcallaghan »

Groxx wrote: post #15

> At 3.5 million inserted documents, the exit velocity of standard MongoDB was 2.11 inserts per second... That's terrifying - do people expect performance like this? Or was this crafted to be a pathological case? 100 element arrays don't seem too common, but that only makes this 300 million entries in e.g. a SQL table - I suspect my laptop running MySQL could outdo that kind of performance (but have no proof. I could…

I used 100 elements per document since I plan on benchmarking support for parallel array indexes using two array fields with 10 elements each.
Post reply on HN