DEIM Forum 2019 H3-3

RDB の実行計画における共通部分プラン木を用いたクエリ最適化
渡佑也†

細谷 柚子†† 日本電信電話株式会社 サービスイノベーション総合研究所 ソフトウェアイノベーションセンタ
〒 108–8019 東京都港区港南 1-9-1 NTT 品川 TWINS ビル 11F
E-mail: †{yuuya.watari.eg,yuzuko.hosoya.gp}@hco.ntt.co.jp
あらまし 本論文では，リレーショナルデータベース（Relational DataBase, RDB）において従前より研究されている最適化手法の一つである複数クエリ最適化について，それを実際の RDB に実装し評価することを通じて，実用化に当たっての課題点を明らかにする．企業活動をはじめとする様々な場面では多くのデータが生成され，それらを分析するための基盤としてデータウェアハウス（Data WareHouse, DWH）が存在する．DWH におけるクエリでは大規模なファクト表に対する結合演算が多用され，その処理時間は長いものとなる．このことは，分析者の迅速な意思決定を阻害することに繋がる．これまで，クエリ間に共通する演算の実行を一度だけ行い，その結果を再利用する手法が提案されてきた．しかしながら，このような手法は今日の主要な RDB には実装されていない．本論文では，複数クエリ最適化を PostgreSQL 上に実装し，DWH のワークロードを代表する TPC-DS を通じて評価することで，その効果と課題点を明らかにする．
キーワード リレーショナルデータベース，データウェアハウス，実行計画，共通部分プラン木
する共通部分式を検出する手法を提案した．近年では，Hari-

1 はじめに
企業活動をはじめとする様々な場面では多くのデータが生成され，それらを分析するための基盤としてデータウェアハウス
（Data WareHouse, DWH）[1] が存在する．DWH には複数のシステムから抽出された多数のデータが蓄積され，企業における経営戦略等を決定する際に役立てられる．その過程で発行されるクエリは，複数の分析者によって同時に実行されたり，ス
ケジュール化されたバッチとしてまとめて処理されたりすることがしばしばあるが，これらのクエリは，大量のデータに対する複雑な処理となっていることが多い．したがって，クエリの実行時間は OLTP（OnLine Transaction Processing）などのワークロードに比べて長いものになる傾向にある．近年のデー
タ数の増加がさらにこの傾向を強める可能性があり，それは分析者の迅速な意思決定を阻害することに繋がる．

DWH で用いられるスキーマは，スター・スキーマやスノー
フレーク・スキーマに代表されるような少数のファクト表と多数のディメンション表で構成されるものであることが一般的であり，クエリはこれらの表の間の結合演算によって表現される．
ファクト表は巨大であることから，結合演算の実行コストは大きい．複数のクエリに類似した結合演算が多数存在する場合，
それらを一度だけ実行して，クエリ間で実行結果を共有することで，全体のパフォーマンスを向上できると考えられる．
結合演算に限らず，クエリ上の同一の演算を共有する試みは，リレーショナルデータベース（Relational DataBase, RDB）[2]
においてこれまで多くなされてきた．それらは，複数クエリ
最適化（Multiple Query Optimization）と呼ばれる．Finkel-

stein [3] は，クエリをグラフで表現することでクエリ間に存在

zopoulos ら [4] が QPipe と呼ばれるパイプライン化されたリレーショナルクエリエンジンを提案している．QPipe では，ス
キャンや結合などの演算子ごとに実行エンジンを設ける演算子
中心（operator-centric）の実行エンジンにより，複数のクエリ間で同一の演算を共有しながら実行する．そのため，クエリをバッチの形でまとめて投入せずとも共有が可能であるという利点を備えている．
これらの先行研究では複数クエリ最適化の有効性が示されてきたにも関わらず，今日の主要な RDB への実装には至っていない．そこで本研究では，複数クエリ最適化を実用化する上での課題点を明らかにすることを目的として，新たな複数クエリ
最適化手法を提案する．そして，それを実際の RDB に実装し評価することにより，実用化に当たっての課題点について議論する．提案手法では，実行計画を表すプラン木について，そのハッシュを元にした共通部分プラン木の抽出を行う．ここで，結合演算や選択演算などに出現する条件句には，似通ってはいるもののパラメータなどがわずかに異なる箇所が存在する．本
手法では，このようなパラメータが異なる条件句を包含するように部分プラン木を抽出する．この手法を広く用いられている

