行/列志向とか圧縮とかその辺の話

列指向データベース（Columnar Database）と行指向データベース（Row-Oriented Database）について書いていく。とりあえず、列？行？という感じな人もいると思うが、どういうまとまりでデータを保存するか？というところの違いがある。

前に書いた内容では、OLTP, OLAPなどの分類方法での説明をしたが、今回は列志向、行志向という分類の話をする。

mnagaa.hatenablog.com

行指向データベース（Row-Oriented Database）

行指向データベースは、データが行単位で格納されるデータベースの一種。各行はテーブルのすべての列のデータを含み、一つの行が一つのレコードを表している。この構造は、関係データベース管理システム（RDBMS）で広く使用されている。

利点

トランザクション処理に最適

行指向データベースは、INSERT、UPDATE、DELETEなどのトランザクション処理が効率的。データベースは行単位でデータを読み書きするため、特定の行に対する変更が迅速に行える。

行単位の操作が速い

行指向データベースは、一度に1行ずつ処理するため、行単位の操作が速い。これにより、レコード単位の操作が頻繁に行われるアプリケーションにおいて高いパフォーマンスを発揮する。

スキーマの整合性が高い

RDBMSは、スキーマの整合性を維持するための強力な機能を提供。これにより、データの一貫性と整合性が保たれ、複雑なデータ関係を持つアプリケーションに適している。

欠点

集計クエリに非効率

行指向データベースは、SUM、AVGなどの集計クエリでは非効率。すべての行をスキャンして必要な列を抽出するため、大量のデータを扱う場合、パフォーマンスが低下する。

ディスクI/Oが多い

特定の列のデータのみを取得する場合でも、行全体を読み込む必要があるため、ディスクI/Oが増加。これにより、特に大規模なデータセットにおいてI/O負荷が高くなる。

使用例

OLTPシステム（オンライン・トランザクション処理）

行指向データベースは、銀行システムや販売管理システムなど、頻繁にデータの挿入、更新、削除が行われるシステムで広く使用される。これらのシステムでは、トランザクションの迅速な処理とデータの整合性が求められるため、行指向データベースが適している。

CRM（顧客関係管理）システム

顧客データの管理において、個々の顧客レコードを頻繁に参照、更新する必要があるため、行指向データベースが効果的。顧客の問い合わせ履歴や購入履歴などのデータを迅速にアクセスできる。

行指向データベースの例

行指向データベースのアーキテクチャ

ストレージエンジン

行指向データベースのストレージエンジンは、データを行単位でディスクに格納。これにより、特定の行のデータを迅速に読み書きできる。ストレージエンジンには、インデックスを使用してクエリパフォーマンスを向上させる機能も含まれている。

インデックス

行指向データベースは、インデックスを使用してクエリのパフォーマンスを向上させる。インデックスは、特定の列の値を迅速に検索できるようにするためのデータ構造。これにより、検索クエリの実行時間が大幅に短縮される。

行指向データベースの最適化技術

クエリ最適化

クエリ最適化は、データベースエンジンがクエリを最適な方法で実行するための技術。これには、クエリの実行計画を生成し、インデックスを使用してクエリを効率的に実行する方法が含まれる。

キャッシュ

行指向データベースは、頻繁にアクセスされるデータをキャッシュに保存することで、クエリパフォーマンスを向上させる。キャッシュにより、ディスクI/Oの回数が減少し、クエリの応答時間が短縮される。

行指向データベースにおけるキャッシュ

バッファキャッシュ

行指向データベースは、データをメモリにキャッシュするためにバッファキャッシュ（またはバッファプール）を使用する。バッファキャッシュは、データベースがディスクから読み込んだデータを一時的に保存する領域。これにより、同じデータに対する後続のアクセスが迅速に行えるようになる。

インデックスキャッシュ

インデックスキャッシュは、データベースインデックスをメモリにキャッシュする仕組み。インデックスは、データベース内の特定の列の値を迅速に検索するためのデータ構造であり、これをキャッシュすることで検索クエリのパフォーマンスが大幅に向上させる。

クエリキャッシュ

クエリキャッシュは、特定のクエリの結果をキャッシュする仕組み。これにより、同じクエリが再度実行された場合、キャッシュされた結果を返すことで、データベースの負荷を軽減し、応答時間を短縮させる。

キャッシュの最適化技術

キャッシュポリシーの設定

キャッシュポリシーは、どのデータをキャッシュするか、またどのデータをキャッシュから削除するかを決定するルール。一般的なキャッシュポリシーには、以下のようなものがある：

