现有研究表明，提升大模型输出的多样性在一定程度上可以提高模型的准确率。将此思路拓展至Text-to-SQL任务中，可以通过提升模型输出SQL查询的多样性来优化模型性能。本文将综述一些常用的SQL查询多样性与相似性度量方法。

1. 词法形态

该类方法主要关注SQL的文本相似度。

实现步骤如下：

1.1 SQL 标准化处理

  • 格式化与清洗 ：利用 Python 库 sqlparse 对 SQL 进行格式化，去除冗余空格，将 SQL 整合成单行，去除注释，并将字符统一转换为大写或小写。

  • 符号掩码化

    • 全统一占位符 ：将具体的表名、列名、字符串、数字等替换为统一占位符，如 TABLE_NAME, COLUMN_NAME, STRING_LITERAL 等。
      例如：
      原始 SQL A:
    1
    SELECT DISTINCT u.id FROM users u JOIN orders o ON u.id = o.user_id;

    标准化后 SQL A:

    1
    SELECT DISTINCT COLUMN_NAME FROM TABLE_NAME JOIN TABLE_NAME ON COLUMN_NAME = COLUMN_NAME;

    注 ：该方法侧重于 SQL 的结构和语法，但忽略了具体的表名、列名等细节，导致表间关系信息丢失（例如无法区分“自连接”和“普通连接”）。

    • 索引式占位符 ：该方法并非将所有表映射为同一词汇，而是根据其出现的顺序或哈希值，映射为 T1, T2, C1, C2 等占位符，从而保留表间的关系信息。
      例如：
      原始 SQL A:
    1
    SELECT DISTINCT u.id FROM users u JOIN orders o ON u.id = o.user_id;

    标准化后 SQL A:

    1
    SELECT DISTINCT C1 FROM T1 JOIN T2 ON C1 = C2;

    注 ：这种方法保留了数据流动的拓扑结构，能够识别出结构相似但逻辑拓扑不同的 SQL（如涉及两张不同表与涉及同一张表的区别）。虽然实现相对复杂，需要维护映射字典，但精确度更高。

1.2 计算文本相似度

获得标准化后的SQL字符串后，可采用通用的文本相似度度量方法进行计算。

1.2.1 编辑距离

通过计算两个SQL字符串之间的最小编辑操作数（插入、删除、替换）来衡量其相似度。编辑距离越小，SQL越相似。

计算过程：

  • 构建矩阵，行表示 SQL A 的字符（或分词），列表示 SQL B 的字符（或分词）。
  • 矩阵单元格 $(i, j)$ 表示将 A 的前 $i$ 个字符变换为 B 的前 $j$ 个字符所需的最小步骤。
  • 通过状态转移方程计算：
    • 若当前字符相同，代价为 0；
    • 若不同，取（上方、左方、左上方）三个单元格中的最小值加 1。

$$
\text{Sim}_{\text{SQL}}(A,B) = 1 - \frac{\text{EditDist}(A, B)}{|A| + |B|}
$$

1.2.2 Jaccard相似度

将SQL分词后，计算两个SQL词集合的交集与并集之比。Jaccard相似度越高，SQL越相似，意味着多样性越低。因此，通常使用 1 减去Jaccard相似度来衡量多样性。

$$
Score_{lexical} = 1 - \frac{|Set_A \cap Set_B|}{|Set_A \cup Set_B|}
$$

2. 句法结构

该类方法关注SQL的骨架形状，即SQL的抽象语法树（AST）结构相似度。

2.1 AST生成

利用强类型SQL解析器（如 sqlglot）生成AST。

2.2 结构相似度计算

主要包含以下两种方法：

2.2.1 AST 结构特征向量

为了准确评估生成SQL查询在逻辑结构上的差异，而非仅关注表名或列名的词汇变化，一种基于抽象语法树（AST）的结构特征提取与距离度量方法被提出。

2.2.1.1 结构特征向量构建

对于每一个生成的 SQL 查询 $q$，首先将其解析为 AST。为消除标识符命名（如表别名、列名）和字面量（Literal Values）对结构分析的干扰，预处理阶段需对 AST 的叶子节点进行匿名化处理。随后，从树结构中提取一组关键统计量，将 $q$ 映射为一个固定维度的结构特征向量 $\mathbf{v}(q) \in \mathbb{R}^{n}$（可根据实际情况扩展维度）：