RDB の一種である PostgreSQL を拡張する形で実装し，DWHのワークロードを代表する TPC-DS [5] を用いてその性能と課題点を明らかにする．なお，単一クエリ内でも共有可能な部分
プラン木が存在する場合があり，それに対する最適化も含め，本論文では複数クエリ最適化と称することとする．
本論文は以下の通り構成される．2 節では，これまでになされてきたクエリの共通部分式実行に関する関連研究について述べる．3 節では，複数クエリ最適化手法である提案手法の詳細について述べる．そして，4 節では，提案手法を PostgreSQL

上に実装し評価することを通じて，実行速度の向上などについリを例に提案手法の概要を説明する．ここでテーブル t1〜t4 は，て明らかにする．さらに，複数クエリ最適化を実用化する上でカラムとして id と x を持っているものとする．クエリ 1，2 にの課題点について議論する．最後に，5 節では，本論文の結論対応するプラン木を図 1 に示す．このプラン木は，PostgreSQL

を述べ，また，今後の課題と展望についても言及する．

が生成したものである．図 1，および，リスト 1，リスト 2 から容易に分かるように，両クエリにはテーブル t1 と t2 との間

2 関連研究
複数クエリ最適化（Multiple Query Optimization）と呼ばれる最適化の歴史は長く，例えば，Finkelstein ら [3] は 1982 年にこの種の最適化を提案している．Finkelstein らは，クエリをグラフで表現することでクエリ間に存在する共通部分式を検出している．このグラフ中のノードは，対象となるテーブルと条
件句，および射影される列の三種類の情報を持つシンプルなものであり，結合条件がノード間のエッジに相当する．
近年では，Harizopoulos ら [4] が QPipe と呼ばれるパイプラ
イン化されたリレーショナルクエリエンジンを提案している．

QPipe では，スキャンや結合などの演算子ごとに実行エンジンを設ける演算子中心（operator-centric）の実行エンジンによの結合演算が共通で出現する．図 1 において，太枠の橙色で示されている Hash Join ノード以下の部分プラン木が共通プラン
木である．提案手法では，この共通部分を抽出し，それを一度だけ実行することにより，実行時間の高速化を目指す．
ところで，この共通プラン木は，条件句の部分がクエリ 1 では t1.x <= 10，クエリ 2 では t1.x <= 15 とわずかに異なっており，完全に同一ではない．現実世界のクエリでは，このようにプラン木の構造は同じであるが条件句が異なるものは多数存在すると考えられる．そのような状況にも対応するため，提案手法において，条件句の差異はプラン木が同一であるか否かを判定する際に考慮しない．すなわち，条件句が異なっていても同一の部分プラン木として判断する．その代わり，共有実行すり，複数のクエリ間での最適化を実現する．パイプライン化することで，同じデータに再びアクセスしてしまう data sharing

リスト 1: クエリ 1

miss や，同一の演算を二度以上実行してしまう work sharing

SELECT t1.id, t2.x FROM t1, t2 WHERE t1.id = t2.id AND t1.x<= 10
UNION ALL
SELECT ∗ FROM t3;

miss を最小限にとどめる．QPipe の大きな特徴は，パイプラ
イン化された構造を取っているため，クエリをバッチの形でまとめて投入せずとも共有が可能であるという点である．しかし，クエリを解釈して実行計画を生成する段階では実行共有を考慮

リスト 2: クエリ 2

しないため，共有可能性を最大化できない．
この問題について，Roy ら [6] の複数クエリ最適化は，greedy
な戦略により共有実行可能性を高めている．例えば，三つ以上のテーブル間の結合演算には複数の結合順序があるが，より共SELECT ∗ FROM t4
UNION ALL
SELECT t1.id, t2.x FROM t1, t2 WHERE t1.id = t2.id AND t1.x<= 15;

