分表分库下的分页方案

为什么分表分库这里就不说了，聊一下在这种场景下如何进行分页查询。

现有方案

业界难题-“跨库分页”的四种方案 里提了四种方案，这里线逐个分析一下：

方案1: 全局视野法

这种方法获取的结果是绝对准确的，但是缺点正如文章里所说：随着翻页的进行，性能越来越低。

方案2: 业务折衷法-禁止跳页查询

这种方案结果也是准确的，并且每次查询的性能也是稳定的。缺点是不能随机跳转到某页。
但是考虑一下用户需要跳转的任意页面动机，我们是不是可以通过查询条件的方式满足用户这方面的需求？比如显示的条目是按照时间递增排序的，当前显示的条目时间是2019/08/01，用户想看2019/08/10号的数据，然后心里估算了一下大约在第10页，然后想直接跳转到Page 10。那么我们是不是可以通过提供一个选择日期范围的功能满足用户的这个需求？

整体来看这种分页方式是最优的，和一些查询功能搭配起来能够满足各种使用场景。

方案3: 业务折衷法-允许模糊数据

如果业务方能够接受，这种方法是没有问题的。但是一定要注意前提：各分库所有非partition key属性，在各个分库上的数据分布，统计概率情况是一致的。
举例来说，业务方使用条目的创建时间排序，现在分两个表A和B，在A表每分钟有10条新纪录写入，B库每分钟只有2条记录写入。那么在页面显示里，页码数越大，不同表返回条目的创建时间差别也更明显。那么如果用户想跳转到某一页找某一天写入的记录，用户心里会怎么估算跳转的页码呢？

这里的模糊指的是：排序顺序不完全准确，但显示的条目不会少，不会重复！

方案4: 终极武器-二次查询法

首先说结论，这个方案是不精确的！

具体操作步骤原文。这里举一个范例说明下为什么是不准的。
现在有两张表A和B，有一列属性名字为priority。A表有1万行记录，priority取值范围为[1,1w]，B表有1万行记录，priority取值范围为[1w+1, 2w]，假设priority属性是唯一的。
现在要按照priority属性排序然后分页，每页10条记录。按照原文的操作步骤，我们来计算一下第1k页的元素。

第一步：
select * from A(B) order by priority offset 5000 limit 5
Priority Range From A: [5001, 5005]
Priority Range From B: [15001, 15005]

第二、三步：
select from A where priority between 5001, 5005
select from B where priority between 5001, 15005

这里的问题：B表的查询返回大量的数据！5005行。

第四、五步：
priority==5001 在全局里的offset是5000。然后上面返回的两个结果集合并排序，得到的offset 1w的记录为 [14996, 15005]。但是从数据集来看，应该返回的是[1w, 1w+10]。
原因是只对"第二、三步"的结果集合并排序，忽略了其他元素的影响。

另外一个问题：返回的每页的数据集，是连续的吗？会遗漏数据吗？
回答是：不是，会遗漏数据，并且会出现重复数据。
我们用反证法想一想，priority属性值唯一，2万条记录，取值范围为[1,2w]。
每页10条元素，共2000页。通过该方案第1000页记录的priority范围为[14996, 15005]。
那么在1-999页，需要显示priority范围为[1,14995]，多于页面能显示的记录数，肯定有条目遗漏。
在1001-2000页，需要显示priority范围为[15006, 2w]，少于页面能显示的条目书，所以肯定要有重复。

我们的方案

我们项目里目前也遇到了类似问题，为什么分表这里不说了。并且有个问题是分表后各个表里的数据分布是不均匀的，我们还做了分库，某些库的网络链接条件特别差，带宽小，延迟高。

我们的思路是利用计数排序的思想。举个例子，还是有一列整型值priority。

第一步：将记录按照floor(priority / VALUE_LENGTH)分组计数。得到类似如下结果：

priority Range	A表中元素个数	B表中元素个数
[0*VALUE_LENGTH, 1*LAVLUE_LENGHT)	10	20
[1*VALUE_LENGTH, 2*LAVLUE_LENGHT)	4	0
[2*VALUE_LENGTH, 3*LAVLUE_LENGHT)	14	11
...	...	...

第二步：通过第一个的分段计数，我们可以知道 [offset, offset+limit) 的元素的priority值分布区间。然后select id, priority from A(B) where priority between RANGE_BEGIN and RANGE_END。将多表的结果集合并排序后就可以找到分页范围内的元素。
比如在按照上表的结果，每页显示10条记录，我们想查询第4页的结果，可知 offset 30 limit 10 的元素priorityt的范围是 [1*VALUE_LENGTH, 3*LAVLUE_LENGHT)，然后到每张表里查询该范围的记录。

第三步：根据id到各个表里获取完整的原始数据。

每张表都需要三次查询。其中第一步的查询结果可以做缓存。如果range length空间够小，第二步里每张表的查询结果集也不会很大，所以可以直接取完整的数据行，省去第三部的按照id取元素。
整体来看即避免了多次数据查询，也避免了结果集过大。

这种方法也很类似搜索引擎里的架构方案。

另外还有其他一些方案：比如数据分表分库，但是所有的数据的索引保存在一个表里。然后查询时通过索引表获取记录id，然后到各个库/表里获取对应元素。