返回资讯中心
外部精选
软件工程
#开发者实时流

Vortex 博客:列式存储分区统计如何加速查询过滤

来源标题:Statistics Are Aggregates

Vortex 发布技术博客,介绍列式格式如何按行分块存储最小值、最大值等统计信息来跳过不匹配的数据区域,并以 x < 10 的查询为例说明过滤加速原理。文中称这类统计为 zone,并追溯了 1998 年 Moerkotte 提出的 SMA(小型物化聚合)概念。

Hacker News 最新surprisetalk2026/11/3 · 14 天前26 分钟阅读

以下正文由 AI 翻译自 Hacker News 最新(原文版权归原站所有),可能存在偏差,重要内容请以原文为准。

深入探讨深入探讨博客博客X 标志用你的数据试试 用你的数据试试 最新文章 2026 年 10 月 14 日 · 作者 Nicholas Gates · 7 分钟阅读 SQL SELECT * FROM measurements WHERE x < 10; 列式格式把每一列拆分成若干行块,并为每个块存储统计信息, 例如最小值和最大值。Vortex 把这些块称为 zone。1 如果某个 zone 内 x 的值介于 50 和 90 之间,那么该 zone 中没有任何一行 能满足 x < 10,因此统计信息可以让读取端跳过这个 zone, 而无需解码它。 这是分析型数据库中最古老的技术之一。现代的问题 聚焦于保留哪些统计信息、每条统计信息应覆盖多少行,这两者 都取决于数据和查询(例如, Prammer 等人,CIDR '25)。 Moerkotte 1998 年的原始论文 把这些统计信息称为小物化聚合(small materialized aggregates,SMA)。虽然许多 系统把这些统计信息称为 zone map,但我们认为值得按字面意思理解 SMA 这个名字, 因为我们在写入文件时会对 zone 内的行计算一个聚合函数(例如 MIN(x))。 然而,许多查询引擎并不这样对待 SMA。它们用统计信息来 跳过无法匹配过滤条件的 zone,但随后又从扫描返回的行中计算聚合, 仿佛统计信息根本不存在。我们认为这种割裂 让引擎无法利用文件已经完成的工作。统计信息就是一种 聚合,而把它当作聚合来对待的引擎可以用它来回答查询的一部分, 而不仅仅是用它来避免读取数据。 #组合统计信息 代码图标 SQL SELECT MIN(x) FROM measurements; 首先,我们谈谈如何用统计信息回答简单查询(不带 过滤条件)。如果每个 zone 都存储自己的最小值,那么文件的最小值就是 各 zone 最小值中的最小值,而表的最小值就是各文件 最小值中的最小值。我们可以在任何拥有元数据的层级上用元数据回答这个查询, 而无需读取 x。MAX 和 COUNT 以相同方式合并,MAX 取最大值,COUNT 求和。 AVG 不是这样工作的。以两个 zone 为例,[10, 20] 和 [100]。它们的 平均值分别是 15 和 100,对这两个平均值再求平均得到 57.5, 而所有三个值的平均值约为 43.33。对平均值求平均会让单行 zone 获得与两行 zone 相同的权重。 相反,我们应该为每个 zone 保留 sum 和 count:(30, 2) 和 (100, 1)。我们把 sum 和 count 分别相加得到 (130, 3),然后才 做除法。这些对就是聚合部分状态(aggregate partials):我们为一组 行维护的状态,以便在产生最终答案之前合并结果。对于 MIN, 部分状态就是最小值本身。对于 AVG,它是 (SUM(x), COUNT(x)),其中 count 不包含 null。 为了把统计信息从 zone 逐级合并到文件再到表,我们必须存储部分状态 而不是最终答案。Vortex 已经这样定义统计信息:每一个 都是某个聚合函数的部分状态,由查询执行期间运行的同一份代码 计算得出。 #过滤条件带来阻碍 当然,很少有查询会聚合整张表。更典型的查询会先 过滤行: 代码图标 SQL SELECT MIN(x) FROM measurements WHERE recorded_at >= TIMESTAMP '2026-09-01 00:00:00'; 表中存储的 x 最小值可能来自 8 月的某一行,而不是 来自 9 月及以后的过滤条件;因此,表级统计信息在这里帮不上忙。 我们合并的层级越高,一个部分状态覆盖的行就越多,其中 越可能有某些行不满足过滤条件。因为表级最小值 几乎无法回答任何带 WHERE 子句的查询,引擎在查询处理过程中很少尝试使用 它们。DataFusion 的 aggregate-statistics 规则 仅在严格条件下才用元数据回答查询,例如统计信息精确 且没有 GROUP BY 子句。在上述 WHERE 子句之后,它针对 x 的 统计信息不再精确,查询便回退到扫描 x。 #分解统计信息 把统计信息从 zone 级合并到文件级让我们沿层级向上走。为了 回答带过滤条件的查询,我们往回向下走,那里 zone 足够小,以至于 过滤条件对 zone 内的所有行一视同仁。 假设数据按时间聚簇。完全在 9 月之前的 zone 没有任何贡献,所以我们跳过它。如果某个 zone 中的每一行都来自 9 月或 之后,那么该 zone 存储的 x 最小值就是该 zone 的答案。对于跨越 截止时间的 zone,我们读取 recorded_at 来识别匹配的行,并 计算它们 x 值的最小值。 9 月 1 日8 月9 月 Zone 1跳过 Zone 2扫描匹配的行 Zone 3使用存储的 MIN(x) recorded_at → 每条横条表示一个 zone 的时间戳范围。此示例假设没有 null 时间戳,且 Zone 3 存储了 x 的最小值。 把这些 zone 分成这三种情况,与我们用于跳过时所用的 min-max 检查相同, 只是应用于 recorded_at。如果没有存储时间统计信息,我们 必须读取 recorded_at 才能判断。把一个无法使用的外层统计信息 分解回其组成统计信息之所以可行,是因为数据在过滤列上聚簇。大多数 zone 完全落在截止时间之前,统计信息让我们跳过它们;或者完全落在 之后,统计信息直接为它们给出答案。只有少数跨越截止时间的 zone 需要扫描。2 存储的最小值也能帮助处理不完全匹配的 zone。假设某个 zone 中的每一行 都匹配,且其存储的最小值为 4。如果下一个 zone 存储的最小值 为 9,那么其中没有任何行能胜过我们已经得到的 4,所以我们跳过它, 无需检查日期。如果它存储的最小值是 1,那么这个 1 可能 属于 8 月的某一行。它只告诉我们匹配行的最小值至少为 1, 所以我们仍然必须找出那些行。 一个完全匹配的 zone 所有日期 ≥ 9 月 1 日 Null 时间戳:0 存储的 MIN(x)4 返回 4↓→ 当前最小值 4 无需扫描 x。 下一个 zone 当前最小值4 存储的最小值:9跳过 zone 所有 x ≥ 9 存储的最小值:1检查匹配的行 所有 x ≥ 1 149x 下一个 zone 的两种可能。存储的 1 可能属于某一行,而该行不满足日期过滤条件。

(原文较长,此处译出前 6000 字,完整内容请点「打开原文」。)

正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。

打开原文
去社区讨论 →