Doris-07-索引的详细介绍(前缀索引、Ordinal索引、Zone Map索引、Bitmap索引、Bloom Filter索引、NGram BloomFilter索引、倒排索引)_doris 索引

索引

介绍

Apache Doris 存储引擎采用类似 LSM 树的结构提供快速的数据写入支持。进行数据导入时，数据会先写入 Tablet 对应的 MemTable 中，当 MemTable 写满之后，会将 MemTable 里的数据刷写（Flush）到磁盘，生成一个个不超过 256MB 的不可变的 Segment 文件。

MemTable 采用 SkipList 的数据结构，将数据暂时保存在内存中，SkipList 会按照 Key 对数据行进行排序，因此，刷写到磁盘上的 Segment 文件也是按 Key 排序的。Apache Doris 底层采用列存的方式来存储数据，每一列数据会被分为多个 Data Page。

为了提高数据读取效率，Apache Doris 底层存储引擎提供了丰富的索引类型，目前 Doris 主要支持两类索引：

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

数据从 MemTable 刷写到磁盘的过程分为两个阶段：

• 第一阶段是将 MemTable 中的行存结构在内存中转换为列存结构，并为每一列生成对应的索引结构；
• 第二阶段是将转换后的列存结构写入磁盘，生成 Segment 文件。

前缀索引

索引生成

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

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

在 Aggregate、Uniq 和 Duplicate 三种数据模型中。底层的数据存储，是按照各自建表语句中，AGGREGATE KEY、UNIQ KEY 和 DUPLICATE KEY 中指定的列进行排序存储的。而前缀索引，即在排序的基础上，实现的一种根据给定前缀列，快速查询数据的索引方式。

我们将一行数据的前 36 个字节 作为这行数据的前缀索引。当遇到 VARCHAR 类型时，前缀索引会直接截断。

前缀索引是一种稀疏索引。数据刷写过程中，每写入一定的数据行（默认为 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文件，从footer中获取Short Key Page的offset以及大小，然后从Segment文件中读取Short Key Page中的索引数据，并解析出每一条前缀索引项。

如果查询过滤条件包含前缀字段时，就可以使用前缀索引进行快速地行过滤。查询过滤条件会被划分成多个Key Range。对一个Key Range进行行过滤的方法如下：

• 在整个Segment的行范围内寻找Key Range上界对应的行号upper rowid（寻找Segment中第一个大于Key Range上界的行）。

  • 对Key Range上界的前缀字段key进行编码。
  • 寻找key可能存在的范围下界start。根据编码寻找前缀索引中第一个等于（存在前缀索引项与key的编码相同）或大于（不存在前缀索引项的与key的编码相同）key编码的前缀索引项。如果找到满足条件的索引项，并且该索引项不是第一条前缀索引项，则将该索引项的前一条前缀索引项对应的行号记录为start（前缀索引是稀疏索引，第一个等于或大于Key Range上界key的数据行有可能在前一条前缀索引项对应的数据行之后）；如果找到满足条件的索引项，并且该索引项是第一条前缀索引项，则记录该索引项对应的行号为start。如果没有找到一条前缀索引项等于或大于key的编码，则记录最后一条前缀索引项对应的行号为start（第一个等于或大于key的行有可能在最后一条前缀索引项之后）。
  • 寻找key可能存在的范围上界end。根据编码寻找前缀索引中第一个大于key的二进制编码的索引项。如果找到满足条件的索引项，则记录该索引项对应的行号为end；如果没有找到一条前缀索引项大于key的编码，则记录Segment最后一行的行号为end。
  • 使用二分查找算法在start与end之间的行范围内寻找第一个大于key的编码的行，行号记为upper rowid。

  注：前缀索引是稀疏索引，不能精确定位到key所在的行，只能粗粒度地定位出key可能存在的范围，然后使用二分查找算法精确地定位key的位置，如图所示。

  

• 在0 ～ upper rowid范围内寻找Key Range下界对应的行号lower rowid（寻找Segment中第一个等于或大于Key Range下界的行）。与寻找Key Range上界对应的row id的方法相同，不再赘述。

• 获取Key Range的行范围。upper_rowid与lower_rowid之间的所有数据行都是当前Key Range需要扫描的行范围。

Ordinal 索引

索引生成

Apache 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：包含当前Page的类型、Ordinal索引项数据的大小、Ordinal索引项数目等信息；
• Short Key Page的Checksum信息。

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

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