$$
\mathbf{v}(q) = [ n_{\text{sel}}, d_{\text{nest}}, b_{\text{join}}, \mathbf{t}{\text{join}}, n{\text{pred}}, b_{\text{subq}}, b_{\text{agg}}, b_{\text{group}}, b_{\text{having}}, b_{\text{order}}, b_{\text{distinct}} …]^\top
$$

向量中各分量定义如下：

  • $n_{\text{sel}}$：SELECT 子句中投影列的数量，反映查询结果的维度；
  • $d_{\text{nest}}$：AST 的最大嵌套深度，衡量查询逻辑的层级复杂度；
  • $b_{\text{join}} \in {0,1}$：指示变量，表示查询是否包含 JOIN 操作；
  • $\mathbf{t}_{\text{join}}$：JOIN 类型的独热编码，涵盖 INNER、LEFT、RIGHT 等连接类型；
  • $n_{\text{pred}}$：WHERE 子句中谓词条件的数量，反映过滤逻辑的复杂度；
  • $b_{\text{subq}} \in {0,1}$：表示是否包含子查询结构；
  • $b_{\text{agg}}, b_{\text{group}}, b_{\text{having}} \in {0,1}$：分别表示是否使用聚合函数、GROUP BY 分组及 HAVING 过滤；
  • $b_{\text{order}}, b_{\text{distinct}} \in {0,1}$：分别表示是否包含排序和去重操作。

该特征向量综合涵盖了 SQL 查询的选择（Selection）、连接（Join）、嵌套（Nesting）及聚合（Aggregation）等核心结构维度，能够有效表征查询的拓扑骨架。

2.2.1.2 归一化结构距离

给定两个查询 $q_i$ 与 $q_j$，定义其结构差异 $d_{\text{struct}}(q_i, q_j)$ 为特征向量间的归一化曼哈顿距离：

$$
d_{\text{struct}}(q_i, q_j) = \frac{1}{d} \sum_{k=1}^{d} \frac{|v_{ik} - v_{jk}|}{\max(v_{ik}, v_{jk}, 1)}
$$

其中 $d=n$ 为特征维度。分母中的 $\max(\cdot, 1)$ 项不仅避免了除零错误，还起到了动态归一化的作用，消除了不同特征量纲（如嵌套层数 $d_{\text{nest}}$ 与布尔标志位 $b_{\text{subq}}$）对距离计算的偏差影响。

2.2.2 树编辑距离 (Tree Edit Distance, TED)

2.2.2.1 AST 规范化

计算距离前，需对每个 SQL 的 AST 执行结构重组，以消除无效的结构差异：

  1. 算子扁平化 (Operator Flattening)： 将嵌套的二元逻辑运算符（如 AND, OR）转换为多元运算符节点，消除解析器产生的左递归或右递归深度差异。例如：

    • 标准 AST 中，WHERE A AND B AND C 可能被解析为嵌套二叉树 AND(A, AND(B, C))。
    • 此类结构会导致层级过深，应将其扁平化为 AND 节点下挂三个子节点 [A, B, C]。

  2. 字典序重排 (Lexicographical Reordering)： 针对满足交换律（Commutative）的节点——包括 FROM 表列表、WHERE 连词条件及 GROUP BY 分组列——对其子树按照归一化的字符串表示进行字典序排序。

    $$
    \text{sort}(\text{AND}(c_2, c_1)) \rightarrow \text{AND}(c_1, c_2)
    $$

    通过此步骤，语义等价的查询将被映射为唯一的拓扑结构。

2.2.2.2 加权树编辑距离

通常采用经典的 RTED 算法 计算规范化 AST 之间的最小编辑成本。RTED 的目标是找到成本最小的操作序列，将 $T_1$ 转换为 $T_2$。

标准操作通常有三种，默认代价（Cost）设为 1：

  1. Rename (替换) ：修改节点的标签（Label）。
  2. Delete (删除) ：删除节点（处理方式取决于具体定义，RTED 通常处理单个节点）。
  3. Insert (插入) ：插入一个新节点。

