Bitmap索引适用场景和最佳实践

trueeyu · 2024年04月17日 08:24

使用 Bitmap 索引，需要综合考虑几个因素:

Bitmap 索引的磁盘空间占用
加载 Bitmap 索引的开销
Bitmap 索引的过滤效果
查询的特点

BitmapIndex 的过滤效果

在 StarRocks 数据文件中，数据是以 Page （默认为 64K）为单位组织和加载的，加载数据的开销主要有几个部分

从磁盘加加载 Page 的 IO 时间
Page 解压缩和解码时间

所以评估索引的过滤效果，应该以 Page 为单位来评估。

StarRocks 本身对于查询有 Bitmap 索引的自适应选择机制，大部分场景下，即使创建了不合适的 Bitmap 索引，也不会对查询性能造成明显的影响。

BitmapIndex 的适用场景

如果不考虑磁盘空间占用和导入性能，Bitmap 索引的适合场景主要有两个:

多个低基数列的组合查询，并且组合查询过滤效果好。
高基数列的过滤查询，并且过滤效果好。

因为 Bitmap 索引本身会占用一些磁盘空间，所以需要综合考虑上面提到的几个因素来决定是否创建 bitmap 索引。

BitmapIndex 可以优化哪些查询

等值 (=)
非等值 (>, >=, <, <=)
Is null

BitmapIndex 支持的数据模型

主键表和明细表中所有列都可以创建 Bitmap 索引

聚合表和更新表只有Key列支持创建 Bitmap 索引

BitmapIndex 支持的数据类型

日期类型：DATE、DATETIME。
数值类型：TINYINT、SMALLINT、INT、BIGINT、LARGEINT、DECIMAL 和 BOOLEAN。
字符串类型：CHAR、STRING 和 VARCHAR。
其他类型：HLL。

Bitmap Index 占用多大磁盘空间

