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方法在查询优化器的所有组件中引入了新的方法-选择、双向和多向连接的基数估计;计划枚举;以及成本模型。除了算法方面，这些方法涉及高度并行架构上的繁重工程实践。具体而言，并行随机数生成方案远远超出草图，由于其应用到许多其他数据处理任务。这也适用于图遍历算法。将草图推广到多路连接估计本身具有智力价值，因为这是一个理论上的开放问题。由于草图最初是流算法，因此在该项目中所做的贡献也直接适用于该领域。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估而被认为值得支持。