16 ms·

I highly recommend people give this paper a read. I think it points the way to a radical redesign of fundamental parts of the system stack over the next 5-10 ye

by sulam 9y ago

I highly recommend people give this paper a read. I think it points the way to a radical redesign of fundamental parts of the system stack over the next 5-10 years. If you work in systems and you aren’t thinking about this stuff, you’re about to be lapped. The Case for Learned Index Structures: https://arxiv.org/pdf/1712.01208v1.pdf https://arxiv.org/pdf/1712.01208v1.pdf

allcentury 9y ago
That was a good read, thanks for sharing this.
AlexTelon 9y ago
A very interesting read indeed! Besides HN how can one find great papers like this? How did you find out about it?
- CaHoop 9y ago
  I saw this paper on reddit.com/r/machinelearning - usually the more interesting ML papers are posted there. Additionally, there is http://www.arxiv-sanity.com/ http://www.arxiv-sanity.com/ which sorts new machine learning papers by popularity.
- sulam 9y ago
  I found this paper after reading through Jeff Dean's talk at NIPS. I recommend that, too, obviously! http://learningsys.org/nips17/assets/slides/dean-nips17.pdf http://learningsys.org/nips17/assets/slides/dean-nips17.pdf You can generally find a paper for each section.
- dekayed 9y ago
  I'd recommend taking a look at Papers We Love https://github.com/papers-we-love/papers-we-love https://github.com/papers-we-love/papers-we-love
  - rmk 9y ago
    Loved the two-minute papers channel that I came across on this list. Thanks!
- godelmachine 9y ago
  1) The Morning Paper - blog.acolyer.org - A new super interesting paper review everyday 2) This is my personal ritual. Every weekday I check out recent entries in "Hardware architectures" and "Emerging Technologies" section of arXiv.org Many other sections are gaining traction with me, like Database. Hope this helps.
  - juanmirocks 9y ago
    Thank you for The Morning Paper
    - travmatt 9y ago
      You'd also like Fermat's Library
      - godelmachine 9y ago
        Oh yes, I do read Fermat's library, but that's more into pure mathematics side, which means I need to put in 3X the efforts to understand the papers, which I do.
chubot 9y ago
I'm gonna throw some cold water on this and say this is not a new paradigm by any means. https://www.sigarch.org/the-unreasonable-ineffectiveness-of-machine-learning-in-computer-systems-research/ https://www.sigarch.org/the-unreasonable-ineffectiveness-of-... However, it's certainly possible that the time for this idea has come. Google is probably in the best position to apply it. I will say that after having worked at Google for over a decade, some of it on data center performance, there are plenty of inefficiencies that have nothing to do with algorithms or code, but have more to do with very coarse-grained resource allocation. In other words, they are "boring management problems" rather than sexy CS problems. I should also add that you're expanding the claims made in the paper, which appears to be a common mistake. If you look at the related work and citations, you'll see that it's mostly about B-Trees, bloom filters, and indices. But I have seen people generalizing this to "a revolution in systems research", which I don't believe is justified. Indexed data structures are important but a revolution in them is not going to cause a revolution in all of systems. Off the top of my head, the general area of "scheduling" (in time and space) is probably more important and more potentially impactful.
- sulam 9y ago
  Have you seen the results when they let a trained model manage Borg? The power reductions were immediate, non-trivial, and performance stayed the same. There's your scheduling result for you. Look at it this way. As the paper points out, a Hashtable is just a heuristic that works fairly well in the worst case and reasonably well in the average case. No one would argue that you couldn't hand-roll an algorithm that is better for a specific, narrowly defined data set. This paper is demonstrating that you don't have to do it by hand, you can train a model automatically without the expected caveats like: size (doesn't have to be huge), latency (the model trains very quickly) or specialized hardware (they used bog-standard CPUs, not GPUs or TPUs). This is obviously just my opinion, but I think it's pretty big. It's not big because of the paper itself, although that's amazing in isolation (they improved on hashtables!). As I said above, it _points the way_. They have a throw-away sentence about co-optimizing data layout along with lookup and not showing those result. My guess is that beats a hashtable in every way. More importantly, if a model can beat bloom filters, b-trees, and hashtables, you'd better hold onto your socks because most algorithms are just waiting to fall. To me this paper is Deep Blue vs Kasparov. We all know what comes next.
