1.概述

索引和底层存储息息相关，doris采用LSM的存储结构，数据首先会写入Tablet对应的memtable中，memtable写满之后，数据会flush写入磁盘，形成一个个不可变的segment文件, 由于memtable用的是skiplist数据结构，skiplist数据是按照key排序的，所以flush到磁盘的segment文件也是按照key排序的，doris底层是按照列存储数据的，存储在一种SST的数据结构中，每列数据会被分为多个data page。

数据从memtable flush到磁盘分为两个阶段:

 1.将memtable中的行存结构转换为列存结构，并为每一列生成对应的索引结构

 2.将转换后的列存结构写入磁盘，生成segment文件。

segment文件分为数据区域、索引区域和footer三个部分，如下图所示:

说明:

data region: 存储各个列的数据信息，每列数据被分为多个data page。

index region: Doris 中将各个列的 index 数据统一存储在 Index Region，这里的数据会按照列粒度进行加载，所以跟列的数据信息分开存储

footer信息

footer信息段在文件的尾部，存储了文件的整体结构，包括数据域和索引域的位置等，共分为SegmentFooterPB，CheckSum，Length，MAGIC CODE 4 个部分。

segementFooterPB定义了元数据信息，包括列的元数据信息，索引的元数据信息，前缀索引信息，总行数等，数据结构如下:

2.索引

目前 Doris 主要支持两类索引：

1. 内建的智能索引，包括前缀索引和 ZoneMap 索引。
2. 用户手动创建的二级索引，包括 倒排索引、 bloomfilter索引、 ngram bloomfilter索引 和bitmap索引。

2.1前缀索引

Doris 不支持在任意列上创建索引。Doris 这类 MPP 架构的 OLAP 数据库，通常都是通过提高并发，来处理大量数据的。

本质上，Doris 的数据存储在类似 SSTable（Sorted String Table）的数据结构中。该结构是一种有序的数据结构，可以按照指定的列进行排序存储。在这种数据结构上，以排序列作为条件进行查找，会非常的高效。

在 Aggregate、Unique 和 Duplicate 三种数据模型中。底层的数据存储，是按照各自建表语句中，AGGREGATE KEY、UNIQUE KEY 和 DUPLICATE KEY 中指定的列进行排序存储的。

而前缀索引，即在排序的基础上，实现的一种根据给定前缀列，快速查询数据的索引方式。前缀索引又叫Short Key Index。

2.1.1存储结构

前缀索引是一种稀疏索引，数据写入过程中，每隔1024行会生成一个索引项，前缀索引会对每一个索引间隔的第一个数据行的前缀字段进行编码，前缀字段的编码与前缀字段的值具有相同的排序规则，即前缀字段的值排序越靠前，对应的编码值排序也越靠前。Segment 文件是按 Key 排序的，因此，前缀索引项也是按 Key 排序的。

一个 Segment 文件中的前缀索引数据保存在一个独立的 Short Key Page 中，其中包含每一条前缀索引项的编码数据、每一条前缀索引项的 offset、Short Key Page 的 footer 以及 Short Key Page 的 Checksum 信息。Short Key Page 的 footer 中记录了 Page 的类型、前缀索引编码数据的大小、前缀索引 offset 数据的大小、前缀索引项的数目等信息

Short Key Page 在 Segment 中的 offset 和大小会被保存在Segment文件的footer中，以便于数据读取时能够正确地从Segment文件中加载出前缀索引数据。前缀索引的存储结构如图所示：

查询时会先打开segment文件，然后在segment footer中找到short key page的offset及大小，然后读取对应的short key page中索引数据，并解析每一条前缀索引项。

2.1.2索引生成规则

doris将一行数据的前36个字节作为前缀索引，如果遇到varchar类型，前缀索引会直接截断，

2.1.3应用案例

1. 以下表结构的前缀索引为 user_id(8 Bytes) + age(4 Bytes) + message(prefix 20 Bytes)。

   ColumnName	Type
   user_id	BIGINT
   age	INT
   message	VARCHAR(100)
   max_dwell_time	DATETIME
   min_dwell_time	DATETIME

2. 以下表结构的前缀索引为 user_name(20 Bytes)。即使没有达到 36 个字节，因为遇到 VARCHAR，所以直接截断，不再往后继续。

   ColumnName	Type
   user_name	VARCHAR(20)
   age	INT
   message	VARCHAR(100)
   max_dwell_time	DATETIME
   min_dwell_time	DATETIME

当我们的查询条件，是前缀索引的前缀时，可以极大的加快查询速度。比如在第一个例子中，我们执行如下查询：

SELECT * FROM table WHERE user_id=1829239 and age=20；

该查询的效率会远高于如下查询：

SELECT * FROM table WHERE age=20；

