Larch：面向 AI SQL 语义谓词的习得式查询优化

关联论文：2606.07923
作者：flyP
更新：2026-07-17

一句话结论

Larch 把 AI SQL 里高开销的语义过滤器当作可学习对象，给出 Larch-A2C（Gated GNN + MDP 排序）与 Larch-Sel（监督学习预测选择率 + 动态规划）两种变体，在多个真实与合成负载下，比 Palimpzest、Quest 等基线 降低 3×–19× 的 token 总开销。

解决什么真问题

现代分析型数据库纷纷引入「语义算子」（semantic operators），让用户用自然语言或 embedding 直接对文本、图片、视频等非结构化数据做过滤——典型表达是 SQL 里的 AI_FILTER(prompt, column)。这类算子有两个棘手特性：

贵且慢：每次调用都是一次 LLM/视觉模型推理，延迟常在百毫秒到秒级，token 账单随数据量线性增长。
黑盒：数据库优化器看不到内部逻辑，传统的代价模型（cost model）和基数估计（cardinality estimation）都失效，导致语义谓词在大表上几乎不可用。

行业里通常有两个绕路做法：要么把语义谓词推到执行链最后（避免重复调用），要么粗暴采样（sample-then-filter）。前者错失并行机会，后者要么漏检要么重算。

Larch 的切入点是两个观察：

语义算子慢，意味着有充分时间在运行时跑重优化——传统 OLTP 优化器不能干的事，这里能干。
非结构化数据几乎都会伴随 embedding 一起存（用于下游检索），于是 prompt 与数据值之间可以做廉价的语义近似——不必每次都真调用大模型。

核心方法

Larch 不是一个单一算法，而是 两个互补变体共享同一个「AI SQL + 优化框架」形态。

1. Larch-A2C：GNN 编码 + MDP 排序

把任意布尔语义过滤表达式看成一棵 AND/OR/NOT 树，叶子节点是一个 AI_FILTER(prompt_i, col_i)。

编码器：Embedding-augmented Gated Graph Neural Network。每个节点既拿到对应的 prompt embedding（来自 prompt 与列的语义近似），又拿到子树结构信息，门控机制决定不同层级的消息传递。
决策形式化：把「选哪个子节点先求值」建模成 Markov Decision Process，状态是当前表达式树的剩余子树，行动是选择下一个求值节点，奖励是「少调一次大模型」。
训练信号：用结构化的 q-error 等反馈作为强化学习奖励，并配合「回归分析 + 异常子计划隔离课程」等技巧避免优化器把算子调度得很差但表面指标好看。

伪代码骨架：

def Larch_A2C(expr_tree, row):
    state = encode_GGNN(expr_tree, prompt_embeds)
    while not is_leaf(state):
        action = policy(state)               # 选下一个要 evaluate 的子表达式
        if is_concrete(action):
            keep |= eval(action, row)        # 真正调 AI_FILTER
        else:
            keep = short_circuit(state, action)  # 用 embedding 近似快速淘汰
    return keep

2. Larch-Sel：选择率预测 + 动态规划

另一条更直接的路线：

选择率预测：用一个监督学习模型直接预测每个语义过滤器的 selectivity（保留比例），输入是 prompt embedding、列 embedding、列的样本统计等。
执行序搜索：在预测到的 selectivity 基础上，用经典动态规划（类似 Selinger 的 join ordering）枚举不同的过滤器求值顺序，挑 总期望 token 开销最低 的那个。

伪代码骨架：

def Larch_Sel(filters, row):
    sels = [predict_selectivity(f, row) for f in filters]
    cost = {}
    def dp(i, chosen):
        if i == len(filters):
            return 0
        key = (frozenset(chosen), i)
        best = inf
        for f in filters - chosen:
            c = sels[f] * eval_cost(f) + (1 - sels[f]) * dp(i+1, chosen | {f})
            best = min(best, c)
        cost[key] = best
        return best
    return dp(0, set())

两条路殊途同归：A2C 适合过滤器多、表达式嵌套深、需要结构感知；Sel 适合过滤器相对独立、可以独立打分的情况。论文报告两者在大多数负载上互为补集——一个差的数据集另一个往往能救回来。

关键实验与数据

论文在多个真实负载（文本/图像/视频混合）和一组合成工作负载上做了对比，基线主要是 Palimpzest 和 Quest——这两个是 AI SQL / semantic query optimization 方向被引用最多的系统。