$$
TED(T_1, T_2) = \sum \text{Cost(Rename)} + \sum \text{Cost(Insert)} + \sum \text{Cost(Delete)}
$$

最终的 AST 相似度定义为：

$$
\text{Sim}_{\text{tree}}(T_1, T_2) = 1 - \frac{\text{TED}(T_1, T_2)}{|T_1| + |T_2|}
$$

3. 语义向量化

利用在大规模代码库上预训练的Transformer模型（如CodeBERT, GraphCodeBERT, UniXcoder），将离散的SQL符号映射到连续的高维语义向量空间。

3.1 DQO (Diversity via Determinantal Point Processes)

  1. 语义向量化 ：使用模型将每条 SQL 映射为高维向量。
  2. 相似度矩阵 ：计算向量之间的相似度矩阵 $L$。若两个 SQL 语义相似，则对应的矩阵元素值较大。
  3. 几何体积 ：在数学上，矩阵 $L+I$ 的行列式 $\det(L+I)$ 表征了这些向量在语义空间张成的“体积”。若所有 SQL 高度相似（向量近似共线），体积较小；若 SQL 覆盖不同的语义方向（向量彼此正交），体积较大。
  4. 边际贡献 ：计算移除第 $i$ 个 SQL 后，整体语义体积的减少量。

$$
Bonus_i = \log \det(L_{all}+I) - \log \det(L_{minus_i}+I)
$$

  • 若移除该 SQL 导致体积显著减小，说明其提供了独特的语义信息，赋予 高奖励 。
  • 若移除后体积几乎不变（说明存在与其高度相似的替代 SQL），则赋予 低奖励或零奖励 。

3.2 SVGD (Stein Variational Gradient Descent)

  1. 嵌入与归一化
    将 SQL 转化为向量，并进行 L2 归一化，使得欧氏距离等价于余弦相似度。

  2. 距离矩阵计算
    计算每两个 SQL 之间的 平方欧氏距离 。

    • 距离矩阵 $\mathcal{D}$：

      $$
      \mathcal{D} = { |\mathbf{x}_i - \mathbf{x}_j|^2 \mid 1 \le i, j \le N, i \neq j }
      $$

    • 自适应带宽 $h$：

      $$
      h = \frac{\text{median}(\mathcal{D})}{\ln(N) + \epsilon}
      $$

      取所有粒子间距离的中位数作为基准带宽 $h$，$\ln(N)$ 项为缩放因子。当样本量 $N$ 增大时，该因子使带宽适度收缩，以保持梯度的敏感度。此举保证了核函数的尺度能适应当前数据的疏密程度，避免因数据过于密集或稀疏导致核函数失效（趋于0或1）。

    • 核函数 $k$：

      $$
      k(\mathbf{x}_i, \mathbf{x}_j) = \exp\left( - \frac{|\mathbf{x}_i - \mathbf{x}_j|^2}{h} \right)
      $$

      $k_{ij}$ 越接近 1，表示两个 SQL 越相似；接近 0 则表示越不相似。

  3. 排斥压力计算
    模拟 SVGD 梯度更新公式中的排斥项：

    • 对于第 $i$ 个 SQL，其压力源自所有其他粒子 $j$ 对它的核函数值之和。
    • 若邻域内存在大量相似 SQL（$k_{ij}$ 较大），则排斥压力（Pressure）较高。

  4. 奖励转换

    $$
    R_i = \alpha \cdot \exp\left( -2 \cdot P(\mathbf{x}_i) \right)
    $$

    • 压力越大（重复度高），奖励衰减越显著。
    • 压力越小（独特），奖励越接近最大值 $\alpha$。

4.行为与执行

数据库优化器生成的物理执行计划是查询行为的蓝图。相较于单纯的 SQL 文本比对，执行计划更能反映查询对系统资源的实际影响及底层逻辑路径。

然而，优化器的标准化机制往往会将句法结构不同但语义等价的查询映射为相同的执行计划。这种特性虽然有助于识别深层的逻辑重复，但也意味着该指标对模型在句法层面的生成多样性不敏感。此外，考虑到获取执行计划对特定数据库环境（Schema、统计信息）的强依赖性以及较高的计算开销，本文不再深入展开基于执行计划的具体度量算法。