LRU（Least Recently Used）: 最近使用されていないデータから順にキャッシュから削除する。
LFU（Least Frequently Used）: 使用頻度が低いデータから順にキャッシュから削除する。
MRU（Most Recently Used）: 最近使用されたデータを優先的にキャッシュから削除する。

プリフェッチ

プリフェッチは、将来のアクセスを予測してデータを事前にキャッシュに読み込む技術。これにより、データが必要になる前にキャッシュにロードされているため、クエリの応答時間をさらに短縮できる。

列指向データベース（Columnar Database）

データが列単位で格納される。各列のデータが連続して保存される。
データウェアハウスやビッグデータ解析に最適なデータ格納形式。

利点

集計クエリに最適: 特定の列だけを読み込むため、SUM、AVGなどの集計クエリが効率的に処理される。
圧縮率が高い: 同じ列のデータが連続して格納されるため、圧縮が効率的に行われる。
ディスクI/Oが少ない: 必要な列だけを読み込むため、ディスクI/Oが減少する。

欠点

トランザクション処理に非効率: 行全体を扱う操作が多いため、INSERT、UPDATE、DELETE操作が遅くなることがある。
複雑な更新が難しい: 列ごとにデータが分かれているため、複雑な更新操作が難しい。

使用例

OLAPシステム（オンライン分析処理）: データウェアハウス、ビジネスインテリジェンス（BI）、ビッグデータ解析など、大量のデータを集計・分析するシステム。

データベース種類	利点	欠点	使用例
行指向データベース	トランザクション処理に優れる、行単位の操作が速い	集計クエリに非効率、ディスクI/Oが多い	OLTPシステム
列指向データベース	集計クエリに優れる、圧縮率が高い、ディスクI/Oが少ない	トランザクション処理に非効率、複雑な更新が難しい	OLAPシステム

具体例と参照局所性

行指向データベースの具体例

格納イメージ

  Row 1: [Column1, Column2, Column3, ...]
  Row 2: [Column1, Column2, Column3, ...]
  Row 3: [Column1, Column2, Column3, ...]

アクセスパターン:
- 行の取得: 特定の行を取得する際には、ディスク上の一連のデータを読み込む。例えば、顧客IDに基づいて顧客の詳細を取得する場合。
- メリット: トランザクション処理において、行全体を一度に処理するため効率的。

列指向データベースの具体例

格納イメージ

  Column1: [Row1, Row2, Row3, ...]
  Column2: [Row1, Row2, Row3, ...]
  Column3: [Row1, Row2, Row3, ...]

アクセスパターン:
- 列の取得: 特定の列を取得する際には、ディスク上の連続したデータを読み込む。例えば、全顧客の年齢の平均を計算する場合。
- メリット: データ分析や集計クエリにおいて、必要な列だけを読み込むため効率的。

参照局所性の重要性

参照局所性（データの物理的な配置とアクセスパターンの一致）は、キャッシュ効率とディスクI/Oのパフォーマンスに直接影響を与える。

行指向データベースの参照局所性

行単位の操作が中心となるトランザクション処理では、行全体が連続して格納されることで高いキャッシュ効率が得られる。

列指向データベースの参照局所性

列単位の操作が中心となる分析処理では、列ごとにデータが連続して格納されることで高いキャッシュ効率が得られる。

主な圧縮アルゴリズム

詳しくは別で書きます。

ランレングス圧縮（Run-Length Encoding, RLE）

概要: 同じ値が連続するデータをその長さとともに圧縮する。例えば、列に「AAAAABBBCCCC」がある場合、「5A3B4C」として保存する。
適用例: 同じ値が連続する場合に効果的。カテゴリ列やフラグ列など。

Flags: [1, 1, 1, 0, 0, 1, 1, 1, 1, 0]

ランレングス圧縮適用後:
- データ: [3, 1, 2, 0, 4, 1, 1, 0]

辞書圧縮（Dictionary Encoding）

概要: 列内の値を辞書に登録し、各値を辞書内の位置（インデックス）で参照する。例えば、「apple, banana, apple, apple」を「1, 2, 1, 1」として保存する。
適用例: カテゴリデータや文字列データなど、値の種類が限定されている場合に有効。

Category: [apple, banana, apple, apple, banana]

辞書圧縮適用後:
- 辞書: {1: "apple", 2: "banana"}
- データ: [1, 2, 1, 1, 2]

デルタ圧縮（Delta Encoding）

概要: 連続する値の差分（デルタ）を保存する。例えば、時系列データ「100, 101, 102, 103」を「100, +1, +1, +1」として保存する。
適用例: 数値データや時系列データなど、連続する値が増減する場合に有効。

