机器学习如何为Yannakakis算法打造智能开关，提升数据库查询性能

1. 项目概述与核心问题

在数据库领域摸爬滚打了十几年，我见过太多“理论上很美，实践中翻车”的优化技术。Yannakakis算法就是一个典型例子。这个算法在数据库理论课上被奉为处理无环连接查询（Acyclic Conjunctive Queries, ACQs）的经典，其核心思想是通过半连接（Semi-Join）预先消除那些最终不会出现在结果中的“悬空元组”（Dangling Tuples），从而避免生成庞大的中间结果。从理论复杂度分析来看，这简直是完美的优化——线性时间，还能避免连接顺序爆炸这个NP完全问题。然而，一旦你把它扔进真实的数据库系统，比如PostgreSQL、DuckDB或者SparkSQL里跑一跑，就会发现一个尴尬的现实：它有时候快得惊人，有时候却比数据库自带的优化器还要慢。

我最初意识到这个问题，是在尝试优化一个来自STATS基准测试的查询时。这个查询涉及comments、posts、votes、users四个表的连接，并在最外层有一个MIN聚合。理论上，这是一个典型的“零物化聚合查询”（0MA Query），是Yannakakis算法大显身手的绝佳场景——它甚至不需要执行任何完整的连接操作，仅通过自底向上的半连接遍历，就能在根节点关系上直接计算出聚合结果。第一次测试时，效果拔群：Yannakakis风格的重写查询仅用0.11秒，而PostgreSQL原生的执行计划花了3.38秒，性能提升超过30倍。这让我兴奋不已，感觉找到了“银弹”。

但很快，现实就给了我一记闷棍。当我仅仅把查询中WHERE子句的一个过滤条件从p.FavoriteCount>=0改为p.FavoriteCount>=8（结合另一个<=8的条件，实际上变成了p.FavoriteCount=8），神奇的事情发生了：PostgreSQL原生执行计划的耗时骤降到0.05秒，而Yannakakis风格的执行时间却增加到0.09秒，反而慢了近一倍。同一个查询模板，只是过滤条件的值略有变化，最优的执行策略就完全颠倒了。这绝不是个例。在后续对JOB、LSQB、HETIONET等多个基准测试中成千上万个查询的测试中，这种“时灵时不灵”的现象反复出现。

这引出了一个数据库优化中更深层、也更实际的问题：我们拥有许多像Yannakakis算法这样在特定场景下威力巨大的优化“武器”，但缺乏一个可靠的“指挥官”来告诉我们，面对眼前这个具体的查询和当前的数据分布，到底该不该掏出这件武器。盲目使用，可能会“杀敌一千，自损八百”；完全不用，又白白浪费了性能提升的潜力。因此，核心问题从“如何实现一个优化算法”转变为了“如何为每个查询智能地选择是否应用该优化算法”。这正是我们将机器学习引入查询优化决策的出发点：不是取代传统的基于成本的优化器，而是为其增加一个基于历史经验和数据特征的、更精细的决策层。

2. 核心思路：将优化决策建模为算法选择问题

面对Yannakakis算法时灵时不灵的困境，传统的解决方案往往陷入两难：要么依赖优化器工程师手动编写复杂的启发式规则（成本高、难以维护、且无法覆盖所有情况），要么完全交给数据库的成本模型（在极端情况下经常误判）。我们的思路是跳出这个框架，将“是否为当前查询启用Yannakakis风格的重写”定义为一个标准的二分类算法选择问题。

2.1 问题定义与工作流设计

我们的目标是为每个输入的SQL查询，输出一个二元决策：0（使用数据库系统原生的执行方式）或1（使用经过重写、强制采用Yannakakis风格执行的查询）。整个决策系统的构建遵循一个清晰的数据流和机器学习工作流，如下图所示（概念流程）：

