在 PostgreSQL 中使用 GIN 索引时如何加快 ORDER BY 排序？

Question

我有一张这样的表：

CREATE TABLE products (
  id serial PRIMARY KEY, 
  category_ids integer[],
  published boolean NOT NULL,
  score integer NOT NULL,
  title varchar NOT NULL);

一个产品可以属于多个类别。category_ids列包含所有产品类别的 id 列表。

典型的查询看起来像这样（总是搜索单个类别）：

SELECT * FROM products WHERE published
  AND category_ids @> ARRAY[23465]
ORDER BY score DESC, title
LIMIT 20 OFFSET 8000;

为了加快速度，我使用以下索引：

CREATE INDEX idx_test1 ON products
  USING GIN (category_ids gin__int_ops) WHERE published;

除非某一类别中的产品太多，否则这会很有帮助。它会快速过滤掉属于该类别的产品，但随后必须以艰难的方式完成排序操作（没有索引）。

已安装的btree_gin扩展允许我像这样构建多列 GIN 索引：

CREATE INDEX idx_test2 ON products USING GIN (
  category_ids gin__int_ops, score, title) WHERE published;

但是Postgres 不想使用它进行排序。即使我DESC在查询中删除了说明符。

任何优化任务的替代方法都非常受欢迎。

---

附加信息：

• PostgreSQL 9.4，带有 intarray 扩展
• 目前产品总数为 260k，但预计将显着增长（高达 10M，这是多租户电子商务平台）
• 每个类别的产品 1..10000（可以增长到 100k），平均低于 100 但那些产品数量多的类别往往会吸引更多的请求

以下查询计划是从较小的测试系统中获得的（选定类别中的 4680 个产品，表中总共 200k 个产品）：

Limit  (cost=948.99..948.99 rows=1 width=72) (actual time=82.330..82.341 rows=20 loops=1)
  ->  Sort  (cost=948.37..948.99 rows=245 width=72) (actual time=80.231..81.337 rows=4020 loops=1)
        Sort Key: score, title
        Sort Method: quicksort  Memory: 928kB
        ->  Bitmap Heap Scan on products  (cost=13.90..938.65 rows=245 width=72) (actual time=1.919..16.044 rows=4680 loops=1)
              Recheck Cond: ((category_ids @> '{292844}'::integer[]) AND published)
              Heap Blocks: exact=3441
              ->  Bitmap Index Scan on idx_test2  (cost=0.00..13.84 rows=245 width=0) (actual time=1.185..1.185 rows=4680 loops=1)
                    Index Cond: (category_ids @> '{292844}'::integer[])
Planning time: 0.202 ms
Execution time: 82.404 ms

注意 #1：82 毫秒可能看起来并不那么可怕，但这是因为排序缓冲区适合内存。一旦我从 products 表中选择了所有列（SELECT * FROM ...在现实生活中大约有 60 列），它的Sort Method: external merge Disk: 5696kB执行时间就会加倍。这仅适用于 4680 种产品。

行动点#1（来自注释#1）：为了减少排序操作的内存占用并因此加快速度，明智的做法是先获取、排序和限制产品ID，然后获取完整记录：

SELECT * FROM products WHERE id IN (
  SELECT id FROM products WHERE published AND category_ids @> ARRAY[23465]
  ORDER BY score DESC, title LIMIT 20 OFFSET 8000
) ORDER BY score DESC, title;

这让我们回到Sort Method: quicksort Memory: 903kB4680 产品大约 80 毫秒。当产品数量增长到 100k 时，仍然会很慢。

Answer 1

我做了很多实验，这里是我的发现。

GIN 和排序

GIN 索引当前（从 9.4 版开始）无法辅助排序。

在 PostgreSQL 当前支持的索引类型中，只有 B-tree 可以产生排序输出——其他索引类型以未指定的、依赖于实现的顺序返回匹配的行。

工作内存

感谢 Chris 指出这个配置参数。它默认为 4MB，如果您的记录集更大，增加到work_mem适当的值（可以从 中找到EXPLAIN ANALYSE）可以显着加快排序操作。

ALTER SYSTEM SET work_mem TO '32MB';

重新启动服务器以使更改生效，然后仔细检查：

