《Data & Knowledge Engineering》：When temporary results meet intermediate index: An optimization technique of procedural SQL query processing
编辑推荐：
针对现代数据密集型应用中优化过程式SQL查询的挑战，提出中间索引（intermediate index）和AutoCox优化技术，通过动态评估中间结果的生产者-消费者关系、基数和选择率，结合what-if分析成本模型，实现仅在 beneficial 时创建和自动释放的临时索引，实验显示成本降低67%并提升261倍性能。
Md Arif Rahman | Syed Jalaluddin Hashmi | Kethsiya Gnanajothy | Young-Koo Lee
计算机科学与工程系，庆熙大学，韩国京畿道龙仁市宜兴区Deogyeong-daero 1732号，邮编17104
摘要
在现代数据密集型应用中，由于对存储在临时内存中的中间结果的访问效率低下，优化命令式程序中的过程性SQL查询颇具挑战性。传统的优化技术和基于机器学习的优化技术往往无法为中间结果创建索引，因为它们主要关注之前存储的基础表和声明性查询。然而，对中间结果进行索引可能是进一步降低依赖查询处理成本的潜在解决方案。据我们所知，目前还没有研究考虑过减少依赖于中间结果的依赖查询的处理成本。受此问题的启发，我们引入了“中间索引”这一概念，即在单次程序执行范围内为中间结果创建的临时索引。利用中间索引，我们提出了一种名为AutoCox的过程性SQL查询优化技术，该技术通过一种新颖的假设分析方法来识别和评估索引的好处。AutoCox根据中间结果的生成者-消费者关系、基数和选择性动态确定是否需要创建索引，同时考虑了索引创建的开销和运行时的重用情况。AutoCox确保中间索引包含最新数据，并且仅在有益时创建，使用后自动删除。实验结果表明，我们的方法显著优于现有方法，能够将依赖查询的处理成本降低67%，并将命令式程序的执行速度提高261倍。这表明我们在关系型大数据处理环境中有效地填补了过程性SQL查询优化方面的一个关键空白。
引言
尽管基于机器学习（ML）的查询优化技术取得了最新进展，提供了更好的执行计划，但这些技术仍然依赖于传统的基于成本的优化器来整合基于历史工作负载模式训练的模型[1]、[2]、[3]、[4]、[5]。查询优化器通常处理的是过程性SQL查询，这些查询包含在命令式程序中的声明性SQL查询，例如存储过程和用户定义的函数。这些程序被广泛用于表达复杂的数据转换、封装业务规则和支持可扩展的分析管道。然而，在大数据环境中，优化命令式程序仍然具有挑战性，特别是当中间结果被物化到临时表或表变量中，并被过程性SQL查询反复访问时。如果没有有效的重用策略，这些中间结构往往会引发严重的性能瓶颈。
为了高效处理中间结果，生成者-消费者关系在优化中起着关键作用。语句是处理中间数据源的基本单元，其中生成者语句生成中间结果，然后由消费者语句消费[6]。我们在图1中展示了这个问题。该图显示了一个生成者语句，它从基础表中过滤或聚合数据，并将结果存储在临时表中，随后由一个或多个消费者语句访问。优化这种关系需要在内联和物化之间进行权衡。
为了优化对中间结果的访问，优化器通常依赖于物化的中间结果，将复杂操作分解为可管理的步骤。物化涉及将中间结果存储在临时表或表变量中，然后由多个消费者语句访问。在某些情况下，这种方法比内联（合并生成者和消费者查询）更受欢迎，以避免冗余计算。例如，多个消费者语句访问同一个中间结果。然而，通过优化对中间结果的访问来找到最佳执行计划时，在使用索引访问它们时会遇到独特的挑战。现有的自动索引方法，如AutoAdmin [7]、HypoPG [8]和Oracle Auto Indexing [9]，主要关注声明性查询。它们无法识别命令式程序中的索引。这一限制导致了以下研究目标。
研究问题1：优化器能否使用索引来优化对中间结果的访问？ 使用索引高效优化对中间结果的访问可以提高消费者语句的性能。然而，如果没有适当的索引，由于索引无法辅助消费者语句，性能会下降。
研究问题2：优化器能否估计在中间结果上创建索引的好处？ 由于中间结果的临时性和动态性，对中间结果进行索引并不简单。中间结果是在运行时生成的，并且会根据数据库的当前状态和程序的输入参数而变化。这意味着在程序执行之前无法构建或评估中间结果的索引。因此，为了为消费者语句提供索引的好处，我们必须在无索引的环境中评估创建索引的潜在好处。这需要一种新的假设分析方法，该方法要考虑中间结果的临时性质以及命令式程序范围内创建索引的开销。目前用于评估索引好处的技术，如假设索引方法中的假设分析[10]，是为存储在数据库中的基础表设计的，用于评估工作负载中独立查询的索引好处。它们没有解决命令式程序中中间结果的独特挑战。此外，当前的方法在查询执行范围之外创建索引，忽略了程序内部创建索引的开销。这是一个关键的限制，因为在收益分析中必须考虑在临时表上创建索引的成本。
据我们所知，我们没有找到任何先前研究在命令式程序范围内基于中间结果评估索引创建好处的方法。受此问题的启发，我们引入了“中间索引”的概念，即在生成者语句的中间结果上创建索引，以辅助其消费者语句。该索引利用消费者语句中的过滤和连接条件来提高执行效率。我们提出了一种名为AutoCox的假设分析方法，用于评估命令式程序范围内中间索引的好处。我们在假设分析方法中使用了成本模型来估计创建中间索引的好处。该模型考虑了创建索引的成本（估计在临时表上创建索引的开销）以及消费者语句的成本（估计有无索引时消费者语句的成本），使用了基数估计和过滤及连接条件的选择性估计。
中间索引的好处包括：(i) 它直接针对消费者语句动态优化对中间结果的访问；(ii) 它在生成者语句之后立即创建，确保中间结果不会被其他消费者语句进一步修改；(iii) 它在程序范围内自动创建和删除，确保高效访问而无需长期维护开销。此外，如果将创建中间索引的决定留给依赖于静态索引创建方法的模型训练阶段，由于中间结果对输入参数非常敏感，因此可能会导致不确定的好处。例如，如果某个参数设置的中间结果的基数很大，创建索引可以显著提高性能；相反，如果基数很小，创建和维护索引的开销会超过好处。我们的方法通过提供系统化的决策来评估中间索引的好处，确保只有在它们带来净性能提升时才创建索引。
本研究的核心贡献如下：
- •
引入了中间索引
，这是一种在生成者语句的中间结果上创建的动态索引，以辅助命令式SQL查询范围内的消费者语句。
- •
提出了基于假设
分析的AutoCox
优化技术，我们开发了一个成本模型来估计创建中间索引的好处，从而在训练基于ML的查询优化器时获得更好的执行计划。
- •
通过广泛的实验证明了我们提出方法的有效性。我们展示了与最先进技术相比，我们的方法将命令式程序的性能提高了261倍。
我们按照以下结构组织其余部分：第2节讨论了研究所需的术语。第3节介绍了我们提出的优化方法。第4节展示了我们的实验结果。第5节讨论了相关研究。最后，第6节进行了总结。
节选内容
初步介绍
为了理解我们提出的方法，我们需要知道如何正确表示包含适当跟踪中间结果的过程性SQL查询的执行计划。由于我们提出的方法基于临时结果的物化，其中生成查询没有被内联，因此我们分析了哪些查询被内联和物化。随后，我们提出了中间索引的正式定义以及理解我们的方法所需的基本术语
提出的优化方法
我们的优化过程在优化器确定哪些临时表被内联或物化之后开始。我们应用AutoCox来识别物化临时表上的中间索引。然后它执行假设分析，以评估在物化临时表上创建中间索引的好处。如果发现有益的索引，它将在物理执行计划中的相应语句之后引入。图3展示了我们的方法
实验
我们通过将其与最先进技术和三个不同的数据集进行比较，评估了我们提出的策略在优化物化中间结果方面的有效性。
相关工作
已经进行了许多关于命令式程序优化的相关研究[6]、[16]、[17]、[18]、[19]、[20]。由于这些程序结合了SQL搜索和过程逻辑，因此它们提供了灵活性和可重用性，但也带来了特殊的优化问题[21]、[22]、[23]。多年来，研究人员探索了各种优化命令式程序的策略，如内联和物化
结论
在这项工作中，我们引入了一种考虑消费者行为的自动索引方法，通过策略性地识别模型训练中的中间索引来优化过程性SQL查询的处理。与主要关注静态查询的传统自动索引技术不同，我们的方法通过分析消费者访问行为动态适应执行模式。在我们的成本模型中引入假设分析，确保只有在
CRediT作者贡献声明
Md Arif Rahman：写作——审阅与编辑、撰写原始草案、可视化、软件、方法论、形式分析、数据整理、概念化。Syed Jalaluddin Hashmi：写作——审阅与编辑。Kethsiya Gnanajothy：写作——审阅与编辑。Young-Koo Lee：写作——审阅与编辑、验证、监督、资源管理、项目协调、资金获取。
利益冲突声明
作者声明他们没有已知的财务利益或个人关系可能影响本文报告的工作。
Md Arif Rahman是韩国庆熙大学计算机科学与工程的博士候选人。他于2009年和2011年在孟加拉国的IUT获得了计算机科学的学士和硕士学位。自2012年以来，他一直在Jashore科技大学担任教职，2015年晋升为助理教授。目前，他在Young-Koo Lee教授的数据与知识工程实验室进行研究。他的研究兴趣包括查询处理、学习
