ClickHouse源码笔记6:探究列式存储系统的排序

分析完成了聚合以及向量化过滤，向量化的函数计算之后。本篇，笔者将分析数据库的一个重要算子：排序。让我们从源码的角度来剖析clickhouse作为列式存储系统是如何实现排序的。

本系列文章的源码分析基于clickhouse v19.16.2.2的版本。

1.执行计划

老规矩，咱们还是先从一个简单的查询出发，通过一步步的通过执行计划按图索骥clickhouse的执行逻辑。

select * from test order by k1;

咱们先尝试打开clickhouse的debug日志看一下具体的执行的pipeline。

这里分为了5个流，而咱们所需要关注的流已经呼之欲出了mergesorting与partialsorting，clickhouse先从存储引擎的数据读取数据，并且执行函数运算，并对数据先进行部分的排序，然后对于已经有序的数据在进行mergesort，得出最终有序的数据。

2. 实现流程的梳理

那咱们接下来要梳理的代码也很明确了，就是partialsortingblockinputstream与mergingsortedblockinputstream。

• partialsortingblockinputstream的实现
  partialsortingblockinputstream的实现很简单，咱们直接看代码吧：

block partialsortingblockinputstream::readimpl()
{
    block res = children.back()->read();
    sortblock(res, description, limit);
    return res;
}

它从底层的流读取数据block，block可以理解为doris之中的batch，相当一批行的数据，然后根据自身的成员变量sortdescription来对单个block进行排序，并根据limit进行长度截断。

sortdescription是一个vector，每个成员描述了单个排序列的排序规则。比如
： null值的排序规则，是否进行逆序排序等。

/// description of the sorting rule for several columns.
using sortdescription = std::vector<sortcolumndescription>;

• sortblock的函数实现

接下来，我们来看看sortblock函数的实现，看看列式的执行系统是如何利用上述信息进行数据排序的。

void sortblock(block & block, const sortdescription & description, uint64 limit)
{
    /// if only one column to sort by
    if (description.size() == 1)
    {
        bool reverse = description[0].direction == -1;

        const icolumn * column = !description[0].column_name.empty()
            ? block.getbyname(description[0].column_name).column.get()
            : block.safegetbyposition(description[0].column_number).column.get();

        icolumn::permutation perm;
        if (needcollation(column, description[0]))
        {
            const columnstring & column_string = typeid_cast<const columnstring &>(*column);
            column_string.getpermutationwithcollation(*description[0].collator, reverse, limit, perm);
        }
        else
            column->getpermutation(reverse, limit, description[0].nulls_direction, perm);

        size_t columns = block.columns();
        for (size_t i = 0; i < columns; ++i)
            block.getbyposition(i).column = block.getbyposition(i).column->permute(perm, limit);
    }

这里需要分为两种情况讨论：1. 单列排序。2.多列排序。多列排序与单列的实现大同小异，所以我们先从单列排序的代码开始庖丁解牛。它的核心代码就是下面的这四行：

    column->getpermutation(reverse, limit, description[0].nulls_direction, perm);
    size_t columns = block.columns();
    for (size_t i = 0; i < columns; ++i)
           block.getbyposition(i).column = block.getbyposition(i).column->permute(perm, limit);

先通过单列排序，拿到每一列在排序之后的icolumn::permutation perm;。然后block之中的每一列都利用这个perm, 生成一个新的排序列，替换旧的列之后，就完成block的排序了。

如上图所示，permutation是一个长度为limit的podarray, 它标识了根据排序列排序之后的排序位置。后续就按照这个perm规则利用函数permute生成新的列，就是排序已经完成的列了。

columnptr columnvector<t>::permute(const icolumn::permutation & perm, size_t limit) const
{
    typename self::container & res_data = res->getdata();
    for (size_t i = 0; i < limit; ++i)
        res_data[i] = data[perm[i]];

    return res;
}

这里细心的朋友会发现，string列在sortblock函数之中做了一些额外的判断

  if (needcollation(column, description[0])) {
            const columnstring & column_string = typeid_cast<const columnstring &>(*column);
            column_string.getpermutationwithcollation(*description[0].collator, reverse, limit, perm);
 }

这部分是一个特殊的字符串生成perm的逻辑，clickhouse支持用不同的编码进行字符串列的排序。比如通过gbk编码进行排序的话，那么中文的排序顺序将是基于拼音顺序的。

• getpermutation的实现
  所以，在clickhouse的排序过程之中。getpermutation是整个排序算子实现的重中之重， 它是column类的一个虚函数，也就是说每一个不同的数据类型的列都可以实现自己的排序逻辑。我们通过columnvector的实现，来管中规豹一把。

template <typename t>
void columnvector<t>::getpermutation(bool reverse, size_t limit, int nan_direction_hint, icolumn::permutation & res) const
{
        if (reverse)
            std::partial_sort(res.begin(), res.begin() + limit, res.end(), greater(*this, nan_direction_hint));
        else
            std::partial_sort(res.begin(), res.begin() + limit, res.end(), less(*this, nan_direction_hint));
    }
    else
    {
        /// a case for radix sort
        if constexpr (std::is_arithmetic_v<t> && !std::is_same_v<t, uint128>)
        {
                return;
            }
        }

        /// default sorting algorithm.
        for (size_t i = 0; i < s; ++i)
            res[i] = i;

       pdqsort(res.begin(), res.end(), less(*this, nan_direction_hint));
    }
}