SHOW work_mem;

原始查询

我已经用 650k 产品填充了我的数据库，其中一些类别最多包含 40k 产品。我通过删除published子句简化了查询：

SELECT * FROM products WHERE category_ids @> ARRAY [248688]
ORDER BY score DESC, title LIMIT 10 OFFSET 30000;

Limit  (cost=2435.62..2435.62 rows=1 width=1390) (actual time=1141.254..1141.256 rows=10 loops=1)
  ->  Sort  (cost=2434.00..2435.62 rows=646 width=1390) (actual time=1115.706..1140.513 rows=30010 loops=1)
        Sort Key: score, title
        Sort Method: external merge  Disk: 29656kB
        ->  Bitmap Heap Scan on products  (cost=17.01..2403.85 rows=646 width=1390) (actual time=11.831..25.646 rows=41666 loops=1)
              Recheck Cond: (category_ids @> '{248688}'::integer[])
              Heap Blocks: exact=6471
              ->  Bitmap Index Scan on idx_products_category_ids_gin  (cost=0.00..16.85 rows=646 width=0) (actual time=10.140..10.140 rows=41666 loops=1)
                    Index Cond: (category_ids @> '{248688}'::integer[])
Planning time: 0.288 ms
Execution time: 1146.322 ms

正如我们所见work_mem，这还不够，所以我们有Sort Method: external merge Disk: 29656kB（这里的数字是近似值，内存中快速排序需要略多于 32MB）。

减少内存占用

不要选择完整的记录进行排序，使用 ids，应用排序、偏移和限制，然后只加载我们需要的 10 条记录：

SELECT * FROM products WHERE id in (
  SELECT id FROM products WHERE category_ids @> ARRAY[248688]
  ORDER BY score DESC, title LIMIT 10 OFFSET 30000
) ORDER BY score DESC, title;

Sort  (cost=2444.10..2444.11 rows=1 width=1390) (actual time=707.861..707.862 rows=10 loops=1)
  Sort Key: products.score, products.title
  Sort Method: quicksort  Memory: 35kB
  ->  Nested Loop  (cost=2436.05..2444.09 rows=1 width=1390) (actual time=707.764..707.803 rows=10 loops=1)
        ->  HashAggregate  (cost=2435.63..2435.64 rows=1 width=4) (actual time=707.744..707.746 rows=10 loops=1)
              Group Key: products_1.id
              ->  Limit  (cost=2435.62..2435.62 rows=1 width=72) (actual time=707.732..707.734 rows=10 loops=1)
                    ->  Sort  (cost=2434.00..2435.62 rows=646 width=72) (actual time=704.163..706.955 rows=30010 loops=1)
                          Sort Key: products_1.score, products_1.title
                          Sort Method: quicksort  Memory: 7396kB
                          ->  Bitmap Heap Scan on products products_1  (cost=17.01..2403.85 rows=646 width=72) (actual time=11.587..35.076 rows=41666 loops=1)
                                Recheck Cond: (category_ids @> '{248688}'::integer[])
                                Heap Blocks: exact=6471
                                ->  Bitmap Index Scan on idx_products_category_ids_gin  (cost=0.00..16.85 rows=646 width=0) (actual time=9.883..9.883 rows=41666 loops=1)
                                      Index Cond: (category_ids @> '{248688}'::integer[])
        ->  Index Scan using products_pkey on products  (cost=0.42..8.45 rows=1 width=1390) (actual time=0.004..0.004 rows=1 loops=10)
              Index Cond: (id = products_1.id)
Planning time: 0.682 ms
Execution time: 707.973 ms

注意Sort Method: quicksort Memory: 7396kB。结果好多了。

JOIN 和附加 B 树索引

正如克里斯所建议的，我已经创建了额外的索引：

CREATE INDEX idx_test7 ON products (score DESC, title);

首先，我尝试像这样加入：

SELECT * FROM products NATURAL JOIN
  (SELECT id FROM products WHERE category_ids @> ARRAY[248688]
  ORDER BY score DESC, title LIMIT 10 OFFSET 30000) c
ORDER BY score DESC, title;

查询计划略有不同，但结果相同：

