位图索引

来自 PostgreSQL Wiki
跳转至导航跳转至搜索

实现概述

此页面详述了为 PostgreSQL 开发的磁盘位图索引访问法。

历史

虽然磁盘位图索引访问法最初是为 Greenplum 的 Bizgres 系统开发的，但它已移植并修改以满足 Postgres 标准。

  • Bizgres 实现
    • Ayush Parashar (Greenplum)
    • Jie Zhang (Greenplum)
    • Mark Kirkwood (Greenplum)
    • Gavin Sherry (Greenplum)
  • PostgreSQL 实现
    • Gavin Sherry (Greenplum)
      • 8.3 初始移植
    • 博士Gianni Ciolli 和 Gabriele Bartolini (2ndQuadrant Italia)
      • 8.4 的错误修复、重构和一般清理
    • Jonah H. Harris (myYearbook.com) 和 Simon Riggs (2ndQuadrant)
      • 8.5 的错误修复、重构、优化和一般清理

待办事项

  • 添加待办事项... :-)

概念

一般

与基于树的索引算法相比，磁盘位图索引为低基数、以读为主的数据提供了巨大的空间和性能优势。这种优势主要归因于 I/O 和 CPU 方面的节省。

在我们的实现中，为每个不同的键值创建一个压缩位图向量。这些位图向量不仅可用于查找表中单个键值的所有出现，还可以使用按位运算查找多个键值。

first_name last_name gender
John Smith M
David Jones M
Michael Johnson M
Chris Lee M
Mike Brown M
Mark Williams M
Paul Rodriguez M
Daniel Garcia M
James Gonzalez M
Maria Lopez F
Sarah Martinez F
Laura Martin F
Robert Perez M
Lisa Miller F
Jennifer Taylor F
Andrea Thomas F
Steve Wilson M
Peter Davis M
Kevin Khan M
Jason Ali M
Jessica Singh F
Michelle Sanchez F
Karen Anderson F
Joe Hernandez M
Brian Chan M
Alex Ahmed M
Richard White M
Linda Wong F
Julie Thompson F
Anna Jackson F
Andrew Kumar M
Mary Moore F
Eric Gomez M
Tom Diaz M
Thomas Walker M
Martin James M
Scott Green M
Matt Robinson M
Jim Clark M
Ali Young M
Tony Scott M
Carlos Chen M
Jeff Hall M
Marco Wright M
Ryan Adams M
Bob Allen M
Dave Hill M
Jose Rossi M

性别与 first_name 和 last_name 这两个属性不同，其基数非常低，只有 2（M 或 F）。因此，它非常适合使用位图索引。

不同的键值

不同的键值由值列表 (LOV) 组件处理...

不同的键位图

如上所述，一个单一比特向量与每个不同的键值相关联...

每个 LOV 项目（M 和 F）的未压缩位图如下

M = 11111111 10001000 11110001 11100010 11111111 11111111
F = 00000000 01110111 00001110 00011101 00000000 00000000

压缩

我们的实现基于混合游程长度压缩算法，该算法用两个组件（即头和内容部分）表示比特向量。

头部分 (头单词)

头部分包含比特，每个比特都对应内容部分中的一个单词。如果头部分中的某个比特为 1，则对应的内容部分中的单词就是一个压缩单词；如果比特为 0，则对应的单词不是压缩单词。

内容部分 (内容单词)

对于内容部分中的压缩单词，该单词中的第一个比特表示压缩的是 1 或 0。其余比特表示“<位数>/<单词大小>”的含义。

示例

考虑 LOV 项目 M 的未压缩位图向量

11111111 10001000 11110001 11100010 11111111 11111111

如果一个单词的大小设置为 8，则此位图向量的 HRL 压缩形式如下

header section:   00001
content section:  11111111 10001000 11110001 11100010 10000010

第一个单词未压缩。

第二个单词未压缩。

第五个单词已被压缩，并且其第一个比特设置为 1。因此，对 1 进行压缩。由于 10 计算结果为 2，这个压缩单词表示 16 个比特的 1（2 * 8 = 16）。

考虑 LOV 项目 F 的未压缩位图向量

00000000 01110111 00001110 00011101 00000000 00000000

如果一个单词的大小设置为 8，则此位图向量的 HRL 压缩形式如下

header section:   00001
content section:  00000000 01110111 00001110 00011101 00000010

第一个单词未压缩。

第二个单词未压缩。

