SQL Server 尋找最小缺失索引值：集合運算與數字表的高效解法

問題定義

給定表 `t_MaxInMinContinuousArr` 包含主鍵 `SNId (INT)`，資料中存在間隙。**需找出最小的 `SNId` 使得 `SNId` 存在但 `SNId+1` 不存在** — 即「最小連續數組中的最大值」，連續數組長度可為 1。

等價轉化：**找出主鍵範圍內最小的缺失值，再減 1**。

測試資料生成腳本

USE tempdb;
GO
IF OBJECT_ID('t_MaxInMinContinuousArr','U') IS NOT NULL DROP TABLE t_MaxInMinContinuousArr;
CREATE TABLE t_MaxInMinContinuousArr(SNId INT PRIMARY KEY, SomeDate DATETIME);

-- 生成 10,000 行基礎資料
DECLARE @i INT = 1;
WHILE @i <= 10000
BEGIN
  INSERT INTO t_MaxInMinContinuousArr VALUES(@i, DATEADD(SECOND, @i, '2024-01-01'));
  SET @i += 1;
END

-- 隨機刪除製造間隙
DELETE FROM t_MaxInMinContinuousArr WHERE SNId IN (5, 100, 500, 1000, 5000);

方案對比

方案一：集合運算 EXCEPT (推薦，簡潔高效)

WITH Bounds AS (
  SELECT MIN(SNId) AS MinId, MAX(SNId) AS MaxId FROM t_MaxInMinContinuousArr
), FullRange AS (
  SELECT number AS SNId FROM master..spt_values, Bounds
  WHERE type='P' AND number BETWEEN Bounds.MinId AND Bounds.MaxId
)
SELECT MIN(SNId) - 1 AS Answer
FROM FullRange
EXCEPT
SELECT SNId FROM t_MaxInMinContinuousArr;

原理：`master..spt_values (type='P')` 提供 0-2047 連續整數，配合 `EXCEPT` 差集運算瞬間找出缺失值。

方案二：LEAD/LAG 窗口函數 (SQL 2012+，單掃描)

WITH Gaps AS (
  SELECT SNId,
         LEAD(SNId) OVER (ORDER BY SNId) AS NextId
  FROM t_MaxInMinContinuousArr
)
SELECT TOP 1 SNId AS Answer
FROM Gaps
WHERE NextId - SNId > 1
ORDER BY SNId;

優勢：無需輔助數字表、單次掃描、支援任意大範圍。

方案三：NOT EXISTS 相關子查詢 (通用相容)

SELECT TOP 1 t1.SNId AS Answer
FROM t_MaxInMinContinuousArr t1
WHERE NOT EXISTS (
  SELECT 1 FROM t_MaxInMinContinuousArr t2 WHERE t2.SNId = t1.SNId + 1
)
ORDER BY t1.SNId;

適用：SQL 2008/2008 R2 無窗口函數環境，需有 `SNId` 索引支援。

方案四：數字表 / 遞歸 CTE (大範圍通用)

-- 遞歸 CTE 生成完整範圍 (MaxId-MinId < 100000 時可用)
WITH Bounds AS (
  SELECT MIN(SNId) MinId, MAX(SNId) MaxId FROM t_MaxInMinContinuousArr
), Nums AS (
  SELECT MinId AS n FROM Bounds
  UNION ALL
  SELECT n+1 FROM Nums, Bounds WHERE n < MaxId
)
SELECT MIN(n) - 1 AS Answer
FROM Nums
WHERE n NOT IN (SELECT SNId FROM t_MaxInMinContinuousArr)
OPTION (MAXRECURSION 0);

效能測試結果 (100 萬行測試資料)

避坑指南

• spt_values 陷阱：僅含 0-2047，**超出範圍會漏查** — 生產環境**禁用**方案一
• 並行計劃：大表加 `OPTION (MAXDOP 1)` 避免並行換頁競爭
• 索引覆蓋：確保 `SNId` 為叢集索引或覆蓋非叢集索引
• 邊界條件：表為空、無間隙 (連續至 MaxId) → 應返回 `NULL` 或 `MaxId`，業務定義為準

生產級推薦腳本 (SQL 2012+)

CREATE PROCEDURE dbo.GetMinMissingMinusOne
    @TableName SYSNAME,
    @ColumnName SYSNAME
AS
BEGIN
    SET NOCOUNT ON;
    DECLARE @sql NVARCHAR(MAX) = N'
    WITH Gaps AS (
        SELECT ' + QUOTENAME(@ColumnName) + N' AS Val,
               LEAD(' + QUOTENAME(@ColumnName) + N') OVER (ORDER BY ' + QUOTENAME(@ColumnName) + N') AS NextVal
        FROM ' + QUOTENAME(@TableName) + N'
    )
    SELECT TOP 1 Val AS MinMissingMinusOne
    FROM Gaps
    WHERE NextVal - Val > 1
    ORDER BY Val;';
    EXEC sp_executesql @sql;
END;

總結

**SQL 2012+ 首選 `LEAD/LAG` 窗口函數** — 單掃描、無輔助表依賴、無範圍限制。SQL 2008/2008 R2 使用 `NOT EXISTS` + 索引。切記 **`master..spt_values` 僅適合臨時調試，嚴禁用於生產業務邏輯**。