PLAIDEngineer Blog
エンジニア積極採用中
OLAPデータベースにおける高速化の技術

OLAPデータベースにおける高速化の技術

Yoshiyuki Komazaki
Yoshiyuki Komazaki

こんにちは、エンジニアのkomukomoです。フリーランスとしてプレイドでお仕事させていただいています。これは社内勉強会をブログ化したものです。この記事では、OLAPデータベースにおいて分析クエリを高速化するために使われている技術について説明します。
また、データベース使用者がどう使うかというよりはデータベース自体の内部の話にフォーカスしています。

Introduction

データベースに対するクエリというと様々なパターンが考えられますが、その処理の分類として、OLTPとOLAPという言葉が使われることがあります。[1]

OLTP（Online Transaction Processing）

  • 大量のデータの中から該当の箇所を特定して表示、更新、削除
  • 例：チケットの予約、口座の入出金

OLAP（Online Analytical Processing）

  • 大量のデータから集計、ソート
  • 例：分析、レポート

※ この記事ではOLTP/OLAPという言葉が頻出しますが、馴染みの無い方は3文字目だけをみてA→”アナリティクス”→”分析処理”と読みかえてみてください。

多くのアプリケーション開発者が慣れ親しんでいるであろうMySQL、PostgreSQLなどのいわゆるRDBMSは、特にOLTPを効率的に実行できる作りになっており、OLAPは得意というわけではありません。

もちろん大規模なデータでなければ十分やっていけると思いますし、数千万行規模の規模なら１台でもそれなりに高速に処理できると思われますが、昨今はデータ量も多く分析することが当たり前になってきており、大規模分析に特化した様々なOLAPデータベースが存在しています。

本記事ではOLTPデータベースと比較しながら、OLAPを高速化するにはどうするか、またはOLAP向けに作られたデータベースはどう実装しているのか、を解説していきます。

対象読者としては

  • RDBMSやSQLを扱ったことがある
  • OLAPデータベースの内部技術に興味はあるが詳しくはない、またはこれから学びたい

ような方を対象としています。

OLAPを高速化するには？

分析やレポートの表示など、OLAPで行われることをものすごく雑にまとめると、“データ読み込み” をしてそのデータに対してフィルタや集約などの “データ処理”をしていると考えられるので、まずはデータ読み込みの観点から解説します。

データ読み込みの基本

少し抽象的にコンピュータがデータを扱う際にどのようにデータを読み込むのか、という話ですが、基本的にはある程度の大きさの範囲をまとめて読むような挙動になっています。[2]
そのため、最終的に使いたいサイズが同じでも、その場所が飛び飛びになっていると不要なデータも読むことになり無駄が多くなります。

CleanShot2024-02-26at11.08.03@2x.png

これはディスクから読んでメモリにのせる際も、メモリからCPUのキャッシュにのせる際も同様です。
この挙動を考慮すると、データをどう並べて保持しておくか（データレイアウト）がデータ読み込みの際に重要ということになります。

データレイアウト

行指向レイアウト

まずはMySQLなどの一般的なOLTPデータベースの話です。
例えばデータベース上で４行３列のテーブルを扱う場合、永続化されたファイルの中身はものすごく簡略化するとこのようにデータを並べて保持しています。

Untitled(3).png

図の左側がデータベース上扱いたいテーブル、右側がファイル内のデータの並びを表しています。
これは行ごとにデータをまとめて配置しているため、

メリット

  • 特定の行に対する操作（追加、更新、読み込みなど）が効率的

デメリット

  • ある特定の列だけ読むのが非効率的
    • 例えばカラムcだけ欲しいと思ってもc0, c1, c2, c3の場所は離れてしまっています
  • 異なる特徴をもつ値（データ型と言ってもよい）が近くに並ぶため圧縮しづらい

という特徴があります。
メリットはまさにOLTPに向いている特徴であり、デメリットはOLAPで求められる特徴です。

列指向レイアウト

ではOLAP向けにするにはどうすればよいかというと、ある行全体にアクセスするよりはある特定のカラムに対しての大規模な読み込みをする処理が多いので、このように並べられています。