第五个单词已被压缩，并且其第一个比特设置为 0。因此，对 0 进行压缩。由于 10 计算结果为 2，这个压缩单词表示 16 个比特的 0（2 * 8 = 16）。

基于排序的优化

由于位图索引通常用于数据仓库系统，因此在 ETL 阶段对值进行预排序可以提供更好的压缩。

示例

考虑 LOV 项目 M 的未压缩位图向量

00000000 00000111 11111111 11111111 11111111 11111111

如果一个单词的大小设置为 8，则此位图向量的 HRL 压缩形式如下

header section:   001
content section:  00000000 00000111 10000100

第一个单词未压缩。

第二个单词未压缩。

第三个单词已被压缩，并且其第一个比特设置为 1。因此，对 1 进行压缩。由于 100 计算结果为 4，这个压缩单词表示 32 个比特的 1（4 * 8 = 32）。

考虑 LOV 项目 F 的未压缩位图向量

11111111 11111000 00000000 00000000 00000000 00000000

如果一个单词的大小设置为 8，则此位图向量的 HRL 压缩形式如下

header section:   001
content section:  11111111 11111000 00000100

第一个单词未压缩。

第二个单词未压缩。

第三个单词已被压缩，并且其第一个比特设置为 0。因此，对 0 进行压缩。由于 100 计算结果为 4，这个压缩单词表示 32 个比特的 0（3 * 8 = 24）。

在各种用例下的操作

以下部分描述了针对不同情况位图索引所遵循的各种过程。

索引创建

元组插入

元组更新

元组删除

索引扫描

VACUUM

运行时行为

预写式日志记录

位图索引的更改已被 WAL 记录，可以防止崩溃。

锁定

插入/更新处理

VACUUM

性能

索引创建

索引大小

索引性能

基准测试套件

页面检查

一般

bm_page_headers()

元页面

bm_metap()

LOV 页

bm_lov_page_stats()

位图页

bm_bmv_page_stats()

页面布局

磁盘上位图索引实现包括多个页面布局

元页面

此页面包含有关索引的元数据，始终存储为第零页，并且被称为 BM_METAPAGE。

+----------------+---------------------------------+
| PageHeaderData | BMMetaPageData                  |
+----------------+---------------------------------+
|                ^ pd_lower                        |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
+--------------------------------------------------+
                               pd_upper/pd_special ^

值列表 (LOV) 页

值列表 (LOV) 页用来存储要索引的属性的唯一值列表，一些与其对应的位图向量相关的元数据，以及指向其位图向量的指针。对于每个唯一的值，都有一个与其关联的 BMLOVItemData。

LOV 页维护一个称为 LOV 项的 BMLOVItemData 实例数组。为了快速查找给定值的 LOV 项，我们创建一个堆来维护所有唯一键值以及 LOV 页中 LOV 项的块号和偏移号。也就是说，这个新堆中有 <属性数量> + 2 个属性。在此堆中，我们还使用属性作为键在此堆上创建一个新的 B 树索引。这样，对于给定的值，我们搜索此 B 树以快速找到给定值的对应 LOV 项的适用块号和偏移号。

第一个 LOV 页保留给 NULL 键值，被称为 BM_LOV_STARTPAGE。

+----------------+---------------------------------+
| PageHeaderData | linp1 linp2 linp3 ...           |
+-----------+----+---------------------------------+
| ... linpN |                                      |
+-----------+--------------------------------------+
|           ^ pd_lower                             |
|                                                  |
|             v pd_upper                           |
+-------------+------------------------------------+
|             | BMLOVItemN ...                     |
+-------------+------------------------------------+
|             ... BMLOVItem3 BMLOVItem2 BMLOVItem1 |
+--------------------------------------------------+
                               pd_upper/pd_special ^

位图向量页

此页面布局表示压缩位图向量。

每个位图页存储两部分信息：标头词和内容词。标头词中的每一比特对应于内容词中的一个词。如果标头词中的某一位是 1，那么其对应的内容词是一个压缩词。否则，它是一个原义词。

如果一个内容词是一个填充词，这意味着有一串 0 位或 1 位。这个内容词中最重要的一位表示这串位是 0 位还是 1 位。其余的位存储值“位数 / BM_WORD_SIZE”。

在此块中，使用了两个数据结构：BMBitmapVectorPageData 和 BMPageOpaqueData。BMBitmapVectorPageData 包含两个固定大小的数组：标头词和内容词；两个数组的大小基于编译时的 Postgres 块大小定义。BMPageOpaqueData 包含与该页面相关的信息，包括使用的词数量、位图中的下一页以及该页面中设置的最后一个 TID。

