优质博文：IT-BLOG-CN
背景：我们系统上云后，数据根据用户UDL部分数据在国内，部分数据存储在海外，因此需要考虑分库查询的分页排序问题
一、分库后带来的问题
需求根据订单创单时间进行排序分页查询，在单表中的查询SQL如下(省略部分查询内容)：每页获取10条记录
sql">select orderId, orderStatus from t_order order by create_time asc limit 20, 10；
我们做了分库之后，如果需要完成上述的需求，需要在两个表中直接执行如下两条SQL：offset都需要从0开始，否则数据就不正确了。我这里为了区分，表的名字后面带上对应的环境，实际生产sql是一样的，只是查询的库不同而已。
sql">select * from t_order_sha order by create_time asc limit 0,30;select * from t_order_fra order by create_time asc limit 0,30;
如上所示：我们需要将前3页的数据全部查出来，然后在内存中重新排序，最后从中取出第3页的数据，也称为“全局查询法”。
该方案存在的问题： 随着页码的增加，每个节点返回的数据会增多，性能也随着下降。同时，服务层需要进行二次排序，增加了服务层的计算量，如果数据过大，对内存和cpu的要求也非常高。
不过这种方案也有很多优化方案，Sharding-JDBC中就对此方案做出优化，采用的是流式处理和归并排序避免内存的过量占用。
二、禁止跳页查询法
我们部分系统（航班列表页）是通过点击“更多”按钮展示下一页的数据（只提供了查询下一页的功能），此时页面上展示的是前n页的数据集。
上述的功能在分库分页查询的情况下，可以极大的降低业务的复杂度，因为当查询第二页数据的时候，可以将上一页的最大值最为查询条件，此时的SQL可以改写为：
sql">select * from t_order_sha where create_time>1726671336 order by time asc limit 10;select * from t_order_fra where create_time>1726671336 order by time asc limit 10;
查询到数据后需要在内存中进行重新排序，但相对于“全局查询”数据量已经减少了很多，页码越大性能提升越明显。此方案的缺点也非常明显：不能跳页查询，只能一页一页查询。
三、二分查找法
二分查找法既能满足性能要求，也能满足业务要求，不过相对前面两种方案理解起来比较困难。
我们还是以上述的查询语句为例（这里为了演示方便，修改为查询第二页，每页返回5条数据）：
sql">select orderId, orderStatus from t_order order by create_time asc limit 5, 5;
【1】SQL改写： 原先的SQL的offset=5，称之为全局offset，这里由于是拆分成了两张表，因此改写后的offset=全局offset/2=5/2=2
核心思想：第一页的5数据肯定包含在t_order_sha或t_order_fra表中的二分后的0-2之中
最终的落到每张表的SQL如下：
sql">select * from t_order_sha order by create_time asc limit 2,5;select * from t_order_fra order by create_time asc limit 2,5;
红色部分表示查询结果
| t_order_sha | t_order_fra |
|---|---|
| 00000000001 | 00000000002 |
| 00000000003 | 00000000008 |
| 00000000004 | 00000000009 |
| 00000000005 | 00000000010 |
| 00000000006 | 00000000011 |
| 00000000007 | 00000000012 |
| 00000000013 | 00000000014 |
| … | … |
【2】返回查询数据中的最小值： t_order_sha = 00000000003 (这个过程只需要比较各个分库的第一条数据，时间复杂度很低)
【3】查询二次改写： 第二次查询使用beteween语句，起点是第二部返回的最小值，终点是每个表第一次查询后的最大值。
t_order_sha 这张表，第一次查询的最大值00000000013，则SQL改写后：
java">select * from t_order_1 where time between 00000000004 and 00000000013 order by time asc;
t_order_fra 这张表，第一次查询的最大值00000000014，则SQL改写后：
java">select * from t_order_1 where time between 00000000004 and 00000000014 order by time asc;
红色部分为第次的查询结果
| t_order_sha | t_order_fra |
|---|---|
| 00000000001 | 00000000002 |
| 00000000003 | 00000000008 |
| 00000000004 | 00000000009 |
| 00000000005 | 00000000010 |
| 00000000006 | 00000000011 |
| 00000000007 | 00000000012 |
| 00000000013 | 00000000014 |
| … | … |
在每个结果集中虚拟一个time_min记录，找到time_min在全局的offset。
下图蓝色部分为虚拟的time_min，红色部分为第2步的查询结果集。
| t_order_sha | t_order_fra |
|---|---|
| 00000000001 | 00000000002 |
| 00000000003 | 00000000004 |
| 00000000004 | 00000000008 |
| 00000000005 | 00000000009 |
| 00000000006 | 00000000010 |
| 00000000007 | 00000000011 |
| 00000000013 | 00000000012 |
| 00000000014 | |
| … | … |
t_order_sha中的第一条数据就是time_min，则offset=3。
t_order_fra中的第一条数据为00000000008，这里的offset为2，则向上推移一个找到了虚拟的time_min，则offset=1。
那么此时的time_min的全局offset=1+3=4。
【5】查找最终结果： 找到了time_min的最终全局offset=4之后，再根据第2步获取的两个结果集在内存中重新排序。
[00000000004,00000000005,00000000006,00000000007,00000000008,00000000009,00000000010,00000000011,00000000012,00000000013,000000000104]
现在time_min也就是00000000004的offset=4，那么原先的SQL：select * from t_order order by time asc limit 5,5;，此时可以发现SQL中的总偏移量和最小值的偏移量的差值5-4=1，因此需要对排序后的结果集向后推移一位取值。同时因为最小值也包含在集合中的，无论前面的差值是多少，这里都需要将最小值踢出去，所以也需要再向后移一位。根据SQL取5条数据，就能够得到如下结果：
00000000006,00000000007,00000000008,00000000009,00000000010
这种方案的优点：可以精确的返回业务所需数据，每次返回的数据量都非常小，不会随着翻页增加数据的返回量。
缺点也是很明显：需要进行两次查询。
