对大量重复值使用什么索引？

Question

让我们做几个假设：

我有一个看起来像这样的表：

 a | b
---+---
 a | -1
 a | 17
  ...
 a | 21
 c | 17
 c | -3
  ...
 c | 22

关于我的套装的事实：

• 整个表的大小是 ~ 10 ¹⁰行。

• 我有 ~ 100k 行，列中有值a，a其他值类似（例如c）。

• 这意味着在“a”列中有大约 100k 个不同的值。

• 我的大多数查询都会读取 a 中给定值的全部或大部分值，例如select sum(b) from t where a = 'c'.

• 该表的编写方式使得连续值在物理上接近（要么按顺序写入，要么我们假设CLUSTER已在该表和列上使用a）。

• 该表很少更新，我们只关心读取速度。

• 该表相对较窄（比如每个元组约 25 个字节，+ 23 个字节的开销）。

现在的问题是，我应该使用什么样的索引？我的理解是：

• BTree我的问题是 BTree 索引会很大，因为据我所知它会存储重复值（它必须这样做，因为它不能假设表是物理排序的）。如果 BTree 很大，我最终不得不读取索引和索引指向的表部分。（我们可以使用fillfactor = 100来稍微减小索引的大小。）

• BRIN我的理解是，我可以在这里有一个小的索引，但代价是阅读无用的页面。使用小pages_per_range意味着索引更大（这是 BRIN 的一个问题，因为我需要读取整个索引），使用大pages_per_range意味着我将读取很多无用的页面。是否有一个神奇的公式可以找到pages_per_range考虑到这些权衡的良好价值？

• GIN/GiST不确定这些在这里是否相关，因为它们主要用于全文搜索，但我也听说它们擅长处理重复键。aGIN或GiSTindex 在这里有帮助吗？

另一个问题是，Postgres 是否会CLUSTER在查询规划器中使用表被编辑（假设没有更新）的事实（例如通过二进制搜索相关的开始/结束页面）？有点相关，我可以将所有列存储在 BTree 中并完全删除表（或实现等效的东西，我相信这些是 SQL Server 中的聚集索引）？是否有一些混合 BTree/BRIN 索引可以帮助这里？

我宁愿避免使用数组来存储我的值，因为我的查询以这种方式最终会降低可读性（我知道这会通过减少元组的数量来降低每个元组 23 个字节的开销）。

Answer 1

树

我的问题是 BTree 索引会很大，因为它会存储重复值（它也有，因为它不能假设表是物理排序的）。如果 BTree 很大，我最终不得不同时读取索引和索引指向的表部分......

不一定——拥有一个“覆盖”的 btree 索引将是最快的读取时间，如果这就是你想要的（即如果你能负担得起额外的存储空间），那么它是你最好的选择。

布林

我的理解是，我可以在这里有一个小的索引，但代价是阅读无用的页面。使用小pages_per_range意味着索引更大（这是 BRIN 的一个问题，因为我需要读取整个索引），使用大pages_per_range意味着我将读取很多无用的页面。

如果你负担不起覆盖 btree 索引的存储开销，BRIN 是你的理想选择，因为你已经有了集群（这对于 BRIN 有用是至关重要的）。BRIN 索引很小，因此如果您选择合适的 值，所有页面都可能在内存中pages_per_range。

是否有一个神奇的公式可以找到考虑到这些权衡的 pages_per_range 的良好值？

没有神奇的公式，但从pages_per_range 略小于平均值占用的平均大小（以页为单位）开始a。对于典型查询，您可能正在尝试最小化：（扫描的 BRIN 页数）+（扫描的堆页数）。Heap Blocks: lossy=n在执行计划中查找 forpages_per_range=1并与其他值进行比较pages_per_range— 即查看有多少不必要的堆块被扫描。

杜松子酒/吉斯特