核心指标：总 token 开销（包含 prompt + completion），不是单次延迟。
主要结果：两种 Larch 变体在所有测试集上 always outperform 现有方法，token 成本降低 3×–19×。
稳定性：论文强调 Larch 在多样化负载下表现稳健，没有出现「A 数据集赢、B 数据集输」的过拟合现象。
代价与收益：优化本身也是一次额外开销，但因为语义算子本身慢，优化时间可以摊薄到后续大量行求值里。

注：原文未给出具体的 workload 行数、模型规格、token 单价等明细。论文摘要强调的是「相对降低」，具体绝对数字需读正文/附录。

亮点与局限

亮点

问题定义清晰：把「语义谓词难优化」从工程痛点提炼成可学习的 cost/selectivity 问题。
双方案互补：A2C 走结构学习路线，Sel 走经典 Selinger 路线，互为 fallback。
embedding 复用：巧妙利用数据库里已经存的 embedding，避免新增特征工程负担。
runtime optimization 的合法性论证：用「语义算子慢」为重优化正名，这一点对工程落地很重要。

局限（基于摘要可推断）

优化本身需要额外 ML 推理开销，对小查询可能反而更慢。
选择率预测模型的可解释性、可调试性较弱，线上出问题时难定位。
摘要只承诺 token 降低，没明确说端到端延迟降低多少——这是个常见盲点。
没有看到与传统「sample-then-filter」的强对比，这恰恰是工程上最常见的简化做法。
依赖 embedding 的可用性；如果数据库里没有预先算好的 embedding，节省的成本会被 embedding 计算抵消。

对工程落地的启发

不要把语义谓词当 last-mile 步骤：很多团队下意识把 AI_FILTER 放到 SQL 末尾，结果丢了并行与短路机会。Larch 提示应该让它进入优化器视野。
选择率可以被学习：传统数据库靠直方图，AI SQL 可以直接训练一个监督模型预测过滤后保留多少行。
慢算子反而是优化机会：当某个算子本身就贵时，为它专门做运行时的重优化是值得的——这条经验可以从 Larch 推广到其他重算子（重型 ML 推理、外部 API 调用）。
embedding 是一等公民：在 RAG / 多模态数据库里，embedding 列应当像普通索引列一样纳入优化器统计。

与同方向工作的关系

Palimpzest（MIT）：AI SQL 早期系统，奠基了 declarative semantic operator 的范式，是 Larch 的主要基线。
Quest（CMU 路线，Semantic Query Optimization）：传统语义查询优化的延续，把 query rewrite 与 ML 结合，Larch 把它列为另一个主要对比对象。
Bespoke-Card / Agent-based cardinality estimation：虽然引用列表不重叠，但思路同源——用 LLM 或 Agent 为数据库内部构件生成专用估计器。
传统查询优化器（Selinger、Volcano、PostgreSQL planner）：Larch-Sel 本质上是把 Selinger 的 join ordering 思想移植到语义谓词上。

适合谁读

数据库内核 / 优化器方向的工程师，想了解 AI4DB（AI for DB）的新边界。
正在做 RAG / 多模态检索 / AI 数据分析平台的工程团队，关注如何控制 token 成本。
关注 learned query optimization 这条研究线的人——Larch 是把 GNN + MDP 引入该方向的代表作之一。
数据平台架构师，需要判断「要不要在自家查询引擎里引入语义谓词优化层」。

工程落地与核查（Jay）

事实核查

断言	核查结论	备注
Palimpzest / Quest 是 Larch 主要基线	✅ 基本成立	Palimpzest（MIT）和 Quest（CMU）是 AI SQL / semantic query optimization 领域有公开代码的代表性系统，可信
「always outperform」现有方法	⚠️ 措辞过强	摘要级断言，未见同行评审定论；「所有测试集均优」在 ML 类论文中通常需正文详细数据支撑，摘要措辞需降级理解
token 总开销降低 3×–19×	⚠️ 需核实基数	相对基线的倍数，未说明基线是哪个（Palimpzest 默认配置？最优配置？）；需确认基线是否经调参公平对比
Larch-A2C 用 GGNN + MDP	✅ 方法可信	Gated GNN 处理树结构 + MDP 建模求值顺序是合理的组合，强化学习奖励设计需读正文确认
Larch-Sel 用 DP 找最优执行序	✅ 理论扎实	Selinger-style DP 在小规模过滤器集合（≤15–20）上可证最优；大规模场景有剪枝风险
embedding 复用节省成本	✅ 合理论点	数据库已有 embedding 不额外计费，用 embedding 做近似短路是合理的工程权衡
优化开销可被摊薄	⚠️ 需看绝对值	优化器本身调一次 GGNN / 查一次 selectivity 模型的成本，必须远小于语义算子节省的成本；若查询只过滤少量行则不划算
与 sample-then-filter 的对比缺失	⚠️ 原文自述的局限	这是真实缺陷——sample-then-filter 是工程上最常见基准，值得在报告中显式说明