Untitled(4).png

同じ列のデータが近くにまとまっているため、

メリット

  • 複数行の必要な列を取り出すのが効率的
  • 同じ特徴をもつ値（データ型と言ってもよい）が近くに並ぶため圧縮しやすい

デメリット

  • 行単位での読み込み・削除などの処理が非効率的

という特徴があります。先ほどの行指向レイアウトとは逆に、メリットがまさにOLAPに向いた特徴であり、デメリットはOLTPに求められる特徴となっています。

ただし実際のところ、OLAPだとしてもある１つのカラムだけが必要ということはあまりなく、どこかのタイミングで同じ行の他のカラムと一緒に扱う必要があるといった理由などから、列指向の利点を得つつ行指向のように各行の値を近くにおいておけるよう、複数行をひとまとまりとしてグルーピングしつつ、そのグループの中で列指向のレイアウトをすることが多いようです。

Untitled(5).png

上の図では4行ごとにグルーピングした上で、そのグループ内で各列ごとにデータを並べています。

ちなみにこの行指向と列指向を組み合わせたデータレイアウトはPAX（Partition Attributes Across）と呼ばれており、これが提案された論文ではCPUがデータを読み込む際のCPUキャッシュのパフォーマンス改善にフォーカスして提案されています[3]。（本記事ではこのPAXも列指向レイアウトとして区別せず扱います。）

実際のファイルの例

以下はApache Parquetというファイルフォーマットの例です。

これ自体はデータベースではなく様々なシステムから使用可能な共通ファイルフォーマットですが、OLAPデータベースで扱うフォーマットと近いものであり、中のネストや繰り返し構造などはBigQueryの元となったDremelの論文を元に開発されたものです。

Apache Parquetのファイル構造。 https://parquet.apache.org/docs/file-format/ より
Apache Parquetのファイル構造。https://parquet.apache.org/docs/file-format/ より

図をみると、Row Group 0、Row Group 1…と複数行をグルーピングしたまとまりがあり、その中に Column a の値（values）、Column b の値、と列ごとにまとまって入っていることがわかります。
また、Footer内にはファイル内のカラムの場所（offset of…）やそのカラムに使われている圧縮アルゴリズム（encodings）などが入っていることが読み取れます。

圧縮

先程、“データ読み込み” からの “データ処理”という書きましたが、圧縮はこの両方に関わる技術といえます。

  • データ読み込み → 圧縮してデータが小さくなれば読み込みを効率化できる
  • データ処理 → 圧縮したまま処理ができれば、処理数を削減またはコストの低い計算を行うことができ高速化できる

データベースの内部で使用される圧縮には以下のような特徴があります。

  • 可逆圧縮
    • JPEGなどの非可逆圧縮ではなく、元のデータを復元できるようにしたいケースがほとんどです。
  • 圧縮したまま処理できるとよい
    • 圧縮アルゴリズムによっては、元のデータの状態に解凍せずに処理できる場合があります。
  • 元のデータに戻す処理が速い方がよい
    • 圧縮した状態で処理ができるわけではない場合はクエリ処理中に元データに戻して計算する必要があるため、この解凍速度は重要です。
    • アルゴリズムの選択がストレージコスト優先（圧縮率）かクエリパフォーマンス優先（解凍速度）かというトレードオフになることも多いです

行指向のデータレイアウトの場合、型も特徴も異なるデータが近くに並んでいるため、データの特徴を利用したアルゴリズムが使いづらく、圧縮するとしても結局様々なデータが入ったまとまりごとにLZ4などの汎用的なアルゴリズムを使うことになりがちです。
列指向のデータレイアウトの場合、そのデータに特化したアルゴリズムが使うことができ圧縮率も処理の効率化もしやすくなります。

OLAPデータベースで特によく使われる圧縮アルゴリズムとしては

  • Run-length Encoding
  • Dictionary Encoding
  • Bitmap Encoding
  • Delta Encoding
  • Bit Packing

などがありますが、ここではRun-length EncodingとDictionary Encodingにだけ簡単に触れておきます。

Run-length Encoding