有しやすい実行計画を選択する．これは，ノードが AND ノー
ドと OR ノードの二種類に分類される特殊な有向非巡回グラフ，

AppendAND-OR DAG 表現を用いて実現されている．
Hash Join

一方，これらとは異なるアプローチも存在する．Sapia [7] は，

DWH のような多次元データベースへのアクセスには特徴的な

Seq ScanSeq ScanHasht3

パターンがあることに着目し，OLAP におけるキャッシュのア
ルゴリズムを向上させる手法を提案した．この手法では，マルt1

コフモデルを用いることで将来実行される可能性の高いクエ(x <= 10)

Seq Scant2(i) クエリ1

リを予測する．この手法も，複数クエリ最適化と呼ぶことができる．
これ以外にも，QPipe と類似しているが，パイプライン化さAppend

れたクエリ実行手法 [8] など，複数クエリ最適化に関する多くの研究がなされてきたが，1 節で述べたように実際の RDB へ

Seq Scanの実装には至っていない．

t4

3 複数クエリ最適化手法

Hash Join
Seq Scant1

Hash
Seq Scan(x <= 15)

本節では，複数クエリ最適化を実現するための提案手法について述べる．2 節で述べたとおり，複数クエリ最適化の手法は様々なものが提案されてきたが，本研究では，RDB が生成した
実行計画，すなわちプラン木を変形する手法を新たに提案する．
次のリスト 1 およびリスト 2 に示す非常に簡単な SQL クエ

t2(ii) クエリ2
図 1: クエリ 1，2 のプラン木Hash Join
Seq ScanHash
Seq Scant1

特別に処理する．このシリアライズを用いた共通部分プラン木

Append(x <= 15)の抽出処理は，クエリ中に存在するプランノードの数を N と

CTE ScanSeq ScanCTE1t3(x <= 10)適化を実用化する上で欠かせないものである．分析者は同じよ
うな構造，例えば同じテーブル間の同一条件による結合などをAppend(i) CTE1

3. 2 部分プラン木に含まれる条件句の統合処理
本節の冒頭でも述べた通り，条件句の処理は，複数クエリ最(ii) クエリ1’

t2

して，O(N ) の計算量で実行できる．

繰り返すと考えられる．しかし，結合条件以外の条件が全く同

Seq ScanCTE Scant4

CTE1

じであると想定するのは難しい．例えば，分析対象の時刻を変化させながらクエリを発行することが考えられる．そこで，そ(iii) クエリ2’のような異なる条件句を包含するような新たな条件に統合して共有実行する必要がある．提案手法では，条件の論理和（OR）

図 2: 共通部分プラン木を CTE として導出したクエリ 1’，2’として統合し，これを実現する．

のプラン木

3. 3 共通部分プラン木の選択率を考慮した共有実行可否のる際には，すべての条件句を満たすような新たな条件句（この例では t1.x <= 15）をもって共有実行する．このようにしてプ
ラン木を書き換えたものが図 2 である．共通プラン木は CTE（Common Table Expressions）として導出され，元のクエリは CTE に対するフィルタを伴った CTE スキャンに書き換えられる．クエリ 1 を書き換えたクエリ 1’ では，CTE をスキャンする際に t1.x <= 10 の条件の下でフィルタを行う．
以上が提案手法の概要である．以降では，この提案手法の詳細について述べる．

判断
提案手法では，同一の部分プラン木が出現しても，それをすべて共有実行するわけではない．これは，共有実行がかえって性能劣化に繋がる可能性を避けるためである．共通部分プラン
木の実行結果は，それを必要としているノードがすべて消費しきるまでメモリ上に保持しておかなければならない．DWH のクエリにおいて出現する同一の部分プラン木の多くは結合演算である可能性が高いと予想される．結合演算の対象は，巨大なファクトテーブルに対するものであることが多く，その結合結果もまた巨大なものとなりやすい．条件句の選択率が高い場合

3. 1 複数クエリ間で共通する部分プラン木の高速な抽出に無理に共有実行を試みると，一時的に結果を保持するために