Timestamps: [100, 101, 102, 103]

デルタ圧縮適用後:
- データ: [100, +1, +1, +1]

ビットマップインデックス（Bitmap Index）

概要: 各異なる値に対してビットマップを作成し、データの存在をビットで表現する。例えば、列に「A, B, A, C」がある場合、「A=1100, B=0010, C=0001」として保存する。
適用例: 値の種類が少ないカテゴリデータやフラグデータに有効。

ハフマン符号化（Huffman Encoding）

概要: 頻度の高い値に短いビット列を、頻度の低い値に長いビット列を割り当てる。圧縮効率が高い。
適用例: 一般的な文字列データやカテゴリデータなど。

圧縮のメリット

ストレージ節約: データの格納サイズが減少し、ストレージコストが削減される。
クエリパフォーマンス向上: 圧縮されたデータを効率的に読み込み、メモリやI/Oの使用量が減少することで、クエリの実行速度が向上する。
キャッシュ効率向上: 圧縮により、同じデータ量をより小さなメモリフットプリントで保持できるため、キャッシュ効率が向上する。

行指向データベースの圧縮アルゴリズム

辞書圧縮（Dictionary Encoding）

概要: 列指向データベースでも使用されるが、行指向データベースでも有効。各行の値を辞書に登録し、インデックスで参照する。
適用例: カテゴリデータや文字列データなど、値の種類が限定されている場合に有効。

Table: Employees
Columns: [Name, Department, Position]

Row 1: ["Alice", "Sales", "Manager"]
Row 2: ["Bob", "HR", "Recruiter"]
Row 3: ["Alice", "HR", "Manager"]

辞書圧縮適用後:
- 辞書: {1: "Alice", 2: "Bob", 3: "Sales", 4: "HR", 5: "Manager", 6: "Recruiter"}
- データ: [[1, 3, 5], [2, 4, 6], [1, 4, 5]]

LZ圧縮（Lempel-Ziv Compression）

概要: 一般的なデータ圧縮アルゴリズムで、データの繰り返しパターンを検出し、それを短い参照で置き換えることで圧縮する。LZ77、LZ78、LZWなどのバリエーションがある。
適用例: 任意のデータに対して適用可能で、行全体のデータを圧縮するのに適している。

Row 1: "The quick brown fox jumps over the lazy dog."
Row 2: "The quick brown fox jumps over the lazy cat."

LZ圧縮適用後:
- データ: "The quick brown fox jumps over the lazy dog." -> LZ圧縮でパターンを検出し、短い参照で置き換える。

ハフマン符号化（Huffman Encoding）

概要: 頻度の高いデータに短いビット列を、頻度の低いデータに長いビット列を割り当てる圧縮技術。データ全体の頻度分析に基づいて効率的な符号化を行う。
適用例: 文字列データやカテゴリデータなど、頻度の偏りがある場合に有効。

ページレベル圧縮

概要: データベースページ（通常8KBまたは16KB）単位で圧縮を行う。各ページのデータを圧縮し、ストレージ使用量を削減する。
適用例: データの物理的なページ単位での管理を行うRDBMSで一般的に使用される。

Data Page: [Row 1, Row 2, Row 3, ..., Row N]

ページレベル圧縮適用後:
- 圧縮されたページ: ページ全体のデータを一度に圧縮し、ストレージ使用量を削減する。

NULL値の圧縮

概要: NULL値を効率的に圧縮する手法。多くの列でNULLが頻出する場合、NULLの位置をビットマップで管理し、ストレージを節約する。
適用例: 列にNULL値が多く含まれる場合に有効。

圧縮のメリット

ストレージ節約: データの格納サイズが減少し、ストレージコストが削減される。
クエリパフォーマンス向上: 圧縮されたデータを効率的に読み込み、メモリやI/Oの使用量を減少させることで、クエリの実行速度が向上する。

圧縮のデメリット

圧縮・解凍のオーバーヘッド: 圧縮されたデータを使用するたびに解凍する必要があるため、オーバーヘッドが発生する。
特定のクエリパフォーマンスの低下: 特定のクエリや操作において、圧縮のために追加の計算が必要となり、パフォーマンスが低下する場合がある。

列指向データベースの更新処理の難しさ

圧縮の再編成

理由: 列指向データベースでは、同じ列のデータが連続して格納され、効率的に圧縮されている。データの更新や削除が発生すると、この圧縮されたデータの再編成が必要になる。
影響: 圧縮データの再編成には時間とリソースがかかるため、更新操作が遅くなる。特に、大量のデータが含まれる列の場合、この影響が顕著。

