Mysql 自定义HASH索引带来的巨大性能提升

有这样一个业务场景,需要在2个表里比较存在于A表,不存在于B表的数据。表结构如下:

Mysql 自定义HASH索引带来的巨大性能提升
T_SETTINGS_BACKUP | CREATE TABLE `T_SETTINGS_BACKUP` (
  `FID` bigint(20) NOT NULL AUTO_INCREMENT,
  `FUSERID` bigint(20) NOT NULL COMMENT 用户ID,
  `FDEVICE` varchar(64) NOT NULL DEFAULT ‘‘ COMMENT 用户设备号(SN),
  `FAPPID` varchar(64) NOT NULL DEFAULT ‘‘ COMMENT 应用ID,
  `FKEYID` varchar(32) NOT NULL DEFAULT ‘‘ COMMENT 设置项ID,
  `FCONTENT` varchar(2000) NOT NULL DEFAULT ‘‘ COMMENT 设置项内容,
  `FUPDATETIME` datetime NOT NULL DEFAULT 1970-01-01 00:00:00 COMMENT 修改时间,
  `FCREATETIME` datetime NOT NULL DEFAULT 1970-01-01 00:00:00 COMMENT 创建时间,
  PRIMARY KEY (`FID`),
  UNIQUE KEY `UDX_USERID_DEVICE_APPID_KEYID` (`FUSERID`,`FDEVICE`,`FAPPID`,`FKEYID`)
) ENGINE=InnoDB AUTO_INCREMENT=21934 DEFAULT CHARSET=utf8mb4 
Mysql 自定义HASH索引带来的巨大性能提升

暂定义上表为A表,记录数:21933

B表表结构如下,记录数:4794959

Mysql 自定义HASH索引带来的巨大性能提升
CREATE TABLE `meizu_device_tmp_1` (
  `id` int(11) unsigned NOT NULL DEFAULT 0,
  `imei` bigint(20) NOT NULL DEFAULT 0 COMMENT imei,
  `sn` varchar(20) CHARACTER SET utf8 NOT NULL DEFAULT ‘‘ COMMENT sn,
  UNIQUE KEY `imei` (`imei`),
  UNIQUE KEY `sn` (`sn`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4
Mysql 自定义HASH索引带来的巨大性能提升

A的FDEVICE和B的SN是关联字段,现在要求出FDEVICE在A不在B的记录数。自然想到下面的LEFT JOIN

Mysql 自定义HASH索引带来的巨大性能提升
mysql> explain select A.fdevice  FROM T_SETTINGS_BACKUP A left JOIN meizu_device_tmp_1 B ON A.FDEVICE=B.sn where B.sn is null;
+----+-------------+-------+-------+---------------+-------------------------------+---------+------+---------+--------------------------------------+
| id | select_type | table | type  | possible_keys | key                           | key_len | ref  | rows    | Extra                                |
+----+-------------+-------+-------+---------------+-------------------------------+---------+------+---------+--------------------------------------+
|  1 | SIMPLE      | A     | index | NULL          | UDX_USERID_DEVICE_APPID_KEYID | 654     | NULL |   22232 | Using index                          |
|  1 | SIMPLE      | B     | index | NULL          | sn                            | 62      | NULL | 4772238 | Using where; Using index; Not exists |
+----+-------------+-------+-------+---------------+-------------------------------+---------+------+---------+--------------------------------------+
2 rows in set (0.00 sec)
Mysql 自定义HASH索引带来的巨大性能提升

执行时间1小时以上,等不出结果直接KILL掉了。

分析上面的执行计划,两个表都用到了覆盖索引,每个表都没有过滤条件,所以需要扫描全部行,2W乘以470W是个巨大的数字,执行器在不停的做内循环的判断,直到完成22232*4772238次。除了这个循环次数巨大外,这个执行计划还有2个需要考量的地方

1)type=index  2)key_len 

type=index 执行效率仅高于全表扫描,在某些情况下比全部扫描更差。key_len比较大,说明索引太长。A表的索引是个4字段的组合索引,有用的比较字段只有FDEVICE,为了覆盖索引优化器把全部字段都加入判断了。

对于key_len 有两个疑问 1)为什么A表的key_len=654? 2)为什么B表的ken_len=62? 

优化key_len, 考虑到业务特性,FUSERID肯定大于0,把SQL改一下,执行计划看起来好一点了,type=range,key_len=8,实际上对A表只用到了FUSERID字段索引,最左前缀,FDEVICE通过WHERE判断。

Mysql 自定义HASH索引带来的巨大性能提升
mysql> desc select A.fdevice  FROM T_SETTINGS_BACKUP A left JOIN meizu_device_tmp_1 B ON A.FDEVICE=B.sn where A.fuserid>0  and B.sn is null;
+----+-------------+-------+-------+-------------------------------+-------------------------------+---------+------+---------+--------------------------------------+
| id | select_type | table | type  | possible_keys                 | key                           | key_len | ref  | rows    | Extra                                |
+----+-------------+-------+-------+-------------------------------+-------------------------------+---------+------+---------+--------------------------------------+
|  1 | SIMPLE      | A     | range | UDX_USERID_DEVICE_APPID_KEYID | UDX_USERID_DEVICE_APPID_KEYID | 8       | NULL |   11116 | Using where; Using index             |
|  1 | SIMPLE      | B     | index | NULL                          | sn                            | 62      | NULL | 4911049 | Using where; Using index; Not exists |
+----+-------------+-------+-------+-------------------------------+-------------------------------+---------+------+---------+--------------------------------------+
2 rows in set (0.01 sec)
Mysql 自定义HASH索引带来的巨大性能提升

