Efficient Query Rewrite Rule Discovery via Standardized Enumeration and Learning-to-Rank(extend)

本文提出了 SLER 系统，通过结合标准化模板枚举与学习排序技术，有效解决了查询重写规则发现中的搜索空间爆炸与冗余问题，成功构建了包含超百万条规则且可扩展至复杂查询场景的史上最大实证验证重写规则库。

要点

这篇论文介绍了一个名为 SLER 的新系统，它的任务是帮数据库“找捷径”。

为了让你轻松理解，我们可以把数据库查询想象成在迷宫里找路，把查询优化想象成给司机推荐最佳路线。

1. 背景：迷宫里的老司机与笨办法

想象你开着一辆车（数据库查询），手里拿着一张地图（查询计划）。你的目标是尽快到达目的地（返回结果）。

• 传统做法：以前的数据库系统里，有一群经验丰富的老专家（人工编写的规则），他们凭经验告诉你：“遇到这种路口，直接右转能省时间”。但这有个大问题：世界上的路口太多了，专家记不全，而且很多路是死胡同，专家也没法穷尽所有可能。
• 现有的自动方法（WeTune）：为了解决专家记不全的问题，之前的技术（WeTune）试图用计算机自动“穷举”所有可能的路线。它就像是一个不知疲倦但有点笨的机器人，试图把迷宫里每一条可能的路都走一遍，看看哪条快。
  • 缺点：迷宫稍微大一点（比如超过 4 个路口），机器人就要跑上几年甚至几十年才能算完。而且，它算出来的 90% 都是废话（比如“先左转再右转”和“先右转再左转”其实是一样的），浪费了大量时间。

2. SLER 的三大绝招

SLER 就像是一个超级智能的导航系统，它用三招解决了上述问题：

第一招：标准化模板（把迷宫“抽象化”）

• 比喻：想象迷宫里有很多路，虽然路牌颜色不同、装饰不同，但结构是一样的（比如都是“先直行，再左转”）。
• 做法：SLER 不关心具体的路牌名字（比如“员工表”、“销售表”），它只关心路口的结构。它把成千上万种具体的路，归纳成几种标准模板。
• 效果：就像把“去北京”、“去上海”、“去广州”都归纳为“去大城市”一样。这样，它不需要把每一条具体的路都跑一遍，只需要跑几种标准结构，就省去了 90% 以上的重复工作。

第二招：去重算法（RTP，把“废话”踢出去）

• 比喻：机器人跑完步发现，它列出的路线里，有两条路其实是一回事，只是名字写得稍微不一样。
• 做法：SLER 有一个专门的“去重员”（RTP 算法）。在生成规则的过程中，它一旦发现两条路本质一样，就立刻把其中一条删掉，不再浪费时间去验证。
• 效果：这就像在整理衣柜时，直接扔掉那些一模一样的衣服，只留一件，让衣柜（规则库）变得非常整洁高效。

第三招：学习排序（LambdaMART，给规则“打分”）

• 比喻：即使去掉了废话，迷宫里可能还有成千上万条路。如果一条一条试，还是太慢。这时候，我们需要一个有经验的教练来预测哪条路最可能快。
• 做法：SLER 训练了一个AI 模型（学习排序模型）。这个模型看过 1 万多个真实的驾驶案例（真实 SQL 查询），它学会了看路口的结构，就能预测哪条规则最可能让车跑得更快。
• 效果：在开始正式跑迷宫之前，AI 先给所有可能的路线打分。它只挑出得分最高的前 10% 去详细验证，直接跳过那些大概率没用的路。这让系统能处理以前根本不敢想的超级复杂迷宫（比如 10 个路口以上的查询）。

3. 成果：从“算不动”到“算得飞起”

• 以前（WeTune）：
  • 只能处理简单的 4 个路口的迷宫。
  • 想处理 5 个路口？需要6 个月甚至更久。
  • 算出来的规则里，90% 是垃圾，50% 是废话。
