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

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

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.