SQL 共现统计慢在哪？Tessera 用稀疏乘法加 AMX 做连接聚合，比 DuckDB 快最高 1802 倍

原文信息：本文译自 arXiv 论文《Tessera: Fast Join-Aggregates over Skewed Sparse Relations in Database Engines》，作者 Gyuyeong Kim（韩国延世大学），2026 年 10 月 29 日提交（arXiv:2610.40620，cs.DB）。原文链接：https://arxiv.org/abs/2610.40620 。原文采用 CC BY 4.0 许可。本文为翻译（节译），省略了参考文献和部分实验细节，文中配图请见原文，表格保留表 1–3；译者在文末补充了译者注。

译者导语：“哪些词经常一起出现”“买了 A 的人还买了什么”“两个用户有多少共同好友”，这类共现统计在 SQL 里就是一条自连接加 GROUP BY，却常常让分析引擎跑上几分钟到几十分钟。原因是数据有偏斜：少数热门值把中间连接结果放大到数百亿行。这篇论文提出的 Tessera 换了个思路：长尾稀疏部分走稀疏矩阵乘、只输出非零结果，热门值组成的稠密核心才交给 CPU 矩阵加速器（Intel AMX）。它已做成 DuckDB、PostgreSQL、Spark、SQLite 的扩展，原 SQL 不用改。在 DuckDB 中比现有最快方案快 2.8～18.8 倍，比 DuckDB 自身执行计划最多快 1,802 倍。做数据仓库、推荐系统特征计算和图分析的读者值得一读。

摘要

连接聚合查询（join-aggregate query）对每一对取值统计或累加匹配行数，处理的往往是偏斜的稀疏关系（skewed sparse relation）：少数取值出现得很频繁，而大多数取值对从未同时出现。传统执行计划要物化数十亿行中间连接结果，单条查询耗时几分钟到几十分钟。近来基于矩阵的方案把这类查询改写成矩阵乘法，以减少或避免物化；但它们依然很慢，要么为不匹配的取值对存储结果单元格，要么仍要为低频取值物化中间连接行。

我们提出 Tessera，一个面向数据库引擎、感知偏斜的连接聚合算子，同时避开这两类开销。具体来说，Tessera 直接在引擎的行上计算稀疏矩阵乘积，只把非零单元格作为结果行输出，并在乘法开始前剪掉不可能达到查询阈值的取值。当最高频取值两两组成的稠密块足够稠密时，它还会把这一块交给 CPU 矩阵加速器计算。实验表明，Tessera 比现有最快系统快 2.8～18.8 倍，比 DuckDB 自身的执行计划最多快 1,802 倍。

（作者在 GitHub 公开了源码，仓库名 GyuyeongKim/Tessera-public。）

一、引言

很多分析问题问的是“两样东西多常一起出现”：哪些词出现在同一篇文档里，哪些电影被同一批用户打过分，哪些商品被同一批顾客购买，两个用户有多少共同好友。

在 SQL 里，这就是连接聚合：把一个关系与自身（或另一个关系）按共享键连接，再按两侧各一个属性分组计数或求和。很多查询只保留计数达到阈值的“强关联对”，比如至少在 100 篇文档里共同出现的词，或者只取前 k 名。连接聚合出现在决策支持基准测试里，也被用于构建集合相似度连接和物品到物品（item-to-item）推荐。在这些场景下执行时间很关键：分析师要等上一个答案才能问下一个问题，推荐系统每次用新数据重新训练都要重算物品相似度。

这些查询背后的关系既偏斜又稀疏。取值频率呈长尾分布：少数取值（常用词、热门电影）出现在大量行中，大多数取值只出现在少量行里。大多数取值对也从未同时出现，因为没有哪个键同时包含它们，我们称之为不匹配对（non-matching pair）。例如，在 30 万篇新闻文章的语料中，89% 的词对从未出现在同一篇文章里。

然而，现有数据库引擎在这类关系上执行连接聚合很慢。以新闻语料的词共现计数为例，连接会产生 200 亿行结果，DuckDB 这样的分析型引擎要逐行构建并聚合每一行。