Sort  (cost=2444.10..2444.11 rows=1 width=1390) (actual time=700.747..700.747 rows=10 loops=1)
  Sort Key: products.score, products.title
  Sort Method: quicksort  Memory: 35kB
  ->  Nested Loop  (cost=2436.05..2444.09 rows=1 width=1390) (actual time=700.651..700.690 rows=10 loops=1)
        ->  HashAggregate  (cost=2435.63..2435.64 rows=1 width=4) (actual time=700.630..700.630 rows=10 loops=1)
              Group Key: products_1.id
              ->  Limit  (cost=2435.62..2435.62 rows=1 width=72) (actual time=700.619..700.619 rows=10 loops=1)
                    ->  Sort  (cost=2434.00..2435.62 rows=646 width=72) (actual time=697.304..699.868 rows=30010 loops=1)
                          Sort Key: products_1.score, products_1.title
                          Sort Method: quicksort  Memory: 7396kB
                          ->  Bitmap Heap Scan on products products_1  (cost=17.01..2403.85 rows=646 width=72) (actual time=10.796..32.258 rows=41666 loops=1)
                                Recheck Cond: (category_ids @> '{248688}'::integer[])
                                Heap Blocks: exact=6471
                                ->  Bitmap Index Scan on idx_products_category_ids_gin  (cost=0.00..16.85 rows=646 width=0) (actual time=9.234..9.234 rows=41666 loops=1)
                                      Index Cond: (category_ids @> '{248688}'::integer[])
        ->  Index Scan using products_pkey on products  (cost=0.42..8.45 rows=1 width=1390) (actual time=0.004..0.004 rows=1 loops=10)
              Index Cond: (id = products_1.id)
Planning time: 1.015 ms
Execution time: 700.918 ms

使用各种偏移量和产品计数，我无法让 PostgreSQL 使用额外的 B 树索引。

所以我采用经典方式并创建了连接表：

CREATE TABLE prodcats AS SELECT id AS product_id, unnest(category_ids) AS category_id FROM products;
CREATE INDEX idx_prodcats_cat_prod_id ON prodcats (category_id, product_id);

SELECT p.* FROM products p JOIN prodcats c ON (p.id=c.product_id)
WHERE c.category_id=248688
ORDER BY p.score DESC, p.title LIMIT 10 OFFSET 30000;

Limit  (cost=122480.06..122480.09 rows=10 width=1390) (actual time=1290.360..1290.362 rows=10 loops=1)
  ->  Sort  (cost=122405.06..122509.00 rows=41574 width=1390) (actual time=1264.250..1289.575 rows=30010 loops=1)
        Sort Key: p.score, p.title
        Sort Method: external merge  Disk: 29656kB
        ->  Merge Join  (cost=50.46..94061.13 rows=41574 width=1390) (actual time=117.746..182.048 rows=41666 loops=1)
              Merge Cond: (p.id = c.product_id)
              ->  Index Scan using products_pkey on products p  (cost=0.42..90738.43 rows=646067 width=1390) (actual time=0.034..116.313 rows=210283 loops=1)
              ->  Index Only Scan using idx_prodcats_cat_prod_id on prodcats c  (cost=0.43..1187.98 rows=41574 width=4) (actual time=0.022..7.137 rows=41666 loops=1)
                    Index Cond: (category_id = 248688)
                    Heap Fetches: 0
Planning time: 0.873 ms
Execution time: 1294.826 ms

仍然没有使用 B 树索引，结果集不适合work_mem，因此结果不佳。

但是在某些情况下，拥有大量产品和小偏移量的PostgreSQL现在决定使用B-tree索引：

SELECT p.* FROM products p JOIN prodcats c ON (p.id=c.product_id)
WHERE c.category_id=248688
ORDER BY p.score DESC, p.title LIMIT 10 OFFSET 300;

