使用 GIN 索引位串

Question

我正在尝试将 PostgreSQL 扩展为索引位串最多 1000 位。（这些位串是通过量化高维向量创建的，因此每个维度最多分配 4 位）。插入很少见，而搜索是最常用的操作。在搜索中，我想获取与位字符串完全匹配的所有行。

对于 GIN 来说，这看起来是一个完美的工作（结合我自己的数据类型），或者你怎么看？

Answer 1

在搜索中，我想获取与位字符串完全匹配的所有行。

使用 B 树索引，默认类型。我在这里没有看到 GIN 索引的案例。

最多 1000 位会导致bit varying类型的磁盘上最多 133 个字节（或稍多）的存储大小。

SELECT pg_column_size(repeat('1', 1000)::varbit)  -- 133

没那么多。一个普通的 B 树索引应该可以。但也许列足够大，以下技巧可以提高性能。

如果位串列的一小部分足够独特，可以将您的搜索范围缩小到很少的命中，那么表达式上的索引 可能会给您带来更好的性能，因为较小的索引可以放入 RAM 中并且处理速度更快。不要为小桌子烦恼，开销会吃掉好处。但是对于大桌子可能会有很大的不同。

例子

给定表：

CREATE TABLE tbl(id serial PRIMARY KEY, b_col varbit);

如果前 10 位足以将搜索范围缩小到几个命中，您可以在表达式上 创建索引b_col::bit(10)。强制转换将bin(n)截断bitstring为 n 位。

CREATE INDEX tbl_b_col10_idx ON tbl ((b_col::bit(10)))

索引定义中的强制转换运算符需要额外的括号。看：

• 如何在 postgres 中的整数 json 属性上创建索引

然后，而不是查询

SELECT * FROM tbl WHERE b_col = '1111011110111101'::varbit; -- 16 bit

你会使用：

SELECT *
FROM   tbl
WHERE  b_col::bit(10) = '1111011110111101'::bit(10) -- utilize index
AND    b_col = '1111011110111101'::varbit;  -- filter to exact match

请注意，当转换为 时，较短的值会0在右侧（最低有效位）填充's bit(n)。

在现实世界的应用程序中，这对于几百个位开始变得有意义。测试转折点。

进一步优化

由于大多数安装使用MAXALIGN8 字节（64 位操作系统）（更多详细信息在这里），因此对于不超过 8 字节的任何数据，您的索引大小是相同的。实际上，每行：

 4 字节项目标识符
 索引元组标头为 8 个字节（或堆元组为 23 + 1 个字节）
 ? 数据的实际空间
 ? 填充到最接近的 8 个字节的倍数

加上每页和索引/表的一些小开销。手册或有关 SO 的相关答案中的详细信息。

因此，您应该能够进一步优化上述方法。取第一个64 位（或最后一个或任何对您最有特色且最适合您的），将其转换为bigint并在此表达式上建立索引。

CREATE INDEX tbl_b_col64_idx ON tbl ((b_col::bit(64)::bigint))

我投了两次 ( b_col::bit(64)::bigint) 因为在varbit和之间没有定义投bigint。此相关答案中的详细信息：

• 将文本表示中的十六进制转换为十进制数

实际上，这只是一个非常快速和简单的散列函数，其中散列值还允许查找值的范围。根据确切的要求，您可以更进一步并使用任何 IMMUTABLE散列函数，例如md5(). 上面链接的答案中的详细信息。

随之而来的查询：

SELECT *
FROM   tbl
WHERE  b_col::bit(64)::bigint = '1111011110111101'::bit(64)::bigint -- utilize index
AND    b_col = '1111011110111101'::varbit;  -- narrow down to exact match

结果索引应该与第一个示例中的索引一样大，但出于以下三个原因，查询应该快得多：

• 索引通常返回多少命中（64位的信息对10位）

• Postgres 可以使用整数运算，即使对于普通运算，它也应该更快=。（没有测试来验证这一点。）

• 该类型integer没有像varbit- 5 或 8 个字节那样的开销。（在我的安装中，最多960 位为 5 个字节，更多为 8 个字节）。
  有效地，为了将索引保持在其最小大小，您只能将24 位打包到varbit索引中 - 与索引的64 位信息相比bigint。

CLUSTER

在这种情况下CLUSTER应该提高性能：

CLUSTER TABLE tbl USING tbl_b_col10_idx;

这是一种一次性操作，必须在您的设计间隔内重复进行。如果您想使用它，请务必阅读手册CLUSTER。或者考虑替代pg_repack。细节：

• 为读取性能配置 PostgreSQL

如果您的值的前 64 位CLUSTER在大多数情况下都是唯一的，则几乎没有帮助，因为在大多数情况下索引扫描将返回单行。如果没有，CLUSTER将有很大帮助。因此，对于具有较少优化索引的第一个示例，效果将大得多。