Detailed Information

ALEX: An Updatable Adaptive Learned Index

Cited 97 time in Web of Science Cited 144 time in Scopus

Ding, Jialin; Minhas, Umar Farooq; Yu, Jia; Wang, Chi; Do, Jae Young; Li, Yinan; Zhang, Hantian; Chandramouli, Badrish; Gehrke, Johannes; Kossmann, Donald; Lomet, David; Kraska, Tim

Issue Date
Association for Computing Machinery
SIGMOD'20 : proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, pp.969-984
Recent work on "learned indexes" has changed the way we look at the decades-old field of DBMS indexing. The key idea is that indexes can be thought of as "models" that predict the position of a key in a dataset. Indexes can, thus, be learned. The original work by Kraska et al. shows that a learned index beats a B+Tree by a factor of up to three in search time and by an order of magnitude in memory footprint. However, it is limited to static, read-only workloads. In this paper, we present a new learned index called ALEX which addresses practical issues that arise when implementing learned indexes for workloads that contain a mix of point lookups, short range queries, inserts, updates, and deletes. ALEX effectively combines the core insights from learned indexes with proven storage and indexing techniques to achieve high performance and low memory footprint. On read-only workloads, ALEX beats the learned index from Kraska et al. by up to 2.2x on performance with up to 15x smaller index size. Across the spectrum of read-write workloads, ALEX beats B+Trees by up to 4.1x while never performing worse, with up to 2000x smaller index size. We believe ALEX presents a key step towards making learned indexes practical for a broader class of database workloads with dynamic updates.
Files in This Item:
There are no files associated with this item.
Appears in Collections:

Related Researcher

  • College of Engineering
  • Department of Electrical and Computer Engineering
Research Area AI 애플리케이션을 위한 알고리즘-시스템 공동 설계, AI-powered Big Data Management, Generative AI, Large Language Model, ML, 고성능 대규모 AI 데이터 분석 및 처리, 모달 AI


Item View & Download Count

  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.