Limit  (cost=3986.65..4119.51 rows=10 width=1390) (actual time=264.176..264.574 rows=10 loops=1)
  ->  Nested Loop  (cost=0.98..552334.77 rows=41574 width=1390) (actual time=250.378..264.558 rows=310 loops=1)
        ->  Index Scan using idx_test7 on products p  (cost=0.55..194665.62 rows=646067 width=1390) (actual time=0.030..83.026 rows=108037 loops=1)
        ->  Index Only Scan using idx_prodcats_cat_prod_id on prodcats c  (cost=0.43..0.54 rows=1 width=4) (actual time=0.001..0.001 rows=0 loops=108037)
              Index Cond: ((category_id = 248688) AND (product_id = p.id))
              Heap Fetches: 0
Planning time: 0.585 ms
Execution time: 264.664 ms

这实际上很合乎逻辑，因为这里的 B 树索引不会产生直接结果，它仅用作顺序扫描的指南。

让我们与 GIN 查询进行比较：

SELECT * FROM products WHERE id in (
  SELECT id FROM products WHERE category_ids @> ARRAY[248688]
  ORDER BY score DESC, title LIMIT 10 OFFSET 300
) ORDER BY score DESC, title;

Sort  (cost=2519.53..2519.55 rows=10 width=1390) (actual time=143.809..143.809 rows=10 loops=1)
  Sort Key: products.score, products.title
  Sort Method: quicksort  Memory: 35kB
  ->  Nested Loop  (cost=2435.14..2519.36 rows=10 width=1390) (actual time=143.693..143.736 rows=10 loops=1)
        ->  HashAggregate  (cost=2434.71..2434.81 rows=10 width=4) (actual time=143.678..143.680 rows=10 loops=1)
              Group Key: products_1.id
              ->  Limit  (cost=2434.56..2434.59 rows=10 width=72) (actual time=143.668..143.670 rows=10 loops=1)
                    ->  Sort  (cost=2433.81..2435.43 rows=646 width=72) (actual time=143.642..143.653 rows=310 loops=1)
                          Sort Key: products_1.score, products_1.title
                          Sort Method: top-N heapsort  Memory: 68kB
                          ->  Bitmap Heap Scan on products products_1  (cost=17.01..2403.85 rows=646 width=72) (actual time=11.625..31.868 rows=41666 loops=1)
                                Recheck Cond: (category_ids @> '{248688}'::integer[])
                                Heap Blocks: exact=6471
                                ->  Bitmap Index Scan on idx_products_category_ids_gin  (cost=0.00..16.85 rows=646 width=0) (actual time=9.916..9.916 rows=41666 loops=1)
                                      Index Cond: (category_ids @> '{248688}'::integer[])
        ->  Index Scan using products_pkey on products  (cost=0.42..8.45 rows=1 width=1390) (actual time=0.004..0.004 rows=1 loops=10)
              Index Cond: (id = products_1.id)
Planning time: 0.630 ms
Execution time: 143.921 ms

GIN 的结果要好得多。我检查了产品数量和偏移量的各种组合，在任何情况下，连接表方法都不会更好。

真实指数的力量

为了让 PostgreSQL 充分利用索引进行排序，所有查询WHERE参数以及ORDER BY参数必须驻留在单个 B 树索引中。为此，我已将排序字段从产品复制到连接表：

CREATE TABLE prodcats AS SELECT id AS product_id, unnest(category_ids) AS category_id, score, title FROM products;
CREATE INDEX idx_prodcats_1 ON prodcats (category_id, score DESC, title, product_id);

SELECT * FROM products WHERE id in (SELECT product_id FROM prodcats WHERE category_id=248688 ORDER BY score DESC, title LIMIT 10 OFFSET 30000) ORDER BY score DESC, title;

Sort  (cost=2149.65..2149.67 rows=10 width=1390) (actual time=7.011..7.011 rows=10 loops=1)
  Sort Key: products.score, products.title
  Sort Method: quicksort  Memory: 35kB
  ->  Nested Loop  (cost=2065.26..2149.48 rows=10 width=1390) (actual time=6.916..6.950 rows=10 loops=1)
        ->  HashAggregate  (cost=2064.83..2064.93 rows=10 width=4) (actual time=6.902..6.904 rows=10 loops=1)
              Group Key: prodcats.product_id
              ->  Limit  (cost=2064.02..2064.71 rows=10 width=74) (actual time=6.893..6.895 rows=10 loops=1)
                    ->  Index Only Scan using idx_prodcats_1 on prodcats  (cost=0.56..2860.10 rows=41574 width=74) (actual time=0.010..6.173 rows=30010 loops=1)
                          Index Cond: (category_id = 248688)
                          Heap Fetches: 0
        ->  Index Scan using products_pkey on products  (cost=0.42..8.45 rows=1 width=1390) (actual time=0.003..0.003 rows=1 loops=10)
              Index Cond: (id = prodcats.product_id)
