ブログ@nnaka2992

データベースってなんだよ

行指向と列指向の違いについての論文を読む

CMU_Advanced_Database_Systems DB 論文

この記事の趣旨

前回と同様に CMU Advanced Databas Systems Spring2023のReading Assignmentとして出ている論文を 読み論文紹介のやり方 / How to review で紹介されている方法をまとめていきます。

今回はBigQueryやSnowflake、Amazon Redshiftといった分析向けデータベースが採用している行指向 ストア(Column-store)と列指向ストア(Row-store)の差と行指向ストアがのどうのような最適化が パフォーマンスに影響を与えているかについて扱った論文を読んで行きます。

Column-Stores vs. Row-Stores: How Different Are They Really?

研究全体の背景

行指向データベースシステムは分析用ワークロードで列指向データベースシステムより優れた パフォーマンスを発揮することで知られている。なぜなら行指向ストアはクエリ実行に必要な データのみをディスクまたはメモリから取得するため、優れたI/Oパフォーマンスを達成できる からである。

問題意識

垂直パーティショニングや全ての行をパーティショニングすることで、列指向データベースで行指向デー タベースのようなパフォーマンスを実現できるだろうか？ また行指向データベースが高速に動作するのは どのような最適化手法の影響が大きいのか？

論文の目的

列指向データベースで垂直パーティショニングやクエリ実行で使われる全ての行にインデックス を張るなどして、擬似的に行指向データベースを再現することで分析用途でのパフォーマンスが 向上するのか？ また行指向データベースの高速化に用いられるテクニックを一つずつ無効化し、 パフォーマンスを比較することでどのような要素が行指向データベースのパフォーマンスを 向上させているかを検証しする。

手法の説明

Star Schema Benchmarkを用いてC-Storeと商用列指向データベースの比較を行う。
列指向データベースでは垂直パーティショニング、全ての列にインデックスを作成、マテリ アライズドビューを使用し行指向データベースの性能に近づけるか検証を行う。
行指向データベースではデータ圧縮、遅延マテリアライゼーション、ブロックプロセッシング をそれぞれ無効化しどの要素の影響が最も大きいか。またこの論文で提案されたinvisible join の評価を行なう。

結果

  1. 列指向ストアに置けるマテリアライズトビュー
    行指向ストア(CS)と列指向ストア(RS)を比較するとCSがRSとRSのマテリアライズドビュー(MV)に 比べ非常に優れたパフォーマンスを発揮する。一方でCSの一つの行にMVとして期待するアウトプット のタプルをStringとして保存すると、普通のRSよりも低いパフォーマンスとなる。
    この結果をまとめるとCS > RS MV > RS > CS MVとなる。

  2. 列指向ストアに行指向ストアを再現する
    RSにCSを再現する方法として以下の4通りの方法とMVを比較する。

    1. 一般的な列指向のアプローチを適用し、効果的であればbitmap1 またはbloom filter2を適用する(T)
    2. 一般的な列指向のアプローチを適用するが、bitmapを積極的に使用する(T(B))
    3. 一つのテーブルを複数のテーブルとして垂直分割を行う(VP)
    4. 全ての行にインデックスを貼り、値の読み込みは全てインデックス経由で行う(AI)

    結果としては平均してMV > T > T(B) > VP > AIとなる。

  3. 列指向ストアに置ける最適化手法とその影響 列指向ストアの最適化手法においてどの影響が大きいかを測定するためそれぞれを無効化することで 検証を行なう。測定対象の最適化項目としては以下の4つを対象とする。

    1. ブロックプロセッシングの有効化(B)または無効化(b)
    2. Invisible joinの有効化(I)または無効化(i)
    3. 保存時のデータ圧縮の有効化(C)または無効化(c)
    4. 遅延マテリアライゼーションの有効化(L)または無効化(l)

    結果は平均するとBICL > bICL > BiCL > biCL > BicL > bicL > biclとなる。

まとめと考察

既に知られていたように行指向ストアは列指向ストアに対して常に優れたパフォーマンスを発揮した。
また列指向ストアで行指向ストアをエミュレートしても、パフォーマンスの改善は見られずむしろ 一般的なクエリ実行に比べ悪い性能を見せた。これは読み込むデータのオーバーヘッドが大きくなる ためである。また全ての行をインデッス化すると遅くなる理由としては今回対象となる列指向 データベースでインデックスアクセスを行う際のオーバーヘッドが大きいためである。
また列指向ストアの最適化手法の影響についても検証した。なかでも遅延マテリアライゼーションと データの圧縮はパフォーマンスの改善に大きく影響した。ブロックプロセッシングや Invisible Joinも上記の二つに比べると影響は小さいものの最適化として有効に働いた。

  1. 属性を表すデータのようにカーディナリティが低いデータのインデックスとして最適 Oracle Document 索引↩
  2. 空間効率が高く、O(n)で検索することが出来るデータ構造。ただしフィルタからのデータ削除は出来ず、誤検知することもある Bloom Filters↩