DEX: Query Execution in a Delta-based Storage System
DEX: Query Execution in a Delta-based Storage System
复制标题
DOI：
10.1145/3035918.3064056
复制
发表时间：
2017-05
期刊：
影响因子：
--
通讯作者：
Amit Chavan;A. Deshpande
中科院分区：
文献类型：
--
作者：
Amit Chavan;A. Deshpande
许多领域越来越依赖强大的数据驱动决策，这使得数据管理系统有必要管理数千到数百万个版本的数据集，这些数据集是随着时间的推移在分析管道的各个阶段获取或构建的。 Delta 编码是一种有效且广泛使用的解决方案，可紧凑地存储大量数据集，同时利用数据集之间的冗余并保持重建任何数据集的平均检索成本较低。然而，在此类存储引擎中，除了单个数据集检出之外，支持任何类型的丰富检索或查询功能都具有挑战性。在本文中，我们对这个问题进行了系统的研究，并提出了 DEX，一种新颖的独立的面向增量的执行引擎，其目标是利用数据集之间已计算的增量来进行高效的查询处理。在这项工作中，我们研究如何对基于记录的文件执行结帐、交集、并集和 t 阈值查询；我们表明，即使处理这些基本查询也会带来许多新的、未经探索的挑战和权衡。从将查询执行限制在一小部分增量的查询计划开始，我们引入了基于增量的代数属性的新转换规则，这使我们能够探索替代计划的搜索空间。对于结帐的情况，我们提出了一种动态编程算法，可以在成本模型下有效地选择最佳查询计划，同时我们设计有效的启发式方法来选择有效的计划，这些计划的性能远远优于其他查询的基本结帐然后查询方法。我们的查询执行方法的一个关键特征是，计算成本主要取决于表达式中增量的大小和数量（通常很小），而不是输入数据集版本（可能非常大）。我们在 git（一种广泛使用的版本控制系统）之上实现了 DEX 原型。我们对具有不同特征的合成数据进行了广泛的实验评估，这表明我们的方法与基线相比表现非常好。
The increasing reliance on robust data-driven decision-making across many domains has made it necessary for data management systems to manage many thousands to millions of versions of datasets, acquired or constructed at various stages of analysis pipelines over time. Delta encoding is an effective and widely-used solution to compactly store a large number of datasets, that simultaneously exploits redundancies across them and keeps the average retrieval cost of reconstructing any dataset low. However, supporting any kind of rich retrieval or querying functionality, beyond single dataset checkout, is challenging in such storage engines. In this paper, we initiate a systematic study of this problem, and present DEX, a novel stand-alone delta-oriented execution engine, whose goal is to take advantage of the already computed deltas between the datasets for efficient query processing. In this work, we study how to execute checkout, intersection, union and t-threshold queries over record-based files; we show that processing of even these basic queries leads to many new and unexplored challenges and trade-offs. Starting from a query plan that confines query execution to a small set of deltas, we introduce new transformation rules based on the algebraic properties of the deltas, that allow us to explore the search space of alternative plans. For the case of checkout, we present a dynamic programming algorithm to efficiently select the optimal query plan under our cost model, while we design efficient heuristics to select effective plans that vastly outperform the base checkout-then-query approach for other queries. A key characteristic of our query execution methods is that the computational cost is primarily dependent on the size and the number of deltas in the expression (typically small), and not the input dataset versions (which can be very large). We have implemented DEX prototype on top of git, a widely used version control system. We present an extensive experimental evaluation on synthetic data with diverse characteristics, that shows that our methods perform exceedingly well compared to the baseline.