查询过滤

数据查询时，会加载每一个列的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的大小。

Zone Map 索引

Apache Doris 会为Segment文件中的一列数据添加Zone Map索引，同时会为列中的每一个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。

索引生成

数据刷写时，会给每一个Data Page创建一条Zone Map索引项。向Data Page中每添加一条数据，都会更新Data Page的Zone Map索引项。

• 如果添加的数据是null，则将Zone Map索引项的has null标志设置为true，否则，将Zone Map索引项的has not null标志设置为true。
• 如果添加的数据小于Zone Map索引项的min value，则使用当前数据更新min value；如果添加的数据大于Zone Map索引项的max value，则使用当前数据更新max value。

当一个Data Page写满之后，会更新一次列的Zone Map索引项，如果Data Page索引项的min value小于列索引项的min value，则使用Data Page索引项的min value更新列索引项的min value；如果Data Page索引项的max value大于列索引项的max value，则使用Data Page索引项的max value更新列索引项的max value；如果Data Page索引项的has null标志为true，则更新列索引项的has null标志为true；如果Data Page索引项的has not null标志为true，则更新列索引项的has not null标志为true。更新Zone Map索引的过程如图4所示。

列中每一个Data Page的Zone Map索引项会被序列化之后保存在Zone Map Index Page中。

Zone Map Index Page中包含以下信息：Zone Map索引项数据、Zone Map Index Page的footer以及Zone Map Index Page的Checksum信息。

Zone Map Index Page的footer中包含当前Page的类型、当前Page中Zone Map索引项数据的大小、当前Page中Zone Map索引项数目以及当前Page中第一条索引项在整个列的Zone Map索引项中的序号等信息。

一个Zone Map Index Page写满之后，会创建新的Zone Map Index Page用于记录该列后续的Zone Map索引项。

如果某一列有多个Zone Map Index Page，则该列的Zone Map索引会采用两级索引机制。第二级索引为多个的Zone Map Index Page，其中保存Data Page的Zone Map索引数据，每一个Zone Map Index Page会生成一条Ordinal索引项，所有Zone Map Index Page的Ordinal索引项会被保存在一个Ordinal Index Page（注意，此处的Ordinal 索引与第3部分的Ordinal 索引不同，此处的Ordinal 索引指向Zone Map Index Page，而第3部分的Ordinal 索引指向Data Page）中作为一级索引。

每一个的Ordinal索引项由key和value两部分组成，key记录了当前Zone Map Index Page中第一条索引项在整个列的Zone Map索引项中的序号，value记录了当前Zone Map Index Page在Segment文件中的offset和大小。

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

一级索引Ordinal Index Page在Segment文件中的offset和大小会被记录在Segment文件的footer中。如果某一列只有一个Zone Map Index Page，则不需要两级索引，这个唯一的Zone Map Index Page在Block中的offset和大小会被记录在Segment文件的footer中。Zone Map索引的存储结构如图所示。

查询过滤

数据查询时，会加载每一个列的Zone Map索引数据，并解析出每一个Data Page的Zone Map索引数据。

通过Segment footer中记录的Zone Map索引的Meta信息判断当前列的Zone Map是否含有两级索引。

如果含有两级索引，则Segment footer中记录了一级索引Ordinal Index Page在Segment文件中的offset和大小，加载一级索引Ordinal Index Page，并解析出每一个的Ordinal索引项的key和value，key记录了每一个Zone Map Index Page中第一条索引项在整个列所有的Zone Map索引项中的序号，value记录了每一个Zone Map Index Page在Segment文件中的offset和大小。

否则，当前列的Zone Map索引只含有一个Zone Map Index Page，Segment footer中记录了该Zone Map Index Page在Segment文件中的offset和大小。可以通过Zone Map Index Page解析出每一个Data Page的Zone Map索引数据，其中包括最大值(max value)、最小值(min value)、是否有null值(has null)以及是否有非null值(has not null)的信息。

使用Zone Map对Data Page进行过滤的方法如下：

