ALERT:基于Radix Tree的工作负载自适应学习型索引
作者:
作者单位:

作者简介:

陈井爽(1996-),男,硕士,主要研究领域为数据库系统;江大伟(1982-),男,博士,研究员,博士生导师,主要研究领域为分布式数据库技术,云数据管理技术,大数据管理技术,区块链技术;陈珂(1977-),女,博士,副研究员,CCF专业会员,主要研究领域为数据库系统,大数据技术,隐私保护;陈刚(1973-),男,博士,教授,博士生导师,CCF杰出会员,主要研究领域为数据库系统,大数据技术,数据智能计算;寿黎但(1974-),男,博士,教授,博士生导师,CCF高级会员,主要研究领域为数据库系统,数据智能技术,数据挖掘.

通讯作者:

寿黎但,E-mail:should@zju.edu.cn

中图分类号:

TP311

基金项目:

浙江省重点研发计划(2021C01009);国家自然科学基金(62050099);浙江省自然科学基金(LY18F020005)


ALERT: Workload-adaptive Learned Index Based on Radix Tree
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    学习型索引通过学习数据分布可以准确地预测数据存取的位置,在保持高效稳定的查询下,显著降低索引的内存占用.现有的学习型索引主要针对只读查询进行优化,而对插入和更新支持不足.针对上述挑战,设计了一种基于Radix Tree的工作负载自适应学习型索引ALERT.ALERT使用Radix Tree来管理不定长的分段,段内采用具有最大误差界的线性插值模型进行预测.同时,ALERT使用一种高效的插入缓冲来降低数据插入更新的代价.针对点查询和范围查询提出两种自适应重组优化方法,通过对工作负载进行感知,动态地调整插入缓冲的组织结构.经实验验证,ALERT与业界流行的学习型索引相比,构建时间平均降低了81%,内存占用平均降低了75%,在保持了优秀读性能的同时,使插入延迟平均降低了50%;此外,ALERT使用自适应重组优化能有效感知查询工作负载特征,与不使用自适应重组优化相比,查询延迟平均降低了15%.

    Abstract:

    Learned indexes are capable of predicting the accurate location of data in storage by learning the data distribution. These indexes can significantly reduce storage consumption while providing efficient query processing. Existing learned indexes are mostly optimized for read-only queries, but inadequate in supporting insertions and updates. In an attempt to address the challenges faced by learned index, this study proposes a workload-adaptive learned index named ALERT. Generally, ALERT employs a Radix Tree to manage variable-length segments, where each segment contains a linear interpolation model with a maximum error-bound. Meanwhile, ALERT utilizes an insertion memory buffer to reduce the cost of updates. Following the database-cracking approach, the study proposes adaptive index maintenance during the run-time processing of point queries and range queries. The maintenance technique is implemented by performing workload-aware dynamic re-organization on the insertion buffer. Experimental results confirm that, when compared to state-of-the-art learned index, ALERT achieves competitive results as it reduces the index's average construction time by 81%, the average memory utilization by 75%, the average latency of insert by 50%, while maintaining competitive read performances. The average query latency of ALERT is also reduced by 15%, owing to its effective workload-aware optimization.

    参考文献
    相似文献
    引证文献
引用本文

陈井爽,陈珂,寿黎但,江大伟,陈刚. ALERT:基于Radix Tree的工作负载自适应学习型索引.软件学报,2022,33(12):4688-4703

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2021-01-26
  • 最后修改日期:2021-04-12
  • 录用日期:
  • 在线发布日期: 2022-05-24
  • 出版日期: 2022-12-06
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号