# ネスト型カラムナストレージ ## 定義 ネスト型カラムナストレージとは、Protocol Buffers等のネスト(入れ子)構造を持つレコードを、フラットなリレーショナルデータと同様にカラム(列)単位で格納しつつ、レコードの構造情報を損失なく保持・復元できるようにする列指向ストレージ形式である。各フィールドの値に加え、「反復フィールドがどの階層で繰り返したか」を示す**repetition level(繰り返しレベル)**と、「オプショナル・反復フィールドのうちどこまでが実際に定義されているか」を示す**definition level(定義レベル)**という2つの整数を付与することで、値だけからは失われる木構造の情報を符号化する。この形式は[[@2010__VLDB__Dremel - Interactive Analysis of Web-Scale Datasets]](VLDB 2010)がGoogleのDremelシステム向けに提案したものであり、著者らはリレーショナルデータへの列指向ストレージ適用は既存研究があったが、ネストデータモデルへの拡張は本論文が最初であると主張する(Source: [[@2010__VLDB__Dremel - Interactive Analysis of Web-Scale Datasets]] §9 Related Work)。 ## 横断的知見 - (単一ソースからの ingest のため、他ソースとの横断的知見はまだない。次回以降、列指向ストレージ・ネストデータモデルを扱う別ソースが入った際に本節を育てる。) ## 未解決の問い - repetition level・definition levelの符号化方式は、Apache ParquetのDremel由来のネストカラム表現(shredding)とどこまで一致し、どこで異なるか。 - Dremel論文はジョイン・インデックス・更新を将来課題として明示的にスコープ外としているが(§6, §10)、これらをこの符号化方式に追加した後継システム(F1・Napa等)ではrepetition/definition levelの扱いはどう拡張されたか。 - 定義レベル・繰り返しレベルをビット列としてパックする際の圧縮効果は、フィールドのスパース性(数千フィールド中数百のみ使用というGoogleの実データ特性、Source: §4.2)にどの程度依存するか。他のワークロード(フィールド充填率が高いデータ)でも同様の利得が出るか。 ## 関連 - ソース: [[@2010__VLDB__Dremel - Interactive Analysis of Web-Scale Datasets]] - 概念: [[列指向OLAPデータベース]] / [[並列データベース]] - エンティティ: [[Protocol Buffers]] / [[Google]] / [[Sergey Melnik]] ## 出典 - [[@2010__VLDB__Dremel - Interactive Analysis of Web-Scale Datasets]](§4 Nested Columnar Storage、Figure 1-3、Appendix A-C)