Cobar在分库场景下提出的OrderBy/Limit的优化转载本文请联系捕虫大师公众号。虽然Cobar是一个“老”的数据库中间件，但它仍然被很多公司使用，它包含了很多有趣的算法和实现。今天分享一个Cobar在分库场景下提出的方法。OrderBy/Limit优化。算法原说明参考：https://github.com/alibaba/cobar/blob/master/doc/cobarSolution.ppt背景Cobar最重要的功能就是分库分表。通常读取性能的瓶颈可以通过增加从库或者缓存来解决。但是MySQL的写性能只能通过分库分表来提高。当我们将数据分布到不同的数据库时，如果是单条数据，我们只需要找到这条数据对应的数据库即可，但是如果是多条数据，可能分布在不同的数据库上，Cobar需要先查询，然后聚合。举个具体的图例子：如果我们要查询tb1表的c1字段，取c1的正序下标（从0开始）为4和5的数据，假设有三个子-数据库，为了得到正确的数据，我们需要去三个分库中获取下标为0-5的数据，假设取到如下数据：得到3堆排序后的数据，对这3堆进行丢弃data0,1,2,3从data开始，保留data4和5，这就是我们需要的。这个算法貌似没问题，但是如果数据量稍有变化，比如：selectc1fromtb1orderbyc1limit9999999,4如果还是按照上面的方法，就得先去各个分库查询0-10000003数据，然后合并丢弃0-9999998数据。相当于在不分库的情况下丢弃了大约三倍的数据。这似乎有点浪费。算法优化Step1：将这条语句拆分成3条语句分别发送到3个分库：Step2：求查询结果的最大值和最小值，假设最小值为3，最大值为11Step3：使用minimumvalue和maximumvalue再次查询假设我们得到的数据如图所示，那么我们是不是很容易推断出这些结果之前有多少数据呢？Step4：找出每条返回结果的偏移量，这里可以推断出子库1最小值前有3333332条数据，子库2最小值前有3333333条数据，子库2最小值前有3333331条数据最小值之前的子库3中的数据。这时候我们就可以舍弃0-9999998的合并数据了，分库1、2、3舍弃最小值之前的所有数据，舍弃0-9999995的数据，然后舍弃3个最小值.3正好够到9999998，所以9999999的数据依次是4、5、5。6.算法分析效率上面的例子说明了优化前：1次查询，查询数据总量约3kw，丢弃9999999条数据优化后：第一次查询，查询数据总量约1kw第二次查询，数据一共丢弃了3条数据从这个例子可以看出查询数据量大大减少，需要计算的丢弃数据量也大大减少。不理想的情况大家可能都看出来了。上面的例子是一个非常理想的情况。如果数据不是那么“理想”，结局是什么？Step4中反向校验前的最小值不足以丢弃怎么办？在这两种情况下，该算法都不会再次起作用。优化的前提根据以上两种情况，可以得出算法生效的前提是：数据（排序字段）在各个分库上的分布要均匀。其实可以做一个极端的假设，比如只有第一个子数据库上面有数据，而其他数据库没有数据，那么这个算法就失效了。综上所述，这个算法是不是没用？确实没用，连科巴都用不上。但是在某些场景下，还是有比较大的提升。分库中的大部分数据都是按字段建模的，因此可以认为几乎是均匀分布的。这时候如果OrderBy/Limit是比较深的翻页Data，可以采用这种策略，但是也需要覆盖底线。如果返回的数据不满足条件，就会继续退化到原来的算法，所以单次效率可能不高，但是从统计的角度来看，它的效率可能会更高。
