Dremel: Interactive Analysis of Web-Scale Datasets
September 4, 2021Dremelは2006年からGoogle社内で利用されているDWHで、社外にはBigQueryとして提供されている。 列指向の形式でデータを保存し、SQLに似た言語のクエリでデータを検索できる。 Dremelは、サーバーのクラスタを木構造に組織し、ルートで受理したクエリの処理を下層のサーバに分配し、その結果を集約することで処理を分散し高速化をはかる。
Dremelのデータモデルは、Protocol Bufferに由来し、複数の同名のフィールド、オプショナルなフィールド、ネストがあり、リレーショナルモデルでない大量のデータを保存し、アドホックに分析できる。
スキーマとデータの例を以下にのせる。
列指向データベースとして、全レコードの特定のフィールドを高速に処理するには、下図のように、フィールドごとにデータを局所化して保存する必要がある。
また、当然ながら、フィールドの繰り返しやオプショナルなフィールドを復元できなければならない。
以上の要件のために、フィールドの値を、パス上で繰り返された途中のフィールドをあらわすrepetition levelやパス上に存在した繰り返し可能かオプショナルなフィールドの数を意味するdefinition levelと一緒に保存する。 下図は上で例示したデータに対応し、rとdはそれぞれrepetition levelとdefinition levelをあらわす。
例えば、パスName.Language.Codeであれば、NameとLanguageは繰り返しされる可能があるため、Codeのrepetition levelは0以上2以下の値をとる。
r1をトップダウンに探索した場合、’en-us’にいたるまで繰り返しがないため、repetition levelは0になる。
0はパス上に繰り返されたフィールドがないことを意味する。
’en’の場合、パス上でLanguageが繰り返されたので、repetition levelはLanguageの階層である2になる。
’en-gb’は、1層目のNameが繰り返されるので1があてはまる。
次に、defintion levelの例をあげる。
r1にはLinks.Backwardがなく、Backwardまでのパス上にオプショナルフィールドのLinksが1つあるので、definition levelは1で、値はNULLである。
r2にName.Language.Countryはなく、Countryのパス上にNameが1つあるので、definition levelは1になる。
木構造で構成されたクラスタのルートで受理したクエリがleaf nodeに到達すると、leaf nodeはGFSなどからなるストレージ層やローカルストレージにデータを問い合わせる。
以下はクラスタの図である。
ルートサーバは、探索すべき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}
$$
論文をこちらからダウンロードできます。 画像は論文から引用したものです。