文章：Query Rewriting via Large Language Models，https://arxiv.org/abs/2403.09060

摘要

查询重写是在将查询传递给查询优化器之前处理编写不良的查询的最有效技术之一。 手动重写不可扩展，因为它容易出错并且需要深厚的专业知识。 类似地，传统的查询重写算法只能处理一小部分查询：基于规则的技术不能推广到新的查询模式，并且基于综合的技术无法处理复杂的查询。 幸运的是，大型语言模型（大语言模型）的兴起，配备了广泛的常识和先进的推理能力，为解决一些以前未解决的问题带来了希望。

在本文中，我们提出了GenRewrite，这是第一个利用大语言模型进行查询重写的整体系统。 我们引入了自然语言重写规则（NLR2）的概念，并使用它们作为大语言模型的提示，同时也是将知识从重写一个查询转移到另一个查询的手段，从而随着时间的推移变得更聪明、更有效。 我们提出了一种新颖的反例引导技术，可以迭代地纠正重写查询中的语法和语义错误，显着减少大语言模型成本和验证所需的手动工作量。 GenRewrite 将 99 个 TPC 查询（最复杂的公共基准）中的 22 个加快了 2 倍以上，这比最先进的传统查询重写和 2.1 的覆盖率高出 2.5 倍至 3.2 倍x 高于开箱即用的大语言模型基线。

1.介绍

低效查询是几乎所有使用数据库产品的组织中的一个主要问题。 这些编写糟糕的查询（可能由缺乏经验的用户编写或由商业智能 (BI) 或其他工具自动生成）通常是性能缓慢的主要驱动因素（在云数据库的情况下，成本过高，例如 Snowflake （Dageville 等人，2016） 或 BigQuery （Fernandes 和 Bernardino，2015）)。 因此，查询重写（SQL-to-SQL）是提高性能和降低成本的关键步骤，因为如果查询优化器给出一个写得不好的查询，那么查询优化器找到更有效的查询计划的机会就会大大降低。首先。 查询重写，无论是手动还是自动完成，仍然是一项具有挑战性的任务。

手动查询重写的挑战。 对总体成本和性能影响最大的写得不好的查询往往也相当复杂。 例如，由 Looker (loo, tics) 自动生成的跨多个页面的 OLAP 查询并不罕见。 确保重写的查询保留原始的语义需要深入了解数据库模式、约束和查询意图，因此即使对于经验丰富的数据库专家来说也是一项耗时且容易出错的任务。 事实上，可能存在数千甚至数百万个此类查询，这使得手动方法成为一项艰巨的任务。

自动查询重写的传统方法的局限性。 尽管进行了大量的研究，自动重写技术仍然存在一些重大缺陷，这些缺陷长期以来限制了其在实践中的有效性。 在这里，最常见的方法是依赖一组“重写规则”，它们是基于模式匹配的语法转换。 如果规则中表达的模式与输入查询匹配，则规则会将匹配的部分替换为对应部分，从而生成语义上等效的查询，并且可能运行得更快。 无论规则是由专家制定和提供的（Bruno等人，2022；Pirahesh等人，1992；Ahmed等人，2006）还是自动推断（Wang等人，2022） ; Ding 等人, 2023)，基于规则的查询重写器与提供给它的重写规则集一样有效。 根据定义，基于规则的查询重写器1 仅限于输入查询与其现有规则之一匹配的情况，因此从根本上无法优化之前未见过的新查询模式（Dong等人，2023）。 虽然基于综合的查询重写不需要先验规则(Dong 等人, 2023)，但实际上它只处理简单的查询（例如，SlabCity (Dong 等人, 2023) t1> 只能优化 22 个 TPC-H 查询中的 2 个和 99 个 TPC-DS 查询中的 3 个）。

