Gsoc08-hashindex

GSoC 提案

项目信息

改进哈希索引性能。 此补丁实现了 ToDo 列表中的项目

• 在哈希索引中，考虑存储哈希值，而不是存储键本身。

想法

补丁中有两个基本想法。

• 在桶中存储哈希值而不是实际键。

我们可以在一个桶中保存更多元组，并减少索引大小。这也意味着所有哈希索引扫描都会变成有损的，并且必须在堆中重新检查。

• 保持每个索引页面的内容按哈希值排序，并在索引扫描期间使用二进制搜索而不是线性搜索来找到匹配项。

性能

以下是带补丁的哈希索引与 B 树索引的一些结果。您可以看到 测试详情以获取有关测试的更多信息。

• 平台

Linux = 2.6.24-16-generic

处理器 = Intel(R) Core(TM)2Duo CPU [email protected]

内存 = 1GB

• 工作负载

表大小 - 39916800 个唯一词，1529MB

查询 - 2000 个等值查询

• 结果

索引	构建时间	索引大小	查询时间	读取的块
哈希	504650.100 ms	1024MB	5189.844 ms	39801
B 树	844495.867 ms	1027MB	5656.045ms	41627

其他

没有补丁的哈希索引非常大。 这里是在较小工作负载上构建索引的一些简单结果。

• 工作负载

表大小 - 3628800 个唯一词，139MB

• 结果

索引	构建时间	索引大小
B 树	51961.123 ms	93MB
没有补丁的哈希	411069.264 ms	2048MB
带补丁的哈希	36288.931 ms	128MB