Alex: A ML-enhanced range index
github.com
github.com
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.
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.
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?
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.
That's somewhat comforting, but I guess that limits the properties of the key space where it is useful?
https://github.com/microsoft/ALEX/blob/d2fc3dc79766aa5c36adc... https://github.com/microsoft/ALEX/blob/d2fc3dc79766aa5c36adc...