不确定这些在这里是否相关，因为它们主要用于全文搜索，但我也听说它们擅长处理重复键。GIN/GiST索引在这里有帮助吗？

GIN 可能值得考虑，但可能不是 GiST——但是如果自然聚类真的很好，那么 BRIN 可能是更好的选择。

这是虚拟数据的不同索引类型之间的示例比较，有点像您的：

表和索引：

create table foo(a,b,c) as
select *, lpad('',20)
from (select chr(g) a from generate_series(97,122) g) a
     cross join (select generate_series(1,100000) b) b
order by a;
create index foo_btree_covering on foo(a,b);
create index foo_btree on foo(a);
create index foo_gin on foo using gin(a);
create index foo_brin_2 on foo using brin(a) with (pages_per_range=2);
create index foo_brin_4 on foo using brin(a) with (pages_per_range=4);
vacuum analyze;

关系大小：

select relname "name", pg_size_pretty(siz) "size", siz/8192 pages, (select count(*) from foo)*8192/siz "rows/page"
from( select relname, pg_relation_size(C.oid) siz
      from pg_class c join pg_namespace n on n.oid = c.relnamespace
      where nspname = current_schema ) z;

姓名 | 尺寸 | 页 | 行/页
:----------------- | :------ | ----: | --------：
富| 149 MB | 19118 | 135
foo_btree_covering | 56 MB | 7132 | 364
foo_btree | 56 MB | 7132 | 364
foo_gin | 2928 KB | 第366话 7103
foo_brin_2 | 264 KB | 33 | 78787
foo_brin_4 | 136 KB | 17 | 152941

覆盖btree：

explain analyze select sum(b) from foo where a='a';

| 查询计划 |
| :------------------------------------------------- -------------------------------------------------- --------------------------------------------- |
| 合计（成本=3282.57..3282.58行=1宽=8）（实际时间=45.942..45.942行=1循环=1）|
| -> Index Only Scan using foo_btree_covering on foo (cost=0.43..3017.80 rows=105907 width=4) (actual time=0.038..27.286 rows=100000 loops=1) |
| 索引条件：(a = 'a'::text) |
| 堆获取：0 |
| 规划时间：0.099 ms |
| 执行时间：45.968 毫秒 |

普通btree：

drop index foo_btree_covering;
explain analyze select sum(b) from foo where a='a';

| 查询计划 |
| :------------------------------------------------- -------------------------------------------------- ----------------------------- |
| 合计（成本=4064.57..4064.58行=1宽=8）（实际时间=54.242..54.242行=1循环=1）|
| -> 使用 foo_btree 对 foo 进行索引扫描 (cost=0.43..3799.80 rows=105907 width=4) (actual time=0.037..33.084 rows=100000 loops=1) |
| 索引条件：(a = 'a'::text) |
| 规划时间：0.135 ms |
| 执行时间：54.280 毫秒 |

BRIN pages_per_range=4：

drop index foo_btree;
explain analyze select sum(b) from foo where a='a';

| 查询计划 |
| :------------------------------------------------- -------------------------------------------------- ----------------------------- |
| 合计 (cost=21595.38..21595.39 rows=1 width=8) (实际时间=52.455..52.455 rows=1 loops=1) |
| -> Bitmap Heap Scan on foo (cost=888.78..21330.61 rows=105907 width=4) (actual time=2.738..31.967 rows=100000 loops=1) |
| 重新检查条件：(a = 'a'::text) |
| 索引重新检查删除的行：96 |
| 堆块：有损=736 |
| -> foo_brin_4 上的位图索引扫描（cost=0.00..862.30 rows=105907 width=0）（实际时间=2.720..2.720 rows=7360 loops=1）|
| 索引条件：(a = 'a'::text) |
| 规划时间：0.101 ms |
| 执行时间：52.501 毫秒 |

BRIN pages_per_range=2：

drop index foo_brin_4;
explain analyze select sum(b) from foo where a='a';

