Bitmap 索引
本文介绍了如何创建和管理 Bitmap(位图)索引,以及 Bitmap 索引的使用案例。
功能简介
Bitmap 索引是一种使用 bitmap 的特殊数据库索引。bitmap 即为一个 bit 数组,一个 bit 的取值有两种:0 或 1。每一个 bit 对应数据表中的一行,并根 据该行的取值情况来决定 bit 的取值是 0 还是 1。
如果查询的过滤条件命中前缀索引,可以显著提高查询效率,快速返回结果。但是一个表只能有一个前缀索引,如果查询的过滤条件没有包含前缀索引的前缀,则为了提高这类查询的效率可以为该列创建 Bitmap 索引。
如何合理设计 Bitmap 索引,以便加速查询
选择 Bitmap 索引的首要考虑因素是列的基数和 Bitmap 索引对查询的过滤效果。与普遍观念相反,Bitmap 索引比较适用于较高基数列的查询和多个低基数列的组合查询,此时 Bitmap 索引对查询的过滤效果比较好,至少可以过滤掉 999/1000 的数据,能够过滤较多的 Page 数据。
如果是单个低基数列的查询,那么 Bitmap 索引过滤效果不佳,待读取的数据行较多并且散落在较多 Page 中。
评估 Bitmap 索引对查询的过滤效果时,需要看加载数据的开销。并且 StarRocks 中底层数据以 Page(默认为 64K)为单位组织和加载的,加载数据的开销主要有几个部分:从磁盘加载 Page 的 IO 时间,Page 解压缩和解码 时间。
然而如果基数过于高,也会带来其他问题,比如占用较多的磁盘空间,并且因为需要导入时需要构建 Bitmap 索引,导入频繁时则导入性能会受影响。
并且还需要考虑查询时加载 Bitmap 索引的开销。因为查询时候只会按需加载 Bitmap 索引,即 查询条件涉及的列值数量/基数 x Bitmap 索引
。这一值越大,则查询时加载的 Bitmap 索引开销也越大。
因此为了确定 Bitmap 索引适合列的基数和查询,建议您参考本文的 [Bitmap 索引性能测试](#Bitmap 索引性能测试),根据实际业务数据和查询进行性能测试:在不同基数的列上使用 Bitmap 索引,分析和权衡 Bitmap 索引对于查询过滤效果(至少可以过滤掉 999/1000 的数据),以及带来的磁盘空间占用,导入性能的影响,和查询时加载 Bitmap 索引的开销等额外影响。
不过,您创建的 Bitmap 索引无法加速查询,例如无法过滤较多 Page 数据,或者查询时加载 Bitmap开销较大,由于 StarRocks 本身对于查询有 Bitmap 索引的自适应选择机制,如果 Bitmap 索引不合适,则查询时不会使用 Bitmap 索引,所以查询性能也不会受到明显影响。
自适应选择是否使用 Bitmap 索引
StarRocks 会针对列基数和查询自适应选择是否使用 Bitmap 索引。如果用 Bitmap 索引起不到过滤较多 Page 数据的效果,或者查询时加载 Bitmap 索引开销较大,则 StarRocks 默认不会使用该 Bitmap 索引,避免使用后导致查询性能变差。
StarRocks 判断是否使用 Bitmap 索引的逻辑:因为一般情况下查询条件涉及的列值数量/列的基数,这一值越小,说明 Bitmap 索引过滤效果好。所以 StarRocks 采用 bitmap_max_filter_ratio/1000
作为判断阈值,当过滤条件涉及比较值的数量 /列的基数 < bitmap_max_filter_ratio/1000
时才会用 Bitmap 索引。bitmap_max_filter_ratio
默认为 1
。
首先以单列查询为例,比如表 employees
中 gender
列的值有 male
和 gender
列为 female
。执行查询SELECT * FROM employees WHERE gender = 'male';
时,因为性别列的基数为 2,比较低(只有 male
和 female
2 个不同值),查询条件只涉及其中一个值,此时查询条件涉及的列值数量/列的基数等于 1/2,该值大于 1/1000,所以该查询不会使用 Bitmap 索引。
再以多列组合查询 SELECT * FROM employees WHERE gender = 'male' AND city IN ('北京', '上海');
为例,假设 City 列的基数为 10000,比较高,查询条件涉及其中 2 个值,此时查询条件涉及的列值数量/列的基数的计算方式是两列相乘,结果为 (1*2)/(2*10000)
,该值小于 1/1000,所以该查询会使用 Bitmap 索引。
bitmap_max_filter_ratio
的取值范围为 1~1000。如果取值为 1000
,则表示只要查询的列有 Bitmap 索引,就会强制使用 Bitmap 索引。
优势
- 能够快速定位查询的列值所在的数据行号,适用于点查或是小范围查询。
- 适用于交并集运算(OR 和 AND 运算),可以优化多维查询。
注意事项
支持优化的查询
Bitmap 索引适用于优化等值 =
查询、[NOT] IN
范围查询、>
,>=
,<
,<=
查询、 IS NULL
查询。不适用于优化 !=
,[NOT] LIKE
查询。
支持的列和列的数据类型
主键表和明细表中所有列都可以创建 Bitmap 索引;聚合表和更新表中,只有 Key 列支持创建 Bitmap 索引。 支持为如下类型的列创建 Bitmap 索引:
- 日期类型:DATE、DATETIME。
- 数值类型:TINYINT、SMALLINT、INT、BIGINT、LARGEINT、DECIMAL 和 BOOLEAN。
- 字符串类型:CHAR、STRING 和 VARCHAR。
- 其他类 型:HLL。
基本操作
创建索引
-
建表时创建 Bitmap 索引。
CREATE TABLE `lineorder_partial` (
`lo_orderkey` int(11) NOT NULL COMMENT "",
`lo_orderdate` int(11) NOT NULL COMMENT "",
`lo_orderpriority` varchar(16) NOT NULL COMMENT "",
`lo_quantity` int(11) NOT NULL COMMENT "",
`lo_revenue` int(11) NOT NULL COMMENT "",
INDEX lo_orderdate_index (lo_orderdate) USING BITMAP
) ENGINE=OLAP
DUPLICATE KEY(`lo_orderkey`)
DISTRIBUTED BY HASH(`lo_orderkey`) BUCKETS 1;本示例中,创建了基于
lo_orderdate
列创建了名称为lo_orderdate_index
的 Bitmap 索引。Bitmap 索引的命名要求参见系统限制。在同一张表中不能创建名称相同的 Bitmap 索引。并且,支持为多个列创建 Bitmap 索引,并且多个 Bitmap 索引定义之间用英文逗号(,)隔开。
备注建表的其他参数说明,参见 CREATE TABLE。
-
建表后使用 CREATE INDEX 创建 Bitmap 索引。详细参数说明和示例,参见 CREATE INDEX。
CREATE INDEX lo_quantity_index ON lineorder_partial (lo_quantity) USING BITMAP;
创建进度
创建 Bitmap 索引为异步过程,执行索引创建语句后可通过 SHOW ALTER TABLE 命令查看索引创建进度,当返回值中 State
字段显示为 FINISHED
时,即为创建成功。
SHOW ALTER TABLE COLUMN [FROM db_name];
当前每张表只允许同时进行一个 Schema Change 任务,在一个 Bitmap 索引未异步创建完成前,无法进行新 Bitmap 索引的创建。
查看索引
查看指定表的所有 Bitmap 索引。详细参数和返回结果说明,参见 SHOW INDEX。
SHOW { INDEX[ES] | KEY[S] } FROM [db_name.]table_name [FROM db_name];
创建 Bitmap 索引为异步过程,使用如上语句只能查看到已经创建完成的索引。
删除索引
删除指定表的 Bitmap 索引。详细参数说明和示例,参见 DROP INDEX。
DROP INDEX index_name ON [db_name.]table_name;
查看查询是否命中了 Bitmap 索引
查看该查询的 Profile 中的 BitmapIndexFilterRows
字段。关于如何查看 Profile,参见分析查询。
Bitmap 索引性能测试
测试目的
在如下 不同基数的列上使用 Bitmap 索引,分析 Bitmap 索引对查询过滤效果以及其他影响,比如磁盘占用等。
并且本小节还会对比强制使用 Bitmap 索引和 StarRocks 针对查询自适应选择是否 Bitmap 索引,来验证 StarRocks 根据查询自适应选择是否使用 Bitmap 索引的效果。
建表和创建 Bitmap 索引
为了避免缓存 Page 影响查询性能,需要确保 BE 配置项 disable_storage_page_cache
为 true
。
本小节以 SSB 20G 的 lineorder 表(具有 1.4 亿行数据)为例说明。
-
原始表 (没有创建 Bitmap 索引)---作为参照对象。
CREATE TABLE `lineorder_without_index` (
`lo_orderkey` int(11) NOT NULL COMMENT "",
`lo_linenumber` int(11) NOT NULL COMMENT "",
`lo_custkey` int(11) NOT NULL COMMENT "",
`lo_partkey` int(11) NOT NULL COMMENT "",
`lo_suppkey` int(11) NOT NULL COMMENT "",
`lo_orderdate` int(11) NOT NULL COMMENT "",
`lo_orderpriority` varchar(16) NOT NULL COMMENT "",
`lo_shippriority` int(11) NOT NULL COMMENT "",
`lo_quantity` int(11) NOT NULL COMMENT "",
`lo_extendedprice` int(11) NOT NULL COMMENT "",
`lo_ordtotalprice` int(11) NOT NULL COMMENT "",
`lo_discount` int(11) NOT NULL COMMENT "",
`lo_revenue` int(11) NOT NULL COMMENT "",
`lo_supplycost` int(11) NOT NULL COMMENT "",
`lo_tax` int(11) NOT NULL COMMENT "",
`lo_commitdate` int(11) NOT NULL COMMENT "",
`lo_shipmode` varchar(11) NOT NULL COMMENT ""
) ENGINE=OLAP
DUPLICATE KEY(`lo_orderkey`)
DISTRIBUTED BY HASH(`lo_orderkey`) BUCKETS 1; -
具有 Bitmap 索引的表:基于
lo_shipmode
,lo_quantity
,lo_discount
,lo_orderdate
,lo_tax
,lo_partkey
创建 Bitmap 索引。CREATE TABLE `lineorder_with_index` (
`lo_orderkey` int(11) NOT NULL COMMENT "",
`lo_linenumber` int(11) NOT NULL COMMENT "",
`lo_custkey` int(11) NOT NULL COMMENT "",
`lo_partkey` int(11) NOT NULL COMMENT "",
`lo_suppkey` int(11) NOT NULL COMMENT "",
`lo_orderdate` int(11) NOT NULL COMMENT "",
`lo_orderpriority` varchar(16) NOT NULL COMMENT "",
`lo_shippriority` int(11) NOT NULL COMMENT "",
`lo_quantity` int(11) NOT NULL COMMENT "",
`lo_extendedprice` int(11) NOT NULL COMMENT "",
`lo_ordtotalprice` int(11) NOT NULL COMMENT "",
`lo_discount` int(11) NOT NULL COMMENT "",
`lo_revenue` int(11) NOT NULL COMMENT "",
`lo_supplycost` int(11) NOT NULL COMMENT "",
`lo_tax` int(11) NOT NULL COMMENT "",
`lo_commitdate` int(11) NOT NULL COMMENT "",
`lo_shipmode` varchar(11) NOT NULL COMMENT "",
INDEX i_shipmode (`lo_shipmode`) USING BITMAP,
INDEX i_quantity (`lo_quantity`) USING BITMAP,
INDEX i_discount (`lo_discount`) USING BITMAP,
INDEX i_orderdate (`lo_orderdate`) USING BITMAP,
INDEX i_tax (`lo_tax`) USING BITMAP,
INDEX i_partkey (`lo_partkey`) USING BITMAP
) ENGINE=OLAP
DUPLICATE KEY(`lo_orderkey`)
DISTRIBUTED BY HASH(`lo_orderkey`) BUCKETS 1;
Bitmap 索引占用磁盘空间情况
- lo_shipmode 字符串类型,基数为7, Bitmap 索引占用磁盘空间 130M
- lo_quantity: 整数类型,基数为 50, Bitmap 索引占用磁盘空间 291M
- lo_discount: 整数类型,基数为 11, Bitmap 索引占用磁盘空间 198M
- lo_orderdate: 整数类型,基数为 2406, Bitmap 索引占用磁盘空间 191M
- lo_tax: 整数类型,基数为 9, Bitmap 索引占用磁盘空间为 160M
- lo_partkey: 整数类型,基数为 60万,Bitmap索引占用磁盘空间为 601M
查询一:基于单个低基数列的查询
查询没有创建 Bitmap 索引的表
查询语句:
SELECT count(1) FROM lineorder_without_index WHERE lo_shipmode="MAIL";
查询性能分析:因为查询的表没有 Bitmap 索引,所以查询时会将包含 lo_shipmode
列数据的 Page 全部读出来,再进行谓词过滤。
总共耗时约 0.91 ms,其中加载数据花了 0.47 ms,低基数优化字典解码花了 0.31 ms,谓词过滤花了 0.23 ms。
PullRowNum: 20.566M (20566493) // 返回结果集的行数。
CompressedBytesRead: 55.283 MB // 读取的总数据量。
RawRowsRead: 143.999M (143999468) // 读取的数据行。因为没有 Bitmap 索引,这一列的数据全部读出来。
ReadPagesNum: 8.795K (8795) // 读取的 Page 数量。因为没有 Bitmap 索引,这一列数据所在的 Page 全部读出来。
IOTaskExecTime: 914ms // Scan 数据的总时间。
BlockFetch: 469ms // 加载数据时间。
DictDecode: 311.612ms // 低基数优化字典解码的时间。
PredFilter: 23.182ms // 谓词过滤的时间。
PredFilterRows: 123.433M (123432975) // 过滤掉的行数。