Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads

被引:68
作者
Ding, Jialin [1 ]
Nathan, Vikram [1 ]
Alizadeh, Mohammad [1 ]
Kraska, Tim [1 ]
机构
[1] MIT, Cambridge, MA 02139 USA
来源
PROCEEDINGS OF THE VLDB ENDOWMENT | 2020年 / 14卷 / 02期
关键词
TREE;
D O I
10.14778/3425879.3425880
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
Filtering data based on predicates is one of the most fundamental operations for any modern data warehouse. Techniques to accelerate the execution of filter expressions include clustered indexes, specialized sort orders (e.g., Z-order), multi-dimensional indexes, and, for high selectivity queries, secondary indexes. However, these schemes are hard to tune and their performance is inconsistent. Recent work on learned multi-dimensional indexes has introduced the idea of automatically optimizing an index for a particular dataset and workload. However, the performance of that work suffers in the presence of correlated data and skewed query workloads, both of which are common in real applications. In this paper, we introduce Tsunami, which addresses these limitations to achieve up to 6x faster query performance and up to 8x smaller index size than existing learned multi-dimensional indexes, in addition to up to 11x faster query performance and 170x smaller index size than optimally-tuned traditional indexes.
引用
收藏
页码:74 / 86
页数:13
相关论文
共 48 条
[1]  
AmazonAWS, 2016, AM REDSH ENG ADV TAB
[2]  
[Anonymous], 2004, P ACM SIGMOD INT C M, DOI DOI 10.1145/1007568
[3]  
[Anonymous], SPAT IND
[4]  
[Anonymous], 1980, OCTREE ENCODING NEW
[5]  
[Anonymous], 2017, Z-order indexing for multifaceted queries in amazon dynamodb
[6]  
[Anonymous], 2009, Proc. VLDB Endow., DOI DOI 10.14778/1687627.1687765
[7]  
Atikoglu Berk, 2012, Performance Evaluation Review, V40, P53, DOI 10.1145/2318857.2254766
[8]  
Bayer Rudolf., 2000, P 26 INT C VER LARG
[9]  
BECKMANN N, 1990, SIGMOD REC, V19, P322, DOI 10.1145/93605.98741
[10]   MULTIDIMENSIONAL BINARY SEARCH TREES USED FOR ASSOCIATIVE SEARCHING [J].
BENTLEY, JL .
COMMUNICATIONS OF THE ACM, 1975, 18 (09) :509-517