已有工作把连接聚合当作矩阵乘积来算，以减少或避免中间连接行，再通过加速乘法来提速。但在偏斜稀疏关系上，这些设计依然低效：连接-投影（join-project）算法把高频取值当作稠密矩阵相乘，却仍要为低频取值构建连接行；库内线性代数和张量核心数据库则保留稠密结果，为不匹配对也留了单元格。即便用上近年 CPU 上的矩阵加速器（例如 Intel AMX），这些开销也限制了“乘法更快”带来的收益。

于是我们要问：数据库引擎怎样才能让偏斜稀疏关系上的整条连接聚合变快？

Tessera 的关键洞察是：偏斜把重复计算集中到了由高频取值组成的一个小小的稠密核心里，而低频取值组成的长尾贡献了大部分结果单元格。 因此，只有当长尾处理和结果写出也足够便宜时，加速稠密核心才划算。

基于这一点，Tessera 在一条稠密边界（dense frontier）处切分取值：边界以内，矩阵加速器把高频取值对当作稠密分块（tile）相乘；边界以外，稀疏路径只计算低频取值的非零结果单元格，承担了大部分工作。每条查询都会比较“一个加速器分块的代价”和“它所替代的稀疏乘积的代价”，以此选出边界。

实现这一设计有四个技术挑战：

1. 低频取值和输出承担了大部分工作，结果可能超出引擎的内存预算。而且只保留达标对的查询通常和保留全部对的查询工作量一样大，因为阈值要在每个单元格算完之后才生效。
2. 最佳边界同时取决于数据和查询：加速器按整个分块计费，剪枝又会改变剩下哪些取值。
3. 矩阵加速器只乘稠密分块，但稠密核心里其实大部分也是零，而它的稠密副本会随行数增长。
4. 算子必须运行在查询规划方式和资源管理方式各不相同的多种引擎里。

Tessera 的对策是：

1. 稀疏路径在引擎的行上运行 Gustavson 稀疏乘积算法，把乘积累加到计数器里，而不是构建连接行；只写出非零单元格，超出引擎内存上限时溢写到文件。在任何乘法之前先丢掉不可能达到阈值的取值，所以阈值越严格，查询越快。
2. 代价模型扫描一遍数据，选出剪枝后预计耗时最短的边界。如果没有足够稠密的块，加速器路径只花这一遍扫描的代价。
3. 把共享高频取值的行分到一起，跳过没有有效乘积的分块，使加速器的工作量与非零分块数挂钩，而不是与核心大小挂钩。
4. 每个引擎通过一个 C 接口和一个基于其扩展钩子的小适配器接入 Tessera。

Tessera 可以直接部署：我们把它作为扩展集成进了 DuckDB、PostgreSQL、SQLite 和 Spark 四个引擎。在 DuckDB、PostgreSQL 和 Spark 中，适配器会改写连接聚合的执行计划，查询本身无需改动，用户通过各引擎自己的包渠道即可安装。

二、背景与动机

2.1 连接聚合

查询形式。 对关系 R(k, x) 的连接聚合，是把 R 与自身按键 k 连接，再对 x 的每一对取值计数：

SELECT a.x, b.x, COUNT(*) FROM R a, R b
WHERE a.k = b.k GROUP BY a.x, b.x

在词共现查询里，k 是文档，x 是词；在物品推荐里，k 是用户，x 是物品；在共同邻居计数里，k 和 x 都是图的顶点。常见变体包括：对两个权重之积求和 SUM(a.v * b.v)；用 a.x < b.x 只保留无序对的一行；用 HAVING 或 ORDER BY ... LIMIT 只保留强关联对（带支持度阈值的频繁项对挖掘就是这种形式）。两关系乘积则把 R(k, x) 与 S(k, y) 连接后按 x、y 分组，例如“电影 × 观众给它打的标签”。物品相似度把一对的计数除以两个物品各自的规模（如余弦或 Jaccard 相似度），保留高于阈值的对。

为什么贵。 数据库引擎把这条查询执行为哈希连接加哈希聚合，每一行连接结果都是一次哈希表更新。一个在 d_k 行中出现的键会产生 d_k² 行连接结果，总量是 Σ d_k²，由少数“长”键主导。新闻语料的 30 万篇文章只有 7,000 万个不同的“文档-词”对，却产生 200 亿行连接结果，几乎全来自长文档和常用词。阈值帮不上忙，因为引擎要聚合完所有连接行之后才过滤分组；把聚合下推到连接之下也消不掉这些行。

