AAAAOrder2020-0000001之面试题

摘要

  • 本文内容基于10.4.8-MariaDB

Q: 假设一个订单的编号规则是AAAAOrder2020-0000001，AAAAOrder2020-0000002…后面的数字是自增长，如果订单号码达到AAAAOrder2020-1000000(100万)，数据库中应该有100万条数据，此时我随机删除2条数据（物理删除，且不考虑日志和备份），请问怎么找到删掉的数据的编号？给出解题思路即可，答案需要在1秒内运行得到。

思路

  1. 其实查找丢失数据方法有很多，不过这里重点强调1秒内运行得到，就限制成了只能在数据库层面完成，实现方法基本上就是sql或者存储过程，而且要尽量减少表的扫描次数和扫描范围、尽可能的使用索引。
  2. 订单编号的序号是自增长，所以可以认为数据是按照编号自增的顺序插入数据表的,如果数据表存在单独的自增主键Id，则可以基于错位法得到缺失的主键Id，这样可以使用主键索引，而且主键自增索引的查询效率是最高的。
  3. 如果没有独立的主键Id，而是使用的orderId作为主键，则需要对orderId截断后进行比较，查询条件一定要使用完整的orderId，以便使用索引，也可以使用行号和截断后的订单编号进行比较的方法。具体实现见下文。

参考答案，作者水平有限，仅供学习交流

  1. 存在自增主键Id，与orderId序号一致，可以通过错位法计算不存在的Id值。
    运行时间基本符合要求。
select id-1 as id_del from test_order where id not in (select id+1 from test_order);
+--------+
| id_del |
+--------+
| 233490 |
| 943220 |
|      0 |  #这里去除0号记录，因为不存在id为0的记录
+--------+
3 rows in set (1.063 sec)
  1. 如果不存在自增主键ID，而是使用orderId作为主键，则也可以通过错位法计算不存在的Id值，主要比较时一定要用完整的orderId，否则不能使用索引。
    运行时间超过要求。
SELECT RIGHT(orderId, 7) - 1 AS id_del FROM test_order
  WHERE orderId NOT in(
    SELECT concat( left(orderId, 14), LPAD( RIGHT(orderId, 7) + 1, 7, 0))
    FROM test_order);
+--------+
| id_del |
+--------+
|      0 |   #这里去除0号记录，因为不存在id为0的记录
| 233490 |
| 943220 |
+--------+
3 rows in set (2.999 sec)
  1. 如果不存在自增主键ID，而是使用orderId作为主键，也可以比较orderId的序号与行号，获取到不一致的第一条记录，然后在从该记录开始继续比较获得下一条不一致的记录，也可以通过存储过程实现。
    运行时间符合要求。

sql示例1

-- 查询第一条丢失记录
select substring(a.orderId,15)-1 as orderId from (
     SELECT @rownum:=@rownum+1 AS rownum, test_order.orderId  FROM (SELECT @rownum:=0) r, test_order
     ) a where substring(a.orderId,15) != a.rownum limit 1;
+---------+
| orderId |
+---------+
|  233490 |
+---------+
1 row in set (0.341 sec)

-- 将上面查询结果作为第二条sql的参数，这里上一条查询结果为 233490，所以下面手工填写对应的值，
-- 这里因为limit不能写变量，所以需要手工填写，如果希望一次执行，可以参考后面的sql示例2和存储过程示例
select substring(a.orderId,15)-1 as orderId from (
     SELECT @rownum:=@rownum+1 AS rownum, test_order.orderId  FROM (SELECT @rownum:=0) r, test_order
     limit 233489,1000000
     ) a where substring(a.orderId,15)-233490 != a.rownum limit 1;
+---------+
| orderId |
+---------+
|  943220 |
+---------+
1 row in set (0.372 sec)

-- 验证是否准确
select orderId from test_order limit 233488,2;
+----------------------+
| orderId              |
+----------------------+
| aaaaorder2020-233489 |
| aaaaorder2020-233491 |
+----------------------+
2 rows in set (0.036 sec)

sql示例2

-- 可以直接粘贴到mysql终端执行，也可以保存到文件，然后在mysql终端执行source /xx/xx/xx.sql
-- 这里修改定界符，就是为了方便看到一个总的执行时间
delimiter ;;
select substring(a.orderId,15)-1 as orderId into @first_order_id from (
     SELECT @rownum:=@rownum+1 AS rownum, test_order.orderId  FROM (SELECT @rownum:=0) r, test_order
     ) a where substring(a.orderId,15) != a.rownum limit 1;

SET @second_limit = @first_order_id - 1;

