在上一篇介绍 Delta Lake原理 的文章中，我提到Delta的商业版有很多开源版没有的“黑科技”，其中有一项就是 Z-order 。Z-order到底是什么，有什么“神奇功效“， 使得Databricks藏着掖着不想拿出来开源呢？ 这篇文章就来讲一讲这个话题。

首先需要明白Z-order是什么，以及能够帮助我们解决什么问题。摘抄下Wikipedia对Z-order的 定义

In mathematical analysis and computer science, functions which are Z-order, Lebesgue curve, Morton space filling curve,[1] Morton order or Morton code map multidimensional data to one dimension while preserving locality of the data points.

这段定义很抽象，还用了很多数学名词，像是勒贝格曲线（Legesgue curve），莫顿空间填充曲线（Morton space filling curve）等，很不好理解。但其实真正重要的是最后一句

Z-order可以将多维数据映射到一维，同时保持数据点的局部性 。

Delta正是借助Z-order保持数据局部性的优势，使得读取数据时可以skip掉大量block，从而极大地提升了Delta的性能。性能提高多少呢？引用下Databricks官方博客对z-order的介绍

Using Databricks Delta’s built-in data skipping and ZORDER clustering features, large cloud data lakes can be queried in a matter of seconds by skipping files not relevant to the query. In a real-world cybersecurity analysis use case, 93.2% of the records in a 504 terabytes dataset were skipped for a typical query, reducing query times by up to two orders of magnitude.

In other words, Databricks Delta can speed up your queries by as much as 100X .

在Databricks的一个真实场景中，Z-order帮助过滤掉了504TB数据中的93.2%，共计470TB数据。换言之， 提高了查询性能达100倍之多 。

Z-order的一种直观解释

按照我们的惯例，对于任何一项技术我们首先要问的一个问题就是： 这项技术为了解决什么问题？ 不过这次我不直接给出答案，而是先用一个例子来引出这个问题。

在 《理解ClickHouse的MergeTree引擎》 这篇文章中，我们提到了ClickHouse里的数据是 按照主键排序存储 的，因此通过主键可以快速地过滤掉无关的数据。

例如对于下面这张表

其中x是递增的整数，y是8192到1循环的整数，z还是递增的整数。共计81920条数据。

ClickHouse会将数据分成10个granule（每8192条数据为一个granule)，分别存储为10个文件，并在索引文件里保存每个granule的主键最大值和最小值。假设主键列为x，则索引如下表所示。

此时如果执行下面这条查询语句

