分页方式和API分页的优化

分页器是应用程序中一个非常常见的功能,本文对比了PC和APP时代下,对分页器的不同要求,从而找出一种适合当下需求的优化方案。

传统SQL分页

SQL在设计的时候就考虑了分页器这种场景,那就是LIMIT OFFSET语句,下面例子就是每页十个,分别查询1、2、3页的场景。

SELECT * FROM users ORDER BY id LIMIT 10 OFFSET 0;
SELECT * FROM users ORDER BY id LIMIT 10 OFFSET 10;
SELECT * FROM users ORDER BY id LIMIT 10 OFFSET 20;
...

我们很容易把他公式化,第N页的条件就是 LIMIT PageSize OFFSET (N-PageBase)*PageSize。这里两个变量PageSize好理解,表示分页长度,PageBase表示起始页,正常情况都是1,如果有分表的场景,比如前100页在一个表,100页之后在另一个表,那就在查100页之后的时候设置PageBase为100即可无缝衔接而不需要其他处理。

LIMIT OFFSET的分页方式在PC时代大行其道,好处一是分页的概念也符合纸张时代的习惯,二是实现简单,而且可以支持直达,比如直接转到第100页都很容易。但是他也有一个弊端,那就是对于一张超大表来说,分页越往后查询时间会越长。因为OFFSET永远都是从0开始数的,比如你执行LIMIT 10 OFFSET 100000数据库会根据查询条件筛出数据,然后从第0个开始,找到第100000个,然后拿出10个,这部分基本无法优化,因为索引基本只能优化到WHERE和ORDER部分,OFFSET基本靠遍历。所以OFFSET等于0是最快的,数据库直接返回开头的数据,OFFSET越大,数据库需要遍历的数据也越多,意味着无谓的开销越大。

一种冷门的优化方式

同样基于主键索引,SELECT只查询主键或索引中的字段效率会高:

SELECT * FROM users ORDER BY id LIMIT 1 OFFSET 500000;   
# 1197ms
SELECT id FROM users ORDER BY id LIMIT 1 OFFSET 500000;  
# 307ms

以上两个查询是基于我的一个数据库测得,相差3倍,原理与Inno DB的索引存储有关。如何利用这个特性来提升速度就不再赘述了。但其实3倍的提升,对数据库来讲只能说还行吧。下面重点分析一种百倍以上的优化方式。

让OFFSET也用上“索引”

这里的索引打引号,其实OFFSET无法使用索引,但是我们可以利用索引避免OFFSET,下面咱们用WHERE条件结合索引来实现前面例子的效果。可以用下面方式:

SELECT * FROM users WHERE id>0 ORDER BY id LIMIT 10 OFFSET 0;
SELECT * FROM users WHERE id>10 ORDER BY id LIMIT 10 OFFSET 0;
SELECT * FROM users WHERE id>20 ORDER BY id LIMIT 10 OFFSET 0;

...
SELECT * FROM users WHERE id>10000 ORDER BY id LIMIT 10 OFFSET 0;

因为id这个字段是有主键索引的,因此在WHERE条件里面可以很快的定位,这个时间复杂度不会大于O(logN),而分页条件这里,全部避免了OFFSET,直接拿出符合条件的前十个。

但是这个例子显然太特别了,必须要按照id排序,同时结果中的id必须连续才可以准确实现传统的分页器效果。假设WHERE条件里面加一个只查女生的条件,我要直达第十页,id应该从哪里开始?的确,分页直达的实现是这种方案的最大缺陷,但是在APP时代这个问题就显得不那么重要,因为你很少会看到哪个APP做了跳转到第十页这种功能,APP永远是feed流,所有的分页都必须是连续的1、2、3、4、5….。所以APP的分页参数就不必用page了,这个例子中,我们只需要把上一页的结尾id带过来即可,当然这里依然有一个必要条件就是结果必须按照id排序,而且id必须唯一才可以。

上面例子中id是主键,肯定具有唯一性。我们看下面这个表,尝试用不唯一的字段score倒序排序。这时候问题来了,如果每页两个,那么第二页的score条件应该怎么设置呢,如果score<2那么可能会漏掉一个人,如果score<=2就会有一个重复。

id   |   name    |    score
1    |   alice   |    2
2    |   bob     |    1
3    |   coder   |    2
4    |   david   |    3

