跳到主要内容
版本: 最新版本-3.5

Bitmap 索引

本文介绍如何创建和管理 Bitmap 索引,以及 Bitmap 索引的使用场景。

简介

Bitmap 索引是一种特殊的数据库索引,它使用位图(bits 的数组)。一个 bit 只有两种取值:0 和 1。 位图中的每个 bit 对应于表中的一行。每个 bit 的值取决于对应行的值。

Bitmap 索引可以帮助提高给定列的查询性能。 如果查询的过滤条件与前缀索引匹配,则可以显着提高查询效率并快速返回结果。 但是,一个表只能有一个前缀索引。 如果查询的过滤条件不包括前缀索引的前缀,则可以为该列创建 Bitmap 索引以提高查询效率。

如何设计 Bitmap 索引加速查询

选择 Bitmap 索引的主要考虑因素是**列的基数和 Bitmap 索引对查询的过滤效果**。 与普遍的看法相反,StarRocks 中的 Bitmap 索引更适合**对高基数列的查询和对多个低基数列组合的查询。 此外,Bitmap 索引需要有效地过滤数据,可能过滤掉至少 999/1000 的数据,从而减少读取的 Page 数据量。**

对于单个低基数列的查询,Bitmap 索引的过滤效果较差,因为需要读取的行太多并且分散在多个 Page 中。

info

在评估 Bitmap 索引对查询的过滤效果时,您需要考虑加载数据的成本。 在 StarRocks 中,底层数据按 Page(默认大小为 64K)组织和加载。 加载数据的成本包括从磁盘加载 Page、解压缩 Page 和解码的时间。

但是,过高的基数也会导致诸如**占用更多磁盘空间**的问题,并且由于 Bitmap 索引需要在数据加载期间构建,因此频繁的数据加载会**影响加载性能**。

此外,应考虑**查询期间加载 Bitmap 索引的开销**。 在查询期间,Bitmap 索引按需加载,query conditions/cardinality x bitmap index 中涉及的列值的数量的值越大,查询期间加载 Bitmap 索引的开销就越大。

要确定 Bitmap 索引的适当基数和查询条件,建议参考本文中的Bitmap 索引的性能测试进行性能测试。 您可以使用实际业务数据和查询来**在不同基数列上创建 Bitmap 索引,以分析 Bitmap 索引对查询的过滤效果(至少过滤掉 999/1000 的数据),磁盘空间使用情况、对加载性能的影响以及查询期间加载 Bitmap 索引的开销。**

StarRocks 具有内置的 Bitmap 索引自适应选择机制。 如果 Bitmap 索引无法加速查询,例如,如果无法过滤掉许多 Page,或者查询期间加载 Bitmap 索引的开销很高,则在查询期间不会使用它,因此查询性能不会受到显着影响。

Bitmap 索引的自适应选择

StarRocks 可以根据列基数和查询条件自适应地选择是否使用 Bitmap 索引。 如果 Bitmap 索引不能有效地过滤掉许多 Page,或者查询期间加载 Bitmap 索引的开销很高,StarRocks 默认情况下不会使用 Bitmap 索引,以避免降低查询性能。

StarRocks 根据查询条件中涉及的值的数量与列基数的比率来确定是否使用 Bitmap 索引。 通常,这个比率越小,Bitmap 索引的过滤效果越好。 因此,StarRocks 使用 bitmap_max_filter_ratio/1000 作为阈值。 当 filter condition/column cardinality 中的值的数量 小于 bitmap_max_filter_ratio/1000 时,将使用 Bitmap 索引。 bitmap_max_filter_ratio 的默认值为 1

以基于单列的查询为例,例如 SELECT * FROM employees WHERE gender = 'male';employees 表中的 gender 列具有值 'male' 和 'female',因此基数为 2(两个不同的值)。 查询条件涉及一个值,因此比率为 1/2,大于 1/1000。 因此,此查询不会使用 Bitmap 索引。