本節冒頭で述べた共通プラン木の抽出については，言うまで利用するメモリを圧迫する恐れがあり，場合によっては，ディも無くこれが大きなオーバーヘッドとなっていては，かえってスクに書き出される可能性がある．こうした状況が頻発すると，クエリの実行時間を増大させてしまうため重要である．提案手

共有実行しない場合に比べて性能が向上しないか，または低下法では，ハッシュを用いた抽出方法により，効率的な抽出を達する恐れがある．提案手法では，RDB が保持する統計情報を成する．

基にした実行結果のサイズの予測を行い，それが閾値を下回る提案手法では，原則としてすべてのプランノードに固有の番場合に限って共有実行を行う．

号を割り当てる．以後，この番号のことをプランノード番号とこの閾値はパフォーマンス上，非常に重要である．その値は，呼ぶことにする．プランノード番号は，そのノードと子孫で構中間結果の保持がメモリを圧迫しない程度に設定すべきである

成される部分プラン木が「同一」であれば，同じ値が割り当て

が，現時点ではユーザが試行錯誤することにより決定することられる．提案手法では，プランノード番号が同じものを共通部を想定している．そのため，利用可能なメモリやディスクの容

分プラン木とみなし CTE として導出することで共有実行する．

量などを基にした算出を行うことが今後の課題である．先行研

ここで，複数の部分プラン木が与えられたとして，何を持っ究では，ディスクへのアクセス速度などのパラメータに基づき，てそれらが「同一」であると判定するかは自明ではない．提案

この閾値を算出している．しかしながら，その背景にある少な

手法では，PostgreSQL 上のプランノード構造に基づき，部分

いメモリ容量と低速なハードディスクドライブ環境に対し，今プラン木を文字列としてシリアライズした上で，文字列と一対

日では，メモリ容量が大幅に向上したほか，ディスクドライブ

一に対応するようにプランノード番号を割り当てることで同一へのアクセスも高速化している．これらを踏まえた新たな算出

性判定を行う．この文字列には，部分プラン木を EXPLAIN コ

方法を考案することが欠かせない．

マンドを用いて出力するときに出現する属性を含ませる．ただし，条件句に相当するフィルタはシリアライズ結果に含めないものとする．フィルタを文字列に含めないと言うことは，条件句が異なっていても同一の部分プラン木であると判定することを意味する．これは，条件句がわずかに異なる部分プラン木も共有可能にするためである．条件句は，3. 2 節で述べる手法で4 評価実験
3 節で提案した複数クエリ最適化手法の性能を評価する四つの実験を行った．これらの実験で用いたデータセットおよびク
エリセットは，DWH のワークロードを代表する TPC-DS [5]である．データセットのスケールファクタは 100 とした．実験

1 では，クエリを一つだけ実行して単一クエリ内での最適化をじる可能性があり，そのような場面に対して提案手法が有効で行い，性能向上を測定した．実験 2，3 では，複数のクエリをあることが判明した．

まとめて実行して実験 1 と同様の測定を行った．実験 2 で使用

一方，これら二つのクエリ以外では顕著な高速化は確認できしたクエリは，条件句などのパラメータが違う同一のクエリでないものの，全体の約 61%のクエリで高速化率が 1 以上となっある．一方，実験 3 では，TPC-DS のクエリセットから無作為た．残りのクエリでも高速化率は 0.95 以上を保ったが，最もに抽出した異なるクエリを用いた．最後に実験 4 では，提案手性能が低下したクエリでは実行時間が約 5.8%増加した．現在

法が実行計画生成に与える性能面での影響について評価するたの手法では共有実行を行うかどうかの判断は，共通プラン木のめ，共通部分プラン木の抽出に要する時間について計測した．

実行結果のサイズが閾値を下回るかどうかで判断している．す実験で使用したマシンは，OS が CentOS 7.3 であり，Xeon

なわち，巨大な部分プラン木の共有実行は回避される一方で，E5-2640（6 コア/12 スレッド）の CPU，および，16GB のメ