catnaroek 9y ago
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.
godelmachine 9y ago
There was a time when people used to get PhD's for researching on index. This paper actually turns the table.
- eggie5 9y ago
  nice pun
eggie5 9y ago
Interesting article I read from Zalando, which in the same vein as the Learned Indexes paper, takes a previously computationally expensive routine (Optimal Cart Pick) and learns it as an approximation to a complex function that, in the end, has faster run-time. https://jobs.zalando.com/tech/blog/accelerating-warehouse-operations-with-neural-networks/ https://jobs.zalando.com/tech/blog/accelerating-warehouse-op...
- sulam 9y ago
  Cool!
sova 9y ago
Yo! This is what I'm talkin' about! Replace directories with self-consistent neural nwots [neural blackbox thingie of weights and activation vals]. It's cool, but for every convenience we take in the direction HD space we backpeddle in processing [meaning, although the dir structure could be super condensed this way with a learned index, this approach is less flexible to cold or not-cpu-related analysis]. It's very cool actually to consider the three branches of processing, hdd, and memcache ... You want to have a balance but in the ideal computer we do no calculation, and that is something worth mentioning. Reading again of the abstract, allow me to add that it's an optimization beyond structures such as Btrees which are already not really decipherable datasets to the naked eyes. So any optimization in a space that's not designed to be human-legible can take whatever shape, and this is certainly a welcome achievement!
- smsx 9y ago
  > but in the ideal computer we do no calculation, and that is something worth mentioning Can you expand on this bit? I'm not sure I understand what you mean
  - sova 9y ago
    Absolutely! This is a statement on minimization of computational effort. When the solution has already been provided we need not do any calculation. One way to think about the quoted statement and how I meant it is to consider big O notation and how some operations take O(n) or (O lg n) steps dependent on input in order to reach a solution or complete a process or spit out a result; in this hypothetical best case our operations all take O(1). This is not really a calculation but in fact knowledge coming to light. Since writing this comment I have text-to-speech'd the whole of the article and I listened to it one afternoon over smooth classical music and I have come to appreciate the fact that many computers will have neural network processors like tensor processors or at the very least really good GPU, making it all the more likely that such algorithms [especially used in the specific case of fault intolerant data organization and file hierarchy] will actually not require so much computational effort as traditionally believed.
dukeflukem 9y ago
Lapped "overtake (a competitor in a race) to become one or more laps ahead."

by sulam 9y ago

allcentury 9y ago

That was a good read, thanks for sharing this.

AlexTelon 9y ago

A very interesting read indeed! Besides HN how can one find great papers like this? How did you find out about it?

CaHoop 9y ago
I saw this paper on reddit.com/r/machinelearning - usually the more interesting ML papers are posted there. Additionally, there is http://www.arxiv-sanity.com/ http://www.arxiv-sanity.com/ which sorts new machine learning papers by popularity.
sulam 9y ago
I found this paper after reading through Jeff Dean's talk at NIPS. I recommend that, too, obviously! http://learningsys.org/nips17/assets/slides/dean-nips17.pdf http://learningsys.org/nips17/assets/slides/dean-nips17.pdf You can generally find a paper for each section.
dekayed 9y ago
I'd recommend taking a look at Papers We Love https://github.com/papers-we-love/papers-we-love https://github.com/papers-we-love/papers-we-love
- rmk 9y ago
  Loved the two-minute papers channel that I came across on this list. Thanks!
godelmachine 9y ago
1) The Morning Paper - blog.acolyer.org - A new super interesting paper review everyday 2) This is my personal ritual. Every weekday I check out recent entries in "Hardware architectures" and "Emerging Technologies" section of arXiv.org Many other sections are gaining traction with me, like Database. Hope this helps.
- juanmirocks 9y ago
  Thank you for The Morning Paper
  - travmatt 9y ago
    You'd also like Fermat's Library
    - godelmachine 9y ago
      Oh yes, I do read Fermat's library, but that's more into pure mathematics side, which means I need to put in 3X the efforts to understand the papers, which I do.

chubot 9y ago