• 过滤条件的运算符不是IS。如果Zone Map索引的has null为true（Data Page中含有NULL值），则Data Page不能被过滤掉。
• 过滤条件为 field = value。如果 value在Zone Map索引的最大值与最小值之间，则Data Page不能被过滤掉。
• 过滤条件为 field != value。如果value小于Zone Map索引的最小值或value大于Zone Map索引的最大值，则Data Page不能被过滤掉。
• 过滤条件为 field < value。如果value大于Zone Map索引的最小值，则Data Page不能被过滤掉。
• 过滤条件为 field <= value。如果value大于或等于Zone Map索引的最小值，则Data Page不能被过滤掉。
• 过滤条件为 field > value。如果value小于Zone Map索引的最大值，则Data Page不能被过滤掉。
• 过滤条件为 field >= value。如果value小于或等于Zone Map索引的最大值，则Data Page不能被过滤掉。
• 过滤条件为 field IN {value1, value2, …}。如果value1、value2、…中至少存在一个值在Zone Map索引的最大值与最小值之间，则Data Page不能被过滤掉。
• 过滤条件为 field IS NULL。如果Zone Map索引的has null为true（Data Page中含有NULL值），则Data Page不能被过滤掉。
• 过滤条件为 field IS NOT NULL。如果Zone Map索引的has not null为true（Data Page中含有非NULL值），则Data Page不能被过滤掉。

对于未被Zone Map索引过滤的Data Page，可以使用Ordinal索引快速定位这些Data Page的起始行的行号，并获取这些Data Page的行范围。通过Data Page对应的Ordinal索引项快速获取当前Data Page的起始行的行号start，通过下一条Ordinal索引项快速获取后一个Data Page的起始行的行号end，左闭右开区间[start, end)即为当前Data Page的row范围。

Bitmap 索引

为了加速数据查询，Apache Doris支持用户为某些字段添加Bitmap索引。Bitmap索引由两部分组成：

• 有序字典：有序保存一列中所有的不同取值。
• 字典值的Roaring位图：保存有序字典中每一个取值的Roaring位图，表示字典值在列中的行号。

例如：如图所示，一列数据为[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]

创建语句：

CREATE INDEX [IF NOT EXISTS] index_name ON table1 (siteid) USING BITMAP COMMENT 'balabala';
1

索引生成

数据刷写时，会给用户指定的列创建Bitmap索引。向列中每添加一个值，都会更新当前列的Bitmap索引。从Bitmap索引的有序字典中查找添加的值是否已经存在，如果本次添加的值在Bitmap索引的有序字典中已经存在，则直接更新该字典值对应的Roaring位图，如果本次添加的值在Bitmap索引的有序字典中不存在，则将该值添加到有序字典，并为该字典值创建Roaring位图。当然，NULL值也会有单独的Roaring位图。

Bitmap索引的字典数据和Roaring位图数据分开存储（一一对应）。

列中Bitmap索引的字典值会按顺序保存在Dict Page中。Dict Page中包含以下信息：Bitmap索引的字典数据、Dict Page的footer以及Dict Page的Checksum信息。Dict Page的footer中包含当前Page的类型、当前Page中Bitmap索引的字典数据的大小、当前Page中Bitmap索引的字典值数目以及当前Page中第一个字典值在整个列的Bitmap索引字典值中的序号等信息。Bitmap索引的字典数据会按照LZ4F格式进行压缩。

一个Dict Page写满之后，会创建新的Dict Page用于记录该列后续的字典数据。

如果某一列有多个Dict Page，则会采用两级索引机制：第二级索引为多个的Dict Page，其中保存Bitmap索引的字典数据，每一个Dict Page生成一条Value索引项，每一个的Value索引项记录了当前Dict Page中第一个字典值的编码以及当前Dict Page在Segment文件中的offset和大小，所有Dict Page的Value索引项会被保存在一个Value Index Page中作为一级索引。

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

一级索引Value Index Page在Segment文件中的offset和大小会被记录在Segment文件的footer中。如果某一列只有一个Dict Page，则不需要两级索引，这个唯一的Dict Page在Segment文件中的offset和大小会被记录在Segment文件的footer中。Bitmap索引的字典数据的存储结构如图所示。

列中Bitmap索引的Roaring位图数据会保存在Bitmap Page中。

Bitmap Page中包含以下信息：Bitmap索引的Roaring位图数据、Bitmap Page的footer以及Bitmap Page的Checksum信息。

Bitmap Page的footer中包含当前Page的类型、当前Page中Bitmap索引的Roaring位图数据的大小、当前Page中Bitmap索引的Roaring位图数目以及当前Page中第一个Roaring位图在整个列的Bitmap索引的Roaring位图中的序号等信息。Bitmap索引的Roaring位图数据不进行压缩。

一个Bitmap Page写满之后，会创建新的Bitmap Page用于记录该列后续的Roaring位图数据。

