ICDE2013study.ppt

Size: px

Start display at page:

Download "ICDE2013study.ppt"

せぴあすえがら
4 years ago
Views:

1 ICDE2013 勉強会 R10: Main Memory Query Processing 担当 : 山室健 1

2 概要 } このセクションの特徴 } in-memory を前提としたクエリ最適化 (Hash Join の高速化や MV による資源の利活用 ) に関する話題 } 紹介する論文リスト } 1. Efficient Many-Core Query Execution in Main Memory Column-Stores } 2. Recycling in Pipelined Query Evaluation } 3. Main-Memory Hash Joins on Multi-Core CPUs: Tuning to the Underling Hardware 2 R10: Main Memory Query Processing 担当 : 山室健

Disk-less Modern Database Management http://.

3 Disk-less Modern Database Management から引用 3 R10: Main Memory Query Processing 担当 : 山室健

4 1. Efficient Many-Core Query Execution in Main Memory Column-Stores Jonathan Dees (SAP) Peter Sanders (KIT - Karlsruher Institut fuer Technology) 4 R10: Main Memory Query Processing 担当 : 山室健

5 1. Efficient Many-Core Query Execution in Main Memory Column-Stores } A overview } 現状提案されている様々な Modern な DB 最適化手法を用いて OLAP 向けのクエリ (TPC-H) の高速化を SAP HANA 上で実現しましたという実装論文 } Contribution } Modern な DB 最適化手法が広く浅く議論されている } OLAP 向けに最適化された既存の ColumnDB(Vectorwise) と比較して倍の高速化 (at SF100 and SF300) 5 R10: Main Memory Query Processing 担当 : 山室健

6 1. Efficient Many-Core Query Execution in Main Memory Column-Stores } 扱っている DB 最適化手法 } Just-in-time SQL Compilation } Vector-at-a-time Query Execution } Column-oriented Storage } NUMA-based Thread Schedulers/Indices } Inverted Indices } Block Summaries like Zonemaps in Netezza } Loop Unrolling/SIMD Instructions }... 6 R10: Main Memory Query Processing 担当 : 山室健

7 1. Efficient Many-Core Query Execution in Main Memory Column-Stores } Experimental } 22 Queries in TPC-H } 4 Xeon X7560 } 8-cores at 2.27 GHz. } 256GiB Mem } Mem bandwidth 50GiB/s } Memory Space Used } データ圧縮率 51% } 索引による余剰領域 19% 論文内 TableⅡから引用 7 R10: Main Memory Query Processing 担当 : 山室健

8 1. Efficient Many-Core Query Execution in Main Memory Column-Stores 処理を並列化しない場合の性能比較 8 論文内 TableⅢ から引用

9 2. Recycling in Pipelined Query Evaluation Fabian Nagel (The University of Edinburgh) Peter Boncz (CWI) Stratis Viglas (The University of Edinburgh) 9 R10: Main Memory Query Processing 担当 : 山室健

10 2. Recycling in Pipelined Query Evaluation } A overview } クエリ実行中に発生した中間結果もしくは最終結果 (Materialized View) をクエリ間で自律的に再利用 (Recycle) することで全体の処理性能を改善 } Contribution } パイプライン実行モデル (Volcano-style) とクエリの中間 / 最終結果を再利用するスキームを統一的に扱う手法の提案 } Recycler Graph(DAG) と Recycler Cache による MV の管理 } 利得 (Benefit) 関数によるクエリの Rewirte 処理 } 実際に Vectorwise[2][20] 上に実装し評価 10 R10: Main Memory Query Processing 担当 : 山室健

2. Recycling in Pipelined Query Evaluation } MV の Recycling } 最適化後のクエリ木と Recycler Graph を比較して Rewriter で書き換え } Recycle Graph を考慮した Optimizer での最適化は行わない

11 2. Recycling in Pipelined Query Evaluation } MV の Recycling } 最適化後のクエリ木と Recycler Graph を比較して Rewriter で書き換え } Recycle Graph を考慮した Optimizer での最適化は行わない (optional) } Execution Engine 上で発生した MV を用いて Recycler を更新 } 各 MV の参照統計情報 } Recycler Graph の更新と Cache の入れ替え論文内 Fig.1 から引用 11 R10: Main Memory Query Processing 担当 : 山室健

12 2. Recycling in Pipelined Query Evaluation } MV の Matching と Insertion } クエリ木と Recycler Graph を Bottom-up 的に Matching } Graph の各ノードは Operator(Leaf は Relation) でノード参照は Has h を用いることで O(1) の探索 123 } Graph 上に存在しない候補が存在した場合にはクエリ実行中に新規エントリを Graph に追加 4 論文内 Fig.2 から引用 12 R10: Main Memory Query Processing 担当 : 山室健

13 2. Recycling in Pipelined Query Evaluation } TPC-H Experiments } 3 つの Recycle Strategy で評価 } HIST: 中間 / 最終結果を Cache に入れるかどうかの判断は過去のクエリ履歴のみから判断 (2 回以上使用しないと Recycle されない ) } SPEC: 初回出現時に投機的に Cache に追加 } PA: Top-k クエリや selection を投機的に Cache に追加 13 R10: Main Memory Query Processing 担当 : 山室健