I'm gonna throw some cold water on this and say this is not a new paradigm by any means. https://www.sigarch.org/the-unreasonable-ineffectiveness-of-machine-learning-in-computer-systems-research/ https://www.sigarch.org/the-unreasonable-ineffectiveness-of-... However, it's certainly possible that the time for this idea has come. Google is probably in the best position to apply it. I will say that after having worked at Google for over a decade, some of it on data center performance, there are plenty of inefficiencies that have nothing to do with algorithms or code, but have more to do with very coarse-grained resource allocation. In other words, they are "boring management problems" rather than sexy CS problems. I should also add that you're expanding the claims made in the paper, which appears to be a common mistake. If you look at the related work and citations, you'll see that it's mostly about B-Trees, bloom filters, and indices. But I have seen people generalizing this to "a revolution in systems research", which I don't believe is justified. Indexed data structures are important but a revolution in them is not going to cause a revolution in all of systems. Off the top of my head, the general area of "scheduling" (in time and space) is probably more important and more potentially impactful.

sulam 9y ago
Have you seen the results when they let a trained model manage Borg? The power reductions were immediate, non-trivial, and performance stayed the same. There's your scheduling result for you. Look at it this way. As the paper points out, a Hashtable is just a heuristic that works fairly well in the worst case and reasonably well in the average case. No one would argue that you couldn't hand-roll an algorithm that is better for a specific, narrowly defined data set. This paper is demonstrating that you don't have to do it by hand, you can train a model automatically without the expected caveats like: size (doesn't have to be huge), latency (the model trains very quickly) or specialized hardware (they used bog-standard CPUs, not GPUs or TPUs). This is obviously just my opinion, but I think it's pretty big. It's not big because of the paper itself, although that's amazing in isolation (they improved on hashtables!). As I said above, it _points the way_. They have a throw-away sentence about co-optimizing data layout along with lookup and not showing those result. My guess is that beats a hashtable in every way. More importantly, if a model can beat bloom filters, b-trees, and hashtables, you'd better hold onto your socks because most algorithms are just waiting to fall. To me this paper is Deep Blue vs Kasparov. We all know what comes next.

catnaroek 9y ago

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.

godelmachine 9y ago

There was a time when people used to get PhD's for researching on index. This paper actually turns the table.

eggie5 9y ago
nice pun

eggie5 9y ago

Interesting article I read from Zalando, which in the same vein as the Learned Indexes paper, takes a previously computationally expensive routine (Optimal Cart Pick) and learns it as an approximation to a complex function that, in the end, has faster run-time. https://jobs.zalando.com/tech/blog/accelerating-warehouse-operations-with-neural-networks/ https://jobs.zalando.com/tech/blog/accelerating-warehouse-op...

sulam 9y ago
Cool!

sova 9y ago

Yo! This is what I'm talkin' about! Replace directories with self-consistent neural nwots [neural blackbox thingie of weights and activation vals]. It's cool, but for every convenience we take in the direction HD space we backpeddle in processing [meaning, although the dir structure could be super condensed this way with a learned index, this approach is less flexible to cold or not-cpu-related analysis]. It's very cool actually to consider the three branches of processing, hdd, and memcache ... You want to have a balance but in the ideal computer we do no calculation, and that is something worth mentioning. Reading again of the abstract, allow me to add that it's an optimization beyond structures such as Btrees which are already not really decipherable datasets to the naked eyes. So any optimization in a space that's not designed to be human-legible can take whatever shape, and this is certainly a welcome achievement!

smsx 9y ago
> but in the ideal computer we do no calculation, and that is something worth mentioning Can you expand on this bit? I'm not sure I understand what you mean
- sova 9y ago
  Absolutely! This is a statement on minimization of computational effort. When the solution has already been provided we need not do any calculation. One way to think about the quoted statement and how I meant it is to consider big O notation and how some operations take O(n) or (O lg n) steps dependent on input in order to reach a solution or complete a process or spit out a result; in this hypothetical best case our operations all take O(1). This is not really a calculation but in fact knowledge coming to light. Since writing this comment I have text-to-speech'd the whole of the article and I listened to it one afternoon over smooth classical music and I have come to appreciate the fact that many computers will have neural network processors like tensor processors or at the very least really good GPU, making it all the more likely that such algorithms [especially used in the specific case of fault intolerant data organization and file hierarchy] will actually not require so much computational effort as traditionally believed.

dukeflukem 9y ago

Lapped "overtake (a competitor in a race) to become one or more laps ahead."