Databend 索引结构说明

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

在 Databend 中,数据以Databend Fuse Engine 结构组织，整体结构参考：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 起始位置。

show create table ontime(
`Year` INT,  -- 第 1 列
...
) ENGINE=FUSE SNAPSHOT_LOCATION='1/458/_ss/71b460c61fa943d1a391d3118ebd984c_v1.json'

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

show create table ontime(
`Year` INT,  -- 第 1 列
...
) ENGINE=FUSE SNAPSHOT_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 索引主要用于解决数据有没有问题，例如：

select avg(DepDelay) from ontime where Year='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 索引分布情况：

同样拿上面的 SQL 语句：

select avg(DepDelay) from ontime where Year='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 重合复非常多，那么就会出现

查询 Age = 20 & Age = 35  需要访问 3 个 parquet

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

关于 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…