大型语言模型（大语言模型）。 大型语言模型（大语言模型）在执行复杂和开放式任务方面取得的巨大成功也为解决一些最困难的数据库问题带来了新的希望。 研究人员已使用大语言模型进行文本到 SQL （Fu 等人，2023；Gao 等人，2023；Sun 等人，[n.d.]；Katsogiannis-Meimarakis 和 Koutrika，2023；Pourreza 和 Rafiei，2024 ) 以及其他一些领域，例如数据清理和集成(Narayan 等人, 2022; Suhara 等人, 2022)、表格处理(Li 等人, 2023;陆等人，2024）和数据库诊断（周等人，2023），它们的查询重写潜力在很大程度上尚未被开发。 在人类专家或现有规则无法重写查询的情况下，例如复杂查询或新查询模式，大语言模型是否可以利用其广泛的常识和高级推理能力来发现重写机会？ 如果是这样，这可以大大减轻人类专家的负担，并允许更多的查询从重写中受益。 据我们所知，本文是第一篇专注于回答这个问题的论文：如何最好地利用大语言模型进行查询重写以及如何应对所涉及的挑战。

使用大语言模型的挑战。 使用大语言模型进行查询重写存在几个挑战：（1）幼稚的策略，即提示只是要求大语言模型“将给定的查询重写为更有效的形式，同时保留等价性”，只能重写一个小的查询子集 (§ 5.2)； (2) 由于 SQL 语言的复杂性以及所谓的“幻觉”问题(Zhang 等人, 2023; Tonmoy 等人, 2024)，大语言模型产生不可信的反应； （3）由于大语言模型无法进行实验并且缺乏特定于数据库的成本模型，因此它们重写的查询在许多情况下并不比原始查询快； (4) 多次调用一个大语言模型在时间和成本上都是昂贵的；最后（5）虽然提供提示可以帮助大语言模型，但提供太多或不相关的提示也会使大语言模型感到困惑，导致错误的反应。

我们的方法。 为了解决上述挑战，我们推出了GenRewrite，这是第一个利用大语言模型进行查询重写的整体系统。 我们引入自然语言重写规则（NLR2）的概念，它是总结重写的文本解释。 我们使用大语言模型本身来生成 NLR2，然后将其用于三个目的。 NLR2 1）作为提示帮助大语言模型提供更好的重写，2）通过提供人类可读的解释使重写更容易理解和验证，最重要的是，3）允许GenRewrite 将通过重写一个查询而获得的知识转移到另一个查询中，从而随着时间的推移变得更聪明、更有效。 由于 NLR2 没有机密信息（例如列或架构名称），因此甚至可以使用先前训练的 GenRewrite 的存储库来引导 GenRewrite 的 NLR2 存储库以用于新的工作负载> 在另一个工作负载上。

为了避免冗余规则，这反过来又会混淆大语言模型，我们为每个 NLR2 维护一个效用分数，以便仅向大语言模型提供那些与当前查询最相关的规则作为提示。 最后，为了最大限度地降低大语言模型成本并最大限度地减少人工验证所需的人力，GenRewrite不会丢弃错误的重写。 相反，它使用一种新颖的反例引导技术来迭代纠正重写查询中的语法和语义错误。

高级工作流程。图1显示了整个工作流程，这是一个迭代过程。 在每次迭代中，工作负载中的每个查询都会经历三个阶段，以找到比之前迭代中发现的更好的重写：1 建议重写、2 纠正重写、3 评估重写。 此外，GenRewrite 维护一个自然语言重写规则 (NLR2) 存储库，用于跨工作负载中的查询进行知识传输。 1从中选择适当的NLR2作为建议新重写的提示。 1 还将所有新发现的 NLR2 合并回存储库中。 2根据大语言模型提供的反例迭代细化重写，以消除语义和句法错误。 3 评估重写的等效性和性能，并相应地更新所使用的 NLR2 的实用分数。 这个过程一直持续到没有发现额外的改进并且重写集稳定为止。

目标用例。 GenRewrite 使用默认的时间预算 30 秒，但用户可以灵活地选择不同的时间或金钱预算。 对于多次执行同一查询的任何场景，每个查询的一次性成本都是合理的。 例如，商业智能 (BI) 仪表板每天对最新数据运行相同的查询，因此这些查询需要重写和优化一次并重复使用多次。 其他示例包括数据库支持的 Web 应用程序、报告工具、批处理作业以及 dbt (dbt, ouse) 和其他数据转换脚本。 事实上，Microsoft 集群中超过 60% 的作业都是重复性的（Jindal 等人，2018），这意味着用户可以调用 GenRewrite 作为识别任何优化的最后一步在运行工作负载之前，以最大程度地减少执行时间和资源消耗。

贡献。 我们做出以下贡献：

(1) 据我们所知，我们首次对查询重写的大语言模型进行了深入分析，强调了该领域未来研究的挑战和机遇（§3)。
(2) 我们推出GenRewrite，这是一个利用大语言模型进行自主查询重写的整体工具。 它通过引入（i）自然语言重写规则（NLR2）的概念来解决使用大语言模型的关键挑战，以找到更好的重写和有效的知识转移，（ii）NLR2的效用分数以最大限度地减少大语言模型引起的混乱不相关或太多的规则，以及（iii）反例引导的迭代修正方法。 （§4)。
(3) 我们在最复杂的公共基准 TPC-DS 上评估了 GenRewrite，将 99 个查询中的 22 个加快了 2 倍以上，这比现有技术的覆盖率高了 2.5 倍到 3.2 倍。 art 传统查询重写，比开箱即用的大语言模型性能高 2.1 倍 (§5)。

2.背景和动机

2.1.传统查询重写的局限性

