在Postgres中分页的五种方法，从基本到异国情调
您可能会惊讶地发现，分页在 Web 应用程序中普遍存在，但很容易实现效率低下。在本文中，我们将研究几种服务器端分页方法，并讨论它们在 PostgreSQL 中实现时的权衡。本文将帮助您确定哪种技术适合您的情况，包括一些您以前可能没有见过的技术，它们依赖于物理集群和数据库统计信息收集器。
在继续之前，提及客户端分页是有意义的。某些应用程序将所有（或大部分）服务器信息传输到客户端并在那里分页。对于少量数据，客户端分页可能是更好的选择，从而减少 HTTP 调用。当记录开始数以千计时，这变得不切实际。服务器端还有其他好处，例如
- 更快的初始页面加载
- 共享数据更改时的准确性更高
- 更快地对大型数据集进行操作
- 业务逻辑的封装
- 在资源受限的客户端上获得更好的性能
PostgreSQL为我们提供了许多服务器端分页技术，这些技术在速度，完整性（不丢失记录）以及对某些页面访问模式的支持方面有所不同。并非所有方法都适用于所有情况，有些方法需要特殊数据或查询。让我们按通用顺序考虑这些方法，从适用于任何查询的方法开始，然后是需要有序数据的方法。我们将以一些依赖于PostgreSQL内部的奇特方法结束。
对任意查询进行分页
限位偏移
最简单的分页方法，限制偏移量，也是最危险的。可悲的是，它是Web应用程序开发教程的主要内容。对象关系映射（ORM）库使它变得简单而诱人，从SQLAlchemy的.slice（1，3）到ActiveRecord的.limit（1）.offset（3）到Sequelize的.findAll（{偏移量：3，limit：1}）。 它们都生成以 LIMIT 1 OFFSET 3 结尾的 SQL。限制偏移量使用很普遍并非巧合，您可以将其附加到任何查询上而无需进一步修改。
限制和偏移数据的ORM方法是一回事，但分页辅助库可能更具欺骗性。例如，流行的Ruby库Kaminari默认使用限制偏移量，同时将其隐藏在高级接口后面。
该技术有两个大问题，导致不一致和抵消效率低下。一致性是指遍历结果集应精确检索每个项目一次，没有遗漏或重复的意图。失调效率低下是指将结果偏移较大的偏移量引起的延迟。
以下是限制偏移分页不一致的原因。假设用户从页面 n 移动到页面 n+1，同时将新元素插入页面 n。这将导致重复（第 n 页的先前最后一个元素被推入第 n+1 页）和遗漏（新元素）。或者，考虑在用户移动到第 n+1 页时从第 n 页中删除的元素。第 n+1 页的先前初始元素将移至第 n 页并省略。
现在是效率低下。大偏移本质上是昂贵的。即使存在索引，数据库也必须扫描存储，计算行数。要使用索引，我们必须按值过滤列，但在这种情况下，我们需要一定数量的行，而不管它们的列值如何。此外，这些行在存储中不需要具有相同的大小，有些行可能存在于磁盘上，但标记为已删除，因此数据库无法使用简单的算术在磁盘上查找开始读取结果的位置。让我们来衡量一下速度放缓。
-- Create table with random strings of various lengths
CREATE TABLE medley AS
SELECT
generate_series(1,10000000) AS n,
substr(concat(md5(random()::text), md5(random()::text)), 1, (random() * 64)::integer + 1) AS description;
-- Notify query planner of drastically changed table size
VACUUM ANALYZE;
-- Low offsets are refreshingly fast
EXPLAIN ANALYZE SELECT * FROM medley LIMIT 100;
估计成本相当低：
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------
Limit (cost=0.00..1.85 rows=100 width=38) (actual time=0.008..0.036 rows=100 loops=1)
-> Seq Scan on medley (cost=0.00..185460.60 rows=9999660 width=38) (actual time=0.007..0.017 rows=100 loops=1)
Planning time: 0.040 ms
Execution time: 0.059 ms
(4 rows)
选择 offset=1000 会使成本约为 19，执行时间为 0.609 毫秒。一旦偏移量=5，000，000，成本上升到92734，执行时间为758.484毫秒。
这些问题并不一定意味着限制偏移不适用于您的情况。在某些应用程序中，用户通常不会将许多页面推进到结果集中，您甚至可以选择强制实施服务器页面限制。如果结果不一致和限制页码在您的应用程序中不是问题，那么限制偏移量可能方便满足您的需求。
何时使用：极限偏移
分页深度受限且允许结果不一致的应用程序。
游标
尽管有缺点，但限制偏移量确实具有在服务器上无状态的优点。将其与另一种分页方法（查询游标）进行对比。与偏移量一样，游标可以在任何查询中使用，但它们的不同之处在于要求服务器为每个 HTTP 客户端保存专用数据库连接和事务。
以下是游标的使用方法：
-- We must be in a transaction
BEGIN;
-- Open a cursor for a query
DECLARE medley_cur CURSOR FOR SELECT * FROM medley;
-- Retrieve ten rows
FETCH 10 FROM medley_cur;
-- ...
-- Retrieve ten more from where we left off
FETCH 10 FROM medley_cur;
-- All done
COMMIT;
游标具有任意查询分页一致性的理想属性，显示事务启动时存在的结果。事务的隔离级别（链接是外部的）保证了结果的分页视图不会更改。
每种分页方法都有一个缺点，游标的问题是资源使用和客户端-服务器耦合。每个打开的事务都会消耗专用的数据库资源，并且无法针对太多客户端进行扩展。还有“WITH HOLD”游标，它们可以存在于事务之外，但它们必须具体化数据。无论哪种方式，这都使游标分页仅适用于小规模情况，如 Intranet 使用。
将 HTTP 桥接到游标会带来复杂性。服务器必须通过令牌或在会话中保留标识符（如客户端 IP 地址）来跨请求标识客户端。服务器还必须判断何时由于不活动而释放事务。最后，服务器负载平衡变得复杂，因为每个客户端每次都必须连接到专用服务器。
何时使用：游标一种单服务器 Intranet 应用程序，它必须以各种多变的顺序对查询进行分页，尤其是在结果一致性很重要的情况下。
有序查询的分页
键集分页
上述技术可以对任何类型的查询进行分页，包括没有顺序子句的查询。如果我们愿意放弃这种普遍性，我们就会获得优化。特别是按索引列排序时，客户端可以使用当前页中的值来选择要在下一页中显示的项目。这称为键集分页。
例如，让我们回到混合泳的例子：
-- Add an index for keyset pagination (btrees support inequality)
CREATE INDEX n_idx ON medley USING btree (n);
SELECT * FROM medley ORDER BY n ASC LIMIT 5;
使用我的随机数据，它返回
n | description
---+-------------------------------------------------------------
1 | 74f70e009396
2 | 8dac5a085eb670a29058d
3 | fce303a32e89181bf5df1601487
4 | fddcced2c12e83516b3bd6cc94f23a012dfd
5 | f51ae548dd27f51147e53e839eeceb6b0c92922145276d668e73d4a6621
(5 rows)
现在，客户端可以查看此结果中的最大值 n，并将其用于请求下一页：
SELECT *
FROM medley
WHERE n > 5
ORDER BY n ASC
LIMIT 5;
即使按 n > 5000000 进行过滤，也保持快速，这与限制偏移示例不同。
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------
Limit (cost=0.43..0.62 rows=5 width=38) (actual time=0.101..0.103 rows=5 loops=1)
-> Index Scan using n_idx on medley (cost=0.43..185579.42 rows=5013485 width=38) (actual time=0.100..0.102 rows=5 loops=1)
Index Cond: (n > 5000000)
Planning time: 0.071 ms
Execution time: 0.119 ms
(5 rows)
键集分页速度很快，而且也很一致。当前页面之前的任何插入/删除都将不影响结果。此方法的两个缺点是缺少随机访问以及客户端和服务器之间可能的耦合。
通常，如果不访问先前的页面以观察其最大元素，则无法直接跳转到给定页面。在某些条件下，我们可以做得更好。如果索引列中的值均匀分布（甚至更好，没有间隙的连续数字），客户端可以做一些数学运算来查找所需的页面，因为索引使得查找最大值变得便宜：
EXPLAIN ANALYZE SELECT max(n) FROM medley;
QUERY PLAN
------------------------------------------------------------------------------------------------------------
Result (cost=0.46..0.47 rows=1 width=0) (actual time=0.021..0.021 rows=1 loops=1)
InitPlan 1 (returns $0)
-> Limit (cost=0.43..0.46 rows=1 width=4) (actual time=0.018..0.018 rows=1 loops=1)
-> Index Only Scan Backward using n_idx on medley (cost=0.43..284688.43 rows=10000000 width=4) (actual time=0.017..0.017 rows=1 loops=1)
Index Cond: (n IS NOT NULL)
Heap Fetches: 0
Planning time: 0.087 ms
Execution time: 0.042 ms
(8 rows)
密钥集分页的另一个问题，即客户端/服务器耦合，需要小心。首先，客户端不知道为哪些列编制了索引。服务器可能需要提供具有固定顺序的终结点，而不是允许客户端自定义顺序。鉴于客户端代码可能不知道正在订购哪一列，服务器必须提供有关如何请求下一页的提示。RFC5988定义 HTTP 链接关系之前和下一个编码链接，供客户端遵循。
由于用户通常以线性方式访问信息页面，因此键集分页通常被认为是在高流量 Web 服务器中对有序记录进行分页的最佳选择。
何时使用：键集可伸缩的应用程序，按顺序提供索引列中的数据，以便进行比较。支持过滤。
异国情调，专业分页
群集 TID 扫描
我们可以使用低级 PostgreSQL 功能为特殊情况设计非标准的分页技术。例如，我们可以对数据实现真正的随机访问，如果我们
- 不要求所有页面的长度完全相同
- 分页行仅支持一个顺序
诀窍是选择与磁盘上的数据库页或这些磁盘页的部分直接对应的返回页。PostgreSQL 数据库中的每个表都包含一个名为 ctid 的秘密列，用于标识其行：
SELECT ctid, * FROM medley WHERE n <= 10;
ctid | n | description
--------+----+-------------------------------------------------------------
(0,1) | 1 | 74f70e009396
(0,2) | 2 | 8dac5a085eb670a29058d
(0,3) | 3 | fce303a32e89181bf5df1601487
(0,4) | 4 | fddcced2c12e83516b3bd6cc94f23a012dfd
(0,5) | 5 | f51ae548dd27f51147e53e839eeceb6b0c92922145276d668e73d4a6621
(0,6) | 6 | eb9fe1dfe1e421903f96b3b5c5dfe1ee1253582d728c35b4ee7330b
(0,7) | 7 | e95202d7f5c612f8523ae705d
(0,8) | 8 | 6573b64aff262a2b940326
(0,9) | 9 | a0a43
(0,10) | 10 | 82cdc134bd249a612cfddd3088dd09e32de5f4fa33
(10 rows)
每个 ctid 的格式为（页面、行）。PostgreSQL可以通过ctid非常快速地检索行，事实上这就是索引内部的工作方式 - 它们将列值映射到ctid。
请注意，尽管 PostgreSQL 在 tid 类型上定义了顺序关系，但它无法通过不等式有效地检索 ctid。
EXPLAIN ANALYZE SELECT count(1) FROM medley WHERE ctid >= '(0,1)'::tid AND ctid < '(1,0)'::tid;
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------
Aggregate (cost=235589.00..235589.01 rows=1 width=0) (actual time=1241.851..1241.852 rows=1 loops=1)
-> Seq Scan on medley (cost=0.00..235464.00 rows=50000 width=0) (actual time=477.933..1241.802 rows=116 loops=1)
Filter: ((ctid >= '(0,1)'::tid) AND (ctid < '(1,0)'::tid))
Rows Removed by Filter: 9999884
Planning time: 0.047 ms
Execution time: 1241.889 ms
(6 rows)
请求范围不起作用，但仍有一种方法可以有效地请求磁盘页面中的所有行。每个页面都包含当前设置（“块大小”）字节的数据（通常为 8k）。行由 32 位指针引用，因此每页最多有 block_size/4 行。（事实上，行通常比最小大小宽，块大小的四分之一提供每页行的上限。以下序列将在第 j 页中生成所有可能的 ctid
SELECT ('(' || j || ',' || s.i || ')')::tid
FROM generate_series(0,current_setting('block_size')::int/4) AS s(i);
让我们用它来获取第 0 页上混合音乐中的所有行。
SELECT * FROM medley WHERE ctid = ANY (ARRAY
(SELECT ('(0,' || s.i || ')')::tid
FROM generate_series(0,current_setting('block_size')::int/4) AS s(i)
)
);
计划人员将此查询标识为 cost=25.03..65.12，运行时间为 2.765 毫秒。请求第 10，000 页的费用类似。所以我们得到了真正的随机访问，有什么不爱的？
有三个缺点
- 删除行时，它们会在页面中留下漏洞。
- 行的顺序可能没有意义。数据库将新行插入到已删除行留下的孔中，这将导致行顺序不正常。
- 不支持“where”子句。
在某些情况下，这不是问题。一种情况是其自然顺序与广告顺序相对应的数据，例如仅追加时间序列数据。另一个是不经常更改的数据。这是因为我们可以通过 CLUSTER 命令控制页面中行的位置。
让我们回到我们的混合泳示例。它在磁盘上的行按 n 列升序排序，因为这是我们插入它们的顺序。如果我们想按描述列排序怎么办？答案是通过索引描述列和聚类对表进行物理重新排序。
CREATE INDEX description_idx ON medley USING btree (description);
CLUSTER medley USING description_idx;
现在，选择第一页中的所有行将按描述的字母顺序返回。如果表发生更改，则新行将按字母顺序追加，但只要表不更改，返回的项目就可以了。它也可以在更改后定期重新聚类，尽管此操作会锁定表，并且在用户需要访问它时无法完成。
最后，可以使用表的总字节大小确定表的总页数。
SELECT pg_relation_size('medley') / current_setting('block_size')::int;
何时使用：TID 扫描
当需要快速深度随机页面访问并且不需要过滤时。特别适用于具有低方差行宽的仅追加时间序列数据。
带有估计书签的键集
正如我们所看到的，普通键集分页不提供将一定百分比跳转到结果中的工具，除非通过客户端猜测。但是，PostgreSQL 统计信息收集器维护每列的值分布直方图。我们可以将这些估计值与限制和小偏移量结合使用，以通过混合方法获得快速的随机访问分页。
首先，让我们看一下混合泳的统计数据：
SELECT array_length(histogram_bounds, 1) - 1
FROM pg_stats
WHERE tablename = 'medley'
AND attname = 'n';
在我的数据库中，n 列有 101 个边界标记，即边界标记之间的 100 个范围。特定的值并不太令人惊讶，因为我的数据是均匀分布的
{719,103188,193973,288794, … ,9690475,9791775,9905770,9999847}
请注意，这些值是近似值。第一个数字不完全为零，最后一个数字也不完全是一千万。范围将我们的信息划分为块大小 B = 10，000，000 / 100 = 100，000 行。
我们可以使用 PostgreSQL 统计收集器中的直方图范围来获取概率正确的页面。如果我们选择W的客户端页面宽度，我们如何请求第i页？它将驻留在块 iW / B 中，偏移 iW % B。
选择 W=20，让我们从混合表中请求第 270，000 页。请注意，PostgreSQL 数组是基于 1 的，因此我们必须调整数组查找中的值：
WITH bookmark AS (
SELECT (histogram_bounds::text::int[])[((270000 * 20) / 100000)+1] AS start,
(histogram_bounds::text::int[])[((270000 * 20) / 100000)+2] AS stop
FROM pg_stats
WHERE tablename = 'medley'
AND attname = 'n'
LIMIT 1
)
SELECT *
FROM medley
WHERE n >= (select start from bookmark)
AND n < (select stop from bookmark)
ORDER BY n ASC
LIMIT 20
OFFSET ((270000 * 20) % 100000);
这执行得非常快（请注意，这里的偏移量恰好为零）。它给出 n = 5407259 到 5407278 的后排行。第 270000 页上的真值是 n = 5400001 到 5400020。这些值偏离了 7239，或大约 0.1%。
我们很幸运地选择了那里的页面。相比之下，第 74999 页要求偏移量为 99980。我们确实知道我们的偏移量最多为 100，000。如果我们愿意做出权衡，上限在我们的控制范围内。通过调整PostgreSQL统计收集器，我们可以得到更精确的列直方图
ALTER TABLE medley ALTER COLUMN n SET statistics 1000;
VACUUM ANALYZE;
现在有 1000 个而不是 100 个直方图桶。在我的数据库中，它们有值
{10,10230,20863, …, 9980444,9989948,9999995}
使用此存储桶大小，我们的偏移量最多为 10，000。权衡是查询规划器现在必须查看更多值，从而减慢速度。因此，这是潜在的偏移效率低下与查询规划器开销的权衡。
这种混合键集/偏移方法可能与许多实际的分页用例不符。它不适用于 where 子句。这是不准确的，当表更改并且统计信息收集器最近未运行时，情况会变得更加准确。
何时使用：带书签的密钥集当客户端想要深度但近似的随机访问而不允许额外过滤时。
结论
与许多工程决策一样，选择分页技术需要权衡取舍。可以肯定地说，键集分页最适用于具有有序线性访问的普通站点。然而，即使是极限偏移也有其优势，更奇特的技术为某些类型的数据提供了特殊的性能特征。你可以看到有很多可能性。为工作选择合适的工具，不要让分页成为一本封闭的书。