III: Small: COMPASS: Online Sketch-based Query Optimization for In-Memory Databases

III：小：COMPASS：内存数据库基于草图的在线查询优化

• 批准号: 2008815
• 负责人: Florin Rusu
• 金额: $ 49.99万
• 依托单位: University of California - Merced
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-10-01 至 2024-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2008815&HistoricalAwards=false
• 关键词: III; Small; COMPASS; Online; Sketch

The query optimizer is a core component of database servers, which represent one of the most successful products of the software industry, adopted massively both across business enterprises and in scientific projects ranging from astronomy to genomics. Despite this success and decades of work, query optimization is still far from solved. The main reasons are the complexity of the problem and the fast pace of hardware development, which makes query optimization a continuously moving target. In this project, the researchers investigate how to design COMPASS, a lightweight, yet effective, query optimizer for modern databases based on two design principles. The first principle is to capitalize on highly-parallel computing architectures in query optimization, while the second is to simplify the type and number of synopses included in the optimizer. The final goal is to build COMPASS, an open-source query optimizer that can be integrated into existing and novel database servers. Due to the extensive use of databases across many domains of modern life, optimal querying can bring benefits to the entire society.COMPASS is an online query optimizer that uses sketch synopses exclusively in order to find optimal execution plans. Sketches are correlated synopses for cardinality estimation that use small space, can be computed efficiently in a single scan over the data, are linearly composable, and have statistically high accuracy. COMPASS uses the parallel execution engine in modern databases to compute sketches at runtime. This is realized by decomposing query processing into two stages, performed before and after optimization. In the first execution stage, selection predicates are pushed-down and sketches are built only over the relevant tuples. Plan enumeration is performed over the join graph by incrementally composing two-way join sketches in order to estimate the cardinality of multi-way joins. The plan is executed in the second processing stage. The holistic COMPASS approach introduces novel methods in all the components of the query optimizer---cardinality estimation for selections, two-way, and multi-way joins; plan enumeration; and cost models. In addition to the algorithmic aspects, these methods involve heavy engineering practices on highly-parallel architectures. Specifically, parallel random number generation schemes go well beyond sketches due to their application to many other data processing tasks. This is also applicable to graph traversal algorithms. The generalization of sketches to multi-way join estimation has intellectual value by itself because this is a theoretical open problem. Since sketches are streaming algorithms at origin, the contributions made in this project are also directly applicable to this area.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

查询优化器是数据库服务器的核心组件，它代表了软件行业最成功的产品之一，在商业企业和从天文学到基因组学的科学项目中广泛采用。尽管取得了如此成功并且经过了数十年的努力，查询优化仍然远未得到解决。主要原因是问题的复杂性和硬件开发的快节奏，这使得查询优化成为一个不断移动的目标。在这个项目中，研究人员研究了如何设计 COMPASS，这是一个基于两个设计原则的轻量级但有效的现代数据库查询优化器。第一个原则是在查询优化中利用高度并行的计算架构，而第二个原则是简化优化器中包含的概要的类型和数量。最终目标是构建 COMPASS，一个可以集成到现有和新型数据库服务器中的开源查询优化器。由于数据库在现代生活的许多领域中得到广泛使用，最佳查询可以为整个社会带来好处。COMPASS 是一个在线查询优化器，专门使用草图概要来找到最佳执行计划。草图是基数估计的相关概要，它使用较小的空间，可以在对数据的单次扫描中有效地计算，是线性可组合的，并且具有统计上的高精度。 COMPASS 使用现代数据库中的并行执行引擎在运行时计算草图。这是通过将查询处理分解为两个阶段来实现的，分别在优化之前和之后执行。在第一个执行阶段，选择谓词被下推，草图仅在相关元组上构建。通过增量地组合双向连接草图来对连接图执行计划枚举，以估计多路连接的基数。该计划在第二处理阶段执行。整体COMPASS方法在查询优化器的所有组件中引入了新颖的方法——选择、双向和多路连接的基数估计；计划枚举；和成本模型。除了算法方面之外，这些方法还涉及高度并行架构上的大量工程实践。具体来说，并行随机数生成方案远远超出了草图，因为它们适用于许多其他数据处理任务。这也适用于图遍历算法。将草图推广到多路连接估计本身就具有智力价值，因为这是一个理论上的开放问题。由于 sketches 最初是流式算法，因此该项目中所做的贡献也直接适用于该领域。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。