連番の空番を取得する方法

解説

今回は備忘録的なネタです。

連番の空番を調べたいってのは結構ある話ですが、わざわざVBAで探すのは面倒です。
(面倒というほどのコーディング量でもありませんが)

今回は簡単なSQLでとる方法をいくつか紹介します。
INやEXISTSを使った方法がよく紹介されていますが、多くはのサンプルは先頭が欠番しているとそこが調べられなくなっています。
ここでは、先頭が欠番していても調べる方法を紹介します。

なお、銀の匙さん、YU-TANGさんの強力な協力によりモジュールを使った二分探索による高速な検索方法も一緒に紹介します。

サンプル

1. IN句使った方法
   件数が増えると遅い。って言うか使えない

   SELECT
       MIN(連番+1) AS 欠番
   FROM
       (
           SELECT {[TOP 1] Or [DISTINCT]} ← これをつけるとちょっと早くなる
                                             TOPのほうが若干早い
               0 AS 連番 ← 固定値は最小値-1とする(1が最小なら0、0が最小なら-1とする)
           FROM
               [テーブル名]
           UNION SELECT
               連番
           FROM
               [テーブル名]
       ) AS [適当な名前]
   WHERE
       連番+1 NOT IN
       (
           SELECT
                連番
           FROM
               [テーブル名]
       )
   

2. EXISTS句使った方法
   サンプル 1よりは速い

   SELECT
       MIN(連番+1) AS 欠番
   FROM
       (
           SELECT {[TOP 1] Or [DISTINCT]} ← これをつけるとちょっと早くなる
                                             TOPのほうが若干早い
               0 AS 連番 ← 固定値は最小値-1とする(1が最小なら0、0が最小なら-1とする)
           FROM
               [テーブル名]
           UNION SELECT
               連番
           FROM
               [テーブル名]
       ) AS [適当な名前]
   WHERE
       NOT EXISTS
       (
           SELECT
                0
           FROM
               [テーブル名]
           WHERE
               連番=[適当な名前].連番+1
       )
   

3. IIfとLEFT JOINを使った方法(銀の匙さん提供)
   これが今のところSQLでは最速

   SELECT
       IIf(先頭連番 > 1, 1, 欠番候補 + 1) AS 欠番
   FROM
       (
           SELECT
               MIN(T1.連番) AS 欠番候補,
               (
                   SELECT
                       MIN(連番)
                   FROM
                       [テーブル名]
               ) AS 先頭連番
           FROM
               [テーブル名] AS T1 LEFT JOIN [テーブル名] AS T2 ON
               T1.連番 + 1 = T2.連番
           WHERE
               T2.連番 Is Null
       ) AS [適当な名前]
   

4. IIfとEXISTSを使った方法(銀の匙さん提供)
   サンプル 2よりはるかに速い

   SELECT
       IIf(先頭連番 > 1, 1, 欠番候補 + 1) AS 欠番
   FROM
       (
           SELECT
               MIN(連番) AS 欠番候補,
               (
                   SELECT
                       MIN(連番)
                   FROM [テーブル名]
               ) AS 先頭連番
           FROM
               [テーブル名] AS T1
           WHERE
               NOT EXISTS
               (
                   SELECT
                       1
                   FROM
                       [テーブル名] AS T2
                   WHERE
                       T2.連番 = T1.連番 + 1
               )
       ) AS [適当な名前]
   

5. モジュールを使った方法 全件サーチ
   速度はデータ件数に比例するがテストで行った300万件ではSQLとは比較にならないくらい速い

   Public Function 欠番検索_全件サーチ() As Long
   
       Dim R_REC                                       As Recordset
   
       欠番検索_全件サーチ = 1
   
       Set R_REC = CurrentDb.OpenRecordset _
                       ("Sample", dbOpenTable, dbReadOnly, dbReadOnly)
   
       R_REC.Index = "PrimaryKey"
   
       Do Until R_REC.EOF
           If R_REC![ID] <> 欠番検索_全件サーチ Then
               Exit Do
           End If
   
           欠番検索_全件サーチ = 欠番検索_全件サーチ + 1
   
           R_REC.MoveNext
       Loop
   
       R_REC.Close
   
   End Function
   