这部分代码较多，笔者简化了一下这部分的逻辑。

• 如果存在limit条件，并且列的长度大于limit，采用std::partial_sort进行perm的排序。
• 如果为数字类型，并且不为uint128类型时，则采用radix sort计数排序来对perm进行排序。
• 如不满足前二者的条件，则使用快速排序作为最终的默认实现。

好的，看到这里。已经完整的梳理了partialsortingblockinputstream，得到了每一个输出的block已经按照我们的排序规则进行排序了。接下来就要请出mergesortingblockinputstream来进行最终的排序工作。

• mergesortingblockinputstream的实现
  从名字上也能看出来，这里需要完成一次归并排序，来得到最终有序的排序结果。至于排序的对象，自然上面通过partialsortingblockinputstream输出的block了。

直接定位到readimpl()的实现，clickhouse这里实现了spill to disk的外部排序逻辑，这里为了简化，笔者先暂时拿掉这部分外部排序的逻辑。

block mergesortingblockinputstream::readimpl()
{
    /** algorithm:
      * - read to memory blocks from source stream;
      */

    /// if has not read source blocks.
    if (!impl)
    {
        while (block block = children.back()->read())
        {
            blocks.push_back(block);
            sum_rows_in_blocks += block.rows();
            sum_bytes_in_blocks += block.allocatedbytes();

            /** if significant amount of data was accumulated, perform preliminary merging step.
              */
            if (blocks.size() > 1
                && limit
                && limit * 2 < sum_rows_in_blocks   /// 2 is just a guess.
                && remerge_is_useful
                && max_bytes_before_remerge
                && sum_bytes_in_blocks > max_bytes_before_remerge)
            {
                remerge();
            }

        if ((blocks.empty() && temporary_files.empty()) || iscancelledorthrowifkilled())
            return block();

        if (temporary_files.empty())
        {
            impl = std::make_unique<mergesortingblocksblockinputstream>(blocks, description, max_merged_block_size, limit);
        }
       
    block res = impl->read();
    return res;
}

由上面代码可以看到，mergesortingblockinputstream这部分就是不断从底层的partialsortingblockinputstream读取出来，并存储全部存储下来。最终读取完成之后，利用mergesortingblocksblockinputstream类，完成所有blocks的归并排序工作。而mergesortingblocksblockinputstream类就是简单完成利用堆进行多路归并排序的过程代码，笔者在这里就不再展开了，感兴趣的同学可以自行参考mergesortingblockinputstream.cpp部分的实现。

3.要点梳理

第二小节梳理完clickhouse的排序算子的实现流程，这里进行一些简单的要点小结：

1. clickhouse的排序实现需要利用排序列生成对应的perm，最终利用perm完成每一个block的排序。

2. 所以每一个不同数据类型的列，都需要实现getpermutation与permute来实现排序。并且可以根据数据类型，选择不同的排序实现。比如radix sort的时间复杂度为o(n)，相对快速排序的时间复杂度就存在了明显的优势。

3. 排序算法存在大量的数据依赖，所以是很难发挥simd的优势的。只有在radix sort下才些微有些部分可以向量化，所以相对于非向量化的实现，不存在太多性能上的优势。

4. 小结

ok，到此为止，咱们可以从clickhouse的源码实现之中梳理完成列式的存储系统是如何实现排序的。
当然，这部分跳过了一部分重要的实现：spill to disk。这个是确保在一定的内存限制之下，对海量数据进行排序时，可以利用磁盘来缓存排序的中间结果。这部分的实现也很有意思，感兴趣的朋友，可以进一步展开来看这部分的实现。
笔者是一个clickhouse的初学者，对clickhouse有兴趣的同学，欢迎多多指教，交流。

5. 参考资料

clickhouse源代码