所以在建表时，正确的选择列顺序，能够极大地提高查询效率。

2.2 Zone Map 索引

segment中的每列数据和列中的每个data page也会有zone map索引项，zone map索引记录每列及列中每个data page的最大值(max value)最小值(min value)，是否有Null值(has null)，是否有非Null值(has not null)等信息。初始化时(数据为空时)，max value会被设置为当前列类型的最小值， min value会被设置为当前列类型的最大值，has null和has not null均为false.

2.2.1索引生成规则

doris默认为key列(AGGREGATE KEY、UNIQ KEY 和 DUPLICATE KEY)开启ZoneMap索引，当表模型为 DUPULCATE 时，所有字段会开启 ZoneMap 索引。

数据写入时，会给data page生成zone map索引，当data page中有数据更新时，对应的zone map索引也要更新。更新规则如下:

 1.如果新增的数据为null, 则has null=true, 否则has not null=true

 2.如果新增数据小于zone map索引中的min value,则使用当前数据更新min value, 如果新增数据大于zone map索引中的max value,则使用当前数据更新max value.

当一个Data Page写满之后，不仅会更新当前data page的zone map索引，也会更新data page所在列的索引。

2.2.2 应用

在查询过程中，范围条件过滤字段会根据zone map索引中的统计信息选取扫描的数据范围。

查询如下:

SELECT * FROM table WHERE age > 20 and age < 1000

在没有命中 Short Key Index 的情况下，会根据条件语句中 age 的查询条件，利用 ZoneMap 索引找到应该扫描的数据 ordinary 范围，减少要扫描的 page 数量。

2.3 Ordinal 索引

2.3.1索引生成规则

Doris 底层采用列存的方式来存储数据，每一列数据会被分为多个Data Page。

数据刷写时，会为每一个Data Page生成一条Ordinal索引项，该索引项保存Data Page在Segment文件中的offset、Data Page的大小以及Data Page的起始行号，所有Data Page的Ordinal索引项会保存在一个Ordinal Index Page中， Ordinal Index Page在Segment文件中的offset以及Ordinal Index Page的大小会被保存在Segment文件的footer中，以便于数据读取时能够通过两级索引找到Data Page（首先，通过Segment文件的footer找到Ordinal Index Page，然后，通过Ordinal Index Page中的索引项找到Data Page）。

Ordinal Index Page包含以下信息：所有Ordinal索引项数据、Ordinal Index Page的footer以及Short Key Page的Checksum信息。Ordinal Index Page的footer中包含当前Page的类型、Ordinal索引项数据的大小、Ordinal索引项数目等信息。

如果列中只有一个Data Page时，即该列只有一条Ordinal索引项，则Segment文件中不需要保存该列的Ordinal索引数据，只需要将这唯一的Data Page在Segment文件中的offset以及该Data Page的大小保存在Segment文件的footer中。数据读取时可以通过Segment文件的footer直接找到这唯一的Data Page。Ordinal索引的存储结构如图3所示。

Ordinal索引的作用是为了方便其他类型的索引能够使用统一的方式查找Data Page，进而可以对其他类型的索引屏蔽Data Page在Segment文件中的offset

2.3.2查询过滤

查询时，会加载每一个列的Ordinal索引数据。通过Segment footer中记录的Ordinal索引的Meta信息判断当前列是否存在Ordinal Index Page，即判断当前列是否有多个Data Page。

如果当前列存在Ordinal Index Page，则从Segment footer中获取Ordinal Index Page在Segment中的offset和Ordinal Index Page的大小，然后从Segment文件中读取Ordinal Index Page数据，并解析出每一条Ordinal索引项，即可通过Ordinal索引项获取当前列中每一个Data Page的起始行号、Data Page在Segment中的offset以及Data Page的大小。

如果当前列不存在Ordinal Index Page，则可以直接从Segment footer中获取当前列中唯一的Data Page在Segment中的offset以及Data Page的大小。

2.4 BitMap索引

为了加速查询，doris支持用户为字段创建Bitmap索引，Bitmap索引由两部分组成:

  1.有序字典：有序保存一列中所有的不同取值。

  2.字典的位图：保存有序字典中每一个值的位图，值是字典值在列中的行号。

一列数据为[x, x, y, y, y, z, y, x, z, x]，一共包含10行，则该列数据的Bitmap索引的有序字典为{x, y, z}, 其中x、y、z对应的位图分别为：

x的位图: [0, 1, 7, 9]

y的位图: [2, 3, 4, 6]

z的位图: [5, 8]

如下图所示：

左侧为有序字典，右侧为字典每一个元素对应的位图。

2.4.1 索引生成规则

