Dremel: Interactive Analysis of Web-Scale Datasets

September 4, 2021

Dremelは2006年からGoogle社内で利用されているDWHで、社外にはBigQueryとして提供されている。 列指向の形式でデータを保存し、SQLに似た言語のクエリでデータを検索できる。 Dremelは、サーバーのクラスタを木構造に組織し、ルートで受理したクエリの処理を下層のサーバに分配し、その結果を集約することで処理を分散し高速化をはかる。

Dremelのデータモデルは、Protocol Bufferに由来し、繰り返されるフィールド、オプショナルなフィールド、ネストがある。 これにより、リレーショナルモデルでない大量のデータを保存し、アドホックに分析できる。 以下の図は、スキーマとデータの例である。 fig2 列指向データベースとして、全レコードの特定のフィールドを高速に処理するには、下図のように、フィールドごとにデータを局所化して保存する必要がある。 同時に、フィールドの繰り返しやオプショナルなフィールドを復元できなければならない。 fig2

以上の要件のために、フィールドの値を、パス上で繰り返された途中のフィールドを意味するrepetition levelやパス上に存在した繰り返し可能かオプショナルなフィールドの数を意味するdefinition levelと一緒に保存する。 下図は上で例示したデータに対応し、rとdはそれぞれrepetition levelとdefinition levelをあらわす。

例えば、パスName.Language.Codeであれば、NameLanguageは繰り返しされる可能があるため、Codeのrepetition levelは0以上2以下の値をとる。 r1をトップダウンに探索した場合、‘en-us’にいたるまで繰り返しがないため、repetition levelは0になる。 0はパス上に繰り返されたフィールドがないことを意味する。 ‘en’の場合、パス上でLanguageが繰り返されたので、repetition levelはLanguageの階層である2になる。 ‘en-gb’は、1層目のNameが繰り返されるので1があてはまる。 fig3

次に、defintion levelの例をあげる。 r1にはLinks.Backwardがなく、Backwardまでのパス上にオプショナルフィールドのLinksが1つあるので、definition levelは1で、値はNULLである。 r2Name.Language.Countryはなく、Countryのパス上にNameが1つあるので、definition levelは1になる。

木構造で構成されたクラスタのルートで受理したクエリがleaf nodeに到達すると、leaf nodeはGFSなどからなるストレージ層やローカルストレージにデータを問い合わせる。 以下はクラスタの図である。 fig7 ルートサーバは、探索すべきtablet(テーブルの水平パーティション)を特定し、下層のノードに検索処理を分散できるようにクエリを書きかえる。 たとえば、以下のクエリがあたえられると、 $$ \texttt{SELECT A, COUNT(B) FROM T GROUP BY A} $$ ルートサーバーはこれを $$ \texttt{SELECT A}, \texttt{SUM(c) FROM} (R^1_1\ \texttt{UNION ALL}\dots R^1_1) \texttt{GROUP BY A} $$ に書きかえる。 \(R^1_1, \dots , R^1_n\)は1層の\(1,\dots , n\)ノードの以下のクエリの結果をあらわす。各層でこの書きかえをleafに到達するまでくりかえす。 $$ R^1_i = \texttt{SELECT A, COUNT(B) AS c FROM}\ T^1_i\ \texttt{GROUP BY A} $$

論文をこちらからダウンロードできます。 画像は論文から引用したものです。