に入れるかどうかの判断は過去のクエリ履歴のみから判断 (2 回以上使用しないと Recycle されない ) } SPEC:

14 2. Recycling in Pipelined Query Evaluation } TPC-H Experiments } 3 つの Recycle Strategy で評価 } HIST: 中間 / 最終結果を Cache に入れるかどうかの判断は過去のクエリ履歴のみから判断 (2 回以上使用しないと Recycle されない ) } SPEC: 初回出現時に投機的に Cache に追加 } PA: Top-k クエリや selection を投機的に Cache に追加 14 R10: Main Memory Query Processing 担当 : 山室健

15 3. Main-Memory Hash Joins on Multi-Core CPUs: Tuning to the Underling Hardware Cagri Balkesen (ETH Zurich) Jens Teubner (ETH Zurich) Gustavo Alonso (ETH Zurich) M. Tamer Özsu (University of Waterloo) 15 R10: Main Memory Query Processing 担当 : 山室健

16 3. Main-memory Hash Joins on Multi-Cores CPUs } A overview } cache-oblivious/conscious な HashJoins 手法の性能比較 } cache-oblivious * : HW 最適化のための knob が無い手法 } cache-conscious: ある特定の HW 環境に最適化された手法 } Contribution * } 既存手法を分析し HW 環境に適した最適化を提案 } 上記 2 つの手法 (oblivious/conscious) と HW 環境の依存関係を分析 / 再考し HW 最適化の基礎を構築 } HW 最適化の重要性を示唆 ( 考慮の有無で 3 6x の性能差 ) } SC: 16 R10: Main Memory Query Processing 担当 : 山室健

17 3. Main-memory Hash Joins on Multi-Cores CPUs } 取り扱う 2 種類の HashJoins * No-Partitioning Joins (Cache-oblivious way) 論文内 Fig.2 から引用 Radix Joins (Cache-conscious way) 論文内 Fig.4 から引用 17 R10: Main Memory Query Processing 担当 : 山室健 *1-pass Algorithm を前提

18 3. Main-memory Hash Joins on Multi-Cores CPUs } Radix Joins(Cache-conscious) } CPU キャッシュ効率を考慮して HashTable を複数分割 } 各 passで2 #radix bits に分割 } キャッシュの観点から極力小さいほうが良い } ただし小さすぎると TLB * によるペナルティが顕在化 [4] } HW を考慮した最適化が必要 *Translation Look-aside Buffer, 物理ページ addr. の virtual/physical 変換表 18 R10: Main Memory Query Processing 担当 : 山室健

19 3. Main-memory Hash Joins on Multi-Cores CPUs } Experimental } サイズの偏りを考慮した 2 パタンのデータ A/B を用意 } 異なる CPU を 4 パタン用意論文内 TableⅠ から引用論文内 TableⅡ から引用 19 R10: Main Memory Query Processing 担当 : 山室健

20 3. Main-memory Hash Joins on Multi-Cores CPUs } Experimental } データ A/B における CPU 時間評価 } No-Partitioning Joinの処理比率 (B/P) は入力サイズに依存 } Radix Joinの大半の時間はPartition 処理論文内 Fig.14 から引用 20 R10: Main Memory Query Processing 担当 : 山室健

Joinの大半の時間はParition 処理 SPARC は弱いメモリモデルを採用しているため同期コストが非常に低い (&

21 3. Main-memory Hash Joins on Multi-Cores CPUs } Experimental } データ A/B における CPU 時間評価 } No-Partitioning Joinの処理比率 (B/P) は入力サイズに依存 } Radix Joinの大半の時間はParition 処理 SPARC は弱いメモリモデルを採用しているため同期コストが非常に低い (& キャッシュ効率の良し悪しの差 ) 論文内 Fig.14 から引用 21 R10: Main Memory Query Processing 担当 : 山室健

22 3. Main-memory Hash Joins on Multi-Cores CPUs } Experimental } Radix Join の Partition 処理時間と Knob の関係は? } 多少の性能の上下はあるが knob の影響は小論文内 Fig.9 から引用 22 R10: Main Memory Query Processing 担当 : 山室健

23 3. Main-memory Hash Joins on Multi-Cores CPUs } Experimental } Radix Join の Partition 処理時間と Knob の関係は? } 多少の性能の上下はあるが knob の影響は小 HW 環境に依存する HashJoin に関しては cache-conscious な手法を用いることで多少の環境依存を犠牲に大幅な性能向上が期待できる論文内 Fig.9 から引用 23 R10: Main Memory Query Processing 担当 : 山室健

ICDE’15 勉強会 R24-4: R27-3 (R24:Query Processing 3, R27 Indexing)

ICDE’15 勉強会 R24-4: R27-3 (R24:Query Processing 3, R27 Indexing) 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) 小山田 (NEC) ICDE 15 勉強会 R24-4: The DBMS - your Big Data Sommelier