以基于多个列组合的另一个查询为例,例如 SELECT * FROM employees WHERE gender = 'male' AND city IN ('Beijing', 'Shanghai');city 列的基数为 10,000,查询条件涉及两个值,因此比率计算为 (1*2)/(2*10000),小于 1/1000。 因此,此查询将使用 Bitmap 索引。

info

bitmap_max_filter_ratio 的值范围为 1-1000。 如果 bitmap_max_filter_ratio 设置为 1000,则强制对具有 Bitmap 索引的列的任何查询使用 Bitmap 索引。

优势

  • Bitmap 索引可以快速定位查询列值的行号,适用于点查询或小范围查询。
  • Bitmap 索引可以优化涉及并集和交集运算(ORAND 运算)的多维查询。

注意事项

可以优化的查询

Bitmap 索引适用于优化相等 = 查询、[NOT] IN 范围查询、>>=<<= 查询和 IS NULL 查询。 它们不适用于优化 !=[NOT] LIKE 查询。

支持的列和数据类型

可以在主键表和重复键表中的所有列以及聚合键表和唯一键表中的键列上创建 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 索引,用逗号 (,) 分隔。

    note

    有关表创建的更多参数,请参阅 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;
info

每个表一次只能有一个正在进行的 Schema Change 任务。 在创建当前 Bitmap 索引之前,您无法创建新的 Bitmap 索引。

查看索引

查看指定表的所有 Bitmap 索引。 有关详细参数和返回结果,请参阅 SHOW INDEX

SHOW INDEXES FROM lineorder_partial;
note

创建 Bitmap 索引是一个异步过程。 使用以上语句,您只能查看已成功完成创建的索引。

删除索引

删除指定表的 Bitmap 索引。 有关详细的参数和示例,请参阅 DROP INDEX

DROP INDEX lo_orderdate_index ON lineorder_partial;

验证 Bitmap 索引是否加速查询

检查查询 Profile 中的 BitmapIndexFilterRows 字段。 有关查看 Profile 的信息,请参阅 查询分析

Bitmap 索引的性能测试

测试目标

分析 Bitmap 索引对不同基数的查询的过滤效果和其他影响,例如磁盘使用情况

本节还将比较始终使用 Bitmap 索引和自适应使用 Bitmap 索引之间的性能,以验证 StarRocks 的 Bitmap 索引自适应选择 的有效性。

创建表和 Bitmap 索引

warning

为避免缓存 Page 数据影响查询性能,请确保 BE 配置项 disable_storage 设置为 true