数据刷写时，会给用户指定的列创建Bitmap索引。向列中每添加一个值，都会更新当前列的BitMap索引。从Bitmap索引对应的有序字典查找新添加的值是否存在，如果已经存在，则只更新该字典值对应的位图；如果不存在，则将该值添加到有序字典中，并为这个值生成位图，Null值也会有单独的位图。可以看出Bitmap只适合低基数的列，如果基数很高，生成大量的位图会占用巨大的空间。

Bitmap索引的字典数据和位图数据分开存储。

字典数据存储在对应的dict page中，位图数据存储在对应的Bitmap page中，而dict page和Bitmap page的元信息会记录在segment footer中。如果一个列有多个dict page则会转化成两级索引，第二级索引为多个dict page,保存字典数据，每一个dict page生成一条value索引项，所有dict page的value 索引项会被被保存在一个value index page中作为一级索引，每一个的Value索引项记录了当前Dict Page中第一个字典值的编码以及当前Dict Page在Segment文件中的offset和大小，而value index page的元信息则保存在segment footer中。

同理如果一个列有多个Bitmap page则会转化成二级索引，第二级索引为多个的Bitmap Page，其中保存Bitmap索引的位图数据，每一个Bitmap Page生成一条Ordinal索引项，所有Bitmap Page的Ordinal索引项会被保存在一个Ordinal Index Page（注意，此处的Ordinal 索引与第3部分的Ordinal 索引不同，此处的Ordinal 索引指向Bitmap Page，而第3部分的Ordinal 索引指向Data Page）中作为一级索引，而Ordinal Index Page的元信息则保存在segment footer中。

2.4.2适用场景

Doris支持在建表时对指定的列创建Bitmap索引，也可以对已经创建的表执行Alter Table命令添加Bitmap索引。

ALTER TABLE table_name ADD INDEX index_name (column_name) USING BITMAP COMMENT ‘’;

目前只支持对TINYINT、SMALLINT、INT、 UNSIGNEDINT、BIGINT、LARGEINT、CHAR、 VARCHAR、DATE、DATETIME、BOOL和DECIMAL类型的字段创建Bitmap索引，其他类型的字段均不支持Bitmap索引。

Bitmap索引比较适合在基数较低的列上进行等值查询或范围查询的场景

2.5 Bloom Filter索引

Bloom Filter索引按照Data Page的粒度生成。数据写入时，会记录每一个写入Data Page的值，当一个Data Page写满之后，会根据该Data Page的所有不同取值为该Data Page生成Bloom Filter索引。数据查询时，查询条件在设置有Bloom Filter索引的字段进行过滤，当某个Data Page的Bloom Filter没有命中时，表示该Data Page中没有需要的数据，这样可以对Data Page进行快速过滤，减少不必要的数据读取。

2.5.1适用场景

Doris支持在建表时对指定的列创建Bloom Filter索引，也可以对已经创建的表执行Alter Table命令添加Bloom Filter索引。

ALTER TABLE table_name SET (“bloom_filter_columns”=”c1, c2, c3”);

目前只支持对SMALLINT、INT、UNSIGNEDINT、 BIGINT、LARGEINT、CHAR、 VARCHAR、DATE、DATETIME和DECIMAL类型的字段创建Bloom Filter索引，其他类型的字段均不支持Bloom Filter索引。对于创建了Bloom Filter索引的字段，查询条件是”=”、”is”或”in”语句时，才会使用Bloom Filter索引进行Data Page的过滤。Bloom Filter索引比较适合在基数较高的列上进行等值查询的场景。

2.6NGram BloomFilter索引

为了提升like的查询性能，增加了NGram BloomFilter索引。

2.6.1 NGram BloomFilter创建​

表创建时指定：

CREATE TABLE `table3` (
`siteid` int(11) NULL DEFAULT "10" COMMENT "",
`citycode` smallint(6) NULL COMMENT "",
`username` varchar(32) NULL DEFAULT "" COMMENT "",
INDEX idx_ngrambf (`username`) USING NGRAM_BF PROPERTIES("gram_size"="3", "bf_size"="256") COMMENT 'username ngram_bf index'
) ENGINE=OLAP
AGGREGATE KEY(`siteid`, `citycode`, `username`) COMMENT "OLAP"
DISTRIBUTED BY HASH(`siteid`) BUCKETS 10
PROPERTIES (
"replication_num" = "1"
);

-- PROPERTIES("gram_size"="3", "bf_size"="256")，分别表示gram的个数和bloom filter的字节数。
-- gram的个数跟实际查询场景相关，通常设置为大部分查询字符串的长度，bloom filter字节数，可以通过测试得出，通常越大过滤效果越好，可以从256开始进行验证测试看看效果。当然字节数越大也会带来索引存储、内存cost上升。
-- 如果数据基数比较高，字节数可以不用设置过大，如果基数不是很高，可以通过增加字节数来提升过滤效果。

