位图索引如何有用？

Question

维基百科给出了这个例子

Identifier    Gender         Bitmaps
                              F    M
1           Female            1    0
2           Male              0    1
3           Male              0    1
4           Unspecified       0    0
5           Female            1    0

但我不明白这一点.

• 这首先是一个指数怎么样？在给定密钥的情况下,不应该指向行(使用rowid)的索引吗？
• 这些索引有用的典型查询是什么？它们如何比B树索引更好？我知道如果我们在Gender这里使用B树索引,我们将获得大量结果,例如,我们寻找Gender = Male,需要进一步过滤(因此不是很有用).Bitmap如何改善这种情况？

Answer 1

如果给出上面的示例,则更好地表示位图索引:

Identifier    Gender          RowID
1             Female          R1
2             Male            R2
3             Male            R3
4             Unspecified     R4
5             Female          R5

性别列上的位图索引(概念上)将如下所示:

Gender       R1    R2   R3   R4   R5
Female       1     0    0    0    1
Male         0     1    1    0    0
Unspecified  0     0    0    1    0

当列中的不同值的数量相对较低时使用位图索引(考虑相反的情况,所有值都是唯一的:位图索引将与每一行一样宽,并且长度使它有点像一个大的单位矩阵. )

所以用这个索引就好了

SELECT * FROM table1 WHERE gender = 'Male'

数据库在索引中的性别值中查找匹配项,查找该位设置为1的所有rowid,然后获取表结果.

像这样的查询:

SELECT * FROM table1 WHERE gender IN ('Male', 'Unspecified')

将获得1位为Male,1位为Unspecified,执行按位-OR,然后获取结果位为1的行.

因此,使用位图索引优于ab*树索引的优点是存储(基数低,位图索引非常紧凑),并且能够在解析实际rowid之前执行按位操作,这可能非常快.

请注意,位图索引可能会对插入/删除产生性能影响(概念上,您在位图中添加/删除列并相应地重新调整它...),并且可以创建大量争用,因为行上的更新可以锁定整个相应的位图条目,并且在提交/回滚第一个更新之前,您无法更新不同的行(具有相同的位图值).

Answer 2

在对多列进行过滤时会产生好处,然后在实际选择数据之前,可以将相应的索引与按位运算合并.如果您有性别,eye_colour,hair_colour则查询

select * from persons where
                      gender = 'male' and 
                      (eye_colour = 'blue' or hair_colour = 'blonde')

首先会在eye_colour ['blue']索引和hair_colour ['blonde']索引之间或者在结果和性别['male']索引之间进行逐位或者按位.此操作在计算和I/O方面都执行得非常快.
生成的比特流将用于拾取实际行.

位图索引通常用于数据仓库应用程序中的"星形连接".

Answer 3

正如维基百科文章中所指出的，他们使用按位运算，这比比较整数等数据类型的性能更好，因此简短的回答是提高了查询速度。

从理论上讲，从您的示例中选择所有男性或所有女性应该花费更少的计算和更少的时间。

仅仅考虑它在引擎盖下的工作原理就应该明白为什么这会更快。一个位在逻辑上要么是真要么是假。如果您想使用 WHERE 子句进行查询，这最终将评估记录的真或假，以确定是否将它们包含在您的结果中。

前言 - 其余部分是外行和非技术人员

那么下一个问题是如何评估为真？即使比较数值也意味着计算机必须...

1. 为要评估的值分配内存
2. 为控制值分配内存
3. 为每个分配值（将此视为两个步骤）
4. 比较两者 - 对于数字，这应该很快，但对于字符串，有更多的字节可以比较。
5. 将结果分配给 0（假）或 1（真）值。

如果您使用多部分 where 子句，例如 Where "this = this AND that = that"，请重复

6. 对步骤 5 中生成的结果执行按位运算
7. 得出最终值
8. 释放在步骤 1-3 中分配的内存

但是使用按位逻辑，您只需要查看 0（假）和 1（真）值。消除了比较工作 90% 的开销。