Mar*_*ery 4 performance index btree
通常，支持多列 B 树索引的 SQL 数据库还支持按索引中列的子集进行查找，当且仅当它们是索引中的第一列。例如，如果我在列上有一个索引(a, b, c, d)并想执行：
SELECT * FROM my_table
WHERE b = 7 AND a = 'foo';
然后这将使用索引并且速度很快，因为该对(a, b)位于索引的开头，因此数据库可以导航树以查找以('foo', 7, ... ).开头的索引记录。但是，如果我跑
SELECT * FROM my_table
WHERE b = 7 AND c = 'bar';
那么索引将不会被使用*，因为匹配的记录将根据它们在 column 中的值分布在整个索引中a。
* （除了可能通过对索引进行完整或部分扫描，如下面Evan 的回答中所述 - 但由于完整索引扫描仍然具有与完整表扫描相同的时间复杂度，并且部分索引扫描可能也会这样做，这没有多大帮助。）
我有一个包含n列和潜在大量行的表。我还有一个前端 GUI，它允许用户通过这些列的任意组合的精确值进行过滤并查看结果表。这个前端产生的任何查询导致全表扫描得到结果是不可接受的；每个可能的过滤器都必须由索引支持。
对于n列，我需要创建的 B 树索引的最小数量是多少，以确保某个索引覆盖了所有可能的列组合？
假设我的表有4列：a，b，c，和d。然后我的用户可以过滤 15 种不同的列组合：
a b c d
a b c
a b d
a c d
b c d
a b
a c
a d
b c
b d
c d
a
b
c
d
但是，我可以仅使用以下 6 个 B 树索引来支持从这 4 个列的任意子集进行查找：
(a, b, c, d)
(b, c, d)
(c, d, a)
(d, b, a)
(a, c)
(a, d)
为了说明这一点，下面是索引旁边的 15 个可能的子集，可用于通过该子集进行查找：
a b c d (a, b, c, d)
a b c (a, b, c, d)
a b d (d, b, a)
a c d (c, d, a)
b c d (b, c, d)
a b (a, b, c, d)
a c (a, c)
a d (a, d)
b c (b, c, d)
b d (d, b, a)
c d (c, d, a)
a (a, b, c, d)
b (b, c, d)
c (c, d, a)
d (d, b, a)
不过，我不确定如何将这个想法推广到具有大量列的表，或者需要的索引数量如何与n 成比例。因此我的问题是：需要多少索引才能将此方法扩展到n列，我如何确定它们是什么？
（我主要对如何使用 B 树索引支持这些查找的具体理论问题感兴趣 - 但我对其他解决方案持开放态度，例如，如果有一种索引类型比一堆索引类型更好地解决了这个精确问题B 树索引会。）
我需要多少个 B 树索引来支持通过 n 列的任何子集进行查找
至少对于 Oracle (12.x) 和 Postgres，答案是：n
即：每列一个索引。两个 DBMS 都能够为单个查询组合多个索引。在旧版 Oracle 中，您需要在所有列上使用单个位图索引。Oracle 12.1 可以动态执行位图“扫描”（不知道 11.x 中是否已经可以这样做 - 我没有要测试的 11.x 安装）。
测试设置：
create table idx_test (a int, b int, c int, d int, e int);
create index idx_a on idx_test(a);
create index idx_b on idx_test(b);
create index idx_c on idx_test(c);
create index idx_d on idx_test(d);
现在用百万行和每列的随机值填充表。我在 Postgres 中使用：
insert into idx_test (a,b,c,d,e)
select (random() * 10000 + 1)::int,
(random() * 100000 + 1)::int,
(random() * 1000000 + 1)::int,
(random() * 100000 + 1)::int,
(random() * 10000 + 1)::int
from generate_series(1,1000000);
然后将行复制到 Oracle 服务器。
以下查询
select *
from idx_test
where b = 42 or a = 24 or c = 100;
在 Postgres 中显示以下执行计划：
create table idx_test (a int, b int, c int, d int, e int);
create index idx_a on idx_test(a);
create index idx_b on idx_test(b);
create index idx_c on idx_test(c);
create index idx_d on idx_test(d);
可以看到每列都使用了对应的索引。Oracle 12.1 的执行计划几乎相同：
insert into idx_test (a,b,c,d,e)
select (random() * 10000 + 1)::int,
(random() * 100000 + 1)::int,
(random() * 1000000 + 1)::int,
(random() * 100000 + 1)::int,
(random() * 10000 + 1)::int
from generate_series(1,1000000);
只有两列的查询将只使用两个索引：
select *
from idx_test
where a = 1001 and b = 45877;
Postgres：
select *
from idx_test
where b = 42 or a = 24 or c = 100;
和甲骨文：
QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on idx_test (cost=6.25..166.36 rows=111 width=20) (actual time=0.032..0.244 rows=113 loops=1)
Recheck Cond: ((b = 42) OR (a = 24) OR (c = 100))
Heap Blocks: exact=113
-> BitmapOr (cost=6.25..6.25 rows=111 width=0) (actual time=0.020..0.020 rows=0 loops=1)
-> Bitmap Index Scan on idx_test_b_idx (cost=0.00..1.96 rows=11 width=0) (actual time=0.009..0.009 rows=11 loops=1)
Index Cond: (b = 42)
-> Bitmap Index Scan on idx_test_a_idx (cost=0.00..2.27 rows=98 width=0) (actual time=0.007..0.007 rows=100 loops=1)
Index Cond: (a = 24)
-> Bitmap Index Scan on idx_test_c_idx (cost=0.00..1.93 rows=2 width=0) (actual time=0.003..0.003 rows=2 loops=1)
Index Cond: (c = 100)
Planning time: 0.077 ms
Execution time: 0.270 ms
索引也用于OR条件：
select *
from idx_test
where a = 1001 or b = 45877;
Postgres：
PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------------
Plan hash value: 2332290563
--------------------------------------------------------------------------------------
| Id | Operation | Name | E-Rows |E-Bytes| Cost (%CPU)|
--------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 43 | 2795 | 740 (0)|
| 1 | TABLE ACCESS BY INDEX ROWID BATCHED| IDX_TEST | 43 | 2795 | 740 (0)|
| 2 | BITMAP CONVERSION TO ROWIDS | | | | |
| 3 | BITMAP OR | | | | |
| 4 | BITMAP CONVERSION FROM ROWIDS | | | | |
|* 5 | INDEX RANGE SCAN | IDX_C | | | 3 (0)|
| 6 | BITMAP AND | | | | |
| 7 | BITMAP CONVERSION FROM ROWIDS | | | | |
|* 8 | INDEX RANGE SCAN | IDX_A | | | 3 (0)|
| 9 | BITMAP CONVERSION FROM ROWIDS | | | | |
|* 10 | INDEX RANGE SCAN | IDX_B | | | 3 (0)|
--------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
5 - access("C"=100)
8 - access("A"=24)
10 - access("B"=42)
甲骨文：
select *
from idx_test
where a = 1001 and b = 45877;
对 SQL Server 2016 进行的快速测试表明，它的作用基本相同：
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on idx_test (cost=4.48..5.99 rows=1 width=20) (actual time=0.118..0.118 rows=0 loops=1)
Recheck Cond: ((b = 45877) AND (a = 1001))
-> BitmapAnd (cost=4.48..4.48 rows=1 width=0) (actual time=0.117..0.117 rows=0 loops=1)
-> Bitmap Index Scan on idx_test_b_idx (cost=0.00..1.96 rows=11 width=0) (actual time=0.075..0.075 rows=11 loops=1)
Index Cond: (b = 45877)
-> Bitmap Index Scan on idx_test_a_idx (cost=0.00..2.27 rows=98 width=0) (actual time=0.038..0.038 rows=93 loops=1)
Index Cond: (a = 1001)
Planning time: 0.150 ms
Execution time: 0.157 ms
这是最有效的索引访问吗？可能不是，但它很可能是索引开销和查询灵活性之间的最佳折衷。
二。
首先，您按列顺序组合所有组合中的所有字段值。所以你最终会得到 (a,b), (a,c) .. (c,d), (a,b,c), (a,b,d) .. (a,b,c, d). 对这个组合值进行哈希处理。使用哈希作为第一个索引的键。该索引为数据表提供了唯一的代理键。使用该代理来查找数据行。第二个索引位于数据表中的代理键上。
举个例子，假设我的数据表有这些行：
+----+--------+--------+--------+-------+
| id | a | b | c | d |
+----+--------+--------+--------+-------+
| 1 | foo | bar | baz | qux |
| 2 | foo | quux | quuz | corge |
| 3 | wibble | wobble | wubble | flob |
| 4 | blep | blah | boop | blem |
+----+--------+--------+--------+-------+
Table 1: data
请特别注意，第 1 行和第 2 行在“a”列中具有相同的值。
因此，对于行 id 1，我们生成以下哈希值（使用我神奇的哈希函数）：
+--------------+-------------+
| value | hash |
+--------------+-------------+
| foo | 2085198204 |
| bar | 1242944992 |
| .. | |
| foobar | 1242667234 |
| .. | |
| foobarbaz | -1417643972 |
| .. | |
| barbaz | -1478044229 |
| .. | |
| foobarbazqux | 54278474 |
+--------------+-------------+
行 id 2 生成这些哈希值
+------------------+-------------+
| value | hash |
+------------------+-------------+
| foo | 2085198204 |
| quux | -406244122 |
| quuz | -821744750 |
| corge | -4773002 |
| fooquux | -237289772 |
| fooquuz | -1705377365 |
| .. | |
| fooquuxquuzcorge | 174363790 |
+------------------+-------------+
由于第 1 行和第 2 行在“a”列中具有相同的值，因此当该列的值单独进行哈希处理时，它们会生成相同的哈希输出。
我们现在可以用哈希/ ID 映射填充表：
+-------------+----+
| hash | id |
+-------------+----+
| 2085198204 | 1 |
| 1242944992 | 1 |
| 1242667234 | 1 |
| -1417643972 | 1 |
| -1478044229 | 1 |
| 54278474 | 1 |
| 2085198204 | 2 |
| -406244122 | 2 |
| -821744750 | 2 |
| -4773002 | 2 |
| -237289772 | 2 |
| -1705377365 | 2 |
| 174363790 | 2 |
+-------------+----+
Table 2: hash/id map
..加上我之前从示例哈希计算中跳过的其他内容。
现在出现一个查询。谓词是“a=foo”。我们获取该值并对其进行哈希处理，得到 2085198204。我们读取表 2 where hash = 2085198204。我们得到两行：id 1 和 id 2。我们读取表 1where id = 1 or id = 2并获取完整行。
第二个查询到达。它有谓词“c=baz 和 b=bar”。我们对列序列中的值进行排序，得到“barbaz”，其哈希值为-1478044229。读取表 2 中的该哈希值可得出 id 1。
如果值可能出现在多个列中——也许“foo”可能出现在 d 列和 a 列中——上面的简单方案可能会返回误报。对数据行进行二次检查会很麻烦。我认为最好将列包含在哈希中，因此“a=foo”哈希到与“d=foo”不同的值。