一、全局视野法

（1）将order by time offset X limit Y，改写成order by time offset 0 limit X+Y
（2）服务层将改写后的SQL语句发往各个分库：即例子中的各取3页数据
（3）假设共分为N个库，服务层将得到N*(X+Y)条数据：即例子中的6页数据
（4）服务层对得到的N乘以(X+Y)条数据进行内存排序，内存排序后再取偏移量X后的Y条记录，就是全局视野所需的一页数据

方案优点：

通过服务层修改SQL语句，扩大数据召回量，能够得到全局视野，业务无损，精准返回所需数据。
支持跳页查询，直接跳转到指定页面。

方案缺点：

每个分库需要返回更多的数据，增大了网络传输量（耗网络）；
除了数据库按照time进行排序，服务层还需要进行二次排序，增大了服务层的计算量（耗CPU）；
最致命的，这个算法随着页码的增大，性能会急剧下降，这是因为SQL改写后每个分库要返回X+Y行数据：返回第3页，offset中的X=200；假如要返回第100页，offset中的X=9900，即每个分库要返回100页数据，数据量和排序量都将大增，性能平方级下降。

二、业务折中法

“全局视野法”虽然性能较差，但其业务无损，数据精准，不失为一种方案，有没有性能更优的方案呢？
“任何脱离业务的架构设计都是耍流氓”，技术方案需要折衷，在技术难度较大的情况下，业务需求的折衷能够极大的简化技术方案。

1、禁止跳页查询

在数据量很大，翻页数很多的时候，很多产品并不提供“直接跳到指定页面”的功能，而只提供“下一页”的功能，这一个小小的业务折衷，就能极大的降低技术方案的复杂度。

查询第一页数据时需要将查询order by time offset 0 limit 100，改写成order by time where time>0 limit 100。上述改写和offset 0 limit 100的效果相同，都是每个分库返回了一页数据。
服务层得到2页数据，内存排序，取出前100条数据，作为最终的第一页数据，这个全局的第一页数据，一般来说每个分库都包含一部分数据。
点击“下一页”时，需要拉取第二页数据，在第一页数据的基础之上，能够找到第一页数据time的最大值time_max。这个上一页记录的time_max，会作为第二页数据拉取的查询条件。将查询order by time offset 100 limit 100，改写成order by time where time>$time_max limit 100
服务层得到2页数据，内存排序，取出前100条数据，作为最终的第2页数据，这个全局的第2页数据，一般来说也是每个分库都包含一部分数据。
如此往复，查询全局视野第100页数据时，不是将查询条件改写为offset 0 limit 9900+100（返回100页数据），而是改写为time>$time_max99 limit 100（仍返回一页数据），以保证数据的传输量和排序的数据量不会随着不断翻页而导致性能下降。

2、允许数据精度损失

“全局视野法”能够返回业务无损的精确数据，在查询页数较大，例如第100页时，会有性能问题，此时业务上是否能够接受，返回的100页不是精准的数据，而允许有一些数据偏差呢？

数据库分库-数据均衡原理

使用patition key进行分库，在数据量较大，数据分布足够随机的情况下，各分库所有非patition key属性，在各个分库上的数据分布，统计概率情况是一致的。

例如，在uid随机的情况下，使用uid取模分两库，db0和db1：

性别属性，如果db0库上的男性用户占比70%，则db1上男性用户占比也应为70%
年龄属性，如果db0库上18-28岁少女用户比例占比15%，则db1上少女用户比例也应为15%
时间属性，如果db0库上每天10:00之前登录的用户占比为20%，则db1上应该是相同的统计规律
......

利用这一原理，要查询全局100页数据，offset 9900 limit 100改写为offset 4950 limit 50，每个分库偏移4950（一半），获取50条数据（半页），得到的数据集的并集，基本能够认为，是全局数据的offset 9900 limit 100的数据，当然，这一页数据的精度，并不是精准的。

根据实际业务经验，用户都要查询第100页网页、帖子、邮件的数据了，这一页数据的精准性损失，业务上往往是可以接受的，但此时技术方案的复杂度便大大降低了，既不需要返回更多的数据，也不需要进行服务内存排序了。

三、二次查询法

1、查询改写

假设有N个数据库，一页只有5条数据，查询第201页的SQL语句为select * from T order by time offset 1000 limit 5;

将select * from T order by time offset 1000 limit 5 修改成 select * from T order by time offset 1000/N limit 5。假如有3个数据库，SQL就是select * from T order by time offset 333 limit 5
假设这三个分库返回的数据(time, uid)如下：

1.jpg

可以看到，每个分库都是返回的按照time排序的一页数据。

2、找到所返回3页全部数据的最小值

第一个库，5条数据的time最小值是1487501123
第二个库，5条数据的time最小值是1487501133
第三个库，5条数据的time最小值是1487501143

2.jpg

故，三页数据中，time最小值来自第一个库，time_min=1487501123，这个过程只需要比较各个分库第一条数据，时间复杂度很低。

3、查询二次改写

第一次改写的SQL语句是
select * from T order by time offset 333 limit 5
第二次要改写成一个between语句，between的起点是time_min，between的终点是原来每个分库各自返回数据的最大值：

第一个分库，第一次返回数据的最大值是1487501523
所以查询改写为
select * from T order by time where time between time_min and 1487501523

第二个分库，第一次返回数据的最大值是1487501323
所以查询改写为
select * from T order by time where time between time_min and 1487501323

第三个分库，第一次返回数据的最大值是1487501553
所以查询改写为
select * from T order by time where time between time_min and 1487501553

相对第一次查询，第二次查询条件放宽了，故第二次查询会返回比第一次查询结果集更多的数据，假设这三个分库返回的数据(time, uid)如下：

3.jpg

可以看到：
由于time_min来自原来的分库一，所以分库一的返回结果集和第一次查询相同（所以其实这次访问是可以省略的）；
分库二的结果集，比第一次多返回了1条数据，头部的1条记录（time最小的记录）是新的（上图中粉色记录）；
分库三的结果集，比第一次多返回了2条数据，头部的2条记录（time最小的2条记录）是新的（上图中粉色记录）；

4、在每个结果集中虚拟一个time_min记录，找到time_min在全局的offset

4.jpg

在第一个库中，time_min在第一个库的offset是333
在第二个库中，(1487501133, uid_aa)的offset是333（根据第一次查询条件得出的），故虚拟time_min在第二个库的offset是331
在第三个库中，(1487501143, uid_aaa)的offset是333（根据第一次查询条件得出的），故虚拟time_min在第三个库的offset是330
综上，time_min在全局的offset是333+331+330=994

5、既然得到了time_min在全局的offset，就相当于有了全局视野，根据第二次的结果集，就能够得到全局offset 1000 limit 5的记录

5.jpg

第二次查询在各个分库返回的结果集是有序的，又知道了time_min在全局的offset是994，一路排下来，容易知道全局offset 1000 limit 5的一页记录（上图中黄色记录）。
是不是非常巧妙？这种方法的优点是：可以精确的返回业务所需数据，每次返回的数据量都非常小，不会随着翻页增加数据的返回量。
不足是：需要进行两次数据库查询。

跨库分页排序