引言
我在莫斯科举行的GopherCon Russia 2019会议上用英语发表了这份报告，在下诺夫哥罗德会议上用俄语做了这份报告。 它是关于位图索引的，它比B树少见，但也很有趣。 我在会议上分享英语演讲的
录音和俄语的文字记录。
我们将研究位图索引的工作原理，何时比其他索引更好，何时比其他索引差以及在什么情况下比它们快得多。 我们将看到哪些流行的DBMS已经具有位图索引。 尝试在Go上编写自己的内容。 对于甜点，我们将使用现成的库来创建我们自己的超快速专业数据库。
我真的希望我的工作对您有用和有趣。 走吧
引言
http://bit.ly/bitmapindexeshttps://github.com/mkevac/gopherconrussia2019大家好！ 晚上六点，我们都很累。 是时候谈论无聊的数据库索引理论了吧？ 不用担心，这里到那里我都会有几行源代码。 :-)
如果没有笑话，那么该报告将充满信息，而且我们没有太多时间。 因此，让我们开始吧。
今天，我将讨论以下内容：
- 什么是索引；
- 什么是位图索引；
- 在何处使用和不使用它，为什么；
- Go上的简单实现，以及与编译器的一些挣扎；
- 在Go-assembler中稍微简单一些，但生产效率更高；
- 位图索引的“问题”；
- 现有的实现。
那么什么是索引？
索引是除主要数据外，我们还持有并更新的单独数据结构。 它用于加快搜索速度。 如果没有索引，则搜索将需要对数据进行完整遍历（称为完全扫描的过程），并且此过程具有线性算法复杂度。 但是数据库通常包含大量数据，线性复杂度太慢。 理想情况下，我们将得到对数或常数。
这是一个巨大的复杂主题，充满了微妙和折衷，但是在研究了各种数据库数十年的发展和研究之后，我准备提出只有几种被广泛使用的创建数据库索引的方法。
第一种方法是分层缩小搜索区域，将搜索区域划分为较小的部分。
通常我们使用各种各样的树来做到这一点。 一个示例是在您的壁橱中放有材料的大盒子，在其中有放有各种主题的材料的小盒子。 如果您需要材料，则可能会在带有“材料”字样的框中寻找它们，而不是在带有“ Cookies”字样的框中寻找它们，对吗？
第二种方法是立即选择所需的元素或元素组。 我们在哈希映射或反向索引中执行此操作。 使用哈希映射与前面的示例非常相似，只是在储藏室中有很多小盒子而不是壁橱里有盒子的盒子。
第三种方法是摆脱搜索的需要。 我们使用布隆过滤器或布谷鸟过滤器进行此操作。 前者可立即提供答案，而无需搜索。
最后一种方法是充分利用现代熨斗赋予我们的所有能力。 这正是我们在位图索引中所做的。 是的，使用它们时，有时我们需要遍历整个索引，但是我们做得非常高效。
就像我说过的那样，数据库索引的主题非常广泛，而且妥协很多。 这意味着有时我们可以同时使用几种方法：如果我们需要进一步加快搜索速度，或者是否有必要涵盖所有可能的搜索类型。
今天，我将讨论其中鲜为人知的方法-位图索引。
我是谁呢？
我是Badoo的团队负责人（也许您更了解我们的另一款产品Bumble）。 我们已经在全球拥有超过4亿用户，并且许多功能都在为他们选择最佳用户对。 我们使用也使用位图索引的自定义服务来执行此操作。
那么什么是位图索引？
顾名思义，位图索引使用位图或位集来实现搜索索引。 从鸟瞰的角度来看，该索引由一个或多个表示任何实体（例如人）及其属性或参数（年龄，眼睛的颜色等）的位图，以及使用位操作（AND，或，不是）以响应搜索查询。
有人告诉我们，位图索引最适合在这样的情况下使用，即在搜索时将基数很少的许多列中的查询组合在一起（例如“眼睛颜色”或“婚姻状况”与“距市中心的距离”之类的查询）时） 但是稍后，我将展示它们在具有高基数的列的情况下可以完美地工作。
考虑一个最简单的位图索引示例。
想象一下，我们有一个具有以下二进制属性的莫斯科餐厅列表：
- 靠近地铁站（靠近地铁站）；
- 有一个私人停车场（有私人停车场）；
- 有一个阳台（有露台）；
- 您可以预订一张桌子（接受预订）；
- 适合素食者（素食主义者友好）；
- 昂贵（昂贵）。
让我们给每个餐厅一个从0开始的序列号，并为6个位图分配内存（每个特征一个）。 然后，根据餐厅是否具有此属性来填充这些位图。 如果餐厅4有阳台，则位图中“有阳台”中的第4位将设置为1（如果没有阳台，则将其设置为0）。
现在，我们有了最简单的位图索引，并且可以使用它来回答如下查询：
- “给我看适合素食者的餐馆”；
- “告诉我带阳台的便宜餐厅，您可以在上面预订桌子。”
怎么了 让我们看看。 第一个请求非常简单。 我们需要做的就是获取“适合素食者”位图，并将其转换为显示其位的餐厅列表。
第二个查询有点复杂。 我们需要对“昂贵”的位图使用NOT位操作来获取便宜餐厅的列表，然后将其与位图“可以保留一张桌子”一起设置，并通过位图“有门廊”来设置结果。 生成的位图将包含符合我们所有条件的场所列表。 在此示例中，这只是Yunost餐厅。
有很多理论，但是不用担心，我们很快就会看到代码。
在哪里使用位图索引？
如果您“谷歌”位图索引，那么90％的答案将以某种方式与Oracle DB有关。 但是其余的DBMS也可能支持这种很酷的功能，对吗？ 不完全是
让我们浏览一下主要嫌疑犯的名单。
MySQL尚不支持位图索引，但是有一个建议书，建议添加此选项（
https://dev.mysql.com/worklog/task/?id=1524 ）。
PostgreSQL不支持位图索引，但是使用简单的位图和位操作来组合其他多个索引中的搜索结果。
Tarantool具有位集索引，它支持对它们的简单搜索。
Redis具有简单的位字段
（https://redis.io/commands/bitfield ），无法搜索它们。
MongoDB尚不支持位图索引，但是还有一个建议书，其中包含添加此选项的建议书
https://jira.mongodb.org/browse/SERVER-1723Elasticsearch在内部使用位图
（https://www.elastic.co/blog/frame-of-reference-and-roaring-bitmaps ）。
- 但是我们家出现了一个新邻居：皮洛萨。 这是用Go编写的新的非关系数据库。 它仅包含位图索引，并且所有内容都基于它们。 我们待会儿再谈她。
实施
但是，为什么很少使用位图索引？ 在回答这个问题之前，我想向您演示一个非常简单的位图索引在Go上的实现。
位图本质上只是数据。 在Go中，我们为此使用字节片。
每个餐厅特征都有一个位图，位图中的每个位指示特定餐厅是否具有此属性。
我们将需要两个辅助功能。 一个将用于用随机数据填充我们的位图。 随机，但餐厅拥有所有资产的可能性很大。 例如，我认为莫斯科很少有餐厅不能预订餐桌，在我看来，大约有20％的场所适合素食主义者。
第二个功能会将位图转换为餐厅列表。
要回答“给我看一下有阳台的便宜餐厅，您可以在那儿预订餐桌”的要求，我们需要进行两位操作：NOT和AND。
我们可以通过使用更复杂的AND NOT操作来稍微简化代码。
我们为每个操作提供功能。 它们都经过切片，从每个切片中获取相应的元素，将它们与位操作组合在一起，然后将结果放入所得切片中。
现在，我们可以使用位图和函数来响应搜索查询。
即使功能非常简单，性能也不是很高，并且我们保存了一个事实，即每次调用该函数时都没有返回新的结果切片。
在使用pprof进行了简要介绍之后，我注意到Go编译器错过了一个非常简单但非常重要的优化：函数内联。
事实是，Go编译器非常害怕通过切片的循环，并明确拒绝内联包含循环的函数。
但是我并不害怕，并且可以像过去那样使用goto而不是循环来欺骗编译器。
而且，如您所见，现在编译器愉快地内联了我们的函数！ 结果，我们设法节省了大约2微秒。 还不错！
如果仔细查看汇编器输出，很容易看到第二个瓶颈。 编译器在我们最热的循环中添加了切片边界检查。 事实是Go是一种安全的语言，编译器担心我的三个参数（三个切片）的大小不同。 毕竟，理论上可能会出现所谓的缓冲区溢出。
让我们向编译器展示所有切片的大小都是相同的，以使编译器放心。 我们可以通过在函数的开头添加一个简单的检查来做到这一点。
看到这一点，编译器愉快地跳过了测试，最终又节省了500纳秒。
大批量
好的，我们设法从简单的实现中压缩了一些性能，但是，实际上，这个结果比使用当前硬件可能的要差得多。
我们所做的只是基本的位操作，而我们的处理器则非常高效地执行它们。 但是，不幸的是，我们将非常小的工作“喂”给了处理器。 我们的函数逐字节执行操作。 我们可以很容易地调整代码，以便使用UInt64 slices处理8字节的块。
如您所见，由于批次增加了8倍，因此这种小的更改使我们的程序加速了8倍。 增益可以说是线性的。
汇编程序实施
但这还不是终点。 我们的处理器可以处理16、32甚至64个字节的片段。 这样的“宽”操作称为单指令多数据（SIMD；一个指令，很多数据），对代码进行转换以使其使用此类操作的过程称为矢量化。
不幸的是，Go编译器远非矢量化方面的优秀学生。 当前，在Go上向量化代码的唯一方法是使用Go汇编器手动进行和放置这些操作。
汇编器围棋是一种奇怪的野兽。 您可能知道汇编程序与要编写的计算机的体系结构紧密相关，但是Go并非如此。 Go汇编器更像是IRL（中间表示语言）或中间语言：实际上与平台无关。 几年前，罗伯·派克（Rob Pike）在丹佛的GopherCon
上就这个主题做了精彩的
演讲 。
此外，Go使用了与众不同的Plan 9格式，该格式与公认的AT＆T和Intel格式不同。
可以肯定地说，手动编写Go汇编器并不是最有趣的活动。
但是，幸运的是，已经有两个帮助我们编写Go汇编程序的高级工具：PeachPy和avo。 这两个实用程序分别从用Python和Go编写的高级代码生成Go汇编程序。
这些实用程序简化了寄存器分配，写入周期之类的事情，并且通常简化了进入Go中汇编程序编程世界的过程。
我们将使用avo，因此我们的程序将几乎是普通的Go程序。
这就是avo程序最简单的示例。 我们有一个main（）函数，该函数在其内部定义了Add（）函数，其含义是将两个数字相加。 有一些辅助功能，用于按名称获取参数并获取免费的合适的处理器寄存器之一。 如ADDQ所示，每个处理器操作在avo上都有相应的功能。 最后，我们看到一个辅助函数来存储结果值。
通过调用go generate，我们将在avo上执行该程序，最后将生成两个文件：
- 用生成的Go汇编代码添加.s；
- stub.go，带有用于连接两个世界的函数头：Go和assembler。
既然我们已经了解了avo的功能和方式，那么让我们看一下我们的功能。 我实现了函数的标量和向量（SIMD）版本。
首先，查看标量版本。
与前面的示例一样，我们要求您向我们提供一个免费且正确的通用寄存器，我们不需要计算参数的偏移量和大小。 所有这些avo都为我们做。
之前我们使用标签和goto（或跳转）来提高性能并欺骗Go编译器，但是现在我们从一开始就这样做。 事实是循环是一个更高层次的概念。 在汇编器中，我们只有标签和跳转。
其余的代码应该已经熟悉并且可以理解。 我们使用标签和跳转来模拟循环，从两个片中获取一小部分数据，然后通过位运算将它们组合在一起（在这种情况下，则为AND，然后将结果放入结果片中）。 仅此而已。
这就是最终的汇编代码。 我们不需要计算偏移量和大小（以绿色突出显示）或跟踪使用的寄存器（以红色突出显示）。
如果将汇编程序中实现的性能与Go中最佳实现的性能进行比较，我们将发现相同。 这是可以预期的。 毕竟，我们没有做任何特别的事情-我们只是复制了Go编译器会做的事情。
不幸的是，我们不能强迫编译器内联用汇编器编写的函数。 Go编译器今天没有此功能，尽管添加它的请求已经存在了一段时间。
这就是为什么无法从汇编程序中的小功能中获得任何好处的原因。 我们需要编写大型函数，或者使用新的math / bits包，或者绕过汇编器。
现在让我们看一下函数的向量版本。
在此示例中，我决定使用AVX2，因此我们将使用适用于32字节块的操作。 代码结构与标量选项非常相似：加载参数，请向我们提供免费的通用寄存器等。
创新之一是较宽的向量运算使用特殊的较宽寄存器。 对于32字节的块，它们是带有前缀Y的寄存器。这就是为什么在代码中看到YMM（）函数的原因。 如果我将AVX-512与64位块一起使用，则前缀为Z。
第二个创新是我决定使用一种称为循环展开的优化，即在跳到循环开始之前手动执行八个循环操作。 这种优化减少了代码中的早午餐（分支）数量，并且受到可用空闲寄存器数量的限制。
那么，性能如何？ 她很美！ 与Go上的最佳解决方案相比，我们获得了大约七倍的加速。 令人印象深刻，是吗？
但是，甚至可以通过为查询计划程序使用AVX-512，预取或JIT（即时编译器）来加速实现。 但这当然是单独报告的主题。
位图索引问题
既然我们已经研究了Go位图索引的简单实现和效率更高的汇编语言，那么让我们最后谈谈为什么很少使用位图索引。
在旧的科学论文中，提到了位图索引的三个问题，但是在较新的科学论文中，我认为它们不再相关。 我们不会深入研究这些问题中的每一个，但是我们将肤浅地考虑它们。
基数大的问题
因此，我们被告知位图索引仅适用于基数较低的字段，即值很少的字段（例如，性别或眼睛的颜色），原因是这些字段的通常表示形式（每个值一位）如果基数很大，它将占用太多空间，此外，这些位图索引将被弱（很少）填充。
, , . . . , — .
, , , roaring . — , bit runs — , .
roaring . , Go.
, , (binning). , , . — , , , . 185,2 185,3 .
, 1 .
, 50 250 , , , 200 .
, .
bitmap- , .
, . , . , , — lock contention, .
.
— . bitmap- , . lock contention.
— . , , — . - (, 100 500 ) . , , .
: .
bitmap- , , , , « ».
, , AND, OR . . - « 200 300 ».
OR.
. , 50 . 50 .
, . range-encoded bitmaps.
- (, 200), , . 200 . 300: 300 . 依此类推。
, , . , 300 , , 199 . 做完了
, bitmap-. , , . , S2 Google. , . « » ( ).
现成的解决方案
. - - , , .
, , bitmap- . , SIMD, .
, , .
Roaring
-, roaring bitmaps-, . , , bitmap-.
, Go- SIMD, , Go- , C, .
Pilosa
, , — Pilosa, , , bitmap- . , .
Pilosa roaring , , : , range-encoded bitmaps, . .
Pilosa .
, . Pilosa, , , , .
NOT «expensive», ( AND-) «terrace» «reservations». , .
, MySQL PostgreSQL — bitmap-.
结论
如果您还没有入睡，谢谢。 由于时间有限，我不得不顺便谈谈许多主题，但我希望该报告是有用的，甚至可以起到激励作用。
即使您现在不需要位图索引，也很高兴知道。 让它们成为您抽屉中的另一个工具。
您和我研究了Go的各种性能技巧，以及到目前为止Go编译器不能很好完成的事情。 但是，每个Go程序员都必须了解它。
这就是我想说的。 谢谢你