标题： 基于成本的数据跳过起源草图选择 显示英文标题

标题： Cost-based Selection of Provenance Sketches for Data Skipping

摘要： 数据出处速写是一种轻量级索引，用于记录回答查询所需的（相关的）数据，它可以显著提升一类重要查询（例如包含HAVING子句和top-k查询）的性能。给定一张表的水平划分，查询Q的数据出处速写会记录哪些片段包含数据出处。 一旦为查询捕获了数据出处速写，就可以通过跳过不属于速写的那些数据来加速后续查询。数据出处速写大小以及因此其有效性往往对分区所依据的属性选择非常敏感。 在这项工作中，我们开发了基于采样的估算技术，以估计数据出处速写的大小，类似于一种特殊的近似查询处理形式。这种技术使得能够在线选择数据出处速写，通过估算一组候选属性的速写大小，然后创建预计能带来最大收益的速写。 我们实验表明，我们的估算足够准确，在大多数情况下可以选择最优或接近最优的数据出处速写，从而与其它选择数据出处速写策略相比，运行时间最多可以提高60%。 显示英文摘要

摘要： Provenance sketches, light-weight indexes that record what data is needed (is relevant) for answering a query, can significantly improve performance of important classes of queries (e.g., HAVING and top-k queries). Given a horizontal partition of a table, a provenance sketch for a query Q records which fragments contain provenance. Once a provenance sketch has been captured for a query, it can be used to speed-up subsequent queries by skipping data that does not belong to a sketch. The size and, thus, also the effectiveness of a provenance sketch is often quite sensitive to the choice of attribute(s) we are partitioning on. In this work, we develop sample-based estimation techniques for the size of provenance sketches akin to a specialized form of approximate query processing. This technique enables the online selection of provenance sketches by estimating the size of sketches for a set of candidate attributes and then creating the sketch that is estimated to yield the largest benefit. We demonstrate experimentally that our estimation is accurate enough to select optimal or near optimal provenance sketches in most cases which in turn leads to a runtime improvement of up to %60 compared to other strategies for selecting provenance sketches.