背景介绍

在交互式分析场景下，很多时候除了固定字段之外，还会有一些动态字段的需求。比如，在游戏场景下，需要动态存储用户每个游戏的play时长。

这种场景下，我们希望在一张表中同时存储固定字段和动态字段的信息，并且可以高效地使用动态字段做过滤查询。

Map类型使用示例

CREATETABLEuser_game_play

(

    mid UInt64,

   buvidString,

    game_play_durationMap(String, UInt32),

   log_dateString

)

ENGINE=MergeTree()

PARTITION BY log_date

ORDERBYmid; 

insert into user_game_play values (1, '123', map('王者荣耀',3600, 'FGO', 1800), '2021-11-14');

SELECT game_play_duration['王者荣耀'] AS duration FROM test.user_game_play

┌─duration─┐

│    3600 │

└──────────┘

Map类型的取值实现

ClickHouse从v21.1.2.15-stable版本开始支持Map类型（详见PR#1586），其读取key对应value的实现逻辑大致如下：

1. 内部用两个数组(ColumnArray)分别存储key和value值，我们分别称之为 key_array和value_array。

2. 对于Map的取值操作（即map[‘key’]操作），先在从key_array中找到要找的key的下标，然后根据这个下标到value_array里获取对应的值。

具体实现细节详见源码FunctionArrayElement::executeMap.

从上述分析可知，Map类型的工作方式本质上和用两个数组分别存储key和value的方式是一样的。只是在功能上做了封装，提高了用户使用的便捷性，但在性能上并没有变化。

Map类型的跳数索引

索引类型

为了提升map操作的性能，我们在社区版本的Map类型基础上，给其加上了多种类型的skipping

index，包括 bloom_filter ，tokenbf_v1，ngrambf_v1

上面这三种skipping index本质上都是用bloom filter存储每个索引粒度的索引值。其中，tokenbf_v1和ngrambf_v1只支持String类型，bloom_filter可支持各种类型。

1. ngrambf_v1是对字符串中固定长度的substring做bloom filter存储和检索。

2. tokenbf_v1是对由非字母数字符号分隔开的token做bloom filter存储和检索。

3. bloom_filter则是直接对字段取值做bloom filter存储和检索。

Map类型的跳数逻辑

在数据写入到Map类型字段时，所有的key会被抽取出来生成每个索引粒度对应的bloom filter。

对于针对Map类型字段的过滤条件，如：

    where game_play_duration[‘王者荣耀’] >= 1800 and game_play_duration[‘王者荣耀’] <=3600

会做以下处理：

1. 从filtering condition中提取map的key。

2. 分析过滤操作符（如 = , >=, <=, >, <, like , in , not in），如果该过滤条件在map不包含对应key时不可能成立，则利用bloom filter过滤掉不可能包含对应key的数据块（索引粒度）。

具体实现细节详见源码PR #28634。

添加索引示例

CREATETABLEuser_game_play

(

    mid UInt64,

    buvidString,

    game_play_durationMap(String, UInt32),

    log_dateString,

    Index idx game_play_duration TYPE bloom_filter GRANULARITY 2,

)

ENGINE=MergeTree()

PARTITION BY log_date

ORDERBY mid;

影响跳数效果的因素

在我们的性能测试中，给Map类型添加skipping index可以收获的性能提升差异很大。

效果好的case可以十几到几十倍的性能提升，而效果不好的则没有明显提升。

跳数索引的过滤效果和两个数据特性相关：

1. 索引值的cardinality：这个比较好理解，当索引值cardinality很小（比如性别，可取值只有男和女），那么过滤效果通常有限。

2. 索引值的分布是否聚集：ClickHouse的跳数索引和主键索引一样，也是稀疏索引。当索引值分布非常离散时，即使包含查询值的记录占比很小，但可能每个数据块（索引粒度）都包含查询值，那么所有数据都需要读进内存做过滤判断。

Map相关函数

ClickHouse社区版本中已经实现了一些map类型相关的函数，包括：

1. map : 基于传入的键值对生成Map类型对象。

2. mapKeys : 获取map对象的所有keys。

3. mapValues : 获取map对象的所有values

4. mapContains : 检查map对象是否包含指定的key。

更多map相关函数细节详见这里。

另外，我们添加了两个map函数mapContainsKeyLike和mapExtractKeyLike（已合并进社区版本，详见这里） 。其中mapContainsKeyLike函数支持通过tokenbf_v1索引进行跳数过滤。