聚类与排序键

分区是一种数据组织策略，它将数据分成粗略的段，从而缩小查询范围。然而，当查询基于与分区键不同的高基数列进行筛选时，分区通常显得不足。例如，如果一个表按 transaction_date 分区，查找特定 customer_id 的查询仍需扫描该日期分区内的所有文件。为了在这种情况下提升效率，现代列式数据库使用聚类和排序键在微分区或数据块级别组织数据存储。

块修剪的工作原理

分析型数据库通常不使用事务系统中常见的B树索引。它们依赖于存储在每个数据文件或微分区头部的元数据。这些元数据记录了该数据块中各列的最小值和最大值。当查询执行时，引擎会将 WHERE 子句的谓词与这些最小/最大范围进行比较。

如果谓词值超出了特定数据块的范围，引擎会完全跳过该数据块。此过程称为块修剪或数据跳过。然而，这种技术的有效性完全由数据在磁盘上的物理排序方式决定。

考虑一个订单ID数据集，它分布在三个存储块中。

未排序数据（低效修剪）：

• 数据块 A： ID [105, 902, 340] → 最小值: 105, 最大值: 902
• 数据块 B： ID [101, 880, 205] → 最小值: 101, 最大值: 880
• 数据块 C： ID [500, 102, 999] → 最小值: 102, 最大值: 999

如果你查询 ID = 205，引擎必须扫描所有三个数据块，因为 205 落入每个数据块的最小/最大范围内。这些范围重叠严重，使得元数据在筛选时失去作用。

已排序/聚类数据（高效修剪）：

• 数据块 A： ID [101, 102, 105] → 最小值: 101, 最大值: 105
• 数据块 B： ID [205, 340, 500] → 最小值: 205, 最大值: 500
• 数据块 C： ID [880, 902, 999] → 最小值: 880, 最大值: 999

现在，查询 ID = 205 会让引擎立即忽略数据块 A 和数据块 C。它只扫描数据块 B。I/O 的这种大幅减少是定义聚类键的主要目的。

数据布局的比较，说明了紧密的最小/最大范围如何让查询引擎跳过不相关的数据块。

线性排序与交错排序

选择单个列作为排序键会建立线性顺序。如果该特定列是查询的主要筛选条件，这种方式非常有效。然而，分析型工作负载通常需要同时在多个维度上进行筛选，例如按 Region 和 ProductCategory 查询。

在线性排序中（例如，ORDER BY Region, ProductCategory），数据首先完全按 Region 排序。ProductCategory 仅在具有相同 Region 的行中进行本地排序。如果你仅按 ProductCategory 查询，数据库将无法有效修剪数据块，因为每个 Region 很可能都包含所有 Product Category。

为此，现代数据仓库实现了多维聚类或 Z 排序（Z 阶曲线）。这种技术将多维数据映射到一维，同时保持所有聚类列的局部性。它交错值在二进制上的表示，确保对于任一列具有相似值的数据点最终在磁盘上存储在一起。

权衡是，Z 排序对于第一列的效率略低于纯线性排序，但对于列表中的第二、第三或第四列则效率高得多。

选择聚类列

选择正确的聚类列需要分析你的查询模式。你不能按所有列进行聚类，因为这样做会稀释排序效果（按十列排序对于最后几列来说实际上是随机顺序）。

有效的聚类键通常具有以下特点：

1. 高基数： 具有许多不同值的列（如 user_id 或 order_id）最能从聚类中获益。低基数列（如 boolean 标志或具有 3 个值的 status）会生成具有相同范围的大块，使得修剪效果不佳。
2. 频繁筛选： 优先考虑那些频繁出现在 WHERE 子句或 JOIN 条件中的列。
3. 大表数据量： 聚类会带来后台维护成本（重写文件）。它通常适用于多TB范围的表，因为在这种情况下，全表扫描的成本过高。

我们可以通过计算列的聚类深度或聚类因子来估算其聚类的有效性。如果一个表有 $N$ 个数据块，并且特定值 $X$ 存在于其中的 $M$ 个数据块中，那么理想的聚类深度是 $1$（即该值仅存在于 1 个数据块中）。如果 $M \approx N$，数据是随机分布的，对 $X$ 的查询将导致全表扫描。

维护与自动聚类

随着新行的插入，数据自然会变得无序。如果你每天追加数据，新行自然会按时间（摄取日期）排序，但它们在 customer_id 或 product_id 方面很可能是无序的。

随着时间的推移，聚类因子会下降。为了保持性能，数据库必须执行维护操作，通常称为“清理”或“重新聚类”。这个过程会读取无序的微分区，在内存中对数据进行排序，并写入新的、有序的微分区。

性能下降与聚类深度相关联。随着相同的值分散到更多文件（深度越高），查询引擎必须读取更多数据才能满足相同的谓词。

设计模式时，你必须平衡这些计算密集型维护操作的成本与查询检索所节省的资源。对于很少查询的表，完美的聚类是资源的浪费。对于支持面向用户的仪表板的核心事实表，持续聚类的投入是满足 SLA 要求的必要条件。