快速 GiST 索引构建 GSoC 2011
想法
目前 GiST 索引没有任何批量加载功能。它必须通过逐个条目插入来创建新的索引。这使得新的索引创建速度相对较慢，与 B 树甚至 GIN 相比。在计算机科学中，有各种关于 R 树批量操作的工作。由于 GiST 在本质上是对 R 树的推广，因此其中一些似乎适用于 GiST。在 [1] 中，介绍了 R 树批量操作技术。尽管存在一些与 GiST 与 R 树的区别相关的问题，但本文的技术似乎适用于 GiST。
细节
算法简要描述
论文 [1] 提出了一种 R 树批量操作技术，它通常是将缓冲树 [2] 应用于 R 树。
论文 [1] 中的技术可以用以下规则简要描述。
M = 能够放入 RAM 的索引键数量；
B = 每个页面中的索引键数量；
每个页面包含 M/(2*B) 个附加缓冲区，附加到某些级别的所有节点。级别以 step floor(log(M/4B, B))) 选择，叶节点不包含缓冲区。即，级别 i*floor(log(M/4B, B))) 中的节点，i = 1,2,3,... 包含缓冲区（编号从下往上，级别 0 包含叶节点）。当条目到达包含缓冲区的节点时，它将被放置到缓冲区中。当缓冲区溢出时，它会向下运行到较低的缓冲区或叶页面中。当在包含缓冲区的节点中发生拆分时，缓冲区将使用惩罚函数拆分为两个缓冲区。
Varlena 键
由于论文 [1] 中考虑的是 R 树，因此键长度是固定的。在 GiST 中，我们可以处理 Varlena 键，这会导致复杂性。例如，在将索引条目放置到适当的缓冲区时，可能会发生页面拆分。Varlena 键的另一个难点是缓冲区的大小和缓冲区级别的步长是根据页面中条目的数量来计算的。使用 Varlena 键时，此数字不是恒定的。
第一个实现将采用非常简单的方法来处理 Varlena 键。当键大小最小时，可以实现最大的缓冲区大小和最小的级别步长。因此，最小的键大小是最坏的情况。由于最小的 Varlena 大小为 4 字节，因此我们可以在初始计算中使用它。
其他可能的应用
- 批量插入。由于 PostgreSQL 中的访问方法接口不包含批量插入函数，因此批量插入操作是通过逐个条目插入来执行的。访问方法不知道期望多少个条目。这种情况下，对 PostgreSQL GiST 应用批量插入技术变得困难。使用当前的访问方法接口，批量插入可以使用类似于 GIN 中的 fastupdate 的技术来实现。但需要注意的是，这种技术会导致并发索引搜索扫描缓冲区。由于缓冲区大小很大（大多数最低缓冲区的大小与整个子树的大小相当），这会导致明显的减速。在索引构建加速和并发搜索减速之间找到折衷方案是一个独立的研究，它似乎不适合在 GSoC 中完成。
- 批量删除。PostgreSQL GiST 中的当前批量删除操作很快，但它不执行索引重构。这会导致索引在批量删除期间恶化。论文 [1] 中的批量删除技术侧重于加速执行索引重构的批量删除过程。将这种方法应用于 GiST 的问题是，GiST 实现没有提供关于存储利用率的任何明确保证。如果存在此类保证，那么它们将隐藏在 picksplit 访问方法中。应用批量删除技术要求 GiST 访问方法了解实现的存储利用率保证。反过来，它需要对 GiST 操作符类进行重构，这似乎不适合在 GSoC 中完成。
时间表
- 直到 6 月 3 日
首先，近似实现。
- 6 月 4 日 - 6 月 6 日
第一次基准测试。
- 6 月 7 日 - 7 月 14 日
解决索引质量问题。在各种 GiST 应用和数据分布上进行测试。解决测试中出现的任何问题。代码重构和注释。
- 7 月 15 日 - 7 月 31 日
在更广泛的数据集上进行详细基准测试。解决剩余问题。
- 8 月 1 日 - 8 月 16 日
最终重构、测试和提交。
待办事项
- 在最新版本的补丁上重新运行一些测试。
测试结果
| 操作符类 | 数据集 | 元组计数 | 平均长度 | 拆分方法 | 构建方法 | 实际时间 | CPU 时间 | 共享读取 | 搜索时间 |
| point_ops | 均匀分布的随机数据 | 1 亿 | N/A | 新的线性 | 常规 | 17 小时 39 分钟 | 27 分钟 | 35568002 | 1 |
| fastbuild (1/366/on) | 3 小时 17 分钟 | 28 分钟 | 2539827 | 1.12 | |||||
| fastbuild (1/366/auto) | 3 小时 23 分钟 | 29 分钟 | 2548365 | 0.90 | |||||
| 双重排序 | 常规 | 9 天 10 小时 | 50 分钟 | 85705372 | 0.089 | ||||
| fastbuild (1/366/on) | 4 小时 9 分钟 | 28 分钟 | 2729786 | 0.094 | |||||
| fastbuild (1/366/auto) | 4 小时 11 分钟 | 28 分钟 | 2729116 | 0.089 | |||||
| point_ops | 一些 USNOA2 星星的集合（已排序） | 1 亿 | N/A | 新的线性 | 常规 | 56 分钟 | 40 分钟 | 1987537 | 1 |
| fastbuild (1/366/on) | 1 小时 22 分钟 | 50 分钟 | 1759204 | 0.48 | |||||
| fastbuild (1/366/auto) | 1 小时 27 分钟 | 50 分钟 | 1761244 | 0.46 | |||||
| 双重排序 | 常规 | 45 分钟 | 42 分钟 | 1671106 | 0.37 | ||||
| fastbuild (1/366/on) | 1 小时 29 分钟 | 55 分钟 | 1803297 | 0.34 | |||||
| fastbuild (1/366/auto) | 1 小时 29 分钟 | 55 分钟 | 1801702 | 0.36 | |||||
| point_ops | 一些 USNOA2 星星的集合（已随机排列） | 1 亿 | N/A | 新的线性 | 常规 | 10 小时 12 分钟 | 23 分钟 | 15650402 | 1 |
| fastbuild (1/366/on) | 3 小时 20 分钟 | 30 分钟 | 2514365 | 1.48 | |||||
| fastbuild (1/366/auto) | 3 小时 16 分钟 | 30 分钟 | 2505735 | 0.89 | |||||
| 双重排序 | 常规 | 8 天 20 小时 | 50 分钟 | 85315498 | 0.072 | ||||
| fastbuild (1/366/on) | 4 小时 15 分钟 | 28 分钟 | 2722891 | 0.068 | |||||
| fastbuild (1/366/auto) | 4 小时 20 分钟 | 30 分钟 | 2725721 | 0.067 |
列描述
- 操作符类 - 索引中使用的操作符类
- 数据集 - 已索引数据集的描述
- 元组计数 - 已索引的元组数量
- 平均长度 - 如果适用，值的平均长度（用于表示字符串和数组的长度）
- 拆分方法 - 索引构建期间使用的 picksplit 实现
- 构建方法 - 索引构建的方法：常规或 fastbuild。对于 fastbuild，级别步长、缓冲区大小、缓冲参数在括号中给出。
- 实际时间 - 索引构建在测试机器上的实际时间
- 共享读取 - 通过 pg_stat_statement 衡量的索引构建期间的页面读取次数
- CPU 时间 - 索引构建期间的 CPU 使用时间
- 搜索时间 - 衡量索引质量比较的指标。定义为使用快速构建索引扫描页面访问次数与在一些测试用例中使用常规构建索引扫描页面访问次数的平均商。值 1 表示快速构建索引与常规构建索引的搜索类似。如果值大于 1，则快速构建索引更慢。如果值小于 1，则快速构建索引更快。
数据集
本节包含上面部分中使用的数据集的详细描述。
- 均匀分布的随机数据
可以使用以下 SQL 命令生成数据。
CREATE TABLE points AS (SELECT point(random(), random() FROM generate_series(1,10000000));
generate_series 的第二个参数可能因所需的元组计数而异。
为了可重复性，数据集可以从 http://89.235.136.212/uniform.txt.gz 下载。
- 美国地名
此数据集可以从 http://download.geonames.org/export/dump/ 获取。
- 英语词典
来自 Ubuntu Linux 中 wamerican 包的美国英语词典。通常位于 /usr/share/dict/american-english 中。
- DBLP 论文标题
原始 XML 可以从 http://dblp.uni-trier.de/xml/ 获取。用于标题提取的简单 PHP 脚本如下。
<?php
$fp = fopen("dblp.xml", "r");
while (!feof($fp))
{
$s = fgets($fp);
if (preg_match('/<title>(.*)<\\/title>/',$s,$matches))
{
$str = $matches[1];
$str = str_replace(chr(0), ' ', $str);
echo $str."\n";
}
}
fclose($fp);
- 一些 USNOA2 星星的集合（已排序）
此数据集可以从 http://89.235.136.212/usnoa2.txt.gz 获取。
- 一些 USNOA2 星星的集合（已随机排列）
此数据集可以从 http://89.235.136.212/usnoa2_shuffled.txt.gz 获取。
