五分钟了解Palo Doris的索引原理及应用场景!

2022-06-09 00:00:00 索引 查询 创建 数据 前缀

索引

索引用于帮助快速过滤或查找数据。

目前 Doris 主要支持两类索引:内建的智能索引,包括前缀索引和ZoneMap索引。用户创建的二级索引,包括Bloom Filter索引和Bitmap倒排索引。

其中ZoneMap索引是在列存格式上,对每一列自动维护的索引信息,包括Min/Max,Null值个数等等。这种索引对用户透明,不在此介绍。以下主要介绍其他三类索引。

前缀索引

原理

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

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

前缀索引是以Block为粒度创建的稀疏索引,一个Block包含1024行数据,每个Block,以该Block的行数据的前缀列的值作为索引。

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

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

ColumnNameType
user_idBIGINT
ageINT
messageVARCHAR(100)
max_dwell_timeDATETIME
min_dwell_timeDATETIME
  1. 以下表结构的前缀索引为 user_name(20 Bytes)。即使没有达到 36 个字节,因为遇到 VARCHAR,所以直接截断,不再往后继续。

ColumnNameType
user_nameVARCHAR(20)
ageINT
messageVARCHAR(100)
max_dwell_timeDATETIME
min_dwell_timeDATETIME

使用场景

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

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

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

SELECT * FROM table WHERE age=20;

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

Bloom Filter 索引

原理

用户可以在建表时指定在某些列上创建Bloom Filter索引(以下简称BF索引)。也可以在运行时通过 ALTER TABLE
 命令新增BF索引。

Bloom Filter本质上是一种位图结构,用于快速的判断一个给定的值是否在一个集合中。这种判断会产生小概率的误判。即如果返回 False
,则一定不在这个集合内。而如果范围 True
,则有可能在这个集合内。

BF索引也是以Block为粒度创建的。每个Block中,指定列的值作为一个集合生成一个BF索引条目,用于在查询是快速过滤不满足条件的数据。

适用场景

由于Bloom Filter数据结构的特性,BF索引比较适合创建在高基数的列上,比如UserID。因为如果创建在低基数的列上,比如”性别“列,则每个Block几乎都会包含所有取值,导致BF索引失去意义。

Bitmap 索引

原理

用户可以在建表时指定在某些列上创建Bitmap索引。也可以在运行时通过 [ALTER TABLE](TODO) 命令新增Bitmap索引。

Bitmap索引是一种特殊的数据库索引技术,其索引使用bit数组(或称bitmap、bit set、bit string、bit vector)进行存储与计算操作。位置编码中的每一位表示键值对应的数据行的有无。一个位图可能指向的是几十甚至成百上千行数据的位置。

这种方式存储数据,相对于 B*Tree
 索引,占用的空间非常小,创建和使用非常快。当根据键值查询时,可以根据Bitmap索引快速定位到具体的行号。而当根据键值做 and/or 或 in(x,y,..) 查询时,直接用索引的位图进行或运算,快速得出结果行数据。

Doris 中的Bitmap索引有如下限制

  • Bitmap 索引仅在单列上创建。

  • bitmap 索引支持的数据类型如下:

    • TINYINT

    • SMALLINT

    • INT

    • UNSIGNEDINT

    • BIGINT

    • CHAR

    • VARCHAR

    • DATE

    • DATETIME

    • LARGEINT

    • DECIMAL

    • BOOL

适用场景

  1. 适用于低基数的列上,建议在100到100000之间,如:职业、地市等。基数太高则没有明显优势;基数太低,则空间效率和性能会大大降低。

  2. 对于特定类型的查询例如count、or、and等逻辑操作因为只需要进行位运算。如:通过类似 select count(*) from table where city = 'beijing' and job = 'teacher'
     这种多个条件组合查询场景,如果在每个查询条件列上都建立了bitmap索引,则可以进行高效的位运算,定位到需要的数据,数据扫描量。当筛选出的结果集越小,bitmap索引的优势越明显。

来源 https://www.modb.pro/db/164805

相关文章