Planning time: 0.318 ms
Execution time: 7.066 ms

这是选择类别中的大量产品和大偏移量的最坏情况。当 offset=300 时，执行时间仅为 0.5 ms。

不幸的是，维护这样的联结表需要额外的努力。它可以通过索引物化视图来完成，但这仅在您的数据更新很少时才有用，因为刷新此类物化视图是一项相当繁重的操作。

所以到目前为止我一直使用 GIN 索引，增加work_mem和减少内存占用查询。

Answer 2

这里有一些快速提示，可以帮助您提高表现。我将从最简单的技巧开始，这对您来说几乎毫不费力，然后在第一个技巧之后转向更困难的技巧。

1.work_mem

因此，我立即发现您的解释计划中报告的排序Sort Method: external merge Disk: 5696kB消耗的内存少于 6 MB，但会溢出到磁盘。您需要增加文件work_mem中的设置，postgresql.conf使其足够大，以便排序可以适合内存。

编辑：此外，在进一步检查时，我发现在使用索引检查catgory_ids哪个符合您的条件后，位图索引扫描被迫变得“有损”，并且在从相关堆页中读取行时必须重新检查条件。 请参阅postgresql.org 上的这篇文章以获得比我给出的更好的解释。:P 最主要的一点是你的work_mem水平太低了。如果您尚未调整服务器上的默认设置，则它的性能不会很好。

此修复基本上不会花费您时间。只要更改为postgresql.conf，您就可以出发了！请参阅此性能调整页面以获取更多提示。

2.架构变更

因此，您在模式设计中决定将 进行非规范化category_ids为整数数组，然后强制您使用 GIN 或 GIST 索引来获得快速访问。根据我的经验，您选择的 GIN 索引的读取速度比 GIST 更快，因此在这种情况下您做出了正确的选择。然而，GIN 是一个未排序的索引；可以将其视为键值对，其中等式谓词很容易检查，但索引无法促进诸如WHERE >、WHERE <或 之类的操作。ORDER BY

一个不错的方法是使用桥接表/连接表来标准化您的设计，用于指定数据库中的多对多关系。

在这种情况下，你有很多类别和一组相应的整数category_id，并且你有很多产品及其相应的product_id。不要将产品表中的列作为 s 的整数数组category_id，而是从架构中删除此数组列，然后创建一个表，如下所示

CREATE TABLE join_products_categories (product_id int, category_id int);

然后，您可以在桥接表的两列上生成B树索引，

CREATE INDEX idx_products_in_join_table ON join_products_categories (product_id);
CREATE INDEX idx_products_in_join_table ON join_products_categories (category_id);

这只是我的拙见，但这些变化可能会给您带来很大的改变。work_mem至少首先要尝试一下这种改变。

祝你好运！

编辑：

建立额外的索引来辅助排序

因此，如果随着时间的推移您的产品线扩展，某些查询可能会返回许多结果（数千、数万？），但这可能仍然只是整个产品线的一小部分。在这些情况下，如果在内存中进行排序，甚至可能非常昂贵，但是可以使用适当设计的索引来辅助排序。

请参阅描述Indexes 和 ORDER BY的官方 PostgreSQL 文档。

ORDER BY如果您创建符合您要求的索引

CREATE INDEX idx_product_sort ON products (score DESC, title);

然后 Postgres 将优化并决定是否使用索引或执行显式排序将更具成本效益。请记住，不能保证Postgres 会使用该索引；它将寻求优化性能并在使用索引或显式排序之间进行选择。如果您创建此索引，请监视它以查看它的使用是否足以证明其创建的合理性，如果您的大多数排序都已显式完成，则将其删除。

尽管如此，在这一点上，您的“最大的性价比”改进可能会使用 more work_mem，但在某些情况下索引可以支持排序。