非常に小さな部分プラン木も共有実行する．性能が低下したク

インメモリと 500GB の HDD で構成される．提案手法を Post-

エリでは，このような小さな部分プラン木の共有実行が行われ

greSQL 11 上に実装した．

ており，それに伴うオーバーヘッドが大きく現れたと考えられる．DWH のクエリは実行時間が数時間に上るものも存在する

4. 1 実験 1: 単一クエリ内での最適化ため，約 5.8%の増加でも無視できないものになる．複数クエ

複数クエリ最適化が単一のクエリ内で有効かどうかを確認するために，TPC-DS のクエリをそれぞれ実行してその実行時間を計測した．図 3 にその結果を示す．なお，30 分を超えても実行が完了しないクエリや，現時点での実装で正常に処理できな
いクエリは除外されている．図 3 は，横軸がクエリ番号，縦軸が共有実行しないときに対する実行時間の比率，すなわち高速化率を示している．これを見ると，大半のクエリでその値がおリ最適化を実際の RDB に適用する上では，このような問題を解消しなければならない．
こうした克服すべき課題が存在する一方で，提案手法を単一クエリに適用すると，類似した構造を持つクエリでは最大で 7.8倍の顕著な高速化が見られたほか，その他のクエリでも，多くの場合において大きな性能低下は存在しないため，提案手法を単一クエリの実行に適用することには意義があるといえる．

よそ 1 であり，共有実行の有無で実行時間が変化していないことが分かる．一方，顕著に高速化したのは，クエリ 28，および

88 であり，高速化率は，それぞれ 4.02 倍，7.84 倍である．
ここからは，クエリが高速化した理由について考察する．7.8倍の高速化が見られたクエリ 88 をリスト 3 に示す．このクエリは，ある特定の条件を満たす製品について，8 時 30 分から

12 時 30 まで 30 分刻みでその販売数を集計するものである．リ
スト 3 は，エイリアスとして s1 から s8 を持つ八つのサブクエ
リで構成されていることが分かる．なお，紙面の都合上，s1 とs8 以外の六つのサブクエリは省略して表記した．このリスト 3に出現する八つのサブクエリはその構造がほとんど同じであり，
条件句のうち時刻の部分が異なるのみである．提案手法はこの共通する構造を CTE として抽出した結果，テーブルに対するアクセスが大幅に減少して性能向上に繋がったと考えられる．
クエリ 28 もリスト 3 と同様に類似した構造が複数回出現する．このようなクエリは，SQL が機械的に生成されるときに生

クエリ88

8
7
5
クエリ28

4
3
2

better

高速化率

6

1
0

クエリ番号

図 3: 単一クエリ内での最適化によるクエリの高速化率

リスト 3: TPC-DS クエリ 88
select ∗from(select count(∗) h8 30 to 9
from store sales, household demographics , time dim, store
where ss sold time sk = time dim.t time sk
and ss hdemo sk = household demographics.hd demo sk
and ss store sk = s store sk
and time dim.t hour = 8
and time dim.t minute >= 30
and ((household demographics.hd dep count = 3 andhousehold demographics.hd vehicle count<=3+2) or(household demographics.hd dep count = 0 andhousehold demographics.hd vehicle count<=0+2) or(household demographics.hd dep count = 1 andhousehold demographics.hd vehicle count<=1+2))
and store.s store name = ’ese’) s1,(...) s2,(...) s3,(...) s4,(...) s5,(...) s6,(...) s7,(select count(∗) h12 to 12 30
from store sales, household demographics , time dim, store
where ss sold time sk = time dim.t time sk
and ss hdemo sk = household demographics.hd demo sk
and ss store sk = s store sk
and time dim.t hour = 12
and time dim.t minute < 30
and ((household demographics.hd dep count = 3 andhousehold demographics.hd vehicle count<=3+2) or(household demographics.hd dep count = 0 andhousehold demographics.hd vehicle count<=0+2) or(household demographics.hd dep count = 1 andhousehold demographics.hd vehicle count<=1+2))
and store.s store name = ’ese’) s8;

4. 2 実験 2: 同一のクエリが複数実行される場合の最適化

