Clickhouse技术分享: 分区裁剪

本文代码截图, 基于2021-07-19的master版本

DataPart存储

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
CREATE TABLE default.lineorder_local
(
`LO_ORDERKEY` UInt32,
`LO_LINENUMBER` UInt8,
`LO_CUSTKEY` UInt32,
`LO_PARTKEY` UInt32,
`LO_SUPPKEY` UInt32,
`LO_ORDERDATE` Date,
`LO_ORDERPRIORITY` LowCardinality(String),
`LO_SHIPPRIORITY` UInt8,
`LO_QUANTITY` UInt8,
`LO_EXTENDEDPRICE` UInt32,
`LO_ORDTOTALPRICE` UInt32,
`LO_DISCOUNT` UInt8,
`LO_REVENUE` UInt32,
`LO_SUPPLYCOST` UInt32,
`LO_TAX` UInt8,
`LO_COMMITDATE` Date,
`LO_SHIPMODE` LowCardinality(String)
)
ENGINE = MergeTree
PARTITION BY toYear(LO_ORDERDATE)
ORDER BY (LO_ORDERDATE, LO_ORDERKEY)
SETTINGS index_granularity = 8192;

选了Clickhouse社区官方的SSB测试套lineorder表为例, 他以toYear(LO_ORDERDATE)为分区键, 此时插入一些数据, 在Clickhouse DataPart级别的目录下, 会出现以下文件

image-20210719104902873

其中跟分区相关的有两个: partition.datminmax_LO_ORDERDATE.idx

partition.dat存储的是Partition的具体数值, 对应Clickhouse的源码

1
2
3
4
5
6
7
struct MergeTreePartition
{
Row value;
public:
void load(const MergeTreeData & storage, const DiskPtr & disk, const String & part_path);
void store(const MergeTreeData & storage, const DiskPtr & disk, const String & part_path, MergeTreeDataPartChecksums & checksums) const;
}

就是我们在system.parts表中看到的partition数值, 其中value的类型是Row, 对应表达式计算后的结果.

其中load函数是读取dat文件的数值到row中, store是存储row数据写入到文件里.

minmax_LO_ORDERDATE.idx存储的是对应字段LO_ORDERDATE的最大值和最小值范围

注意是LO_ORDERDATE的值, 而非toYear(LO_ORDERDATE)的值

对的代码在IMergeTreeDataPart的内部struct

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct MinMaxIndex
{
/// A direct product of ranges for each key column. See Storages/MergeTree/KeyCondition.cpp for details.
std::vector<Range> hyperrectangle;
bool initialized = false;

public:
MinMaxIndex() = default;

/// For month-based partitioning.
MinMaxIndex(DayNum min_date, DayNum max_date)
: hyperrectangle(1, Range(min_date, true, max_date, true))
, initialized(true)
{
}

void load(const MergeTreeData & data, const DiskPtr & disk_, const String & part_path);
void store(const MergeTreeData & data, const DiskPtr & disk_, const String & part_path, Checksums & checksums) const;
void store(const Names & column_names, const DataTypes & data_types, const DiskPtr & disk_, const String & part_path, Checksums & checksums) const;

void update(const Block & block, const Names & column_names);
void merge(const MinMaxIndex & other);
};

partition.dat类似, 他们都有loadstore方法, 但是MinMaxIndex额外有updatemerge, 因为DDL的SQL并不会改变partition, 但一个Delete where的语句有可能改变了上下界.

举例总结

举个例子来说, 如果一组数据, 只有3个值, 其中 LO_ORDERDATE列为: 1992-01-01,1992-06-021992-12-01, 那么partition.dat存储的值就是toYear(LO_ORDERDATE)的数值, 也就是1992; 而minmax_LO_ORDERDATE.idx存储的是1992-01-011992-12-01, 表示这个区间的上下确界.

数据查询

单调函数

下图是一个比较典型的单调递增函数:

image-20210715164527310

下图是一个典型的非单调递增函数

image-20210715164955108

单调函数的特点, x的最大最小值, 必然是y的最大最小值(单调递增).

所以很容易想到, 如果Clickhouse某个函数是单调的, 那么能通过DataPart上的minmax索引, 来过滤整个DataPart.

CK的整个分区裁剪实际上是在分区column上的minmax索引, 而非字面理解的分区裁剪

Clickhouse函数

在Clickhouse的IFunction.h文件里面, 有两个关于单调性的CK函数接口: hasInformationAboutMonotonicitygetMonotonicityForRange

image-20210719141057728

其中实现这些函数的, 基本上都可以实现分区裁剪功能, 没实现的不能实现分区裁剪.

Clickhouse Function接口在21年经过重构, 有一部分函数实现新的接口, 一部分实现老接口

image-20210719141707904

实现IFunctionBase的函数

image-20210719141638424

实现IFunction的函数

DataPart筛选

MergeTree引擎的数据筛选的代码封装在MergeTreeDataSelectExecutor类中

首先, 根据分区键和查询语句, 构造KeyCondition

image-20210719143828417

然后, 遍历每个DataPart过滤不符合条件的, 保留能够命中minmax索引的DP

image-20210719144211941

在方法checkInHyperrectangle判断函数链是不是都是单调, 例如toYear(toDate('2010-10-10'))这类两个函数复合的表达式, 两个都是单调函数, 因此单调链是有效的.

image-20210719145332621

限制

上文提到实现hasInformationAboutMonotonicity基本上能够分区裁剪, 之所以说基本上, 原因在于还有一些例外.

回到上面的KeyCondition, 在整个构造过程中, 有一个非常重要的函数isKeyPossiblyWrappedByMonotonicFunctionsImpl来判断是否单调.

image-20210719150454648

从代码上看到, 只有参数个数是1或者2个才能命中; 有2个参数的, 其中一个需要是常量表达式.

因此类似date_trunc(unit, value[, timezone])这函数也是单调的, 但是因为有3个参数, 因此也是无法命中索引.

这个是代码实现问题, 只是3个参数的函数非常少, 没啥动力去实现.