The Case for Learned Index Structures
© 2018 Association for Computing Machinery. Indexes are models: a B-Tree-Index can be seen as a model to map a key to the position of a record within a sorted array, a Hash-Index as a model to map a key to a position of a record within an unsorted array, and a BitMap-Index as a model to indicate if...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Association for Computing Machinery (ACM)
2021
|
| Online Access: | https://hdl.handle.net/1721.1/132272 |
| _version_ | 1826207009598341120 |
|---|---|
| author | Kraska, Tim Beutel, Alex Chi, Ed H Dean, Jeffrey Polyzotis, Neoklis |
| author_facet | Kraska, Tim Beutel, Alex Chi, Ed H Dean, Jeffrey Polyzotis, Neoklis |
| author_sort | Kraska, Tim |
| collection | MIT |
| description | © 2018 Association for Computing Machinery. Indexes are models: a B-Tree-Index can be seen as a model to map a key to the position of a record within a sorted array, a Hash-Index as a model to map a key to a position of a record within an unsorted array, and a BitMap-Index as a model to indicate if a data record exists or not. In this exploratory research paper, we start from this premise and posit that all existing index structures can be replaced with other types of models, including deep-learning models, which we term learned indexes. We theoretically analyze under which conditions learned indexes outperform traditional index structures and describe the main challenges in designing learned index structures. Our initial results show that our learned indexes can have significant advantages over traditional indexes. More importantly, we believe that the idea of replacing core components of a data management system through learned models has far reaching implications for future systems designs and that this work provides just a glimpse of what might be possible. |
| first_indexed | 2024-09-23T13:42:22Z |
| format | Article |
| id | mit-1721.1/132272 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T13:42:22Z |
| publishDate | 2021 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/1322722021-09-21T03:27:35Z The Case for Learned Index Structures Kraska, Tim Beutel, Alex Chi, Ed H Dean, Jeffrey Polyzotis, Neoklis © 2018 Association for Computing Machinery. Indexes are models: a B-Tree-Index can be seen as a model to map a key to the position of a record within a sorted array, a Hash-Index as a model to map a key to a position of a record within an unsorted array, and a BitMap-Index as a model to indicate if a data record exists or not. In this exploratory research paper, we start from this premise and posit that all existing index structures can be replaced with other types of models, including deep-learning models, which we term learned indexes. We theoretically analyze under which conditions learned indexes outperform traditional index structures and describe the main challenges in designing learned index structures. Our initial results show that our learned indexes can have significant advantages over traditional indexes. More importantly, we believe that the idea of replacing core components of a data management system through learned models has far reaching implications for future systems designs and that this work provides just a glimpse of what might be possible. 2021-09-20T18:21:36Z 2021-09-20T18:21:36Z 2021-01-11T14:49:33Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/132272 en 10.1145/3183713.3196909 Proceedings of the ACM SIGMOD International Conference on Management of Data Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery (ACM) ACM |
| spellingShingle | Kraska, Tim Beutel, Alex Chi, Ed H Dean, Jeffrey Polyzotis, Neoklis The Case for Learned Index Structures |
| title | The Case for Learned Index Structures |
| title_full | The Case for Learned Index Structures |
| title_fullStr | The Case for Learned Index Structures |
| title_full_unstemmed | The Case for Learned Index Structures |
| title_short | The Case for Learned Index Structures |
| title_sort | case for learned index structures |
| url | https://hdl.handle.net/1721.1/132272 |
| work_keys_str_mv | AT kraskatim thecaseforlearnedindexstructures AT beutelalex thecaseforlearnedindexstructures AT chiedh thecaseforlearnedindexstructures AT deanjeffrey thecaseforlearnedindexstructures AT polyzotisneoklis thecaseforlearnedindexstructures AT kraskatim caseforlearnedindexstructures AT beutelalex caseforlearnedindexstructures AT chiedh caseforlearnedindexstructures AT deanjeffrey caseforlearnedindexstructures AT polyzotisneoklis caseforlearnedindexstructures |