は，ディメンション表に対する結合演算が共通部分プラン木と実験 2 では，異なるパラメータ（条件句など）を持つ同一のして抽出されているものの，その条件句が非常に複雑な構造をクエリがまとめて発行される状況で実験を行った．本実験では，持っている．こうした複雑な条件句を論理和によって統合した

TPC-DS のクエリのうち 31 個のクエリについて，それぞれパ

結果，共通部分プラン木の条件句評価に大きなオーバーヘッド

ラメータを変化させながら五回まとめて実行し，その実行時間が生じ，実行速度の向上が抑えられたと考えられる．この問題を計測した．これらのクエリは，提案手法の現時点での実装がに対処するには，条件句を統合する際に単純に論理和をとるのサポートしているクエリである．なお，PostgreSQL には複数ではなく，より最適化した形に変形することが求められる．

クエリ間で中間結果を共有する仕組みが用意されていないため，以上の議論をまとめる．同一のクエリをパラメータを変化さ

五つのクエリを UNION ALL により結合し，実験 1 と同様の単せながらまとめて実行したところ，最大で 17.3 倍の高速化が一クエリに対する最適化問題に帰着させた上で，共通部分プラ確認された．4.98 倍高速化したクエリでは，大規模なファクト

ン木を CTE として導出して，提案手法を実現した．

表に対する結合演算結果を再利用でき，性能向上が得られた．

なお，本実験では，同一のクエリのみをまとめて実行するた

その一方，条件句の処理に大きなオーバーヘッドが生じたといめ，クエリの実行計画全体が共通部分プラン木となる．このよう理由で高速化が抑えられたクエリが存在したものの，最も低うな状況は，現実世界でのワークロードでは起こりづらいと考い高速化率は 1.60 倍であり，性能低下は存在しなかったといえられるため，抽出する部分プラン木を限定した．具体的には，

える．

テーブルのスキャン（Seq Scan），および結合演算（Hash Join，

Merge Join，Nest Loop）である．集約演算などのより上位のノードの共有実行は，実装されていない．
図 4 に実験結果を示す．横軸がクエリ番号，縦軸が高速化率である．これを見ると，多くのクエリで高速化率が 2 以上となっていることが分かる．特に，クエリ 96 では，高速化率が4.98 倍に達している．本実験では，同一のクエリを 5 回繰り返
したことから，4.98 倍という高速化率は，複数クエリ最適化がほぼ理想的に機能していることを意味する．クエリ 96 は，日時や店舗名などがある特定の値に一致する売上件数を集計するものであり，このクエリで最も実行時間を費やすのは，大規模なファクト表である store sales 表と複数のディメンション表との結合演算である．この結合演算結果は，先に述べた日時や店舗名などによるフィルタにより，368,575 件まで削減された．これは，store sales 表の 287,974,400 件に対して 0.13%と非常に小さく，3. 3 節で述べた選択率を考慮した共有実行が非常に効
果的に働いた例であるといえる．また，実験 1 で大幅な高速化が確認されたクエリ 88 では，複数クエリ間の共有実行により高速化率が 17.3 倍に達した．これらのクエリを含めて 23 個のクエリで高速化率が 3 を超えた．
一方，クエリ 85 では高速化率が 1.95 倍となるなど，いくつかのクエリで高速化率が 2 倍以下にとどまった．クエリ 85 で

4. 3 実験 3: 異なるクエリが複数実行される場合の最適化
実験 3 では，異なる分析を意図したクエリが同時に発行される状況を想定して，TPC-DS のクエリセットから無作為に抽出した相異なる五つのクエリをまとめて実行して，その実行時間を計測した．本実験では，五つのクエリの組（以後，「組」を省略して単にクエリと呼ぶ）を 500 個無作為に抽出して実験に用いた．図 5 にその結果を示す．図 5 の縦軸は提案手法による高速化率を示しており，その率が高いクエリから順に左より並べている．図 5 は棒グラフであり，それぞれの棒はクエリの組に対応するが，数が非常に多いため，棒を識別することはできない．
実験結果をまとめる．クエリの高速化率は最大で 2.1 倍（図5 の最も左）に達し，全体の 68%のクエリで高速化率が 1 以上となった．また，高速化率が 0.95 以上のクエリは全体の 94%である．特に，1.2 倍以上高速化したものは全体の 11%のクエリに上る．このように多くのクエリでは，提案手法は良い結果を示したものの，実験 1 と同様，一部のクエリにおいては性能が低下しており，最大で実行時間が 32%増加したクエリ（図 5の最も右）が存在した．
性能が低下した理由として，部分プラン木の結果行数を誤って推定したことが挙げられる．実行時間が 17%増加したクエリ