Run-length Encoding（以下、RLE）とは、同じ値が連続するデータに対して、値とその個数でまとめて表現する圧縮方法です。

CleanShot2024-02-21at16.21.39@2x.png
Run-length Encodingの例。VLDB 2009 tutorial on Column Oriented Database Systemsより

図の例は左側がもとのデータ、右側がRLE適用後のデータです。例えば右のRLE適用後のQuarterの（Q2, 301, 350）というのはQ2という値が301番目から350個続いている、という意味になります。

以下のようなGROUP BYを使う集計など、圧縮したまま計算することで効率化できるケースがあります。

SELECT
  Quarter,
  COUNT(*)
FROM t
GROUP BY Quarter

# 擬似コード
# rles = [(Q1, 1, 300), (Q2, 301, 350), ...]
for rle in rles:
  key = rle[0]
  result[key] += rle[2]

値の重複があり、その値でソートされているときに圧縮効率が最も高くなりますが、そうでない場合は逆にサイズが増えてしまうこともあるので使用箇所は見極める必要があります。

一般的にデータベースではORDER BY句がない場合、結果の行順序を保証しないことが多いため、データベースが内部で保持している行の順序を並び替えた上でRLEを適用することはできます。

CleanShot2024-02-25at11.47.46@2x.png
データを並び替えてRLEを適用する例。 BigQueryのブログのデータ例より

ただし、どう並び替えれば最適かという問題はNP完全問題として知られているため、例えばBigQueryでは近似的なモデルを使って解いているそうです（2016年の情報）。

Dictionary Encoding

Dictionary Encodingは、何度も現れる長いデータをより短いデータで置き換える圧縮方法です。

CleanShot2024-02-21at17.34.15.png
Dictionary Encodingの例。左側が元のデータ、右側がDictionary Encoding適用後のデータ。

上の図の例では'Andrea'は0、'Andy'は1、…と割り当てた辞書を作り、その値を元の順番通り並べたものが圧縮後のデータになっています。

元のデータが文字列型で変換後が数値型となり、数値型のまま処理をすることができればパフォーマンス向上が期待できます（文字列の比較より数値型の比較のほうが通常は高速です）。可変長のデータを固定長にできるという意味でもメモリやキャッシュサイズを考慮した計算がしやすくなります。
元データの順序情報を保つように辞書を作成すれば、大小比較のクエリに対応することも可能です。

-- 与えられたクエリ
SELECT ... FROM t WHERE name LIKE 'And%'
↓
-- データベース内部で最適化されたクエリのイメージ。Dictionaryを見れば'And%'は0~1であると判断できる
SELECT ... FROM t WHERE name BETWEEN 0 AND 1

また、SELECT DISTINCT name FROM t のようなクエリの場合はDictionaryのvalueだけで処理が可能です。

RLEと同様、常に効果があるとは限らず、値の種類が多い場合などは逆にサイズが大きくなってしまうこともあります。

どの圧縮アルゴリズムを使うか

どの圧縮アルゴリズムを使えばよいかは、データの特徴だけでなくクエリによっても異なるため難しい問題です。対応方法はデータベースによりますが、

  • データベースが自動判定する
  • ユーザが指定する
  • 特定のアルゴリズムのみを使用する

といったようなパターンがあります。

例えばAmazon Redshiftではデフォルトでは自動で圧縮アルゴリズムが選択されますが、手動で選択することも可能です。（参考：圧縮エンコード）

データベース内では様々なデータ処理がありますが、圧縮した状態のまま処理を行えるようにする場合、各圧縮アルゴリズムごとに処理を書くとそれらの組合せが膨大になってしてしまうので統一的なAPIをもつことが多いようです。例えばDuckDBでは統一的なデータの持ち方があるようです。

処理の高速化

単にデータファイルを列指向レイアウトにして必要な部分を読むだけでもI/Oは改善可能ですが、OLAPではCPUでの大量のデータ処理が必要になるため、まだまだ高速化の余地があります。[4]

読み込んだ後の様々なデータ処理の高速化ということで主にCPUにフォーカスします。まずは

  1. CPUはどう処理をしているか
  2. OLTPデータベースではどういう処理をしているのか