• 现在（SLER）：
  • 速度快：处理 4 个路口的迷宫，时间缩短了一半以上。
  • 能处理大迷宫：成功处理了5 个、6 个甚至更多路口的复杂迷宫。
  • 规则库巨大：自动发现了超过 100 万条新规则（以前只有几万条），而且都是经过验证的“真金白银”。
  • 效果显著：对于复杂的查询，SLER 能一步到位找到最优解，而旧方法要么找不到，要么要绕好几圈。

4. 总结

简单来说，SLER 就是一个懂行、会偷懒、有眼光的数据库优化助手：

1. 懂行：它把复杂的查询抽象成标准模板，不再死磕细节。
2. 会偷懒：它用算法自动剔除重复和无效的规则，不跑冤枉路。
3. 有眼光：它用 AI 预测哪些规则最有用，优先验证，把精力花在刀刃上。

这项技术让数据库能够自动发现以前人类专家发现不了的“隐藏捷径”，让复杂的查询跑得更快，就像给数据库装上了一个超级导航，无论路多复杂，都能帮你找到最快的路。

技术摘要

这是一篇关于数据库查询重写规则自动发现系统的技术论文总结。论文提出了一种名为 SLER (Scalable Learning-to-Rank for Efficient Rewrite rule discovery) 的系统，旨在解决现有自动化规则枚举方法在效率、可扩展性和有效性方面的严重瓶颈。

以下是该论文的详细技术总结：

1. 研究背景与问题 (Problem)

• 核心挑战：查询重写是优化数据库性能的关键技术。现有的自动化规则枚举方法（如 SOTA 的 WeTune）面临三大主要问题：
  1. 搜索空间爆炸：随着查询计划节点数（Node count）的增加，规则枚举空间呈指数级增长。WeTune 处理 4 节点规则需耗时约 9 天，而处理 5 节点规则需 6 个月，6 节点规则甚至需要十年以上。
  2. 严重冗余：现有方法生成的规则中，超过 90% 是冗余的，且剩余的非冗余规则中超过 50% 是琐碎的（trivial），优化价值极低。
  3. 可扩展性差：现实世界的复杂查询（如 PostgreSQL 中的生产查询）通常包含 5-8 个甚至更多节点。现有方法受限于只能处理 4 节点以下的模式，无法优化复杂的嵌套子查询或深层连接结构。
  4. 验证困难：依赖 SMT 求解器（如 Z3）进行语义等价性验证时，由于 NP=coNP 等理论复杂性，验证时间不可预测，导致大规模枚举不可行。

2. 方法论 (Methodology)

SLER 系统通过结合标准化模板枚举与**学习排序（Learning-to-Rank, LTR）**技术，构建了一个高效且可扩展的规则发现框架。其核心流程包含三个主要组件：

A. 基于标准化模板的规则枚举器 (Standardized Rule Enumerator)

• 标准化模板 (Standardized Templates)：为了消除结构冗余，SLER 将查询计划抽象为标准化模板（保留操作符结构，去除数据细节）。
• 操作符重排与移除：定义了一套标准化规则，强制将投影（Project）和过滤（Filter）等操作符下推到连接（Join）操作符之下，或移除冗余操作符。
  • 例如：优先顺序定义为 Project > Distinct > Filter。
  • 效果：将原本需要指数级验证的冗余模板对，减少为常数级或多项式级验证，大幅降低了验证开销。
• 小到大假设的证伪：论文通过实证分析（仅 9% 的复杂规则可由简单规则组合而成）否定了“小到大”（Small-to-Large）的启发式组合策略，确立了直接枚举复杂模板的必要性。

B. 基于模板对的去重器 (RTP-Based Deduplicator)

• RTP 算法 (Reduce by Template Pair)：在枚举阶段即进行去重，而非枚举完成后。
  • 为每个模板对维护一个独立的规则库。
  • 在生成新规则时，立即检查其是否与当前库中的规则等价或冗余。
  • 如果新规则是冗余的，立即停止该路径的进一步枚举，避免昂贵的 Z3 验证调用。
• 多路归并 (Multi-way Subsumption)：结合子集去重和子集合并策略，确保在去除冗余的同时保留优化能力。