SELECT sum(z) FROM test WHERE x < 10000
ClickHouse会根据索引确定只需要读取1和2这两个granule，从而减少了80%的数据读取量。
可是如果组成主键的列不止一列呢？也不复杂，只要把多列组成tuple，并且按照每列的大小关系定义tuple的大小关系即可。例如主键是x和y组成的复合主键，则索引文件的内容如下
granule
min
max
1
1,8192
8192,1
2
8193,8192
16384,1
...
...
...
10
73729,8192
81920,1
对于过滤条件包括x和y两列的查询
SELECT sum(z) FROM test WHERE x < 10000 AND y > 10000
或是只包括x的查询
SELECT sum(z) FROM test WHERE x > 70000
都可以继续使用索引文件来快速地过滤掉不满足条件的granule（这里我就不具体演示了）。
然而如果是只包括y的查询
SELECT sum(z) FROM test WHERE y > 70000
索引就完全无法使用了。 这是因为数据是按照(x, y)的值排序的，本质上来说首先x列是有序的，只有在x值相同时，y列才保证有序。所以这种基于x列排序的索引必须在过滤条件中包含x列时，才能充分利用有序的特性来过滤数据。
那么有没有一种索引，或者说一种排序方式，使得数据可以在x列和y列上“平等地”有序呢？ 这样无论x列还是y列，都可以单独地作为过滤条件。
而这正是Z-order希望解决的问题。
Z-order就是这样一种在复数列上“平等的”排序方式。
Z-order的基本思想
上一节提到Z-order本质是一种“排序方式”，使得数据按照这种顺序存储后，无论对主键的哪一列，都表现出一定的“有序性”，从而在查询时可以过滤掉许多无关的数据。
那么如何做到在复数列上有序呢？其实这是做不到的，Z-order也没有做到这一点。所以实际上Z-order退而求其次，实现的是在复数列上的“局部性” 。
什么是局部性呢？直观地来讲，就是数值接近的值不会相距太远。例如对于(3, 8)这个值，如果按照Z-order进行排序，则(4, 8)，(3, 9)或是(2, 7)，都不会距离(3, 8)太远。
具体来说，Z-order其实就是下图所示的这种“曲折型”的排序方式
图中的每个圆点代表(0, 0)，(2, 3)这样的数据点。可以看到，在Z-order的顺序里，(0, 0)在(1, 0)前，(1, 0)在(0, 1)前，然后(1, 1)又在(2, 0)前，以此类推。因为整个图看起来像是在反复地画“Z”字，所以这种排序方式被称为Z-order。
至于如何计算出这种排序，我先按下不表，会放到最后一节中详细讲解。
以下举一个具体例子来展示下Z-order如何应用于存储领域。假设我们有如下的数据，以x和y作为组成Z-order的两列，z列为需要做聚合的指标列。
x
y
z
0
0
1
0
3
1
1
0
1
1
2
1
2
1
1
2
3
1
3
0
1
3
3
1
按照Z-order排序以后，数据会变成下面这样（建议大家可以对照着上面的图，手动地对这些数据进行一下排序）。
(0, 0, 1)
(1, 0, 1)
(3, 0, 1)
(2, 1, 1)
(1, 2, 1)
(0, 3, 1)
(2, 3, 1)
(3, 3, 1)
接下来就只需要把数据按顺序保存成文件即可。至于这种存储的顺序有何好处？下一节会来谈谈。
Z-order和Skip Index
上一节展示了Z-order是如何对数据进行排序的，接下来谈谈这种存储顺序如何影响查询性能。其实Z-order最主要的效果是提高了数据在多个维度的局部性，从而提高Skip Index的效率。 注意只有在多个维度上构建索引才需要用到Z-order，因为如果只有一个维度，那直接对那个维度排序的局部性就是最好的。
在上周的文章《ClickHouse的索引原理》中，我讲了ClickHouse的Skip Index的原理。以其中的minmax索引为例，来看看Z-order对提高minmax索引的效率有哪些帮助。
还是以上一节的例子为例，假设设置ClickHouse的granularity为2（即每2行为一个granule）。如果按照ClickHouse默认的主键排序方式，数据的存储顺序如下
(0, 0, 1)
(0, 3, 1)
(1, 0, 1)
(1, 2, 1)
(2, 1, 1)
(2, 3, 1)
(3, 0, 1)
(3, 3, 1)
按照每2行为一个granule，最后产生的minmax索引就是
granule
x_min
x_max
y_min
y_max
0
0
0
0
3
1
1
1
0
2
2
2
2
1
3
3
3
3
0
3
从minmax索引可以很明显地看出，由于数据以(x, y)的顺序存储，所以在x列有很好的局部性，每个granule的(x_min, x_max)都是不相交的。而y列的局部性就比较差了，有比较多的重合。
这时如果我们运行下面这个简单的“过滤-聚合”查询
SELECT sum(z) FROM test WHERE y = 2
因为过滤条件是y=2，通过minmax可知需要读取的granule是0, 1, 2, 3，共4个。索引完全没有起到过滤的效果。
再来看看假如以Z-order对数据进行排序情况会怎样。上一节展示过数据以Z-order排序的结果如下
(0, 0, 1)
(1, 0, 1)
(3, 0, 1)
(2, 1, 1)
(1, 2, 1)
(0, 3, 1)
(2, 3, 1)
(3, 3, 1)
minmax索引则变成
granule
x_min
x_max
y_min
y_max
0
0
1
0
0
1
2
3
0
1
2
0
1
2
3
3
2
3
3
3
运行和上文同样的查询sql。
SELECT sum(z) FROM test WHERE y = 2
在新的minmax索引的帮助下，确定需要查询的granule只有2这一个。索引的过滤效率是75%。
于是我们看到，相比主键排序的存储方式，数据经过Z-order排序后，索引的过滤结果数从4个减少到了1个，效率提升了4倍之多。
实现Z-order
在讲完了Z-order的基本思想以及它能带来的好处之后，剩下的就只剩“如何实现”这个大话题了。这一块我可能不会展开太多，毕竟大部分读者都不太会需要自己去实现Z-order。
关于实现我只讲一个主题，那就是如何对一个数据集使用Z-order进行排序。
上文中我们展示了Z-order是一种Z字型的排序方式，那么对于任意一个数据集如何应用这个排序呢？换言之，怎么知道哪个数据在前，哪个数据在后？
我们先从最简单的一种情况开始，那就是Z-order只包含两列(x, y)（以下简称坐标），而且x和y都是整数类型。
实现上，我们使用一个值来确定坐标在Z-order上的顺序，这个值就被称为Z-Address。对每个坐标我们都可以计算出一个对应的Z-Address，而坐标在Z-order上的前后关系，就是Z-Address的大小关系。
至于Z-Address如何计算，办法是将x和y表示为二进制以后，每个bit位相互插值即可产生Z-Address。
对于更多列的，以及不是整数类型的情况，相对就更加复杂了，我这里不再细说。简单地来说，就是通过保序映射（order-preserving map）将其映射到整数以后，再使用整数的计算方法。
欢迎关注我的微信公众号：Data Dive，一个专注于大数据顶层认知和底层原理的公众号。