recluster table
概要
聚簇的灵感来源于 Snowflake 中的数据聚簇和 Oracle 中的属性聚簇。
聚簇表根据表中一组特定列的值，以有序的方式存储数据。聚簇有利于分区消除和文件碎片整理。
默认情况下，数据按照自然维度存储在表中。我们需要按照聚簇键对表进行重新聚簇。另一方面，即使聚簇表已经很好地聚簇，如果不断写入新数据，聚簇也会随着时间的推移而变差。因此，有必要添加重新聚簇操作。
设计
有关更详细的原则和图片，请参考 snowflake auto clustering。
执行全表排序的成本非常高，特别是对于不断有新数据流入的表。为了在高效修剪和低成本之间取得平衡，表只需要大致排序，而不是完全排序。因此，在 指标 中引入了两个指标来确定表是否聚簇良好。重新聚簇的目标是减少 overlap 和 depth。
为了避免多次重复处理同一块数据，我们将块分成不同的级别，类似于 LSM 树。重新聚簇类似于 LSM 压缩操作。level 表示该块中的数据已被聚簇的次数。重新聚簇操作在同一级别上执行。
pub struct ClusterStatistics {
... ...
pub level: i32,
}
重新聚簇操作的工作流程分为两个任务：块选择和块合并。
语法
ALTER TABLE [ IF EXISTS ] <table_name> RECLUSTER [ FINAL ] [ WHERE condition ] [ LIMIT <segment_count> ]
如果指定 final，则执行优化，直到表聚簇得足够好。否则，重新聚簇工作流程只会运行一次。
该语句应由表上的 DML 触发。
指标
-
overlap 与给定块重叠的块的数量。
-
depth 在同一点重叠的块的数量。这些点是从聚簇值域范围内的最小值和最大值收集的。
块选择
新传入数据的初始级别为 0。我们首先关注较新的数据，换句话说，选择操作优先在级别 0 上执行。这样做的好处是减少写放大。
-
计算每个点的深度和块的重叠，并汇总以获得 avg_depth。该算法已经反映在 system$clustering_information 中，这里不再重复。avg_depth 的理想结果是 1。为了实现大致排序，考虑定义一个阈值或一个比率（threshold = blocks_num * ratio）。只要 avg_depth 不大于此阈值，就可以认为此级别的块已聚簇良好，然后我们在下一级别执行块选择。
-
选择具有最高深度的点范围（一个或多个），并选择该范围覆盖的块作为下一块合并的对象集。如果存在多个具有最高深度的范围，则在块合并期间可以并行化多个块集。
提示：
1. 聚簇键可能在表具有数据时创建或更改，因此可能存在未按照聚簇键排序的块。考虑在执行重新聚簇时暂时忽略此类块。
2. 如果一个块的聚簇键只有一个值（最大值和最小值相等，达到恒定状态）并且其 row_num 为 1_000_000，则将其级别设置为 -1 并在执行重新聚簇时将其过滤掉。
3. 选择的块可能需要考虑总大小，否则排序可能会超出内存。
块合并
对收集的块进行排序和合并。合并后的块超过某个阈值（1_000_000 行）后，将分为多个块。新生成的块放入下一级别。
组织块并生成新的 segment 和 snapshot，最后更新表元数据。如果在此期间有新的 DML 执行，则当前工作流程将无法提交并返回错误。我们需要稍后考虑具体的处理流程。
重复选择和合并操作，直到表聚簇得足够好。
