ICDE 2015 Study (R24-4, R27-3)
?
1 like?876 views
R24-4: The DBMS - your Big Data Sommelier R27-3: A Comparison of Adaptive Radix Trees and Hash Tables
![発想: メタデータをつかってデータのロードを減らす
?問合せ例
– place = “Japan” のデータを取得するモノ
– 本来 T_part2.csv のロードは必要ない
? place = “US” なので (メタデータ情報)
?従来の DBMS
– メタデータ/実データどちらも全てロード
してから処理する
– ? T_part2.csv のロードは無駄に
?提案方式
– 方針: メタデータだけ事前にロード
– ? T_part2.csv が問合せ対象に入らないこ
とを確認し、ロードを省くことができる
Ｚ
[date] 2015 05/17
[place] Japan
[date] 2014 08/20
[place] US
メタデータ
ロードが楽
実データ
ロードが大変
T_part1.csv
T_part2.csv
SELECT * FROM T
WHERE place = “Japan”
R24-4: The DBMS - your Big Data Sommelier](https://image.slidesharecdn.com/icde2015study-150516043531-lva1-app6892/85/ICDE-2015-Study-R24-4-R27-3-3-320.jpg)
![R27-3: A Comparison of Adaptive Radix Trees and
Hash Tables
Victor Alvarez, Stefan Richter, Xiao Chen, Jens Dittrich (Saarland University)
?(概要) ART [Leis, ICDE’13] の性能測定を “ちゃんと” やる
– Adaptive Radix-Tree (ART): インメモリDB向けのインデックス
– ART は “ハッシュテーブル並みの性能でレンジクエリもサポートす
る夢の索引” とうたわれているが、実際のところどうなの？
?(目的) [Leis, ICDE’13] で欠けていた３つの評価をやる
1. 類似するデータ構造である Judy Array との比較
2. ちゃんとチューニングしたハッシュテーブルとの比較
3. レンジクエリの性能測定
? (結果) ART は銀の弾丸ではない！
– ポイントクエリではハッシュテーブルに勝てず、レンジクエリでは
B+ Tree に勝てない（が、どちらも二番手となる性能）](https://image.slidesharecdn.com/icde2015study-150516043531-lva1-app6892/85/ICDE-2015-Study-R24-4-R27-3-6-320.jpg)
![Radix Tree と ART (Adaptive Radix Tree)
? Radix Tree (中間ノードを圧縮したトライ / パトリシア木)
– Good: 探索時に条件分岐が発生しない (単なる配列アクセス) ため、CPU
キャッシュミスが少ない (? 二分木)
– Bad: まだまだメモリ利用効率が悪く、キャッシュ効率も悪い
? データがスパースでも、最大の子供数分の容量を食う
? ART (Adaptive Radix Tree) [Leis, ICDE’13]
– 最適化された 256-way の Radix Tree
– ノードの圧縮: 実際の子供の数に応じて (Adaptive) ノードのデータ構造を
変えることで、ノードを圧縮する
– 探索効率化: 探索処理は SIMD を活用して高速に実行
各ノードは「子ノードへのポインタ」の配列
子ノードが少ない場合でも、最大子共数分の容量を消費
子ノードの数に応じて、ノードを異なるデータ構造で表現
子ノードが多い (Dense) ? Radix Tree と同様の表現
子ノードが少ない (Sparse) ? 圧縮表現
R27-3: A Comparison of Adaptive Radix Trees and Hash Tables](https://image.slidesharecdn.com/icde2015study-150516043531-lva1-app6892/85/ICDE-2015-Study-R24-4-R27-3-7-320.jpg)
ICDE 2015 Study (R24-4, R27-3)
- 1. R24-4: The DBMS - your Big Data Sommelier (R24: Query Processing 3) R27-3: A Comparison of Adaptive Radix Trees and Hash Tables (R27: Indexing) Masafumi Oyamada ICDE’15 勉強会
- 2. R24-4: The DBMS - your Big Data Sommelier Yagiz Kargin , Martin Kersten , Stefan Manegold , Holger Pirk (CWI) ?(目的) “インスタント分析” を実現したい – 課題: DBMS で巨大なデータを分析しようと思うと、データのロー ド?索引付けに時間がかかって、すぐに分析が開始できない ?(発想) メタデータを利用し、ロードするデータを絞り込む – 科学分野ではデータが複数の “ファイル” からなり、各ファイルが “メタデータ” を持つ（例: 取得時刻） – クエリの条件にはメタデータから得られる情報が指定されることが 多い（例: 「昨日取得したデータの平均値を計算して」） – ? まずはメタデータだけをロードしておいて、実際にロードする データ（ファイル）は条件にマッチするものだけにしよう！ ?(方式) メタデータを考慮した問合せ最適化 in MonetDB – “メタデータに対する処理” が最初におこなわれるような問合せプ ランの書き換えルールを MonetDB のオプティマイザに導入 MonetDB チーム
- 3. 発想: メタデータをつかってデータのロードを減らす ?問合せ例 – place = “Japan” のデータを取得するモノ – 本来 T_part2.csv のロードは必要ない ? place = “US” なので (メタデータ情報) ?従来の DBMS – メタデータ/実データどちらも全てロード してから処理する – ? T_part2.csv のロードは無駄に ?提案方式 – 方針: メタデータだけ事前にロード – ? T_part2.csv が問合せ対象に入らないこ とを確認し、ロードを省くことができる Ｚ [date] 2015 05/17 [place] Japan [date] 2014 08/20 [place] US メタデータ ロードが楽 実データ ロードが大変 T_part1.csv T_part2.csv SELECT * FROM T WHERE place = “Japan” R24-4: The DBMS - your Big Data Sommelier
- 4. アプローチ: オプティマイザの拡張 ? 実データ と メタデータ をプラン内で区別するようオプ ティマイザを拡張 ?プランの最適化時には、メタデータに対する処理をできる だけ最初にやるよう、プランを書き換え メタデータは既にロードされており、すぐに処理できる その処理結果をつかって、ロードする実データを pruning する R24-4: The DBMS - your Big Data Sommelier
- 5. 評価 ?データ: 地震波形の実データ (mSEED フォーマット) – sf27: 4384ファイル, 36GB (DB にロード後は伸張され 627 GB) ?問合せ: 集計値の計算 – T_4: 特定期間の波形の平均値の計算 R24-4: The DBMS - your Big Data Sommelier （データのロードも含めた） 問合せを完了するまでの時間 インデックスを作成して利用するもの （インデックス作成コストが大きく フルスキャンよりも遅い） データをフルスキャンするもの 提案方式 選択率が極めて高い場合を除き 従来方式よりもよい性能
- 6. R27-3: A Comparison of Adaptive Radix Trees and Hash Tables Victor Alvarez, Stefan Richter, Xiao Chen, Jens Dittrich (Saarland University) ?(概要) ART [Leis, ICDE’13] の性能測定を “ちゃんと” やる – Adaptive Radix-Tree (ART): インメモリDB向けのインデックス – ART は “ハッシュテーブル並みの性能でレンジクエリもサポートす る夢の索引” とうたわれているが、実際のところどうなの？ ?(目的) [Leis, ICDE’13] で欠けていた３つの評価をやる 1. 類似するデータ構造である Judy Array との比較 2. ちゃんとチューニングしたハッシュテーブルとの比較 3. レンジクエリの性能測定 ? (結果) ART は銀の弾丸ではない！ – ポイントクエリではハッシュテーブルに勝てず、レンジクエリでは B+ Tree に勝てない（が、どちらも二番手となる性能）
- 7. Radix Tree と ART (Adaptive Radix Tree) ? Radix Tree (中間ノードを圧縮したトライ / パトリシア木) – Good: 探索時に条件分岐が発生しない (単なる配列アクセス) ため、CPU キャッシュミスが少ない (? 二分木) – Bad: まだまだメモリ利用効率が悪く、キャッシュ効率も悪い ? データがスパースでも、最大の子供数分の容量を食う ? ART (Adaptive Radix Tree) [Leis, ICDE’13] – 最適化された 256-way の Radix Tree – ノードの圧縮: 実際の子供の数に応じて (Adaptive) ノードのデータ構造を 変えることで、ノードを圧縮する – 探索効率化: 探索処理は SIMD を活用して高速に実行 各ノードは「子ノードへのポインタ」の配列 子ノードが少ない場合でも、最大子共数分の容量を消費 子ノードの数に応じて、ノードを異なるデータ構造で表現 子ノードが多い (Dense) ? Radix Tree と同様の表現 子ノードが少ない (Sparse) ? 圧縮表現 R27-3: A Comparison of Adaptive Radix Trees and Hash Tables
- 8. ART: 子ノードの数に応じてノードのデータ構造を変更 If (子ノード数 ≤ 16) If (子ノード数 ≤ 48) If (子ノード数 > 48) (1) 子ノードを持つキーのキー値を N 個並べる (探索時は、線形探索) (2) 続いて、キーと同じ順で、子ノードへのポインタを N 個並べる (1)256個の配列を用意し、インデックスの示すキーが子ノードを持つなら、 子ノードへのポインタのポインタを格納 (探索時は、配列アクセス) (2) 子ノードの数だけ、子ノードへのポインタを並べる Radix Tree と同様に、子ノードへのポインタをそのまま並べる。イン デックスがキー値となる R27-3: A Comparison of Adaptive Radix Trees and Hash Tables
- 9. 評価 ? ポイントクエリ (1Billion のタプルに対する検索) – 比較対象 (抜粋) ? Judy Array ? Cuckoo hashing (モダンな Open addressing アルゴリズム) をつかった ハッシュテーブル実装 – 結果 ? Judy Array には勝つ (ART は Judy 比 2x の性能だが 2x 容量を食う) ? ハッシュテーブルには負ける (ハッシュテーブルは ART とくらべて数倍の 性能) ? レンジクエリ – 比較対象 ? Judy Array ? Cuckoo hashing をつかったハッシュテーブル実装 ? B+-Tree – 結果 ? Judy, ハッシュテーブルには勝つ (2x の性能) ? B+-Tree には負ける Radix Tree の改良版で ART に類似。細かな違いは論文参照 ※ ART には B+-Tree と比べると木の管理がはるかに楽、という利点も R27-3: A Comparison of Adaptive Radix Trees and Hash Tables
- 10. ポイントクエリ (Lookup throughput) R27-3: A Comparison of Adaptive Radix Trees and Hash Tables
- 11. レンジクエリ (Lookup throughput) R27-3: A Comparison of Adaptive Radix Trees and Hash Tables