矩阵视角。 令 X 为“每个键一行、每个取值一列”的矩阵，X(k, x) 是行 (k, x) 的出现次数或权重。取值对 (i, j) 的计数就是 C(i, j) = Σ_k X(k, i) · X(k, j)，即 C = XᵀX；两关系乘积则是 XᵀY。矩阵乘积对 X 的每一行只读一次，把乘积累加进 C，不需要构建连接行。但在真实数据上，X 和 C 都是稀疏的，而现有基于矩阵的设计关注的却是乘法本身有多快。

2.2 基于矩阵的设计

• 连接-投影算法按频率切分取值，高频部分做稠密矩阵乘，但低频取值仍要连接并构建连接行。
• 库内线性代数（如 SPALM）在 DuckDB 内为每个分块选择稀疏或稠密核函数，但它的算子会写出包含所有取值对的稠密结果。
• 张量核心数据库（如 TCUDB）在 GPU 上做稠密乘，稀疏输入时退回哈希连接或稀疏核函数。
• 稀疏矩阵库（如 GraphBLAS）擅长处理稀疏操作数，但使用自己的矩阵格式，并把结果组装成矩阵。SPALM、TCUDB 和 GraphBLAS 都要在完整乘积算完后才按阈值过滤。

更快的乘法收益有限。 例如在 8,192 个最高频新闻词组成的块上，SPALM 的 2.75 秒核函数时间里，只有 0.67 秒花在带稠密操作数的核函数上，所以稠密核函数再快，这一块最多也只能提速 1.32 倍。我们还测了一个很自然的设计：把高频块交给 Intel AMX（一条 CPU 指令就能乘一个小稠密矩阵），其余部分留给引擎。即使稠密部分以 AMX 峰值速度运行，在最佳切分点上剩余部分仍占总时间的 47% 和 76%。结论是：只有当低频取值和结果写出也很便宜时，矩阵加速器才划得来。

2.3 我们的思路

表 1 对比了现有系统。

Tessera 顺着数据的偏斜来分工：稀疏路径处理低频取值和输出，CPU 矩阵加速器处理稠密核心，两者在代价模型为每条查询设定的边界处会合。现有系统都至少缺一项上述特性，也没有一个用上 CPU 矩阵加速器。

稀疏路径是 Tessera 的主路径，因为低频取值产生了大部分结果单元格。比如要统计和某个词一起出现的词，Tessera 遍历包含它的文章，为文章里的每个其他词的计数器加一，既不构建连接行，也不探测哈希表。只有被碰过的计数器才变成结果行，不排序，直接写进每线程的输出块。

乘积前剪枝。 两个词共同出现的文章数不可能超过其中任一词出现的文章数（有权重时再乘以 X 的最大元素）。因此，有阈值时 Tessera 在任何乘法之前就丢掉不可能达标的取值；top-k 查询先在最高频取值上跑一轮，得到一个阈值。

矩阵加速器上的稠密核心。 Intel AMX、Arm SME、IBM Power10 的矩阵单元等矩阵加速器，都是 CPU 中能用一条指令乘小矩阵（称为分块，tile）的部件，直接使用 CPU 的缓存和内存，乘法速度是向量单元的数倍。但它总是乘整个分块，分块里的零和有效乘积代价一样。所以，结果中的一个块只有当密度（有效乘积占比）超过盈亏平衡密度 d* 时，放到加速器上才划算。按频率排序后，偏斜会让这样的块聚集在高频取值处：例如 4,096 个最高频新闻词组成的块包含了全部连接行的 48%，密度高于 d*；医学摘要语料则不是这样。可见核心划不划算取决于数据本身。

边界放在哪里。 边界太小，稠密块留给了稀疏路径；太大，加速器要算大量几乎全零的分块。加速器越快，d* 越低，边界外移；稀疏路径越便宜，d* 越高，边界内移；剪枝也会移动边界。因此需要代价模型逐条查询地确定边界。没有足够稠密的块时，Tessera 只走稀疏路径，代价仅是代价模型的那一遍扫描。剪枝只丢掉那些所有单元格都不可能达标的取值，结果保持精确。