如果某一列有多个Bitmap Page，则会采用两级索引机制。第二级索引为多个的Bitmap Page，其中保存Bitmap索引的位图数据，每一个Bitmap Page生成一条Ordinal索引项，所有Bitmap Page的Ordinal索引项会被保存在一个Ordinal Index Page 中作为一级索引。

每一个的Ordinal索引项由key和value两部分组成，key记录了当前Bitmap Page中第一个Roaring位图在整个列的BitMap索引Roaring位图中的序号，value记录了当前Bitmap Page在Segment文件中的offset和大小。

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

一级索引Ordinal Index Page在Segment文件中的offset和大小会被记录在Segment文件的footer中。如果某一列只有一个Bitmap Page，则不需要两级索引，这个唯一的Bitmap Page在Segment文件中的offset和大小会被记录在Segment文件的footer中。Bitmap索引的Roaring位图数据的存储结构如图所示。

查询过滤

数据查询时，会加载列的Bitmap索引数据，并解析出有序字典和Roaring位图数据。

• 首先，通过Segment footer中记录的Bitmap索引的字典Meta信息判断当前列的Bitmap索引的字典是否含有两级索引，如果含有两级索引，则Segment footer中记录了一级索引Value Index Page在Block中的offset和大小，首先加载一级索引Value Index Page，并解析出每一个的Value索引项，获得每一个Dict Page中第一个字典值和每一个Dict Page在Segment文件中的offset和大小；否则，当前列的Bitmap索引只含有一个Dict Page，Segment footer中记录了该Dict Page在Segment文件中的offset和大小。可以通过Dict Page解析出每一个字典值。
• 然后，通过Segment footer中记录的Bitmap索引的Roaring位图Meta信息判断当前列的Bitmap索引的Roaring位图是否含有两级索引，如果含有两级索引，则Segment footer中记录了一级索引Ordinal Index Page在Segment文件中的offset和大小，首先加载一级索引Ordinal Index Page，并解析出每一个的Ordinal索引项，获得每一个Bitmap Page中第一个Roaring位图在整个列的Bitmap索引Roaring位图中的序号以及每一个Bitmap Page在Segment文件中的offset和大小；否则，当前列的Bitmap索引只含有一个Bitmap Page，Segment footer中记录了该Bitmap Page在Segment文件中的offset和大小。可以通过Bitmap Page中解析出每一个字典值对应的Roaring位图。

真正使用Bitmap索引进行数据过滤时才会加载Dict Page和Bitmap Page。

使用某一个查询过滤条件进行行过滤的方法如下：

• 过滤条件为 field = value。从 Dict Page 中寻找第一个等于或大于 value 的字典值，并且获取该字典值在有序字典中的序号ordinal。如果寻找到的字典值恰好等于value，则从 Bitmap Page 中读取第ordinal个位图，则该位图表示通过该查询条件过滤之后留下的行范围。
• 过滤条件为 field != value。从Dict Page中寻找第一个等于或大于value的字典值，并且获取该字典值在有序字典中的序号ordinal。如果寻找到的字典值恰好等于value，则从Bitmap Page中读取第ordinal个位图，则该位图表示需要被过滤掉的行范围。
• 过滤条件为 field < value。从Dict Page中寻找第一个等于或大于value的字典值，并且获取该字典值在有序字典中的序号ordinal。从Bitmap Page中读取前面ordinal个位图，这些位图的并集表示通过该查询条件过滤之后留下的行范围。
• 过滤条件为 field <= value。从Dict Page中寻找第一个等于或大于value的字典值，并且获取该字典值在有序字典中的序号ordinal。如果寻找到的字典值恰好等于value，则从Bitmap Page中读取前面ordinal + 1个位图；如果寻找到的字典值大于value，则从Bitmap Page中读取前面ordinal个位图，这些位图的并集表示通过该查询条件过滤之后留下的行范围。
• 过滤条件为 field > value。从Dict Page中寻找第一个等于或大于value的字典值，并且获取该字典值在有序字典中的序号ordinal。如果寻找到的字典值恰好等于value，则从Bitmap Page中读取第ordinal个位图之后的所有位图；如果寻找到的字典值大于value，则从Bitmap Page中读取第ordinal以及之后的所有位图，这些位图的并集表示通过该查询条件过滤之后留下的行范围。
• 过滤条件为 field >= value。从Dict Page中寻找第一个等于或大于value的字典值，并且获取该字典值在有序字典中的序号ordinal。从Bitmap Page中读取ordinal之后的所有位图，这些位图的并集表示通过该查询条件过滤之后留下的行范围。