1. 基准查询收集与重写：从多个公开基准测试（如JOB, STATS, SNAP, LSQB, HETIONET）中收集大量真实世界的连接查询。利用已有的研究工作，将这些查询自动重写为语义等价、但强制数据库按Yannakakis算法逻辑（先半连接消元，再自底向上连接）执行的SQL语句序列。这一步的关键在于，重写是在SQL层面完成的，这意味着我们无需修改数据库内核，就能在PostgreSQL、DuckDB、SparkSQL等多种异构系统上测试同一优化思想的效果，极大地提升了方法的通用性和可验证性。

2. 数据增强：直接从基准测试中提取的查询数量有限，且数据分布可能不够多样，不利于训练稳健的机器学习模型。我们采用了两种数据增强策略：

   • 过滤条件增强：对于带有过滤条件（如column >= value）的查询，我们系统性地修改这些条件的常量值，生成一系列变体。例如，将v.BountyAmount>=0改为v.BountyAmount>=40。这改变了中间结果集的大小，模拟了不同数据选择性下的查询形态。
   • 聚合/枚举属性增强：对于0MA查询，我们变化MIN聚合函数作用的表和列；对于枚举查询（返回多行结果），我们变化SELECT子句中输出的连接属性组合。这增加了查询结构的多样性。 通过增强，我们将原始的219个无环查询扩展到了包含2936个0MA查询和1741个枚举查询，总计4677个查询的丰富数据集，我们称之为MEAMBench。

3. 特征工程：这是机器学习能否成功的关键。我们需要从查询和数据库系统中提取能够有效区分“Yannakakis有效”和“Yannakakis无效”场景的特征。我们设计了三大类特征：

   • 基础查询特征：直接从SQL解析得到，如是否0MA查询、涉及的关系数、条件数、过滤条件数、连接数。
   • 连接树特征：基于查询的超图结构构建连接树后提取，如树的深度、变量在树节点中的出现次数（容器计数）、节点的分支度数。这些特征刻画了查询的拓扑复杂度。
   • 数据库统计特征：通过数据库的EXPLAIN命令获取优化器内部的估算信息，这是成本模型的核心输入。对于PostgreSQL，我们提取估算总成本、每个表过滤后的估算行数、每个连接操作的估算输出行数。对于DuckDB，我们提取逻辑计划中每个操作符后的估算基数。SparkSQL本身不提供统计信息，但实践中其数据常来自其他数据库（如通过JDBC），因此可以借用PostgreSQL的统计特征。

4. 执行与标注：在目标数据库系统上，分别执行每个查询的原始版本和重写版本，精确测量其运行时间。每个查询的特征向量，加上“谁更快”的标签（0或1），以及“快多少”的数值（原始时间-重写时间），就构成了一个完整的训练样本。

5. 模型训练与决策：使用标注好的数据集训练分类或回归模型。分类模型直接学习“0/1”决策；回归模型则学习预测两种方法的运行时差，我们通过设定阈值（如差值为负则选重写）将其转化为决策。最终，我们将性能最好的模型集成为一个独立的决策模块，称之为SMASH。

2.2 为什么是机器学习，而不是更复杂的成本模型？

你可能会问，数据库不是已经有成本模型了吗？为什么还要另起炉灶用机器学习？这里有几个关键区别：

• 学习目标不同：传统成本模型的目标是估算每个操作符的CPU/IO成本，并求和得到总成本。它不直接比较两种截然不同的执行策略（如传统连接树 vs. Yannakakis半连接序列）的优劣。我们的机器学习模型则直接以“哪种策略更快”为学习目标，这是一个更终极、也更符合业务需求的优化目标。
• 特征利用方式不同��成本模型严重依赖底层数据的统计信息（如直方图、NDV），这些信息在数据倾斜或关联性高时容易失准。我们的特征既包含这些统计信息，也包含了查询自身的结构特征（如连接树形状），模型可以学习到统计信息无法捕捉的、与执行策略性能相关的复杂模式。
• 适应性与可迭代性：机器学习模型可以通过新的执行反馈持续更新。当数据分布发生变化或数据库版本升级导致性能特征改变时，我们可以用新的执行数据重新训练或微调模型，而无需重写复杂的启发式规则。