+----------------+---------------------------------+
| PageHeaderData | BMBitmapVectorPageData          |
+----------------+---------------------------------+
|                ^ pd_lower                        |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                               v pd_upper         |
+-------------------------------+------------------+
|                           ... | BMPageOpaqueData |
+-------------------------------+------------------+
                                ^ pd_special

源代码详细信息

文件

由于按磁盘方式编制的位图索引是另一种访问方法，因此会相应地布置新文件

  • src/backend/access/bitmap/
    • bitmapattutil.c--属性级别 List-of-Values (LOV) 处理
    • bitmap.c--顶级访问方法接口函数
    • bitmapinsert.c--位图插入
    • bitmappages.c--特定于位图的页面处理
    • bitmapsearch.c--位图搜索/迭代
    • bitmaputil.c--通用位图实用函数/VACUUM 处理
    • bitmapxlog.c--WAL 处理
  • src/include/access/
    • bitmap.h--按磁盘方式编制访问方法的位图标题文件

命名约定

函数

对于 b-tree 和哈希访问方法，不用下划线前缀命名的函数，位图索引函数的命名类似于 gin/gist 中使用 lowerCamelCase，前缀为 bm。示例如下

  • bmInitLOVPage
  • bmReadBuffer
  • bmWriteAndReleaseBuffer
  • bmSetTIDBit

结构/类型定义/变量

C 结构和类型定义使用 UpperCamelCase 命名。结构成员和变量使用 lowerCamelCase 命名，除非邮政已对该变量使用了一致性名称。

例如，content words 的结构成员应为“contentWords”，而不是 content_words 或 contentwords。

评论

为了进一步提升PostgreSQL 源代码文档，所有评论与 doxygen 兼容。来自 bitmappages.c

/**
 * Reads, locks, and returns a given relation's block as a buffer.
 *
 * @param[in]       reln        The relation whose block to read
 * @param[in]       blockNum    The block number to read
 * @param[in]       lockMode    The buffer content lock type to use
 *
 * @return  A locked buffer containing the requested block of the requested relation.
 */
Buffer
bmReadBuffer (Relation reln, BlockNumber blockNum, int lockMode)
{

编译时选项

位图索引追踪

为了帮助进行调试和准确性验证，已对位图索引访问方法添加了大量追踪。如果需要追踪，则必须在编译时通过定义（取消注释）src/include/access/bitmap.h 中的 TRACE_BITMAP_INDEX 来启用追踪。启用时，所有相关的内部位图索引信息都将在消息级别 DEBUG1-DEBUG5 中发出。

追踪的示例如下

DEBUG:  bminsert (rel => "bitmapx1",
DEBUG:            ht_ctid => "(0,1)")
DEBUG:  bmPerformInsert (rel => "bitmapx1",
DEBUG:                   ht_ctid => "(0,1)")
DEBUG:  bmReadBuffer (reln => "bitmapx1",
DEBUG:                blockNum => 0,
DEBUG:                lockMode => 1)
DEBUG:  bmOpenLOVHeapAndIndex (metaPage->bm_lov_heapId => 66151,
DEBUG:                         metaPage->bm_lov_indexId => 66154,
DEBUG:                         lockMode => 3)
DEBUG:  bmInsertTuple (reln => "bitmapx1",
DEBUG:                 metaBuffer => 0,
DEBUG:                 tidBit => 1,
DEBUG:                 ht_ctid => "(0,1)",
DEBUG:                 lovHeap => "pg_bm_66150",
DEBUG:                 lovIndex => "pg_bm_66150_index",
DEBUG:                 use_wal => "TRUE")
...
DEBUG:  bmSetTIDBit (reln => "bitmapx1",
DEBUG:               lovBuffer => 1,
DEBUG:               lovOffset => 2,
DEBUG:               tidBit => 1,
DEBUG:               use_wal => "TRUE")

目录更改

  • 位图索引已新增为 WAL 的资源管理器（RM_BITMAP_ID）
  • 位图索引已新增至 pg_am、pg_amop、pg_proc 及类似项中。
  • 已创建 pg_bitmapindex，这是一用于包含数据库范围的位图索引特定数据的新名称空间。
取自“https://wiki.postgresql.ac.cn/index.php?title=Bitmap_Indexes&oldid=35379”