III: Small: Regret-Bounded Query Evaluation via Reinforcement Learning

数据库系统试图保护其用户不受复杂数据处理的影响。用户在高抽象层次上指定查询，描述所需的结果，而不是生成结果的方式。因此，给定一个查询，数据库系统需要自动找到有效的数据处理计划。这些计划是基于对查询和数据的简化假设生成的。通常情况下，这些假设被证明过于简单，生成的计划不能在合理的处理时间内完成。在这种情况下，必须根据专家知识手动生成有效的处理计划。这给雇用数据库专家的组织带来了很高的开销。没有这种专业知识的外行用户可能无法完全执行某些查询。拟议的项目将通过一种新的规划生成方法来克服这些挑战。这种方法没有简化假设，因此保证了接近最优的计划。提出的工作将探索“查询内学习”的潜力，这是一种结合查询执行和计划生成的新方法。查询内学习将单个查询的执行分成许多微集，在这些微集中尝试不同的计划。每一集都有两个目的。首先，它生成查询结果片段，这些片段将被收集以形成完整的查询结果。其次，它提供了关于计划备选方案质量的信息。这些信息将被用来为剩下的剧集选择更好的计划。该项目将使用强化学习领域的方法来选择每一集的计划。这些方法提供了在不确定情况下做出接近最优决策的正式保证。本项目将把这种保证转化为对接近最优预期加工成本的保证。研究成果将集成到SkinnerDB中，这是一个全新的数据库系统，从底层开始设计，无需人工干预即可实现强大的性能。SkinnerDB将完全放弃诸如粗粒度数据统计或简化成本和基数模型之类的工具，这些工具通常用于选择查询计划。相反，它将完全依赖于强化学习，并结合针对查询内学习需求量身定制的执行引擎。这将使它能够从头开始学习近乎最优的计划，甚至对于在新加载的数据上执行的查询或包含新引入的用户定义函数。从第一种表现出良好性能的方法开始，该项目将探索各种扩展，如并行和分布式处理、查询计划编译和基于磁盘的数据处理。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Database systems try to shield their users from the intricacies of data processing. Users specify queries at a high level of abstraction, describing desired results rather than the way in which they are generated. Hence, given a query, database systems need to find efficient data processing plans automatically. Those plans are generated based on simplifying assumptions about queries and data. All too often, those assumptions turn out to be overly simplistic and generated plans do not finish within reasonable amounts of processing time. In such cases, efficient processing plans must be generated manually, based on expert knowledge. This creates high overheads for organizations which employ database experts. Laymen users who have no access to such expertise may be unable to execute certain queries altogether. The proposed project will overcome those challenges by a novel approach to plan generation. This approach makes no simplifying assumptions and therefore guarantees near-optimal plans.The proposed work will explore the potential for "intra-query learning," a new approach combining query execution and plan generation. Intra-query learning divides the execution of a single query into many micro-episodes in which different plans are tried. Each episode serves two purposes. First, it generates query result fragments that will be collected to form complete query results. Second, it yields information on the quality of plan alternatives. This information will be leveraged to select better plans for the remaining episodes. The project will use methods from the area of reinforcement learning to select plans in each episode. Those methods offer formal guarantees on making near-optimal decisions under uncertainty. This project will translate such guarantees into guarantees on near-optimal expected processing cost. The research outcomes will be integrated into SkinnerDB, a novel database system designed from the ground up for robust performance without manual interventions. SkinnerDB will entirely abandon tools such as coarse-grained data statistics, or simplifying cost and cardinality models, that are traditionally used to select query plans. Instead, it will rely exclusively on reinforcement learning in combination with an execution engine that is tailored to the needs of intra-query learning. This will enable it to learn near-optimal plans from scratch even for queries that execute on freshly loaded data or contain newly introduced user-defined functions. Starting from a first approach showing promising performance, the project will explore various extensions such as parallel and distributed processing, query plan compilation, and disk-based data processing.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.