質問への回答

質問の歴史

この課題は、キャパシティプランニングやリソース配分の領域から生じており、特にホテル予約プラットフォームやクラウドインフラの自動スケーリング、医療施設のスケジューリングなどのシステムに関連しています。初期の解決策は、カーソルベースのイテレーションや外部アプリケーションロジックを使用してタイムラインをイテレートしており、大規模データセットに対して深刻なパフォーマンスのペナルティを受けていました。ANSI SQL:2003のウィンドウ関数の登場により、トランザクション分析への純粋な関係的アプローチが可能になり、データベースがエンジン内で複雑な区間演算を効率的に処理できるようになりました。

問題

start_timeとend_timeのタイムスタンプを持つリソース予約のテーブルが与えられたとき、単一の瞬間にアクティブな同時予約の最大数を特定し、このピークが発生した特定の時間ウィンドウを特定することが目的です。標準的な集計は時間的データを圧縮し、単純なジョインは区間が重なるとデカルト爆発を引き起こすため、問題は複雑化します。堅牢な解決策は、区間の開始と終了を離散イベントとして扱い、すべての遷移ポイントでアクティブなリソースの実行カウントを計算しなければなりません。

解決策

標準的なアプローチは、UNION ALLを使用して区間を離散イベントに変換し、開始（重み+1）と終了（重み-1）を分け、次にSUM() OVER (ORDER BY timestamp)を適用して同時性を追跡します。同じタイムスタンプで同時に開始/終了がある場合、終了イベントを開始イベントよりも先に処理する必要があります（セカンダリソートキーを使用）。最後に、最大同時性値をフィルタリングするためにこれをCTEでラップします。

WITH events AS (
  SELECT start_time AS ts, 1 AS delta, 0 AS is_end
  FROM reservations
  UNION ALL
  SELECT end_time AS ts, -1 AS delta, 1 AS is_end
  FROM reservations
),
concurrency AS (
  SELECT ts,
         SUM(delta) OVER (ORDER BY ts, is_end, delta 
                          ROWS UNBOUNDED PRECEDING) AS concurrent_count
  FROM events
)
SELECT MAX(concurrent_count) AS peak_concurrency
FROM concurrency;

ピーク使用の特定の時間ウィンドウを見つけるには、最大と等しい数を持つ連続するタイムスタンプの間の期間を特定するために再結合します。

人生の中の状況

あるSaaSプラットフォームは、jobsテーブルにおいて数百万のビデオトランスコーディングジョブを追跡し、started_atとcompleted_atのタイムスタンプを持っていました。オペレーションチームは、GPU利用率が100%に達した正確な期間を特定してキューのスケジューリングを最適化する必要がありました。

考慮されたアプローチの一つは、カーソルを使用して時間的にイテレートし、開始時にカウンターをインクリメントし、終了時にデクリメントすることでした。これは、命令型言語に慣れ親しんでいる開発者にとっては単純でしたが、この方法は行を順次処理し、本番データの処理に45分以上かかり、テーブルをロックしました。また、読み取りの一貫性を確保するために、複雑なトランザクション管理が必要でした。

別のアプローチでは、1分ごとの行を持つ時系列テーブルを生成し、BETWEEN述語を使用して区間と結合しました。これにより正確な結果が得られましたが、1年間の分単位の精度を維持するためには数十億の行が必要で、一時的なストレージをテラバイト消費し、サブミニットのピークスパイクを捕捉できませんでした。

チームは、開始と終了を+1/-1イベントとして扱うイベントベースのUNION ALLアプローチを選択しました。これにより、タイムスタンプ列に標準のB木インデックスを使用して、クエリは12秒で実行されました。この方法は、ジョブが他のジョブが開始する正確に終了するというエッジケースを正しく処理しました。

分析により、ピーク同時性は毎晩のバッチ処理中の02:00から02:07 UTCの間に発生し、847の同時ジョブに達したことが明らかになりました。このウィンドウの特定のために動的キューのスロットリングを実装することで、カスケード失敗を防ぎ、インフラの過剰な提供を30%削減しました。

候補者がしばしば見逃すこと

ゼロ期間の区間（start_time = end_time）をどのように処理して、同時性カウントを不正に膨らませないようにしますか？

ゼロ期間の区間は、同時負荷に寄与すべきでない瞬間的なイベントを表します。これを標準の区間として扱うと、自己終了イベントの間アクティブとしてカウントされる可能性があります。この解決策は、厳格な順序キーを割り当てる必要があります：タイムスタンプが衝突したときに終了イベント（-1）を開始イベント（+1）の前に処理し、ビジネスロジックに応じてゼロ期間の区間をイベントストリームから完全に除外するか、0のデルタを割り当てます。ANSI SQLでは、区別子列を追加することで実装されます：ORDER BY ts, is_end ASC, delta ASC、これにより終了が新しい割り当てのカウントを同じタイムスタンプでインクリメントする前にデクリメントします。

開始と終了イベントを組み合わせる時にUNIONの代わりにUNION ALLを使用すると、なぜイベントベースのアプローチが潜在的に不正確な結果を返す可能性がありますか？

UNIONは暗黙的にDISTINCT操作を実行し、重複タイムスタンプを圧縮します。もし二つの予約が正確に2023-10-01 10:00:00に開始すると、UNIONはこれを一つの行に減少させ、累積合計が一つの+1増加を逃すことになります。これにより同時性を過小評価する結果になります。UNION ALLは、各個別のinterval境界を別々のイベントとして保持し、これは数学的に必要です。なぜなら、各予約が全体の負荷に独立して寄与するからです。候補者は、この違いを見逃し、ユニークなタイムスタンプを仮定しがちですが、正確な集計には多重性が不可欠です。

最大値だけでなくピーク同時性の特定の時間ウィンドウを計算する際に、連続する時間期間が同じピーク値を持つ場合、出力にギャップが生じないようにするにはどうすればよいですか？

最大同時性値を特定した後、この値が発生するすべてのタイムスタンプを見つけるために再結合します。それによって離散ポイントが得られます。連続的な持続ブロックを再構築するためには、Gaps and Islands技術を適用する必要があります：**LAG()**を使用して、前の行がピークであったかどうかを確認し、LEAD()を使用して、次の行がピークであるかどうかを確認します。前の値が異なる行（アイランドの開始）または次の値が異なる行（アイランドの終了）のみを出力します。その後、これらをROW_NUMBER()を使用して開始-終了ペアを作成します。候補者は、しばしば生のタイムスタンプリストを出力したり、カウント値でGROUP BYを使用したりして、連続するピークインシデントを識別するために必要な時間的隣接情報を失います。