适用场景

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

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

目前只支持对TINYINT、SMALLINT、INT、 UNSIGNEDINT、BIGINT、LARGEINT、CHAR、 VARCHAR、DATE、DATETIME、BOOL和DECIMAL类型的字段创建Bitmap索引，其他类型的字段均不支持Bitmap索引。Bitmap索引比较适合在基数较低的列上进行等值查询或范围查询的场景。

Bloom Filter 索引

Apache Doris支持用户对取值区分度比较大的字段添加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进行快速过滤，减少不必要的数据读取。

创建语句：

CREATE TABLE IF NOT EXISTS sale_detail_bloom  (
    sale_date date NOT NULL COMMENT "销售时间",
    customer_id int NOT NULL COMMENT "客户编号",
    saler_id int NOT NULL COMMENT "销售员",
    sku_id int NOT NULL COMMENT "商品编号",
    category_id int NOT NULL COMMENT "商品分类",
    sale_count int NOT NULL COMMENT "销售数量",
    sale_price DECIMAL(12,2) NOT NULL COMMENT "单价",
    sale_amt DECIMAL(20,2)  COMMENT "销售总金额"
)
Duplicate  KEY(sale_date, customer_id,saler_id,sku_id,category_id)
PARTITION BY RANGE(sale_date)
(
PARTITION P_202111 VALUES [('2021-11-01'), ('2021-12-01'))
)
DISTRIBUTED BY HASH(saler_id) BUCKETS 10
PROPERTIES (
"replication_num" = "3",
"bloom_filter_columns"="saler_id,category_id",
"dynamic_partition.enable" = "true",
"dynamic_partition.time_unit" = "MONTH",
"dynamic_partition.time_zone" = "Asia/Shanghai",
"dynamic_partition.start" = "-2147483648",
"dynamic_partition.end" = "2",
"dynamic_partition.prefix" = "P_",
"dynamic_partition.replication_num" = "3",
"dynamic_partition.buckets" = "3"
);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

索引生成

数据刷写时，会给每一个Data Page创建一条Bloom Filter索引项。Apache Doris采用了基于Block的Bloom Filter算法。每一个Data Page对应的Bloom Filter索引数据会被划分为多个Block，每个Block的数据长度为BYTES_PER_BLOCK（默认为32字节，共256bit），Block中的每一个Bit位会被初始化为0。向Data Page中写入数据时，每一个不同的取值value都会将一个Block中的BITS_SET_PER_BLOCK（默认值为8）个Bit置位为1。Bloom Filter索引的结构如图所示。

单个Data Page的Bloom Filter索引数据长度BLOOM_FILTER_BIT通过如下公式计算：
$$BLOOM\_FILTER\_BIT=-N\ast ln(FPP)(ln(2{)}^2)$$
其中，N表示当前Data Page中的不同取值的个数；FPP（False Positive Probablity） 表示期望的误判率，默认取值为0.05。（注：计算出的Bloom Filter数据长度（单位为bit）一定是2的整数次幂。）

Bloom Filter中，每一个Block的长度为BYTES_PER_BLOCK（32字节），因此，Bloom Filter中的Block数量通过如下公式计算：
$$BLOCK\_NUM=(BLOOM\_FILTER\_BIT÷8)÷BYTES\_PER\_BLOCK;$$
为Data Page生成Bloom Filter索引项的方法如下：

• 针对Data Page中的每一个不同的取值value，计算出一个64位的HASH_CODE。Apache Doris中，Bloom Filter的Hash策略为HASH_MURMUR3。

• 取HASH_CODE的高32位计算出当前value在Bloom Filter中对应的Block，方法如下：
  $$BLOCK\_INDEX=(HASH\_CODE>>32)\&(BLOCK\_NUM-1)$$
  其中，BLOCK_INDEX表示Block的序号，BLOCK_NUM为2的整数次幂，则BLOCK_INDEX一定小于BLOCK_NUM。

