SQL选择系列中的第一个缺失值

Question

我被问到以下内容:我有一个表(让我们称之为tbl),它有一个int类型的列(让它称为num),它有序列号:

num
---
 1
 2
 4
 5
 6
 8
 9
 11

现在,您需要编写一个返回第一个缺失数字的查询(在此示例中,答案将为3).

这是我的答案(作品):

select top 1 (num + 1)
from tbl
where (num + 1) not in (select num from tbl)

写完这篇文章之后,我被问到,如果tbl包含1000万条记录 - 如何提高性能(因为显然myinner查询会导致全表扫描).

我的想法是关于num字段的索引并且不存在.但我很乐意听到其他一些选择.

Answer 1

在SQL Server 2012+中,我只会使用lead():

select num
from (select num, lead(num) over (order by num) as next_num
      from tbl
     ) t
where next_num <> num + 1;

但是,如果您有索引,我怀疑您的版本将具有最佳性能tbl(num).该not exists版本值得测试:

select top 1 (num + 1)
from tbl t
where not exists (select 1 from tbl t2 where t2.num = t.num + 1);

唯一的问题是获得第一个数字.您不能保证该表是"按顺序"读取的.所以,这将返回一个数字.使用索引(或更好的聚簇索引)num,以下内容应该快速并保证返回第一个数字:

select top 1 (num + 1)
from tbl t
where not exists (select 1 from tbl t2 where t2.num = t.num + 1)
order by num;

Answer 2

这是另一种使用方法ROW_NUMBER:

SQL小提琴

;WITH CteRN AS(
    SELECT *,
        RN = num - ROW_NUMBER() OVER(ORDER BY num)
    FROM tbl
)
SELECT TOP 1 num - RN
FROM CteRN
WHERE RN > 0
ORDER BY num ASC

如果适当INDEX打开num,这里是一百万行测试工具下的统计数据.

Original - NOT IN     : CPU time = 296 ms,  elapsed time = 289 ms
wewesthemenace        : CPU time = 0 ms,  elapsed time = 0 ms
notulysses(NOT EXISTS): CPU time = 687 ms,  elapsed time = 679 ms.

Answer 3

您可以尝试使用not exists：

select top 1 t.num + 1
from tbl t
where not exists (select * from tbl where num = t.num + 1) order by t.num

SQLFiddle

或者使用row_number：

select top 1 t.r
from (
   select num
        , row_number() over (order by num) as r
   from tbl) t
where t.r <> t.num
order by t.num

SQLFiddle