本节以表 lineorder (SSB 20G) 为例。

  • 原始表(没有 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_shipmodelo_quantitylo_discountlo_orderdatelo_taxlo_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,占用 130M
  • lo_quantity:整数类型,基数 50,占用 291M
  • lo_discount:整数类型,基数 11,占用 198M
  • lo_orderdate:整数类型,基数 2406,占用 191M
  • lo_tax:整数类型,基数 9,占用 160M
  • lo_partkey:整数类型,基数 600,000,占用 601M

查询 1:对低基数单列的查询

查询没有 Bitmap 索引的表

查询:

SELECT count(1) FROM lineorder_without_index WHERE lo_shipmode="MAIL";

查询性能分析:由于查询的表没有 Bitmap 索引,因此需要读取包含 lo_shipmode 列数据的所有页面,然后应用谓词过滤。

总时间:大约 0.91 秒,数据加载耗时 0.47 秒,低基数优化的字典解码耗时 0.31 秒,谓词过滤耗时 0.23 秒。

PullRowNum: 20.566M (20566493) // Number of rows in the result set.
CompressedBytesRead: 55.283 MB // Total amount of data read.
RawRowsRead: 143.999M (143999468) // Number of rows read. Since there is no bitmap index, all data in this column is read.
ReadPagesNum: 8.795K (8795) // Number of pages read. Since there is no bitmap index, all pages containing data for this column are read.
IOTaskExecTime: 914ms // Total time for scanning data.
BlockFetch: 469ms // Time for loading data.
DictDecode: 311.612ms // Time for decoding dictionary for low cardinality optimization.
PredFilter: 23.182ms // Time for predicate filtering.
PredFilterRows: 123.433M (123432975) // Number of rows filtered out.

查询具有 Bitmap 索引的表

强制使用 Bitmap 索引
info

要强制使用 Bitmap 索引,根据 Starrocks 的配置,需要在每个 BE 节点的 be.conf 文件中设置 bitmap_max_filter_ratio=1000,然后需要重新启动 BE 节点。

查询:

SELECT count(1) FROM lineorder_with_index WHERE lo_shipmode="MAIL";

查询性能分析:由于查询的列是低基数,Bitmap 索引无法有效地过滤数据。 即使 Bitmap 索引可以快速定位实际数据的行号,也需要读取大量行,这些行分散在多个页面中。 因此,它不能有效地过滤掉需要读取的页面。 此外,还会产生加载 Bitmap 索引并使用 Bitmap 索引过滤数据的额外开销,从而导致总时间更长。

总时间:2.077 秒,加载数据和 Bitmap 索引耗时 0.93 秒,低基数优化的字典解码耗时 0.33 秒,用 Bitmap 索引过滤数据耗时 0.42 秒,用 ZoneMap Index 过滤数据耗时 0.17 秒。

PullRowNum: 20.566M (20566493) // Number of rows in the result set.
CompressedBytesRead: 72.472 MB // Total amount of data read. The size of the bitmap index for this column is 130MB, with 7 unique values. The size of a bitmap index for each value is 18MB. The data size of Pages is 55MB = 73MB.
RawRowsRead: 20.566M (20566493) // Number of rows read. 20 million rows are actually read.
ReadPagesNum: 8.802K (8802) // Number of Pages read. All Pages are read because the 20 million rows filtered by bitmap index are randomly distributed across different Pages, and Page is the smallest data reading unit. Therefore, bitmap index does not filter out Pages.
IOTaskExecTime: 2s77ms // Total time for scanning data, longer than without bitmap index.
BlockFetch: 931.144ms // Time for loading data and bitmap index. Compared to the previous query, an additional 400ms was spent to load bitmap index (18MB).
DictDecode: 329.696ms // Time for decoding dictionary for low cardinality optimization is similar since the output row count is the same.
BitmapIndexFilter: 419.308ms // Time for filtering data with the bitmap index.
BitmapIndexFilterRows: 123.433M (123432975) // Number of rows filtered by the bitmap index.
ZoneMapIndexFiter: 171.580ms // Time for filtering data with ZoneMap Index.
根据 StarRocks 默认配置确定是否使用 Bitmap 索引

查询:

SELECT count(1) FROM lineorder_with_index WHERE lo_shipmode="MAIL";

查询性能分析:根据 StarRocks 的默认配置,仅当过滤条件列中的不同值的数量 / 列基数 < bitmap_max_filter_ratio/1000(默认为 1/1000)时才使用 Bitmap 索引。 在这种情况下,该值大于 1/1000,因此不使用 Bitmap 索引,导致性能类似于查询没有 Bitmap 索引的表。

PullRowNum: 20.566M (20566493) // Number of rows in the result set.
CompressedBytesRead: 55.283 MB // Total amount of data read.
RawRowsRead: 143.999M (143999468) // Number of rows read. Since the bitmap index is not used, all data in this column is read.
ReadPagesNum: 8.800K (8800) // Number of Pages read. Since the bitmap index is not used, all pages containing data for this column are read.
IOTaskExecTime: 914.279ms // Total time for scanning data.
BlockFetch: 475.890ms // Time for loading data.
DictDecode: 312.019ms // Time for decoding dictionary for low cardinality optimization.
PredFilterRows: 123.433M (123432975) // Number of rows filtered out by predicate.

查询 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;

查询性能分析:由于查询的表没有任何 Bitmap 索引,因此读取包含 lo_shipmodelo_quantitylo_discountlo_tax 列数据的所有 Page,然后应用谓词过滤。

总耗时:1.76 秒,数据加载(4 列)耗时 1.6 秒,谓词过滤耗时 0.1 秒。

PullRowNum: 4.092K (4092) // Number of rows in the result set.
CompressedBytesRead: 305.346 MB // Total amount of data read. Data of 4 columns is read, totaling 305MB.
RawRowsRead: 143.999M (143999468) // Number of rows read. Since there is no bitmap index, all data of these 4 columns are read.
ReadPagesNum: 35.168K (35168) // Number of Pages read. Since there is no bitmap index, all Pages containing data of these 4 columns are read.
IOTaskExecTime: 1s761ms // Total time for scanning data.
BlockFetch: 1s639ms // Time for loading data.
PredFilter: 96.533ms // Time for predicate filtering with 4 filter conditions.
PredFilterRows: 143.995M (143995376) // Number of rows filtered out by predicates.

查询具有 Bitmap 索引的表

强制使用 Bitmap 索引
info

要强制使用 Bitmap 索引,根据 Starrocks 的配置,必须在每个 BE 节点的 be.conf 文件中设置 bitmap_max_filter_ratio=1000,然后必须重新启动 BE 节点。

查询:

SELECT count(1) FROM lineorder_with_index WHERE lo_shipmode="MAIL" AND lo_quantity=10 AND lo_discount=9 AND lo_tax=8;

查询性能分析:由于这是一个基于多个低基数列的组合查询,Bitmap 索引有效,过滤掉一部分 Page,显着减少了数据读取时间。

总耗时:0.68 秒,加载数据和 Bitmap 索引耗时 0.54 秒,用 Bitmap 索引过滤数据耗时 0.14 秒。

PullRowNum: 4.092K (4092) // Number of rows in the result set.
CompressedBytesRead: 156.340 MB // Total amount of data read. The bitmap index effectively filters out 2/3 of the data. Out of this 156MB, 60MB is index data, and 90MB is actual data.
ReadPagesNum: 11.325K (11325) // Number of Pages read. The bitmap index effectively filters out 2/3 of the Pages.
IOTaskExecTime: 683.471ms // Total time for scanning data, significantly less than the total time spent without bitmap index.
BlockFetch: 537.421ms // Time for loading data and the bitmap index. Although additional time is spent loading the bitmap index, it significantly reduces the time to load data.
BitmapIndexFilter: 139.024ms // Time for filtering data with bitmap index.
BitmapIndexFilterRows: 143.995M (143995376) // Number of rows filtered out by bitmap index.
根据 StarRocks 默认配置确定是否使用 Bitmap 索引

查询:

SELECT count(1) FROM lineorder_with_index WHERE lo_shipmode="MAIL" AND lo_quantity=10 AND lo_discount=9 AND lo_tax=8;

查询性能分析:根据 StarRocks 的默认配置,如果过滤条件列中的不同值的数量 / 列基数 < bitmap_max_filter_ratio/1000(默认为 1/1000),则使用 Bitmap 索引。 在这种情况下,该值小于 1/1000,因此使用 Bitmap 索引,导致性能类似于强制使用 Bitmap 索引。

总耗时:0.67 秒,加载数据和 Bitmap 索引耗时 0.54 秒,用 Bitmap 索引过滤数据耗时 0.13 秒。

PullRowNum: 4.092K (4092) // Number of rows in the result set.
CompressedBytesRead: 154.430 MB // Total amount of data read.
ReadPagesNum: 11.209K (11209) // Number of Pages read.
IOTaskExecTime: 672.029ms // Total time for scanning data, significantly less than without bitmap index.
BlockFetch: 535.823ms // Time for loading data and bitmap index. Although loading bitmap index takes a little more time, it greatly reduces data loading time.
BitmapIndexFilter: 128.403ms // Time for filtering data with bitmap index.
BitmapIndexFilterRows: 143.995M (143995376) // Number of rows filtered out by bitmap index.

查询 3:对高基数单列的查询

查询没有 Bitmap 索引的表

查询:

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

查询性能分析:由于查询的表没有 Bitmap 索引,因此读取包含 lo_partkey 列数据的页面,然后应用谓词过滤。

总耗时:大约 0.43 秒,包括数据加载耗时 0.39 秒,谓词过滤耗时 0.02 秒。

PullRowNum: 255 // Number of rows in the result set.
CompressedBytesRead: 344.532 MB // Total amount of data read.
RawRowsRead: 143.999M (143,999,468) // Number of rows read. Since there is no bitmap index, all data in this column is read.
ReadPagesNum: 8.791K (8,791) // Number of pages read. Since there is no bitmap index, all data of this column are read.
IOTaskExecTime: 428.258ms // Total time for scanning data.
BlockFetch: 392.434ms // Time for loading data.
PredFilter: 20.807ms // Time for predicate filtering.
PredFilterRows: 143.999M (143,999,213) // Number of rows filtered out by predicates.

查询具有 Bitmap 索引的表

强制使用 Bitmap 索引
info

要强制使用 Bitmap 索引,根据 Starrocks 的配置,必须在每个 BE 节点的 be.conf 文件中设置 bitmap_max_filter_ratio=1000,然后重新启动 BE 节点。

查询:

SELECT count(1) FROM lineorder_with_index WHERE lo_partkey=10000;

查询性能分析:由于查询的列是高基数,Bitmap 索引有效,允许过滤掉一部分页面,并显着减少读取数据的时间。

总耗时:0.015 秒,包括加载数据和 Bitmap 索引耗时 0.009 秒,Bitmap 索引过滤耗时 0.003 秒。

PullRowNum: 255 // Number of rows in the result set.
CompressedBytesRead: 13.600 MB // Total amount of data read. Bitmap Index filtering is effective, filtering out a large amount of data.
RawRowsRead: 255 // Number of rows read.
ReadPagesNum: 225 // Number of pages read. The bitmap index can effectively filter out data, filtering out a large number of pages.
IOTaskExecTime: 15.354ms // Total time for scanning data, significantly less than the total time spent without Bitmap Index.
BlockFetch: 9.530ms // Time for loading data and Bitmap Index. Although additional time is spent loading the Bitmap Index, it significantly reduces the time to load data.
BitmapIndexFilter: 3.450ms // Time for filtering data with Bitmap Index.
BitmapIndexFilterRows: 143.999M (143,999,213) // Number of rows filtered out by Bitmap Index.
根据 StarRocks 默认配置确定是否使用 Bitmap 索引

查询:

SELECT count(1) FROM lineorder_with_index WHERE lo_partkey=10000;

查询性能分析:根据 StarRocks 的默认配置,当不同值的数量/列基数 < bitmap_max_filter_ratio/1000(默认 1/1000)时,将使用 Bitmap 索引。 由于满足此条件,因此查询使用 Bitmap 索引,并且性能类似于强制使用 Bitmap 索引时的性能。

总耗时:0.014 秒,包括 加载数据和 Bitmap 索引耗时 0.008 秒,Bitmap 索引过滤耗时 0.003 秒。

PullRowNum: 255 // Number of rows in the result set.
CompressedBytesRead: 13.600 MB // Total amount of data read. The bitmap index can effectively filter out data, filtering out a large number of data.
RawRowsRead: 255 // Number of rows read.
ReadPagesNum: 225 // Number of pages read. The bitmap index can effectively filter out data, filtering out a large number of pages.
IOTaskExecTime: 14.387ms // Total time for scanning data, significantly less than the total time spent without Bitmap Index.
BitmapIndexFilter: 2.979ms // Time for filtering data with Bitmap Index.
BitmapIndexFilterRows: 143.999M (143,999,213) // Number of rows filtered out by Bitmap Index.
BlockFetch: 8.988ms // Time for loading data and Bitmap Index. Although additional time is spent loading the Bitmap Index, it significantly reduces the time to load data.