执行时间依旧很长,等不了直接KILL了。

优化到这一步,还有什么别的招数,可以提高执行性能的?似乎已经到了尽头。

回顾下两表的关联字段,A.FDEVICE=B.sn,两个字段都是字符串,在数据类型上考虑,自然想到,是不是可以把记录比较字段从字符串的比较,改成数字的比较?这是个优化的方向。在计算机里底层数据都是01010这样,只需要把数字换算成0101就可以做等值比较了,但是变成字符,需要先去字符编码表找到字符对应的数字,在把数字换算成0101,这里多出一步查找操作。另一方面字符占用的空间比数字要大很多,一个页内能存下的item条目比数字的要少,这会导致更多的数据页读取。

根据这个方向,尝试使用自定义HASH索引,常见的HASH函数有MD5,password,crc32,sha1等,只有crc32哈希之后的值的数字型的。

Mysql 自定义HASH索引带来的巨大性能提升
mysql> select md5(sdsafa),password(sdsafa),crc32(sdsafa),SHA1(sdsafa);
+----------------------------------+-------------------------------------------+-----------------+------------------------------------------+
| md5(sdsafa) | password(sdsafa) | crc32(sdsafa) | SHA1(sdsafa) |
+----------------------------------+-------------------------------------------+-----------------+------------------------------------------+
| c5067032ca64a35620fc5c75aa42265c | *45ABB21DBD1E6A5659E05F1EBAF589A3B39EB835 | 1766538443 | b9349f6a0b8138e3e6461745fd257678eefeb9a2 |
+----------------------------------+-------------------------------------------+-----------------+------------------------------------------+
1 row in set (0.00 sec)
Mysql 自定义HASH索引带来的巨大性能提升

在表里加个字段记录hash之后的值,并对这个字段加上索引。

Mysql 自定义HASH索引带来的巨大性能提升
mysql> CREATE TABLE `meizu_device_tmp_3` (
    ->   `id` int(11) unsigned NOT NULL DEFAULT 0,
    ->   `imei` bigint(20) NOT NULL DEFAULT 0 COMMENT imei,
    ->   `sn` varchar(20) CHARACTER SET utf8 NOT NULL DEFAULT ‘‘ COMMENT sn,
    ->   `hash_sn` bigint(20) DEFAULT NULL,
    ->   UNIQUE KEY `imei` (`imei`),
    ->   KEY `hash_sn` (`hash_sn`)
    -> ) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 ;
Query OK, 0 rows affected (0.20 sec)

mysql> insert into meizu_device_tmp_3 select id,imei,sn,crc32(sn) from meizu_device_tmp_1;
Query OK, 4794959 rows affected (1 min 50.31 sec)
Records: 4794959  Duplicates: 0  Warnings: 0

mysql> select * from meizu_device_tmp_3 limit 1;
+----------+---------+--------------------+------------+
| id       | imei    | sn                 | hash_sn    |
+----------+---------+--------------------+------------+
| 23930528 | 1311265 | MX21CA2ALHR2460302 | 2330453935 |
+----------+---------+--------------------+------------+
1 row in set (0.00 sec)
Mysql 自定义HASH索引带来的巨大性能提升

查询时,关联字段先crc32计算后,再比较,这样就变成了数字和数字的比较了,被驱动表比较字段也有索引。

但是crc32算法可能存在hash碰撞,也就是不同的值hash出来的结果是一样的,这就“撞”上了。为了避免碰撞导致的比较结果不准确,在hash比较之后,再做一次原值的比较。

优化之后的查询语句是这样的

Mysql 自定义HASH索引带来的巨大性能提升
mysql> desc select A.fdevice  FROM T_SETTINGS_BACKUP A left JOIN meizu_device_tmp_3 B ON crc32(A.FDEVICE)=B.hash_sn and A.fdevice=B.sn where  B.sn is null;
+----+-------------+-------+-------+---------------+-------------------------------+---------+------+-------+-------------------------+
| id | select_type | table | type  | possible_keys | key                           | key_len | ref  | rows  | Extra                   |
+----+-------------+-------+-------+---------------+-------------------------------+---------+------+-------+-------------------------+
|  1 | SIMPLE      | A     | index | NULL          | UDX_USERID_DEVICE_APPID_KEYID | 654     | NULL | 22232 | Using index             |
|  1 | SIMPLE      | B     | ref   | hash_sn       | hash_sn                       | 9       | func |     1 | Using where; Not exists |
+----+-------------+-------+-------+---------------+-------------------------------+---------+------+-------+-------------------------+
2 rows in set (0.00 sec)
Mysql 自定义HASH索引带来的巨大性能提升

巨大的改变,被驱动表的rows=1. SQL执行时间0.38秒。

 

hash索引有这么大的好处,但是也存在不少缺点

1)hash不能处理范围比较,只能处理等值比较。

2)hash不能做排序,hash出来的结果是随机分布的。

3)hash不支持部分索引,如index a(10)就不支持。

4)hash无法覆盖索引

5)hash有碰撞,碰撞得比较厉害时,处理碰撞的代价就比较高。

 

CRC32算法:http://wenku.baidu.com/view/465dca06e87101f69e31951f.html

自定义hash索引:http://www.lizhonghaosc.cn/mysql-chuang-jian-zi-ding-yi-ha-xi-suo-yin/

 

Mysql 自定义HASH索引带来的巨大性能提升,布布扣,bubuko.com

Mysql 自定义HASH索引带来的巨大性能提升

上一篇:MSSQL charindex


下一篇:如何更改SQL Server 2008 登陆验证方式