C. 基于 LambdaMART 的规则排序器 (Rule Ranker)

• 学习排序模型：引入 LambdaMART（基于梯度提升决策树 GBDT 的排序模型）来预测规则的有效性。
• 特征工程：
  • 模板编码：利用树卷积神经网络（Tree Convolutional NN）将查询计划树映射为 9 维向量（包含 L2 距离、余弦相似度等）。
  • 表达式复杂度：统计操作符表达式中的字符串长度、聚合深度、乘法依赖、逻辑否定等特征。
• 训练与推理：
  • 使用来自开源和商业工作量的 11,000+ 真实 SQL 查询进行训练，标签基于实际执行时间的减少量（1=有效，0=无效）。
  • 预过滤机制：在枚举大规模模板（如 7 节点以上）前，先利用排序器对模板对进行打分，仅选择 Top-K 最有潜力的模板对进行详细枚举和验证。这实现了在可控的计算成本下探索大规模规则空间。

3. 主要贡献 (Key Contributions)

1. 提出 SLER 框架：首个能够高效处理大规模（>4 节点）查询重写规则发现的系统，构建了包含超过 100 万条 经过实证验证的 rewrite 规则库（目前最大）。
2. 标准化枚举算法：证明了“小到大”组合策略的局限性，提出了基于标准化模板的枚举方法，将冗余模板的验证复杂度从指数级降低至多项式级。
3. RTP 去重算法：设计了在枚举过程中实时剪枝冗余规则的算法，显著减少了验证调用次数。
4. 数据驱动的排序机制：揭示了数学证明方法（SMT）在规则优先级排序上的局限性，首次引入机器学习模型（LambdaMART）来筛选高价值规则，解决了大规模规则空间的可扩展性问题。
5. 实证突破：成功枚举了 5 节点和 6 节点规则，并通过排序器实现了对 7 节点及以上复杂模板的可行性探索。

4. 实验结果 (Results)

• 效率提升：
  • 在 2-4 节点规则枚举上，SLER 比 WeTune 快 34%-88%。
  • 在去重（De-redundancy）阶段，SLER 比 WeTune 快 99% 以上（例如 4 节点去重从 20 天缩短至 10 分钟）。
  • 可扩展性：WeTune 在 5 节点时超时（Timeout），而 SLER 能在约 30 天内完成 5 节点枚举，约 395 天完成 6 节点枚举。通过 Top-K 过滤，SLER 能在 143 分钟内发现 40% 模板覆盖下 80% 的有效规则。
• 规则数量与质量：
  • 构建了 679,316 条新规则，是 WeTune 规则库规模的 98.25 倍。
  • 发现了大量 WeTune 无法处理的复杂模式（如深层嵌套子查询、多表连接冗余）。
  • 端到端性能：在真实查询测试中，SLER 生成的规则能显著减少查询执行步骤（Scenario A），达到比 WeTune 更高的优化比率（Scenario B），甚至能解决 WeTune 完全无法优化的查询（Scenario C）。
• 排序器效果：Top 500 条规则贡献了 98.6% 的平均性能提升，而底部 50% 的规则仅贡献 11.9%，证明了排序机制能精准识别高价值规则。

5. 意义与影响 (Significance)

• 突破规模限制：打破了现有查询优化器只能处理简单（≤4 节点）模式的瓶颈，使得优化器能够处理现代 ORM 框架和 AI 生成 SQL 中常见的复杂、深层嵌套查询。
• 自适应优化：SLER 的架构具有高度可扩展性，能够无缝集成新的操作符（如聚合、窗口函数），为下一代自适应数据库优化器奠定了基础。
• 工业价值：通过在开源和腾讯内部商业工作负载上的验证，证明了该系统在实际生产环境中的巨大潜力，能够自动发现并应用大量人工难以编写的优化规则。

总结：SLER 通过“标准化消除冗余” + "RTP 实时剪枝” + "LTR 智能排序”的三重机制，成功解决了查询重写规则发现中的效率与可扩展性难题，将规则库规模从千级提升至百万级，并覆盖了更复杂的查询场景，是数据库查询优化领域的一项重大进展。