尽管人类专家花费了数十年的努力来制定一套广泛的重写规则，但许多查询仍然无法通过基于规则的方法重写为更有效的形式（Dong等人，2023）。 这是因为重写规则捕获的查询模式从根本上是有限的。 在重写机会避开现有规则的情况下，利用常识就变得至关重要，因为常识在识别计算冗余和探索替代方法以实现相同结果方面发挥着至关重要的作用。 为了说明这一点，我们提供了来自 TPC-DS (tpc, mark) 的示例查询，这是一个对商业智能系统的挑战进行建模的行业标准基准。

清单 2 中的示例查询源自 TPC-DS 基准的第 11 季度，以提高可读性，旨在查找 1998 年至 1999 年 Web 销售增长率高于商店销售增长率的客户同一时期。 该查询首先创建一个通用表表达式 (CTE) year_total，该表达式使用 UNION ALL 合并每个客户每年的商店和网络销售数据（第 2-4 行和第 6-8 行） （第 5 行）。 然后，它对销售类型和年份列应用过滤器，以提取每个客户 1998 年和 1999 年的商店和网络销售数据（第 22-29 行），并将结果连接到客户 ID 上，以便于比较各个客户的销售数据。不同年份和销售类型的同一客户（第 19-21 行）。 最后，它筛选出网络销售增长率高于商店销售增长率的客户（第 30-31 行）。 更一般地，编写得不好的查询可能会使用UNION ALL来组合多个数据源，使用单个列来标记每个部分，然后在标签列上应用过滤器以单独使用每个部分。 在这种情况下，组合和过滤操作会相互抵消，应该从查询中删除，以获得更好的性能和可读性。 修改后的查询（如清单 3 所示）仅进行了两项更改：(1) 分别为商店和网络销售数据生成两个 CTE，而不是将它们合并为一个，(2) 删除有关销售类型的过滤器在主查询中。 因此，当在 TPC-DS 比例因子设置为 10 的 PostgreSQL 上进行测试时，观察到的加速约为 9 倍，将执行时间从 18 分钟减少到 2 分钟。 显着的加速不仅仅归因于避免与销售类型列上的 UNION ALL 和谓词相关的所有计算。 相反，观察到的性能差距还归因于这样一个事实：在 PostgreSQL 中，查询中的谓词越多，低估基数的趋势就越明显。 显然，原始查询比修订后的查询有更多的谓词，并且由于基数严重低估，PostgreSQL 在原始查询中选择了嵌套循环连接而不是排序合并连接。 除了性能提升之外，这种重写还增强了模块化和可维护性。

为了通过模式匹配规则解决这种计算冗余，最初的挑战在于识别标签列。 然后，必须跟踪子查询结果的使用情况并确定组合结果是否未被使用。 这种用法可能出现在谓词子句、case when 子句或外部查询块内的任何部分中。 考虑到多种可能的模式，尽管设计了许多规则，但我们仍然可能无法覆盖所有情况以消除不必要的 UNION ALL。 然而，人类观察者在看到上面的例子时，会直观地认识到“组合然后分裂”的过程实际上没有任何作用，应该从查询中删除。 这种直觉源于一般知识而不是明确的规则。 鉴于人类专家的时间和资源有限，手动检查每个查询是否存在潜在的冗余是不可行的。 虽然人类的智慧仍然是无价的，但像 GPT-4 等编码大量常识的大型语言模型（大语言模型）可能会成为潜在的游戏规则改变者，从而实现自动识别和利用重写机会。

2.2.大语言模型背景

本节简要概述了本文其余部分中使用的 LLM 相关术语。

Token 。 标记是大语言模型用来处理语言的单元或构建块。 例如，字符串“tokenization”被分解为两个词符“词符”和“ization”，而像“the”这样的短常用词则被表示为单个词符(ope,tion) 。 使用大语言模型的成本通常由输入和输出中的标记数量决定。

零样本提示与少样本提示。 成功使用大语言模型的关键是找到最优提示，俗称提示工程(goo,e AI)。 根据提示中提供的示例数量，提示工程分为两种场景：零样本提示（高等人，2023）和少样本提示（顾等人，2023） 。 零样本提示中没有提供示例。 图4显示了一个简单的提示，仅包含输入查询本身和简洁的一句话重写指令。 相反，在少样本提示中，向大语言模型提供有限数量的示例，使其能够从输入示例中识别显式或隐式模式并生成相应的输出。 例如，在文本到 SQL 的上下文中，少样本提示中的示例可能包括数据库模式、自然语言查询和相应的 SQL 查询作为解决方案。

3.使用大语言模型进行查询重写的经验教训

