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

III：小：通过强化学习进行遗憾限制查询评估

• 批准号: 1910830
• 负责人: Immanuel Trummer
• 金额: $ 50万
• 依托单位: Cornell University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-08-01 至 2022-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1910830&HistoricalAwards=false
• 关键词: III; Small; Regret; Bounded; Query

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.

数据库系统试图保护其用户免受数据处理的复杂性。用户以高水平的抽象来指定查询，描述所需的结果，而不是生成的方式。因此，给定查询，数据库系统需要自动找到有效的数据处理计划。这些计划是基于简化有关查询和数据的假设而生成的。这些假设常常过于简单，而生成的计划并不能在合理的处理时间内完成。在这种情况下，必须根据专家知识手动生成有效的处理计划。这为采用数据库专家的组织创造了高间接费用。无法访问此类专业知识的外行用户可能无法完全执行某些查询。拟议的项目将通过一种新颖的计划生成方法来克服这些挑战。这种方法没有简化的假设，因此可以保证近乎最佳的计划。拟议的工作将探索“疑问学习”的潜力，这是一种结合查询执行和计划生成的新方法。 Query-Query学习将单个查询的执行划分为尝试尝试不同计划的许多微观情节。每个情节都有两个目的。首先，它生成查询结果片段，这些片段将被收集以形成完整的查询结果。其次，它产生有关计划替代品质量的信息。将利用此信息为其余情节选择更好的计划。该项目将使用加强学习领域的方法在每个情节中选择计划。这些方法为在不确定性下做出近乎最佳的决定提供了正式的保证。该项目将把此类保证转化为近乎预期的处理成本的保证。研究结果将集成到SkinnerDB，这是一个新型的数据库系统，从头开始，无需手动干预即可进行稳健的性能。 SkinnerDB将完全放弃工具，例如粗粒数据统计信息，或简化传统上用于选择查询计划的成本和基数模型。取而代之的是，它将仅依赖于增强学习，并与执行引擎相结合，该执行引擎量身定制的，该引擎是根据疑问学习的需求而定制的。这将使IT能够从头开始学习近乎最佳的计划，即使是在新鲜加载数据上执行或包含新引入的用户定义功能的查询。从首次显示出令人鼓舞的性能的方法开始，该项目将探索各种扩展，例如平行和分布式处理，查询计划编译以及基于磁盘的数据处理。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的知识分子优点和更广泛的审查标准通过评估来获得支持的。

项目成果

SkinnerDB: Regret-bounded Query Evaluation via Reinforcement Learning

• DOI: 10.1145/3464389
• 发表时间: 2021-09
• 期刊: ACM Transactions on Database Systems (TODS)
• 作者: Immanuel Trummer;Junxiong Wang;Ziyun Wei;Deepak Maram;Samuel Moseley;Saehan Jo;Joseph Antonakakis;Ankush Rayabhari

Building learned federated query optimizers

构建学习型联合查询优化器

• 发表时间: 2022
• 期刊: CEUR workshop proceedings
• 作者: Victor Giannakouris, Immanuel Trummer

Procrastinated Tree Search: Black-box Optimization with Delayed, Noisy, and Multi-fidelity Feedback

• DOI: 10.1609/aaai.v36i9.21280
• 发表时间: 2021-10
• 作者: Junxiong Wang;D. Basu;Immanuel Trummer

UDO: Universal Database Optimization using Reinforcement Learning

• DOI: 10.14778/3484224.3484236
• 发表时间: 2021-04
• 期刊: Proc. VLDB Endow.
• 作者: Junxiong Wang;Immanuel Trummer;D. Basu

Demonstrating UDO: A Unified Approach for Optimizing Transaction Code, Physical Design, and System Parameters via Reinforcement Learning

演示 UDO：通过强化学习优化交易代码、物理设计和系统参数的统一方法

• DOI: 10.1145/3448016.3452754
• 发表时间: 2021
• 期刊: Proceedings of the 2021 International Conference on Management of Data
• 作者: Wang, Junxiong;Trummer, Immanuel;Basu, Debabrota
• 通讯作者: Basu, Debabrota