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，这是一个可以集成到现有和新颖的数据库服务器中的开源查询优化器。由于广泛使用现代生活的许多领域的数据库，最佳查询可以为整个Society.compass带来好处，这是一个在线查询优化器，它专门使用素描概要，以找到最佳的执行计划。草图是使用较小空间的基数估计的相关概念，可以在数据上进行单个扫描，可有效地计算出数据，是可线的组合，并且具有统计上很高的精度。 Compass在现代数据库中使用并行执行引擎在运行时计算草图。通过将查询处理分解为两个阶段，在优化之前和之后执行。在第一个执行阶段，选择谓词被推入，草图仅在相关的元组上构建。通过逐步构成双向联接草图，以估算多路连接的基数，通过加入图表进行计划枚举。该计划在第二处理阶段执行。整体指南针方法在查询优化器的所有组成部分中介绍了新方法 - 选择选择，双向和多路连接的基数估计；计划枚举；和成本模型。除了算法方面，这些方法还涉及高度并行体系结构的繁重工程实践。具体而言，由于其应用于许多其他数据处理任务，因此并行随机数生成方案远远超出了草图。这也适用于图形遍历算法。将草图对多路加入估计的概括本身具有智力价值，因为这是一个理论上的开放问题。由于草图是原始的流算法，因此该项目中所做的贡献也直接适用于该领域。该奖项反映了NSF的法定任务，并且使用基金会的知识分子优点和更广泛的审查标准，认为值得通过评估来获得支持。