2.6.2 NGram BloomFilter使用注意事项​

1. NGram BloomFilter只支持字符串列
2. NGram BloomFilter索引和BloomFilter索引为互斥关系，即同一个列只能设置两者中的一个
3. NGram大小和BloomFilter的字节数，可以根据实际情况调优，如果NGram比较小，可以适当增加BloomFilter大小
4. 如果要查看某个查询是否命中了NGram Bloom Filter索引，可以通过查询的Profile信息查看

2.7 倒排索引

从2.0.0版本开始，Doris支持倒排索引，可以用来进行文本类型的全文检索、普通数值日期类型的等值范围查询，快速从海量数据中过滤出满足条件的行。本文档主要介绍如何倒排索引的创建、删除、查询等使用方式。

inverted index：倒排索引，是信息检索领域常用的索引技术，将文本分割成一个个词，构建 词 -> 文档编号 的索引，可以快速查找一个词在哪些文档出现。

在Doris的倒排索引实现中，table的一行对应一个文档、一列对应文档中的一个字段，因此利用倒排索引可以根据关键词快速定位包含它的行，达到WHERE子句加速的目的。

与Doris中其他索引不同的是，在存储层倒排索引使用独立的文件，跟segment文件有逻辑对应关系、但存储的文件相互独立。这样的好处是可以做到创建、删除索引不用重写tablet和segment文件，大幅降低处理开销。

2.7.1 功能

• 增加了字符串类型的全文检索
  • 支持字符串全文检索，包括同时匹配多个关键字MATCH_ALL、匹配任意一个关键字MATCH_ANY、匹配短语词组MATCH_PHRASE
  • 支持字符串数组类型的全文检索
  • 支持英文、中文以及Unicode多语言分词
• 加速普通等值、范围查询，覆盖bitmap索引的功能，未来会代替bitmap索引
  • 支持字符串、数值、日期时间类型的 =, !=, >, >=, <, <= 快速过滤
  • 支持字符串、数字、日期时间数组类型的 =, !=, >, >=, <, <=
• 支持完善的逻辑组合
  • 新增索引对OR NOT逻辑的下推
  • 支持多个条件的任意AND OR NOT组合
• 灵活、快速的索引管理
  • 支持在创建表上定义倒排索引
  • 支持在已有的表上增加倒排索引，而且支持增量构建倒排索引，无需重写表中的已有数据
  • 支持删除已有表上的倒排索引，无需重写表中的已有数据

2.7.2 使用

CREATE TABLE table_name
(
  columns_difinition,
  INDEX idx_name1(column_name1) USING INVERTED [PROPERTIES("parser" = "english|unicode|chinese")] [COMMENT 'your comment']
  INDEX idx_name2(column_name2) USING INVERTED [PROPERTIES("parser" = "english|unicode|chinese")] [COMMENT 'your comment']
  INDEX idx_name3(column_name3) USING INVERTED [PROPERTIES("parser" = "chinese", "parser_mode" = "fine_grained|coarse_grained")] [COMMENT 'your comment']
  INDEX idx_name4(column_name4) USING INVERTED [PROPERTIES("parser" = "english|unicode|chinese", "support_phrase" = "true|false")] [COMMENT 'your comment']
)
  table_properties;

• 利用倒排索引加速查询

-- 1. 全文检索关键词匹配，通过MATCH_ANY MATCH_ALL完成
SELECT * FROM table_name WHERE column_name MATCH_ANY | MATCH_ALL 'keyword1 ...';

-- 1.1 logmsg中包含keyword1的行
SELECT * FROM table_name WHERE logmsg MATCH_ANY 'keyword1';

-- 1.2 logmsg中包含keyword1或者keyword2的行，后面还可以添加多个keyword
SELECT * FROM table_name WHERE logmsg MATCH_ANY 'keyword1 keyword2';

-- 1.3 logmsg中同时包含keyword1和keyword2的行，后面还可以添加多个keyword
SELECT * FROM table_name WHERE logmsg MATCH_ALL 'keyword1 keyword2';

-- 1.4 logmsg中同时包含keyword1和keyword2的行，并且按照keyword1在前，keyword2在后的顺序
SELECT * FROM table_name WHERE logmsg MATCH_PHRASE 'keyword1 keyword2';


-- 2. 普通等值、范围、IN、NOT IN，正常的SQL语句即可，例如
SELECT * FROM table_name WHERE id = 123;
SELECT * FROM table_name WHERE ts > '2023-01-01 00:00:00';
SELECT * FROM table_name WHERE op_type IN ('add', 'delete');

2.8参考文档

doris官方文档

https://doris.apache.org/zh-CN/

百度开发者中心

https://developer.baidu.com/article/detail.html?id=293810

csdn