はじめに
株式取引システムで、リアルタイムデータから時足データを取得する処理がボトルネックになっていました。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