三、设计

3.1 总体流程

Tessera 是一个单一算子，引擎用它替换原来的连接和聚合。输入是行 (k, x)（或带权重的 (k, x, v)），输出是 C = XᵀX 的非零单元格。流程分六步：

1. 收集：引擎适配器在执行计划中识别出连接聚合，把输入行一次性流式交给 Tessera；键被编码为稠密整数，重复的 (k, x) 合并为一项。
2. 排名：按频率给取值编号（最高频为第一），并按键存储 X，每行内的取值按排名排序。这样前 H 个排名组成的块就是 C 中最稠密的块，一个数 H 就能切分工作，剪枝也变成对排名的一刀切。
3. 剪枝：对带 HAVING 或 ORDER BY ... LIMIT 的查询，丢掉单元格不可能达标的取值。
4. 定边界：代价模型为本查询选出边界 H。
5. 乘积：排名都小于 H 的取值对在矩阵加速器（论文中称为 grid）上计算；两个低频取值的对走稀疏路径；边界取值与低频取值的对，求和时走稀疏路径，计数时经“重-轻路径”（heavy-light path）在加速器上算。每个无序对只算一次。
6. 输出：单元格写入每线程输出块，适配器把排名映射回原始取值，以引擎的类型输出。

支持的查询：自连接聚合（COUNT() 或 SUM(a.v * b.v)，可带 a.x < b.x 等取值对过滤、HAVING f >= c 或 ORDER BY f DESC LIMIT k）；两关系上的 COUNT() 或 SUM(a.v * b.w)；高于阈值的物品相似度（余弦或 Jaccard）。键和取值须为不含 NULL 的 64 位整数或字符串，权重为数值。其他查询（如 a.x <> b.x、第三个关系、额外的分组列或聚合、行级安全）适配器不改计划，由引擎原样执行。

3.2 稀疏路径与输出

直接把 X 交给稀疏矩阵库再把结果矩阵转回行，会做很多查询并不需要的工作：库会把 C 构建成排序好的矩阵，常常算对称乘积的两半，用哈希表累加，还要在算完所有单元格后才应用阈值。Tessera 的原则是只算关系型结果需要的部分：结果只需要乘积的一半，接受无序的行，而且只有可能达标的取值才参与计算。

• 对称稀疏路径：用 Gustavson 算法一次算 C 的一列 j（j ≥ H），多线程并行处理不同列。对每个包含 j 的行，把该行中排名小于 j 的取值 i 的乘积累加进以 i 为下标的数组。由于每行按排名排序，扫描到 j 即可停止，每个无序对只算一次。最后被碰过的数组项就是第 j 列的结果单元格，输出后只重置这些项。
• 取值剪枝：对计数和整数权重，|C(i, j)| 不超过取值 i 那一列 |X| 的总和乘以 |X| 的最大元素。Tessera 对排名的每个后缀取这些上界的最大值，于是可能达标的取值构成一个前缀。阈值越高前缀越短，其余取值在任何乘法和边界选择之前就被剪掉。对 top-k，先在 256 个最高频取值上跑一轮得到第 k 大单元格的下界，再在第二轮只加入可能达到该下界的其他取值。
• 输出块：每个线程把单元格追加到自己的输出块（每块 2²⁰ 个单元格，内存紧张时更小），这些块就是结果。超出引擎内存上限时，每个线程把块追加到各自的临时文件，读取时再映射回来，避免线程争用同一个文件。

3.3 选择稠密边界

难点有三：加速器按分块计费，非零分块数取决于行如何分组而不仅是块的密度；边界有准备成本（要排列它覆盖的行并构建分块）；同一张表在不同阈值下需要不同边界。固定规则总会顾此失彼。

Tessera 的做法是在每条查询执行前，从数据本身廉价地估算每个候选边界的耗时：候选值 H ∈ {0, 512, 1024, 2048, …}，从 512 翻倍到 65,536（或全部取值）。估算由四项组成：分块项（含有效乘积的分块数，在几千组连续行的样本上统计）、块项（每对取值块的簿记与结果开销）、准备项（边界覆盖的每行、每个非零元素的开销）、稀疏项（精确统计涉及边界外取值的乘积数）。因为每行的取值已按排名排序，一遍扫描就能同时评估所有候选。模型有七个常数，每台机器用几次强制边界的运行测一次即可。

