如何在mysql中实现自然排序

背景

熟悉mysql的同学应该清楚，mysql在对字符串做order by排序时是按照字典序进行排序的，但是如果字符串中包含数字的话（我们称这种类型的字符串为alphanumeric），仅按照字典序的排序结果对用户不太友好。我们举个例子，假设我们在mysql中存了一张files表，里面记录了文件的id以及文件的name，表里的数据如下：

id	name
1	1测试2
2	测试
3	1
4	1测试12
5	1测试1
6	1测试20

name字段目前是乱序的，现在我们对该表执行order by查询，即SELECT * FROM files ORDER BY name：

id	name
3	1
5	1测试1
4	1测试12
1	1测试2
6	1测试20
2	测试

我们重点关注以“1测试”开头的那四个name，他们末尾都带有了数字，但因为mysql默认采取字典序排序，所以排序的结果是"1" < "12" < "2" < "20"，这显然不太友好，我们更期望数字部分是根据数字大小排序的。这种非数字部分按照字典序排序，数字部分按照数字大小进行排序的方式我们就称之为自然排序（natural sort）。

与字典序排序相比，自然排序的结果更加人性化，对用户更加友好。现代操作系统其实已经实现了文件名的自然排序，我们以Mac为例：

现代的编程语言也都内置了自然排序算法，比如php的natsort方法。但是由于mysql中没有内置对应的函数，我们只能通过其他的办法来实现mysql的自然排序。

思路

要想对mysql做一些扩展，一共有以下三种方法：

1. 修改底层源码。
2. 编写mysql扩展（plugin）。
3. 编写存储函数（stored function）。

显然，要想实现自然排序，我们势必要对order by做一些手脚。如果是第一种方法，不仅难度大，而且不利于mysql的版本升级。如果是第二种方法，mysql扩展又不支持扩展语法层面的能力。那么我们只能采用第三种方法了，也就是存储函数或者又称之为UDF。

如果采用存储函数，那么其实我们在排序时还是用的字典序，所以我们需要借助存储函数将原来待排序的字段（比如例子中的name字段）转换成就算按照字典序排序也能达到自然排序效果的字段。

我们再来看看自然排序的核心思想：非数字部分按照字典序排序，数字部分按照数字大小排序。所以我们只要将数字部分转换成可按大小排序的字符串即可。我们以上例中的”1测试12“和”1测试2“为例，我们将末尾”12“和”2“转化为定长的字段，比如”0000012“和”0000002“。此时”0000012“按照字典序比”0000002“大，这就实现字典序下的自然排序。

好了说了这么多，show me the code：

DELIMITER ;;
CREATE FUNCTION NatSort (Varstring VARCHAR(50))
RETURNS VARCHAR(1000)
READS SQL DATA
DETERMINISTIC
BEGIN
DECLARE v_length INT DEFAULT 0;
DECLARE v_num VARCHAR(50) DEFAULT '';
DECLARE v_index INT DEFAULT 1;
DECLARE v_result VARCHAR(1000) DEFAULT '';
DECLARE v_flag INT DEFAULT 0;
DECLARE v_char CHAR(1) DEFAULT '';
SET v_flag=0;
SET v_index=1;
SET v_length=CHAR_LENGTH(Varstring);

-- 遍历字符串
WHILE v_index <= v_length DO
    SET v_char = mid(Varstring,v_index,1);
    IF (ASCII(v_char)>=48 AND ASCII(v_char)<=57) THEN
        SET v_num=concat(v_num,mid(Varstring,v_index,1)); -- 获取字符串里的数字
        SET v_flag = 1;
    ELSE 
        IF v_flag = 1 THEN
            SET v_flag=0;
            SET v_result=concat(v_result,lpad(cast(v_num AS UNSIGNED),10,'0')); -- 将数字转成定长字符串
            SET v_num=''; -- 重置v_num
        END IF;

        SET v_result=concat(v_result, v_char);
    END IF;
    SET v_index = v_index + 1;
END WHILE;

IF v_flag=1 THEN
    SET v_result=concat(v_result,lpad(cast(v_num AS UNSIGNED),10,'0'));
END IF;

RETURN v_result;
END;;

在上述代码中，我们将所有数字转成了共10位的定长字符串。我们看一下函数的具体效果，我们执行SELECT *, NatSort(name) as name_sort FROM files ORDER BY name_sort：

id	name	name_sort
3	1	0000000001
5	1测试1	0000000001测试0000000001
1	1测试2	0000000001测试0000000002
4	1测试12	0000000001测试0000000012
6	1测试20	0000000001测试0000000020
2	测试	测试

从结果中我们可以看到，已经实现了自然排序，经过实际测试，性能还行。

注意和优化

细心的同学可能已经发现了，上述算法并不完美。我们在代码中将数字扩充为了定长为10位的字符串，那么如果原字符串中的数字长度大于10位，那么算法就失效了。所以在实际使用过程中，要根据具体的业务场景设定定长的位数。

另外，为了提高查询性能，我们可以事先就将转换后的字符串存储在表中，这样就不需要每次查询时都需要调用存储函数。这也是常用的一种以“空间换时间”的优化手段。

本文首发于http://www.kissyu.org/2017/04/16/%E5%A6%82%E4%BD%95%E5%9C%A8mysql%E4%B8%AD%E5%AE%9E%E7%8E%B0%E8%87%AA%E7%84%B6%E6%8E%92%E5%BA%8F/ 转载请标注作者和来源