开场白
我在莫斯科举行的 GopherCon Russia 2019 会议上用英语发表了这份报告，并在下诺夫哥罗德的一次聚会上用俄语发表了这份报告。 我们正在谈论位图索引 - 不像 B 树那么常见，但同样有趣。 分享 会议上的演讲为英文，文字记录为俄文。
我们将看看位图索引是如何工作的，什么时候比其他索引更好，什么时候比其他索引差，以及在什么情况下它比其他索引快得多； 让我们看看哪些流行的 DBMS 已经有了位图索引； 让我们尝试用 Go 编写自己的代码。 “作为甜点”，我们将使用现成的库来创建我们自己的超快速专业数据库。
我真心希望我的作品对您有用且有趣。 去！
介绍
大家好！ 现在是晚上六点，我们都累极了。 是时候谈论无聊的数据库索引理论了，对吧？ 别担心，我到处都会有几行源代码。 🙂
抛开所有笑话不谈，这份报告充满了信息，而我们的时间不多了。 那么让我们开始吧。
今天我主要讲以下内容：
- 什么是索引；
- 什么是位图索引；
- 哪里使用了它，哪里没有使用它，以及为什么；
- Go 中的简单实现和编译器的一些麻烦；
- Go 汇编器中的实现稍微不那么简单，但效率更高；
- 位图索引的“问题”；
- 现有的实施。
那么什么是索引呢？
索引是我们除了主数据之外维护和更新的一个单独的数据结构。 它用于加快搜索速度。 如果没有索引，搜索将需要完全遍历数据（这个过程称为全扫描），并且这个过程具有线性算法复杂度。 但数据库通常包含大量数据，线性复杂度太慢。 理想情况下，我们会得到一个对数或常数。
这是一个非常复杂的主题，充满了微妙之处和权衡，但在回顾了数十年的数据库开发和研究之后，我愿意说只有几种广泛使用的方法来创建数据库索引。
第一种方法是分层缩小搜索空间，将搜索空间划分为更小的部分。
我们通常使用不同种类的树木来做到这一点。 一个例子是你衣柜里的一大盒材料，其中包含分为不同主题的小盒材料。 如果您需要材料，您可能会在一个写着“材料”而不是写着“Cookies”的盒子里寻找它们，对吧？
第二种方法是立即选择所需的元素或元素组。 我们在哈希映射或反向索引中执行此操作。 使用哈希映射与前面的示例非常相似，但你的衣柜里不是一盒盒子，而是一堆装最终物品的小盒子。
第三种方法是消除搜索的需要。 我们使用布隆过滤器或布谷鸟过滤器来做到这一点。 第一个会立即给出答案，使您无需搜索。
最后一种方法是充分利用现代硬件赋予我们的所有能力。 这正是我们在位图索引中所做的。 是的，在使用它们时，我们有时需要遍历整个索引，但我们做得非常高效。
正如我所说，数据库索引的主题非常广泛并且充满了妥协。 这意味着有时我们可以同时使用多种方法：如果我们需要进一步加快搜索速度，或者如果我们需要覆盖所有可能的搜索类型。
今天我将讨论其中最不为人所知的方法 - 位图索引。
我是谁来谈论这个话题？
我在 Badoo 担任团队负责人（也许您更熟悉我们的其他产品 Bumble）。 我们已经在全球拥有超过 400 亿用户，并拥有许多为他们选择最佳匹配的功能。 我们使用自定义服务（包括位图索引）来做到这一点。
那么什么是位图索引呢？
位图索引，顾名思义，使用位图或位集来实现搜索索引。 从鸟瞰角度来看，该索引由一个或多个代表任何实体（例如人）及其属性或参数（年龄、眼睛颜色等）的位图以及使用位运算（AND、OR、NOT）的算法组成。 ）来回答搜索查询。
我们被告知，位图索引最适合并且非常适合那些将多个低基数列中的查询组合起来的搜索（例如“眼睛颜色”或“婚姻状况”与“距市中心的距离”之类的内容）。 但稍后我将证明它们也适用于高基数列。
让我们看一下位图索引的最简单示例。
想象一下，我们有一个莫斯科餐厅列表，其二元属性如下：
- 靠近地铁；
- 有私人停车场；
- 有一个阳台（有露台）；
- 您可以预订餐桌（接受预订）；
- 适合素食者（素食主义者友好）；
- 昂贵（昂贵）。
让我们为每个餐厅指定一个从 0 开始的序列号，并为 6 个位图分配内存（每个特征一个）。 然后，我们将根据餐厅是否具有此属性来填充这些位图。 如果餐厅 4 有阳台，则“有阳台”位图中的第 4 位将设置为 1（如果没有阳台，则设置为 0）。
现在我们有了最简单的位图索引，我们可以用它来回答如下查询：
- “显示素食餐厅”；
- “给我看看带阳台的便宜餐厅，你可以在那里预订餐桌。”
如何？ 我们来看看吧。 第一个请求非常简单。 我们需要做的就是获取“素食友好”位图并将其转换为暴露位图的餐馆列表。
第二个请求稍微复杂一些。 我们需要在“昂贵”位图上使用 NOT 位图来获取便宜餐馆的列表，然后将其与“我可以预订餐桌”位图进行 AND 运算，并将结果与“有一个阳台”位图进行 AND 运算。 生成的位图将包含满足我们所有标准的机构列表。 在此示例中，这只是 Yunost 餐厅。
其中涉及很多理论，但不用担心，我们很快就会看到代码。
位图索引用在哪里？
如果您 Google 位图索引，90% 的答案都会以某种方式与 Oracle DB 相关。 但其他 DBMS 可能也支持这样一个很酷的东西，对吧？ 并不真地。
让我们来看看主要嫌疑人名单。
MySQL尚不支持位图索引，但有一个提案建议添加此选项（).
PostgreSQL 不支持位图索引，但使用简单的位图和位操作来组合跨多个其他索引的搜索结果。
Tarantool 具有位集索引并支持对其进行简单搜索。
Redis 有简单的位域）而无法搜索它们。
MongoDB还不支持位图索引，但是也有一个Proposal建议添加这个选项
Elasticsearch 在内部使用位图).
- 但是我们家出现了一位新邻居：皮洛萨。 这是一个用 Go 编写的新的非关系数据库。 它仅包含位图索引并以它们为基础。 我们稍后再讨论。
Go 中的实现
但为什么位图索引很少被使用呢？ 在回答这个问题之前，我想向您展示如何在 Go 中实现一个非常简单的位图索引。
位图本质上只是数据片段。 在 Go 中，我们使用字节切片来实现这一点。
对于一个餐厅特征，我们有一个位图，位图中的每一位表示特定餐厅是否具有该属性。
我们需要两个辅助函数。 其中一个将用于用随机数据填充我们的位图。 随机的，但餐厅有一定的概率拥有每个属性。 例如，我相信莫斯科很少有不能订座的餐馆，而且在我看来，大约有20%的餐馆适合素食者。
第二个函数会将位图转换为餐馆列表。
为了回答“显示有露台且可以预订的便宜餐馆”这一查询，我们需要两个位运算：NOT 和 AND。
我们可以通过使用更复杂的 AND NOT 运算符来稍微简化我们的代码。
我们为每个操作都有函数。 它们都遍历切片，从每个切片中取出相应的元素，通过位运算将它们组合起来，并将结果放入结果切片中。
现在我们可以使用位图和函数来回答搜索查询。
尽管函数非常简单，但性能并没有那么高，而且我们通过在每次调用函数时不返回新的结果切片来节省大量资金。
使用 pprof 进行一些分析后，我注意到 Go 编译器缺少一个非常简单但非常重要的优化：函数内联。
事实上，Go 编译器非常害怕通过切片的循环，并且断然拒绝内联包含此类循环的函数。
但我并不害怕，我可以通过使用 goto 而不是循环来欺骗编译器，就像过去的美好时光一样。
而且，正如您所看到的，现在编译器将愉快地内联我们的函数！ 结果，我们设法节省了大约 2 微秒。 不错！
如果仔细观察汇编输出，第二个瓶颈很容易看出。 编译器在我们最热的循环内添加了切片边界检查。 事实上，Go 是一种安全语言，编译器担心我的三个参数（三个切片）的大小不同。 毕竟，那么理论上就会存在发生所谓缓冲区溢出的可能性。
让我们通过向编译器显示所有切片的大小相同来让编译器放心。 我们可以通过在函数的开头添加一个简单的检查来做到这一点。
看到这一点，编译器很高兴地跳过了检查，最终我们又节省了 500 纳秒。
大佬们
好吧，我们设法从简单的实现中挤出一些性能，但这个结果实际上比当前硬件可能的结果要差得多。
我们所做的只是基本的位操作，并且我们的处理器非常高效地执行这些操作。 但不幸的是，我们用非常小的工作片段“喂养”我们的处理器。 我们的函数逐字节执行操作。 我们可以非常轻松地调整代码以使用 UInt8 切片来处理 64 字节块。
正如您所看到的，这个小变化通过将批量大小增加了八倍，使我们的程序速度提高了八倍。 增益可以说是线性的。
汇编程序中的实现
但这还没有结束。 我们的处理器可以处理 16、32 甚至 64 字节的块。 这种“广泛”操作称为单指令多数据（SIMD；一条指令，许多数据），而转换代码以使其使用此类操作的过程称为矢量化。
不幸的是，Go 编译器在矢量化方面远非出色。 目前，矢量化 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() 函数，其含义是将两个数字相加。 这里有一些辅助函数可以按名称获取参数并获取空闲且合适的处理器寄存器之一。 每个处理器操作在 avo 上都有一个对应的函数，如 ADDQ 中所示。 最后，我们看到一个用于存储结果值的辅助函数。
通过调用gogenerate，我们将在avo上执行程序，结果会生成两个文件：
- add.s 以及 Go 汇编器中的结果代码；
- Stub.go 带有函数头来连接两个世界：Go 和汇编器。
现在我们已经了解了 avo 的作用和作用，让我们看看我们的函数。 我实现了函数的标量和向量 (SIMD) 版本。
让我们首先看看标量版本。
与前面的示例一样，我们要求一个免费且有效的通用寄存器，我们不需要计算参数的偏移量和大小。 avo 为我们做了这一切。
我们曾经使用标签和 goto（或跳转）来提高性能并欺骗 Go 编译器，但现在我们从一开始就这样做。 重点是周期是一个更高层次的概念。 在汇编程序中，我们只有标签和跳转。
其余的代码应该已经熟悉并且可以理解。 我们模拟一个带有标签和跳转的循环，从两个切片中取出一小段数据，将它们与位操作组合起来（在本例中为 AND NOT），然后将结果放入结果切片中。 全部。
这就是最终的汇编代码的样子。 我们不必计算偏移量和大小（以绿色突出显示）或跟踪所使用的寄存器（以红色突出显示）。
如果我们将汇编语言实现的性能与 Go 中最佳实现的性能进行比较，我们会发现它们是相同的。 这是预期的。 毕竟，我们没有做任何特别的事情——我们只是重现了 Go 编译器会做的事情。
不幸的是，我们不能强制编译器内联用汇编语言编写的函数。 Go 编译器目前还没有这样的功能，尽管很长一段时间以来一直有人要求添加它。
这就是为什么不可能从汇编语言中的小函数中获得任何好处。 我们需要编写大型函数，或者使用新的 math/bits 包，或者绕过汇编语言。
现在让我们看看函数的向量版本。
对于此示例，我决定使用 AVX2，因此我们将使用对 32 字节块进行操作的操作。 代码的结构与标量版本非常相似：加载参数、请求空闲的共享寄存器等。
一项创新是更广泛的向量运算使用特殊的宽寄存器。 对于 32 字节块，这些寄存器是以 Y 为前缀的。这就是您在代码中看到 YMM() 函数的原因。 如果我将 AVX-512 与 64 位块一起使用，则前缀将为 Z。
第二个创新是我决定使用一种称为循环展开的优化，这意味着在跳转到循环开头之前手动执行八次循环操作。 这种优化减少了代码中的分支数量，并受到可用空闲寄存器数量的限制。
那么，性能呢？ 她很漂亮！ 与最佳 Go 解决方案相比，我们实现了约七倍的加速。 令人印象深刻，对吧？
但即使是这种实现也可以通过使用 AVX-512、预取或查询调度程序的 JIT（即时编译器）来加速。 但这肯定是一个单独报告的主题。
位图索引的问题
现在我们已经了解了 Go 中位图索引的简单实现以及汇编语言中更高效的实现，最后让我们谈谈为什么位图索引很少使用。
较旧的论文提到了位图索引的三个问题，但较新的论文和我认为它们不再相关。 我们不会深入探讨每个问题，而是会从表面上看待它们。
高基数问题
所以，我们被告知位图索引只适用于基数较低的字段，即那些值很少的字段（例如，性别或眼睛颜色），原因是此类字段的通常表示形式（一个每个值位）在高基数的情况下，它将占用太多空间，而且，这些位图索引将很难（很少）填充。
有时我们可能会使用不同的表示形式，例如我们用来表示数字的标准表示形式。 但压缩算法的出现改变了一切。 在过去的几十年里，科学家和研究人员提出了大量的位图压缩算法。 它们的主要优点是不需要解压缩位图来执行位操作——我们可以直接对压缩位图执行位操作。
最近，混合方法开始出现，例如咆哮位图。 他们同时使用三种不同的位图表示形式 - 位图本身、数组和所谓的位运行 - 并在它们之间进行平衡，以最大限度地提高性能并最大限度地减少内存消耗。
您可以在最流行的应用程序中找到咆哮的位图。 各种编程语言已经有大量的实现，其中包括超过三种的 Go 实现。
另一种可以帮助我们处理高基数的方法称为分箱。 想象一下，您有一个代表人身高的字段。 高度是一个浮点数，但我们人类并不这么认为。 对于我们来说，身高185,2厘米和185,3厘米没有区别。
事实证明，我们可以将相似的值分成1厘米以内的组。
如果我们还知道很少有人身高低于 50 厘米和高于 250 厘米，那么我们基本上可以将具有无限基数的字段转变为基数约为 200 个值的字段。
当然，如果有必要，我们可以事后进行额外的过滤。
高带宽问题
位图索引的下一个问题是更新它们的成本可能非常高。
数据库必须能够在可能有数百个其他查询正在搜索数据的同时更新数据。 我们需要锁来避免并发数据访问或其他共享问题。 凡是有一个大锁的地方，就会出现一个问题——锁争用，当这个锁成为瓶颈时。
这个问题可以通过使用分片或版本索引来解决或规避。
分片是一件简单且众所周知的事情。 您可以像对任何其他数据一样对位图索引进行分片。 您将获得一堆小锁，而不是一个大锁，从而消除锁争用。
解决该问题的第二种方法是使用版本化索引。 您可以拥有一份用于搜索或阅读的索引副本，以及一份用于写入或更新的索引副本。 并且在某个时间段内（例如，每 100 毫秒或 500 毫秒一次）复制它们并交换它们。 当然，这种方法仅适用于您的应用程序可以处理稍微滞后的搜索索引的情况。
这两种方法可以同时使用：您可以拥有分片版本索引。
更复杂的查询
位图索引的最后一个问题是，我们被告知它们不太适合更复杂类型的查询，例如跨度查询。
事实上，如果你想一想，像 AND、OR 等位运算不太适合“显示房价在每晚 200 到 300 美元之间的酒店”这样的查询。
一个幼稚且非常不明智的解决方案是获取每个美元值的结果，并通过按位“或”运算将它们组合起来。
更好的解决方案是使用分组。 例如，50 美元为一组。 这将使我们的进程加快 50 倍。
但通过使用专门为此类请求创建的视图也可以轻松解决该问题。 在科学论文中，它被称为范围编码位图。
在这种表示中，我们不仅仅为某个值（例如 200）设置一位，而是将该值和所有值设置得更高。 200及以上。 300 相同：300 及以上。 等等。
使用这种表示形式，我们只需遍历索引两次即可回答此类搜索查询。 首先，我们将获得房间费用低于或 300 美元的酒店列表，然后我们将从其中删除房间费用低于或 199 美元的酒店。 准备好。
您会感到惊讶，但即使是地理查询也可以使用位图索引。 诀窍是使用用几何图形围绕坐标的几何表示。 例如，Google 的 S2。 该图形应该能够以三个或更多可编号的相交线的形式表示。 这样我们就可以将地理查询变成“沿着间隙”（沿着这些编号线）的多个查询。
就绪解决方案
我希望我对您有点感兴趣，现在您的武器库中又多了一个有用的工具。 如果您需要做这样的事情，您就会知道该往哪个方向看。
然而，并不是每个人都有时间、耐心或资源从头开始创建位图索引。 尤其是更先进的技术，例如使用 SIMD。
幸运的是，有几个现成的解决方案可以帮助您。
咆哮的位图
首先，还有我已经讨论过的相同的咆哮位图库。 它包含创建成熟的位图索引所需的所有必要容器和位操作。
不幸的是，目前没有一个 Go 实现使用 SIMD，这意味着 Go 实现的性能低于 C 实现等。
皮洛萨
另一个可以帮助您的产品是 Pilosa DBMS，实际上它只有位图索引。 这是一个相对较新的解决方案，但它正在迅速赢得人心。
Pilosa 在内部使用咆哮位图，并让您能够使用它们，简化并解释了我上面谈到的所有内容：分组、范围编码位图、字段的概念等。
让我们快速看一下使用 Pilosa 回答您已经熟悉的问题的示例。
该示例与您之前看到的非常相似。 我们创建 Pilosa 服务器的客户端，创建索引和必要的字段，然后用带有概率的随机数据填充字段，最后执行熟悉的查询。
之后，我们对“昂贵”字段使用 NOT，然后将结果（或 AND）与“露台”字段和“预订”字段相交。 最后，我们得到最终结果。
我真的希望在可预见的将来这种新型索引也将出现在像MySQL和PostgreSQL这样的DBMS中——位图索引。
结论
如果你还没睡的话，谢谢。 由于时间有限，我不得不简要讨论许多主题，但我希望这次演讲有用，甚至可能具有激励性。
位图索引很有必要了解一下，即使您现在不需要它们。 让它们成为您工具箱中的另一个工具。
我们研究了 Go 的各种性能技巧以及 Go 编译器还不能很好处理的事情。 但这对于每个 Go 程序员来说绝对有用。
这就是我想告诉你的。 谢谢你！
来源： habr.com