3.4 从稀疏行喂给矩阵加速器

即使在边界内，一行也只包含 H 个取值中的少数几个，稠密核心大部分仍是零。如果把边界复制成“每个键一行”的稠密矩阵再调用厂商库，副本会随输入而非结果增长，库还会乘那些全零的分块。

Tessera 直接从涉及某个分块的行构建该分块，并跳过没有任何行同时包含两个块取值的分块：

• 由行构建面板（panel）：把边界切成若干取值块、把行切成若干连续行组（chunk）；对共享非零元素的“块 × 行组”写一个面板（每个值一字节），并标记块的哪一半有值；每个块用一个位图标记哪些行组有面板。由于每值一字节，加速器路径支持 1～255 的计数和权重；更大的整数权重走精确整数求和的稀疏路径，实数权重走浮点稀疏路径（不剪枝）。
• 行的顺序：含相同取值的行应落在同一行组。Tessera 用两个 MinHash 签名对行排序，近似地把相似行聚在一起。
• 成对循环：对块对 (b1, b2)，先把两个块的行组位图求交，只读取两者共有的行组；再在每个共有行组里只乘有值的那一半面板。结果分块保存 32 位和，若边界列总和显示可能溢出 2³¹，就不用边界执行该查询。
• 分组成对循环：像分块矩阵乘法那样安排块对的顺序，让面板在留在缓存时被重复使用（末级缓存放一组 b2 的面板，二级缓存放几个 b1 的面板）。
• 重-轻路径：边界取值与低频取值的对数量很多，计数时把一批低频取值的行收集起来，用每行的边界取值位图在加速器上统计。

3.5 在数据库引擎中运行

把数据导出给外部程序会产生来回拷贝，引擎也无法限制或取消这部分工作；把算子写死在某个引擎里，又会绑定该引擎的计划结构。Tessera 的核心是一个带小型 C 接口的库：接收批量输入行、查询选项和取消回调，返回结果行，由适配器转换为引擎类型。

任何提供三类常见扩展点的引擎都能承载 Tessera：一个把 Tessera 替换进连接和聚合位置的钩子（有可扩展优化器时改写子计划，用户照写原 SQL；没有时作为表函数调用）；用引擎自己的扫描读取输入行；以引擎类型返回结果行。

把查询留给引擎：Tessera 要为每一行输入付费（构建 X），而引擎的哈希连接和聚合是为每一行连接结果付费，所以连接放大倍数小的查询在引擎里更快。适配器根据引擎为每张表保存的行数和去重计数，估算“每行输入产生的连接行数”，低于阈值时交还引擎执行。

引擎资源：工作线程在调用线程所在的 CPU 上运行，语句超时等信号仍由引擎线程处理；输出在引擎内存上限下溢写到引擎的临时目录；Tessera 在各阶段之间和每个工作项上轮询取消回调，由适配器抛出引擎自己的取消错误。

3.6 两关系乘积与物品相似度

两者复用加速器路径和稀疏路径，只改变排名后的结果如何在两者间切分。对 XᵀY，两个输入的取值共享一个排名空间，各有自己的边界，代价模型的变体同时选两个边界。对物品相似度，Tessera 在输出单元格时用精确计数 C(i, j) 和规模 C(i, i)、C(j, j) 计算相似度；对集合而言，只有较小规模至少达到较大规模的某个比例（余弦为 t²，Jaccard 为 t）时才可能超过阈值 t，于是可以跳过规模相差过大的对。

3.7 其他矩阵加速器

原型面向 Intel AMX，移植到其他 CPU 矩阵加速器是后续工作。Arm SME 的外积指令和 IBM Power10 的矩阵单元同样把 8 位乘积累加为 32 位和，作者预计加速器路径和代价模型可以迁移，但有三点差异：Power10 的 8 位乘积有一个有符号操作数，权重大于 127 需要第二次乘积；SME 的分块大小随处理器向量长度变化，面板宽度也要跟着变；两者都是累加向量外积，而不是乘两个从内存加载的分块，喂数方式和代价模型都要相应调整。

四、实现