列単位のデータ配置

理由: 列指向データベースでは、行のデータが複数の列に分散して格納されている。行全体を更新する場合、複数の列に対して個別にアクセスし、更新する必要がある。
影響: 複数の列に対して個別に更新を行うため、更新操作が複雑化し、パフォーマンスが低下する。

更新処理を改善するための対策

Write-Optimized Storage（ライト最適化ストレージ）

メモリ内書き込み: 更新操作をまずメモリ内のライト最適化ストレージ（WOS）に記録。これにより、ディスク上の圧縮データに対する即時の再編成を避ける。
バッチ処理: 一定期間または一定量の更新が蓄積された後に、バッチ処理でディスク上の圧縮データに反映させる。再編成のコストを効率化する。
Write-Optimized Storage（WOS）の使用例

-- メモリ内のWOSに更新を記録
UPDATE accounts SET balance = balance - 100 WHERE account_id = 'A';

-- バッチ処理でディスク上のデータを更新
COMMIT;

Delta Storage（デルタストレージ）

変更の記録: 更新操作をデルタストレージに記録し、元のデータは変更せずに保持。頻繁な更新操作が発生しても元の圧縮データに対する負担を軽減する。
マージプロセス: 一定の条件で、デルタストレージのデータを元のデータとマージし、圧縮データを更新する。これにより、圧縮データの再編成を効率的に行う。
Delta Storageの使用例

-- デルタストレージに更新を記録
UPDATE accounts SET balance = balance - 100 WHERE account_id = 'A';

-- マージプロセスで圧縮データを更新
MERGE DELTA;

分割アプローチ（Segmented Approach）

データの分割: データを複数のセグメントに分割して格納。更新操作は特定のセグメントに対してのみ行われ、他のセグメントには影響を与えない。
セグメントの再編成: 必要に応じて、特定のセグメントのみを再編成する。これにより、全体の再編成コストを削減する。

列指向ファイルフォーマットと圧縮

Parquetなどの列指向ファイルフォーマットも、同様の圧縮アルゴリズムを使用してデータを効率的に保存する。 ParquetはApache Hadoopエコシステムで広く使用されており、特にデータウェアハウスやビッグデータ分析において効果的。

Parquetの圧縮アルゴリズム

ランレングス圧縮（Run-Length Encoding, RLE）

概要: 同じ値が連続するデータの長さを圧縮。例えば、「AAAAABBBCCCC」を「5A3B4C」として保存する。
適用例: 同じ値が繰り返されるデータ列。

辞書圧縮（Dictionary Encoding）

概要: 列内の値を辞書に登録し、各値を辞書内のインデックスで参照。例えば、「apple, banana, apple, apple」を「1, 2, 1, 1」として保存する。
適用例: 繰り返しの多いカテゴリデータや文字列データ。

デルタ符号化（Delta Encoding）

概要: 連続する値の差分（デルタ）を保存。例えば、時系列データ「100, 101, 102, 103」を「100, +1, +1, +1」として保存する。
適用例: 連続する数値データや時系列データ。

ビットパッキング（Bit Packing）

概要: データをビット単位で格納し、効率的に圧縮。特に整数値に対して効果的。
適用例: 整数データ列。

Parquetの圧縮設定

Parquetファイルフォーマットでは、各列に対して異なる圧縮アルゴリズムを適用できる。以下は、Parquetファイルの圧縮設定の例。

Parquetファイルの圧縮設定（Python）

import pandas as pd
import pyarrow as pa
import pyarrow.parquet as pq

# サンプルデータ
data = {
    'category': ['apple', 'banana', 'apple', 'banana', 'apple'],
    'value': [1, 2, 3, 4, 5],
    'timestamp': [100, 101, 102, 103, 104]
}

df = pd.DataFrame(data)

# Parquetファイルに書き込む際の圧縮設定
table = pa.Table.from_pandas(df)
pq.write_table(
    table,
    'sample.parquet',
    compression='SNAPPY',  # 圧縮アルゴリズムの指定（例：SNAPPY, GZIP, BROTLIなど）
    use_dictionary=True,   # 辞書圧縮を有効にする
    use_deprecated_int96_timestamps=True  # 古い形式のタイムスタンプを使用
)

