Filter Representation in Vectorized Query Execution
Filter Representation in Vectorized Query Execution
复制标题
DOI：
10.1145/3465998.3466009
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
Amadou Latyr Ngom;Prashanth Menon;Matthew Butrovich;Lin Ma;Wan Shen Lim;T. Mowry;Andrew Pavlo
中科院分区：
文献类型：
--
作者：
Amadou Latyr Ngom;Prashanth Menon;Matthew Butrovich;Lin Ma;Wan Shen Lim;T. Mowry;Andrew Pavlo
内存技术的进步使数据库管理系统（DBMS）将其工作数据集存储在主内存中。这种趋势将查询执行的瓶颈从磁盘访问到CPU效率。提高CPU效率的一种技术是面向批处理的处理或矢量化，因为它可以减少开销的解释。对于每个元组的每个向量（批次），DBM必须跟踪在所有先前的处理步骤中幸存下来的有效（可见）元组集。为此，现有系统采用了两个数据结构之一或过滤表示：选择向量或位图。在这项工作中，我们分析了每种方法的优势和劣势，并提供有关如何实施矢量操作的建议。通过广泛的微基准测试，我们确定最佳策略是许多因素的函数：通过元组迭代的成本，操作本身的成本以及SIMD矢量化是多么可观。我们的分析表明，对于可以使用SIMD指令进行矢量化的操作，位图表现更好，并且由于较便宜的迭代逻辑，选择向量在所有其他操作上都表现更好。
Advances in memory technology have made it feasible for database management systems (DBMS) to store their working data set in main memory. This trend shifts the bottleneck for query execution from disk accesses to CPU efficiency. One technique to improve CPU efficiency is batch-oriented processing, or vectorization, as it reduces interpretation overhead. For each vector (batch) of tuples, the DBMS must track the set of valid (visible) tuples that survive all previous processing steps. To that end, existing systems employ one of two data structures, or filter representations: selection vectors or bitmaps. In this work, we analyze each approach's strengths and weaknesses and offer recommendations on how to implement vectorized operations. Through a wide range of micro-benchmarks, we determine that the optimal strategy is a function of many factors: the cost of iterating through tuples, the cost of the operation itself, and how amenable it is to SIMD vectorization. Our analysis shows that bitmaps perform better for operations that can be vectorized using SIMD instructions and that selection vectors perform better on all other operations due to cheaper iteration logic.