• 取HASH_CODE的低32位计算出当前value会将Block中的哪些Bit置位为1，方法如下：

  uint32_t key = (uint32_t)HASH_CODE
  uint32_t SALT[8] = {0x47b6137b, 0x44974d91, 0x8824ad5b, 0xa2b7289d,  0x705495c7, 0x2df1424b, 0x9efc4947, 0x5c6bfb31};
  uint32_t masks[BITS_SET_PER_BLOCK];
  for (int i = 0; i < BITS_SET_PER_BLOCK; ++i) {
          masks[i] = key * SALT[i];
          masks[i] = masks[i] >> 27;
          masks[i] = 0x1 << masks[i];
  }
  1
  2
  3
  4
  5
  6
  7
  8

  其中，masks[i]包含32个Bit，其中只有1个Bit被置位为1，其他31个Bit均为0。

  将masks[i]与Block中第i个32Bit按位取或，更新Data Page的Bloom Filter索引数据。（一个Block中包含256个Bit，即 BITS_SET_PER_BLOCK 个32 Bit）

  uint32_t* BLOCK_OFFSET =  BLOOM_FILTER_OFFSET + BYTES_PER_BLOCK * BLOCK_INDEX
  for (int i = 0; i < BITS_SET_PER_BLOCK; ++i) {
  	*(BLOCK_OFFSET + i) |= masks[i];
  }
  1
  2
  3
  4

Bloom Filter索引项中单独设置了Data Page中是否包含了NULL值的标志。

列中每一个Data Page的Bloom Filter索引项会被保存在Bloom Filter Index Page中。Bloom Filter Index Page中包含以下信息：Bloom Filter索引项数据、Bloom Filter Index Page的footer以及Bloom Filter Index Page的Checksum信息。Bloom Filter Index Page的footer中包含当前Page的类型、当前Page中Bloom Filter索引项数据的大小、当前Page中Bloom Filter索引项数目以及当前Page中第一条索引项在整个列的Bloom Filter索引项中的序号等信息。

一个Bloom Filter Index Page写满之后，会创建新的Bloom Filter Index Page用于记录该列后续的Bloom Filter索引项。如果某一列有多个Bloom Filter Index Page，则该列的Bloom Filter索引会采用两级索引机制。第二级索引为多个的Bloom Filter Index Page，其中保存Data Page的Bloom Filter索引数据，每一个Bloom Filter Index Page生成一条Ordinal索引项，所有Bloom Filter Index Page的Ordinal索引项会被保存在一个Ordinal Index Page中作为一级索引。

每一个的Ordinal索引项由key和value两部分组成，key记录了当前Bloom Filter Index Page中第一条索引项在整个列的Bloom Filter索引项中的序号，value记录了当前Bloom Filter Index Page在Segment文件中的offset和大小。Ordinal Index Page中包含以下信息：所有Bloom Filter Index Page的Ordinal 索引数据、Ordinal Index Page的footer以及Ordinal Index Page的Checksum信息。Ordinal Index Page的footer中包含当前Page的类型、当前Page中索引数据的大小、当前Page中索引项数目等。一级索引Ordinal Index Page在Segment文件中的offset和大小会被记录在Segment文件的footer中。如果某一列只有一个Bloom Filter Index Page，则不需要两级索引，这个唯一的Bloom Filter Index Page在Segment文件中的offset和大小会被记录在Segment文件的footer中。Bloom Filter索引的存储结构如图所示。

查询过滤

数据查询时，会加载列的Bloom Filter索引数据，并解析出每一个Data Page的Bloom Filter索引项。首先，通过Segment footer中记录的Bloom Filter索引的Meta信息判断当前列的Bloom Filter是否含有两级索引，如果含有两级索引，则Segment footer中记录了一级索引Ordinal Index Page在Segment文件中的offset和大小，先加载一级索引Ordinal Index Page，并解析出每一个的Ordinal索引项的key和value，key记录了每一个Bloom Filter Index Page中第一条索引项在整个列所有的Bloom Filter索引项中的序号，value记录了每一个Bloom Filter Index Page在Segment文件中的offset和大小；否则，当前列的Bloom Filter索引只含有一个Bloom Filter Index Page，Segment footer中记录了该Bloom Filter Index Page在Segment文件中的offset和大小。可以通过Bloom Filter Index Page解析出每一个Data Page的Bloom Filter索引数据。

判断某个值value是否命中Bloom Filter的方法如下：

