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

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

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.