2.5
2

6

高速化率

高速化率

7
5
4
3
2

better8

better

17.3倍

1.5
1
0.5

1
0
3

12 15 20 26 28 37 42 49 53 63 79 85 90 93 98
88
96
クエリ番号

図 4: 複数クエリ最適化による高速化率の分布0

クエリ

図 5: 複数クエリ最適化による高速化率の分布

20, 92, 23, 2, 22 の組み合わせでは，二つの共通部分プラン木
果行数の推定値について，実際の行数が 2213 倍小さく見積もられるという大幅な乖離が存在した．そのため，本来は共有実行すべきでない部分についてそれを行ってしまい，性能が低下したと考えられる．
以上をまとめると，複数クエリ最適化はほとんどのクエリに対して有効に働くか，十分許容できる範囲内のオーバーヘッドにとどまるものの，ごく一部のクエリにおいて大幅な性能低下

8抽出に要する時間（ms）

が CTE として抽出された．このうち一つの部分プラン木の結

7
6
5
4
3
2
1
0
1

2

3

4

5

6

7

8

9

10

クエリ数

を招いた．その性能低下は，データベースの統計情報に基づく
実行行数の推定値に誤りがあることによって引き起こされたと

図 6: 共通部分プラン木抽出に要する時間考えられる．この推定値の乖離は，複数クエリ最適化に限らず
とも RDB 全般の文脈において問題となるものであるが，複数クエリ最適化ではその影響が大きなものになるという課題点が明らかとなった．これは，複数クエリ最適化を実用化する上での大きな障壁となり得る．

は，クエリの実行計画を生成する際に計算されるコストを活用し，コストが閾値を超えた場合のみ複数クエリ最適化を有効化することで実現できる．これは，PostgreSQL 11 から導入された JIT（Just-In-Time）コンパイルと同じ戦略である．

この問題に対する改善策としては，クエリの実行途中に推定値を大幅に超える結果が生成された場合，直ちに共有実行を中5 まとめと今後の課題

断することが考えられる．先行研究の多くは，この問題に対処しておらず，これを改善することが実用化に向けた今後の課題であるといえる．
また，実行速度が向上したクエリがごく一部に限られた原因

本論文では，従前より研究されている複数クエリ最適化について，その実用化に向けた課題を明らかにするため，新たな最適化手法を提案し評価を行った．

として，各クエリの実行計画が共有実行を前提にしていないこ

提案手法では，RDB が生成するプラン木に共通する構造がとが挙げられる．提案手法では，クエリごとに独立して生成さ存在することに着目し，それを CTE として抽出し一度だけ実れたプラン木を変形することで，共有実行を実現している．こ

行してその結果を共有する．DWH を代表するベンチマークでこで二つのクエリに共通の結合演算が存在したとして，一方がある TPC-DS を用いて本手法の効果を評価したところ，一部

ハッシュ結合，もう一方がマージ結合として計画されていた場のクエリで最大 17.3 倍の実行時間短縮が確認できた．多くの

合，それらを共有実行することはできない．このような現象がクエリでは，実行速度の差違は認められず，複数クエリ最適化

どの程度発生し，共有実行を妨げていたのかについて，より詳が有効に働かなかったものの，ほとんどの場合において性能低細な調査が必要である．

下は生じないか軽微であった．このことから，複数クエリ最適化を実用化することには，十分な意義があるといえる．しかし4. 4 実験 4: 共通部分プラン木抽出に要する時間