Tessera 已为 DuckDB、PostgreSQL、Spark、SQLite 四个引擎发布，安装方式与该引擎的其他扩展一样，一条命令即可。核心库约 4,600 行 C++，每个引擎一个适配器，不修改任何引擎源码（表 2）。在 x86-64 上，核心在运行时选择 AMX、AVX-512 或 AVX2；其他 CPU（如 Apple 芯片）运行可移植版本。没有 AMX 时所有取值都走稀疏路径；在不支持 AVX2 的 x86-64 CPU 上，适配器把所有查询留给引擎。

表 2：适配器如何把 Tessera 接入四个引擎

分发方式：DuckDB 中执行 INSTALL tessera FROM community；PostgreSQL 用户运行 pgxn install tessera_pg，针对本地服务器编译扩展；Spark 用户通过 --packages 引入 Maven Central 上的构件；Python 程序从 PyPI 安装 SQLite 扩展。二进制包面向 Linux x86-64 和 macOS Apple 芯片。

适配器阈值：DuckDB、PostgreSQL、Spark 的适配器在“估计每行输入的连接行数”低于某个界限时把连接交还引擎。界限设在“均匀键自连接下 Tessera 比引擎慢一倍”的位置：DuckDB v2.0.0 为 6，评测用的 v1.3.2 构建为 4；PostgreSQL 和 Spark 的计划从来不会快一倍，因此不设界限。在整数和字符串键、单一类型权重、取值对过滤、阈值、两关系和相似度上，每个适配器返回的行都与引擎自身计划一致（浮点舍入误差除外），溢出时抛出相同的错误。

五、评估

5.1 方法

测试服务器为两颗 Intel Xeon Silver 4514Y（每颗 16 核，每核 2 MB L2，每颗 30 MB L3）、256 GB DDR5 内存，Ubuntu 24.04、Linux 6.17。每次运行只用一个插槽的 16 核及其 NUMA 节点的 128 GB 内存，所有引擎内存上限均为 100 GB。

表 3：评测用的关系 R(k, x)

对比对象包括各引擎自身的执行计划（DuckDB v1.3.2 和 1.5.6、PostgreSQL、SQLite、Spark）、SPALM，以及引擎之外的程序：oneMKL 的 SYRK、SuiteSparse:GraphBLAS、MMJoin、频繁项集挖掘工具 Eclat 和 FP-growth（限定为二项集），以及多种集合相似度连接算法。在 DuckDB 中，每条查询取 DuckDB 两个版本的计划和 SPALM 中最快者作为“现有最快系统”。负载包括完整乘积（COUNT）、带 a.x < b.x 和 1%～0.1% 支持度 HAVING 阈值的剪枝查询，以及 k 从 10 到 10⁴ 的 top-k 查询。

5.2 主要结果

• 对比现有系统：Tessera 在所有关系上都胜过所有现有系统。完整乘积上比现有最快系统快 5.8～18.8 倍；在最适合 SPALM 的高频块上也快 2.8～4.3 倍。例如在新闻语料上，Tessera 用时 2.9 秒，SPALM 54.3 秒，引擎 8.6 分钟。在基因矩阵上，引擎用时 30 分钟，Tessera 只要 1.0 秒，快 1,802 倍。
• 阈值的影响：剪枝查询保留的对越多，Tessera 的耗时只缓慢增长，而引擎在任何阈值和 k 下耗时都一样。新闻语料上的 top-k 查询，Tessera 对每个 k 都不到 1 秒，引擎要 226 秒。与用 SQL 写的 Apriori 频繁项过滤相比，Tessera 在新闻和评分数据上快 40～252 倍；只有在 kosarak 的 1% 支持度下（很少有取值达标），SQL 改写快 1.3 倍。
• 其他引擎：在 PostgreSQL、Spark 和 SQLite 中，Tessera 比各引擎自身计划快 44～394 倍；即使只用一个线程，也比 SQLite 计划快 95～253 倍。
• 对比稀疏库和项集挖掘：在完整乘积上比 oneMKL SYRK 和 GraphBLAS 快 4.2～31.3 倍；在 0.3% 支持度下比只计数不输出的 MMJoin 快 7.1～14.0 倍；单线程统计频繁对比 Eclat 和 FP-growth 快 11.5～98.6 倍（kosarak 会话较短，收益缩小到 1.9～5.1 倍）。