という前提知識について説明した後、

  1. 高速化するには？

の解説をします。

CPUはどう処理しているか

※ここではCPUの基本的な挙動について説明しますが、あくまで基本的な例ですのでCPUによっては異なる可能性があります。

以下はCPUがそもそもどのようにプログラムを実行しているかを表した図です。

Untitled(7).png

プログラムをコンパイルするとCPUが解釈可能な命令の列（命令1、命令2）が生成されます。命令というのは例えば加算命令、分岐命令、メモリ読み書きの命令などがあります。

プログラムの実行時にはそれをメモリに載せ、決められた場所からCPUが順番に命令を読み込んで解釈し、実行していきます。

命令実行にデータ（AAA, BBB, …）が必要であれば更にメモリに対して読み書きをします。

キャッシュ

メモリの読み書きというのは他の処理に比べると遅いため、CPUはそれぞれ命令やデータをおいておくためのキャッシュやそれら両方に対応したキャッシュなどをもっています。

Untitled(8).png

近い場所にある命令やデータを一度に持ってくることでキャッシュを活用し、メモリアクセスの頻度を下げることで高速化をしています。

例：

  • 命令1の読み込み時に命令2も同時に取得しキャッシュにのせる → 命令2の処理時はキャッシュから読み込み可能なためメモリアクセスが不要になる
  • データAAAの読み込み時にBBB、CCCも取得しキャッシュにのせる → BBBの処理時にキャッシュから読み込み可能なためメモリアクセスが不要になる

パイプライン処理

命令の処理は、命令の読み込み、解釈、実行など様々なステップから構成されますが、これらの処理は並列に実行することが可能です。これをパイプライン処理といいます。

以下の図は、例としてCPUの処理がFetch、Decode、Execute、Memory、Writeというステップで構成されていて、命令A、B、C、Dを実行しているCPUの実行の様子を示しています。横軸は時刻を表し、例えば時刻3の時点で、命令CのFetch、命令BのDecode、命令AのExecuteのステップを同時に処理しています。

Untitled(9).png

基本的には命令はプログラムの順番通りに実行していきますが、分岐命令など（IF文など）がある場合は”次”ではない別の場所にある命令を実行することになり、この場合処理し始めていたものが無駄になることがあります。

以下の図は、Aが分岐命令のケースを示しています。本来AをExecuteして分岐結果がわかるまでは正確に次に必要な命令はわかりませんが、CPUはとりあえずB、Cの処理を始めます。しかし実はDが必要だったことがわかり、途中まで処理したB、Cを破棄し、無駄な時間ができています。

Untitled(10).png

CPUはこのような無駄を回避するために分岐先を予測しようとしますが、もちろん完璧ではありませんし、データベースの処理はクエリとデータによって分岐が変わるため予測は非常に困難です。例えばtrue/falseがランダムで入ったカラムaに対してa == true のようなフィルタをするクエリの場合、その部分では約50%の分岐予測ミスが起きるでしょう。

SIMD命令

また、CPUによってはSIMD命令という１つの命令で複数のデータの処理を行うことで高速化できるものがあります。

Untitled(11).png

ある処理の結果を次の結果に使うなど、処理の各命令同士に依存関係がある場合はSIMD命令を使うのは難しくなりますが、データベースの処理においては各行で独立して計算できることが多いため、多くのOLAPデータベースではこの命令を使えるよう実装されています。

高速化に関するCPUの動作まとめ

これらのCPUの動作を考慮すると高速に処理したいなら、

  • できるだけ近くのデータを処理する（データキャッシュを活かす）
  • できるだけ同じことを繰り返す（命令キャッシュを活かす）
  • 分岐を少なくする（パイプラインの無駄をなくす）
  • まとめて処理できるものはする（SIMD命令を使う）

といったテクニックが重要ということがわかります。

OLTPデータベースではどういう処理をしているか

続いて、よくあるOLTPデータベースがどうSQLを処理しているかの基本的なプログラミングモデルの話をします。もちろん簡略化していますし全てがこれというわけでないですが、おおよそ以下のような流れで処理されています。

