Databend 是一个存储、计算别离的云原生数仓，根据云上基础设施完成了存储和计算的无限扩容及按需按量付费模式。

在 Databend 中,数据以Databend Fuse Engine 结构组织，全体结构参阅：Databend 存储架构总览。在这篇文章里咱们先来回忆一下：

Databend 索引结构说明

在上篇文章中咱们描绘了 Databend Fuse table 存储组织结构。本篇来讲一下 Databend Fuse Engine 的索引结构。

Databend 支撑的索引有：

  • Min/Max 索引

  • 稀少索引（暂未启用）

  • Bloom index

  • Cluster key

这些索引都是自动创建，不需求用户再去办理。现阶段首要工作的索引有：Min/Max 索引， bloom index 索引以及 Cluster key 索引， 其间 稀少索引还没启用。下面别离描绘一下他们的结构。

Min / Max 索引

这个索引是 OLAP 数据库的灵魂索引，是 Databend Fuse Engine 现在首要运用的索引。这个索引首要分为三个级别存储：

使用 show create table 找到对应的 Snapshot 文件，这个文件也是 table 的 root 起始位置。

showcreatetableontime(
`Year`INT,--第1列
...
)ENGINE=FUSESNAPSHOT_LOCATION='1/458/_ss/71b460c61fa943d1a391d3118ebd984c_v1.json'

把这个文件下载到本地使用 vscode 翻开后格式化：

showcreatetableontime(
`Year`INT,--第1列
...
)ENGINE=FUSESNAPSHOT_LOCATION='1/458/_ss/71b460c61fa943d1a391d3118ebd984c_v1.json'{
"format_version":1,
"snapshot_id":"71b460c6-1fa9-43d1-a391-d3118ebd984c",
"timestamp":"2022-11-29T03:44:03.419194Z",
"prev_snapshot_id":null,
"schema":{
"fields":[
...--字段界说相关
],
"metadata":{}
},
"summary":{
"row_count":90673588,
"block_count":200,
"perfect_block_count":0,
"uncompressed_byte_size":65821591614,
"compressed_byte_size":2761791374,
"index_size":1194623,
"col_stats":{
...
"0":{--Ontime表中第一个字段Year的min/max索引
"min":{
"Int64":1987
},
"max":{
"Int64":2004
},
"null_count":0,
"in_memory_size":362694352,
"distinct_of_values":0
},
...
}，
},
"segments":[
...
[
"1/458/_sg/ddccbb022ba74387be0b41eefd16bbbe_v1.json",
1
],
...
],
"cluster_key_meta":null
}{
"format_version":1,
"snapshot_id":"71b460c6-1fa9-43d1-a391-d3118ebd984c",
"timestamp":"2022-11-29T03:44:03.419194Z",
"prev_snapshot_id":null,
"schema":{
"fields":[
...--字段界说相关
],
"metadata":{}
},
"summary":{
"row_count":90673588,
"block_count":200,
"perfect_block_count":0,
"uncompressed_byte_size":65821591614,
"compressed_byte_size":2761791374,
"index_size":1194623,
"col_stats":{
...
"0":{--Ontime表中第一个字段Year的min/max索引
"min":{
"Int64":1987
},
"max":{
"Int64":2004
},
"null_count":0,
"in_memory_size":362694352,
"distinct_of_values":0
},
...
}，
},
"segments":[
...
[
"1/458/_sg/ddccbb022ba74387be0b41eefd16bbbe_v1.json",
1
],
...
],
"cluster_key_meta":null
}

能够在这个文件中，清楚的看到第三列的 min 最小值是 1 , 最大值是 31 。在 Snapshot 这层的 min/max 索引首要用于解决数据有没有问题，例如：

selectavg(DepDelay)fromontimewhereYear='2003';

上面查询，如果这儿的条件在所有的 Snapshot 对应的 min/max 都没找到对应的区间，就能够直接返回空。

接下来是 Databend fuse engine 重要索引构建存储在 Segments 中，Snapshot 文件最终面能够看到当前的 Snapshot 包含了哪些 Segment。咱们解析一个 Segment 文件:

{
"format_version":1,
"blocks":[
{--block...
...
"row_count":556984,
"block_size":405612604,
"file_size":25302413,
"col_stats":{
...
"0":{
"min":{
"Int64":2003
},
"max":{
"Int64":2003
},
"null_count":0,
"in_memory_size":2227936,
"distinct_of_values":1
},
...
},
"col_metas":{
--用于记录每个col的起始位位置及长度
},
"cluster_stats":null,
"location":[
"1/458/_b/e4f3795c79004f22b80ed5ee821edf23_v0.parquet",
0
],
"bloom_filter_index_location":[
"1/458/_i_b_v2/e4f3795c79004f22b80ed5ee821edf23_v2.parquet",
2
],
"bloom_filter_index_size":60207,
"compression":"Lz4Raw"
...
}
],
"summary":{
"row_count":11243809,
"block_count":25,
"perfect_block_count":25,
"uncompressed_byte_size":8163837349,
"compressed_byte_size":339392734,
"index_size":1200133,
"col_stats":{
...
"0":{
"min":{
"Int64":1988
},
"max":{
"Int64":2003
},
"null_count":0,
"in_memory_size":44975236,
"distinct_of_values":0
},
...
}
}
}

能够看到 Segment 中包含了一个 Segment 级别的 min/max 索引，一同每个 Block 也有一个 min/max 索引 。

相同咱们还能够拿 ontime 字段中 Year 的 min/max 索引散布情况：

Databend 索引结构说明

相同拿上面的 SQL 语句：

selectavg(DepDelay)fromontimewhereYear='2003'

在这个语句中首先在 Snapshot 中射中有用区间，然后使用 Segment 供给的总览供给的 summary 信息承认有用射中到一个详细的 Segment ,然后在 Segment 中的 block 中找到有用的 Block（Parqeut) 根据需求的字段，从 “col_metas” 找到运用列的起始位置获取相应的值。这样大概是一个 min/max 索引的工作过程。

咱们会发现 SELECT 运用 min/max 索引：首要是使用 min/max 索引，把一个详细的查询落到不同的 segment 和 block 上。

Databend 中每行都会有 min/max 索引，String 类型的现在只需部分长度做 min/max 索引。

Bloom Index

上面的例子中咱们展现了一个使用 min/max 索引最终射中到一个 Block 上的请求, 而且这个 Block 的 min/max 是一样的，后面的操作只需求读取这个 Block 就能够了。在 Databend 实践应用场景还遇到很多的字符串等值类查询。

Databend 关于这类查询首先也是使用 min/max 索引定位详细的 Block，然后再使用 bloom_filter_index_location 供给的 bloom index 定位到详细的 offset 位置。

关于 Databend Bloom index 完成能够参阅：bohutang.me/2022/11/21/…

Cluster Key

上面咱们给咱们演示的 min/max 索引，看起来已经能够完美工作了，但实践工作中可能数据是无序的写入，造成每个 Block 或是 Segment 的 min/max 重合复非常多，那么就会呈现

Databend 索引结构说明

查询 Age = 20 & Age = 35 需求拜访 3 个 parquet

引进 Cluster Key 如果运用 Age 做为 Cluster key, Databend 会尽量让按 age 列排序，一同把小的文件进行兼并，例如：

Databend 索引结构说明

关于 cluster key 更多信息请参阅：databend.rs/doc/sql-com…

总结

现在 Databend Fuse engine 还比较年轻，还有不少能够优化的当地，现在索引层面现在比较老练是 min/max, bloom index 索引， 其间 Cluster key 估计在 Databend 0.9 版本发布时就能够稳定下来。后续引进 Parquet 的多个 RowGroup 也会把稀少索引启用。

Databend Fuse engine 也一直在进化，您有什么好的建议也欢迎反馈给咱们。

关于 Databend

Databend 是一款开源、弹性、低成本，根据对象存储也能够做实时剖析的新式数仓。期待您的关注，一同探究云原生数仓解决方案，打造新一代开源 Data Cloud。

  • Databend 文档：databend.rs/

  • Twitter：twitter.com/Datafuse\_L…

  • Slack：datafusecloud.slack.com/

  • Wechat：Databend

  • GitHub ：github.com/datafuselab…