5.3 两关系乘积与物品相似度

• 两关系乘积：在 MovieLens 评分 × 标签的两种连接上，Tessera 比 SPALM 快 9.8～17.1 倍，比 DuckDB 1.5.6 快 15.3～120.3 倍；DuckDB v1.3.2 在按用户连接时内存溢出。标签数据没有稠密核心，代价模型不设边界，收益全部来自稀疏路径和输出。
• 放大倍数小的连接：IMDb 电影的演员、关键词、公司三种连接，每行输入只产生 2.1～5.3 行连接结果，DuckDB 统计信息估计为 1.1～2.0，低于界限 4，适配器正确地交还引擎执行。若强制使用 Tessera，DuckDB 1.5.6 反而快 1.20～3.40 倍。
• 相似度连接：阈值从 0.95 降到 0.1 时，Tessera 耗时最多增长 2.9 倍。在 MovieLens 余弦相似度上，结果从 160 万对增长到 2.22 亿对，耗时只从 0.45 秒增长到 1.29 秒。16 线程下比 GraphBLAS 快 3.3～32.9 倍，在 0.7 及以下阈值比并行 AllPairs 最多快 4.3 倍，且结果精确（并行 AllPairs 用浮点上界与阈值比较，最多漏掉 4.9% 的结果）。单线程下，在 0.95 的高阈值时前缀过滤类算法最多领先 75 倍，但在 0.1 时 Tessera 反超 2.3～3.2 倍。

5.4 深入分析

• 矩阵加速器的贡献：16 线程下，有无边界的收益从新闻语料完整乘积的 1.43 倍到最稠密的基因矩阵的 6.88 倍不等；单线程下为 1.68～8.92 倍。加速器让 Tessera 在高频块上相对 SPALM 的优势从 2.2～2.3 倍提高到 3.4～4.3 倍，在基因矩阵上从 1.7 倍提高到 5.8 倍。从 1 到 16 线程，Tessera 扩展了 8.0～12.0 倍。
• AMX 对比向量单元：在设了边界的关系上，AMX 比 AVX-512 VNNI 版加速器路径和不带加速器路径的 AVX-512 版快 1.33～6.38 倍，因为 VNNI 上一次分块乘积的代价高 5.3～5.5 倍，盈亏平衡密度也相应提高。在没有稠密核心的 kosarak 上，AVX-512 版反而快 10%～14%。
• 消融实验：分组成对循环带来 1.40～1.96 倍收益（没有它，加速器路径在新闻和评分的完整乘积上甚至不如不设边界）；取值剪枝在剪枝查询上最多带来 2.93 倍，与加速器合计最多 5.53 倍；重-轻路径和行排序的影响不超过 1.19 倍。
• 稀疏路径收益拆解：以“哈希累加器 + 计算两半 + 组装排序矩阵”的逐行乘积为起点，稠密计数器最多带来 2.1 倍，只算一半约 2 倍，不排序的每线程输出块最多 3.7 倍。与稀疏库的差距主要来自“只算一半”和“输出行而不是矩阵”，这恰恰是关系型结果允许的。
• 逐查询边界的必要性：固定边界取错时最多慢 7.0 倍，三个完整乘积的最佳边界在 4,096 到 16,384 之间变化。代价模型在新闻和基因数据上选中最佳值，在评分数据上只慢 6.5%。在模型未拟合过的 18 个关系（含 PubMed、图数据和 6 个合成 Zipf 关系）共 36 条查询中，34 条在模型所选边界下的耗时与最佳强制边界相差不超过 10%；而最好的固定选择（不设边界）最多落后 9.1 倍。
• 输出内存上限：把输出内存限制在 256 MB 时，Tessera 几乎把 5.71 亿和 8.83 亿个单元格全部写入文件，只慢 2.8% 和 3.3%。
• 收益有限的情况：没有稠密块时（kosarak、PubMed、图数据），代价模型让所有取值走稀疏路径，额外开销最多 6.2%。实数权重下，Tessera 在新闻和评分数据上比 SPALM 快 8.7～10.5 倍（整数权重下为 10.6～13.2 倍），但在基因矩阵上只快 1.1 倍，因为加速器路径不再处理它的稠密块。

