PostgreSQL，整数数组，相等索引

Question

我有一个巨大的整数数组列表（300,000,000 条记录）存储在 Postgres 9.2 DB 中。我想有效地搜索这些记录以获得完全匹配（仅相等）。我听说过 intarray 模块和相应的 gist-gin 索引。我想问以下问题：

• PostgreSQL 是否使用哈希函数来检查整数数组的相等性，还是执行一个比较数组元素的蛮力算法？
• 如果 PostgreSQL 使用哈希函数，是否有一些 PostgreSQL 函数代码来实际获取特定数组的哈希函数结果？
• 哪个索引最适合这样的任务？B-tree，还是 intarray 模块提供的 gist - gin 索引？数据集将是静态的，即，一旦插入所有记录，就不会再插入。所以，建立索引/更新索引的时间对我来说并不重要。

Answer 1

问：PostgreSQL 是否使用散列函数来检查整数数组的相等性，还是执行一个比较数组元素的蛮力算法？

不是根据文档中的数组函数和运算符：

数组比较逐个元素比较数组内容，使用元素数据类型的默认 B 树比较函数

没有提到哈希。

intarray提供了其他运算符，但不替换 之间的相等运算符int[]。它公开的最接近的函数_int_same()在语义上是不同的（元素的顺序无关紧要）并且实现为排序+顺序比较，而不是散列。

幸运的是，在 SQL 级别实现基于哈希的快速搜索并不难，在您的情况下（大数组、无更新、完全匹配），它甚至可能是最有效的方法。

脚步：

1）选择一个哈希函数。我建议md5使用数组的文本表示：

create function arr_hash(int[]) returns bytea as
$$ select digest($1::text, 'md5');$$
language sql immutable;

该功能digest(text,text)是pgcrypto扩展的一部分。与md5它相比，它具有为更精简的索引生成二进制（16 字节）而不是十六进制（32 字节）的优势。

2）创建功能索引：

create index index_name on table_name(arr_hash(col_name));

对于您拥有的那种数据集，它会比 GIN 索引快几个数量级（实际上我会担心 GIN 索引的创建会花费非常不合理的时间，但请尝试一下）。

3）像这样使用它：

select 1 from table_name
 where arr_hash(col_name)=arr_hash('{10,20,30,...lot of values}'::int[])
 and   col_name='{10,20,30,...lot of values}'::int[];

Answer 2

1）正如您已经发现的，您不能使用b树，因为索引大小大于页面大小

2）给定：

根据经验，GIN 索引的搜索速度比 GiST 索引快，但构建或更新速度较慢；因此 GIN 更适合静态数据，GiST 更适合经常更新的数据。

你必须使用 GIN。不，GIN 不使用哈希函数，也不使用暴力算法。这是一个反向索引：

GIN 索引存储一组（键，倒排列表）对，其中倒排列表是键出现的一组行 ID。同一行 ID 可以出现在多个发布列表中，因为一项可以包含多个键。每个键值仅存储一次，因此对于相同键出现多次的情况，GIN 索引非常紧凑。

在内部，GIN 索引包含基于键构建的 B 树索引，其中每个键是一个或多个索引项的元素（例如，数组的成员）