前言
在实际应用中, 为了降低单表的数据量, 会对较大的表进行水平切分, 将单表的数据切分到多表多库中.
既然要切分, 就要有一个切分的依据, 比如说按照 ID 取模等. 那么多张表联合分页是如何做到的呢?
如果分表的依据是字段 A, 但是需要根据字段 B 进行分页查询, 针对这种情况应该如何处理呢?
为了后面方便说明, 这里举个例子.
有一个文章表 user_article
其中有一个文章的发表时间
publish_date. 这个时间用户是可以修改的.按照 ID 取模分到了两个表中.
user_article_1 user_article_0
现在有这样一个需求:
按照文章的发表时间进行排序分页
单表
先来看在单表的时候, 我们是如何查询的, 之后再扩展到多表.
select * from `user_article` order by `publish_date` offset 0 limit 10;
单表查询很简单, 一条 sql 搞定.
多表
对于多表的情况, 将其抽象一下, 就是有两个有序列表:
[1, 5, 7, 8, 9]
[2, 3, 4, 6, 10]
现在要取合并后的有序列表第 n 页的数据.
方案一
想到的第一个方案, 将两个列表合并之后, 就可以退化为单列表的情况了.
对应到 sql查询中, 如果要取第三页的数据, 可以肯定的是, 每个列表都不会读到第四页, 所以我们可以将每个表的前三页拿出来, 在内存中进行合并后, 就可以拿到全局的第三页了.
# 取第三页的数据
select * from `user_article_0` order by `publish_date` offset 0 limit 3*10;
select * from `user_article_1` order by `publish_date` offset 0 limit 3*10;
这种方案确实可以获取到分页的数据, 但是查询的数据量随着页数的增大而增大. 如果查询第200页的数据, 那每张表都要返回2000条数据, 性能太低.
方案二
如果说, 我们按照页数依次获取, 中间不跳页的话, 那么就可以将上一次查询的终点保存下来, 供下一次查询使用.
比如, 上一次查询, 最后一条数据是8, 那么, 下一次查询从各个列表中取出大于8的10条数据, 内存排序后取前10条, 同时将最后一条的值存下来供下一次查询使用.
对应到sql查询中, 就需要有一个全局的searchId.
select * from `user_article_0` where `publish_date` > ‘searchId‘ order by `publish_date` limit 10;
select * from `user_article_1` where `publish_date` > ‘searchId‘ order by `publish_date` limit 10;
每页查询数量固定, 效率较高. 但同时, 这种功能方案不能做到跳页, 如果要查询第 n 页的数据, 前提是查询了 n-1页. 同时, 此方案要求 publish_date字段无重复值, 如果有20条相同的publish_date, 在翻页的时候就会丢失部分数据.
方案三
那么, 有没有一种方案, 即能跳页查询, 查询数量也能保持在常量级呢?
说明
来了, 为了方便说明, 先从数组开始:
[1, 3, 5, 7, 11, 18, 23, 32, 41]
[2, 8, 9, 15, 17, 22, 27, 51, 60]
此时, 如果想获取全局: offset 4 limit 4 的数据. 因为我们不知道全局偏移量4在各个数组中的各自偏移量. 所以在方案一中需要进行大量的查询, 如果我们知道了, 问题不就解决了么.
第一步, 分别取各列表半个偏移量的数据
先分别取各个数据中offset 2 limit 4的数据. 结果如下:
[5, 7, 11, 18]
[9, 15, 17, 22]
注意: 这里的offset 2, 是通过全局偏移量/表个数算出来的.
拿到这个数据之后, 我们得到了什么? 其中的最小值5, 全局偏移量必定>=2.
- 如果数据1中小于5的值大于2个, 那么第一次查询时结果必定不同
- 如果数据2中存在小于5的值, 那么5的全局偏移量只会增加.
第二步, 获取最小值的全局偏移量
通过第一步的分析, 如果我们能够知道数据2中存在多少个小于5的值, 那么我们就能够计算出5的全局偏移量. 进而得到全局偏移量为4的数据.
查询数据2中, data > 5 and data < 9的数据, 结果如下:
[8]
前面, 我们知道9在数据2中的偏移量为2. 同时 数据2中, >5 and <9的数据, 个数为1, 计算可得, 数据2中小于5的数据个数为: 2-1=1
又因, 5在数据1中的偏移量为2, 进而可得, 5的全局偏移量为: 2+1=3. (加上数据2中小于5的数量)
第三步, 整合数据并返回
我们将前后查询的结果整合一下, 得到如下数据:
[5, 7, 11, 18]
[8, 9, 15, 17, 22]
再将两数组合并为一个数组:
[5, 7, 8, 9, 11, 15, 17, 18, 22]
已知, 5的全局偏移量为3, 则偏移量为4的数据为7. 我们从7开始, 向后拿4个, 就是全局的offset 4 limit 4的数据了.
[7, 8, 9, 11]
问题
到这里, 你以为已经完成了么? 看下面这组数据:
[1, 2, 3, 4, 5, 6, 7, 8]
[9, 10, 11, 12, 13, 14, 15, 16]
很明显, 这组数据分布十分不均匀, 按照上面的操作获取分页数据offset 4 limit 4
第一步折半查询结果offset 2 limit 4
[3, 4, 5, 6]
[11, 12, 13, 14]
然后拿到3的全局偏移量2. 得到偏移量4的数据为5. 组合后返回结果为:
[5, 6, 9, 10]
这, 明眼人一看, 就知道结果应该是[5, 6, 7, 8].
很明显, 因为数据都在一张表上, 所以导致第一次获取数据没有取完. 但是, 到这一步, 我们获取到的偏移量是没有问题的.
也就是说, 全局偏移量为4的数据为5. 那么, 我们就可以退回到方案二 进行处理了.
当然, 如果对数据的精度要求没有那么高, 或者确信数据分布不会出现这种极限情况, 可以忽略.
貌似网上将这种方法称为二次查询, 没有找到文章提到这个问题, 难道说实际应用中不会遇到么?
sql
将上面方案转为 sql, 取第4页的数据, 既offset 30 limit 10
第一步, 分别取各表数据
select * from `user_article_0` order by `publish_date` offset 30/2 limit 10;
select * from `user_article_1` order by `publish_date` offset 30/2 limit 10;
我们在这一步, 统计出查询结果的最小值 M
第二步, 最小值全局偏移量
下方sql中的 M‘, 代表各个查询结果的最小值.
select * from `user_article_0` where `publish_date`>M and `publish_date`<"M‘" order by `publish_date`;
select * from `user_article_1` where `publish_date`>M and `publish_date`<"M‘" order by `publish_date`;
此时, 通过计算, 我们已经得到M的全局偏移量了. 同时, 也拿到了偏移量30的值S.
如果数据分布十分不均匀, 在这一步, 极端情况会将前面所有数据都拿出来.
第三步, 返回结果
如果确信不会出现前面提到的极限情况, 这里直接组合结果并返回即可.
否则, 继续执行下面查询并返回. 此时, 排序字段不可重复.
select * from user_article_0 where publish_date > S order by publish_date limit 10;
select * from user_article_1 where publish_date > S order by publish_date limit 10;
此方案执行了三倍的数据库查询, 但优点是查询效率恒定与页数无关, 且支持跳页.
方案四
因为我们的数据是按照 ID 取模, 根据概率分布, 两个库的数据分布应该是一样的. 那是不是可以每个表取半页数据, 拿回来拼上.
这样的话, 取第3页数据的 sql为:
select * from user_article_0 order by publish_date offset 20/2 limit 5;
select * from user_article_1 order by publish_date offset 20/2 limit 5;
这样的话, 数据不太准确, 拿到的数据顺序可能不对, 但重点是查询效率高啊. 应该是有对顺序精度没什么要求的场景吧. 想到了这种方案, 但是暂时没有想到应用场景.
如果是针对分表字段排序的话, 那么数据分布均匀, 此方案完美.
最后
具体业务应该如何选择分页方式呢?
- 如果不需要跳页, 直接选择方案二
- 如果对顺序精度没什么要求, 直接选择方案四
- 如果只需要查询前 n 页数据, 且 n 比较小. 那么方案一 可能更适合你
- 如果需要查询所有数据, 且需要跳页, 可以选择 方案一 和 方案三 结合的方式. 优先选择当前效率更高的.
当然了, 前面说的情况, 排序字段与分表字段不同, 数据分布可能不均匀. 如果是相同的字段, 那就没这么多事了, 数据都是均匀分布的, 参考 方案四
最后, 对于排序使用的字段, 最好能够保证其唯一性, 如果不能, order by的时候, 请添加辅助字段排序.