はじめに

株式取引システムで、リアルタイムデータから時足データを取得する処理がボトルネックになっていました。PostgreSQLのB-treeインデックス（二分木探索）を活用したクエリ最適化により、約6.6倍（14.9ms → 2.3ms）の高速化を実現したので、その手法を紹介します。

課題: 時足データの取得が遅い

株価エンジン起動時に、過去250時間分の時足データ（各時間帯の最終価格）を取得する必要がありました。

データベース構造

stock_prices テーブル（株価リアルタイムデータ）

┌────────┬─────────────────────┬──────────┬────────┐
│ symbol │ timestamp           │ price    │ volume │
├────────┼─────────────────────┼──────────┼────────┤
│ 1234   │ 2025-01-15 09:00:12 │ 1500.0   │ 1000   │
│ 1234   │ 2025-01-15 09:00:58 │ 1501.0   │ 500    │
│ 1234   │ 2025-01-15 09:01:23 │ 1502.0   │ 800    │
│ 1234   │ 2025-01-15 10:00:05 │ 1505.0   │ 1200   │
│ 1234   │ 2025-01-15 10:00:47 │ 1506.0   │ 700    │
│ ...    │ ...                 │ ...      │ ...    │
└────────┴─────────────────────┴──────────┴────────┘

インデックス: idx_symbol_time (symbol, timestamp)
データ量: 約1億レコード（全銘柄・全時刻の分足レベルデータ）

business_days テーブル（営業日カレンダー）

┌────────────┬──────────────────┐
│ date       │ is_business_day  │
├────────────┼──────────────────┤
│ 2025-01-15 │ true             │
│ 2025-01-16 │ true             │
│ 2025-01-17 │ false (土曜日)   │
│ 2025-01-18 │ false (日曜日)   │
│ 2025-01-19 │ false (祝日)     │
│ 2025-01-20 │ true             │
│ ...        │ ...              │
└────────────┴──────────────────┘

取得したいデータ

各時間帯（9:00, 10:00, 11:00...15:00）の最終価格を250時間分

2025-01-15 09:00台 → 1502.0 (09:01:23の価格)
2025-01-15 10:00台 → 1506.0 (10:00:47の価格)
2025-01-15 11:00台 → 1510.0 (11:00:55の価格)
...

最適化の核心: B-tree二分木探索で目的データに直接アクセス

❌ 旧方式: 集計テーブルを参照

事前に時足データを集計したテーブルhourly_aggregatedを使用していました。

SELECT symbol, timestamp, price, 
       open_price, high_price, low_price, volume,
       ma_5, ma_25, ma_50, ma_75, ma_250,
       -- 以下、多数のテクニカル指標カラム
FROM hourly_aggregated
WHERE symbol = '1234'
ORDER BY timestamp DESC
LIMIT 250

DB側の処理イメージ:

[PostgreSQL の処理]

1. hourly_aggregatedテーブル全体をスキャン
   ↓
2. WHERE symbol = '1234' で絞り込み
   ↓ (多数のカラムを含む大きなレコードを走査)
3. ORDER BY timestamp DESC でソート
   ↓
4. LIMIT 250 で上位250件を取得

【問題点】
- テーブルサイズが大きい（多数のカラム × 大量レコード）
- 全レコードスキャン → メモリ上でソート → 切り出し
- ヒープアクセスが多い（ディスクI/Oが多発）
- 集計テーブルの事前計算・維持コストが高い

✅ 新方式: LATERAL JOIN + 営業日カレンダー

ポイント: 複合インデックス(symbol, timestamp)のB-tree二分木探索を最大限活用

WITH business_hours AS (
    -- 営業日の営業時間のみを生成（9時〜15時）
    SELECT bd.date + (h.hour || ' hours')::INTERVAL as hour_start
    FROM business_days bd
    CROSS JOIN (SELECT generate_series(9, 15) as hour) h
    WHERE bd.is_business_day = true
      AND bd.date <= CURRENT_DATE
    ORDER BY bd.date DESC, h.hour DESC
    LIMIT 300
)
SELECT sp.timestamp, sp.price, sp.volume
FROM business_hours bh
CROSS JOIN LATERAL (
    -- 各時間帯の最終レコードを二分木探索で直接取得
    SELECT timestamp, price, volume
    FROM stock_prices sp
    WHERE symbol = '1234'
      AND timestamp >= bh.hour_start
      AND timestamp < bh.hour_start + INTERVAL '1 hour'
    ORDER BY timestamp DESC
    LIMIT 1
) sp
ORDER BY sp.timestamp DESC
LIMIT 250

