希尔伯特曲线对液体聚类的影响

Question

我了解到 Databricks 的新 Liquid Clustering 功能使用 Hilbert Curve 将记录放入不同的 DLT (Parquet) 底层文件中。

我猜测您为液体聚类选择的列作为该算法的输入，而文件的选择是该算法的输出。

但是我并不真正理解其中的含义，或者这与典型的数据库索引或主键算法有何不同，我认为它们更像树。实际上，Databricks 的工作人员告诉我，该算法也使用树，但这并不能真正帮助我理解。

这意味着什么？例如，假设液体按 4 列聚集。前 3 列基本上是自变量，第四列依赖于它们，因为它是它们的哈希值。在典型的数据库中，我认为这使得第四列变得无关紧要，因为当您沿着树向下移动那么远时，您已经利用了它包含的信息，因此您应该从索引中删除该列以节省空间。

但是有人告诉我，由于正在使用希尔伯特曲线，因此包含第四列仍然可能很有价值。这是正确的吗？有人可以解释一下并添加一些颜色吗？

编辑：我可能有点错误，并且希尔伯特曲线是在之后使用更传统的 ZORDER 树？

Answer 1

液体集群到底是什么？从概念上讲，液体集群类似于 SQL Server 的聚集索引 - 它以物理方式组织数据，以便相邻记录（同一 parquet 文件中的记录）具有相似的集群列值。

从技术上讲，它使用希尔伯特曲线来实现这一点。它不使用 z 曲线，也与树没有任何关系。

您应该在聚类键中包含该列吗？ 是的，如果该列在过滤器中经常使用。

在您的示例中，如果您通过哈希搜索，则 3 列上的索引没有用 - 您需要获取用作哈希函数输入的 3 个键。将哈希值作为第四列将按哈希值组织数据，并在您查找特定哈希值时帮助修剪数据文件。

它节省还是浪费任何空间？不。包含或排除列只会影响行如何分组到文件中 - 它确实会影响占用的空间量。

那么添加一列是免费的吗？添加一列确实会影响其他列的修剪有效性。让我们举个例子：一个包含 X 列和 Y 列的表，每列均匀分布值 0、1、2、3。

假设您的表大小为 1 GB，目标 parquet 文件大小为 256 MB。 Liquid 聚类会将表组织成 4 个文件，但看看它根据聚类键是否是 X 与 X+Y 有多么不同：

  Y 0   1   2   3           Y 0   1   2   3
X +---------------+       X +-------+-------+
0 |    file 1     |       0 |       |       |
  +---------------+         | file 1| file 2|
1 |    file 2     |       1 |       |       |
  +---------------+         +-------+-------+
2 |    file 3     |       2 |       |       |
  +---------------+         | file 3| file 4|
3 |    file 4     |       3 |       |       |
  +---------------+         +-------+-------+

第一种情况（按 X 聚类）：

• 当您通过X（或X+Y）搜索时，您可以修剪3个文件，而只需要扫描一个文件
• 当您按Y搜索时，您需要扫描所有文件

第二种情况（按X+Y聚类）：

• 当您通过X或Y搜索时，您可以修剪2个文件，并且只需要扫描2个文件
• 当您通过X+Y搜索时，可以修剪3个文件，只需扫描一个文件

任一选项都可以更好，这取决于表的查询方式。

类似更多的列、更多的值和更大的体积。包含额外的列只会使数据文件中其他列的关键范围更宽。

有用的参考资料：

• 有关液体聚类的 Databricks 文档
• 液体设计文档（很好地解释了它如何比 Z 曲线更好）
• 3d 曲线的示例图像（感受曲线在更高维度下的外观）