6. モジュールを使った方法 二分探索 Find系メソッド版

   Public Function 欠番検索_二分探索_Find系メソッド() As Long
   
       Dim R_REC                                       As Recordset
   
       Dim StartValue                                  As Long
       Dim EndValue                                    As Long
       Dim FindValue                                   As Long
   
       Set R_REC = CurrentDb.OpenRecordset _
                       ("SELECT ID FROM Sample ORDER BY ID", dbOpenDynaset, _
                        dbReadOnly, dbReadOnly)
   
       R_REC.MoveLast
   
       StartValue = 1
       EndValue = R_REC![ID]
       FindValue = EndValue \ 2
   
       If R_REC.RecordCount = EndValue Then
           欠番検索_二分探索_Find系メソッド = EndValue + 1
   
           Exit Function
       End If
   
       R_REC.FindFirst "ID=" & FindValue
   
       Do
           If R_REC.NoMatch = True Then
               If StartValue = FindValue Then
                   欠番検索_二分探索_Find系メソッド = FindValue
   
                   Exit Do
               Else
                   EndValue = FindValue
                   FindValue = StartValue + (EndValue - StartValue) \ 2
   
                   R_REC.FindFirst "ID=" & FindValue
               End If
           ElseIf R_REC.AbsolutePosition + 1 = FindValue Then
               StartValue = FindValue + 1
               FindValue = FindValue + (EndValue - FindValue) \ 2 + 1
   
               R_REC.FindNext "ID=" & FindValue
           Else
               EndValue = FindValue
               FindValue = StartValue + (EndValue - StartValue) \ 2
   
               R_REC.FindPrevious "ID=" & FindValue
           End If
       Loop
   
       R_REC.Close
   
   End Function
   

7. モジュールを使った方法 二分探索 Move系メソッド版

   Public Function 欠番検索_二分探索_Move系メソッド() As Long
   
       Dim R_REC                                       As Recordset
   
       Dim StartValue                                  As Long
       Dim EndValue                                    As Long
       Dim FindValue                                   As Long
   
       Dim CurrentPosition                             As Long
   
       Set R_REC = CurrentDb.OpenRecordset _
                       ("Sample", dbOpenTable, dbReadOnly, dbReadOnly)
   
       R_REC.Index = "PrimaryKey"
   
       R_REC.MoveLast
   
       StartValue = 1
       EndValue = R_REC![ID]
       FindValue = EndValue \ 2
   
       If R_REC.RecordCount = EndValue Then
           欠番検索_二分探索_Move系メソッド = EndValue + 1
   
           Exit Function
       End If
   
       R_REC.MoveFirst
   
       R_REC.Move FindValue - 1
   
       CurrentPosition = FindValue
   
       Do
           If R_REC.EOF = True Then
               R_REC.MoveFirst
   
               EndValue = CurrentPosition
               FindValue = CurrentPosition - (EndValue - StartValue) \ 2 - 1
   
               R_REC.Move FindValue - 1
   
               CurrentPosition = FindValue
           ElseIf R_REC![ID] <> CurrentPosition Then
               If StartValue = CurrentPosition Then
                   欠番検索_二分探索_Move系メソッド = CurrentPosition
   
                   Exit Do
               Else
                   EndValue = CurrentPosition
                   FindValue = -(EndValue - StartValue) \ 2 - 1
   
                   R_REC.Move FindValue
   
                   CurrentPosition = CurrentPosition + FindValue
               End If
           Else
               StartValue = CurrentPosition + 1
               FindValue = (EndValue - CurrentPosition) \ 2 + 1
   
               R_REC.Move FindValue
   
               CurrentPosition = CurrentPosition + FindValue
           End If
       Loop
   
       R_REC.Close
   
   End Function
   

8. モジュールを使った方法 二分探索 SQL版(銀の匙さんカスタマイズ)

   Public Function 欠番検索_二分探索_SQL() As Long
   
       Dim DB                                          As Database
       Dim Q_OBJ                                       As QueryDef
       Dim R_REC                                       As Recordset
   
       Dim StartValue                                  As Long
       Dim EndValue                                    As Long
       Dim FindValue                                   As Long
   
       Set DB = CurrentDb
   
       Set R_REC = DB.OpenRecordset _
                   ("SELECT " & _
                        "MIN(ID) AS 最小値, MAX(ID) AS 最大値, COUNT(*) AS 件数 " & _
                    "FROM Sample", dbOpenForwardOnly, dbReadOnly, dbReadOnly)
   
       StartValue = 1
   
       If R_REC![件数] = R_REC![最大値] Then
           欠番検索_二分探索_SQL = R_REC![最大値] + 1
   
           Exit Function
       ElseIf R_REC![最小値] <> StartValue Then
           欠番検索_二分探索_SQL = StartValue
   
           Exit Function
       End If
   
       EndValue = R_REC![最大値]
       FindValue = EndValue \ 2
   
       R_REC.Close
   
       Set Q_OBJ = DB.CreateQueryDef _
                       ("", _
                        "PARAMETERS START_VALUE LONG, END_VALUE LONG;" & _
                        "SELECT " & _
                           "MIN(ID) AS 最小値, MAX(ID) AS 最大値, " & _
                           "COUNT(*) AS 件数 " & _
                        "FROM Sample " & _
                        "WHERE ID BETWEEN [START_VALUE] AND [END_VALUE]")
   
       Do
           Q_OBJ.Parameters![START_VALUE] = StartValue
           Q_OBJ.Parameters![END_VALUE] = FindValue
   
           Set R_REC = Q_OBJ.OpenRecordset _
                           (dbOpenForwardOnly, dbReadOnly, dbReadOnly)
   
           If R_REC![件数] = 0 Then
               欠番検索_二分探索_SQL = StartValue
   
               Exit Do
           ElseIf R_REC![最小値] <> StartValue Then
               欠番検索_二分探索_SQL = StartValue
   
               Exit Do
           ElseIf R_REC![最小値] = StartValue And _
                  R_REC![最小値] + 1 = R_REC![最大値] And _
                  R_REC![件数] < (FindValue - StartValue + 1) Then
               欠番検索_二分探索_SQL = R_REC![最大値] + 1
   
               Exit Do
           ElseIf R_REC![最小値] + 1 < R_REC![最大値] And R_REC![件数] = 2 Then
               欠番検索_二分探索_SQL = R_REC![最小値] + 1
   
               Exit Do
           ElseIf R_REC![最小値] = StartValue And _
                  (R_REC![最大値] - R_REC![最小値] + 1) = R_REC![件数] And _
                  R_REC![件数] < (FindValue - StartValue + 1) Then
               欠番検索_二分探索_SQL = R_REC![最大値] + 1
   
               Exit Do
           End If
   
           If R_REC![最小値] = StartValue And R_REC![最大値] = FindValue And _
              R_REC![最大値] - R_REC![最小値] + 1 = R_REC![件数] Then
               StartValue = FindValue + 1
               FindValue = FindValue + (EndValue - FindValue) \ 2 + 1
           Else
               EndValue = FindValue
               FindValue = StartValue + (EndValue - StartValue) \ 2
           End If
   
           R_REC.Close
       Loop
   
       R_REC.Close
   
       DB.Close
   
   End Function
   