因此,用这种分页方式,必须要保证排序字段的唯一。那么这个例子是不是就无法优化呢,其实也是可以的。

处理不唯一字段和多维排序

那么我们想想用传统的LIMIT OFFSET语句怎么处理score排序的场景,其实用这种方式要想确保不出问题也得引入多维排序,否则某些数据库对相同值的排序结果可能每次也不尽相同。

SELECT * FROM users ORDER BY score DESC, id DESC LIMIT 2 OFFSET 2;

我们继续用上面的思想对这个查询优化,基于score, id两个排序字段,构造一个新的排序字段score_sort。他的值由score和id生成。

id   |   name    |    score   |  score_sort
1    |   alice   |    2       |   2001
2    |   bob     |    1       |   1002
3    |   coder   |    2       |   2003
4    |   david   |    3       |   3004

这样我就可以用上面的方式对分页做优化了

SELECT * FROM users WHERE score_sort<MAX_INT ORDER BY score_sort DESC LIMIT 2 OFFSET 0;
SELECT * FROM users WHERE score_sort<2003  ORDER BY score_sort DESC LIMIT 2 OFFSET 0;

这里我只给id留了3位数,id作为自增字段不可能只有3位的。因为我做了一个预估,同一个score的用户最多的情况也远小于1000,因此我们只需要把id对1000取余,只要能避免重复即可,因为我们主需求是对score排序,id的引入基本是为了避免排序出错。如果数据库不支持bigint,留给id的位置越少那就留给score的越多,我们要优先满足第一排序的字段。在数据库允许的情况下,我们尽量保证每个参与排序的字段都完整加入。

当然,避免溢出更保险的做法是把score_sort转成字符串,字符串的排序请自行了解字典序。score_sort用字符串的话要求你必须对第一排序字段也要预估范围,事先固定好字符串的长度才行,否则可能出现”9″>”10″的情况。下面例子我预估score和id都在7位整型以内。

id   |   name    |    score   |  score_sort
1    |   alice   |    2       |   "00000020000001"
2    |   bob     |    1       |   "00000010000002"
3    |   coder   |    2       |   "00000020000003"
4    |   david   |    3       |   "00000030000004"

预估越大,字符串越长,带来的存储空间浪费和性能损失也越多,越小则越容易溢出,所以这个预估务必准确平衡。另外,还可以使用进制转换,把10进制转成62进制[0-9A-Za-z],这样可以很大的节省字符串长度,优化存储和查询效率。

其实,现在最新的数据库大都可以支持big int了,换算成十进制可以有20位以上,因此大部分场景都应该尽量避免用字符串。其实上面例子使用十进制的拼接只是为了方便解说,但是对计算机来说并不友好,我们完全可以用二进制,令score_sort = (score << 32) + id,就可以实现二进制的拼接,计算更快,bit利用率更高。

NoSQL分页

NoSQL为了性能,没有SQL那么多的查询特性,但是基本上都支持range或scan的查询方式,其实也就是上面那种设置值大于或小于某个值的形式。有兴趣的朋友可以查看我的另一篇文章《理解redis SCAN》

没有银弹

没有银弹就是说没有一种方式可以解决所有问题,我们在制定编程方案的时候,也要认识到这个问题,下面总结一下LIMIT语句和RANGE两种分页的优缺点:

LIMIT OFFSET: 方便,可以任意指定排序字段和排序方式,任意指定跳转的页数。缺点是偏移量offset的处理需要耗费较多的计算资源,传统的分页器通常还会有一个COUNT查询,获取总的记录条数和页数,这也是容易产生瓶颈的地方。

RANGE:快速,通常会基于索引快速定位数据,也可以不必计算总结果数,因为分页到结果数小于PageSize的时候就是分页结束的时候。缺点灵活度不够,不能任意排序,必须专门针对排序场景,对字段做组合唯一处理;不支持任意页数的跳转,必须基于前一页的分页结果递推下一页。

其实这个规律也是计算机世界的普遍规律,就像空间时间的互换规律一样,要满足灵活性,就不能满足高性能,满足高性能就一定会损失灵活性。

值得一提的是在APP的影响之下,许多面向PC的分页方式也逐步换成feed流的形式而去掉了分页直达这种功能。

发表评论