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

数据库系统试图保护用户免受复杂的数据处理的影响。用户在高抽象级别上指定查询，描述所需的结果而不是生成结果的方式。因此，对于给定的查询，数据库系统需要自动找到有效的数据处理计划。这些计划是根据有关查询和数据的简化假设生成的。很多时候，这些假设被证明过于简单，并且生成的计划无法在合理的处理时间内完成。在这种情况下，必须根据专业知识手动生成有效的加工计划。这给雇用数据库专家的组织带来了高昂的管理费​​用。无法获得此类专业知识的外行用户可能无法完全执行某些查询。拟议的项目将通过一种新颖的计划生成方法来克服这些挑战。这种方法没有做出简化的假设，因此保证了接近最优的计划。所提出的工作将探索“查询内学习”的潜力，这是一种结合查询执行和计划生成的新方法。查询内学习将单个查询的执行划分为许多微片段，在这些微片段中尝试不同的计划。每集都有两个目的。首先，它生成查询结果片段，这些片段将被收集以形成完整的查询结果。其次，它提供有关计划替代方案质量的信息。该信息将用于为剩余剧集选择更好的计划。该项目将使用强化学习领域的方法来选择每集的计划。这些方法为在不确定性下做出接近最优的决策提供了正式的保证。该项目将把这种保证转化为对接近最优的预期处理成本的保证。研究成果将集成到 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.