| 查询计划 |
| :------------------------------------------------- -------------------------------------------------- ----------------------------- |
| 合计 (cost=21659.38..21659.39 rows=1 width=8) (实际时间=53.971..53.971 rows=1 loops=1) |
| -> Bitmap Heap Scan on foo (cost=952.78..21394.61 rows=105907 width=4) (actual time=5.286..33.492 rows=100000 loops=1) |
| 重新检查条件：(a = 'a'::text) |
| 索引重新检查删除的行：96 |
| 堆块：有损=736 |
| -> foo_brin_2 上的位图索引扫描（cost=0.00..926.30 rows=105907 width=0）（实际时间=5.275..5.275 rows=7360 loops=1）|
| 索引条件：(a = 'a'::text) |
| 规划时间：0.095 ms |
| 执行时间：54.016 毫秒 |

杜松子酒：

drop index foo_brin_2;
explain analyze select sum(b) from foo where a='a';

| 查询计划 |
| :------------------------------------------------- -------------------------------------------------- ------------------------------ |
| 合计 (cost=21687.38..21687.39 rows=1 width=8) (实际时间=55.331..55.331 rows=1 loops=1) |
| -> Bitmap Heap Scan on foo (cost=980.78..21422.61 rows=105907 width=4) (actual time=12.377..33.956 rows=100000 loops=1) |
| 重新检查条件：(a = 'a'::text) |
| 堆块：精确=736 |
| -> foo_gin 上的位图索引扫描（cost=0.00..954.30 rows=105907 width=0）（实际时间=12.271..12.271 rows=100000 loops=1）|
| 索引条件：(a = 'a'::text) |
| 规划时间：0.118 ms |
| 执行时间：55.366 毫秒 |

dbfiddle在这里

Answer 2

除了btree和brin似乎是最明智的选择之外，还有一些其他可能值得研究的异国情调的选择 - 它们可能对您的情况有所帮助：

• INCLUDE索引。他们将-希望- Postgres里的下一个主要版本（10），围绕2017年九月的指数某处(a) INCLUDE (b)具有相同的结构上的指标(a)，但包括在叶子页，所有的值b（但无序的）。这意味着您不能将它用于例如SELECT * FROM t WHERE a = 'a' AND b = 2 ;. 可能会使用索引，但虽然(a,b)索引将通过单个查找找到匹配的行，但包含索引将必须通过（在您的情况下可能为 100K）值匹配a = 'a'并检查这些b值。
  另一方面，索引的宽度略小于(a,b)索引，并且您b的查询不需要 order on来计算SUM(b)。你也可以有例如(a) INCLUDE (b,c,d) 它可用于与您的查询类似的在所有 3 列上聚合的查询。

• 过滤（部分）索引。一个起初听起来可能有点疯狂的建议^*：

  CREATE INDEX flt_a  ON t (b) WHERE (a = 'a') ;
  ---
  CREATE INDEX flt_xy ON t (b) WHERE (a = 'xy') ;
  

  每个a值一个索引。在您的情况下，大约有 10 万个索引。虽然这听起来很多，但考虑到每个索引在大小（行数）和宽度（因为它只存储b值）方面都非常小。但在所有其他方面，它（100K 个索引一起）将(a,b)在使用(b)索引空间时充当 b 树索引。
  缺点是您必须自己创建和维护它们，每次将新值a添加到表中时。由于您的表相当稳定，没有很多（或任何）插入/更新，这似乎不是问题。

• 汇总表。由于该表相当稳定，您始终可以使用您需要的最常见聚合（sum(b), sum(c), sum(d), avg(b), count(distinct b)等）创建和填充汇总表。它将很小（只有 100K 行）并且只需要填充一次并且只有在主表上插入/更新/删除行时才更新。

^{*：从这家在其生产系统中运行 1000 万个索引的公司复制的想法：堆：在生产中运行 1000 万个 Postgresql 索引（和计数）。}