基于游标的分页
文档版本
| 编辑者 | 版本 | 变更日期 | 变更说明 |
|---|---|---|---|
| Neko | v1.0.1 | 2022-09-30 | 替换用词和错误的 SQL 解释 |
| Neko | v1.0.0 | 2022-09-07 | 创建 |
说明
在 GraphQL 分页最佳实践[1]中会提到两个关键的 query 查询参数，分别是：
first（本次查询所获取的条目数）before（自字面量所选中的行开始，将该行的前一行做为本次查询的最后一行）after（自字面量所选中的行开始，将该行的下一行做为本次查询的第一行）
在这其中，first 所表达的含义其实和我们日常分页需求中所需要实现的 LIMIT 语句或是 pageSize 参数是类似的，它用来控制返回的数据条目的数量；before 和 after 所表达是游标所指向的字段字面量值。 比如填写 first: 10, before: 100 作为参数的时候，其表达了：选中 id 为 100 的行，并将 id 为 100 的行之前的 10 条数据按排序规则和筛选规则查询并返回到查询客户端，如果表格是正序排列，那么此刻应该返回 [89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]； 反之，如果填写了 first: 10, after: 100 作为参数的时候，其表达了：选中 id 为 100 的行，并将 id 为 100 的行之后的 10 条数据按排序规则和筛选规则查询并返回到查询客户端，如果表格是正序排列，那么此刻应该返回 [101, 102, 103, 104, 105, 106, 107, 108, 109, 100, 101]。
在 Postgres 中我们应该如何实现这样的查询呢？
如何查询
常见的实现
我们最常使用的分页查询一般遵循下面的 SQL 语句：
SELECT
id,
field_1
FROM table1
WHERE field_1 = 1
OFFSET 40
LIMIT 20其表达我们期望从 table1 中选择 id 和 field 两个字段作为返回值，并筛选 field_1 的值为 1 的条目，跳过查询到的表的前 40 行，返回前 20 行的数据。如果上述 SQL 语句中的 LIMIT 后面伴随的值是恒定的 20，那么我们可以推断出现在应该是在查询第 3 页，本页数据要求返回 20 条。
这非常直观，从 SQL 语句当中我们能读到语义化的查询和分页过程，但是其实这样的分页模式也有一些不好的点。
弊端
OFFSET 在大表中的查询效率问题[2]
其中最关键的是 OFFSET。OFFSET 在大表的查询中，要求数据库对表内条目注意扫描并且在内存中计数，只有达到了我们所设定的 OFFSET 的值之后的数据才会被数据库返回回来[3]。 这意味着如果查询的页数和页面大小非常大，比如 2022 页，每页 50 条数据的情况下，我们可以说现在数据库需要扫描 100000 条以上的数据才能开始为我们读取需要返回的数据并加以返回，在这样的极端情况下，查询会变的很慢。 虽然这样的场景在绝大多数面向 C 端用户的互联网产品中不太容易出现，但是也许会有软件工程师或是数据库设计师依然会需要去考虑类似的场景。
分页条目出现重复或是偏移
分页在产品使用中可能会遭遇的另一个最大的问题就是分页条目可能出现偏移的问题。举个例子：
- 我们假设现在有数据：
[1, 2, 3, 4, 5, 6] - 我们说查询的时候倒序排列所有数据：
[6, 5, 4, 3, 2, 1] - 客户端 A 请求第 1 页，每页大小为 3，此时获取到了数据：
[6, 5, 4]，是正常的 - 系统新增了一条新数据，此时总数据变更为：
[7, 6, 5, 4, 3, 2, 1] - 客户端 A 请求第 2 页，每页大小为 3，此时将会获取到数据：
[4, 3, 2]
此刻我们对比客户端 A 上拿到的两页数据，发现实际上是总共获取到了 [6, 5, 4, 4, 3, 2]，4 这个条目出现了两遍，同样的数据在第二页上的第一行中再次出现了。 对于这种情况而言我们是不太好用 OFFET 和 LIMIT 去简单解决的，也许会需要引入额外的 WHERE 条件进行筛选。
章节小结
综上所述，普通的 OFFET 和 LIMIT 语句的搭配使用在这两种情况的任意一种当中已经不太适合我们继续去实现分页了。 唯一能解决上述问题的办法，就是先尽量避免使用 OFFSET，其次是去创建一个分页所对应的「锚点」，以此实现一个能够执行「指向某个特定行的指针，通过该指针构建表的上下文，从而进行分页」任务的查询方法，比如我们能够说我们上一次获取的最后一条数据是 4，那么无论前面有多少新增数据，数据库都应该从 4 这条数据之后开始返回，而不是固定地、死板地分页，然后出现重复的情况。 也许你可能会想说，「锚点」或者说「游标」、「指针」不是很好实现嘛，直接传递主键，然后对着主键比大小就好了？确实，对于按主键排序的数据而言，这是能解决问题的，但是不巧的是，在很多场景下，分页往往会伴随很多筛选和排序的规则，如果排序的规则复杂起来，那么直接采用主键 ID 作为「锚点」的话就会出现不匹配排序规则的情况，从而导致数据乱序和混杂。 我们需要引入别的方式方法来解决问题。
可能的实现
我们可以查阅 PostgreSQL 的文档发现，数据库除去我们最熟悉的 OFFET 和 LIMIT 语句可以被用来实现分页以外，还有两个功能可能可以为我们提供解决上述两种问题：
ROW_NUMBER() OVER()CURSOR
不过可惜的是，这两种方法实际上都有各自较大的缺陷。
对于 ROW_NUNBER() OVER() 语句而言，小型的查询和低频次的数据库访问不会有太大的影响，但一旦查询所包含的临时表内容增多，就会增大内存开销。在实际的测试中，ROW_NUNBER() OVER() 的效率也会很低，差距在 15 倍到 3 倍不等[4]。 对于 CURSOR（游标）而言，每次使用 CURSOR 的时候都需要在数据库运行时中创建一个临时的内存空间来存储其相关的数据，这些相关的数据当中就包含了需要游标读取的表内容，并且还有可能会锁住行，甚至是整张表，如果使用不当的话，则有可能出现阻塞甚至死锁的情况[5]。与此同时，当 CURSOR 被声明时，新的数据库连接会保持开放，方便重新复用游标，在处理和维护不妥的情况下这可能会导致数据库连接数量过多而影响整体 IO 性能[6]。游标更适合在大数据中、连接客户端少的场景中使用，比如数据分析、数据挖掘等大数据场景；但是对于日常开发所面临的常规业务场景，我们通常会有数十甚至上百个服务的 replicas 被同时部署，这将会创建非常多的数据库连接和 CURSOR 调用消耗，进而影响整体数据库性能。
不过也不是说除此以外就没有别的实现方式了。
解决方案
密钥集分页/键集分页
有这么一个查询实践，它被称之为密钥集分页（Keyset Pagination），或者说键集分页，它也被称之为 seek method（搜寻方式），是基于游标分页的一种实践。为了避免歧义，此处我们再次进行说明：在本文中我们所讨论的游标实际上是指「指向某个特定行的指针，通过该指针构建表的上下文，从而进行分页」。 要理解这个新的查询实践，我们知道为了解决上述我们所提出来的所有问题，因为 ROW_NUMBER() OVER()，CURSOR，和 OFFET 或多或少都有点影响实际运行效果的缺陷，我们需要避免使用这三个语句。我们此刻引入的概念也能实现游标的部分功能，进而完全解决了我们的问题。
密钥集分页/键集分页的名字看起来很怪，但是我们可以暂时抛开这个名字，专注于它是如何解决问题的。它遵循下面的规则：
- 我们希望筛选的是表中靠后的数据
- 对于单个字段筛选而言，我们使用
WHERE (single_field >= ?)的公式。 - 对于多个字段筛选而言，我们使用
WHERE (field_1, field_2) > (?, ?)的公式， - 语句中的
>=号、>号和我们期望查询的方向应当是同步的，如果ORDER BY使用的是DESC降序，且我们要查询的数据是靠后的，此处就应该填写<=或是<，反之，应该填写>=或是> - 公式中的顺序应当和
ORDER BY所排序的字段优先级顺序一致 - 如果
ORDER BY中的语句排序规则各不相同，可以使用拓展写法
所以假设我们现在有一个邮件列表，邮件列表的筛选规则是 ORDER BY received_at DESC, subject DESC，其含义是按邮件接受时间倒序排列，如果时间相同，根据邮件主题倒序排列，且上一页的最后一个项目的收件时间是 2022-09-07，收件主题是 A test mail 那么我们在实现密钥集分页/键集分页时就应该在查询中包含 WHERE (received_at, subject) > ('2022-09-07', 'A test mail')，这样就能筛选到我们分页的锚点在哪里了。
这个公式本质上是 PostgreSQL 封装的 SQL 方言，如果我们要使用拓展写法的话，应该对照下面的转换案例进行转换[7]：
WHERE (x, y) > (a, b)等同于
WHERE
(x > a) AND
(x = a AND y > b)或者超多字段[8]
WHERE (x, y, z) > (a, b, c)等同于
WHERE
(x > a) OR
(x = a AND y > b) OR
(x = a AND y = b AND z > c)在我们看到了拓展写法的时候，我们也许就能理解为什么这样的公式能够查询到锚点了： 它本质上是在筛选出符合我们所填写的值和大小规则相匹配的行，筛选的规则就是枚举出所有可能的排序情况。
另外，之所以规则中包含了一条「公式中的顺序应当和 ORDER BY 所排序的字段优先级顺序一致」，也是因为在拓展中我们能看到，最后一个字段 y 或者第二个例子中的最后一个字段 z 他们不会有额外的相等 = 判断，而是只有我们所填写的大于号 >、小于号 > 的判断，这意味着靠前的字段是有可能出现相同数值的，而最后一个字段之后已经不再有额外的排序字段了，意味着他们要么相等，要么有次序地排列着，所以不再需要有 = 号的判断。
延伸阅读
Faster SQL Pagination with jOOQ Using the Seek Method – Java, SQL and jOOQ.
How To Do Pagination in Postgres with Golang in 4 Common Ways | by Iman Tumorang | Easyread | Medium
Implementing pagination in GraphQL and Go using gqlgen | by Chris Czurylo | Medium
DECLARE CURSOR - PostgreSQL 中文文档
贡献者
絢香猫页面历史
GraphQL Cursor Connections Specification 中提到一个返回 ConnectionType 的字段必须包括前向分页参数（first）、后向分页参数（after）或两者。这些分页参数允许客户端在返回之前对边缘集进行分页。 ↩︎
在网站 MySQL ORDER BY / LIMIT performance: late row lookups at EXPLAIN EXTENDED 中详细阐述了该问题的深层原因。 ↩︎
较高的偏移量是正常的，因为查询需要计算出第一个
OFFSET + LIMIT记录（并且只取其中的LIMIT）。这个值越高，查询运行的时间就越长。在 Why does MYSQL higher LIMIT offset slow the query down? - StackOverflow 中由 Nikos Kyr 回答，Elzo Valugi 编辑修正。 ↩︎当数据量在 100 时，
ROW_NUNBER() OVER()语句相较于OFFET语句慢了 15.5 倍，当数据量在 480000 时，ROW_NUNBER() OVER()语句相较于OFFET语句慢了 8.6 倍，当数据量在 999900 时，ROW_NUNBER() OVER()语句相较于OFFET语句慢了 3.97 倍。在 OFFSET vs. ROW_NUMBER() - StackOverflow 中由 zzzeek 回答。 ↩︎在 Why is it considered bad practice to use cursors in SQL Server? 由 Josef 回答 ↩︎
在 pagination - Using "Cursors" for paging in PostgreSQL - Stack Overflow 由 Craig Ringer 回答 ↩︎
在 sql server - Generic SQL predicate to use for keyset pagination on multiple fields - Stack Overflow 由 The Impaler 回答 ↩︎
在 server - Generic SQL predicate to use for keyset pagination on multiple fields - Stack Overflow 中由 Jake Z 回答 ↩︎