4 ms·

I've read that paper, and I wasn't particularly impressed. Is there any concrete evidence that learned indices scale to databases with complex schemata and a la

I've read that paper, and I wasn't particularly impressed. Is there any concrete evidence that learned indices scale to databases with complex schemata and a large transactional volume? Could learned indices be profitably used, say, in the database backend of an ERP system?

sulam 9y ago
There are immediate applications to data warehousing. I hope that's obvious to you, but if not I'm happy to unpack that. Whether or not it applies to online databases probably depends on several factors. The ones I can think of off the top of my head are the read/write ratio, the write rate in general, and obviously size of your data set (although the approach works at GB, not TB, so most can take advantage). Here's a way, I, a systems engineer who doesn't design databases, could imagine using it immediately: 1) Do I have any indexed queries? If not, nothing to do here. 2) Does the data change rapidly? If so, nothing to do here. 3) Okay, now I'm in the zone of profitability: 1) investigate just letting the model do all the work. This is unlikely to be successful in many cases, but it's pretty easy to try. 2) investigate "model-assist", in this mode I let the model give me an answer and, if I don't like it, I use the B-tree. The model is fast enough that this is not a huge hit to my overall performance. 3) investigate "model-replace", in this mode I build my b-tree and do everything like normal. In the meantime I'm training my model. Once my model seems well-trained (I could hand it a randomized subset of queries and, once the accuracy and performance beats the b-tree I consider it well-trained), I switch to using it. As data changes I could potentially go back to the b-tree, update the model (literally throw it away and re-build) and do it again. 4) Investigate "co-opetition" -- make the b-tree a component of the model. If you read the paper, you see how they layer different models. A b-tree is just a particular kind of model that happens to be computationally expensive but has high accuracy. You could include it in the model graph and let it compete for queries like everything else. Anyway, I'm speculating here, but it seems obvious this has immediate impact in one large space relating to databases (data warehousing) and potential impact in many of the rest.
- catnaroek 9y ago
  > There are immediate applications to data warehousing. I am not too worried about data warehouses. Data warehouses can be fed by batch processes, which you can run, say, once every day or once every week. This leads to the design of algorithms that optimize aggregate measures of performance (e.g. amortized complexity, average complexity, throughput) rather than microscopic measures of performance (e.g. worst-case complexity, latency). Machine learning techniques have a track record of delivering good aggregate results. However, online databases require optimal worst-case performance. The occasional massively slow operation is not okay - we'd rather every operation be a tiny bit slower instead. > Do I have any indexed queries? If not, nothing to do here. Of course I do. Needless to say, complex schemata come with lots of indices that are necessary to speed up queries that pull data from 10-15 tables each. > Does the data change rapidly? If so, nothing to do here. Of course the data changes rapidly. Crucially, an online transactional database's input comes from external parties (e.g., public-facing web servers) that cannot be considered trustworthy. Many machine learning techniques are vulnerable to so-called “adversarial examples”. Feeding adversarial examples to an ML-powered index could cause the database's performance to drop drastically in ways that are provably not possible with B-trees.
  - sulam 9y ago
    So, would you take a bet that this won't have been used in any self-evident way within the next 5 years? Because I would take the other side of that bet. :)
    - catnaroek 9y ago
      I'm not in the business of predicting the future, since that is beyond my control. What other people do with learned indices is up to them. I'm just stating my concerns.
oh-kumudo 9y ago
Data warehousing is one obvious application: data is immutable; have a sort key. So NN as a builtin once index structure is perfect for such case. It is only a matter of time for commercial analytic DB to pick up this idea, I would presume.
- catnaroek 9y ago
  You're right, data warehousing seems like a compelling use case for learned indices. I'm primarily worried about OLTP systems, though.

sulam 9y ago

There are immediate applications to data warehousing. I hope that's obvious to you, but if not I'm happy to unpack that. Whether or not it applies to online databases probably depends on several factors. The ones I can think of off the top of my head are the read/write ratio, the write rate in general, and obviously size of your data set (although the approach works at GB, not TB, so most can take advantage). Here's a way, I, a systems engineer who doesn't design databases, could imagine using it immediately: 1) Do I have any indexed queries? If not, nothing to do here. 2) Does the data change rapidly? If so, nothing to do here. 3) Okay, now I'm in the zone of profitability: 1) investigate just letting the model do all the work. This is unlikely to be successful in many cases, but it's pretty easy to try. 2) investigate "model-assist", in this mode I let the model give me an answer and, if I don't like it, I use the B-tree. The model is fast enough that this is not a huge hit to my overall performance. 3) investigate "model-replace", in this mode I build my b-tree and do everything like normal. In the meantime I'm training my model. Once my model seems well-trained (I could hand it a randomized subset of queries and, once the accuracy and performance beats the b-tree I consider it well-trained), I switch to using it. As data changes I could potentially go back to the b-tree, update the model (literally throw it away and re-build) and do it again. 4) Investigate "co-opetition" -- make the b-tree a component of the model. If you read the paper, you see how they layer different models. A b-tree is just a particular kind of model that happens to be computationally expensive but has high accuracy. You could include it in the model graph and let it compete for queries like everything else. Anyway, I'm speculating here, but it seems obvious this has immediate impact in one large space relating to databases (data warehousing) and potential impact in many of the rest.

catnaroek 9y ago
> There are immediate applications to data warehousing. I am not too worried about data warehouses. Data warehouses can be fed by batch processes, which you can run, say, once every day or once every week. This leads to the design of algorithms that optimize aggregate measures of performance (e.g. amortized complexity, average complexity, throughput) rather than microscopic measures of performance (e.g. worst-case complexity, latency). Machine learning techniques have a track record of delivering good aggregate results. However, online databases require optimal worst-case performance. The occasional massively slow operation is not okay - we'd rather every operation be a tiny bit slower instead. > Do I have any indexed queries? If not, nothing to do here. Of course I do. Needless to say, complex schemata come with lots of indices that are necessary to speed up queries that pull data from 10-15 tables each. > Does the data change rapidly? If so, nothing to do here. Of course the data changes rapidly. Crucially, an online transactional database's input comes from external parties (e.g., public-facing web servers) that cannot be considered trustworthy. Many machine learning techniques are vulnerable to so-called “adversarial examples”. Feeding adversarial examples to an ML-powered index could cause the database's performance to drop drastically in ways that are provably not possible with B-trees.
- sulam 9y ago
  So, would you take a bet that this won't have been used in any self-evident way within the next 5 years? Because I would take the other side of that bet. :)
  - catnaroek 9y ago
    I'm not in the business of predicting the future, since that is beyond my control. What other people do with learned indices is up to them. I'm just stating my concerns.

oh-kumudo 9y ago

Data warehousing is one obvious application: data is immutable; have a sort key. So NN as a builtin once index structure is perfect for such case. It is only a matter of time for commercial analytic DB to pick up this idea, I would presume.

catnaroek 9y ago
You're right, data warehousing seems like a compelling use case for learned indices. I'm primarily worried about OLTP systems, though.