分析完成了聚合以及向量化过滤,向量化的函数计算之后。本篇,笔者将分析数据库的一个重要算子:排序。让我们从源码的角度来剖析ClickHouse作为列式存储系统是如何实现排序的。
本系列文章的源码分析基于ClickHouse v19.16.2.2的版本。
老规矩,咱们还是先从一个简单的查询出发,通过一步步的通过执行计划按图索骥ClickHouse的执行逻辑。
咱们先尝试打开ClickHouse的Debug日志看一下具体的执行的pipeline。
image.png
这里分为了5个流,而咱们所需要关注的流已经呼之欲出了MergeSorting
与PartialSorting
,ClickHouse先从存储引擎的数据读取数据,并且执行函数运算,并对数据先进行部分的排序,然后对于已经有序的数据在进行MergeSort,得出最终有序的数据。
那咱们接下来要梳理的代码也很明确了,就是PartialSortingBlockInputStream
与MergingSortedBlockInputStream
。
它从底层的流读取数据Block,Block可以理解为Doris之中的Batch,相当一批行的数据,然后根据自身的成员变量SortDescription
来对单个Block进行排序,并根据limit
进行长度截断。
SortDescription
是一个vector,每个成员描述了单个排序列的排序规则。比如
: null值的排序规则,是否进行逆序排序等。
接下来,我们来看看sortBlock
函数的实现,看看列式的执行系统是如何利用上述信息进行数据排序的。
这里需要分为两种情况讨论:1. 单列排序。2.多列排序。多列排序与单列的实现大同小异,所以我们先从单列排序的代码开始庖丁解牛。它的核心代码就是下面的这四行:
先通过单列排序,拿到每一列在排序之后的IColumn::Permutation perm;
。然后Block
之中的每一列都利用这个perm
, 生成一个新的排序列,替换旧的列之后,就完成Block
的排序了。
生成Perm
如上图所示,Permutation
是一个长度为limit
的PodArray
, 它标识了根据排序列排序之后的排序位置。后续就按照这个perm
规则利用函数permute
生成新的列,就是排序已经完成的列了。
这里细心的朋友会发现,String
列在sortBlock
函数之中做了一些额外的判断
这部分是一个特殊的字符串生成perm
的逻辑,ClickHouse支持用不同的编码进行字符串列的排序。比如通过GBK编码进行排序的话,那么中文的排序顺序将是基于拼音顺序的。
getPermutation
是整个排序算子实现的重中之重, 它是Column
类的一个虚函数,也就是说每一个不同的数据类型的列都可以实现自己的排序逻辑。我们通过ColumnVector
的实现,来管中规豹一把。这部分代码较多,笔者简化了一下这部分的逻辑。
limit
条件,并且列的长度大于limit
,采用std::partial_sort
进行perm
的排序。UInt128
类型时,则采用Radix Sort
计数排序来对perm
进行排序。好的,看到这里。已经完整的梳理了PartialSortingBlockInputStream,得到了每一个输出的Block
已经按照我们的排序规则进行排序了。接下来就要请出MergeSortingBlockInputStream
来进行最终的排序工作。
Block
了。直接定位到readImpl()
的实现,ClickHouse这里实现了Spill to disk
的外部排序逻辑,这里为了简化,笔者先暂时拿掉这部分外部排序的逻辑。
由上面代码可以看到,MergeSortingBlockInputStream这部分就是不断从底层的PartialSortingBlockInputStream读取出来,并存储全部存储下来。最终读取完成之后,利用MergeSortingBlocksBlockInputStream类,完成所有Blocks的归并排序工作。而MergeSortingBlocksBlockInputStream类就是简单完成利用堆进行多路归并排序的过程代码,笔者在这里就不再展开了,感兴趣的同学可以自行参考MergeSortingBlockInputStream.cpp部分的实现。
第二小节梳理完ClickHouse的排序算子的实现流程,这里进行一些简单的要点小结:
perm
,最终利用perm
完成每一个Block的排序。getPermutation
与permute
来实现排序。并且可以根据数据类型,选择不同的排序实现。比如radix sort
的时间复杂度为O(n),相对快速排序的时间复杂度就存在了明显的优势。SIMD
的优势的。只有在radix sort
下才些微有些部分可以向量化,所以相对于非向量化的实现,不存在太多性能上的优势。OK,到此为止,咱们可以从Clickhouse的源码实现之中梳理完成列式的存储系统是如何实现排序的。
当然,这部分跳过了一部分重要的实现:Spill to disk
。这个是确保在一定的内存限制之下,对海量数据进行排序时,可以利用磁盘来缓存排序的中间结果。这部分的实现也很有意思,感兴趣的朋友,可以进一步展开来看这部分的实现。
笔者是一个ClickHouse的初学者,对ClickHouse有兴趣的同学,欢迎多多指教,交流。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。