SET @limitsql = CONCAT( 'SELECT @rownum:=@rownum+1 AS rownum, test_order.orderId  FROM (SELECT @rownum:=0) r, test_order
limit ', @second_limit, ',1000000' );

SET @SQL = CONCAT( 'select substring(a.orderId,15)-1 as orderId into @second_order_id from (', @limitsql, '
) a where substring(a.orderId,15)-', @first_order_id, ' != a.rownum limit 1' );

PREPARE stmt FROM @SQL;
EXECUTE stmt;

SET @del_ids = concat( @first_order_id, ',', @second_order_id );
;;
delimiter ;
SELECT @del_ids;


source /Users/hanqf/Desktop/exec.sql
Query OK, 1 row affected (0.710 sec)

Query OK, 0 rows affected (0.710 sec)

Query OK, 0 rows affected (0.710 sec)

Query OK, 0 rows affected (0.710 sec)

Query OK, 0 rows affected (0.710 sec)
Statement prepared

Query OK, 1 row affected (0.710 sec)

Query OK, 0 rows affected (0.710 sec)

+---------------+
| @del_ids      |
+---------------+
| 233490,943220 |
+---------------+
1 row in set (0.000 sec)

存储过程示例

DROP PROCEDURE IF EXISTS find_delete_order_id;
CREATE PROCEDURE `find_delete_order_id`(OUT del_ids varchar(255))
BEGIN
  DECLARE first_order_id INT;
  DECLARE second_order_id INT;
  DECLARE second_limit INT;

  select substring(a.orderId,15)-1 as orderId into first_order_id from (
     SELECT @rownum:=@rownum+1 AS rownum, test_order.orderId  FROM (SELECT @rownum:=0) r, test_order
     ) a where substring(a.orderId,15) != a.rownum limit 1;

  set second_limit = first_order_id-1;

  select substring(a.orderId,15)-1 as orderId into second_order_id from (
     SELECT @rownum:=@rownum+1 AS rownum, test_order.orderId  FROM (SELECT @rownum:=0) r, test_order
     limit second_limit,1000000
     ) a where substring(a.orderId,15)-first_order_id != a.rownum limit 1;

  set del_ids = concat(first_order_id,',',second_order_id);
  -- 此处为了方便测试，所以在存储过程中就打印了结果
  select del_ids;

END;


CALL `find_delete_order_id`(@del_ids);
+---------------+
| del_ids       |
+---------------+
| 233490,943220 |
+---------------+
1 row in set (0.704 sec)

Query OK, 2 rows affected (0.704 sec)

select @del_ids;
+---------------+
| @del_ids      |
+---------------+
| 233490,943220 |
+---------------+
1 row in set (0.000 sec)

表结构

DROP TABLE IF EXISTS `test_order`;
CREATE TABLE `test_order` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `orderId` varchar(30) DEFAULT NULL,
  PRIMARY KEY (`id`),
  UNIQUE KEY `index_order_id` (`orderId`) USING HASH
) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8;

数据初始化

说明：

  1. 直接将100w的数据插入数据表有点慢，实测130多秒吧，这里可以先将数据初始化到内存表中，然后再从内存表导入即可，总时间大概只需要12秒左右。

  2. 因为数据都是写入内存中，所以写入数据时可能会报内存不足，解决方法如下：
    a.永久修改，在my.cnf中增加如下配置:
    tmp_table_size=1G
    max_heap_table_size=1G

    b.临时修改,mysql终端执行：
    set tmp_table_size = 1073741824;
    set max_heap_table_size = 1073741824;
    show variables like "%table_size%";

-- 创建内存表，重启数据库后，内存表中的数据会被清空，但是表结构依旧存在，不需要时可以drop掉
DROP TABLE IF EXISTS `test_order_memory`;
CREATE TABLE `test_order_memory` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `orderId` varchar(30) DEFAULT NULL,
  PRIMARY KEY (`id`),
  UNIQUE KEY `index_order_id` (`orderId`) USING HASH
) ENGINE=MEMORY AUTO_INCREMENT=1 DEFAULT CHARSET=utf8;

-- 初始化内存表
DROP PROCEDURE IF EXISTS add_test_order_memory;
CREATE PROCEDURE `add_test_order_memory`(IN n int)
BEGIN
  DECLARE i INT DEFAULT 1;
    WHILE (i <= n ) DO
      INSERT INTO test_order_memory (orderId) VALUES (concat('aaaaorder2020-',LPAD(i, 7, 0)));
      set i=i+1;
    END WHILE;
END;

-- 创建1000000条数据
call add_test_order_memory(1000000);
Query OK, 1000000 rows affected (7.354 sec)

-- 将内存表中数据导入实际表中
INSERT into test_order SELECT * from  test_order_memory;
Query OK, 1000000 rows affected (5.035 sec)
Records: 1000000  Duplicates: 0  Warnings: 0

-- 查看结果
select * from test_order limit 5;
+----+-----------------------+
| id | orderId               |
+----+-----------------------+
|  1 | aaaaorder2020-0000001 |
|  2 | aaaaorder2020-0000002 |
|  3 | aaaaorder2020-0000003 |
|  4 | aaaaorder2020-0000004 |
|  5 | aaaaorder2020-0000005 |
+----+-----------------------+
5 rows in set (0.000 sec)

-- 删除两条数据，这里就随便填两个id号
delete from test_order where id in (233490,943220);
Query OK, 2 rows affected (0.001 sec)
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 206,378评论 6赞 481
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 88,356评论 2赞 382
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 152,702评论 0赞 342
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 55,259评论 1赞 279
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 64,263评论 5赞 371
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 49,036评论 1赞 285
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,349评论 3赞 400
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,979评论 0赞 259
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 43,469评论 1赞 300
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,938评论 2赞 323
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,059评论 1赞 333
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,703评论 4赞 323
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,257评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,262评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,485评论 1赞 262
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,501评论 2赞 354
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,792评论 2赞 345