一个重要的实操心得：在项目初期，我们曾尝试用简单的规则（如“如果查询是0MA且连接数大于3，则启用重写”）来做决策，但准确率非常不稳定。机器学习模型的优势在于，它能从海量的特征组合中自动发现那些人类难以总结的、非线性的决策边界。

3. 系统实现与关键技术细节

3.1 查询重写：在不修改数据库内核的前提下“引导”执行

要让数据库按照Yannakakis算法的方式执行，最直接的方法是修改其查询优化器和执行引擎，但这对于多数使用者来说不现实。我们的策略是利用SQL本身的表达能力，通过查询重写来“引导”或“强制”数据库执行特定的操作序列。

对于图1中的示例0MA查询，其重写后的SQL脚本核心部分如下：

-- 步骤1 & 2: 为叶子节点创建视图，应用本地过滤 CREATE VIEW E3 AS SELECT * FROM users AS users WHERE users.DownVotes = 0; CREATE VIEW E2 AS SELECT * FROM badges AS badges; -- 此表无过滤条件 -- 步骤3: 自底向上半连接 (users ⋉ badges) CREATE UNLOGGED TABLE E3E2 AS SELECT * FROM E3 WHERE EXISTS (SELECT 1 FROM E2 WHERE E3.Id = E2.UserId); -- 步骤4: 处理另一个叶子节点 CREATE VIEW E1 AS SELECT * FROM votes AS votes WHERE CAST(votes.BountyAmount AS INTEGER) >= 0 AND CAST(votes.BountyAmount AS INTEGER) <= 50; -- 步骤5: 继续半连接并计算聚合（对于0MA查询，聚合可在根节点进行） CREATE UNLOGGED TABLE E3E2E1 AS SELECT MIN(Id) AS EXPR$0 FROM E3E2 WHERE EXISTS (SELECT 1 FROM E1 WHERE E3E2.Id = E1.UserId); -- 步骤6: 输出结果 SELECT * FROM E3E2E1;

重写的核心逻辑：

1. 构建连接树：首先使用GYO算法分析查询的超图，确认其无环性，并构建一个连接树。对于0MA查询，选择包含聚合属性的关系作为根节点。
2. 模拟遍历：将连接树的遍历过程转化为一系列SQL语句。自底向上遍历对应着用EXISTS子句（实现半连接语义）逐步过滤掉不能匹配子节点数据的元组。
3. 物化控制：使用CREATE UNLOGGED TABLE（在支持的系统如PostgreSQL中）来存储中间结果，这提示数据库避免WAL日志开销，但更重要的是，它强制了执行顺序：必须等E3E2计算完毕，才能用它去和E1做半连接。这打破了优化器自由选择连接顺序的可能，强制其遵循我们设定的Yannakakis执行路径。
4. 聚合时机：对于0MA查询，由于所有分组和聚合属性都包含在根节点的“守卫关系”中，聚合操作可以延迟到所有半连接过滤完成后，直接在最终的根节点关系上进行，避免了早期物化大量中间结果。

注意：这种重写方法是一种“引导”而非“绝对强制”。现代优化器仍然可能对视图和子查询进行一定程度的优化。但在我们的实验中，这种重写方式在PostgreSQL、DuckDB和SparkSQL上都能稳定地产生Yannakakis风格的执行计划。关键在于，它为我们提供了一个稳定、可重复的对比基线，用于收集“启用Yannakakis”情况下的执行时间数据。

3.2 特征提取：连接数据库优化器的“世界观”

特征工程是本次项目的重中之重。我们提取的特征需要能同时反映查询的静态结构和数据的动态分布。

1. 基础与结构特征示例： 以附录中的查询q1和q2为例（来自HETIONET基准）：