六、相关工作（略述）

连接-投影与库内线性代数方案加速的是高频取值的乘法，却把低频取值和结果留在慢路径上；Tessera 反过来把低频取值和结果当作主要工作，只把稠密核心交给加速器。稀疏矩阵库在数据库之外计算矩阵，而 Tessera 在引擎内计算关系型结果并跳过不需要的工作。频繁项集挖掘和相似度连接算法各自服务一类查询且在数据库之外运行，Tessera 把同样的剪枝带进了引擎内的 SQL 查询。GPU 和 CPU 上已有把稀疏数据打包进矩阵分块的核函数工作，但它们加速的是单个稀疏核函数，Tessera 则是在现有 CPU 上、在引擎里运行完整查询。

七、结论

Tessera 是一个面向偏斜稀疏关系的数据库连接聚合算子。在这类关系上，大部分时间花在低频取值和输出上，而不是乘法本身，这限制了“乘法更快”所能带来的收益。因此 Tessera 先把这些部分变便宜，再只把高频取值组成、由代价模型逐查询确定大小的稠密核心交给 CPU 矩阵加速器。在 DuckDB 中，它比现有最快系统快 2.8～18.8 倍；在四个引擎中，比引擎自身计划最多快三个数量级。

作者认为这一经验不止适用于连接聚合：矩阵加速器对数据库引擎帮助最大的方式，是引擎保留稀疏的关系型执行，只把偏斜产生的稠密子问题（如连接和分组中的热点值）交给它，而不是把查询整体改写成稠密线性代数。

译者注

1. 先判断你的查询是不是“这一类”：Tessera 针对的是“自连接（或两表按同一键连接）+ 按两侧各一列分组计数/求和”，且连接放大倍数大的场景，典型如商品共购、标签共现、共同好友、物品相似度。如果你的查询是普通的星型模型事实表关联维表，每行输入只产生一两行连接结果，Tessera 的适配器本来就会把查询交还引擎，不会有收益。判断方法很简单：用 EXPLAIN ANALYZE 看连接算子输出行数是否比输入多出几个数量级。
2. 即使不装扩展，思路也能用：论文里收益最大的几项（阈值前置剪枝、只算无序对的一半、高频值单独处理）在 Spark 或 SQL 层面也能部分模仿。例如先按单值频次过滤掉不可能达到支持度阈值的取值，再做自连接；对 a.x < b.x 只算一半；把热门值单独拎出来处理以缓解数据倾斜。这些都是 MapReduce 服务 MRS 上跑 Spark SQL、或在数据仓库 GaussDB（DWS）里做共现统计时常用的调优手段，Tessera 的实验正好量化了每一步大概值多少。
3. 硬件与部署注意点：矩阵加速器路径依赖 Intel AMX（第四代及以后的至强可扩展处理器提供），在云上选用弹性云服务器 ECS 时，请以实例规格页面标注的 CPU 型号为准确认是否支持；没有 AMX 时 Tessera 只走稀疏路径，论文的消融数据显示仍有可观收益。论文列出的二进制包只覆盖 Linux x86-64 和 macOS Apple 芯片，在鲲鹏等 Arm 服务器上大概率需要自行从源码构建（译者推测，原文未专门讨论）。托管数据库服务一般只允许安装平台白名单内的扩展，PostgreSQL 扩展能否在托管实例上使用，需先查对应产品文档；自建 DuckDB、Spark 或 PostgreSQL 则可以直接试用。
4. 它还是一篇刚提交的论文：评测由作者本人完成，部分对比系统（如 SPALM）也出自同一作者团队的前序工作。生产环境引入前，建议先在自己的数据分布上复测，并关注扩展与所用引擎版本的兼容性。

相关阅读

• 数据湖分析智能体自己造工具：TEAL 无标注演化目录与索引，紧预算下准确率提升 21.7 个点：https://bbs.huaweicloud.com/blogs/b5fa0cbdf56b4ec981b88888f57f9930
• AI 智能体直接改数据库，约束谁来守？PostgreSQL 约束索引让跨表校验提速最高 2.41 倍：https://bbs.huaweicloud.com/blogs/829a4a73dede49a0b89ffd0a1f9bff3e