9. モジュールを使った方法 二分探索 レコードポジション(YU-TANGさん提供)

   Public Function 欠番検索_二分探索_位置() As Long
   
       Dim 未走査開始位置  As Long
       Dim 未走査終了位置  As Long
       Dim 未走査区間      As Long
       Dim 欠番あり        As Boolean
       Dim i               As Long
   
       With CurrentDb.OpenRecordset("select ID from Sample order by ID")
   
           If Not .EOF Then
               .MoveLast
               未走査終了位置 = .AbsolutePosition
   
               ' ループで走査
               Do While True
                   i = .AbsolutePosition
                   欠番あり = .Collect(0) - i <> 1
                   If 欠番あり Then
                       未走査終了位置 = i - 1
                   Else
                       未走査開始位置 = i + 1
                   End If
   
                   未走査区間 = 未走査終了位置 - 未走査開始位置 + 1
                   ' 未走査区間がある場合
                   If 未走査区間 Then
                       .AbsolutePosition = 未走査開始位置 + (未走査区間 \ 2)
                   ' 未走査区間がない場合
                   Else
                       Exit Do      ' 走査終了
                   End If
               Loop
           End If
   
           欠番検索_二分探索_位置 = 未走査開始位置 + 1
   
           .Close
       End With
   
   End Function
   

計測

計測結果
確認データ件数:300万件
テーブル構造:ID(長整数), データ(テキスト(50)
キー:ID

なお、サンプル 1(IN句を使った方法)はお話にならないくらい遅いので計測していません。
また、サンプル 2(EXISTS句を使った方法)はTOP 1を使った結果を載せています

それぞれ3回計測した平均値を載せています。

SQLの結果はほぼ同じ(誤差の範囲内だと思う)です。

モジュールの全件サーチは件数が増えれば増えるほど欠番が後ろになればなるほど遅くなっていきます。
全件調べますから当然ですね。

二文探索法は今回の結果ではMove系メソッド版が最速となっています。
この速度だと実運用にも耐えられるのではないでしょうか？

Find系メソッド版もレコードポジション版もdbOpenDynasetを使っているのでキャッシュの効き具合などが影響し結果は一定しません。計測方法によっては逆転する可能性もあります。

応用

これらを応用すると他にキーがあっても調べられます。

SELECT
    IIf(先頭連番 > 1, 1, 欠番候補 + 1) AS 欠番
FROM
    (
        SELECT
            MIN(T1.連番) AS 欠番候補,
            (
                SELECT
                    MIN(連番)
                FROM
                     [テーブル名]
                WHERE
                     日付=#2009/05/29#
            ) AS 先頭連番
        FROM
            [テーブル名] AS T1 LEFT JOIN [テーブル名] AS T2 ON
            (T1.日付 = T2.日付 AND T1.連番 + 1 = T2.連番)
        WHERE
            T1.日付=#2009/05/29# AND
            T2.連番 Is Null
    ) AS [適当な名前]

モジュール版でやるにはFind系メソッド版とSQL版なら比較的楽にできると思います。
Move系メソッド版とレコードポジション版はかなり面倒なことになるでしょう。

その他

ほかにも方法はあると思います。こんなのもあるというのがありましたらぜひお知らせください。

通常、空番は欠番として扱うのがコンピュータシステムの基本です。取り扱いには十分ご注意ください。

謝辞

SQLサンプルと二分探索のアイディアを下さった銀の匙さん、二分探索関数を下さったYU-TANGさんには心からお礼申し上げます。ありがとうございます。