Untitled(12).png

まず、SQL（図の左）が与えられるとそれをパースし様々なチェックを行ったあと実行計画（図の右）を作成します。実行計画は各処理を行うオペレータ（図の右のLimit、Projection、…のこと）の入出力がつながったツリー構造になります。図の例では一直線ですが、例えばJOINなどは場合インプットが２つあるオペレータです。

その後、実行計画ツリーのルート（図ではLimit）から実行していきます。

Untitled(13).png

LimitオペレータがProjectionオペレータに１行要求し、それを受けてProjectionがFilterに１行要求し、…という形で連鎖していき、この例ではLIMIT 5 なので最大５行アウトプットできるまで繰り返して終了します。下向きの矢印が制御の流れ、上向きの矢印がデータの流れとなっています。

もう少しプログラム的にまとめると以下のようになります。

Untitled(14).png

  • SQLから実行計画を作成する
  • 実行計画はオペレータで構成され、各オペレータの入出力で繋がったツリーとなっている
  • 実行計画の各オペレータは１行を返すイテレータとして機能する
  • rootから再帰的にイテレータを実行（next()の呼び出し）することで最終的な結果を返す

ちなみにこのようなデータベース処理のモデルは、このスタイルのクエリエンジンを提案した論文からvolcano model、volcano iterator modelなどと呼ぶことがあります。

高速化するには？

上述のようなモデルの場合、処理する行数が少ないOLTPであればとくに問題はなく実装も容易です。

ただ、データレイアウトの章でOLAP向けの効率的なデータの持ち方の解説をしましたが、処理するフェーズでそれを活かせないのではあまり意味がありません。また、圧縮した状態での処理やSIMD命令を使うのも難しいです。

簡単な解決策としては１行１行処理するのではなく複数行の列指向なデータにしてまとめて処理するという方法が考えられます。

Untitled(15).png

こうすることで、

  • 隣接したデータに繰り返し同じ処理をすることができCPUキャッシュを有効活用できる
  • 複数行を一度に処理するテクニックが活用できる
    • 列ごとの圧縮したままでの処理が使える
    • SIMD命令が使用しやすくなる
    • その他にも
      • NULLの値はビット列として持ち、値とは別にまとめて処理する
      • 間接的ではあるが処理が減れば分岐命令削減が期待できる
      • ...

など様々な効率化ができるようになります[5]。

ここでの説明はかなり簡略化していますが、例えばInfluxDB 3.0の内部のクエリ処理エンジンであるDataFusionはこのようなモデルになっています。DuckDBは本記事執筆時点は少し異なるモデルに変わっていますが、初期実装は同様のモデルだったようです。

OLAPでよく使われるインデックス

データベースの高速化といえばインデックスも大きく関わってくるため、OLAPでよく使用されるインデックスについて触れておきます。

OLTPとOLAPでは処理の性質の違いから、主に以下のような違いがあります。

  • OLTP：ある少数の行を特定するときに全スキャンを避けるためインデックスを使う。データを見つけるためのインデックス。e.g. B-tree index
  • OLAP：大量のデータを処理することが想定されているので、どちらかというと行を特定するというよりはスキャンを速くしたり、まとめて処理したりするためのインデックス[6]。

よく使用されるインデックスの例を紹介します。

Skipping Index

Skipping Indexは、スキャンの際に不要なデータをまとめて読み飛ばして高速化するためのものです[7]。

例えば複数行のまとまりに対し、事前に最大値・最小値を計算しておきます。処理の際にはクエリからそのまとまりを処理すべきかどうかを判断し、不要と判断した部分は処理をまるごと省略しスキャンを高速化します。

CleanShot2024-02-22at14.35.00@2x.png

上図の例では、Skipping Indexとして4行ごとにカラムa の最大（max）・最小（min）を保持しています。WHERE a > 10 というクエリの場合は、Skipping Indexのmaxの値をみて10より大きいときだけ元のデータにアクセスし、そうでない場合は元データの読み込みをスキップします。

