第2回　列指向ストレージとインデックス構造¶

本日の到達目標¶

行指向と列指向ストレージの違いを、物理的なI/Oの観点から説明できる
B木とLSM木の構造と、それぞれ得意な操作を説明できる
多変量データの反復試行（特徴量追加・モデル比較）において列指向が有利な理由を説明できる

1. なぜストレージの仕組みを学ぶか¶

多変量解析では以下のような操作を 何度も 繰り返す： - 説明変数を追加・削除してモデルを比較する - 学習データと検証データを分割してスコアを評価する - 数百万行 × 数十列のデータから特定の列だけを抽出する

この「繰り返し」がボトルネックになる。
ストレージの仕組みを理解することで、なぜ列指向が分析ワークロードに向くかが分かる。

2. 行指向 vs 列指向ストレージ¶

2.1 行指向ストレージ（Row-Oriented Storage）¶

構造：1レコード（行）が連続したバイト列として格納される

[id=1, 日付=2024-01-01, 売上=1200, 天気=晴, 気温=15.3]
[id=2, 日付=2024-01-02, 売上=980,  天気=雨, 気温=12.1]
[id=3, 日付=2024-01-03, 売上=1500, 天気=曇, 気温=13.8]
...

特性 - 得意：特定の行（レコード）を丸ごと読み書きする操作（INSERT, UPDATE, SELECT ） - 苦手：少数の列だけを全行スキャンする操作（SELECT 売上 FROM 売上表） - 代表例*：PostgreSQL, MySQL, Oracle DB（OLTPシステム向け）

2.2 列指向ストレージ（Column-Oriented Storage）¶

構造：同一列の値が連続したバイト列として格納される

id列:   [1, 2, 3, 4, 5, ...]
売上列: [1200, 980, 1500, 1100, 2300, ...]
天気列: [晴, 雨, 曇, 晴, 晴, ...]
気温列: [15.3, 12.1, 13.8, 14.2, 16.0, ...]

特性 - 得意：特定の列だけを全行スキャンする操作（集計・分析） - 苦手：特定行の全列を一度に読む操作（単一レコードの参照） - 代表例：Apache Parquet, Apache ORC, Amazon Redshift, DuckDB（OLAPシステム向け）

2.3 I/O削減の原理¶

具体例：1億行 × 100列のテーブルから5列だけを読む場合

ストレージ型	読み込むデータ	説明
行指向	100列分（全部）	行単位で読むため不要な95列も読む
列指向	5列分のみ	必要な列だけを直接読める

削減率 = (100 - 5) / 100 = 95% のI/Oを削減できる

2.4 圧縮効率の違い¶

列指向では同じ型・似た値が連続するため、圧縮効率が高い。

データ型	圧縮手法	効果
整数列（増加傾向）	デルタ符号化	差分だけを記録して大幅に削減
文字列（カテゴリ）	辞書符号化	実値の代わりに整数IDを記録
繰り返し多い列	ランレングス符号化（RLE）	"晴晴晴曇曇"→"晴×3, 曇×2"

3. インデックス構造¶

3.1 B木（B-tree）¶

ユースケース：範囲検索・等値検索を高速化（例：日付範囲での絞り込み）

構造の概略

               [2024-07-01]
              /              \
    [2024-03-01]          [2024-09-01]
    /       \              /       \
[1月〜3月] [4月〜6月] [7月〜9月] [10月〜12月]

特性 - 木の高さ = O(log N) → 探索が高速 - すべての葉ノードが同じ深さ（バランス木） - 得意：範囲検索（WHERE 日付 BETWEEN '2024-01-01' AND '2024-03-31'） - 弱点：大量の書き込みでノード分割が頻発し、書き込みが遅くなる

3.2 LSM木（Log-Structured Merge-tree）¶

ユースケース：書き込みが多いシステム（センサーログ、IoT等）

構造の概略

書き込み → MemTable（メモリ内、常にソート済み）
              ↓ 容量閾値を超えると
           SSTable L0（ディスク上の不変ファイル）
              ↓ バックグラウンドで定期的にマージ
           SSTable L1, L2, ... （レベルが上がるほど大きく、重複なし）

特性 - 書き込みは常にMemTableへの追記 → 書き込みが高速（ランダムI/Oがない） - 読み込みは複数レベルを探索 → 書き込みよりやや遅い - 代表例：Apache Cassandra, RocksDB, Apache HBase

3.3 B木 vs LSM木の比較¶

観点	B木	LSM木
書き込み	ランダムI/O発生・やや遅い	順次I/O・高速
読み込み	高速（インデックス直接探索）	やや遅い（複数ファイル探索）
適用	OLTP（更新＋参照の混在）	書き込み集約型（ログ・センサー）
データ例	関係型DB（PostgreSQL等）	Cassandra, RocksDB

4. 多変量解析への応用¶

4.1 特徴量追加の反復試行¶

重回帰分析では「変数を一つ加えたらAICが下がるか？」を繰り返し検証する。

問題：行指向ストレージでは毎回全列を読み直す → 無駄なI/Oが大きい
解決：列指向ストレージなら追加した列だけを読み込めばよい

試行1: y, x1, x2         → 3列読み込み
試行2: y, x1, x2, x3     → 3列は再利用 + x3を1列追加
試行3: y, x1, x2, x3, x4 → 4列は再利用 + x4を1列追加

4.2 モデル比較のI/O設計¶

後半の各回では以下のような比較を繰り返す：

タスク	読む列	行数
重回帰のVIF診断	説明変数のみ	全行
PCA（第8-9回）	特徴行列 X の全列	全行
k-means（第10-11回）	PCA出力（低次元）	全行
PLS（第12-13回）	X と y	全行

要点：分析用ファイルを列指向フォーマット（Parquet等）で保存しておくと、
必要な列だけ読む操作が大幅に速くなる。

5. 版管理と再現性（整合性との接続）¶

列指向ストレージと合わせて考えるべき問題：特徴量のズレ

例：1月1日にモデルAを構築、1月31日にモデルBを構築
→ その間に売上データが修正・追加されていた場合、比較が不公平になる

解決策：
- 分析に使うデータを「版」として固定する（スナップショット） - Parquetファイルとして日付付きで保存、または Delta Lake 等を利用

→ これは第3回「整合性」の議題へ続く

6. 基盤リンクの整理¶

基盤概念	本回での役割	後半分析での意味
列指向	核心：必要な列だけ読む・圧縮で削減	特徴量追加・モデル比較の反復を支える
整合性	版管理の必要性を予告	学習と検証でデータがズレないようにする
DAG	特徴量生成を再計算可能にする考え方	前処理パイプラインの設計（第4回）
近似	列数が多い場合の索引探索を近似で	候補変数の絞り込みを高速化

7. 本日のまとめ¶

行指向はレコード単位の読み書きに強く、列指向は列単位のスキャン・集計に強い
多変量分析の反復試行では列指向が有利（不要な列を読まない）
B木は範囲検索、LSM木は書き込み集約シナリオに向く
分析用データを列指向フォーマットで固定（版管理）することで再現性を確保できる

次回予告¶

第3回では CAP定理と整合性モデル を扱う。
分散データベースにおける「整合性」「可用性」「分断耐性」のトレードオフを理解し、
訓練・検証データを再現可能に作るための設計原則を学ぶ。

事後課題¶

下記を調べ、A4半枚程度でまとめること： 1. Apache Parquet と CSV を比較して、分析ワークロードでどちらが有利か理由と共に説明する 2. DuckDB が「インメモリ列指向エンジン」として近年注目される理由を調べる

第2回 列指向ストレージとインデックス構造¶