Bitvector-aware Query Optimization for Decision Support Queries
Bitvector-aware Query Optimization for Decision Support Queries
复制标题
用于决策支持查询的位向量感知查询优化
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Vivek R. Narasayya
中科院分区：
文献类型：
--
作者：
B. Ding;S. Chaudhuri;Vivek R. Narasayya
位向量过滤是一种重要的查询处理技术，可以显著降低执行成本，特别是对于具有多个连接的复杂决策支持查询。尽管其广泛的应用，但是，它的含义查询优化并没有得到很好的理解。在这项工作中，我们研究了位向量过滤器如何影响查询优化。我们表明，直接将位向量过滤器的查询优化可以增加计划空间的复杂性的查询中的关系的数量的指数因子。我们分析的计划与位向量过滤器的星星和雪花查询的右深树没有交叉产品的计划空间。令人惊讶的是，通过一些简化的假设，我们证明了，可以从查询中的关系数量中的线性数量的计划中找到具有位向量过滤器的最小成本的计划。这大大降低了这种查询的计划空间复杂度，从指数到线性。出于我们的分析，我们提出了一个算法，占位向量过滤器在查询优化的影响。我们的算法优化了连接顺序的任意决策支持查询选择从一个线性数量的候选计划在查询中的关系的数量。我们实现了我们的算法在商业数据库DBMS-X的转换规则。我们对行业标准基准测试和客户工作负载的评估表明，与DBMS-X相比，我们的技术将工作负载的总CPU执行时间减少了22%-64%，单个查询的CPU执行时间减少了两个数量级。
Bitvector filtering is an important query processing technique that can significantly reduce the cost of execution, especially for complex decision support queries with multiple joins. Despite its wide application, however, its implication to query optimization is not well understood. In this work, we study how bitvector filters impact query optimization. We show that incorporating bitvector filters into query optimization straightforwardly can increase the plan space complexity by an exponential factor in the number of relations in the query. We analyze the plans with bitvector filters for star and snowflake queries in the plan space of right deep trees without cross products. Surprisingly, with some simplifying assumptions, we prove that, the plan of the minimal cost with bitvector filters can be found from a linear number of plans in the number of relations in the query. This greatly reduces the plan space complexity for such queries from exponential to linear. Motivated by our analysis, we propose an algorithm that accounts for the impact of bitvector filters in query optimization. Our algorithm optimizes the join order for an arbitrary decision support query by choosing from a linear number of candidate plans in the number of relations in the query. We implement our algorithm in a commercial database DBMS-X as a transformation rule. Our evaluation on both industry standard benchmarks and customer workload shows that, compared with DBMS-X, our technique reduces the total CPU execution time by 22%-64% for the workloads, with up to two orders of magnitude reduction in CPU execution time for individual queries.