Optimally Leveraging Density and Locality to Support LIMIT Queries
Optimally Leveraging Density and Locality to Support LIMIT Queries
复制标题
最佳地利用密度和位置来支持 LIMIT 查询
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Aditya G. Parameswaran
中科院分区：
文献类型：
--
作者：
Albert Kim;Liqi Xu;Tarique Siddiqui;Silu Huang;S. Madden;Aditya G. Parameswaran
现有的数据库系统并没有针对带有LIMIT子句的查询进行优化，而是以全有或全无的方式进行操作。在本文中，我们提出了一个快速的LIMIT查询评估引擎，称为NeedleTail，目的是让分析师浏览一个小样本的查询结果的大数据集，尽可能快，独立的结果集的整体大小。NeedleTail引入了密度图，一个轻量级的内存索引结构，以及一组高效的算法（具有理想的理论保证）来快速定位有希望的块，权衡局部性和密度。在使用样本计算总量的设置中，我们扩展了调查抽样的技术，以减轻样本中的偏差。我们的实验结果表明，NeedleTail在HDD上返回结果的速度平均快4倍，在SSD上快9倍，同时占用的内存比现有技术少23倍。
Existing database systems are not optimized for queries with a LIMIT clause---operating instead in an all-or-nothing manner. In this paper, we propose a fast LIMIT query evaluation engine, called NeedleTail, aimed at letting analysts browse a small sample of the query results on large datasets as quickly as possible, independent of the overall size of the result set. NeedleTail introduces density maps, a lightweight in-memory indexing structure, and a set of efficient algorithms (with desirable theoretical guarantees) to quickly locate promising blocks, trading off locality and density. In settings where the samples are used to compute aggregates, we extend techniques from survey sampling to mitigate the bias in our samples. Our experimental results demonstrate that NeedleTail returns results 4x faster on HDDs and 9x faster on SSDs on average, while occupying up to 23x less memory than existing techniques.