• 首先，基于HASH_MURMUR3方法对查询过滤条件的值value计算出64位的HASH_CODE；
• 然后，采用与生成Bloom Filter索引数据相同的方法计算出该value值在Bloom Filter中对应的Block，以及在Block中对应的BITS_SET_PER_BLOCK个Bit位。
• 判断Bloom Filter索引数据中对应Block的这BITS_SET_PER_BLOCK个Bit的值是否均为1。如果对应Block中的这BITS_SET_PER_BLOCK个Bit值均为1，则表示Bloom Filter命中，该value值在Bloom Filter对应的Data Page中可能存在；否则，表示Bloom Filter未命中，该value值在Bloom Filter对应的Data Page中一定不存在。

数据查询时，查询过滤条件（“=”、"IS"或"IN"语句）在设置有Bloom Filter索引的列依次对每一个Data Page进行过滤。进行NULL值查询时，可以直接使用Bloom Filter索引项中的NULL值标志进行Data Page过滤。进行非NULL值查询时，使用查询过滤条件对Data Page进行过滤的方法如下：

• 过滤条件为 field = value 。如果value未命中某一个Data Page对应的Bloom Filter，则该Data Page可以被过滤掉。
• 过滤条件为 field IN {value1, value2, …} 。如果 value1、value2、…中所有值都未命中某一个Data Page对应的Bloom Filter，则该Data Page可以被过滤掉。

过滤条件为 field IS NULL 。如果NULL值未命中某一个Data Page对应的Bloom Filter，则该Data Page可以被过滤掉。

适用场景

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

 ALTER TABLE table_name SET ("bloom_filter_columns"="c1, c2, c3"); 
1

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

NGram BloomFilter索引

为了提升like的查询性能，增加了NGram BloomFilter索引，其实现主要参照了ClickHouse的ngrambf。

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

表创建时指定：

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上升。
-- 如果数据基数比较高，字节数可以不用设置过大，如果基数不是很高，可以通过增加字节数来提升过滤效果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

倒排索引

介绍

从2.0.0版本开始，Doris支持倒排索引，可以用来进行文本类型的全文检索、普通数值日期类型的等值范围查询，快速从海量数据中过滤出满足条件的行。

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

Doris使用CLucene作为底层的倒排索引库。CLucene是一个用C++实现的高性能、稳定的Lucene倒排索引库。Doris进一步优化了CLucene，使得它更简单、更快、更适合数据库场景。

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

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

Doris倒排索引的功能简要介绍如下：

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

使用

建表时定义倒排索引：

CREATE TABLE table_name
(
  columns_difinition,
  INDEX idx_name1(column_name1) USING INVERTED [PROPERTIES("parser" = "english|chinese")] [COMMENT 'your comment']
  INDEX idx_name2(column_name2) USING INVERTED [PROPERTIES("parser" = "english|chinese")] [COMMENT 'your comment']
)
table_properties;
1
2
3
4
5
6
7

• USING INVERTED 是必须的，用于指定索引类型是倒排索引
• PROPERTIES 是可选的，用于指定倒排索引的额外属性，目前有一个属性parser指定分词器
  • 默认不指定代表不分词
  • english是英文分词，适合被索引列是英文的情况，用空格和标点符号分词，性能高
  • chinese是中文分词，适合被索引列有中文或者中英文混合的情况，采用jieba分词库，性能比english分词低
• COMMENT 是可选的，用于指定注释

CREATE TABLE table_name
(
    columns_difinition,
    INDEX idx_name1(column_name1) USING INVERTED [PROPERTIES("parser" = "english|chinese")] [COMMENT 'your comment']
    INDEX idx_name2(column_name2) USING INVERTED [PROPERTIES("parser" = "english|chinese")] [COMMENT 'your comment']
)
table_properties;
1
2
3
4
5
6
7

已有表增加倒排索引：

-- 语法1
CREATE INDEX idx_name ON table_name(column_name) USING INVERTED [PROPERTIES("parser" = "english|chinese")] [COMMENT 'your comment'];
-- 语法2
ALTER TABLE table_name ADD INDEX idx_name(column_name) USING INVERTED [PROPERTIES("parser" = "english|chinese")] [COMMENT 'your comment'];
1
2
3
4

删除倒排索引：

-- 语法1
DROP INDEX idx_name ON table_name;
-- 语法2
ALTER TABLE table_name DROP INDEX idx_name;
1
2
3
4

利用倒排索引加速查询：

-- 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 'keyword2 keyword2';

-- 1.3 logmsg中同时包含keyword1和keyword2的行，后面还可以添加多个keyword
SELECT * FROM table_name WHERE logmsg MATCH_ALL 'keyword2 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');
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16