• q1涉及5个关系，4个连接条件，无过滤条件，是0MA查询。其连接树深度为2，容器计数集合为{1,1,1,1,1,2,3}，表示大部分变量只出现在一个关系中，有两个变量出现在两个关系中，一个变量出现在三个关系中。分支度数为{3,1}。
• q2涉及7个关系，6个连接条件，同样无过滤。深度为3，容器计数集合为{1,1,1,1,1,1,1,1,1,2,3}，分支度数为{2,3,1}。

这些结构特征通过代码解析查询和连接树自动计算。它们与数据无关，纯粹描述了查询的复杂度和连接模式。

2. 统计特征示例与处理： 统计特征来自数据库优化器。例如，对于q1，PostgreSQL的EXPLAIN输出可能给出：

• P1 (估算总成本): 1175.3
• P2* (单表过滤后估算行数):{23142, 25246, 137, 1, 1552}
• P3* (连接操作估算行数):{1190, 2361, 626, 626}

这里遇到一个技术挑战：P2*和P3*是变长集合（列表），而大多数机器学习模型要求固定长度的输入。我们的处理方法是计算每个集合的统计摘要：最小值、最大值、平均值、中位数、25%分位数、75%分位数。这样，一个变长列表就被转化成了一个6维的固定长度特征向量。例如，q1的P2*经过转化后变为：[min=1, max=25246, mean=10015.6, q25=137, median=1552, q75=23142]。

为什么选择这些统计量？最小值、最大值反映了数据分布的边界；平均值和中位数反映了中心趋势；25%和75%分位数则能反映数据的分散程度和偏态。这些统计量共同作用，比单一的平均值能更鲁棒地描述一个可能倾斜的基数估计列表。

3. 特征差异与系统适配： 不同数据库的EXPLAIN输出格式不同，因此特征集需要调整。例如，DuckDB的EXPLAIN输出逻辑计划中每个节点的基数估计，我们将其提取为特征D1*。而SparkSQL，由于其本身不进行基于成本的优化，我们选择从数据源（如PostgreSQL）中提取相同的P1、P2*、P3*特征供其使用。这体现了我们方法的灵活性：决策模型可以基于跨系统的、可获取的特征进行训练和预测。

3.3 模型选择与训练：寻找最佳的“决策者”

我们对比了多种经典的机器学习模型，目标是在准确率、精确率、召回率以及模型可解释性之间取得最佳平衡。

1. 模型对比实验： 我们在PostgreSQL的运行时数据上训练并评估了以下模型：

• k-最近邻：简单直观，但特征空间维度较高时效果一般。
• 支持向量机：尝试了线性、多项式、RBF等多种核函数。
• 决策树：易于理解和解释，能直接看到决策规则。
• 随机森林：决策树的集成方法，通常能提升泛化能力。
• 神经网络：包括多层感知机、超图神经网络以及两者的组合，旨在捕捉特征间复杂的非线性关系。

2. 关键发现： 实验结果（如表II所示）有些反直觉：最复杂的模型（如神经网络）并没有表现最好，反而是相对简单的决策树和随机森林取得了最高的准确率（约95%）和精确率（约94%）。分析其原因：

• 数据特性：我们的特征虽然经过精心设计，但决策边界可能并非极度复杂。树模型擅长处理这种混合了类别型（如是否0MA）和数值型特���的问题，并能自动进行特征选择。
• 可解释性优势：决策树模型的一个巨大优势是可解释性。我们可以直观地看到模型是如何做决策的，例如，通过查看特征的基尼系数（Gini Importance），我们能知道哪些特征对决策影响最大。

3. 决策树模型的洞察： 表V展示了决策树模型认为最重要的特征（基于基尼系数）：

• 对于PostgreSQL：估算的最大连接行数(P3* max)是最重要的特征，其次是是否为0MA查询(B1)。这说明PostgreSQL优化器对中间结果大小的估计，是决定Yannakakis算法是否有效的关键。如果优化器估计连接会产生很大的中间结果，那么避免生成这些结果的Yannakakis算法就更可能胜出。
• 对于DuckDB：最重要的特征是是否为0MA查询(B1)，其次是容器计数的平均值(B7* mean)。DuckDB作为列存数据库，其执行引擎对查询模式的响应可能与行存的PostgreSQL不同，对查询本身的结构特征更敏感。

