哈希提案

摘要

哈希索引在相等查询中是使用非常广泛的索引。但在 PostgreSQL 中，它的性能不比 B 树好。PostgreSQL 社区以前讨论过这个问题

 http://archives.postgresql.org/pgsql-hackers/2007-09/msg00051.php

本项目试图通过存储哈希值而不是实际键来解决此问题。这是 PostgreSQL TODO 列表中列出的几种提高哈希索引性能的方案之一。这项工作将通过存储哈希值而不是实际键来解决这个问题。然后我提出一个想法来处理该方案的消极方面。我将同时对它们和原始实现和 B 树进行基准测试，以展示改进。

详细说明

• 部分 A. 存储哈希值而不是实际键

已在此处进行了讨论：http://archives.postgresql.org/pgsql-hackers/2004-06/msg00168.php Neil Conway 已发布了一个针对 PostgreSQL 旧版本的补丁。

 http://archives.postgresql.org/pgsql-patches/2005-05/msg00164.php

但它将显著增加跳过具有相同的哈希代码但不完全等于正在查找的键的项目的成本（因为你需要访问堆查找它们是否不相同，从而导致额外的磁盘访问）。

• 部分 B. 第一方案的多样性

我们仍将在存储桶中存储哈希值和元组指针。但在插入元组时，我们可以确定是否存储实际键。如果在插入过程中遇到相同的哈希值，我们将同时存储哈希值和实际键。也就是说，当有很多元组具有相同的哈希代码时，第一个元组只能存储哈希代码，而其他元组将同时存储哈希代码和实际值。

• 部分 C. 基准测试并也许寻找其他提高性能的方法

由于哈希索引的应用领域，基准测试应满足以下条件

 - Workload - All of the queries should be equality queries.
 - Data - The key should be almost unique (i.e. most of the equality queries are point queries instead of multipoint queries). 
          Multipoint queries can only be efficient for cluster file.
 

我将对第一版方案和第二版方案与此前的版本和 B 树索引进行测试，以展示改进之处。

我们还可以在进行基准测试时尝试寻找其他提高性能的方法，并与其他开发人员讨论以进一步改进。

• 部分 D. 备选方案

如果方案效果不佳，我将不得不制定一个备选方案。至少，我认为这样可很好地处理大型索引字段。因此，我会在 Alter Index 中添加一个子句，这样它将在用户有时遇到特殊情况时成为可选项。因此，即使对方案进行最坏的处理，它仍然可在某些情况下使用。