以 ssb 20G 的 lineorder 表 (1.4亿行）为例说明:

原始表 (没有创建 bitmap index)

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;

对 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;

磁盘空间占用情况:

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

使用案例

为了方便说明问题，我们关闭 StarRocks 自有 cache: disable_storage_page_cache=true

通过对比这 3 种场景下的性能，来说明问题:

查询没有创建 Bitmap 索引的表
查询有 Bitmap 索引的表，并强制走 Bitmap 索引 (be.conf bitmap_max_filter_ratio=1000)
查询有 Bitmap 索引的表，由 StarRocks 默认配置决定是否使用 Bitmap 索引 (bitmap_max_filter_ratio=1)，默认千分之一过滤度才使用用 bitmap index

查询1: 单个低基数列上有等值过滤条件的查询

查询没有创建 Bitmap 索引的表

select count(1) from lineorder_without_index where lo_shipmode="MAIL";

因为没有索引 lo_shipmode 列的数据 page 全部读出来，再过滤。

总共耗时 914ms, 其中读数据并解码花了 780ms, 过滤花了 23 ms

select count(1) from lineorder_without_index where lo_shipmode="MAIL";
 
PullRowNum: 20.566M (20566493) // 返回结果集的行数
CompressedBytesRead: 55.283 MB // 读取了 55M 数据
RawRowsRead: 143.999M (143999468) // 因为没有索引，这一列的数据全部读出来
ReadPagesNum: 8.795K (8795) // 因为没有索引，这一列的 Page 全部读出来
IOTaskExecTime: 914ms // Scan 数据的总时间
    BlockFetch: 469ms     // Page 解码时间
    DictDecode: 311.612ms // 低基数解码时间
    PredFilter: 23.182ms  // 这一列数据全部读出来，并且进行过滤的时间
    PredFilterRows: 123.433M (123432975) // 过滤掉的行数

查询创建了 bitmap 索引的表，并强制走索引

select count(1) from lineorder_with_index where lo_shipmode="MAIL";

索引对行数过滤效果比较好，但是对于 Page 没有过滤效果，相当于引入了加载 Bitmap 和使用 Bitmap 索引过滤的开销，但是读的 Page 并没有减少，所以总时间反而更多

总共耗是 2s，其中读索引和读数据并解码花了 1.2s, Bitmap 索引过滤数据，花了 0.4s, ZoneMap 索引花了 0.17s

select count(1) from lineorder_with_index where lo_shipmode="MAIL";

PullRowNum: 20.566M (20566493) // 返回结果集的行数
CompressedBytesRead: 72.472 MB // 索引总大小是 130M，7个唯一值，单个值的索引大小为 18M，再加上数据 page （55M）= 73M 
RawRowsRead: 20.566M (20566493) // 实际只读了 2000万行
ReadPagesNum: 8.802K (8802) // 这 2000万行数据是随机分布在各个 Page的，所以 Bitmap 索引对于 Page没过滤效果，实际上还是读了所有 Page。
IOTaskExecTime: 2s77ms // Scan 数据总时间，相对于没创建索引更慢了
    BlockFetch: 931.144ms // 多读了 18M 数据，多花了 400ms
    DictDecode: 329.696ms // 输出的行数是一样的，所花时间差不多
    BitmapIndexFilter: 419.308ms // Bitmap 索引过滤数据，花了 419ms
    BitmapIndexFilterRows: 123.433M (123432975) // Bitmap 索引过滤掉 12亿行数据
    ZoneMapIndexFiter: 171.580ms

查询创建了 bitmap 索引的表，并由 StarRocks 自己决定是否走 Bitmap Index

select count(1) from lineorder_with_index where lo_shipmode="MAIL";

实际上效果等同于没有创建 Bitmap 索引。

select count(1) from lineorder_with_index where lo_shipmode="MAIL";

PullRowNum: 20.566M (20566493)
CompressedBytesRead: 55.283 MB
RawRowsRead: 143.999M (143999468)
ReadPagesNum: 8.800K (8800) 
IOTaskExecTime: 914.279ms
    BlockFetch: 475.890ms
    DictDecode: 312.019ms
    PredFilter: 17.311ms
    PredFilterRows: 123.433M (123432975)

查询2: 多个低基数列上有组合过滤条件的查询

查询没有创建 Bitmap 索引的表

select count(1) from lineorder_without_index where lo_shipmode="MAIL" and lo_quantity=10 and lo_discount=9 and lo_tax=8;

总共耗时 1.7s, 其中加载4个列的数据1.6s，过滤数据0.1s

PullRowNum: 4.092K (4092) // 返回结果集的行数
CompressedBytesRead: 305.346 MB // 读取了 4 列，总共 305M
RawRowsRead: 143.999M (143999468) // 因为没有索引，这几列的数据全部读出来
ReadPagesNum: 35.168K (35168) // 因为没有索引，这一列的 Page 全部读出来
IOTaskExecTime: 1s761ms // Scan 数据的总时间
    BlockFetch: 1s639ms // Page 解码时间
    PredFilter: 96.533ms // 使用 4 个过滤条件过滤的时间
    PredFilterRows: 143.995M (143995376) // 过滤掉的行数

查询创建了 bitmap 索引的表，并强制走索引

select count(1) from lineorder_with_index where lo_shipmode="MAIL" and lo_quantity=10 and lo_discount=9 and lo_tax=8;

总共耗时 0.68s，共中加载索引和数据用了 0.53s, Bitmap 索引过滤使用 0.14s

PullRowNum: 4.092K (4092)
CompressedBytesRead: 156.340 MB // BitmapIndex 组合过滤效果比较好，过滤掉了2/3数据，156M中，其中索引占 60M, 数据占 90M
ReadPagesNum: 11.325K (11325) // 过滤掉了 2/3 的 Page
IOTaskExecTime: 683.471ms
    BlockFetch: 537.421ms
    BitmapIndexFilter: 139.024ms
    BitmapIndexFilterRows: 143.995M (143995376)

查询创建了 bitmap 索引的表，使用默认配置

效果等同于强制走 Bitmap 索引

select count(1) from lineorder_with_index where lo_shipmode="MAIL" and lo_quantity=10 and lo_discount=9 and lo_tax=8;

PullRowNum: 4.092K (4092)
CompressedBytesRead: 154.430 MB
ReadPagesNum: 11.209K (11209)
IOTaskExecTime: 672.029ms
    BlockFetch: 535.823ms
    BitmapIndexFilter: 128.403ms
    BitmapIndexFilterRows: 143.995M (143995376)

查询3: 单个高基数列上有过滤条件的查询

查询没有创建 Bitmap 索引的表

select count(1) from lineorder_without_index where lo_partkey=10000;

PullRowNum: 255
CompressedBytesRead: 344.532 MB
RawRowsRead: 143.999M (143999468)
ReadPagesNum: 8.791K (8791)
IOTaskExecTime: 428.258ms
    BlockFetch: 392.434ms
    PredFilter: 20.807ms
    PredFilterRows: 143.999M (143999213)

查询创建了 bitmap 索引的表，并强制走索引

select count(1) from lineorder_with_index where lo_partkey=10000;

PullRowNum: 255
CompressedBytesRead: 13.600 MB
RawRowsRead: 255
ReadPagesNum: 225
IOTaskExecTime: 15.354ms
    BlockFetch: 9.530ms
    BitmapIndexFilter: 3.450ms
    BitmapIndexFilterRows: 143.999M (143999213)

查询创建了 bitmap 索引的表，使用默认配置

select count(1) from lineorder_with_index where lo_partkey=10000;

PullRowNum: 255
CompressedBytesRead: 13.600 MB
RawRowsRead: 255
ReadPagesNum: 225
IOTaskExecTime: 14.387ms
    BitmapIndexFilter: 2.979ms
    BitmapIndexFilterRows: 143.999M (143999213)
    BlockFetch: 8.988ms

sakuya · 2024年04月18日 03:06

磁盘空间占用情况:

lo_shipmode 字符串类型，基数为7, Bitmap 索引占用磁盘空间 130M
…
请问索引对各字段的磁盘占用是从哪里查看的？

trueeyu · 2024年04月18日 03:46

当前看起来比较麻烦，需要用工具才行，后面我们优化下这里。

MaricoWei · 2024年09月19日 08:02

那如果bitmap索引也建议高基数列，布隆索引也建议高基数列，在实际应用中应该选哪个呢？

trueeyu · 2024年09月19日 08:28

Bitmap索引，