GSoC 2012 的范围更好索引

简短说明

范围类型是 PostgreSQL 的重大新特性。为了提供对范围的高效搜索，我们必须对范围类型建立索引。目前 GiST 为 9.2 实现的索引方法，它以内部页和叶页条目形式保存范围。该方法在范围高度重叠以及"@>", "<@" 运算符的使用中，可能非常低效，因为搜索成本和使用 "&&" 运算符的搜索成本相似。将范围映射到二维空间可高效地处理这些情况。本项目重点是实现基于二维空间映射的范围类型 GiST 和 SP-GiST 运算符类。

项目详情

本项目的优先顺序如下

范围的 GiST 和 SP-GiST 运算符类。
范围的选取率估算。
数组的 GiST 和 SP-GiST 运算符类。

最低的完成标准只达到第 1 项，但真正的项目目标是对所有提到的选项都做到最好。

更好的范围索引

目前为 9.2 实现的索引方法将内部页中的范围定义为底层范围的边框范围。因此，如果一个叶页包含范围 (a1, b1), (a2, b2), ... (an, bn)，则内部页的相应条目将变为 (min(a1, a2, ... an), max(b1, b2, ... bn))。然而，一些研究论文 [1] 建议将范围映射到二维空间。在这种情况下，范围 (a,b) 将显示为具有坐标 a 和 b 的一个点。

在这样的映射中，"&&", "@>", "<@" 搜索运算符在二维空间上都有相对应的矩形区域。有一个概念证明信息 [2] 表明使用现有的空间运算符类可带来巨大的好处。不过，使用空间运算符类不方便，它不处理有穷和无穷的包含和不包含边框。因此，为这些范围索引实现特定的运算符类非常重要。所以，以下二维空间树可用于范围索引

使用 GiST 的 R 树
使用 SP-GiST 的四叉树
使用 SP-GiST 的 k-d 树

范围的选取率估算

本项目的目标二在于为 &&、@>、<@ 运算符提供更优的选择性估计。一个想法是收集以下统计数据

范围“密度”图
范围长度图

并根据它们对 &&、@>、<@ 进行选择性估计。

数组的 GiST 和 SP-GiST 索引

PostgreSQL 核心仅使用 GIN 支持数组中的运算符“@>”、"<@”、"&&"，基于索引的搜索。intarray contrib 模块还为整数数组提供 GiST 索引支持。但是，类似的 GiST 索引对于其他数组类型也同样适用，而不仅仅是整数数组。本项目专注于为数组实现通用 GiST 索引，并实现数组的实验性 SP-GiST 索引。

针对数组提出的 GiST 索引与 intarray contrib 模块中实现的索引非常类似，但是有一些差异。数组可能具有以下几种表示方式

原始数组
原始数组元素哈希数组（适合于数组元素大于其哈希的情况）
签名（位图，其中设置了对应于数组元素哈希的位）

后两种表示方式是有损的。根据数组大小选择表示方式。所有提到的表示方式都可以用于叶节点和内部条目。内部条目的表示方式选择将在运行时进行，即不计划出现类似于 gist__int_ops 和 gist__intbig_ops 的两难选择。

数组的 SP-GiST 索引是一个非常艰巨的任务，以下是我认为可以实现的想法。可以按照前面提及的 GiST 索引方式之一表示叶元组。内部元组节点表示签名中的位数，而内部元组前缀表示签名中的位集。内部元组节点和前缀中提到的位绝不能设置在对应于所有基础数组的签名中。因此，如果需要前缀或节点中列出的某些位，则在索引扫描期间可以跳过子树。

链接

进度表

6 月 1 日前

实现用于范围的 2d 映射基于 GiST 的 opclass

6 月 1 日 - 6 月 17 日

实现用于范围的 2d 映射基于 SP-GiST 的四叉树

6 月 18 日 - 6 月 24 日

实现用于范围的 2d 映射基于 SP-GiST 的 k-d 树

6 月 25 日 - 7 月 8 日

对各种数据集进行全面测试。关于各种 opclass 适用性的结论

7 月 9 日 - 7 月 12 日

根据测试结果重新设计 opclass。

7 月 13 日 - 8 月 2 日

实现针对范围的更优统计信息，并针对 &&、<@、@> 运算符等提供选择性估计。

8 月 3 日起

测试和重构。