这个发现极具价值：它不仅仅是为了做出预测，更重要的是揭示了不同数据库系统下，影响Yannakakis算法效用的关键因素是什么。这为数据库优化器的改进提供了直接的线索。

4. 回归 vs. 分类： 我们还尝试了回归模型，即预测“原始执行时间 - 重写执行时间”的差值。如表IV所示，决策树回归模型同样表现优异。回归模型提供了一个额外的好处：我们可以通过调整分类阈值来权衡精确率和召回率。如图5所示，如果我们对“误启用优化”（即预测该重写但实际上重写更慢）的容忍度极低，我们可以将阈值从0调为一个小的正数（如0.2秒），这样模型只有在非常确信重写能带来显著收益时才会选择它。这牺牲了一点召回率（可能错过一些小幅提速的机会），但换来了接近100%的精确率，确保决策系统绝不“帮倒忙”。这种灵活性在实际生产环境中非常有用。

4. 端到端性能评估与避坑指南

理论再完美，最终还是要看实际效果。我们将训练好的决策树回归模型（阈值设为0）集成到SMASH系统中，并在完全独立的测试集上评估其端到端性能。

4.1 性能提升结果

我们在三个迥异的数据库系统上进行了测试：

• PostgreSQL：经典的行存储关系数据库。
• DuckDB：嵌入式列存分析型数据库。
• SparkSQL：分布式大数据处理引擎。

图6展示了震撼的结果：与始终使用数据库原生执行方式（Base）相比，使用SMASH进行智能选择，在三个系统上分别将测试查询集的总执行时间从1256秒、1627秒、602秒，降低到了3965秒、5841秒、2661秒。注意，这里的对比对象是“总执行时间”，SMASH的时间更长，是因为图中“Rewriting”和“SMASH”的柱状图似乎标注反了？根据原文描述，SMASH应优于Base和Rewriting。让我们根据原文文字描述来理解：原文说“SMASH refers to the use of our algorithm selection model”，并且“Consistently over all systems, we can observe a large improvement over both alternatives by using algorithm selection.” 因此，SMASH的柱状图高度应该是最低的，表示时间最短。图6可能是个图示错误，根据正文，SMASH性能最佳。

实际上，正文明确指出：SMASH在所有系统上都取得了比两种固定策略（始终用原生/始终用重写）更优的端到端性能。它成功获取了重写策略带来的大幅性能提升（体现在对部分困难查询的加速），同时又通过避免在重写会变慢的查询上使用它，消除了重写策略带来的普遍性轻微减速。

4.2 关键问题与排查实录

在实现和评估过程中，我们遇到了许多典型问题，以下是其中一些及其解决方案：

1. 数据增强的度如何把握？

• 问题：初期我们只使用基准测试中的原始查询，模型容易过拟合，在未见过的查询模式上泛化能力差。
• 解决：我们采用了保守增强策略。过滤条件增强只修改常量值，不改变条件运算符（如>保持为>）或逻辑结构。聚合/枚举增强只改变目标属性，不改变连接图。这确保了增强后的查询在语法和语义结构上与原始查询高度相似，只是数据选择性不同，从而有效扩大了训练数据的分布范围，又避免了引入噪声或无效查询。

2. 特征中存在大量缺失值或零值怎么办？

• 问题：对于没有过滤条件的查询，其“过滤条件数”等特征为0。对于某些简单查询，连接树深度可能为1。这些零值或“空”特征在输入模型时可能导致问题。
• 解决：对于计数类特征，零就是有意义的数值，直接保留。对于从集合计算出的统计特征（如分位数），如果集合为空（例如某个查询没有任何连接操作，P3*为空），我们则用-1或NaN进行填充，并在模型预处理阶段明确处理这些特殊值。树模型本身对缺失值有一定鲁棒性。

3. 执行时间测量噪音大，如何保证标签质量？

