• 解説

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

    連番の空番を調べたいってのは結構ある話ですが、わざわざ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回計測した平均値を載せています。

    欠番 探索回数(上段)・計測時間(下段 単位:ミリ秒 ※小数点以下切捨て) 数字はサンプルの番号
    2 3 4 5 6 7 8 9
    1 1 1 1 1 22 21 1 23
    50,890 8,494 22,489 0 864 406 3,964 640
    450,000 1 1 1 450,000 23 25 20 23
    51,765 8,458 22,567 1,171 890 390 8,364 734
    1,500,000 1 1 1 1,500,000 21 21 1 22
    51,953 8,463 22,573 3,906 885 401 5,609 1,609
    2,500,000 1 1 1 2,500,000 22 21 21 23
    51,234 8,442 22,614 6,568 948 411 6,609 2,750
    なし(3,000,001) 1 1 1 3,000,001 1 1 1 1
    51,922 8,494 22,552 7,822 536 0 2,677 745
    処理平均 51,552 8,470 22,559 3,893 824 321 5,444 1,295

    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さんには心からお礼申し上げます。ありがとうございます。

スポンサードリンク

スポンサードリンク

説明がわからないなどありましたらお問い合わせでお知らせください。

ここに掲載された情報を使用したことによって発生した、いかなる損害に対しても
管理者である雅は一切責任を負いません。

スポンサードリンク