工程落地：实际怎么用

架构分层建议

用户 SQL (含 AI_FILTER)
         │
         ▼
   Larch Optimizer (A2C 或 Sel)
    ┌────┴────┐
    │ GGNN/MI │  ← 优化阶段（一次性开销）
    │ selectivity模型│
    └────┬────┘
         ▼
   执行计划（过滤器顺序）
         │
         ▼
  embedding 近似短路（不花 token）
         │
         ▼
  语义算子按序求值（花 token）

关键工程决策点

1. embedding 预计算是前置依赖

Larch 的短路优化依赖 prompt embedding + column embedding 做语义近似。数据库里没有现成 embedding 列的情况下，需要提前算好。建议：

# 初始化时：批量算好所有文本/多模态列的 embedding
for col in semantic_columns:
    col.embedding = embedding_model.encode(col.raw_data, model="text-embedding-3-small")
    col.store(".larch_embeddings/")  # 持久化，避免重复计算

2. 选择率预测模型的维护

selectivity 模型有数据漂移风险：底层数据分布随时间变化，模型预测精度下降。建议：

周期性用最新数据重训练（建议以数据版本为 trigger，而非固定时间间隔）。
上线初期做 A/B：优化计划 vs. 固定顺序，对比实际 token 消耗，监控是否持续优于基线。
保留优化器的决策日志：每次输出的执行序 + 实际 selectivity，用于线下回放分析。

3. DP 搜索空间的剪枝

Larch-Sel 的 DP 复杂度是 O(2^n)，过滤器超过 15–20 个时搜索空间爆炸。实际落地必须加剪枝：

MAX_FILTERS_DP = 15  # 超过则降级为贪心
if len(filters) > MAX_FILTERS_DP:
    # 降级：用 selectivity 贪心选 top-K 先执行，其余按原始顺序
    sorted_filters = sorted(filters, key=lambda f: selectivity_model.predict(f))[:MAX_FILTERS_DP]
    remaining = set(filters) - set(sorted_filters)
    return sorted_filters + list(remaining)

4. Larch-A2C 的训练成本

GGNN + RL 训练不轻量。工程上建议：

预训练一个通用 checkpoint，下游团队做 fine-tune 或直接 frozen inference。
在线推理时 GGNN 前馈一次开销约 5–20ms（视模型规模），远低于一次 LLM 语义过滤（100ms–数秒），优化收益成立。

主要工程坑

坑	描述	解法
数据漂移导致 selectivity 模型失效	数据分布变化后历史训练数据不再代表真实 workload	加监控：预测 selectivity vs. 实际 selectivity 的 q-error；q-error 超过阈值自动触发重训练
embedding 可用性是隐性依赖	没有预存 embedding 的列无法做短路优化，节省效果打折扣	在 schema 注册阶段强制要求 embedding 列存在；缺失则走降级路径
小查询优化成本不划算	查询只过滤 10 行，优化器开销反而比直接执行还贵	设最低行数阈值：行数 < MIN_OPTIMIZE_ROWS 时跳过 Larch，直接按固定顺序执行
A2C 的 RL 奖励函数设计困难	q-error 奖励稀疏，训练不稳定	论文提到「异常子计划隔离课程」等技巧；工程实现建议先用行为克隆做 warm-up，再加 RL 微调
与传统索引的交互	AI_FILTER 和 B-tree / HNSW 索引并行存在时，优化器需要全局视野	把索引可用性作为 Larch 执行计划的额外输入；两路并行时取结果的交集
「always outperform」不是工程保险	论文结论不能直接当作生产 SOTA	上线前必须做 per-workload 评估；不同数据分布、filter 复杂度下结果可能显著不同

迁移建议

已有 AI SQL 引擎的团队：

先加 selectivity 预测（轻量版）：不做 GNN，先用一个简单模型（逻辑回归 / 轻量 GBMT）预测 selectivity，验证「执行序优化能省 token」这个假设是否在自家 workload 上成立。
选 Sel 路线先行：Larch-Sel 比 A2C 更容易实现（无 RL），可以先用 DP 验证效果，再决定是否引入 A2C。
benchmark 基础先建：记录当前 AI_FILTER 的调用次数 + 总 token 消耗，这是后续对比的必备基线。
embedding 缓存优先：确保 embedding 计算一次可重复使用，否则 Larch 的收益会被 embedding 计算成本吃掉。