Skipping Indexは、

  • 元のデータに対して非常に小さなサイズ
  • 計算コストが高くない
  • メンテナンスが楽

という特徴があるためOLAPデータベースで広く使用されています。

全体のデータの並び順とその値に関連があるなど、グループごとの傾向に差異がでるときに効果を発揮しやすくなります。

実際の使用例です：

  • ClickHouse
    • Skipping Indexに使うデータとしてmin-max、set、Bloom filterなどの種類がありユーザが設定できます。[8]
      • ちなみにBloom filterというのはデータの集合に対して、あるデータが”存在しない”、または”存在するかもしれない” という結果を返すことができるデータ構造の一つですが、Skipping Indexの目的としてはぴったりのデータ構造です。
  • Snowflake
    • クエリの最適化時にファイルのメタデータを読むことで不要な読み込みを減らすことに加え、Hash Join時などにも動的にデータを作成し読み飛ばすために使用しているそうです[9]。
  • Apache Parquet
    • 各行グループごとのメタデータとしてカラムの最大値・最小値などを入れる場所があります。
    • Apache Parquet自体はファイルフォーマット（+操作用ライブラリ）なので、これを使う側が対応していればSkipping Indexのように使用可能です。
  • PostgreSQL
    • OLTP向けのデータベースでももちろん使用可能です。
    • PostgreSQLではBlock Range Index（BRIN）と呼ばれています。

Bitmap Index

Bitmap Indexは何度も現れる値を同じビット列として保持しておき、処理の際に使用します。

Untitled(16).png
Bitmap Indexの例。左側が元データ、右側がBitmap Index

図の例では、viewという値は0、2、3、5、6番目に存在するため、Bitmap Index上のviewに対応するbitsの0、2、3、5、6番目が1で残りが0になっています。（図のbitsは左から0番目、1番目、…としています）

たとえばWHERE event_name IN ('view', 'buy') というクエリを処理する場合はそれらに対応する10110110と00001001 というビット列をOR演算で処理すれば、必要な行を素早く抽出できます。その他、ANDやカウントなどにも使用可能です。

テーブルの全ての行を一つのビット列にすると非常に長くなってしまうので、Skipping Indexのときと同様、これを複数行のまとまりごとに作成します。

ちなみに情報を失っておらずサイズも減らせるため、これ自体可逆圧縮ともいえます。

値の種類が多いと無駄な0のbitが増えてサイズが増えてしまいますが、Bitmap用の圧縮アルゴリズム（Roaring Bitmaps等）を使うなどの工夫をすることが多いようです。

実際に使用されている例です。

  • Druid
    • Dimensionというものに指定されたカラム全てにBitmap Indexが作成されます。BitmapはRoaring Bitmapにより圧縮されています。
  • Pinot
    • ユーザが指定したカラムに作成することができます。

データベースの例

実際のどのようなデータベースがあるか、今回触れたトピックの観点で紹介します。

  • PostgreSQL、MySQL、Spanner、SQLite、…
    • 行指向のOLTPデータベースといえるかと思います。（pg_analyticsなどの拡張は除きます）
  • ClickHouse、Druid、Pinot、DuckDB、…
    • ファイルフォーマットはそれぞれ異なりますが、列指向のOLAPデータベースといえると思います。
    • ただしリアルタイムな処理をする部分（ログデータのようにデータが来つづけ、データの挿入後にすぐ利用するようなもの）は部分的に新しいデータだけ行指向のような持ち方になっている場合もあります。
  • TiDB、AlloyDB
    • 行指向・列指向の両方の形式でデータをもつことでOLTP・OLAPに対応した、HTAP（Hybrid transaction/analytical processing）といわれる類のデータベースです。
    • 行指向側にデータを書き込み、列指向側にコピーされます。どのカラムを列指向側でも持つようにするかは使用者が選ぶことができます。
    • ちなみにTiDBの列指向な処理部分（TiFlashと呼ばれています）はClickHouseを元に作られているようです。
  • BigQuery
  • Snowflake
    • 列指向レイアウトでファイルが保存されており、クエリエンジンも本記事で述べたような技術で効率化がされています。[9:1]
    • UnistoreによりOLTPも対応できるようになっているそうです。
  • Rockset
    • RocksDBというOrdered Key-Valueストア（範囲スキャンに対応したkey-value store）に行スキャン用・列スキャン用・転置インデックス用などの形式で保持しておき、クエリに応じて適切なものを使います。RocksetではこれをConverged Indexと呼んでいます。

