问题描述

最近线上出现了一个问题，查询用户券数据时，发现分页返回有重复值，最后定位到是因为order by(排序)字段有大量重复值导致的。

-- 有数据再第一页和第二页重复出现了
select id from AAA where user_id='123'  ORDER BY invalid_tm desc  limit  0,10;
-- 第二页  
select id from AAA  where user_id='123'  ORDER BY invalid_tm desc  limit 10,10;

很明显，这是由于order by 排序导致的，那么mysql order by排序底层是采用什么机制呢？

order by排序

MySQL支持二种方式的排序，Index和FileSort。

• Index排序：索引排序，即我们通常为了查询建立的索引，也就是说，Mysql能为排序和查询使用相同的索引；
• FileSort：文件排序，当不能使用Index排序时，使用文件排序。FileSort排序有两种方法，堆排序和快速排序。

Index排序使用场景

• where + order by 场景
  如果where 条件字段满足最左前缀，且order by字段也在组合索引字段中，则使用组合索引；
• 只有order by场景
  order by中字段满足组合索引字段排序，则使用组合使用，
• order by id（主键）
  不管有没有where条件，或者where 字段有没有索引，只要order by id，都会使用Index 排序，而不会使用FileSort

其余情况下，使用FileSort排序，可以通过EXPLAIN中的Extra来判断使用哪种排序方式。

image.png image.png

FileSort排序使用场景

在不能使用Index索引排序的时候，使用FileSort排序，FileSort排序有两种方式：

• 堆排序：在排序量不大的情况下，使用堆排序

• 快速排序：在需要大量排序的情况下，使用快排

从执行计划中只能看出来是使用Index排序，还是FileSort排序。而使用堆排序还是快排，是Mysql根据待排序数据量的大小进行切换具体根据函数check_if_pq_applicable进行判定的。

有一个简单的判断，如果使用的是order by limit n ，且在数据量不大的情况下（数据可以在内存中加载），使用的是堆排序；
而当n到了一个数量级的时候会切换成快排，具体使用那种算法是优化器通过函数check_if_pq_applicable进行判定的。
同时，如果没有limit时，就算数据量小，使用的也是快排（这个结论是从下面的参考文章中得出的）。

在大量排序的情况下快速排序是有优势的，而堆排序使用优先队列只完成少量的排序是有优势的，因为它根本不需要排序完成只排序你需要的数据量就可以了，MySQL认为快速排序的速度是堆排序的3倍。

快速排序和归并排序

问题释疑

从导致问题的sql，我们可以判断使用的是FileSort排序中的堆排序。那么为啥堆排序会出问题呢？

因为快速排序和堆排序是不稳定的排序算法，也就是对于重复值是不能保证顺序的。而直接利用索引的话其返回数据是稳定的，因为索引的B+树叶子结点的顺序（就是聚簇索引的顺序）是唯一且一定的。
因此在这种不稳定的算法情况下上面的查询出现了不一样的结果，归根结底就是使用索引避免排序和堆排序对于重复值的处理上是不同的。

order by limit排序时，根据取值大小创建相应容量的堆，即
order by limit 0,10；——创建一个10容量的堆，然后取前10
order by limit 10,10 ——创建一个20容量的堆，然后取10到20

我们可以在java中模拟一下mysql内存中堆排序的过程，

package FileSort;
import java.util.Date;
import java.util.PriorityQueue;

/**
 * @version 1.0
 * @date 2020/11/7 14:19
 */
public class MysqlFileSort {