ながら，ごく一部のクエリで実行時間が最大で 32%増加するな提案手法では，RDB（PostgreSQL）によって実行計画が生ど，無視することのできない顕著な性能低下が生じた．これは，成されたのち，そのプラン木に共通する部分がないか探索し，

RDB の統計情報に基づく実行結果のサイズの推定において大必要に応じて CTE として抽出する作業を行う．これは，実行

きな誤差が存在したことが影響していると考えられる．このよ

計画生成（プランニング）におけるオーバーヘッドとなる．本

うな誤差が存在することを前提にした手法の改良が必要である

実験では，まとめるクエリの数を 1〜10 まで変化させながら，ことが判明した．

抽出にかかる時間を計測した．

今後の課題としては，次のものが挙げられる．まず，直前でその結果を図 6 に示す．図 6 より，抽出にかかる所要時間

述べたように RDB が提供する推定値に存在する誤差を考慮しは，対象となるクエリ数に対して概ね線形に増加することが分なければならない．また，多くのクエリにおいて提案手法ではかった．10 クエリをまとめて実行する際の抽出時間は約 7.7 ミ

実行速度が向上しなかった．この原因として，同時実行するクリ秒であり，10 ミリ秒以内に抑えられている．通常，DWH やエリの実行計画が独立して生成されているために，共有実行しOLAP のクエリでは，実行時間が数分から数時間に及ぶものがづらいものに計画されていることが挙げられる．その程度につ多いため，この抽出時間は十分に無視できるといえる．

いて詳細に評価するとともに，共有実行を前提としたクエリのその一方で，RDB は，OLTP（OnLine Transaction Pro-

実行計画生成が求められる．さらに，本研究における評価実験

cessing）の用途で使用されることもあり，そのようなワーク

では，複数クエリ最適化の対象として，同一のクエリを繰り返

ロードでのクエリは非常に小さく実行時間が短いものとなる

す場合と無作為に選択したクエリを同時実行する場合を設定しことがある．こうしたクエリの実行では，数ミリ秒のオーバーたが，これは実際のワークロードに適しているとはいえない．

ヘッドは無視できないものになる．したがって，クエリに応じ

現実世界でのワークロードに即した分析が必要である．

て共通部分プラン木の抽出を無効化しなければならない．これ

文

献[1] Inmon, W. H.: Building the Data Warehouse, John Wiley& Sons, Inc., New York, NY, USA (1992).
[2] Codd, E. F.: A Relational Model of Data for Large Shared
Data Banks, Commun. ACM, Vol. 13, No. 6, pp. 377–387(1970).
[3] Finkelstein, S.: Common Expression Analysis in Database
Applications, Proceedings of the 1982 ACM SIGMOD International Conference on Management of Data, SIGMOD’82, New York, NY, USA, ACM, pp. 235–245 (1982).
[4] Harizopoulos, S., Shkapenyuk, V. and Ailamaki, A.: QPipe:
A Simultaneously Pipelined Relational Query Engine, Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data, SIGMOD ’05, New York,NY, USA, ACM, pp. 383–394 (2005).
[5] Nambiar, R. O. and Poess, M.: The Making of TPCDS, Proceedings of the 32Nd International Conference on
Very Large Data Bases, VLDB ’06, VLDB Endowment, pp.
1049–1058 (2006).
[6] Roy, P., Seshadri, S., Sudarshan, S. and Bhobe, S.: Eﬃcientand Extensible Algorithms for Multi Query Optimization,
Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, SIGMOD ’00, New York,NY, USA, ACM, pp. 249–260 (2000).
[7] Sapia, C.: PROMISE: Predicting Query Behavior to Enable
Predictive Caching Strategies for OLAP Systems, Proceedings of the Second International Conference on Data Warehousing and Knowledge Discovery, DaWaK 2000, London,
UK, UK, Springer-Verlag, pp. 224–233 (2000).
[8] Boncz, P. A., Zukowski, M. and Nes, N.: MonetDB/X100:
Hyper-Pipelining Query Execution., Cidr, Vol. 5, pp. 225–
237 (2005).