我们进行了全面的实验来研究大语言模型对于重写各种查询并提高其性能的适用性。 具体来说，我们仔细审查了大语言模型建议的每个重写，并评估其正确性和延迟。 我们特别注意辨别哪些问题可以有效解决，哪些问题不能有效解决，以及哪些条件可以将后者转化为前者。 Our study not only provided valuable insight int the capabilities of LLMs and the challenges associated with using it for query rewriting but also contributed to the development and refinement of GenRewrite that is presented in §4. 下面我们总结了影响 GenRewrite 设计决策的主要经验教训。

Lesson 1：即使有简单的提示，大语言模型在某些工作负载上也非常有效。 推理查询的性能问题并确保正确重写是一项艰巨的任务。 令人惊讶的是，即使是如图4所示的简单提示，大语言模型通过理解查询中固有的语义，也能找到许多显着提高性能但被重写规则甚至人类忽略的重写机会。专家。 零样本提示对于大语言模型训练语料库中复杂度低、频率高的查询效果最好。 一个典型的例子是 Leetcode 工作负载 (lee, Code)。 例如，考虑一下 LeetCode 问题 #176，其中的目标是从 Employee 表中找到第二高的薪水。 图5中的Q1是该问题的人工编写的解决方案（由LeetCode参与者提交），而Q2是大语言模型生成的重写。 当在随机填充一百万行的数据库上执行时，Q2 比 Q1 快大约 2000 倍。 优化过程涉及通过推理深入理解查询意图：（1）确定 Q1 的目标是找到第二高的薪水，（2）意识到有另一种方法可以实现相同的目标，即：首先使用子查询找到最高工资，然后将所有工资与该最高工资进行比较以找到第二个最大值，最后（3）认识到Q2通过减少所需的比较次数来实现性能改进。

Lesson 2：随着查询复杂性的增加，大语言模型很难识别重写机会。 虽然大语言模型在理解数据语义、执行推理和生成代码方面表现出了卓越的能力，但众所周知，它们的能力并不是无限的。 同样，随着查询变得更加复杂，大语言模型识别重写机会的能力就会减弱。 虽然大语言模型仍然有可能发现重写机会，但可能性的降低需要大语言模型运行更多的迭代，从而导致成本显着升高。 在§2.1中，我们演示了如何通过消除不必要的UNION ALL将Q11优化为更有效的形式。 TPC-DS 基准测试中的 Q4 和 Q74 也存在类似的问题。 特别是 Q4，是更复杂的一个，其词符数量最高（Q4 为 1,170，而 Q11 为 723，Q74 为 591），与 UNION ALL 组合的段最多（3 个，其他为 2），以及最高的连接数（第 4 季度为 5 个，其他为 3 个）。 尽管进行了多次尝试（使用图 4 中显示的提示运行了 10 次），但 Q4 的重写均未建议删除 UNION ALL，这一修改可以显着减少执行时间。 相反，Q11 的 10 次尝试中有 4 次和 Q74 的 10 次尝试中有 6 次朝着正确的重写方向发展。 这一观察提出了一个问题：我们是否可以通过知识迁移弥合大语言模型可以优化的查询和大语言模型不能优化的查询之间的差距，从而使大语言模型能够优化更广泛的查询，特别是那些高度复杂的查询。 这是我们 NLR2 概念背后的主要动机。

请注意，正确的重写方向，例如在 Q74 的重写中消除不必要的 UNION ALL 的建议，并不能保证对原始查询的无错误或等效重写。 此类查询的复杂性加剧了在不引入错误的情况下操作其元素的挑战。

Lesson 3：当提示中提供合适的重写提示时，大语言模型可以优化以前难以优化的查询。 由于零样本提示对于查询重写任务并不普遍有效，因此在提示中纳入精确的指导变得至关重要。 从文本到 SQL 任务中使用的少样本提示中汲取灵感(Sun 等人, [n.d.])，一种方法是为大语言模型提供示例，其中包括输入查询及其优化版本。 然而，另一种策略也有希望。 考虑这样的场景：人类专家分析两个可以使用相同想法进行优化的查询，例如 Q4 和 Q74。 人们想到的见解是，这两个查询都可以从“避免不必要的 UNION ALL”中受益。 事实上，将这种见解作为提示集成到提示中始终会导致大语言模型建议在不同的尝试中删除 UNION ALL。 与少样本提示方法相比，后一种方法有两个好处：（1）它需要更少的标记，从而降低成本并加速重写生成过程，（2）提示很容易被人类解释，促进更快的调试。 然而，由于人类专家的时间限制，手动分析每个查询并提出有益的重写提示是不切实际的。 因此，需要一种自动化方法来识别为每个查询量身定制的重写提示。

详细文章内容见Query Rewriting via Large Language Models，https://arxiv.org/abs/2403.09060