优化 Postgres 的前 N 排序以加载最少数量的缓冲区页

Question

考虑一个包含三列项目的示例表:

• id(UUID，主键)
time(timestamptz)
• store_id(uuid，外键)

在(store_id, time) INCLUDING (id)上存在一个覆盖b树索引

查找top-N项

我想编写一个查询，它能有效地从一组指定的商店中获取20个最新的商品。每个store_id可能有数万或数十万行。这是一个产生正确结果的相对简单的查询:

SELECT id, time
FROM items
WHERE store_id = ANY(ARRAY[
'aaaaaaaa-aaaa-aaaa-aaaa-aaaaaaaaaaaa',
'bbbbbbbb-bbbb-bbbb-bbbb-bbbbbbbbbbbb',
...
]::uuid[])
ORDER BY time DESC
LIMIT 20;

然而，根据EXPLAIN (ANALYZE, BUFFERS)的查询计划，尽管有LIMIT 20子句，Postgres仍然读取了超过10,000个缓冲页。即使使用SSD，速度也很慢。实际情况是Postgres在排序之前读取所有索引项。

查询计划这个查询计划是在这个问题第一次发布之后生成的，我已经执行了一些其他的数据库优化，比如驯鹿索引和真空。查询现在运行得相当快，但仍然要访问超过7900个缓冲页。

Limit  (cost=553.97..554.02 rows=20 width=56) (actual time=214.618..214.624 rows=21 loops=1)
Output: id, time
Buffers: shared hit=7606 read=369 dirtied=1
I/O Timings: read=205.188
->  Sort  (cost=553.97..574.15 rows=8073 width=56) (actual time=214.617..214.620 rows=20 loops=1)
Output: id, time
Sort Key: items.time DESC
Sort Method: top-N heapsort  Memory: 28kB
Buffers: shared hit=7606 read=369 dirtied=1
I/O Timings: read=205.188
->  Index Only Scan using items_store_id_time_covering_id_idx on public.items  (cost=0.43..336.31 rows=8073 width=56) (actual time=0.730..211.783 rows=11920 loops=1)
Output: id, time
Index Cond: (items.store_id = ANY ('{aaaaaaaa-aaaa-aaaa-aaaa-aaaaaaaaaaaa,bbbbbbbb-bbbb-bbbb-bbbb-bbbbbbbbbbbb, ...}'::uuid[]))
Heap Fetches: 282
Buffers: shared hit=7606 read=369 dirtied=1
I/O Timings: read=205.188
Settings: effective_cache_size = '3052336kB', random_page_cost = '1.1'
Query Identifier: -1648601102884428975
Planning Time: 0.160 ms
Execution Time: 214.647 ms

横向连接-速度快50-100倍

一个非常有用的解决方案是使用横向连接迭代地只加载每个store_id的20个最新项，然后取其中的20个最新项。这只加载了几百个缓冲页面，对于我的测试工作负载来说，效率提高了50-100倍!

SELECT id, time
FROM unnest(ARRAY[
'aaaaaaaa-aaaa-aaaa-aaaa-aaaaaaaaaaaa',
'bbbbbbbb-bbbb-bbbb-bbbb-bbbbbbbbbbbb',
...
]::uuid[]) AS store_ids(store_id)
JOIN LATERAL (
SELECT id, time
FROM items
WHERE store_id = store_ids.store_id
ORDER BY time DESC
LIMIT 20
) ON TRUE
ORDER BY time DESC
LIMIT 20;

查询计划这个查询计划更有效率，访问119个缓冲页。

Limit  (cost=26.21..26.26 rows=20 width=24) (actual time=0.284..0.287 rows=20 loops=1)
Output: items.id, items.time
Buffers: shared hit=119
->  Sort  (cost=26.21..26.76 rows=220 width=24) (actual time=0.283..0.285 rows=20 loops=1)
Output: items.id, items.time
Sort Key: items.time DESC
Sort Method: top-N heapsort  Memory: 27kB
Buffers: shared hit=119
->  Nested Loop  (cost=0.43..20.35 rows=220 width=24) (actual time=0.055..0.247 rows=200 loops=1)
Output: items.id, items.time
Buffers: shared hit=119
->  Function Scan on pg_catalog.unnest store_ids  (cost=0.00..0.11 rows=11 width=16) (actual time=0.005..0.006 rows=11 loops=1)
Output: store_ids.store_id
Function Call: unnest('{aaaaaaaa-aaaa-aaaa-aaaa-aaaaaaaaaaaa,bbbbbbbb-bbbb-bbbb-bbbb-bbbbbbbbbbbb,...}'::uuid[])
->  Limit  (cost=0.43..1.44 rows=20 width=24) (actual time=0.011..0.019 rows=18 loops=11)
Output: items.id, items.time
Buffers: shared hit=119
->  Index Only Scan Backward using items_store_id_time_covering_id_idx on public.items  (cost=0.43..5.48 rows=100 width=24) (actual time=0.010..0.017 rows=18 loops=11)
Output: items.id, items.time
Index Cond: (items.store_id = store_ids.store_id)
Heap Fetches: 20
Buffers: shared hit=119
Settings: effective_cache_size = '3052336kB', random_page_cost = '1.1'
Query Identifier: -8987254562252190725
Planning:
Buffers: shared hit=28
Planning Time: 0.254 ms
Execution Time: 0.321 ms

然而，更聪明的查询计划是依次从每个store_id中加载20个项目，只保留具有最新time列的20个项目。我也更喜欢声明式SQL而不是命令式SQL(特别是for-each性质的横向连接)，以便为查询规划器提供更多的控制，理想情况下可以获得更好的性能。

其他尝试我还尝试了两种替代方法，使用ROW_NUMBER()和模拟松散索引扫描，这两种方法在这种情况下都表现不佳，因为Postgres仍然读取超过10,000个缓冲区页面。

是否有一个(简单)的方法来让Postgres生成一个查询计划，加载和排序的行数最少?查询规划器和执行器是否能够实现"更智能的查询计划"?上面描述的吗?

Answer 1

你的方法可能是最好的方法。一个更好的计划可能需要像"索引跳过扫描"这样的东西，这在PostgreSQL中没有实现。一个补丁已经被提议，并经过了19个委员会，但遗憾的是，尽管每个人都表示感兴趣，但它从未成功。

Answer 2

我不知道你是真的需要它更快，还是只是因为不完美而生气。在第一种情况下，您应该与我们分享计划，以便我们可能提出实用的改进建议。(在第二种情况下，准备好失望吧)。

您可以得到比建议的解决方案更好的方法，不是为每个store_id读取20行，而是只读取比每个store_id实际返回的多一行。但是获得这个计划需要查询比"命令式"更糟糕，它需要动态构造。

(SELECT id, time FROM items WHERE store_id = 'a1...' ORDER BY time DESC) 
union all 
(SELECT id, time FROM items WHERE store_id = 'b7...' ORDER BY time DESC)
-- etc, 
ORDER BY time DESC LIMIT 20;

也许一个更实用的解决方案是在(time, store_id, id)上添加索引，然后使用原始查询。但是，如果查询中的store_id数组完全由没有新项目，只有旧项目的商店组成，那么这将非常糟糕。更糟糕的是，PostgreSQL将无法检测到这种情况，因此选择不同的计划。