论文标题
数据库查询处理中的偏移值编码
Offset-value coding in database query processing
论文作者
论文摘要
最近的工作表明，偏移值编码如何加快数据库查询执行的速度，不仅排序，而且在排序流中的重复删除和分组（聚集），订单保留交换（shuffle），合并加入等等。它已经在Google的NAPA和F1查询系统中节省了数千个CPU，例如在分组算法和日志结构合并方面。 但是，为了实现有趣的订单的全部好处，查询执行算法不仅必须消耗和利用偏移值代码，还必须为管道中的下一个操作员生成偏置值代码。我们的研究已寻求方法来生成偏移值代码，而不比较连续的输出行一对一，列列。这篇简短的论文介绍了一种新的定理，并基于其证明和简单的推论，详细描述了订单保留算法如何（从过滤器到合并连接甚至混合甚至散发）如何计算其输出的偏移值代码。这些计算令人惊讶地简单且非常有效。
Recent work shows how offset-value coding speeds up database query execution, not only sorting but also duplicate removal and grouping (aggregation) in sorted streams, order-preserving exchange (shuffle), merge join, and more. It already saves thousands of CPUs in Google's Napa and F1 Query systems, e.g., in grouping algorithms and in log-structured merge-forests. In order to realize the full benefit of interesting orderings, however, query execution algorithms must not only consume and exploit offset-value codes but also produce offset-value codes for the next operator in the pipeline. Our research has sought ways to produce offset-value codes without comparing successive output rows one-by-one, column-by-column. This short paper introduces a new theorem and, based on its proof and a simple corollary, describes in detail how order-preserving algorithms (from filter to merge join and even shuffle) can compute offset-value codes for their outputs. These computations are surprisingly simple and very efficient.
