背景

Databend Clustering 的设计受到 Snowflake Data Clustering 和 Oracle Attribute Clustering 的启发。

注：这里的 Clustering 是分组、聚类的意思，下文将译为聚类。

聚类后的表会根据表中某一组列的值，以某种顺序存储数据。聚类有利于分区的消除（partition elimination）和文件碎片整理（file defragmentation）。默认情况下，数据是按照自然维度存储在表中的。因此，需要根据聚类键（cluster key）对表进行重聚类。另一方面，即使表已经聚类过，数据得到有效地组织，但如果不断地写入新的数据，聚类情况会随着时间的推移而变差。因此，有必要增加重聚类（recluster）操作。

设计

如果计划了解更详细的原理和图景，请参考 探索 Snowflake auto clustering 设计 一文。

执行全表排序的成本非常高，尤其是对于不断有新数据流入的表。为了在高效剪枝和低成本之间取得平衡，只需要对表进行粗略排序而不是完全排序。因此，在观测指标 一节中引入了两个指标来确定表是否已经有效聚类。重新聚类的目的是为了减少重叠 "overlap"和深度 "depth" 。

为了避免对同一份数据进行多次搅动，这里将数据块划分到不同的层（level），就像 LSM 树一样。那么重聚类就与 LSM 树的压缩操作类似。层表示该块中的数据被聚类的次数。重聚类操作是在同一层上进行的。

pub struct ClusterStatistics {
    ... ...
    pub level: i32,
}

重聚类操作的工作流程可以划分为两个任务：块选择（Block Selection）和块合并（Block Merge）。

语法

alter table [if exists] tbl_name recluster [final] [where condition]

如果指定 "final"，那么优化将会反复执行直到该表的聚类程度足够好。否则，重聚类的工作流程将只会运行一次。

观测指标

• "overlap"与指定块重叠的块数。
• "depth"在同一点重叠的块数。这些点是从聚类值域范围中的最小值和最大值中收集的。

块选择

新流入的数据的初始层是第 0 层（level 0）。我们首先要关注的就是这些较新的数据，换句话说，选择操作优先在第 0 层执行。这样做的优点是可以减少写放大。1.计算每个点的深度和重叠的块数，汇总得到 "avg_depth" 。这个算法已经反映在 system$clustering_information 中，这里不再进行复述。avg_depth 的理想结果是 1 。为了实现粗略排序，需要定义一个阈值（threshold）或者是一个比率（ratio）（"threshold = blocks_num * ratio"）。只要 "avg_depth" 不大于该阈值。就认为这一层中的块的聚类程度足够好，那么我们将对下一层执行块选择。2.选择深度最大的点范围（一个或多个）并选择该范围所覆盖的区块作为下一次块合并的对象集。如果存在不止一个的深度最大的范围，那么在块合并过程中，可能会出现多组块并行的情况。

Tip:

• 聚类键（cluster key）可能会在表中存在数据的时候创建/变更，故而可能存在一些没有按聚类键进行排序的块。目前计划是在重聚类过程中暂时忽略这些块。
• 如果某个块的聚类键只有一个值（最大值和最小值相等，达到一个不变的状态）且行数 “row_num” 为 “1_000_000” ，那么重聚类时，将其所处层数设为 -1 并过滤掉。
• 需要考虑选定的块的总大小，以免在排序时遇到内存溢出（out of memory, OOM）。

块合并

接下来就需要对收集到的块进行排序和合并。当合并后的块超过某个确定的阈值（"1_000_000" 行）之后，就会进一步拆分成多个块。新生成的块放入下一层。然后，我们需要组织块并生成新的段和快照，最后更新表的元信息。如果在此期间有新的 DML 执行，当前的工作流将无法提交（commit），并返回错误。具体的处理流程仍然需要进一步的讨论。选择和合并操作会重复进行，直到表的聚类程度足够好。