DEIM Forum 2016 D4-6
データ仮想化におけるクエリ分割実行の実装と評価
齋藤 和広
†米田 信之
†村松 茂樹
†渡辺 泰之
†小林 亜令
††株式会社 KDDI 研究所 〒102-8460 東京都千代田区飯田橋 3-10-10 ガーデンエアタワー
E-mail: †{ku-saitou, no-maita, mura, yasuyuki, kobayasi}@kddilabs.jp
あらまし 複数のデータソース(DS)にあるデータを複合的に分析するために，DS の統合が求められている．これ を実現する手段として，複数の DS を論理的に統合するデータ仮想化がある．データ仮想化は，スキーマ情報のみ を統合し，クエリ実行時に必要なデータを DS から取得する．そのため，DS から取得するデータ量が物理メモリサ イズを超えるほど大規模であると，クエリ処理性能が劇的に劣化する．更に，最悪の場合，クエリ実行が失敗する 課題がある．本研究では，データを分割取得してクエリ処理することで，上記課題を解消する手法を提案する．ま た，提案手法をオープンソースソフトウェアの Presto に実装し，TPC-H ベンチマークを用いて評価する． キーワード データ仮想化，データベース，問合せ処理，Presto
1. は じ め に
企 業 が 持 つ デ ー タ の 多 種 多 様 化 に よ り ， デ ー タ の 用 途 や 目 的 に 応 じ て 異 な る デ ー タ ソ ー ス（ DS）が 複 数 構 築 さ れ て い る ． ま た ビ ッ グ デ ー タ 活 用 の 普 及 に よ り デ ー タ 分 析 が 複 雑 化 し ， 様 々 な デ ー タ を 複 合 的 に 利 用 す る 事 例 が 増 え て い る ． 企 業 の 競 争 力 向 上 に は デ ー タ 分 析 の 加 速 が 必 須 で あ り ，デ ー タ 分 析 を 効 率 化 す る た め ， 複 数 存 在 す る DS の 統 合 が 求 め ら れ て い る ．し か し DS の 物 理 的 な 統 合 は ， 移 設 に 伴 う 既 存 の ア プ リ ケ ー シ ョ ン へ の 影 響 や コ ス ト の 観 点 か ら 容 易 に 実 現 で き な い ． そ こ で 筆 者 ら は ， 複 数 DS の 論 理 的 統 合 を 実 現 す る デ ー タ 仮 想 化 技 術 [1]に 着 目 し て い る ．デ ー タ 仮 想 化 は ス キ ー マ 情 報 の み を 統 合 し ， 実 際 の デ ー タ を 統 合 し な い ． デ ー タ 仮 想 化 を 実 現 す る デ ー タ 仮 想 化 シ ス テ ム （ DVS） が ， ク エ リ 実 行 時 に 必 要 な デ ー タ を DS か ら 取 得 す る ． こ れ に よ り 複 数 の DS を 参 照 す る ク エ リ の 実 行 を 実 現 し て い る ．し か し ，DS か ら 取 得 す る デ ー タ や ，DVS に お け る ク エ リ 処 理 の 中 間 結 果 サ イ ズ が 物 理 メ モ リ サ イ ズ を 超 え る ほ ど 大 規 模 に な る と ， ク エ リ 処 理 性 能 が 劇 的 に 劣 化 し ， 最 悪 の 場 合 に は ク エ リ 実 行 が 失 敗 す る ． 本 課 題 を 解 消 す べ く ， DS か ら デ ー タ を 分 割 取 得 し ， DVS に お い て ク エ リ 処 理 を 分 割 実 行 す る 手 法 を 提 案 す る ．提 案 手 法 は ，DVS で 確 実 に 実 行 可 能 な 利 用 メ モ リ サ イ ズ と な る 分 割 ク エ リ の 生 成 と 演 算 の 分 割 実 行 で 構 成 さ れ る ． 本 手 法 を オ ー プ ン ソ ー ス ソ フ ト ウ ェ ア の 分 散 SQL ク エ リ エ ン ジ ン で あ る Presto[2]に 実 装 し ， TPC-H を 用 い て 有 効 性 を 評 価 す る ． 本 論 文 の 構 成 は 以 下 の 通 り で あ る ． 2 節 で デ ー タ 仮 想 化 技 術 の 概 要 と 課 題 を 述 べ ， 3 節 で 提 案 手 法 の 詳 細 を ， 4 節 で Presto へ の 実 装 を 述 べ る ． 5 節 で 提 案 手 法 を 評 価 し ， 最 後 に 6 節 で 本 論 文 の 結 論 と 今 後 の 課 題 を 述 べ る ．2. デ ー タ 仮 想 化
2.1. 概 要
デ ー タ 仮 想 化 は ， DVS に 接 続 し た DS 上 の デ ー タ を テ ー ブ ル 形 式 の ス キ ー マ 情 報 に マ ッ ピ ン グ す る こ と で 複 数 の DS を 論 理 的 に 一 つ の デ ー タ ベ ー ス シ ス テ ム （ DBS） に で き る ． こ れ ら の ス キ ー マ 情 報 は 仮 想 ス キ ー マ と 呼 ば れ ，DVS 上 に 登 録 さ れ る ．仮 想 ス キ ー マ は ， 対 象 デ ー タ の 部 分 デ ー タ を 抽 出 す る 条 件 や ，複 数 の DS を 跨 ぐ デ ー タ を 結 合 す る ビ ュ ー 等 を 表 現 す る こ と が で き る ．ま た ，DBS の よ う に ス キ ー マ 定 義 さ れ て い る デ ー タ だ け で な く ， CSV や JSON 等 の フ ァ イ ル で も 仮 想 ス キ ー マ と し て 定 義 可 能 で あ る ． デ ー タ 仮 想 化 の 対 象 と な る DS に は ，DBS に 限 ら ず ， フ ァ イ ル シ ス テ ム や Web サ ー バ な ど の ネ ッ ト ワ ー ク 経 由 で デ ー タ 取 得 可 能 な シ ス テ ム も 含 ま れ る ． そ の た め の 仕 組 み と し て ， DVS は DS へ の 接 続 プ ロ ト コ ル や デ ー タ フ ァ イ ル の 種 類 に 応 じ た コ ネ ク タ を 持 ち ， ク エ リ 実 行 時 は 適 切 な コ ネ ク タ で 接 続 先 か ら デ ー タ を 取 得 す る ． 図 1 に デ ー タ 仮 想 化 の 概 要 図 を 示 す ．ユ ー ザ は ，仮 想 ス キ ー マ を 処 理 対 象 の テ ー ブ ル と す る SQL ク エ リ を DVS に 投 稿 す る こ と が で き る ． DVS は ユ ー ザ が 投 稿 し た SQL ク エ リ か ら 仮 想 ス キ ー マ の 情 報 に 従 っ て 独 自 の 演 算 木 を 生 成 し ， 処 理 対 象 の デ ー タ が あ る DS を 特 定 す る ．次 に DVS は DS の イ ン タ フ ェ ー ス に 合 わ せ た ク エ リ を 生 成 し ， 演 算 木 に 従 っ て そ の DS に 投 稿 す る ． 投 稿 し た ク エ リ の 結 果 が DS か ら 返 る と ， DVS は そ の 結 果 を 仮 想 ス キ ー マ の デ ー タ 形 式 に 変 換 す る ． 更 に DVS は ， DS で 処 理 し な か っ た 残 り の 演 算 を 処 理 し ， ユ ー ザ に そ の 結 果 を 返 す ．2.2. データ仮 想 化 の課 題
デ ー タ 仮 想 化 は ， ユ ー ザ が 投 稿 し た ク エ リ を 実 行 す る た め に ，利 用 す る デ ー タ を DS 又 は DVS の 物 理 メ モ リ に 展 開 す る ． そ の た め ， DS 又 は DVS の 物 理 メ モ リサ イ ズ を 超 え る ほ ど 大 規 模 な デ ー タ を 扱 う 場 合 に ， ク エ リ 処 理 性 能 が 劇 的 に 劣 化 し ， 最 悪 の 場 合 に は ク エ リ の 実 行 が 失 敗 す る 課 題 が あ る ． こ の 課 題 は ， DS 及 び DVS 間 の デ ー タ 通 信 時 と ，DVS に お け る ク エ リ 処 理 時 の 二 箇 所 で 発 生 す る ． 以 下 で 課 題 の 詳 細 を 述 べ る ．
2.2.1. デ ー タ 通 信 時
DVS は ネ ッ ト ワ ー ク 経 由 で DS に ク エ リ を 投 稿 し て デ ー タ を 取 得 す る ．こ こ で DVS の 処 理 待 ち が 発 生 す る と ，取 得 す る デ ー タ を DS 又 は DVS の 物 理 メ モ リ で 保 持 し て お く 必 要 が あ る ． そ の デ ー タ サ イ ズ が 物 理 メ モ リ を 超 え る と ス ト レ ー ジ ア ク セ ス が 頻 発 し ， 場 合 に よ っ て は メ モ リ 不 足 で 強 制 終 了 す る ． 例 え ば DVS が JDBC で DS か ら デ ー タ を 取 得 す る 場 合 ，DVS が DS に 投 稿 し た ク エ リ の 結 果 を 全 て 取 得 し て ，DVS の 演 算 処 理 が 始 ま る ま で DVS の 物 理 メ モ リ に 保 持 す る ． ま た JDBC の カ ー ソ ル を 利 用 し た 場 合 ， DVS の 演 算 処 理 が 開 始 さ れ る ま で DS の 物 理 メ モ リ で デ ー タ を 保 持 す る ． こ の よ う に ， デ ー タ の 取 得 方 法 に 応 じ て ， DVS と DS の ど ち ら か で メ モ リ 不 足 が 発 生 す る 可 能 性 が あ る ． こ れ を 回 避 す る た め ，DS で 出 来 る 限 り デ ー タ サ イ ズ を 小 さ く す る 手 法 が 考 え ら れ る ． そ の 手 段 の 一 つ が ク エ リ プ ッ シ ュ ダ ウ ン で あ り ，DS へ 関 係 演 算 処 理（ 射 影 や 選 択 ， 結 合 な ど ） を 委 譲 す る こ と で ， デ ー タ サ イ ズ を 削 減 す る [3]． ま た 別 の 手 段 と し て ， 異 な る DS の デ ー タ に 対 す る 結 合 演 算 を 含 む ク エ リ に お い て ， 片 方 の DS の デ ー タ を も う 一 方 の DS に 再 配 置 す る こ と で デ ー タ を 削 減 す る 手 法 が あ る [4]． し か し こ れ ら の デ ー タ 削 減 の 手 法 を 用 い た と し て も ， デ ー タ 通 信 の サ イ ズ を 物 理 メ モ リ サ イ ズ 以 下 に で き な い 場 合 が あ る ． 例 え ば ク エ リ プ ッ シ ュ ダ ウ ン し た 結 果 が 大 規 模 で あ る 場 合 や ， 結 合 す る デ ー タ が ど ち ら も 大 規 模 で あ る 場 合 で あ る ． ま た デ ー タ 仮 想 化 は ， 既 に 運 用 さ れ て い る DS を 対 象 と で き る が ， そ の DS に と っ て は 構 築 当 初 に 想 定 し て い な い 用 途 の た め ， 従 来 の 用 途 や 運 用 上 の 制 約 に よ っ て DS の リ ソ ー ス を 利 用 で き ず ， 前 述 の デ ー タ 削 減 の 手 法 が 使 え な い 場 合 が あ る ． 従 っ て ， DS 又 は DVS の 物 理 メ モ リ の サ イ ズ を 超 え る 大 規 模 な デ ー タ で も ， 確 実 に DS か ら デ ー タ 取 得 で き る 手 法 が 必 要 と な る ．2.2.2. DVS に お け る ク エ リ 処 理 時
DVS は DS か ら 取 得 し た デ ー タ に 対 し て ク エ リ 処 理 を 実 行 す る ．DVS に お け る ク エ リ 処 理 方 式 は ，従 来 の DBS の ク エ リ 処 理 方 式 が 適 用 さ れ る ．こ れ に は ，演 算 毎 に デ ー タ を 全 て 実 体 化 し て 処 理 す る Materialized 方 式 [5]， 演 算 木 の ル ー ト か ら 順 に 下 位 の 演 算 に 対 し て 1 レ コ ー ド ず つ 要 求 し て 処 理 す る Volcano 方 式 [6]， ブ ロ ッ ク 単 位 で 取 得 し て 並 列 処 理 す る Morsel 方 式 [7]が 存 在 す る ． 上 記 の 方 式 は い ず れ も ， 一 度 読 み 込 ん だ デ ー タ を メ モ リ に 保 持 し た ま ま 全 て の 演 算 を 処 理 す る ．そ の た め ， 入 力 デ ー タ が 大 規 模 の 場 合 や ， ま た 多 対 多 の 結 合 演 算 や 直 積 演 算 ， キ ャ ス ト に よ る 型 の 変 換 ， 列 数 の 増 加 等 に よ っ て ， 演 算 結 果 の 出 力 デ ー タ の サ イ ズ が 入 力 デ ー タ よ り も 大 き く な る 場 合 に ， 物 理 メ モ リ を 超 え る こ と が あ る ． そ の 結 果 ， メ モ リ 不 足 が 発 生 し ， 演 算 処 理 で ス ト レ ー ジ ア ク セ ス の 頻 発 に よ る 性 能 の 劣 化 や 強 制 終 了 す る 場 合 が あ る ． 従 っ て ， 物 理 メ モ リ の サ イ ズ を 超 え る 大 規 模 な デ ー タ を 対 象 と す る 演 算 に お い て も ，DVS が 確 実 に 演 算 処 理 で き る 手 法 が 必 要 と な る ．2.3. 既 存 の DVS
デ ー タ 仮 想 化 に 関 す る 研 究 と し て ， 関 係 デ ー タ ベ ー ス と XML デ ー タ ベ ー ス を 対 象 と す る GRelC[8]と ，DS の 統 計 情 報 を 活 用 し て DS の 処 理 順 序 を 最 適 化 す る OASIS[9]が あ る ． 両 者 と も に ， グ リ ッ ド 環 境 上 に 散 ら ば る 複 数 の DS を 対 象 に ， 仮 想 的 な 一 つ の デ ー タ ス ト レ ー ジ を 提 供 し て お り ，ユ ー ザ は デ ー タ の 場 所 や 各 DS の イ ン タ フ ェ ー ス を 意 識 す る こ と な く ア ク セ ス す る こ と が 可 能 と な る ．一 方 ，DVS 上 で は ク エ リ 処 理 を 行 わ ず ， ク ラ イ ア ン ト が デ ー タ 取 得 後 に 独 自 で 処 理 を 実 行 す る こ と が 前 提 で あ る ． ま た 大 規 模 デ ー タ の 取 得 に 関 す る 考 慮 も し て い な い ． DVS の 一 種 で あ る MIND[10]や ， オ ー プ ン ソ ー ス ソ フ ト ウ ェ ア と し て DVS の 実 装 を 行 っ て い る Teiid[11] は ， 複 数 の DS を 仮 想 的 に 一 つ の ス ト レ ー ジ と し て ユ ー ザ に 提 供 す る だ け で な く ，通 常 の DBS と 同 様 に SQL ク エ リ 処 理 が 可 能 で あ る ． 複 数 の DS を 跨 ぐ テ ー ブ ル 同 士 の 結 合 処 理 も 可 能 で あ り ， 複 数 の DS の 結 果 を DVS に 集 約 し ，DVS 上 の ク エ リ エ ン ジ ン で 結 合 処 理 を図 1 デー タ 仮 想化 の 概要 図
実 現 し て い る ． し か し 大 規 模 デ ー タ の 処 理 を 前 提 と し て い な い た め ，デ ー タ 通 信 時 及 び DVS の ク エ リ 処 理 時 に メ モ リ 不 足 が 発 生 す る 可 能 性 が あ る ．
オ ー プ ン ソ ー ス ソ フ ト ウ ェ ア の Presto[2] 及 び Apache Drill[12]は ， 分 散 シ ス テ ム の Apache Hadoop で 管 理 さ れ る デ ー タ を SQL イ ン タ フ ェ ー ス で 操 作 可 能 な 分 散 ク エ リ エ ン ジ ン で あ る ． こ れ ら は ， Apache Hadoop 以 外 の DS も 対 象 に 処 理 で き ，デ ー タ 仮 想 化 を 実 現 で き る ．更 に ，DVS に お け る ク エ リ 処 理 を 分 散 処 理 す る こ と が で き ， デ ー タ 規 模 に 応 じ て 物 理 サ ー バ を 増 や す こ と で 大 規 模 デ ー タ に 対 応 で き る ． し か し ， 構 築 し た 物 理 サ ー バ の 物 理 メ モ リ を 超 え る 規 模 の デ ー タ に 対 し て は ク エ リ 処 理 す る こ と が で き な い ．
3. 提 案 手 法
前 節 で 述 べ た デ ー タ 仮 想 化 の 課 題 を 解 消 す る た め に ， DS か ら デ ー タ を 分 割 取 得 す る ク エ リ 分 割 手 法 と ， ス ト レ ー ジ を 利 用 し た DVS の 分 割 実 行 手 法 を 提 案 す る ． 3.1 で は ク エ リ 分 割 手 法 に つ い て 述 べ ，3.2 で DVS の 分 割 実 行 手 法 を 述 べ る ． 3.3 で は こ れ ら の 手 法 で 共 通 し て 必 要 な 分 割 条 件 に つ い て 述 べ る ． 3.4 で は 提 案 手 法 を 含 む DVS の シ ス テ ム 構 成 に つ い て 述 べ る ．3.1. クエリ分 割 手 法
本 手 法 で は ，DS か ら デ ー タ を 取 得 す る ク エ リ を 複 数 に 分 割 し た 分 割 ク エ リ を 作 成 し ， 一 つ の ク エ リ で 取 得 す る デ ー タ サ イ ズ を 物 理 メ モ リ サ イ ズ 以 下 に す る ． こ れ に よ り ， デ ー タ 通 信 時 に 発 生 す る 課 題 を 解 消 す る ． 分 割 ク エ リ は ， 本 来 一 つ で あ っ た ク エ リ に 対 し て ， 3.3 で 述 べ る 分 割 条 件 を 利 用 し て ， 取 得 す る デ ー タ の 範 囲 を 指 定 し て 複 数 に 分 割 し た ク エ リ で あ る ． こ の 分 割 ク エ リ を 全 て 実 行 し て ， 一 つ の デ ー タ を 取 得 す る ． 例 え ば DS の イ ン タ フ ェ ー ス が SQL の 場 合 ，SQL ク エ リ の WHERE 句 で ， 特 定 の 列 の 実 値 に 対 す る 取 得 範 囲 の 条 件 式 を 追 加 す る ． そ し て そ の 特 定 の 列 に お け る 全 て の 範 囲 を 網 羅 す る よ う に 条 件 式 を 変 更 し ，SQL ク エ リ を 複 数 個 生 成 す る ． 生 成 し た 分 割 ク エ リ は ，DVS の ク エ リ 実 行 時 に 順 次 DS に 投 稿 さ れ る ．一 つ の 分 割 ク エ リ に よ っ て 部 分 デ ー タ を 取 得 後 ，そ の デ ー タ が DVS の 次 の 演 算 処 理 で 利 用 さ れ て メ モ リ が 解 放 さ れ た 後 に ， 次 の 分 割 ク エ リ を 投 稿 す る ．な お ，DVS の 演 算 処 理 も 物 理 メ モ リ を 利 用 す る た め ， 分 割 ク エ リ の 分 割 条 件 は 3.2 で 述 べ る 分 割 実 行 を 考 慮 し て 設 定 さ れ る ．3.2. DVS の分 割 実 行 手 法
本 手 法 は ，DVS に お け る 演 算 処 理 で 物 理 メ モ リ サ イ ズ を 超 え る 場 合 を 考 慮 し ，DVS 上 の 一 時 ス ト レ ー ジ を 利 用 し て 演 算 処 理 を 分 割 実 行 す る ．こ れ に よ り DVS の ク エ リ 処 理 に お け る 課 題 を 解 消 す る ． 分 割 実 行 は DVS が 作 成 し た 演 算 木 に 従 っ て ，演 算 単 位 で 行 わ れ る ． あ る 演 算 で 分 割 実 行 が 必 要 と 判 断 さ れ た 場 合 ，Materialized 方 式 と 同 様 に そ の 演 算 の み が 処 理 さ れ る よ う 制 御 す る ． そ の 演 算 に は ， ク エ リ 分 割 手 法 と 同 様 に 分 割 条 件 が 作 成 さ れ ， 分 割 条 件 に 従 っ た デ ー タ の み を 入 力 デ ー タ と し て 処 理 す る ． そ の 入 力 デ ー タ は DS か 一 時 ス ト レ ー ジ に 格 納 さ れ て い る 必 要 が あ る ． そ の た め ， 分 割 実 行 さ れ る 演 算 の 直 前 の 演 算 は ， 分 割 の 要 否 に 関 わ ら ず ， 一 時 ス ト レ ー ジ に 出 力 す る 必 要 が あ る ． 分 割 実 行 し た 演 算 の 出 力 デ ー タ は 一 時 ス ト レ ー ジ に 退 避 す る ． 分 割 実 行 の 演 算 木 の 例 を 図 2 に 示 す ．こ の 演 算 木 で は ， 各 DS へ の 分 割 ク エ リ の 投 稿 と 結 合 演 算 処 理 を 順 次 繰 り 返 し ， 結 果 を 一 時 ス ト レ ー ジ に 格 納 す る ． そ の 結 果 を 集 約 演 算 （ GROUP BY） の 分 割 条 件 に 従 っ て 2 分 割 で 一 時 ス ト レ ー ジ 内 の 指 定 の 分 割 範 囲 の デ ー タ に 対 し て 処 理 し ， 一 時 ス ト レ ー ジ に 格 納 す る ． 最 後 に 整 列 演 算 （ ORDER BY） を 一 時 ス ト レ ー ジ に あ る デ ー タ に 対 し て 実 行 し ， ク エ リ 処 理 完 了 と な る ．3.3. 分 割 条 件
ク エ リ 分 割 手 法 及 び DVS の 分 割 実 行 手 法 で は ，分 割 す る た め の 条 件 を 生 成 す る ． そ の 分 割 条 件 は 以 下 の 三 つ の 要 素 で 構 成 さ れ る ． 分 割 数 分 割 基 準 属 性 （ 分 割 の 基 準 と な る 属 性 ） 分 割 範 囲 （ 分 割 し て 処 理 す る デ ー タ の 範 囲 ） 分 割 数 は ， 分 割 対 象 の ク エ リ や 演 算 で 利 用 す る メ モ リ サ イ ズ を ， 物 理 メ モ リ サ イ ズ で 割 っ て 小 数 点 以 下 を 切 り 上 げ る こ と で 算 出 す る ． 分 割 基 準 属 性 は 処 理 対 象 の 数 と 等 し く 選 択 さ れ ，単 項 演 算 と 分 割 ク エ リ は 一 つ ， 二 項 演 算 は 二 つ の デ ー タ の そ れ ぞ れ か ら 一 つ ず つ 選 択 さ れ る ． 分 割 範 囲 は 分 割 さ れ る デ ー タ の 範 囲 で あ り ，図 2 分割 実 行 の演 算 木の 例
分 割 後 の デ ー タ サ イ ズ が 物 理 メ モ リ サ イ ズ 以 下 と な る よ う に ， 分 割 基 準 属 性 が 持 つ 実 値 か ら 決 定 さ れ る ． こ れ は 分 割 数 分 作 成 さ れ る ． 分 割 範 囲 の 計 算 に は ， 演 算 毎 の 中 間 結 果 サ イ ズ の 予 測 と ， 更 に デ ー タ を 分 割 す る た め に 列 の 実 値 が 必 要 と な る ． 分 割 範 囲 を 計 算 す る 最 も 単 純 な 方 法 は ， 属 性 毎 の 最 大 値 と 最 小 値 を 統 計 情 報 と し て 作 成 し ， 分 割 数 で 最 大 値 か ら 最 小 値 を 均 等 に 分 割 す る 方 法 で あ る ． し か し 実 値 の 分 布 が 偏 る こ と で 分 割 範 囲 内 の サ イ ズ に 偏 り が 生 じ ， 利 用 可 能 な 物 理 メ モ リ サ イ ズ を 超 え る 場 合 が あ る ． そ こ で 提 案 手 法 で は ， 統 計 情 報 と し て 属 性 毎 の 実 値 の 分 布 を 表 す ヒ ス ト グ ラ ム を 利 用 す る こ と で ， 偏 り を 考 慮 し た 分 割 範 囲 の 計 算 を 行 う [13]．ま た ，分 割 の 要 否 の 判 定 に 利 用 す る 演 算 毎 の 出 力 デ ー タ サ イ ズ （ 中 間 結 果 ） も 同 様 に ヒ ス ト グ ラ ム を 利 用 し て 計 算 す る [14]． 以 下 で 単 項 演 算 と 二 項 演 算 ， 分 割 ク エ リ の 分 割 条 件 の 生 成 方 法 を 述 べ る ．
3.3.1. 単 項 演 算 の 分 割 条 件
単 項 演 算 に お け る 分 割 条 件 は ， 分 割 実 行 さ れ た 結 果 同 士 で 追 加 処 理 が 発 生 し な い よ う に 生 成 す る こ と で ， 余 計 な I/O や DS へ の ク エ リ 投 稿 を 抑 制 す る ． そ の た め に ， 分 割 基 準 属 性 を 演 算 の キ ー 属 性 に し ， そ の 属 性 に 対 す る 分 割 範 囲 で 分 割 実 行 す る ． 例 え ば 集 約 演 算 の 場 合 ，GROUP BY 句 で 指 定 さ れ る 属 性 を 分 割 基 準 属 性 に 選 択 す る こ と で ， 一 回 の 分 割 実 行 内 で 演 算 処 理 を 完 結 す る こ と が で き る ． な お ， キ ー 属 性 が な い 演 算 の 場 合 や ， も し く は 複 数 の キ ー 属 性 が あ る 場 合 に は ， 入 力 デ ー タ を 取 得 す る 際 に 検 索 が 高 速 な 属 性（ 索 引 付 き 等 ） を 優 先 す る 選 択 ポ リ シ ー と な る ． 例 外 と し て ， GROUP BY 句 が な い 場 合 の 集 計 処 理 （ COUNT(*)等 ）に お い て ，分 割 実 行 後 に ，そ れ ぞ れ の 結 果 に 対 し て 更 に 集 計 処 理 を 実 行 す る 必 要 が あ る ． ま た ， 整 列 演 算 に 関 し て も 最 終 的 に 分 割 実 行 し た 結 果 の そ れ ぞ れ で 順 序 の 整 合 性 を と る 必 要 が あ る が ， 提 案 手 法 で は 分 割 範 囲 の 指 定 を ソ ー ト の 順 序 と 合 せ て 分 割 実 行 し た 順 序 通 り に 結 果 を 並 べ る こ と で ， 整 列 演 算 の 処 理 を 完 了 す る こ と が で き る ．3.3.2. 二 項 演 算 の 分 割 条 件
二 項 演 算 に お け る 分 割 実 行 は ， 単 項 演 算 の 場 合 と 同 様 に ， 分 割 実 行 単 位 で 演 算 が 完 結 す る 分 割 条 件 を 生 成 す る ． 結 合 演 算 に 関 し て は ， 結 合 条 件 で 利 用 さ れ る 二 つ の 属 性 を そ れ ぞ れ 分 割 基 準 属 性 に 選 択 し ， こ れ ら の 分 割 範 囲 を 各 分 割 実 行 で 共 通 の 値 に す る ．こ れ に よ り ， Block Nested Loop Join の よ う に 同 じ デ ー タ を 複 数 回 呼 び 出 す 必 要 が な く な り ， ブ ロ ッ ク 単 位 の Merge Join の 要 領 で 実 行 す る こ と が で き る ． た だ し ， 直 積 演 算 に 関 し て は 複 数 回 の 呼 び 出 し が 必 須 で あ り ， 二 つ の デ ー タ の 分 割 基 準 属 性 は ， そ れ ぞ れ が 単 項 演 算 に お け る キ ー 属 性 が な い 場 合 の 選 択 ポ リ シ ー に 従 う ． 集 合 演 算 （ UNION）に 関 し て も 結 合 条 件 が 存 在 し な い た め ，キ ー 属 性 が な い 場 合 の 選 択 ポ リ シ ー に 従 う が ， 分 割 実 行 単 位 で 演 算 を 完 結 さ せ る た め に ， 二 つ の デ ー タ で 同 じ 分 割 条 件 を 生 成 す る ．3.3.3. 分 割 ク エ リ の 分 割 条 件
DS か ら 分 割 し て デ ー タ を 取 得 す る 分 割 ク エ リ の 分 割 条 件 は ， 演 算 木 に お け る 直 上 の 演 算 の 分 割 条 件 を 利 用 す る ． し か し ， DS と DVS で 利 用 で き る 物 理 メ モ リ サ イ ズ が 異 な る 場 合 が あ る ． も し DS の 方 が 小 さ く ， 直 上 の 演 算 の 分 割 条 件 で は メ モ リ に 保 持 で き な い 場 合 ， DS の メ モ リ 溢 れ に よ る 遅 延 や 強 制 終 了 が 発 生 す る ．そ こ で 以 下 の 二 つ の 方 法 で こ れ を 回 避 す る ． 一 つ は ， 取 得 す る デ ー タ を DVS に 蓄 積 す る 全 取 得 手 法 で あ る ．も う 一 つ は ， 分 割 条 件 を 再 計 算 し ， 直 上 の 演 算 の 分 割 範 囲 を 更 に 分 割 す る Scan 分 割 手 法 で あ る ．ま た ，演 算 木 の 直 上 に 分 割 実 行 す る 演 算 が な い 場 合 も 同 様 の 方 法 で 回 避 す る ．分 割 条 件 を 再 計 算 す る 場 合 は ，DS に 投 稿 す る ク エ リ の 出 力 デ ー タ サ イ ズ を 用 い て ， 分 割 の 要 否 の 判 断 と 分 割 条 件 の 計 算 を 行 う ．3.4. 提 案 手 法 のシステム構 成
こ れ ま で に 述 べ た 提 案 方 手 法 を 含 む DVS の シ ス テ ム 構 成 図 を 図 3 に 示 す ．DVS は ま ず ，ク ラ イ ア ン ト か ら 投 稿 さ れ た ク エ リ を 評 価 し ，従 来 の DVS と 同 様 に 仮 想 ス キ ー マ 情 報 を 基 に 演 算 木 を 生 成 す る ． こ の 演 算 木 か ら 演 算 毎 の 利 用 メ モ リ サ イ ズ を 算 出 し ， 演 算 毎 に 一 定 サ イ ズ を 超 え る 演 算 の 分 割 条 件 を 生 成 す る ．次 に DS か ら デ ー タ を 取 得 す る た め の ク エ リ を 生 成 す る ． デ ー タ が 大 規 模 な 場 合 ， 分 割 条 件 に 従 っ て ク エ リ を 分 割 し て 生 成 す る ． そ し て 演 算 木 に 従 っ て ， 対 象 の DS に 順 次 ク エ リ を 投 稿 し ，そ の 結 果 に 対 し て DVS 上 で の 演 算 を 処 理 す る ．DVS 上 で の 演 算 処 理 に 分 割 実 行 が 必 要 な 場 合 ， そ の 分 割 さ れ た 演 算 処 理 の 結 果 を 一 時 ス ト レ ー ジ に 退 避 し て 次 の 分 割 処 理 を す る ． 演 算 木 上 の 全 演 算 が 完 了 し た 段 階 で ， 結 果 を ク ラ イ ア ン ト に 転 送 す る ．4. 実 装
4.1. Presto
提 案 手 法 を ，オ ー プ ン ソ ー ス ソ フ ト ウ ェ ア で DVS の 一 種 で あ る Presto に 実 装 し た ． バ ー ジ ョ ン は 0.100 を 利 用 し た ． な お ， Presto は DS が SQL ク エ リ を 処 理 可 能 で あ っ た と し て も デ ー タ を 取 得 す る だ け で あ り ， 数 値 型 の 範 囲 選 択 演 算 と 射 影 演 算 以 外 を ク エ リ プ ッ シ ュ ダ ウ ン し な い ．そ こ で ，提 案 手 法 の 実 装 に 先 立 ち ，JDBC コ ネ ク タ を 対 象 に ，数 値 型 以 外 の 選 択 演 算 ，結 合 演 算 ， 集 約 演 算 ， 整 列 演 算 ， 集 合 演 算 の ク エ リ プ ッ シ ュ ダ ウ ン を 実 装 し た ． Presto は ，ク ラ イ ア ン ト か ら SQL ク エ リ を 受 け 付 け ，実 行 計 画 を 作 成 す る Coordinator と ， DS か ら デ ー タ を 取 得 し て 演 算 処 理 を 実 行 す る Worker か ら 構 成 さ れ る ． Coordinator は 実 行 計 画 と し て SQL ク エ リ か ら Left-deep な 演 算 木 を 作 成 す る ． ま た 演 算 木 に は ， DS か ら デ ー タ を 取 得 す る Scan 演 算 が あ り ， DS の 接 続 情 報 と ク エ リ プ ッ シ ュ ダ ウ ン す る 演 算 の 情 報 が 含 ま れ て い る ． Worker は Coordinator か ら 実 行 計 画 を 受 け 取 る と ， 処 理 対 象 の デ ー タ を 取 得 す る た め に DS の イ ン タ フ ェ ー ス に 合 わ せ た ク エ リ を 生 成 す る ． 以 降 で 述 べ る 提 案 手 法 の 実 装 で は DS に DBS を 想 定 し て い る た め ，生 成 す る ク エ リ は ク エ リ プ ッ シ ュ ダ ウ ン す る 演 算 を 含 む SQL ク エ リ と な る ．SQL ク エ リ 実 行 後 ，Worker に て 演 算 木 に 従 っ た 演 算 処 理 を 実 施 す る ． Presto の ク エ リ 処 理 方 式 は Volcano 方 式 を ベ ー ス に ， 最 大 1MB の ペ ー ジ 単 位 で デ ー タ 要 求 し て 演 算 処 理 す る 方 式 を 採 用 し て い る ．DS か ら の デ ー タ 取 得 は JDBC の カ ー ソ ル を 採 用 し ， 演 算 の 要 求 に 対 し て 都 度 DS か ら デ ー タ を 取 得 す る ． な お カ ー ソ ル の フ ェ ッ チ サ イ ズ は 1000 レ コ ー ド に 設 定 し て い る ．
4.2. 提 案 手 法 の実 装
提 案 手 法 で あ る ク エ リ 分 割 手 法 及 び DVS の 分 割 実 行 手 法 の Presto に お け る 実 装 を 述 べ る ．提 案 手 法 の シ ス テ ム 構 成 で あ る 図 3 を Presto の シ ス テ ム 構 成 に 適 用 す る と 図 4 と な る ．色 塗 り の ボ ッ ク ス が 新 規 に 作 成 し た モ ジ ュ ー ル で ，点 線 の ボ ッ ク ス が Presto で 既 存 の モ ジ ュ ー ル に 変 更 を 加 え た も の で あ る ．Coordinator で SQL ク エ リ か ら 生 成 さ れ る 実 行 計 画 に 対 し て 分 割 条 件 を 付 与 し ，Worker に 転 送 す る ．Worker は 演 算 木 に 従 っ て 演 算 を 処 理 し ， 分 割 条 件 に 従 っ て 一 時 ス ト レ ー ジ を 利 用 し て 分 割 実 行 す る ．DBS の デ ー タ は ，分 割 条 件 が あ る 場 合 に 分 割 ク エ リ を 生 成 し て 取 得 す る ． な お 統 計 情 報 と 一 時 ス ト レ ー ジ は ，そ れ ぞ れ 管 理 用 の DBS と し て PostgreSQL[15]を 利 用 し て 構 築 す る ． 以 下 で ， 実 装 の シ ス テ ム 構 成 に 従 い ， 分 割 条 件 の 実 装 ，DVS の 分 割 実 行 手 法 の 実 装 ，並 び に ク エ リ 分 割 手 法 の 実 装 の 詳 細 を 述 べ る ．4.2.1. 分 割 条 件 の 実 装
分 割 条 件 の 計 算 に 必 要 な 処 理 対 象 テ ー ブ ル の 統 計 情 報 （ テ ー ブ ル 名 ， テ ー ブ ル サ イ ズ ， レ コ ー ド 数 ， 属 性 名 ， 型 名 ， 型 の サ イ ズ ， 属 性 の ヒ ス ト グ ラ ム 情 報 ） は ，Coordinator 専 用 の 管 理 用 デ ー タ ベ ー ス か ら 取 得 す る ．こ の 統 計 情 報 は ，ユ ー ザ が ク エ リ を 実 行 し た 際 に ， 該 当 の テ ー ブ ル が あ る DBS か ら 取 得 し て 管 理 用 デ ー タ ベ ー ス に 格 納 す る ．一 度 DBS か ら 取 得 す る と ，テ ー ブ ル の デ ー タ が 変 更 さ れ る ま で は 再 度 取 得 し な い ． 分 割 条 件 生 成 の モ ジ ュ ー ル は ， ま ず 実 行 計 画 の 演 算 木 と 統 計 情 報 を 利 用 し て 演 算 毎 の 出 力 デ ー タ の ヒ ス ト グ ラ ム （ 中 間 ヒ ス ト グ ラ ム ） と 出 力 デ ー タ サ イ ズ を 計 算 す る ．演 算 の 入 出 力 デ ー タ の 合 計 サ イ ズ を ，Presto の 利 用 可 能 な メ モ リ サ イ ズ と 比 較 す る こ と で 分 割 の 要 否 を 判 断 す る ． 分 割 を 要 す る 演 算 は ， 入 出 力 デ ー タ の 中 間 ヒ ス ト グ ラ ム か ら 分 割 条 件 を 生 成 し ， そ の 演 算 に 紐 付 け た 形 で 実 行 計 画 に 付 与 す る ． Scan 演 算 は 演 算 木 上 の 直 上 の 演 算 の 分 割 条 件 を 引 き 継 ぐ ． Scan 演 算 の 実 行 時 ， Presto は デ ー タ 取 得 に JDBC の カ ー ソ ル を 利 用 す る ． そ の た め ， DBS の 利 用 可 能 メ モ リ サ イ ズ が Presto よ り 小 さ い 場 合 に ，分 割 範 囲 内 で 取 得 す る デ ー タ サ イ ズ が DBS の 利 用 可 能 な メ モ リ サ イ ズ を 超 え る 可 能 性 が あ る ． こ れ を 回 避 す る た め に ，Presto に 全 取 得 手 法 と Scan 分 割 手 法 の 二 つ を 実 装 す る ．全 取 得 手 法 は ，JDBC の カ ー ソ ル を オ フ に し て 全 デ ー タ を DVS に 蓄 積 す る こ と で 実 現 し ，分 割 条 件 の 生 成 時 に そ の た め の フ ラ グ を 設 定 す る ． も う 一 つ の Scan 分 割 手 法 は ， 直 上 の 演 算 の 分 割 範 囲 内 に お い て ， DBS の 利 用 可 能 な メ モ リ サ イ ズ を 用 い て 更 に 分 割 範 囲 を 計 算 す る ． な お 直 上 の 演 算 が 分 割 実 行 し な い 場 合 は ， Scan 演 算 の 出 力 デ ー タ サ イ ズ と DBS の 利 用 可 能図 3 提案 手 法 のシ ス テム 構 成 図
図 4 Presto に お ける 提案 手 法 の実 装
な メ モ リ サ イ ズ か ら 分 割 要 否 判 定 と 分 割 条 件 の 生 成 を 行 う ．
4.2.2. DVS の 分 割 実 行 手 法 の 実 装
Coordinator で 分 割 条 件 の 生 成 が 完 了 し た 後 ，分 割 条 件 の 有 無 か ら 演 算 毎 の 入 出 力 場 所 （ DBS， メ モ リ ， 一 時 ス ト レ ー ジ ） を 決 定 し ， 各 演 算 に 付 与 す る ． 入 力 場 所 と し て 設 定 さ れ る「 DBS」は ，演 算 の 直 下 が Scan 演 算 の 場 合 に 設 定 さ れ る ． Worker は Coordinator か ら 実 行 計 画 を 受 け 取 っ て 演 算 木 の ル ー ト か ら 各 演 算 の 処 理 を 順 次 開 始 す る ． Presto の ク エ リ 処 理 方 式 は Volcano 方 式 が ベ ー ス の た め ， 分 割 条 件 が あ る 演 算 が Materialized 方 式 の 実 行 と な る よ う に ， 本 実 装 で は 直 下 の 演 算 が 完 了 す る ま で 処 理 を 開 始 し な い ． そ の 直 上 の 演 算 も ， そ の 分 割 実 行 が 全 て 完 了 後 に 処 理 を 開 始 す る ． そ の た め ， 複 数 の 演 算 で 分 割 実 行 が あ る 場 合 ， 最 も 深 い 演 算 か ら 処 理 を 開 始 す る ． 二 項 演 算 の 分 割 実 行 に 関 し て も 同 様 で ， そ れ 以 下 の 演 算 に 分 割 実 行 が あ る 場 合 は ， 左 右 の 両 方 の 演 算 が 完 了 す る ま で 開 始 し な い ． 待 ち 状 態 の 演 算 に お い て 入 力 場 所 が「 DBS」の 場 合 は ，該 当 の Scan 演 算 の 実 行 （ ク エ リ の 投 稿 ） も 行 わ な い ． こ れ に よ り 分 割 実 行 の 演 算 以 外 で メ モ リ を 消 費 せ ず 処 理 で き る ． 分 割 実 行 時 の 入 出 力 場 所 で あ る 一 時 ス ト レ ー ジ に は ，Worker 専 用 の 管 理 用 デ ー タ ベ ー ス を 利 用 す る ．入 力 場 所 が「 一 時 ス ト レ ー ジ 」の 演 算 は ， SQL ク エ リ を 利 用 し て 入 力 デ ー タ を 取 得 す る ． 分 割 実 行 の 場 合 は 分 割 条 件 を 付 与 し て 分 割 実 行 に 必 要 な デ ー タ の み を 取 得 す る ． 入 力 デ ー タ が 格 納 さ れ て い た テ ー ブ ル は ， 入 力 デ ー タ を 全 て 取 得 し た 後 に 削 除 す る ． 出 力 場 所 が 「 一 時 ス ト レ ー ジ 」 の 演 算 は ， 最 初 に 演 算 処 理 結 果 の 出 力 先 テ ー ブ ル を 作 成 す る ． 挿 入 に は INSERT ク エ リ を 発 行 す る ．4.2.3. ク エ リ 分 割 手 法 の 実 装
分 割 条 件 が 付 与 さ れ た Scan 演 算 は ， Worker に て 分 割 ク エ リ を 生 成 す る ．直 上 の 演 算 が 分 割 実 行 の 場 合 は ， 一 回 の 分 割 実 行 に つ き ， 一 つ の 分 割 ク エ リ を 実 行 し ， ク エ リ 結 果 を そ の 演 算 に 渡 す ． そ の 演 算 の 分 割 実 行 が 完 了 後 に ， 次 の 分 割 ク エ リ を 実 行 す る ． JDBC の カ ー ソ ル オ フ の フ ラ グ が 立 っ て い る 場 合 は 全 取 得 手 法 で あ り ， JDBC の フ ェ ッ チ サ イ ズ を 0 に 設 定 変 更 し て 分 割 ク エ リ を 実 行 す る ． 一 方 で ， 直 上 の 演 算 の 分 割 条 件 以 外 に 更 に Scan 独 自 の 分 割 範 囲 が あ る 場 合 は Scan 分 割 手 法 で あ り ， DBS か ら 取 得 す る ク エ リ を 更 に そ の 範 囲 で 分 割 し て 実 行 す る ． こ の 場 合 ， 直 上 の 演 算 は ， そ の 分 割 範 囲 内 に あ る 複 数 の 分 割 ク エ リ が 実 行 完 了 し て か ら ， 演 算 処 理 を 開 始 す る ． 通 常 の 分 割 ク エ リ は ， 直 上 の 演 算 の 分 割 実 行 完 了 後 に 次 の 分 割 ク エ リ を 実 行 す る が ， Scan 独 自 の 分 割 ク エ リ に 限 り ， そ れ ぞ れ 実 行 完 了 後 に す ぐ 次 の 分 割 ク エ リ を 実 行 す る ． ま た ，Scan 演 算 に 分 割 条 件 が あ り ，直 上 の 演 算 が 分 割 実 行 で は な い 場 合 も 同 様 に ， 一 つ の 分 割 ク エ リ が 実 行 完 了 後 ， す ぐ に 次 の 分 割 ク エ リ を 実 行 す る ．5. 評 価
5.1. 評 価 目 的
本 評 価 で は ，提 案 手 法 を 実 装 し た Presto を 利 用 し て 提 案 手 法 の 有 効 性 を 評 価 す る ． 提 案 手 法 は ， 従 来 の Presto で は 実 行 で き な い 規 模 の ク エ リ の 実 行 が 可 能 と な る ． そ こ で ， 従 来 の Presto が ク エ リ 実 行 を 失 敗 す る 環 境 に お い て ， そ の ク エ リ 実 行 時 の 動 作 を 評 価 す る ． ま た ，Scan 演 算 に お け る 二 つ の 分 割 ク エ リ の 生 成 手 法 で あ る 全 取 得 手 法 と Scan 分 割 手 法 の そ れ ぞ れ の 実 装 の 違 い を 明 確 に す る ． 更 に ， 利 用 可 能 な メ モ リ サ イ ズ を 超 え た 場 合 と そ う で な い 場 合 と の 動 作 の 違 い と し て ， 一 時 ス ト レ ー ジ の 利 用 に お け る 性 能 の 影 響 を 評 価 し ， 提 案 手 法 の 性 能 を 分 析 す る ．5.2. 評 価 環 境
評 価 の た め に ， ク エ リ プ ッ シ ュ ダ ウ ン を 実 装 し た 従 来 の Presto （ Original） と 提 案 手 法 を 実 装 し た Presto （ Proposal）を 1 台 の サ ー バ（ DVS）に 構 築 し た ．な お ， 両 Presto の Worker 及 び Coordinator は 同 一 の サ ー バ に 構 築 し て い る ． デ ー タ 仮 想 化 の 対 象 DS は 2 台 構 成 （ PG1, PG2 ） と し , そ れ ぞ れ の サ ー バ に PostgreSQL （ 9.4.0 ） [15] を 構 築 し た ． 3 台 の サ ー バ は Dell PowerEdge R410 で あ り ， 仕 様 は CPU: Xeon X5675 (3.06GHz , 6 Cores) x 2, Memory: 96GB, SAS-HDD: 1TB x 4 (RAID 1), NIC: 1000Base -T で あ る ． 3 台 の ネ ッ ト ワ ー ク は 1GbitEthernet で 構 築 し た ．導 入 ソ フ ト ウ ェ ア は 3 台 共 に CentOS 6.6 と Java 1.8.0 で あ る ． 各 サ ー バ の 利 用 可 能 な メ モ リ サ イ ズ は ， 評 価 の 簡 易 化 の た め に 物 理 メ モ リ サ イ ズ よ り 小 さ く し ， Presto の あ る サ ー バ を 2GB に ， 各 DS を 1GB に 設 定 し た ． 評 価 用 の ク エ リ と デ ー タ は TPC-H[16]を 利 用 し た ． 本 評 価 で 利 用 し た ク エ リ は ，TPC-H で 提 供 さ れ て い る サ ン プ ル ク エ リ の 内 ， 特 に 利 用 メ モ リ サ イ ズ が 大 き い Q5 と Q9 を 利 用 し た ． 評 価 用 デ ー タ の サ イ ズ は Scale 1（ 約 1GB）と Scale10（ 約 10GB）で あ る ．デ ー タ 配 置 は ，Lineitem テ ー ブ ル を PG1 に 配 置 し ，そ れ 以 外 の テ ー ブ ル を PG2 に 配 置 し た ．5.3. 評 価 結 果
Original と Proposal に て ， TPC-H の ク エ リ Q5 と Q9 を 実 行 し た ．図 5 (a)は TPC-H の Scale 1 の デ ー タ に 対 し て ク エ リ を 3 回 実 行 し た 結 果 の 平 均 実 行 時 間 で あ り ， 図 5 (b)は Scale 10 の デ ー タ で 同 様 に 実 行 し た 結 果 で あ る ． な お ， Proposal は ， 分 割 ク エ リ の 生 成 手 法 別 に 全 取 得 手 法 （ cursor off） と Scan 分 割 手 法 （ split scan） で そ れ ぞ れ 実 行 し た ．Scale 1 で は ， Original で も 実 行 可 能 な デ ー タ サ イ ズ で あ り ， Proposal に お い て も 分 割 実 行 が 発 生 し て い な い ． そ の た め ， 少 し 誤 差 は あ る も の の ， 各 手 法 が 横 並 び の 結 果 と な っ た ． Scale 10 で は ， 累 計 10GB の デ ー タ で あ り ， Original で は 実 行 で き ず ， Proposal は 提 案 手 法 に よ っ て 実 行 可 能 と な る こ と を 確 認 し た ．Q5 に 関 し て は ，演 算 の 分 割 実 行 は 発 生 し て い な い が ，PG1 で 実 行 す る Lineitem 取 得 の ク エ リ が 1GB を 超 え た ．そ の た め ，全 取 得 手 法 で は カ ー ソ ル を オ フ に し ，Scan 分 割 手 法 で は 分 割 ク エ リ を 2 つ 生 成 し た ．Q9 は ，Lineitem と Part の 結 合 演 算 が 2 分 割 さ れ ， 更 に PG1 へ の Lineitem 取 得 の ク エ リ が 1GB を 超 え て Q5 と 同 様 の 挙 動 と な っ た ． 従 っ て Scan 分 割 手 法 で は ，Lineitem 取 得 の 分 割 ク エ リ が 3 つ ，Part 取 得 の 分 割 ク エ リ が 2 つ 生 成 さ れ た ．
5.4. 考 察
図 5 (b)に お け る 二 つ の 分 割 ク エ リ 手 法 を 比 較 す る と ， 性 能 面 で 全 取 得 手 法 が 優 れ て い る こ と が わ か る ． こ の 二 つ の 手 法 の 大 き な 違 い は 分 割 ク エ リ の 数 で あ り ， こ の 影 響 が 性 能 の 差 を 生 ん で い る と 考 え ら れ る ． こ れ を 検 証 す る た め に ，Scale 10 の Q9 に お け る 実 行 時 間 の 内 訳 を 図 6 に 示 す ． split query は 分 割 ク エ リ の 実 行 待 ち 時 間 で ， storage write は 演 算 の 分 割 実 行 に お け る 一 時 ス ト レ ー ジ へ の 書 き 込 み ，storage read は 同 様 に 一 時 ス ト レ ー ジ か ら の 読 み 込 み ，etc.は そ れ ら を 除 く 従 来 手 法 の 処 理 （ 分 割 ク エ リ で な い ク エ リ の 実 行 待 ち や ，Presto 上 の 演 算 処 理 等 ）で あ る ．こ の 図 か ら ，Scan 分 割 手 法 が split query で 多 く の 時 間 を 要 し て い る こ と が わ か る ． 分 割 ク エ リ は 分 割 基 準 属 性 に イ ン デ ッ ク ス の な い 属 性 を 選 択 す る と 全 件 探 索 す る た め ， こ の よ う に 分 割 ク エ リ の 数 の 差 が 顕 著 と な る ． 上 記 の こ と か ら ， 性 能 面 で は カ ー ソ ル を オ フ に し た 全 取 得 手 法 が 優 れ て い る と 言 え る ． 一 方 で リ ソ ー ス 利 用 量 の 観 点 で は ，Scan 演 算 に お い て ペ ー ジ 単 位 の デ ー タ を 保 持 す る Scan 分 割 手 法 と 比 較 す る と ，全 取 得 手 法 は 一 度 全 て の デ ー タ を DVS で 保 持 す る 必 要 が あ り ，メ モ リ の 利 用 効 率 が 悪 い ． 提 案 手 法 で は 全 取 得 手 法 を 前 提 に 演 算 の 入 出 力 サ イ ズ の 合 計 か ら 分 割 条 件 を 計 算 し て い る が ，Scan 分 割 手 法 を 前 提 に 計 算 式 を 再 考 す る こ と で ，DVS 上 で よ り 多 く の デ ー タ を 演 算 処 理 可 能 と な り ， 分 割 数 を 削 減 で き る と 考 え ら れ る ． 次 に ，図 6 の 実 行 時 間 の 内 訳 の う ち ，提 案 手 法 の 分 割 実 行 に よ っ て 生 じ る 処 理 を 分 析 す る ．etc.以 外 の 三 つ の 部 分 は 全 て 分 割 実 行 に よ る オ ー バ ヘ ッ ド で あ る ． こ こ で は ， 一 時 ス ト レ ー ジ の 読 み 書 き に 着 目 す る ． 読 み 込 み（ storage read）に 関 し て は ，全 体 の 約 3%と 小 さ い が ，書 き 込 み（ storage write）が 全 体 の 約 25%と 大 き く ， ボ ト ル ネ ッ ク と な っ て い る こ と が わ か る ． つ ま り 提 案 手 法 の 高 速 化 の た め に は ， 一 時 ス ト レ ー ジ へ の 書 き 込 み の チ ュ ー ニ ン グ が 重 要 と な る ． 現 状 ， 一 時 ス ト レ ー ジ と し て PostgreSQL を 利 用 し ，挿 入 に INSERT コ マ ン ド を 利 用 し て い る ． 本 実 装 の 性 能 向 上 と い う 観 点 で は ， PostgreSQL の チ ュ ー ニ ン グ や ， 高 速 な 挿 入 ツ ー ル （ pg_bulkload 等 ）の 利 用 等 に よ っ て ボ ト ル ネ ッ ク を 軽 減 で き る と 考 え ら れ る ．6. お わ り に
本 論 文 で は ， デ ー タ 仮 想 化 に お い て ， 物 理 メ モ リ サ イ ズ を 超 え る 大 規 模 デ ー タ の ク エ リ 処 理 性 能 が 劇 的 に図 5 TPC-H に よ る従 来手 法 と 提案 手 法 の
実 行 時 間 比 較
(a)
Scale 1
(b)
Scale 10
図 6 Scale 10 の Q9 にお け る 実行 時 間
の 内 訳
劣 化 し ， 最 悪 の 場 合 に は ク エ リ 実 行 が 失 敗 す る 課 題 を 解 決 す る た め に ，ク エ リ 分 割 手 法 及 び DVS の 分 割 実 行 手 法 を 提 案 し た ．ク エ リ 分 割 手 法 に よ り ，DS か ら デ ー タ を 分 割 取 得 す る こ と が 可 能 と な り ， DVS と DS の デ ー タ 通 信 時 の 課 題 を 解 決 し た ．更 に ，DVS の 分 割 実 行 手 法 に よ っ て DVS の ス ト レ ー ジ を 利 用 し て ，演 算 木 の 各 演 算 を 分 割 実 行 す る こ と が 可 能 と な り ，DVS の ク エ リ 処 理 時 の 課 題 を 解 決 し た ． 提 案 手 法 の 有 効 性 を 確 認 す る た め に ， 提 案 手 法 を Presto へ 追 加 実 装 し ，TPC-H を 用 い て 評 価 を 実 施 し た ． そ の 結 果 ， 従 来 手 法 で は 実 行 で き な い 規 模 の ク エ リ に 対 し て 有 効 に 働 き ， ク エ リ を 確 実 に 実 行 可 能 で あ る こ と を 示 し た ． 今 後 の 課 題 は ， 物 理 メ モ リ を 超 え る 大 規 模 デ ー タ に 対 し て 評 価 実 験 す る こ と で 提 案 手 法 の 有 効 性 を 検 証 す る こ と で あ る ． ま た ， 本 論 文 に お け る 提 案 手 法 の 実 装 は Volcano 方 式 ベ ー ス で あ り ， Morsel 方 式 の よ う に オ ペ レ ー タ が 並 列 実 行 さ れ る 場 合 に お い て も 同 様 に 有 効 で あ る こ と を 検 証 し た い ．
参 考 文 献
[1] Rick F. van der Lans, Data Virtualization for Business Intelligence Systems, Morgan Kaufmann (2012). [2] Presto, https://prestodb.io/. [3] 齋 藤 和 広 ， 米 田 信 之 ， 渡 辺 泰 之 ， 村 松 茂 樹 ， 小 林 亜 令 ，デ ー タ 仮 想 化 シ ス テ ム に お け る 効 率 的 な ク エ リ プ ッ シ ュ ダ ウ ン の 実 装 と 評 価 , 情 報 処 理 学 会 研 究 報 告 , Vol. 2015-DBS-162，No.25, pp.1-6 (2015). [4] 米 田 信 之 ， 米 川 慧 ， 齋 藤 和 広 ， 渡 辺 泰 之 ， 村 松 茂 樹 ，小 林 亜 令 ，デ ー タ 仮 想 化 に お け る 効 率 的 な ク エ リ 処 理 の 実 装 と 評 価 , DEIM2016.
[5] S. Idreos, et al., MonetDB: Two Decades of Research in Column-oriented Database Architectures , IEEE Data Engineering Bulletin, vol. 35, No. 1, pp. 40-45 (2012).
[6] G. Graefe, Volcano-an extensible and parallel query evaluation system, IEEE Trans. Knowledge Data Engineering, vol. 6, no. 1, pp. 120 –135 (1994). [7] V. Leis, et al., Morsel-driven parallelism: a
NUMA-aware query evaluation framework for the many-core age, In Proceedings of SIGMOD, pp. 743-754 (2014). [8] S. Fiore, et al., Data Virtualization in Grid Environments through the GRelC Data Access and Integration Service, In Proceedings of ICITST, pp. 1– 6 (2009).
[9] M. Salloum, et al., Online Ordering of Overlapping Data Sources, PVLDB, Vol. 7, No. 3, pp. 133-144 (2013).
[10] S. Nural, et al., Query Decomposition and Proc essing in Multidatabase Systems, In Proceedings of Object Oriented Database Symposium of the 3rd European Joint Conference on Engineering Systems Design and Analysis, pp. 41-52 (1996).
[11] Teiid: JBoss Project, http://teiid.jboss.org/
[12] Apache Drill, https://drill.apache.org/.
[13] 齋 藤 和 広 ， 渡 辺 泰 之 ， 村 松 茂 樹 ， 小 林 亜 令 , ヒ ス
ト グ ラ ム を 利 用 し た SQL ク エ リ の 分 割 範 囲 計 算 手 法 の 提 案 , 情 報 処 理 学 会 第 77 回 全 国 大 会 大 会 講 演 論 文 集 第 1 分 冊 ， pp.497-498 (2015).
[14] N. Bruno and S. Chaudhuri, Exploiting Statistics on Query Expressions for Optimization, in Proceedings of SIGMOD, pp.263-274 (2002).
[15] PostgreSQL, http://www.postgresql.org/
