3 ms·

Alex: A ML-enhanced range index

82 points by ngaut 6y ago

theblackcat1002 6y ago
This will be quite useful if ported to database
- random3 6y ago
  It is / will in various shapes. Check out Andy Pavlo's (CMU) work on self-driving databases https://www.cs.cmu.edu/~pavlo/ https://www.cs.cmu.edu/~pavlo/
yahyaheee 6y ago
This is an amazing accomplishment, I could see the ideas here being applied to more data structures
thesz 6y ago
The paper [1] does not refer to COLA or Fractal Indices. https://dl.acm.org/doi/pdf/10.1145/3318464.3389711 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 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.
- jasonwatkinspdx 6y ago
  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.
  - thesz 6y ago
    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.
- continuations 6y ago
  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?
  - thesz 6y ago
    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.
nn3 6y ago
I had expected something really fancy for the predictive model, but it's a really simple linear predictor that even I can understand ) 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/d2fc3dc79766aa5c36adc2772abd29b7fcf0e8fa/src/core/alex_base.h#L79 https://github.com/microsoft/ALEX/blob/d2fc3dc79766aa5c36adc... https://github.com/microsoft/ALEX/blob/d2fc3dc79766aa5c36adc2772abd29b7fcf0e8fa/src/core/alex_base.h#L120 https://github.com/microsoft/ALEX/blob/d2fc3dc79766aa5c36adc...

82 points by ngaut 6y ago

theblackcat1002 6y ago

This will be quite useful if ported to database

random3 6y ago
It is / will in various shapes. Check out Andy Pavlo's (CMU) work on self-driving databases https://www.cs.cmu.edu/~pavlo/ https://www.cs.cmu.edu/~pavlo/

yahyaheee 6y ago

This is an amazing accomplishment, I could see the ideas here being applied to more data structures

thesz 6y ago

The paper [1] does not refer to COLA or Fractal Indices. https://dl.acm.org/doi/pdf/10.1145/3318464.3389711 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 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.

jasonwatkinspdx 6y ago
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.
- thesz 6y ago
  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.
continuations 6y ago
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?
- thesz 6y ago
  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.

nn3 6y ago

I had expected something really fancy for the predictive model, but it's a really simple linear predictor that even I can understand ) 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/d2fc3dc79766aa5c36adc2772abd29b7fcf0e8fa/src/core/alex_base.h#L79 https://github.com/microsoft/ALEX/blob/d2fc3dc79766aa5c36adc... https://github.com/microsoft/ALEX/blob/d2fc3dc79766aa5c36adc2772abd29b7fcf0e8fa/src/core/alex_base.h#L120 https://github.com/microsoft/ALEX/blob/d2fc3dc79766aa5c36adc...