アルゴリズム	特徴	適用例
SNAPPY	高速な圧縮と解凍が特徴。多くのシナリオでバランスが良い。	一般的なデータ分析タスク
GZIP	高圧縮率を提供するが、SNAPPYよりも圧縮と解凍に時間がかかる。	ストレージコスト削減が重要で、読み書き速度が重視されないシナリオ
BROTLI	非常に高い圧縮率。特にテキストデータに対して効果的。	テキストデータの圧縮。ウェブコンテンツの配信
LZ4	非常に高速な圧縮と解凍。SNAPPYに似ているが、圧縮率はやや低い。	低レイテンシが要求されるアプリケーション
ZSTD (Zstandard)	高圧縮率と高速な圧縮・解凍を両立。最新のアルゴリズムで、多くのデータ形式に適している。	バランスの取れた圧縮率と速度が要求されるシナリオ
UNCOMPRESSED	圧縮を行わない。圧縮や解凍のオーバーヘッドがなく、読み書きが高速。	圧縮のオーバーヘッドを避けたい場合。短期間でのデータ処理

その他

ワイドカラムストアの特徴

データモデル

列ファミリー: データは「列ファミリー」と呼ばれるグループにまとめられる。各列ファミリーには複数の列が含まれ、各列はキーと値のペアで構成される。
スキーマレス: スキーマが事前に定義されていないため、データの構造を柔軟に変更できる。各行（レコード）は異なる列を持つことができる。

行キーと列ファミリー

行キー: 各行には一意のキーが割り当てられる。このキーにより、特定の行を効率的に検索できる。
列ファミリー: 列ファミリーは論理的なグループであり、関連するデータをまとめる。各列ファミリーは、複数の列（キーと値のペア）を含むことができる。

ワイドカラムストアの利点

柔軟なデータモデル

スキーマレス: 事前にスキーマを定義する必要がないため、データモデルの変更が容易。
列の追加が容易: 新しい列を追加する際にも、既存のデータ構造を変更する必要がない。

スケーラビリティ

分散システム: ワイドカラムストアは、データを複数のノードに分散して保存し、水平スケーリングを容易にする。大規模なデータセットにも対応できる。

効率的なデータアクセス

行キーによる高速検索: 行キーを使って特定の行を効率的に検索できる。
列ファミリーによるグループ化: 関連するデータを列ファミリーにまとめることで、データのアクセスが効率的になる。

ワイドカラムストアの使用例

リアルタイム分析

使用例: ソーシャルメディアのアクティビティログやクリックストリームデータの分析。
理由: スキーマレスなデータモデルと効率的なデータアクセスが、リアルタイムのデータ分析に適している。

IoTデータ管理

使用例: IoTセンサーデータの収集と分析。
理由: スキーマレスなデータモデルにより、さまざまな種類のセンサーデータを柔軟に格納できる。

ユーザープロファイルストレージ

使用例: ユーザープロファイルやカスタマーデータの管理。
理由: ユーザーごとに異なる属性を持つデータを効率的に管理できる。

ワイドカラムストアの代表的なデータベース

Apache Cassandra

高可用性とスケーラビリティを持つ分散データベース。大規模なデータセットに適しており、特に書き込みが多いワークロードに強い。

リングトポロジ: ノードがリング状に接続され、データが均等に分散される。
可用性と耐障害性: ノード障害に対して高い耐障害性を持つ。

HBase

Hadoopエコシステムの一部であり、HDFS（Hadoop Distributed File System）上で動作する。大規模なデータセットのリアルタイム読み書きに適している。

リアルタイムアクセス: HDFS上での高速なランダムアクセスを提供。
Hadoopとの統合: MapReduceやHadoopの他のツールとのシームレスな統合。

japan.zdnet.com

Google Bigtable

GoogleのスケーラブルなNoSQLデータベースサービス。低レイテンシーで大規模なデータ処理が可能。

スケーラビリティ: ペタバイト規模のデータを処理可能。
パフォーマンス: 低レイテンシーで高いスループットを提供。

cloud.google.com

Amazon DynamoDB

Amazonの完全マネージドなNoSQLデータベースサービス。スケーラブルで高可用性を提供し、自動スケーリング機能を持つ。

自動スケーリング: トラフィックに応じて自動的にスケーリング。
管理の容易さ: フルマネージドであり、運用負担が少ない。

aws.amazon.com

ワイドカラムストアのデータモデル例

Row Key: user123
-----------------------------------------
| Column Family: personal               |
| ---------------|--------------------- |
| First Name     | Alice                |
| Last Name      | Smith                |
| Age            | 30                   |
-----------------------------------------
| Column Family: contact                |
| ---------------|--------------------- |
| Email          | alice@example.com    |
| Phone          | 123-456-7890         |
-----------------------------------------
| Column Family: preferences            |
| ---------------|--------------------- |
| Language       | English              |
| Subscription   | Premium              |
-----------------------------------------