    public static void main(String[] args) {
        PriorityQueue<UserInfo> queue = new PriorityQueue();
        Date date = new Date();
        UserInfo req0 = new UserInfo();
        req0.setId(202847L);
        req0.setInvalidTm(date);

        UserInfo req1 = new UserInfo();
        req1.setId(202848L);
        req1.setInvalidTm(date);

        UserInfo req2 = new UserInfo();
        req2.setId(202849L);
        req2.setInvalidTm(date);

        UserInfo req3 = new UserInfo();
        req3.setId(202850L);
        req3.setInvalidTm(date);

        UserInfo req4 = new UserInfo();
        req4.setId(202851L);
        req4.setInvalidTm(date);

        UserInfo req5 = new UserInfo();
        req5.setId(202852L);
        req5.setInvalidTm(date);

        UserInfo req6 = new UserInfo();
        req6.setId(202853L);
        req6.setInvalidTm(date);

        UserInfo req7 = new UserInfo();
        req7.setId(202854L);
        req7.setInvalidTm(date);

        UserInfo req8 = new UserInfo();
        req8.setId(202855L);
        req8.setInvalidTm(date);

        UserInfo req9 = new UserInfo();
        req9.setId(202856L);
        req9.setInvalidTm(date);

        UserInfo req10 = new UserInfo();
        req10.setId(202857L);
        req10.setInvalidTm(date);

        UserInfo req11 = new UserInfo();
        req11.setId(202858L);
        req11.setInvalidTm(date);

        UserInfo req12 = new UserInfo();
        req12.setId(202859L);
        req12.setInvalidTm(date);

        UserInfo req13 = new UserInfo();
        req13.setId(2028560L);
        req13.setInvalidTm(date);

        UserInfo req14 = new UserInfo();
        req14.setId(202861L);
        req14.setInvalidTm(date);

        UserInfo req15 = new UserInfo();
        req15.setId(202862L);
        req15.setInvalidTm(date);

        UserInfo req16 = new UserInfo();
        req16.setId(202863L);
        req16.setInvalidTm(date);

        UserInfo req17 = new UserInfo();
        req17.setId(202864L);
        req17.setInvalidTm(date);

        UserInfo req18 = new UserInfo();
        req18.setId(202865L);
        req18.setInvalidTm(date);

        queue.add(req0);queue.add(req1);queue.add(req2);queue.add(req3);queue.add(req4);
        queue.add(req5);queue.add(req6);queue.add(req7);queue.add(req8);queue.add(req9);

        //limit 0,10——创建一个10容量的堆，然后取前10
//        queue.remove();
//        queue.add(req10);
//        queue.remove();
//        queue.add(req11);
//        queue.remove();
//        queue.add(req12);
//        queue.remove();
//        queue.add(req13);
//        queue.remove();
//        queue.add(req14);
//        queue.remove();
//        queue.add(req15);
//        queue.remove();
//        queue.add(req16);
//        queue.remove();
//        queue.add(req17);
//        queue.remove();
//        queue.add(req18);

        //limit 10,20 ——创建一个20容量的堆，然后取10到20
        queue.add(req10);
        queue.add(req11);
        queue.add(req12);
        queue.add(req13);
        queue.add(req14);
        queue.add(req15);
        queue.add(req16);
        queue.add(req17);
        queue.add(req18);
        while(!queue.isEmpty()) {
            UserInfo e=queue.remove();
            System.out.print(e+" ");
        }
    }
}

public class UserInfo implements Comparable<UserInfo>{

    private Long id;
    private Date invalidTm;

    public Long getId() {
        return id;
    }

    public void setId(Long id) {
        this.id = id;
    }

    public Date getInvalidTm() {
        return invalidTm;
    }

    public void setInvalidTm(Date invalidTm) {
        this.invalidTm = invalidTm;
    }

    @Override
    public int compareTo(UserInfo o) {
        if(this.invalidTm.after(o.invalidTm)) {
            return 1;
        }else if(this.invalidTm==o.invalidTm) {
            return this.invalidTm.compareTo(o.invalidTm);
        }else {
            return -1;
        }
    }

    @Override
    public String toString() {
        return "UserInfo{" +
                "id=" + id +
                ", invalidTm=" + invalidTm +
                '}';
    }
}

问题解决

从上面的介绍我们知道，是因为排序字段重复导致的，那么解决办法就是再加一个排序字段(通常是主键id)，使其排序唯一，就可以解决问题了。

对于这种情况，mysql官网有详细的介绍（https://dev.mysql.com/doc/refman/5.7/en/limit-optimization.html），感兴趣的小伙伴可以自己去看下。

image.png

参考文章：
https://www.jianshu.com/p/8c2154872f83
https://www.cnblogs.com/lamp01/p/10770172.html