他にも様々なデータベースが存在しますが、興味のある方は例えば分析系のクエリのベンチマークをまとめたClickBenchというサイトがあるのでそういったサイトで比較しつつ探してみても面白いかもしれません。

まとめ

本記事では、以下のような内容を解説しました。

  • クエリの分類
    • OLTP：チケットの予約、口座の入出金など、特定の行に対しての処理
    • OLAP：分析やレポートなど、特定の列に対する大量データの処理
  • データのレイアウト
    • 行指向レイアウトはOLTPが得意
    • 列指向レイアウトはOLAPが得意
  • 圧縮
    • サイズを削減することによる効率化
    • 圧縮したまま処理することによる効率化
    • アルゴリズムは様々
  • データ処理の高速化
    • まとめて処理することによる効率化
    • CPUキャッシュを活かして効率化
  • インデックス
    • OLAPではスキャンを速くしたり、まとめて処理したりするためのインデックスが使用されることが多い
    • Skipping Index、Bitmap Index
  • データベースの例
    • 処理によって向き不向きがある
    • OLTP、OLAPを両方カバーしようとしているデータベースもある

OLAP高速化の技術の基本的な部分について浅く広く触れたつもりですが、深くは触れていませんしまだまだデータベースという観点でみればデータ書き込み、スケジューリング、並列化、最適化戦略、などなど様々なトピックがあります。より深く知りたい方は参考資料にのせたリンクなどを参照してみてください。

プレイドでは、行動解析というプロダクトの性質上本当に大量のデータがあるため、実際にこれらの知識を使ったりデータベースに手を入れたりすることもあります。もしプレイドに興味のある方はぜひ採用ページをご覧ください！

参考資料

  1. OLTP/OLAPという言葉がシステム全体を指すこともありますが、この記事では”OLTP/OLAP”はその処理自体を指すこととします。また、”OLTP/OLAPデータベース”という場合、どちらかといえばその処理が得意と思われるデータベースを意味するものとします。 ↩︎

  2. https://ja.wikipedia.org/wiki/参照の局所性 ↩︎

  3. PAXを提案した論文ではpage内のレイアウトを列指向にすることでCPU cacheを活用できるようにして高速化するとかかれています。page全体をメモリに載せると不要なカラムもメモリにのることになりますが、そもそもOLAPではディスクI/OではなくCPUとメモリバウンドであり、CPUのキャッシュミスが主要なボトルネックになるとのことです。 ↩︎

  4. Column-stores vs. row-stores: how different are they really? ではOLTPデータベースの読み込み部分を列指向のようにしてOLAPデータベースと比較し、OLAPデータベースのデータ処理部分の最適化の効果について述べられています。 ↩︎

  5. このvolcano modelを複数行で処理する先駆け的なMonetDB/X100の論文では、コンパイラによるSoftware pipeliningが重要であり行単位の処理だとそれができないという旨がかかれていますが、さらにCPUとコンパイラの説明が必要になることと、現代のout-of-orderのCPUとコンパイラにおいても同様に重要といえるかどうかの判断が私の知識ではできなかったため記事からは省略しています。 ↩︎

  6. この場合 “インデックス”（索引）という用語でいいのかどうか若干違和感があるのですが、データベースのドキュメントや学術論文でも普通に使用されているので、本記事では気にせず処理を高速化するための補助的なデータ構造という意味でインデックスという言葉を使っています。 ↩︎

  7. 読み飛ばすことをdata pruningと呼んだり、そのデータのことをSmall Materialized Aggregates（SMAs）、Zone mapsと呼んだりすることもあります。 ↩︎

  8. Understanding ClickHouse Data Skipping Indexes ↩︎

  9. The Snowflake Elastic Data Warehouse ↩︎ ↩︎

記事をシェア