DEIM Forum 2016 D4-5
データ仮想化における効率的なクエリ処理の実装と評価
米田 信之
†米川 慧
†齋藤 和広
†渡辺 泰之
†村松 茂樹
†小林 亜令
††株式会社 KDDI 研究所 〒102-8460 東京都千代田区飯田橋 3-10-10 ガーデンエアタワー
E-mail: †{no-maita, ke-yonekawa, ku-saitou, yasuyuki, mura, kobayasi}@kddilabs.jp
あらまし 近年，企業におけるデータ分析の普及に伴い，更なる競争力向上のためのデータ統合が注目されてい る．データ統合技術の 1 つにデータ仮想化がある．これは複数のデータソースを仮想統合し，単一データソースで あるかのようなアクセス性を提供する技術である．データ仮想化におけるクエリ処理は，データソースから中間デ ータを抽出し，データ仮想化システム上で結合処理を実現する．しかしクエリによっては，中間データの肥大化す る処理や，抽出データ量を削減できない処理が発生し，クエリ処理の著しい遅延や異常終了を引き起こす問題があ る．そこで筆者らは，クエリ分解と中間結果再配置により，中間データを削減するクエリ処理手法を考案し，オー プンソースソフトウェアの Presto に実装した．また，TPC-H ベンチマーク を用いた実験により，本手法の有効性 を評価する． キーワード データ仮想化，データベース，問合せ処理，Presto
1. は じ め に
近 年 ， 企 業 に お け る ビ ッ グ デ ー タ 分 析 の 普 及 に 伴 い ， 更 な る 競 争 力 向 上 の た め の デ ー タ 統 合 が 注 目 さ れ て い る ． デ ー タ 分 析 に お い て は ， 1 つ の シ ス テ ム に 閉 じ た 単 一 デ ー タ ベ ー ス の み な ら ず ， 企 業 内 の 様 々 な デ ー タ を 組 み 合 わ せ た 分 析 を す る こ と で 新 た な 価 値 や 知 見 を 生 む こ と が 多 い ． そ の 一 方 ， デ ー タ 分 析 を 取 り 巻 く シ ス テ ム 環 境 は ， 組 織 に お け る 部 門 や 事 業 ご と に サ イ ロ 化 さ れ て い る こ と が 多 く ， デ ー タ 分 析 に 取 り 掛 か る ま で の プ ロ セ ス に 多 く の 時 間 と コ ス ト が 費 や さ れ て い る ． し た が っ て ， 組 織 内 の デ ー タ 統 合 を 実 現 す る こ と は ， デ ー タ 分 析 サ イ ク ル の 迅 速 化 な ら び に コ ス ト 削 減 を 可 能 と し ， 延 い て は 企 業 の 競 争 力 向 上 に 繋 が る も の と 考 え る ． し か し な が ら ， 組 織 内 の デ ー タ ベ ー ス を 1 つ に 統 合 す る こ と は 容 易 で は な い ． こ れ は ， デ ー タ ベ ー ス の 収 容 変 更 に 伴 う 既 存 ア プ リ ケ ー シ ョ ン の 改 修 や ， デ ー タ 移 行 ， 関 連 業 務 シ ス テ ム へ の 影 響 が 発 生 す る た め で あ る ． 実 現 す る た め に は ， 膨 大 な 時 間 と コ ス ト が 掛 か る こ と が 想 像 で き る ． そ こ で 筆 者 ら は ，デ ー タ 仮 想 化 [1]（ 図 1）に よ る デ ー タ 統 合 の 実 現 に 着 目 し て い る ． こ れ は ， 複 数 の デ ー タ ソ ー ス（ DS）を 仮 想 統 合 し ，あ た か も 単 一 の デ ー タ ソ ー ス で あ る か の よ う な ア ク セ ス 性 を 提 供 可 能 と す る ， デ ー タ 統 合 技 術 で あ る ． デ ー タ 仮 想 化 に よ る デ ー タ 統 合 が 実 現 す る と ， デ ー タ ベ ー ス 利 用 者 は ， デ ー タ 仮 想 化 シ ス テ ム（ DVS）に 対 し て SQL 等 の ク エ リ を 投 稿 す る こ と で 透 過 的 に デ ー タ ア ク セ ス が 可 能 と な る ． こ の 際 ， デ ー タ ベ ー ス シ ス テ ム （ DBS） の レ イ ア ウ ト や ， 固 有 の イ ン タ フ ェ ー ス ， 事 前 の デ ー タ 移 行 を 意 識 す る 必 要 は な い ． そ し て ， 新 た な DS が 構 築 さ れ る 場 合 に は ，ネ ッ ト ワ ー ク を 介 し た DVS と の 接 続 に よ り ，デ ー タ 統 合 環 境 に 加 え る こ と が で き る ． し か し な が ら ， デ ー タ 仮 想 化 に お け る ク エ リ 処 理 で は ， 中 間 デ ー タ が 肥 大 化 す る 処 理 や ， 抽 出 デ ー タ 量 を 削 減 で き な い 処 理 が 発 生 し ， 著 し い 処 理 遅 延 を 招 く こ と が あ る ． こ れ ら は ， DVS の 生 成 す る DBS 向 け の サ ブ ク エ リ が 非 効 率 で あ る た め 発 生 す る ． こ の 問 題 は ， 昨 今 構 築 さ れ て い る よ う な ビ ッ グ デ ー タ を 有 す る DBS が 対 象 と な る 場 合 ， 影 響 が 顕 在 化 す る ． そ こ で 本 研 究 で は ， デ ー タ 仮 想 化 に お け る ク エ リ 処 理 に つ い て ， ク エ リ 分 解 お よ び 中 間 デ ー タ 再 配 置 を 用 い る 効 率 化 手 法 を 提 案 す る ． ま た ， 提 案 手 法 を オ ー プ ン ソ ー ス ソ フ ト ウ ェ ア の Presto[2]に 実 装 し ，TPC-H[3] ベ ン チ マ ー ク を 用 い て 提 案 手 法 の 有 効 性 を 評 価 す る ． 本 論 文 の 構 成 は 以 下 の 通 り で あ る ．2 節 で DVS に お け る ク エ リ 処 理 概 要 と 課 題 に つ い て 述 べ ， 3 節 で 課 題 解 決 す る た め の ク エ リ 処 理 手 法 を 提 案 す る ．4 節 で は ， 提 案 手 法 を 適 用 し た プ ロ ト タ イ プ の 実 装 に つ い て 述 べ ， 5 節 で 評 価 実 験 ，6 節 で 本 研 究 を 通 じ て の 考 察 ，最 後 に 7 節 で ま と め と 今 後 の 課 題 を 示 す ．データソース
データ
ソース
データ仮想化システム
図 1 デー タ 仮 想化 概 要
2. デ ー タ 仮 想 化 に お け る 課 題
2.1. クエリ処 理 概 要
デ ー タ 仮 想 化 は ， 複 数 の DS を 仮 想 統 合 し ， あ た か も 単 一 DS で あ る か の よ う な ア ク セ ス 性 を 提 供 す る 技 術 で あ る ． DVS が 対 象 と す る DS は ， SQL を イ ン タ フ ェ ー ス と す る DBS や CSV な ど の フ ァ イ ル ， Web コ ン テ ン ツ な ど 様 々 で あ る ． な お 本 論 文 で は ， DS が DBS で あ る も の と し て 議 論 を 進 め る ． DVS に お け る ク エ リ 処 理 は 図 2 の よ う な 処 理 フ ロ ー と な る ． DVS と DBS は ， ネ ッ ト ワ ー ク 接 続 さ れ て い る ．DVS は ，各 々 DBS が 保 持 す る デ ー タ ベ ー ス を 把 握 す る た め の ス キ ー マ 情 報 を 持 っ て い る ． こ れ を 仮 想 ス キ ー マ と 呼 ぶ ． ユ ー ザ は ， 仮 想 ス キ ー マ に 基 づ き ， SQL な ど を 用 い た ク エ リ を 作 成・投 稿 す る こ と が で き る ．DVS は ，ユ ー ザ か ら 要 求 さ れ た ク エ リ を 取 得 す る と ，ク エ リ の 構 文 解 析 ，実 行 計 画 生 成 ，最 適 化 を 施 す ． こ こ で 生 成 さ れ た 実 行 計 画 に 基 づ き ， ク エ リ 処 理 に 必 要 と な る デ ー タ を ，各 DBS よ り 随 時 取 得 す る ．こ の と き DVS か ら DBS へ 投 稿 さ れ る ク エ リ を ， サ ブ ク エ リ と 呼 ぶ ．サ ブ ク エ リ は ，DBS の ス キ ー マ や ，SQL な ど の イ ン タ フ ェ ー ス 形 式 に 応 じ て ， 動 的 に 生 成 さ れ る ． サ ブ ク エ リ 結 果 の 取 得 後 ，DVS に て 結 合 ，集 計 ，整 列 演 算 が 実 行 さ れ ， 最 終 的 な ク エ リ 結 果 を ユ ー ザ に 返 却 す る ．DVS に お け る 実 行 計 画 は ，こ れ ら サ ブ ク エ リ に よ る デ ー タ 取 得 か ら ，DVS 上 で の 演 算 処 理 を 含 め た も の と な る ．2.2. 基 礎 実 験
デ ー タ 仮 想 化 技 術 の 現 状 を 把 握 す る た め ， 既 存 デ ー タ 仮 想 化 製 品 や 技 術 に つ い て の 調 査 を 実 施 し た ． 本 調 査 で は ，MIND[4]，Presto，Teiid[5]に つ い て ，複 数 の DBS に よ る デ ー タ 仮 想 化 環 境 を 構 築 し ，TPC-H ベ ン チ マ ー ク を 用 い て ， そ れ ぞ れ の 振 る 舞 い を 確 認 し た ． 調 査 の 結 果 ， い ず れ の 対 象 に つ い て も ク エ リ 処 理 が 著 し く 遅 く な る ， あ る い は 異 常 終 了 す る ケ ー ス が 確 認 さ れ た ． こ れ ら の ク エ リ 処 理 に つ い て ， 実 行 計 画 を 詳 細 に 確 認 し た と こ ろ ， DBS か ら DVS に 転 送 さ れ る サ ブ ク エ リ 結 果 が 膨 大 と な っ て い る こ と が 分 か っ た ． こ れ に よ り ，デ ー タ 転 送 処 理 や DVS に お け る サ ブ ク エ リ 結 果 を 用 い た ク エ リ 処 理 に 時 間 を 要 す る こ と と な り ， 著 し い 処 理 遅 延 を 引 き 起 こ し た と 考 え ら れ る ． ま た ， サ ブ ク エ リ 結 果 が 大 き す ぎ る 場 合 に は ，DVS に て 異 常 終 了 す る こ と も 確 認 さ れ た ． こ の こ と か ら ，DVS に お け る ク エ リ 処 理 の 効 率 化 を 議 論 す る 上 で は ，DVS に て 生 成 さ れ る ，サ ブ ク エ リ の デ ー タ 抽 出 量 が 重 要 に な る も の と 考 え る ．2.3. 既 存 DVS のクエリ処 理 方 式
2.3.1. 単 一 DBS 処 理
調 査 対 象 の DVS に つ い て ，サ ブ ク エ リ 生 成 の 仕 組 み を 調 査 し た ． MIND の 手 法 で は ， サ ブ ク エ リ に 直 積 が 混 入 す る こ と が あ る ．こ れ は ，ユ ー ザ が 投 稿 し た SQL ク エ リ に つ い て ，ス キ ー マ 定 義 情 報 を 参 照 し ，DBS と の 対 応 付 け の み で サ ブ ク エ リ を 生 成 す る こ と に 起 因 す る ． こ れ に よ り ，同 一 DBS で あ れ ば ，結 合 条 件 が 存 在 し な い に も 関 わ ら ず ，サ ブ ク エ リ の FROM 句 に ，複 数 の テ ー ブ ル 名 が 定 義 さ れ る 事 象 が 発 生 す る ． 結 果 と し て ， サ ブ ク エ リ に 直 積 や 多 対 多 結 合 が 混 入 し ， 結 果 サ イ ズ の 肥 大 化 を 招 く こ と が あ る ． Presto で は ，デ ー タ 取 得 対 象 と な る テ ー ブ ル ご と に ． サ ブ ク エ リ が 生 成 さ れ る 仕 組 み と な っ て い る ． Presto は ， 投 稿 さ れ た ク エ リ の 実 行 計 画 生 成 に お い て ， Left-deep Tree を 構 築 す る ． こ の Left-Left-deep Tree に お け る ス キ ャ ン ， 範 囲 選 択 お よ び 射 影 演 算 ま で を プ ッ シ ュ ダ ウ ン し ， サ ブ ク エ リ と し て 生 成 し て い る ． 結 果 と し て ， 単 一 テ ー ブ ル に 閉 じ た サ ブ ク エ リ が 生 成 さ れ る た め ， 直 積 や 多 対 多 結 合 演 算 は 混 入 し な い ． し か し な が ら ， 結 合 に よ る 絞 り 込 み の 恩 恵 が 得 ら れ ず ， 抽 出 件 数 も 多 く な る 傾 向 に あ る ．も し 範 囲 選 択 が さ れ な い 場 合 に は ， 対 象 カ ラ ム 全 件 を 取 得 す る こ と と な る ．Teiid で は ，Bushy Tree に よ る 結 合 演 算 を 含 め た プ ッ シ ュ ダ ウ ン を 実 現 し て い る も の の ， 多 対 多 結 合 演 算 を 排 除 で き て い な い ．Presto 同 様 に Left-deep Tree を 生 成 後 ，ク エ リ に お け る 結 合 条 件 と ス キ ー マ 定 義 を 参 照 し ， 単 一 DBS に 閉 じ た 結 合 演 算 に つ い て 探 索 す る ．発 見 さ れ た 場 合 に は ，実 行 計 画 を Bushy Tree へ と 更 新 し ，結 合 演 算 を プ ッ シ ュ ダ ウ ン す る ． し か し な が ら ， 多 対 多 結 合 の 場 合 に も プ ッ シ ュ ダ ウ ン さ れ る た め ， 非 効 率 と な る 場 合 が あ る ．
DBS-A
DVS
①クエリ取得 ②クエリ最適化 ③サブクエリ送信 ⑤データ送信 ⑥クエリ処理 ⑦結果返却DBS-B
④サブクエリ処理図 2 DVS に おけ る ク エリ 処 理 の流 れ
2.3.2. 複 数 DBS 間 の 処 理
調 査 対 象 と し た シ ス テ ム に つ い て ， MIND と Presto で は ， DVS か ら DBS へ サ ブ ク エ リ が 投 稿 さ れ ， デ ー タ を 取 得 し ，DVS 上 で 結 合 処 理 す る ア ー キ テ ク チ ャ で あ る ． 範 囲 選 択 や 射 影 演 算 の プ ッ シ ュ ダ ウ ン に と ど ま る と ， DBS か ら DVS へ 転 送 せ ざ る を 得 な い ． 例 え ば 図 3 に お い て ，t1 が 巨 大 な テ ー ブ ル で あ っ た 場 合 ，大 規 模 な デ ー タ 転 送 が 発 生 し う る ． 結 果 と し て ， 転 送 に よ る 著 し い 遅 延 ，あ る い は DVS の メ モ リ 不 足 に よ る 処 理 遅 延 や 異 常 終 了 を 引 き 起 こ す ．片 山 ら [6]も 課 題 と し て 挙 げ て い る よ う に ， 複 数 の DS を 跨 る 場 合 の 効 率 化 が 必 要 と 考 え る ．Teiid で は ， Dependent Join と 呼 ば れ る 仕 組 み に よ り 工 夫 さ れ て い る も の の ，そ の 効 果 は 限 定 的 で あ る ．1 つ は Key Pushdown で あ り ， 先 行 す る サ ブ ク エ リ で 得 た 結 果 を ， 後 続 サ ブ ク エ リ の IN 句 に キ ー 情 報 と し て 挿 入 す る 方 法 で あ る ．も う 1 つ は Full Pushdown で あ り ， 前 述 し た 先 行 サ ブ ク エ リ の 結 果 を ， 後 続 サ ブ ク エ リ が 実 行 さ れ る DBS に ，テ ン ポ ラ リ テ ー ブ ル と し て 書 き 込 む 方 法 で あ る ．前 者 は Query Injection，後 者 は Ship Join と も 呼 ば れ る [1]．ど ち ら も ，後 続 サ ブ ク エ リ の 抽 出 デ ー タ 量 を 絞 り 込 む こ と に 有 効 で あ る が ， Key Pushdown は IN 句 へ の 挿 入 件 数 が 多 い 場 合 ， 却 っ て DBS 側 の 処 理 が 著 し く 遅 延 す る こ と が あ り ， 大 規 模 な デ ー タ 処 理 に は 不 向 き と 考 え ら れ る ．Full Pushdown は ，前 者 と 比 較 し て 効 率 的 で あ る も の の ， ユ ー ザ 自 身 が ク エ リ 内 に 記 述 す る こ と を 必 要 と し て い る ． 効 果 的 に 使 い こ な す た め に は ，ユ ー ザ 自 身 が DBS の 物 理 レ イ ア ウ ト や デ ー タ に 対 す る 知 識 を 持 た な け れ ば な ら な い ．
2.4. 既 存 DVS におけるクエリ処 理 課 題
以 上 2 節 で の 議 論 か ら ，DVS に お け る ク エ リ 処 理 効 率 に 関 す る 課 題 は 次 の と お り で あ る ． 課 題 1： 直 積 や 多 対 多 を 避 け る こ と 課 題 2： サ ブ ク エ リ に よ る 抽 出 デ ー タ 量 を 削 減 す る こ と3. 提 案 方 式
前 節 で 述 べ た 課 題 を 解 決 す る 手 法 と し て ， ク エ リ 分 解 と 中 間 デ ー タ 再 配 置 の 2 つ を 述 べ る ． な お ， 中 間 デ ー タ 再 配 置 手 法 に つ い て は ， ク エ リ 分 解 手 法 を 前 提 と し た も の と な っ て い る ． 本 節 で は ，TPC-H ベ ン チ マ ー ク に お け る ク エ リ を 題 材 と し て ，手 法 に つ い て 述 べ る ．ま た DBS が 2 つ あ る も の と し ， 一 方 に テ ー ブ ル Lineitem， 他 方 に そ の ほ か の テ ー ブ ル が 配 置 さ れ て い る も の と 仮 定 す る ．3.1. クエリ分 解 手 法
課 題 1 を 解 決 す る 手 法 と し て ，ク エ リ グ ラ フ [7]の 分 解 に よ り サ ブ ク エ リ 生 成 単 位 を 決 定 す る（ 図 4）．こ こ で は ， 一 対 一 も し く は 一 対 多 の 関 係 の み で 連 結 し た ク エ リ グ ラ フ を 求 め ， こ れ ら を サ ブ ク エ リ の 最 小 単 位 と す る こ と で ， 直 積 や 多 対 多 結 合 を 回 避 す る ． ま ず ， ユ ー ザ に よ り 投 稿 さ れ た ク エ リ に つ い て ， ク エ リ グ ラ フ に 変 換 す る ． ク エ リ グ ラ フ は ， ノ ー ド が テ ー ブ ル ， ノ ー ド 間 エ ッ ジ が テ ー ブ ル 間 結 合 を 表 し て い る ． 得 ら れ た ク エ リ グ ラ フ に 対 し て ， 次 の 基 準 に よ り グ ラ フ 分 解 操 作 を 実 施 す る ． 基 準 1： DBS が 物 理 的 に 異 な る エ ッ ジ 基 準 2： 多 対 多 条 件 と な る エ ッ ジ こ の 操 作 の 結 果 ， 分 解 さ れ た 1 つ 以 上 の ク エ リ グ ラ フ が 得 ら れ る ． 分 解 さ れ た ク エ リ グ ラ フ を も と と し て ， サ ブ ク エ リ を 生 成 す る こ と が で き る ． 分 解 操 作 時 に 取 り 除 い た エ ッ ジ（ 結 合 演 算 ）に つ い て は ，後 述 す る 3.2 節 の 手 法 に よ り ， 処 理 方 法 を 決 定 す る ． す べ て の 結 合 後 に ， 集 計 ， 整 列 演 算 を 処 理 す る ． L S N R O C G L S N R O C 配置DBで分解 × × L S N R O C 多対多で分解 × L O C S N R SubQ3 SubQ2 SubQ1 G1 G2 G3図 4 クエ リ 分 解手 法
t1 t2 t3 DVSDBS-A
DBS-B
図 3 絞り 込 み 不十 分 によ る 影 響
分 解 操 作 の 例 に つ い て ，図 4 を も と に 述 べ る ．ク エ リ グ ラ フ の 初 期 状 態 が 図 左 上 で あ る ．ま ず ，2 つ の DBS に お け る テ ー ブ ル 配 置 よ り ，基 準 1 の 操 作 で L－ O 間 ， L－ S 間 の エ ッ ジ が 分 解 さ れ る ． 次 に ， C－ S 間 が 多 対 多 の 関 係 で あ っ た と 仮 定 す る ． す る と 基 準 2 に よ り ， C－ S 間 の エ ッ ジ で 分 解 さ れ る ．こ の 操 作 の 結 果 ，3 つ の 分 解 さ れ た グ ラ フ が 生 成 さ れ ， こ れ ら を サ ブ ク エ リ の 単 位 と す る こ と で ， 直 積 や 多 対 多 を 回 避 す る こ と が で き る ． こ こ で の サ ブ ク エ リ は ， コ ネ ク テ ッ ド な グ ラ フ と な っ て い る ノ ー ド （ テ ー ブ ル ） と ， 残 っ て い る エ ッ ジ（ 結 合 条 件 ），そ し て 削 除 さ れ た 結 合 条 件 に 含 ま れ て い た カ ラ ム ， 集 計 演 算 等 に 必 要 と な る カ ラ ム を 出 力 す る も の と な る ． グ ラ フ 分 解 操 作 の 基 準 判 定 に つ い て ， い く つ か の 手 法 が 考 え ら れ る ． 1 つ は テ ー ブ ル 定 義 情 報 を 用 い た ル ー ル ベ ー ス の 分 解 で あ る ．基 準 1 と な る DBS ご と の テ ー ブ ル 配 置 は ，各 DBS と テ ー ブ ル 間 の 紐 づ け 情 報 に よ り 確 認 で き る ． 基 準 2 に 関 し て は ， テ ー ブ ル 定 義 情 報 よ り ， 結 合 条 件 カ ラ ム が 一 意 性 制 約 （ unique な ど ） を 有 す る か 否 か で 判 定 で き る ．こ の 手 法 に つ い て は ，DVS が DBS の テ ー ブ ル 定 義 情 報 を 持 つ 必 要 が あ る ．も う 1 つ の 手 段 と し て ，サ イ ズ 推 定 技 術 の 応 用 が 考 え ら れ る ． エ ッ ジ に 紐 づ く テ ー ブ ル と 結 合 条 件 ご と に 結 合 後 の サ イ ズ 推 定 を す る こ と で ， 肥 大 化 を 招 く 結 合 で あ る か 判 断 す る こ と が 可 能 と 考 え る ．
3.2. 中 間 データ再 配 置 手 法
課 題 2 に 対 し て は ，サ ブ ク エ リ の 結 果 を 他 方 の DBS に 一 時 的 再 配 置 し ， 結 合 や 集 計 ， 順 序 整 列 演 算 を プ ッ シ ュ ダ ウ ン す る 手 法 を 提 案 す る （ 図 5）． 3.1 の 手 法 に よ り 得 ら れ た サ ブ ク エ リ 群 に つ い て ， サ イ ズ 推 定 を 用 い て ボ ト ル ネ ッ ク と な り う る サ ブ ク エ リ を 確 認 し ， 効 率 の よ い サ ブ ク エ リ の 組 み 合 わ せ 順 序 を 実 行 計 画 と し て 組 み 立 て る ． 本 手 法 は Greedy Algorithm を ベ ー ス と し て 設 計 し た [8]． ア ル ゴ リ ズ ム は ， あ る サ ブ ク エ リ 群 が 与 え ら れ た と き ， コ ス ト 最 大 と 推 定 さ れ る サ ブ ク エ リ と ， 結 合 後 に も っ と も コ ス ト 最 小 と な る サ ブ ク エ リ の 組 み 合 わ せ ， そ し て 結 合 演 算 の 実 行 場 所 を 判 定 し ， 実 行 計 画 を 出 力 す る ． サ ブ ク エ リ 同 士 の 結 合 演 算 の 実 行 場 所 は ， DVS，DBS 間 の デ ー タ 処 理 を コ ス ト と し て ， も っ と も 小 さ く な る よ う 選 択 す る ． こ こ で ，DBS1 に サ ブ ク エ リ SubQ1，DBS2 に サ ブ ク エ リ SubQ2 が あ り ，SubQ1 が コ ス ト 最 大 で あ っ た と す る ． こ の と き ， 以 下 の 式 に よ り 実 行 場 所 を 選 択 す る ．Read(SubQ1) + Ship(SubQ1) + Read(SubQ2) + Ship(SubQ2) ≥ Read(SubQ2) + Ship(SubQ2) ∗ 2
+ Write(SubQ2) + Read(SubQ1) + Read(SubQ2) + Ship(Join(SubQ1, SubQ2)) 上 記 式 が 成 り 立 つ 場 合 は ，再 配 置 処 理（ SubQ2 の 結 果 を DBS1 に 配 置 し ，DBS1 で SubQ1 と SubQ2 を 結 合 処 理 す る ）を 選 択 す る ．式 の 左 辺 は ，DVS で 結 合 す る 場 合 の コ ス ト ， 右 辺 は 再 配 置 処 理 時 の コ ス ト で あ る ． こ こ で は ， デ ー タ 処 理 に お け る 読 み 込 み ， 書 き 込 み ， 転 送 処 理 を コ ス ト 要 素 と し て い る ．DVS の 場 合 は ，DBS1， DBS2 そ れ ぞ れ で 読 み 込 み と 転 送 処 理 が 発 生 す る ． DBS1 に 中 間 結 果 を 配 置 す る 場 合 は ，DBS2 で の SubQ2 DBS1 lineitem DBS2 other tables DBS1 lineitem DBS2 other tables
DVS
SubQ1 SubQ3 SubQ2
⑤SubQ1‘
DVS
③SubQ3 ①SubQ2 ②SubQ2 結果配置 ④SubQ3 結果配置図 5 中間 デ ー タ再 配 置手 法
L O C S N R SubQ3 SubQ2 SubQ1 推定サイズ 6,000,000 220,000 2,000 SubQ3 SubQ2 SubQ1 推定サイズ 900,000 1,200,000 SubQ1 コスト 24,440,000≧7,560,000 12,004,000≧7,206,000 Step1 Step2 SubQ3 SubQ1 推定サイズ 1,200,000 SubQ2 220,000 SubQ3 SubQ1 推定サイズ 7,000 SubQ2 コスト 5,240,000≧1,867,000 Step3 Step4図 6 再配 置 プ ラン の 探索 例
の 読 み 込 み ，DVS へ の 転 送 処 理 ，そ し て DVS か ら DBS1 へ の 転 送 ，書 き 込 み 処 理 ，そ の 後 DBS1 に お い て ，SubQ1， SubQ2 が そ れ ぞ れ 読 み 込 ま れ ， 結 合 結 果 Join(SubQ1,SubQ2)が DVS へ 転 送 処 理 さ れ る ． 図 6 は ，実 行 計 画 の 探 索 プ ロ セ ス を 示 し た も の で あ る ．Step1 で は ，分 解 さ れ た サ ブ ク エ リ に つ い て ，そ れ ぞ れ 実 行 後 の 推 定 サ イ ズ を 求 め る ． こ の と き ， SubQ1 の 推 定 サ イ ズ が 最 も 大 き く ， ボ ト ル ネ ッ ク に な り う る と 判 断 す る ．
Step2 で は ，SubQ1 と SubQ2，SubQ3 そ れ ぞ れ の 結 果 を 結 合 し た 場 合 の 推 定 サ イ ズ と コ ス ト を 求 め て い る ． い ず れ も 6,000,000 件 か ら 削 減 さ れ て お り ， 効 率 化 が 見 込 ま れ る ． ま た ， コ ス ト は 左 辺 が DVS で の 結 合 時 ， 右 辺 は 再 配 置 時 の コ ス ト 値 で あ る ． SubQ2， SubQ3 ど ち ら を 選 択 し た 場 合 も ，再 配 置 時 が 効 率 的 と 判 断 す る ． こ の 場 合 に は ，よ り 低 コ ス ト で 実 現 可 能 な SubQ3 の 再 配 置 プ ラ ン を 選 択 す る 。 Step3 で は ， 残 っ た サ ブ ク エ リ を Step1 同 様 に 列 挙 し ，推 定 サ イ ズ を 求 め て い る ．こ こ で は SubQ1，SubQ3 結 合 後 の 推 定 サ イ ズ が 大 き く ， ボ ト ル ネ ッ ク に な り う る と 判 断 す る ． Step4 で は ， SubQ2 と 結 合 し た 場 合 の 推 定 サ イ ズ お よ び コ ス ト を 求 め る ． 結 果 と し て ， SubQ2 を 再 配 置 し 結 合 す る プ ラ ン が 効 率 的 と 判 断 し ， Step4 で 挙 げ た プ ラ ン 候 補 が 採 用 さ れ る ． こ の プ ラ ン 探 索 は ， す べ て の サ ブ ク エ リ が 特 定 の DBS に 集 約 さ れ る か ，も し く は 最 適 化 さ れ な い と 判 断 す る ま で 繰 り 返 す ．最 後 の 結 合 演 算 が DBS に プ ッ シ ュ ダ ウ ン 可 能 と 判 断 さ れ た 場 合 に は ， 最 上 位 の 集 計 ， 整 列 演 算 も 含 め て プ ッ シ ュ ダ ウ ン す る こ と が で き る ． 最 終 的 に 得 ら れ る 実 行 計 画 例 を 図 7 に 示 す ．
4. 実 装
3 節 で 述 べ た 提 案 手 法 に つ い て ， オ ー プ ン ソ ー ス ソ フ ト ソ フ ト ウ ェ ア の Presto に 拡 張 実 装 し た ．ベ ー ス と し た バ ー ジ ョ ン は ，Presto-0.100 で あ る ．本 節 で は ，提 案 手 法 を Presto に 適 用 す る 上 で の 要 点 を 述 べ る ．4.1. 実 行 計 画 の最 適 化 機 能
グ ラ フ 分 解 を 用 い た サ ブ ク エ リ 生 成 お よ び 再 配 置 を 含 む 実 行 計 画 の 生 成 に つ い て は ， Presto の 生 成 す る 実 行 計 画 を 書 き 換 え る こ と で 実 現 す る ．Presto で は ，最 適 化 処 理 の 中 で Left-deep Tree と な る 実 行 計 画 を 生 成 す る ． ク エ リ グ ラ フ は ， こ の 実 行 計 画 よ り ， テ ー ブ ル お よ び 結 合 条 件 を 抽 出 し て 生 成 す る ． DBS の 物 理 配 置 は ，同 様 に 実 行 計 画 内 の テ ー ブ ル ア ク セ ス 情 報 か ら 抽 出 可 能 で あ る ．多 対 多 判 定 に つ い て は ， 統 計 情 報 を 用 い た ヒ ス ト グ ラ ム 方 式 の サ イ ズ 推 定 を 応 用 し て い る [9]．結 合 演 算 後 の デ ー タ 件 数 を 推 定 し ，入 力 と な っ た 2 つ の デ ー タ 件 数 い ず れ も 上 回 る 場 合 に 多 対 多 で あ る と 判 定 す る ． 上 記 操 作 で 得 ら れ た 情 報 を も と に 、 分 解 グ ラ フ 群 を 得 る ． 次 に ，分 解 グ ラ フ 情 報 を 用 い て ，Left-deep Tree の 実 行 計 画 を ， サ ブ ク エ リ 単 位 の サ ブ ツ リ ー を 有 す る Bushy Tree に 変 形 す る ． そ の 後 ， 3.2 節 の 手 法 に 従 い ， こ れ ら サ ブ ク エ リ 結 果 と ， サ ブ ク エ リ 同 士 の 結 合 演 算 結 果 サ イ ズ を 推 定 し ， 中 間 デ ー タ 再 配 置 を 考 慮 し た 実 行 計 画 に 更 新 し て い く ．
4.2. 実 行 処 理
提 案 手 法 を 実 現 す る に あ た り ， Presto に お け る プ ッ シ ュ ダ ウ ン 機 能 を 改 修 し て い る ． 元 と な っ て い る Presto で は ， プ ッ シ ュ ダ ウ ン 機 能 が 範 囲 選 択 と 射 影 演 算 に 限 定 さ れ て い る ． こ れ に つ い て ， 結 合 や 集 計 ， 整 列 演 算 も プ ッ シ ュ ダ ウ ン で き る よ う 改 修 し て い る [10]． 中 間 デ ー タ 再 配 置 処 理 に つ い て は ， サ ブ ク エ リ 実 行 結 果 を テ ン ポ ラ リ テ ー ブ ル に 格 納 す る こ と で 実 現 し て い る ．CREATE TABLE 句 に よ り テ ン ポ ラ リ テ ー ブ ル を 生 成 し ，INSERT 句 で 結 果 挿 入 す る ．テ ン ポ ラ リ テ ー ブ ル 名 は ， 複 数 ク エ リ の 発 生 時 を 考 慮 し ， ク エ リ ご と に 一 意 と な る よ う な 識 別 子 を 付 与 す る ． ク エ リ 処 理 の 終 了 後 ， テ ン ポ ラ リ テ ー ブ ル を 削 除 す る ．5. 評 価 実 験
提 案 手 法 の 有 効 性 を 検 証 す る た め ， プ ロ ト タ イ プ を 用 い た 評 価 実 験 を 実 施 す る ． 評 価 実 験 で は ， 提 案 手 法 を 実 装 し た DVS と 複 数 の DBS が 接 続 さ れ た デ ー タ 仮 想 化 環 境 を 構 築 し ，TPC-H ベ ン チ マ ー ク を 用 い て 提 案 手 法 の 効 果 を 確 認 す る ． 比 較 対 象 と し て ， 改 修 前 の Presto-0.100，ク エ リ 分 解 お よ び プ ッ シ ュ ダ ウ ン の み を 実 装 し た DVS， 全 提 案 手 法 を 実 装 し た DVS の 3 パ タ ー ン で 実 行 す る ． 評 価 観 点 と し て ， ク エ リ 実 行 時 間 と DVS－ DBS 間 の デ ー タ 転 送 量 を 観 察 す る ．5.1. 環 境
本 実 験 で は ，プ ロ ト タ イ プ 実 装 し た DVS 1 台 お よ び Lineitem σ Orders Customer Nation Region Supplier σ +GROUPBY/ORDERBY SubQ2 SubQ3 SubQ1’ (DB1) (DB1)図 7 実行 計 画 例
DBS 1～ 3 台 の 複 数 構 成 と す る ．
実 験 に 用 い た 主 な 環 境 仕 様 は 次 の と お り で あ る ． CPU： Intel Xeon X5675 3.07GHz， RAM： 96GB， OS： CentOS 6.6．同 仕 様 の サ ー バ を 4 台 用 意 し ，DVS，DBS そ れ ぞ れ を 構 築 す る ． ま た ， 各 サ ー バ 間 は 1Gbps Ethernet に よ り ネ ッ ト ワ ー ク 接 続 さ れ る ． DBS に は ， そ れ ぞ れ PostgreSQL9.3.9 を 導 入 す る ． 実 験 デ ー タ と し て ， TPC-H デ ー タ セ ッ ト を Scale 1 で 生 成 し た ．デ ー タ 配 置 に つ い て は ，DBS の 構 成 に よ る 効 果 の 差 異 を 確 認 す る た め ， 以 下 の よ う な 3 つ の ケ ー ス で 構 築 す る ． 構 成 1： DBS 1 つ で 構 成 し ， 全 テ ー ブ ル を 配 置 構 成 2：DBS 2 つ で 構 成 し ，lineitem の み ，そ れ 以 外 の テ ー ブ ル と し て 配 置 構 成 3： DBS 3 つ で 構 成 し ， lineitem の み ， orders の み ， そ れ 以 外 の テ ー ブ ル と し て 配 置
5.2. 実 験 結 果
実 験 結 果 に つ い て ， ク エ リ 実 行 時 間 の 比 較 を 図 8， デ ー タ 転 送 量 の 比 較 を 図 9， ま た 提 案 手 法 で 生 成 さ れ た 実 行 計 画 を 図 10 に 示 す ． 図 8,9 の 凡 例 に つ い て ， Proposal は 再 配 置 を 含 む 提 案 手 法 を 実 装 し た DVS ， Pushdown は ク エ リ 分 解 の み 適 用 し た DVS，Presto は 改 修 前 に よ る 実 行 結 果 を 表 し て い る ． 図 8 は ，各 DVS に て TPC-H Q3，Q5，Q10 を 実 行 し た と き の ク エ リ 処 理 に 要 し た 時 間 を 表 し て い る ． 提 案 手 法 と 他 の 実 行 時 間 を 比 較 す る と ，構 成 1，2 に お い て は 2～ 6 倍 の 高 速 化 と な っ て い る ．構 成 2 の Q5 に お い て は ，Proposal と Pushdown の 差 が 観 察 さ れ ，中 間 デ ー タ 再 配 置 の 有 効 性 が 確 認 で き る ． こ れ に 対 し ， 構 成 3 の Q3，Q10 を 見 る と ，Proposal と Presto が 同 程 度 の 実 行 時 間 と な っ て い る ． ま た Presto に つ い て は ， 構 成 1 ～ 3 そ れ ぞ れ に お い て ， 実 行 時 間 が ほ ぼ 変 わ っ て い な い ． こ れ は ， Presto が 構 成 に よ ら ず テ ー ブ ル 単 位 に サ ブ ク エ リ を 生 成 す る た め で あ る ． な お ， 構 成 3 の Q5 Pushdown に つ い て の み ，実 装 上 の 不 具 合 に よ り ，正 し C L O SubQ1 Agg DVS C L O SubQ1 Agg SubQ2 DVS C L O SubQ3 Agg DVS SubQ2 SubQ1 Q3構成1 Q3構成2 Q3構成3 C L DVS S N R SubQ3 Agg O SubQ1 SubQ2 SubQ4 Q5構成3 C L O SubQ1 Agg DVS S N R C L O SubQ1 Agg DVS S N R SubQ2 SubQ3 Agg Q5構成1 Q5構成2図 10 提 案 手 法に よ る実 行 計 画
C L O SubQ1 Agg DVS N C L O SubQ1 Agg DVS N Agg SubQ1 SubQ2 C L O SubQ1 Agg DVS N SubQ2 SubQ3 Q10構成1 Q10構成2 Q10構成3図 8 クエ リ 実 行時 間 の比 較
図 9 デー タ 転 送量 の 比較
い デ ー タ を 取 得 で き て い な い ． 図 9 は ，同 様 に 実 行 し た 場 合 に ，DVS－ DBS 間 で 発 生 し た デ ー タ 量 を 表 し て い る ． デ ー タ 量 の 算 出 に は ， DBS か ら DVS へ 転 送 さ れ る サ ブ ク エ リ 結 果 返 却 処 理 と ， DVS か ら DBS へ 転 送 さ れ る 中 間 デ ー タ 再 配 置 処 理 の 2 つ の 要 素 を 合 算 し て い る ． い ず れ の 構 成 ・ ク エ リ に つ い て も ， 提 案 手 法 で は デ ー タ 転 送 量 は 大 幅 に 削 減 さ れ て い る こ と が 分 か り ， 有 効 に 機 能 し た と 考 え ら れ る ．ま た 構 成 2,3 の Q5 よ り ，中 間 デ ー タ 再 配 置 手 法 が 有 効 に 機 能 し た も の と 分 か る ． 構 成 1 に つ い て ， 提 案 手 法 が 効 率 的 で あ る 理 由 は ， プ ッ シ ュ ダ ウ ン に よ る 効 果 で あ る ．単 一 DBS で 完 結 す る た め ，ク エ リ 分 解 操 作 の 結 果 は 1 本 の ツ リ ー と な り ， 集 計 や 順 序 整 列 演 算 に つ い て も DBS に プ ッ シ ュ ダ ウ ン さ れ て い る（ 図 10）．こ れ は 単 一 DBS 内 で ク エ リ 実 行 す る こ と と 同 様 で あ る ． 本 構 成 の 場 合 ， ク エ リ グ ラ フ は 分 解 さ れ ず ， ま た 中 間 デ ー タ 再 配 置 処 理 も 発 生 し な い ． 構 成 2 に つ い て は ， Q3， Q5 に つ い て 中 間 デ ー タ 再 配 置 の 効 果 が 得 ら れ ， Presto， Pushdown に 対 し 実 行 時 間 お よ び デ ー タ 転 送 量 が 効 率 化 さ れ て い る ． Q10 に つ い て は ， 再 配 置 処 理 さ れ て い な い が ， 実 行 時 間 ， デ ー タ 転 送 量 の 観 点 で も 目 立 っ て 高 く な い ．こ れ は ，SubQ1 と SubQ2 の サ イ ズ 推 定 結 果 か ら ，DVS で の 結 合 が 有 利 と 判 断 さ れ た た め で あ る ．い ず れ に ク エ リ に つ い て も ， Presto， Pushdown（ Q5） の 実 行 時 間 は lineitem を 取 得 す る サ ブ ク エ リ が ボ ト ル ネ ッ ク と な っ て い る ． TPC-H に お い て ，lineitem は も っ と も 大 き な テ ー ブ ル で あ り ， 結 果 取 得 に 時 間 を 要 す る ．こ れ に つ い て 提 案 手 法 で は ， 他 方 の DBS に お け る サ ブ ク エ リ を 先 に 実 行 し ， lineitem が 配 置 さ れ た DBS へ 再 配 置 す る こ と で ， 実 行 時 間 が 短 縮 さ れ て い る ． 構 成 3 に つ い て は ， 提 案 手 法 に よ り デ ー タ 転 送 量 が 大 幅 削 減 さ れ て い る も の の ，Q3，Q10 の ク エ リ 実 行 時 間 は Presto と 同 等 で あ っ た ．提 案 手 法 の 処 理 詳 細 を 確 認 す る と ， 中 間 デ ー タ 再 配 置 処 理 に 時 間 を 要 し て い る こ と が 分 か っ た （ 表 1）． タ ス ク に つ い て ， PLAN は Presto 内 で の 実 行 計 画 を 生 成 す る た め の 所 用 時 間 で あ る ．そ れ 以 外 に つ い て は ，DBS に 発 行 さ れ る SQL 命 令 の 所 要 時 間 で あ り ， そ れ ぞ れ シ ー ケ ン シ ャ ル に 進 め ら れ て い る ． 中 間 デ ー タ 再 配 置 処 理 に は INSERT 命 令 を 用 い た が ， デ ー タ 量 の 増 加 と 共 に 命 令 回 数 と 時 間 が 増 加 し て い る ． こ れ は ， Presto に 提 案 手 法 を 実 装 す る 上 で ，一 命 令 を Presto に お け る ペ ー ジ 単 位 に 生 成 し た た め で あ る ． 別 の 要 因 と し て ， デ ー タ 配 置 が 分 離 し た こ と に よ り ， サ ブ ク エ リ の プ ッ シ ュ ダ ウ ン 効 果 が 減 少 し た こ と で あ る ．例 え ば Q3 は ，lineitem，orders，customer の 3 テ ー ブ ル を 結 合 す る ク エ リ で あ る ． 構 成 3 の 場 合 は す べ て の テ ー ブ ル が 分 離 さ れ る 状 態 と な る た め ， い ず れ の サ ブ ク エ リ も ， 範 囲 選 択 と 射 影 演 算 の プ ッ シ ュ ダ ウ ン に と ど ま り ， デ ー タ 転 送 量 が 大 き く な っ た ． こ の こ と を 踏 ま え ， 実 行 計 画 の 生 成 に 用 い る 判 定 式 も ， INSERT 命 令 の コ ス ト を 踏 ま え て チ ュ ー ニ ン グ が 必 要 と 考 え る ． 実 行 計 画 の 生 成 処 理 に つ い て は ， お よ そ 表 1 の PLAN で 示 し た 程 度 の 時 間 で 完 了 し て お り ， 極 端 に 処 理 時 間 を 要 す る こ と は な か っ た ．
6. 考 察
提 案 手 法 の ク エ リ 分 解 は ， 実 行 計 画 の 探 索 空 間 を 削 減 す る こ と に 有 効 と 考 え ら れ る ． デ ー タ 仮 想 化 環 境 や Multidatabase で は ，DS（ DBS）の サ イ ト 間 転 送 も 考 慮 す る 必 要 が あ る た め ， テ ー ブ ル の 結 合 順 序 を 決 定 す る う え で は 探 索 空 間 が 広 い ． 提 案 手 法 を 用 い る こ と で ， Bushy を 含 む 効 率 的 な 実 行 計 画 が 生 成 可 能 と 考 え る ． 本 手 法 と 同 様 に ， テ ー ブ ル グ ル ー プ か ら サ ブ ツ リ ー を 生 成 し ，効 率 的 な Bushy プ ラ ン を 得 る 手 法 も 研 究 さ れ て い る [11]． 一 方 で ， デ ー タ 転 送 量 の 観 点 で は ， 実 行 計 画 を 十 分 に 探 索 し き れ て い な い ． 図 9 の Q5 と Q10 の Proposal つ い て ， 構 成 2 と 構 成 3 を 比 較 す る と ， 僅 か だ が 構 成 3 の ほ う が 少 な い ． 構 成 3 は ， 物 理 レ イ ア ウ ト が 異 な る た め orders が 分 離 さ れ て い る も の の ，デ ー タ 転 送 量 は 効 率 化 さ れ て い る ． 構 成 2 の 場 合 ， ク エ リ 分 解 次 第 で は 構 成 3 と 同 様 の サ ブ ク エ リ 単 位 と す る こ と も 可 能 で あ る こ と か ら ，提 案 手 法 の ク エ リ 分 解 粒 度 に つ い て ， 更 な る 工 夫 の 余 地 が あ る も の と 考 え る ． ま た ， 転 送 量 を 効 率 化 す る 手 法 と し て Semi-join な ど も あ る ． カ ラ ム 数 が 多 く な る 場 合 に は 有 効 と 考 え ら れ ， プ ラ ン 探 索 に 組 み 込 む こ と が 望 ま し い ． 構成 タスク 時間(s) 備考 PLAN 0.288 SELECT 2.610 PLAN 0.361 CREATE 0.033SELECT 0.594 orders, customer INSERT 1.943 INSERT 18回 SELECT 1.869 DROP 0.022 PLAN 0.377 CREATE 0.032 SELECT 0.827 orders INSERT 12.145 INSERT 89回 CREATE 0.059 SELECT 0.091 customer INSERT 0.149 INSERT 4回 SELECT 2.560 DROP 0.027 DROP 0.018 Q03 構成1 Q03 構成2 Q03 構成3
表 1 提案 手 法 にお け る Q3 処 理詳 細
中 間 デ ー タ 再 配 置 処 理 に つ い て は ， 効 率 的 な 実 現 方 法 も 検 討 す べ き と 考 え る ． 評 価 実 験 に お い て ， 提 案 手 法 に よ る ク エ リ 処 理 方 式 に よ っ て ， 中 間 デ ー タ 量 を 削 減 で き る こ と を 確 認 し た ． し か し な が ら ， 中 間 デ ー タ 再 配 置 処 理 の デ ー タ サ イ ズ が 大 き い 場 合 ， INSERT 命 令 が ボ ト ル ネ ッ ク と な り ， ク エ リ 処 理 の 遅 延 が 確 認 さ れ た ．こ れ に つ い て は ，INSERT 命 令 単 位 の デ ー タ 量 変 更 や ， DBMS 製 品 ご と に INSERT 命 令 の 効 率 化 検 討 ， あ る い は 中 間 デ ー タ を フ ァ イ ル と し て 転 送 し ，DBS に ロ ー ド さ せ る こ と で ， よ り 高 速 に 処 理 す る こ と も 可 能 と 考 え ら れ る ． デ ー タ 仮 想 化 に お い て ， 提 案 手 法 の ク エ リ 処 理 は シ ー ケ ン シ ャ ル 性 が 高 い ． 提 案 手 法 の 狙 い は ， サ ブ ク エ リ の 実 行 結 果 を 再 配 置 す る こ と で ， よ り デ ー タ 量 が 大 き く な る 後 続 の サ ブ ク エ リ を 効 率 化 す る こ と で あ る ． こ の た め ， 順 次 実 行 す る 形 態 と な る こ と が 特 徴 的 で あ る ．一 方 Presto で は ，DBS へ の サ ブ ク エ リ を 同 時 実 行 し ， デ ー タ が 取 り 込 ま れ 次 第 ， 順 次 処 理 を 開 始 す る 特 徴 を 持 つ ．多 数 の DBS に ま た が り ，デ ー タ 量 が ボ ト ル ネ ッ ク と な る ほ ど 大 き く な い 場 合 は ， 却 っ て 提 案 手 法 の 処 理 速 度 が 遅 く な る 可 能 性 が あ る ． 異 常 終 了 を 引 き 起 こ す ク エ リ に つ い て ， 提 案 手 法 は 根 本 的 な 解 決 と な っ て い な い ． ク エ リ 処 理 に お け る デ ー タ 量 を 削 減 し 効 率 化 す る こ と は 可 能 だ が ， ク エ リ に よ っ て は 効 率 化 で き な い こ と が 考 え ら れ る ． サ ー ビ ス レ ベ ル が 高 く ， 異 常 終 了 が 好 ま し く な い ユ ー ス ケ ー ス に 対 し て は ， 確 実 な 実 行 方 式 を 備 え る こ と が 望 ま し い も の と 考 え る [12]． 提 案 手 法 は ， 大 規 模 デ ー タ を 保 有 す る DBS に 対 し て ， ネ ッ ト ワ ー ク リ ソ ー ス は 効 率 化 が 期 待 で き る も の の ，そ の ト レ ー ド オ フ と し て CPU 処 理 負 荷 を 与 え る こ と が 多 く な る ． デ ー タ 転 送 量 の 小 さ く な る 中 間 デ ー タ 再 配 置 を 目 指 す と ， Fact テ ー ブ ル を 有 す る DBS に 対 し ， 外 部 キ ー と な る Dimension テ ー ブ ル へ の サ ブ ク エ リ 結 果 を 再 配 置 し ， 結 合 ， 集 計 や 順 序 整 列 演 算 を プ ッ シ ュ ダ ウ ン す る 実 行 計 画 が 多 く な る も の と 考 え ら れ る ． 結 果 と し て ，大 規 模 デ ー タ を 保 有 す る DBS の 処 理 負 荷 を 高 く す る こ と に な る ． こ の 反 面 ， 従 来 デ ー タ 仮 想 化 の よ う な デ ー タ 転 送 量 が 多 い 場 合 ，IO や ネ ッ ト ワ ー ク リ ソ ー ス を 消 費 す る も の と 考 え ら れ る ． 実 用 に お い て は ，DBS へ の 負 荷 影 響 を 踏 ま え ，リ ソ ー ス 制 御 機 能 を 有 す る こ と が 望 ま し い ． 企 業 内 で 用 い ら れ る DBS の リ ソ ー ス は ，そ の 本 来 業 務 を 対 象 と し て サ イ ジ ン グ さ れ て お り ，常 時 DVS の 要 求 に こ た え ら れ る と は 限 ら な い ． リ ソ ー ス 状 態 を 考 慮 し た 実 行 計 画 の 生 成 ，実 行 制 御 が 必 要 に な る も の と 考 え る ．ま た ，DBS の 特 性 に よ っ て は ， デ ー タ 挿 入 を 得 意 と す る 製 品 も あ る ．コ ス ト モ デ ル を チ ュ ー ニ ン グ す る こ と で ，DBS 資 源 を 有 効 活 用 し た 全 体 最 適 化 が 期 待 で き る ．
7. お わ り に
本 研 究 で は ， デ ー タ 仮 想 化 環 境 に お け る ク エ リ 処 理 に つ い て ， 既 存 デ ー タ 仮 想 化 製 品 お よ び 技 術 を 調 査 し た ． 調 査 の 結 果 ， サ ブ ク エ リ の 処 理 結 果 が 肥 大 化 す る 事 象 と 要 因 ，そ し て DVS に お け る ク エ リ 処 理 の 課 題 を 明 ら か と し た ． 本 課 題 に つ い て ， ク エ リ 分 解 と 中 間 結 果 再 配 置 に よ り ， 中 間 デ ー タ 量 を 削 減 す る ， 効 率 的 な ク エ リ 処 理 手 法 を 考 案 し た ． 考 案 手 法 に つ い て ， オ ー プ ン ソ ー ス ソ フ ト ウ ェ ア の Presto に 実 装 し ，TPC-H を 用 い て 評 価 実 験 を 実 施 し た ． そ の 結 果 ， 中 間 デ ー タ 量 を 削 減 で き る こ と ， ク エ リ 実 行 時 間 を 短 縮 で き る こ と が 確 認 さ れ た ．一 方 ，DBS の 分 離 が 多 く な り ，プ ッ シ ュ ダ ウ ン 効 果 を 得 に く い 状 態 に な る と ， 中 間 デ ー タ 量 が 増 加 し ， デ ー タ 挿 入 処 理 が ボ ト ル ネ ッ ク と な る こ と が 確 認 さ れ た ． 今 後 の 課 題 は ， 中 間 デ ー タ の 再 配 置 方 法 に つ い て 効 率 よ い 手 段 を 取 り 込 む こ と ， 並 列 実 行 も 考 慮 し た 実 行 計 画 生 成 を す る こ と ， 実 用 化 す る 上 で の リ ソ ー ス 制 御 手 法 を 検 討 す る こ と で あ る ．参 考 文 献
[1] Rick F., van der Lans ， “Data Virtualization for Business Intelligence Systems ”, Morgan Kaufmann 2012.
[2] Presto, https://prestodb.io/ . [3] TPC-H, http://www.tpc.org/tpch/.
[4] S.Nural., et al., ”Query Decomposition and Processing Multidatabase Systems”, Object Oriented Database Symposium of the thrid European Joint Conference on Engineering Systems Design and Analysis, pp.41 -52, France 1996. [5] Teiid, http://teiid.jboss.org/. [6] 片 山 大 河 ，嶋 村 誠 ，金 松 基 孝 ，”異 種 デ ー タ ソ ー ス を 透 過 的 に ア ク セ ス 可 能 と す る 統 合 デ ー タ ベ ー ス シ ス テ ム”， 情 報 処 理 学 会 研 究 報 告 ， Vol.2013-DBS-157， 2013
[7] M.Tamer Özsu. and P. Valduriez., “Principles o f Distributed Database Systems Third Edition”, Springer Science, 2011.
[8] D.Kossmann and K.Stocker., “Iterative Dynamic Programming: A New Class of Query Optimization Algorithms”, ACM Transactions on Database Systems, Vol.25, Issue 1, March 2000.
[9] N. Bruno and S. Chauddhuri., “Exploiting Statistics on Query Expressions for optimization”, in Proceedings of 2002 ACM SIGMOD international conference on Management of data, pp.263 -274, 2002. [10] 齋 藤 和 広 , 米 田 信 之 , 渡 辺 泰 之 , 村 松 茂 樹 , 小 林
亜 令 , “デ ー タ 仮 想 化 シ ス テ ム に お け る 効 率 的 な ク エ リ プ ッ シ ュ ダ ウ ン の 実 装 と 評 価”, 情 報 処 理 学 会 研 究 報 告 , Vol.2015-DBS-162, 2015.
[11] R. Ahmed., et al., “Of snowstorms and b ushy trees”, Proceedings of the VLDB Endowment, Vol.7, Issue 13, August 2014.
[12] 齋 藤 和 広 , 米 田 信 之 , 渡 辺 泰 之 , 村 松 茂 樹 , 小 林 亜 令 , “デ ー タ 仮 想 化 シ ス テ ム に お け る ク エ リ 分 割 実 行 の 実 装 と 評 価”, DEIM2016.