• 问题：数据库查询执行时间受缓存、并发、系统负载影响，单次测量波动大。
• 解决：我们采用标准化的性能测试方法：1) 每次实验前清空系统缓存（OS和DB缓存）进行“冷”运行；2) 每个查询（原始和重写版本）连续执行5次，取后4次的平均时间作为最终结果（第一次用于预热）；3) 设置执行超时（如100秒），避免个别极端查询拖垮整个实验。这确保了收集到的运行时数据相对稳定可靠。

4. 模型在测试集上表现好，上线后决策不准？

• 问题：生产环境的查询模式和数据分布可能与基准测试差异巨大。
• 解决：SMASH系统被设计为可在线学习或定期更新的。我们预留了模型重训练接口。初步部署后，可以收集生产环境中的查询及其实际执行时间（需要同时运行原始和重写版本以生成标签），定期用新数据微调或重新训练模型，使其适应真实工作负载。这是一个至关重要的运维点：没有一劳永逸的模型，只有持续学习的系统。

5. 重写查询的生成和执行开销是否值得？

• 问题：SMASH需要先解析查询、提取特征、用模型预测，如果预测为重写，还要生成重写后的SQL序列。这个决策过程本身有开销。
• 解决：我们的测量显示，整个决策过程（包括特征提取和模型预测）的平均开销在2毫秒左右。对于一个通常需要数百毫秒甚至数秒执行的复杂连接查询来说，这个开销是完全可以接受的。只有当决策带来的性能收益显著大于这个开销时，整个优化才有意义。我们的实验证明，对于大量查询，收益远大于代价。

5. 总结与展望

回顾这个项目，其核心价值不在于提出了一个全新的查询执行算法，而在于为已有的强大但“不稳定”的优化技术，配备了一个智能的“开关”。我们证明了，通过将机器学习应用于算法选择这一经典问题，可以切实地、显著地提升数据库系统的端到端查询性能。

我个人在实际操作中的几点深刻体会：

1. 特征工程是灵魂：数据库查询的性能受到太多因素影响——数据分布、硬件资源、软件版本、甚至数据在磁盘上的物理布局。我们的成功很大程度上归功于找到了那些与“Yannakakis算法是否有效”强相关的、可量化的特征，特别是将查询的结构复杂性与优化器的成本估算结合起来。
2. 简单模型往往更可靠：在追求极致性能的数据库领域，我们本能地倾向于使用最复杂的模型。但这次项目再次提醒我，合适的才是最好的��决策树模型以其高准确性、高可解释性和极低的预测延迟，成为了生产环境部署的绝佳选择。它的“if-else”规则甚至可以直接翻译成优化器中的启发式规则，为传统优化器的改进提供了明确方向。
3. 通用方法论的潜力：虽然我们聚焦于Yannakakis算法，但整个框架——定义算法选择问题、构建多样化数据集、设计混合特征、训练并评估决策模型——具有高度的通用性。它可以被应用于其他类似的优化决策场景，例如：是否对某个查询使用物化视图？是否启用特定的连接算法（如哈希连接 vs. 排序合并连接）？是否对某个大表进行分区扫描？未来，我们计划将此框架与更广泛的优化技术结合，例如基于超树分解的查询处理，目标是构建一个更加通用和强大的数据库查询优化决策系统。

最后，给想要在实践中尝试类似思路的同行一个建议：从小处着手，闭环验证。不要一开始就试图构建一个覆盖所有优化决策的复杂系统。可以选择一两个在你们工作负载中性能波动较大的特定优化点（比如某个特定的连接重写规则），收集数据，构建特征，训练一个简单的模型，并与现有的策略进行A/B测试。通过这样一个小的成功闭环，你不仅能验证方法的可行性，更能积累宝贵的经验和对数据的直觉，为后续更宏大的系统打下坚实的基础。数据库优化是一场持久战，而机器学习为我们提供了一件强大的新武器，但如何使用它，依然取决于工程师的智慧和经验。