Hacker News Reader

Comment by thesz | Hacker News Reader

The paper [1] does not refer to COLA or Fractal Indices.

https://dl.acm.org/doi/pdf/10.1145/3318464.3389711

ALEX uses gaped arrays (arrays with holes) to amortize key insertion. This wastes bandwidth - an exchange of read bandwidth wasted for speed of insertion gained.

Cache-Oblivious Lookahead Arrays (hence, COLA [2]) waste bandwidth in a different way - they use several layers of inserted data which are merged in amortized way during insertion.

[2] https://en.wikipedia.org/wiki/Fractal_tree_index - Fractal Tree Index is based on COLA paper.

That COLA thing allows for variable size keys, etc. And, generally speaking, is quite fruitful and efficient structure, especially for a disk storage.

Because of this, I think this paper lacks very important part - a comparison with modern write-and-read-efficient structure. Without this comparison, it is not worth considering.

View on HN

ALEX copies the next entry to the right into the gaps, meaning there's no read bandwidth wasted. It's also key to how they estimate the cost model to decide when to split a model. I'd suggest rereading the ALEX paper with a bit more care rather than using it just as a diving board to talk about unrelated papers you're fond of. There's some really interesting and novel ideas here.

Please forgive me, but no to both.

Having gaps in an array is a waste of bandwidth (TLB, for example, memory controller bandwidth is wasted too).

The COLA approach also can be adjusted - it is not necessary to have arrays with sizes that are power of two, we can use any other multiplier, correcting the necessity of merging. Many contemporary storage technologies can be adjusted to the workload and data statistics. Fighting against half a century (B+-trees were used by IBM in 1973) old technology with machine learning is, at the very least, not honorary.

Please, excuse me for not reading ALEX paper more thoroughly. I think onus is not on me in this case. So, my second no - I will not read ALEX paper again until they compare their achievements with more or less current technology.

Is Fractal Tree Index what is used in TokuDB?

While it sounds nice in theory, in practice it was very slow. The only thing TokuDB good at was bulk inserts. Other than that both writes and reads were slower than B+ tree.

I think eventually TokuDB just faded away.

Is there any other implementation of COLA/Fractal Tree that fares better?

I don't know intricate details of technology that TokuDB was using. These things are patented and I prefer to stay away.

My experience indicates that region allocation (inside DB file or other space) algorithm can be a big win. I devised an algorithm that produced O(log^2N) regions for log-structured merge trees backend and that resulted in larger regions allocated and more read/write bandwidth available (larger pages, adjusted to size of data). The overhead was not all that big - slightly less than 2 times over actual data size, BerkeleyDB log was much bigger (100x as big).

The SQLite's implementation of LSM trees used O(NlogN) regions allocations - it managed space using 1M bytes pages. Most of other databases does something like that - bitmaps in MS SQL Server are exactly this.

Also, you can trade space over speed and vice versa. Most of databases can utilize cover indices - index that contains all fields used in query will not trigger lookup operation into the actual table. With B+-trees, you cannot have many indices, they are all random inserts, basically, and B+-trees will degrade. With TokuDB or LSM trees you can have many indices, with different coverage, because you can tolerate random inserts much, much better (several orders of magnitudes better).

Indices are often highly compressible due to their redundancy because of sorting.

Thus, to get most of TokuDB, you have to change how you approach problems. You can do things that are not quite possible with B+-trees and that is what you have to get used to.

This may be second things why TokuDB is faded - thinking inertia.

Reply on news.ycombinator.com