DB側の処理イメージ:

[PostgreSQL の処理]

1. business_hours CTE: 営業日×営業時間を生成
   例: 2025-01-15 09:00, 2025-01-15 10:00, ...
   ↓
2. 各時間帯ごとにLATERAL JOIN実行:
   
   【時間帯: 2025-01-15 09:00】
   B-treeインデックス (symbol, timestamp) で二分木探索
   ↓
   log₂(N) の計算量で (symbol='1234', timestamp>='2025-01-15 09:00:00') 
   の範囲開始点を特定
   ↓
   インデックスから該当データブロックのアドレスを取得
   ↓
   データブロックに直接アクセス（ピンポイントI/O）
   ↓
   timestamp DESC でスキャンして LIMIT 1 → 最終レコード取得
   ↓
   次の時間帯へ...

【改善点】
✅ B-tree二分木探索で目的データのアドレスに直接ジャンプ
✅ 各時間帯で1レコードのみ取得（早期終了）
✅ 必要なカラムのみSELECT（price, volumeのみ）
✅ 営業日のみ検索（土日祝をスキップ）

なぜ速いのか？

1. B-tree二分木探索による効率的なアクセス

PostgreSQLのB-treeインデックスは二分木構造で、log₂(N)の計算量で目的データを特定できます。

B-treeインデックスの二分木探索イメージ:

                    [ルートノード]
                   /              \
         [symbol='1000'台]    [symbol='5000'台]
            /        \              /         \
    ['1000'-'2000'] ['2000'-'3000'] ...     ...
         /    \
   ['1234']  ['1500']
      ↓
   [timestamp範囲]
      ↓
   データブロックアドレス: 0x1A2B3C

探索回数: log₂(100,000,000) ≒ 27回の比較で特定

線形探索（フルスキャン）との違い:

❌ 線形探索: 1億レコードを順番にチェック → O(N)
✅ B-tree二分木探索: 約27回の比較で到達 → O(log N)

2. 営業日・営業時間に絞り込み

土日祝日をスキップ（約30%削減）
営業時間外（16時〜翌8時）をスキップ（約71%削減）
実質的な検索対象を約80%削減

3. LATERAL JOINによる早期終了

各時間帯でLIMIT 1により、最終レコードを見つけた瞬間にスキャン終了。

結果

項目	旧方式	新方式	改善率
実行時間	14.9ms	2.3ms	6.6倍高速化
データソース	集計テーブル	リアルタイムテーブル	リアルタイム性向上
I/O効率	多数のカラム取得	必要なカラムのみ	メモリ効率向上
スキャン方式	線形スキャン	B-tree二分木探索	計算量O(N)→O(log N)

まとめ

PostgreSQLのB-treeインデックスによる二分木探索を活用することで、大量データから目的のレコードに効率的にアクセスできます。

成功のポイント:

✅ 適切な複合インデックス設計: (symbol, timestamp)
✅ インデックスを活用できるクエリ構造: LATERAL JOIN
✅ 不要な検索範囲の排除: 営業日カレンダーで絞り込み

時系列データを扱う金融システムでは、この手法が非常に効果的です。同じアプローチで日足データも**3,530倍高速化（28.6秒 → 8.1ms）**を実現しました。

参考: クエリ全体

完全なSQLクエリ（クリックで展開）

WITH business_hours AS (
    SELECT bd.date + (h.hour || ' hours')::INTERVAL as hour_start
    FROM business_days bd
    CROSS JOIN (
        SELECT generate_series(9, 15) as hour
    ) h
    WHERE bd.is_business_day = true
      AND bd.date <= CURRENT_DATE
    ORDER BY bd.date DESC, h.hour DESC
    LIMIT 300
)
SELECT sp.timestamp, sp.price, sp.volume
FROM business_hours bh
CROSS JOIN LATERAL (
    SELECT timestamp, price, volume
    FROM stock_prices
    WHERE symbol = %s
      AND timestamp >= bh.hour_start
      AND timestamp < bh.hour_start + INTERVAL '1 hour'
    ORDER BY timestamp DESC
    LIMIT 1
) sp
ORDER BY sp.timestamp DESC
LIMIT 250