DEIM Forum 2023 2a-2-1

局所探索法を用いた高スケールな実体化ビュー選択
乗松 奨真†

伊藤 竜一†

佐々木勇和†

鬼塚真†† 大阪大学大学院情報科学研究科 〒 565–0871 大阪府吹田市山田丘 1-5
E-mail: †{norimatsu.shoma,ito.ryuichi,sasaki,onizuka}@ist.osaka-u.ac.jp
あらまし

クエリ数が膨大なワークロードにおいて高速なクエリ処理のために，実体化ビューの利用が有効である．

実体化する部分クエリの選択が重要となるが，クエリ数が膨大な場合実体化するクエリを整数計画問題として解くことは解の探索空間が膨大であることと扱う変数の数が膨大になるため実行が困難である．本稿では，総利得の高い部
分クエリの近傍は同様に総利得が高い傾向があるという性質を活用して，最適な実体化ビュー選択の問題を局所探索法を用いて解決する．これは総利得の高い部分クエリの近傍は同様に総利得が高い傾向があるためである．有効な局所探索法のためには，適切な初期解を設定して局所解に陥らないようにするため，ワークロードのおける様々な統計
情報の top-k を初期解として利用する．初期解選択後，近傍探索により解候補を改善し，新たな解候補に対し整数計
画問題を解き，得られた解に対して再び近傍探索を行うという処理を繰り返すことで最適解へと漸近する．実験では小規模な Join Order Benchmark と大規模な天文台データベースでの実験により，既存技術である BIGSUBS の問題
点を明確にすると共に，提案手法の有効性を示した
キーワード 問い合わせ処理，データベース技術，実体化ビュー
ストレージ容量制約を使い切り利得を最大化する解から離れ

1 はじめに
近年データベースシステムに対して多くのユーザが存在し，大量のクエリが実行されている [1] [2]．そして，これらのクエリの処理速度を向上させることが大きな問題となっている．
本稿では，この問題を解決するたため大量クエリ処理には多くの共通した処理が含まれているという特徴 [3] [4] を利用したクエリ処理高速化の課題に取り組む．この共通したクエリ処理の結果を実体化ビューとして保持し，実体化ビューを再利用することで，高速な検索クエリ処理を実現できるようにな
る [3] [4]．しかし，テーブルに対して更新が行われると，そのテーブルに関するクエリ処理の結果が変わってしまうため，クエリによりテーブルが更新された場合は関連する実体化ビューにも更新する必要があり，関連する実体化ビューが多い場合はその処理に時間がかかる．また，実体化ビューはクエリの処理
結果を物理的に保存するため，容量を要する．よって，実体化
ビューの保存容量をどれほど許容するかを示すストレージ容量制約が必要となる．これらのトレードオフや制限を考慮しつ
つ，全ての実体化ビュー候補に対し，整数計画問題を解くこと
で最適な実体化ビュー群を解として得ることができる．このような背景のもと，最適な実体化ビューを高速に選択する手法が提案されている [2] [3] [4] [5] [6]．例えば BIGSUBS [2] では，巨大なワークロードを対象としているおり，実体化ビュー選択問
題とクエリが利用する実体化ビューを決定する問題を分けて考えることで，整数計画問題を高速化する．BIGSUBS では，ス
トレージ容量制約を課すことで，実体化ビューの容量が制限されるため，同時に更新性能の過度な劣化を防ぐことができる．
この手法では，利得とストレージ容量制約の両方を考慮し，容量当たりの利得の良い実体化ビューのみを選択できる．しかし，てしまうという問題点が存在する．また，確率を用いた実体化
ビュー選択を行うため，解が振動してしまうという問題点も存在する．本稿では，解の振動の問題と，容量を使い切らない問
題を解決し，実体化ビューによる利得を最大に漸近させる最適化を高速化する手法を提案する．具体的には，メタヒューリス
ティックである局所探索法 [7] を利用することで解の探索を高速化する．実体化ビュー選択問題に対して局所探索法を適用するには，近傍解を適切に決定することおよび初期解の選択方法が技術課題である．近傍解を適切に決定する方法においては，あるサブクエリの包含関係にあるサブクエリを元のサブクエリの近傍であると定義する．そしてクエリワークロードにおいて近傍の関係にあるサブクエリ同士はそれらの利得が類似するという特性を活用する．具体的には，包含関係にある親サブクエリの方が子サブクエリよりもクエリ表現が複雑であるため，実体化することで得られる利得がより大きく，逆に子サブクエリの方がより多くのクエリで利用される可能性が高い．この特性を活用して，局所探索法における近傍解を決定し，解が収束する
まで最適解の探索を実行する．次に初期解の選択方法に関しては，利得が高い解を高速に選択できるように，サブクエリに関する情報を用いて，利得，容量当たりの利得，ワークロード内での頻度がそれぞれ上位のサブクエリを初期解とする 3 つの方法を提案する．実験は提案手法による実体化ビュー選択が高速であること，選択された実体化ビューにより高い利得が得られること，実体化ビューを利用したワークロードが高速であること，局所探索に効果があることを確認するために行った．Join

Order Benchmark [8] のデータベースとワークロードを用いた低スケールな実験と天文台のデータベースとワークロードを用いて高スケールな実験を行った．このベンチマークは結合処理が多く含まれ，整数計画問題で扱う変数が多くなり，最適解を求める時間が多くかかるため，実験に用いるワークロードとしクエリ1て適する．これを用いた実験により，提案手法や最新技術であ𝜎!"#$%&る BIGSUBS [2] の性能を確認する．天文台のデータベースとワークロードは実世界データを用いており，これを用いた実験

クエリ2
𝜋*+,.'!(#𝑠;𝑠<⋈*+,.456'012 $789:3.12⋈*+,..#/012 $ 2*,3.12
𝑠;𝜎'!(#$)販売)
𝜎!"#$%&

𝐸𝑀𝑃

により，実環境での提案手法や BIGSUBS の性能を確認する．

𝐸𝑀𝑃

これらの実験により，BIGSUBS の特徴と問題点を明確にする𝑠%𝜎456'0$)⽇本)

𝐷𝐸𝑃𝑇

𝐶𝑂𝑈𝑁𝑇𝑅𝑌
クエリ4

クエリ3

と共に，提案手法の有効性を示した．

𝜋*+,.'!(#

問題での定式化を説明する．3 節で提案手法の詳細について説明する．4 節で実験について述べる．5 節で関連研究について，

6 節で本稿のまとめ，今後の課題を述べる．

𝜋*+,.456'0𝑠<

本稿の構成は，次の通りである．2 節で事前知識，整数計画𝑠;⋈*+,..#/012 $ 2*,3.12𝑠;⋈*+,.456'012 $789:312

𝜎!"#$%&

𝜎'!(#$)販売)

𝜎!"#$%&𝑠%𝜎456'0$)⽇本)

𝐸𝑀𝑃

𝐷𝐸𝑃𝑇

𝐸𝑀𝑃

𝐶𝑂𝑈𝑁𝑇𝑅𝑌

図1

2 問題定義異なるクエリ間でのサブクエリの重複提案手法では，局所探索を用いて整数計画問題を高速化する．

が高速化される．また，このように複数クエリにまたがって同

整数計画問題で用いられる変数の詳細について 2. 1 節においてじサブクエリが存在するために，実体化ビュー選択問題は複雑

前提知識として説明する．次に，2. 2 節でワークロードにおけになる．

る利得を最大化する最適化問題を解くために用いられる整数計
画問題の定式化を説明する．本稿では，ワークロード W に含まれるクエリ数を n，サブクエリ数を m として，W に含まれるクエリ qi (1 ≤ i ≤ n) 集合を Q，サブクエリ sj (1 ≤ j ≤ m)の集合を S とする．また，クエリの実行プランは木構造で表す

2. 2 整数計画問題を用いた実体化ビュー選択
この節では整数計画問題の定式化について説明する．サブク
エリの処理に対して，事前計算した実体化ビューを利用することで，クエリ処理の時間を削減できる．しかし，ストレージ容量には制限がある場合では，無制限にクエリの実行プラン木にことができる．

含まれるサブクエリを実体化ビューとして保持することはでき

2. 1 事 前 知 識ない．また，多くのクエリ処理の結果が実体化ビューとして保サブクエリの利得: 実体化ビュー選択問題はワークロード全持されていると，更新処理の際，実体化ビュー内の全ての結果

体の実行コストを下げる実体化ビュー群を適切に選択する問題を更新する必要があるため，更新処理の性能が低下する．そこである．この実体化ビューを評価するために利得を用いる．利で，BIGSUBS [2] では，クエリワークロードに含まれる各クエ

得は実体化ビューを利用したクエリと利用しないクエリの実行

リに対して，全てのクエリを実体化できないストレージ容量制

コストの差で計算する．サブクエリの実行コストは，クエリ最約を課すことで実体化ビューの容量を制限し，更新処理性能の適化で用いられる推定実行コストを用いる．BIGSUBS [2] の定低下を抑えている．これらのことを考慮しつつ，実体化ビュー

義に従って利得を以下のように定義する．

を利用することで得られる利得を計算し，ワークロード全体のuij = cost(i) − cost(i|sj )利得を最大化，つまりクエリ応答時間が最も短くなるよう目的(1)関数を定める．実体化ビュー選択問題は以下のように定義され

但し，実体化ビューを利用しないで qi を処理する際のコスト

る．整数計画問題に対する入出力は以下である．

を cost(i)，sj を実体化したビューを利用して qi を処理する際定義 1. 入力:W ，uij ，bj ，xjk ，Bmaxのコストを cost(i|sj ) とする．また，以下の式のようにワーク

uij はクエリ qi で実体化したサブクエリ sj を利用する際の利ロードに含まれる各クエリを qi とし，そのサブクエリ sj を実得，bj はの sj の容量，xjk は sj が sk を包含する場合に 1 を体化することで得られる利得 uij の全クエリにおける和，つまとるバイナリ変数，Bmax が実体化できるサブクエリの上限容

り sj のワークロード全体における総利得を Uj とする．

量である．

Uj =

n
∑

定義 2. 出力: 実体化することでワークロード全体の利得を最
uij

(2)

i=1

大化できるサブクエリ群，得られる合計利得．
実体化ビュー選択問題は整数計画問題を用いて以下のようにサブクエリの重複: ワークロード内の異なるクエリ間で重複したサブクエリが存在する場合がある．図 1 にその例を示す．
サブクエリ s1 がクエリ q1 ，q2 ，q3 ，q4 に包含され，s2 がクエリ

q2 ，q4 に共通し，s3 がクエリ q2 ，q3 に共通している．このような重複したサブクエリを実体化ビューとして保存し，再利用することで複数のクエリが高速化され，ワークロード全体の処理

定式化できる．

maximizen ∑m∑uij · yij(3)

bj · zj ≤ Bmax(4)

i=1 j=1s.t.

m∑

ト: このコストは M V (sserach (A|B)) の構築コストの 1/|B| 倍
である (|B| は B のレコード数)．このコストをcost(remakeM V (ssearch (A|B))) とすると，以下の式となる．
cost(remakeM V (ssearch (A|B))) = cost(sserach (A|B))·1/|B|

j=1

yik +

m
1 ∑

m j=1

yij · xjk ≤ 1∀i ∈ [1, n], k ∈ [1, m]

j̸=k

(5)
yij ≤ zj∀i ∈ [1, n], j ∈ [1, m](6)(3) 式がこの最適化問題の目的関数である．この目的関数はW 全体における実体化ビューの利得を最大化するものである．
(4)∼ (6) 式は最適化を行う際に，満たすべき制約を示している．但し，整数計画問題扱う変数は以下である．zj は sj が実体化される場合に 1 をとるバイナリ変数，yij は qi が実体化さ(7)
総 書 き 込 み コ ス ト: 更 新 ク エ リ で は ，delete，insert とこ の 二 つ の 組 み 合 わ せ で あ る update が 存 在 す る ．この insert コ ス ト と delete コ ス ト を 取 得 す る こ と で 全 ての 更 新 に 対 応 可 能 で あ る が ，本 稿 で は ，insert の み を 想
定 す る ．M V (sserach (A|B)) へ と 更 新 差 分 を 書 き 込 む コ
ス ト を cost(insert(M V (sserach (A|B)))) と す る ．こ の コ ス
ト は B テ ー ブ ル へ の insert コ ス ト (cost(insert(B))) とM V (sserach (A|B)) のカラム数 column(M V (sserach (A|B)))，
B テーブルのカラム数 column(B) を用いて以下の式となる．

れた sj をクエリ処理の際に利用する場合に 1 をとるバイナリ

cost(insert(M V (sserach (A|B))))変数とする．(4) 式は実体化ビューの容量を制限するストレー= cost(insert(B)) · column(M V (sserach (A|B)))/column(B)ジ制約である．この制約はストレージ制約を課している．また，(8)

ストレージ制約により実体化ビューの個数は制限され，デー
タベース更新があった場合の実体化ビュー再作成コストの過度

次に書き込みレコード数 ninsert(M V (sserach (A|B))) は |B| とな増加を防いでいる．(5) 式はサブクエリの利得を重複して評M V (sserach (A|B)) のレコード数 |M V (sserach (A|B))| を用い

価しないための制約である．この制約に関しては 2. 3 節で後∑述する．また，(3) 式で， ni=1 yij が 1 以上となる j の集合をて以下の式となる．

Mj とする．この場合，sk (k ∈ Mj ) の実体化ビューは 1 つ以

ninsert(M V (sserach (A|B))) = |M V (sserach (A|B))|/|B| (9)上利用されている．つまり，bk = 1(∀k ∈ Mj ) とする必要があ

総書き込みコスト cost(ALLinsert(M V (sserach (A|B)))) は in-

る．この制約式が (6) 式である．(3)∼ (6) 式は BIGSUBS [2]sert コストと書き込みレコード数の積である．

や Wide-deep [4] でも同様の整数計画問題が定義されているが，クエリ内に集約演算を含む場合，実体化した際の容量は更新コ

cost(ALLinsert(M V (sserach (A|B))))

ストを適切に表現できないため，更新処理性能の問題を解決す= ninsert(M V (sserach (A|B))) · cost(insert(M V (sserach (A|B)))

ることはできない．この観点から本稿では，ワークロードに更新クエリを含む場合，更新コストを予測し，整数計画問題に組み込む．更新方法は PostgreSQL [9] で開発されているインク
リメンタルビューメンテナンス (IV M ) [10] を想定する．この手法は実テーブルに発生した変化分に応じてデータベースに格納されている実体化ビューの一部分だけを更新するという手法であり，一から再計算する完全リフレッシュと比較して短時(10)以上の変数を用いて Mj は以下の式となる．

Mj = cost(search(B))+ cost(remakeM V (ssearch (A|B)))(11)+ cost(ALLinsert(M V (sserach (A|B))))間で実体化ビューの更新が可能である [11]．本稿では，更新ク

この更新コスト Mj を用いてワークロード内に更新クエリを含

エリは 1 クエリにつき，1 テーブルに対して，1 レコードを更む場合の整数計画問題の目的関数を以下のように定義する．

新するものとする．以下では，A テーブルと B テーブルを用
いて検索を行うサブクエリ sj (sserach (A|B)) の実体化ビューを

maximizen ∑m∑

M V (sserach (A|B)) とする．B テーブルが B + dB へと更新され，M V (sserach (A|B)) が M V (sserach (A|B + dB)) となる場
合のコスト Mj を考える．この際 IVM による更新コスト評価
において，考慮するものは以下の 3 つである．

uij · yij − zj · Mj /n(12)

i=1 j=1

2. 3 重複評価制約
一つのクエリに対して実体化ビューの利得を複数重複して評価しないために，ある実体化ビューをクエリ処理において利用実体化ビューにおける更新対象レコードを特定するコスト:

する場合には，その実体化されたサブクエリが包含するサブク

このコストは B テーブルから更新対象を見つけるコストと等エリの実体化ビューが同じクエリ処理において利用されないよ∗

主キ

うにする必要がある．上記のようにクエリが利用する実体化

ー = 1) のコストとなる．このコストを cost(search(B)) とビューによる利得を適切に評価するための制限式が (5) 式であ価であるため，クエリ (select

f rom

B

where

する．
実体化ビューを更新する際に必要な実体化ビュー再処理コスる．(5) 式の制限を設けず式 (3)∼(6) の整数計画問題を解く場
合サブクエリの利得を重複して評価する場合があるが，これはクエリ

実体化ビュー
作成用
ワークロード実体化ビュー選択

実体化ビュー
定義

定義データ

れたビューの定義情報を用いて実体化ビューを作成するクエリ実装部分を発行し，このクエリをデータベース上で実行することで実体実体化ビュー作成機構

化ビューを作成する．そして，データベース上で実行したいク
エリを，実体化ビューの定義情報を用いて実体化ビューを利用するように書き換える．このクエリをデータベース上で実行

クエリ

クエリ書き換え機構

実体化ビューを利用するクエリすることで，実体化ビューを利用する高速なクエリ実行が可能となる．本稿において実装した部分は，提案手法である実体化
ビュー選択部分，実体化ビュー作成機構，クエリ書き換え機構

図2

実体化ビュー利用までの流れである．本章では，提案手法における実体化ビュー選択手法についてその概要を 3. 1 節，詳細を 3. 2 節で説明し，3. 3 節で実適切な評価ではない．このような適切でない評価を防ぐため，

yik が 1，つまり qi が実体化された sk を利用する場合，qi が skが包含する他のサブクエリを利用できない制限を設ける．sk が包含する全ての他のサブクエリが qi によって利用されているか否かは yij · xjk によって表される．yik が 1 の場合は，yij · xjk
は全て 0 である必要がある．yik が 0 の場合は，yij · xjk は自由に選択できる．例えば，図 1 において，s1 と s3 を実体化する場合を考える．q2 において，s3 が s1 を包含しているため，

q2 において削減できるコストは s3 のコストのみである．ここでクエリ q2 での利得は s1 ，s3 の利得を合計したものとすると，重複して利得を評価することになり，過剰な利得が得られてしまう．ここで，(5) の制限式を設けることにより，s3 のみの利得として評価することができる．

体化ビュー作成とクエリ書き換えについて説明する．

3. 1 実体化ビュー選択手法の概要
提案手法は，メタヒューリスティックな手法である局所探索法 [7] による考慮する変数削減と整数計画問題を用いて，得られる解をワークロード高速化に最も寄与する実体化ビュー群である最適解に漸近する手法である．ここで実体化ビュー選択問
題における解は実体化対象となるサブクエリ群である．以降，
局所探索法を用いて最適な実体化ビューを選択するアルゴリズ
ムの概要を説明する．まず sj の総利得 Uj ，容量当たりの総利
得 Ej ，W 内に出現するサブクエリ sj の頻度 Fj を算出し全サブクエリの中から上位 k 件 (top − k) を選択し，bj の総和がBmax を満たすまで初期解として選択する．その後初期解の近傍に解候補を広げ，得られた解候補に対して整数計画問題を解

2. 4 局所探索法
提案手法は局所探索法を用いて実体化ビュー選択を高速化す

くことにより解を決定する．この解の決定が局所探索法における近傍解の入れ替えである．ここでサブクエリ si の近傍クエ

るが，本節では一般的な局所探索方法 [7] について説明する．局

リ neighbors(si ) を，si を含む親サブクエリおよび si に含ま

所探索法は近似アルゴリズムの中での最も単純なアルゴリズムれる子サブクエリの和集合として，以下のように定義する．

の枠組みの 1 つで，良質な近似解を求めることを主な目的としている．このアルゴリズムは以下のように実装される．

1. 解を 1 つランダムに生成する．
2. 現在の解の近傍の内 1 つをある条件で選び近傍解とする．
3. 定義した条件を満たすなら近傍解と現在の解を入れ替える．
4. 終了条件を満たすまで 2 以下を繰り返す．

定義 3. 近傍クエリ: サブクエリ si に対して，si を含む親サブ
クエリおよび si に含まれる子サブクエリの和集合として定義される．ただし，木構造における直接の親子関係以外の推移的な包含関係は考慮しないこととする．

neighbors(si ) := parents(si ) ∪ children(si )(13)

このアルゴリズムにおいて定義するべきパラメータは以下の 4
つである．

•

近傍の定義

•

近傍解を選ぶ条件•

近傍解と現在の解を入れ替える条件

•

終了条件

この局所探索法の提案手法への適用方法や，提案手法におけるパラメータの定義は 3 章にて詳しく説明する．

但し，parents は引数 si の親サブクエリ群を全クエリ群から探索して返す関数であり，children は引数の子サブクエリ群を返す関数である．以降，近傍を解候補として整数計画問題により解を求める処理を繰り返すことで，最適解を探索する．終了
条件は実体化ビューにより得られる利得が改善しなくなる場合とする．局所探索法を利用することで，提案手法の整数計画問
題は (3)∼(6) 式と比較して，解候補が削減されるため処理する
変数が削減される．つまり，全ての式において解候補であるサ

3 提案手法ブクエリ sj の探索範囲が狭まり，解候補に含まれるサブクエ
リのみを扱えば良くなる．t 回目の反復において整数計画問題

ワークロードの情報を用いて，実体化ビューをデータベース
上に作成し，この実体化ビューを用いてクエリをデータベース
上で実行する実際の流れは図 2 の通りである．まず，ワーク
ロードの情報を用いて実体化ビュー選択技術により，実体化するサブクエリを決定する．その後，実体化ビューとして選択さで扱う解候補群を Bt (t ≦ 反復回数) とすると，以下のように定式化される．

maximizen ∑∑が膨大となるため，整数計画問題の処理時間が長くなるという

uij · yij

(14)

bj · zj ≤ Bmax

(15)

i=1 j∈Bt

s.t.

∑

j∈Bt

yik +

m
∑

1
yij · xjk ≤ 1
m j∈B

3. 2. 2 近傍探索による解候補の列挙
クエリの木構造において，子サブクエリの方がクエリ表現が簡略であるため，親サブクエリよりワークロード内での出現頻∀i ∈ [1, n], k ∈ [1, m]

t

度が高い．また，同様に親サブクエリの方がクエリ処理が複雑であるため，子サブクエリよりクエリ内での利得が高い．このj̸=kyij ≤ zj

問題点がある．

∀i ∈ [1, n], j ∈ Bt

(16)

ような理由から，解候補となっているワークロード全体におけ(17)る総利得の高いサブクエリの近傍クエリもまた総利得が高いと推測して解候補に追加する．

全ての式においてサブクエリ j の範囲が解候補群 Bt 内に含ま3. 2. 3 整数計画問題の繰り返しによる最適解の探索れる j に限定される．また，ワークロード内に更新クエリを含提案手法では，整数計画問題と解候補の探索を反復する．以む場合の整数計画問題は以下のように定式化される．

maximizen ∑∑uij · yij − zj · Mj /n

下の式のように解候補 Bt (t = 0 · · · 反復回数) は一つ前の反復(18)における解 Ct−1 に対して近傍探索をおこなうことで得られる．

i=1 j∈Bts.t.

∑

Bt = Ct ∪bj · zj ≤ Bmax
1 ∑yij · xjk ≤ 1
m j∈B∀i ∈ [1, n], k ∈ [1, m]

Ct (t > 0) の場合は，以下の式によって，解候補 Bt に対し整数計画問題を解くことで得られる解であると定義する．

t

j̸=k

(20)
yij ≤ zj

(23)

但し，C0 は 3. 2. 1 節に示した方法で得られる初期解群とする．

m

yik +

neighbors(ct )ct ∈Ct

(19)

j∈Bt

∪

∀i ∈ [1, n], j ∈ Bt

Ct+1 = ILP (Bt )

(24)

(21)
ここで ILP は解候補に対して整数計画問題を解く関数である．

3. 2 実体化ビュー選択手法の詳細

この反復は得られた解の実体化ビューにより得られる総利得が3. 2. 1 初期解の列挙

改善しなくなった場合に終了とする．この手法では整数計画問

近傍探索では局所解に陥る可能性があるが，これを初期解の題の目的関数の値は必ず収束する．その理由は，整数計画問題

選択によって解決している．図??のようにワークロードに含まに与えられる変数は必ず，1 つ前の反復において得られた解をれるクエリの統計情報であるサブクエリの利得，頻度，容量を含んでいるためである．このため，1 つ前の反復における整数計

用いて初期解を決定する．この初期解選択方法として 3 つ列挙

画問題の目的関数と比較して，同じ値か，良い値を取ることとする．

なる．この同じ値を取った時にアルゴリズムを終了としている．

topk-U: 実体化ビューの利得が高い順に k 個を列挙する手法である．この手法では単純に，利得の高いサブクエリを選択

3. 3 実体化ビューの作成，クエリ書き換えするため，最適解に含まれるサブクエリを効率的に探索できる．

本稿では，解として得られた実体化ビューを実際に作成して，ただし，容量が巨大で，非常に効率の悪いサブクエリを選択しその実体化ビューを利用するようクエリ書き換えを行うシステてしまうことが問題点である．

ムを開発した．本システムでは，PostgreSQL [9] の EXPLAIN

topk-E: 実体化ビューの容量当たりの利得が高い順に k 個をコマンドにより出力される実行プラン内のサブクエリ群を実体列挙する手法である．ワークロードに全体における容量当たり化候補とする．しかし，このコマンドの仕様上，いくつかの問の総利得 Ej は以下のように定義される．

題点があったため，工夫を施した．その問題点と工夫について以下に示す．

Ej = Uj /bj(22)

この手法は，topk − U と比較して容量も考慮する手法となっており，topk − U と同様に，最適解に含まれるサブクエリを効率的に探索できる．ただし，容量も考慮するため，容量が巨大であるが多くのクエリに含まれるサブクエリを探索できない可能性があることが問題点である．

topk-F: ワークロードにおける sj の出現頻度が高い順に k個列挙する手法である．topk − F は W での頻度の高い sj が初期解となり，多くのクエリに共通するサブクエリが初期解となることにより，後の近傍探索により広い範囲での探索が行え，得られる解が最適解に漸近しやすくなる．ただし，初期解の数

LIMIT OFFSET 句: PostgreSQL の EXPLAIN コマンド
では，LIMIT OFFSET 句を含むサブクエリは OFFSET で指定される値が異なる場合でも同じ EXPLAIN 結果を返す．しかし，実際には OFFSET の値がずれている分，違うサブクエリ
出力結果を返すことが必要である．EXPLAIN 結果からは違う
サブクエリ出力結果であることが判別できず，実体化ビューとする時に正しい結果とならない．このため LIMIT OFFSET 句を含む場合は 1 から始まる OFFSET のみに限定することした．

Nested Loop Join: Nested Loop Join は繰り返しにより結果を出力する処理であるが，EXPLAIN コマンドではこの部
分の下位のサブクエリは 1 回分しか出力されず，適当なコスト

計算はできない．このため，Nested Loop より下位のサブクエ

マシン

MacBook Pro (Retina，Early 2015)

リは整数計画問題の解候補から外した．

cpu

2.7 GHz dual Intel Core i5

メモリ

8 GB 1867 MHz DDR3

Bitmap Index Scan: Bitmap Index Scan は実行プラン
内で Bitmap を作成することで，処理を高速化する処理である

ILP solver

Gurobi9.1 2が，クエリとして Bitmap を作成することはできない．このた

データベースIMDBめ，Bitmap Index Scan より下位のサブクエリは整数計画問題の解候補から外した．

4 実

データベースサイズ比較を行うことと，実体化ビューの実際の効果を測定するこJOB(109 クエリ)

ワークロード予測実行コスト
表1験

本稿における実験の目的は BIGSUBS [2] と提案手法の性能

7GB

ワークロード

200M

実験 1 環境，データベース，ワークロードマシン

MacBook Pro (Retina，Early 2015)

cpu

2.7 GHz dual Intel Core i5

メモリ

8 GB 1867 MHz DDR3とである．実験で測定する評価指標はアルゴリズム実行時間

ILP solver

Gurobi9.1 3(実行時間)，整数計画問題によって得られる合計利得，実体

データベース天文台

化ビューが使用する容量である．また，実体化ビューの実際

データベースサイズの効果を測定する際には，実体化ビュー作成時間と，実体化

ワークロードビューを利用したワークロード実行時間を測定する．実験でワークロード予測実行コスト

は，Join-Order-Benchmark(JOB) と天文台のワークロードを用いた．このワークロードに関しては 4. 1 節で詳しく説明す

表2

14TB
天文台ワークロード (5000 クエリ)

69G

実験 2 環境，データベース，ワークロード

ワークロード実行マシン

Ubuntu16.04.1，x86˙64 GNU/Linux

ワークロード実行 cpu

2.1GHz Intel(R) Gold6130 CPU*64

では，解候補を削減しないで行う整数計画問題 (N ILP ) によ

ワークロード実行メモリ

1.6TB

る．また，実験はワークロードと目的別に数種類行った．実験
り得られる最適解および BIGSUBS [2] と比較して，提案手法

実体化ビュー選択マシン

MacBook Pro (Retina，Early 2015)の有効性を評価する (実験 1 − 1，2 − 1)．次に，近傍探索の有実体化ビュー選択 cpu

2.7 GHz dual Intel Core i5

効性を評価するために，3 つの初期解に対して整数計画問題を実体化ビュー選択メモリ

8 GB 1867 MHz DDR3

適用した近傍探索を行わない場合との比較を行う (実験 1 − 2

ILP solver

Gurobi9.1 4

データベース天文台，2 − 2)．次に，ワークロード内に更新クエリが存在する場合の実験を行う (実験 1 − 3)．JOB のワークロード内には更新クエリが存在しないため，更新クエリは自作で追加した．最後に，実体化ビューが実際にどの程度の効果をもたらすかを確認する(3 − 1)．但し，BIGSUBS では反復的アルゴリズムで最後に得データベースサイズ
ワークロード

14TB
天文台ワークロード (500 クエリ)

ワークロード予測実行コスト

1.7G

実測ワークロード実行時間

20.54h表3

実験 3 環境，データベース，ワークロードられる結果が最適値とは限らないため，解の探索途中で得られた，最も性能が高い解の結果を掲載した．サブクエリの実行コ

二つ目は，天文台データベース [12] とそこで処理されている

ストには，PostgreSQL の explain コマンドを用いてサブクエ

ワークロードである．このデータベースは実際に天文台で運用リの推定実行コストを用いる．

されているものである．データベース容量は 14T B と高スケー

4. 1 ベンチマーク
本稿では，二つのデータベースとワークロードを用いる．
一つ目は，インターネットムービーデータベース (IMDB)を想定したワークロードである Join-Order-Benchmark (JOB)

ルとなっている．また使用するワークロード内のクエリも実際に発行されているものであるため，提案手法が実環境でも有効であるかを確認することを目的とする．

4. 2 実 験 環 境[8] である．このワークロードは実験用の人工ワークロードであ実験において利用する三つの実験環境およびデータベース，

る．JOB で使用されるデータモデルは，構成するテーブル数がワークロードを表 1，2，3 に示す．各実験がいずれの実験環境

21 と多い．また，ワークロードにはテーブルの結合処理を含むを使用しているかは各実験結果を示す節の最初に記す．ワーク

クエリが多数存在する．よって，整数計画問題によって処理さ

ロード予測実行コストはワークロードに含まれる全てのクエリ

れる決定変数が多くなる．決定変数が多いと整数計画問題を解の予測実行コストの和のことである．

くコストが大きくなるため，本実験を行うワークロードに選択
した 1 ．但し，本ワークロード内では，サブクエリを実体化し

4. 3 実 験 結 果た際の容量で実体化ビューの更新コストを適切に表現するためストレージ容量制約の大小によって実体化ビューに選ばれるにクエリ内の SELECT 句に指定される集約演算を削除した．

サブクエリは変化する．提案手法の有効性のストレージ容量制

1：postgreSQL による cost 予測値，容量予測値が極端に大きいクエリを外し，

4：https://www.postgresql.jp/document/11/html/using-explain.html

109 クエリで実験を行った．

5：http://www.gurobi.com

容量制約:0.1GB

実行時間 (s)合計利得 (M)

使用容量 (%)

485

39.8

99.9

N ILP

容量制約:10GB，更新クエリ数:10

実行時間 (s)合計利得 (M)

使用容量 (%)

559

59.5

99.9

N ILP

(最適値)
BIGSUBS

1.28

最適値との比較 (%)

24.3

3.12

最適値との比較 (%)

37.1

2.88

最適値との比較 (%)

28.0

5.39

最適値との比較 (%)

31.9

3.24

52.9

4.93

54.9

提案手法 (topk − F )実行時間 (s)合計利得 (M)

使用容量 (%)

523

60.1

99.9

表6

9.26

45.3

BIGSUBS

10.87

提案手法 (topk − E)

実験 1 − 2 結果 (容量制約:10GB，更新クエリ数:10)

容量制約:10GB，更新クエリ数:1000

実行時間 (s)合計利得 (M)

使用容量 (%)

469

57.3

99.9

N ILP

提案手法 (topk − U )

8.12
6.05

9.2

BIGSUBS

46.4
56.1

7.61

45.0

3.98

39.6

最適値との比較 (%)
提案手法 (topk − E)

99.9

提案手法 (topk − U )

99.9

1.99

45.6

提案手法 (topk − F )99.9

実験 1 − 1 結果 (容量制約:10GB)

1.20

49.8

約の変化に応じてどのように変化するか確かめるために，ストレージ容量制約である Bmax を変化させて実験を行った．

4. 3. 1 実験 1 − 1: 最適解，BIGSUBS との比較
この実験は N ILP により得られる総利得の最適値，BIG-

99.6

86.8
3.85

38.7

最適値との比較 (%)

表7

95.9

86.8

最適値との比較 (%)

74.9

17.9

69.1

最適値との比較 (%)

93.3

最適値との比較 (%)

表5

54.8

77.2

最適値との比較 (%)
提案手法 (topk − F )

(最適値)

91.2

最適値との比較 (%)

97.7

76.2

(最適値)
最適値との比較 (%)

99.9

92.3

最適値との比較 (%)

実験 1 − 1 結果 (容量制約:0.1GB)

99.9

88.9

最適値との比較 (%)

99.9

41.1

72.3

提案手法 (topk − U )

99.9

80.2

N ILP

43.0

最適値との比較 (%)

70.4

提案手法 (topk − F )4.83

提案手法 (topk − E)

99.9

93.2

提案手法 (topk − U )容量制約:10GBBIGSUBS
最適値との比較 (%)

79.1

提案手法 (topk − E)

表4

31.5

(最適値)

99.4

67.6

実験 1 − 2 結果 (容量制約:10GB，更新クエリ数:1000)
容量制約:10GB

実行時間 (s)合計利得 (G)

使用容量 (%)

BIGSUBS

7021

28.5

39.2

提案手法 (topk − E)

55.0

27.6

98.6

提案手法 (topk − U )

63.0

27.8

96.6

提案手法 (topk − F )

593.1

27.4

99.9

表8

実験 1 − 3 結果 (容量制約:10GB)

SUBS と提案手法により得られる総利得とアルゴリズム実行時
実行時間 (s)合計利得 (G)

使用容量 (%)

BIGSUBS

7564

56.3

39.9

提案手法 (topk − E)

66.9

57.3

72.8

い切っていないことから，最適値には近似できない．上記に対し提案手法 (topk − U )

52.3

57.5

79.0

て提案手法では容量を使い切ることで，どのストレージ制約の提案手法 (topk − F )

789.9

53.1

49.3

間，使用容量を比較するために行った．実験環境は表 1 である．
それぞれの結果を表 4，5 に示す． BIGSUBS は容量制約を使場合でも N ILP により得られる最適値と比べて 75% ∼ 97%程度の精度を達成した．

4. 3. 2 実験 1 − 2: 更新クエリがある場合の最適解，BIGSUBS との比較
この実験はワークロード内に更新クエリが存在する場合の提案手法の有効性を確かめるために行った．ストレージ容量制約
は 10GB で，ワークロード内における検索クエリと更新クエリの比率を変化させた際の結果を確かめた．具体的には 検索 : 更
新 = 109 : 10，検索 : 更新 = 109 : 1000 での 2 つで実験を行った．実験は JOB を用いて行なったが，このワークロードには
更新クエリは存在していないため，更新クエリは手動で作成した．実験環境は表 1 である．それぞれの結果を表 6，7 に示す．
更新クエリ数が増加していくにつれて，最適値への近似が難しくなっていることがわかった．これは最適値へと近似するために実体化するべきサブクエリは多くのテーブルの処理を含まな
い小さなサブクエリを多く含むからであり，BIGSUBS や提案
手法ではこの小さなサブクエリまで探索できていないと考えられる．BIGSUBS と提案手法で比較すると，ワークロードに更新クエリを含む場合でも，アルゴリズム実行時間，合計利得共に，提案手法が優れている傾向にあった．

容量制約:1000GB

表9

実験 1 − 3 結果 (容量制約:1000GB)

4. 3. 3 実験 1 − 3: 高スケールにおける BIGSUBS との比較
この実験は高スケールなデータベース，ワークロードにおいて，N ILP により得られる総利得の最適値，BIGSUBS と提案手法により得られる総利得とアルゴリズム実行時間，使用容量を比較するために行った．つまり，実験 1 − 1(4. 3. 1 節) を
高スケールで行ったものである．天文台データベースを用いる実験では N ILP による最適解は導出していない．これは，天文台データベース，ワークロードは共に高スケールであり，

N ILP で解く場合整数計画問題で扱う変数が膨大となり，短時間で最適解を得ることはできないためである．また，高ス
ケールな実験の場合，BIGSUBS の確率的アルゴリズムによる結果の振動が大きく現れていたために，10 回実験を行い，その平均値を提案手法と比較する．実験環境は表 2 である．提案手法と BIGSUBS の平均の比較結果を表 8，9 に示す． 高スケー
ルな実験では，実行時間に着目すると BIGSUBS と提案手法では大きな差が存在した．提案手法の (topk − E ，topk − U ) にお
いては，BIGSUBS の 1/100 程度の実行時間であった．提案手法の topk − F は他の提案手法 2 に比べて，実行時間が 10 倍程度となっている．これはデータベース，ワークロードが高ス実行時間 (s)合計利得 (M)

使用容量 (%)

実行時間 (s)合計利得 (G)

使用容量 (%)

近傍探索なし (topk − E)

0.01

25.7

99.9

近傍探索なし (topk − E)

13.3

56.6

100

近傍探索なし (topk − U )

0.01

19.2

99.9

近傍探索なし (topk − U )

12.2

56.6

100

近傍探索なし (topk − F )

0.01

11.2

99.9

近傍探索なし (topk − F )

57.6

44.2

100

提案手法 (topk − E)

3.12

37.1

99.9

提案手法 (topk − E)

66.9

57.3

72.8

提案手法 (topk − U )

2.88

28.0

99.9

提案手法 (topk − U )

52.3

57.5

79.0

提案手法 (topk − F )

5.39

31.9

99.9

提案手法 (topk − F )

789

53.1

49.3

容量制約:0.1GB

表 10

容量制約:1000GB

実験 2 − 1 結果 (容量制約:0.1GB)

容量制約:10GB

実験 2 − 2 結果 (容量制約:1000GB)

表 13

実行時間 (s)合計利得 (M)

使用容量 (%)

近傍探索なし (topk − E)

0.03

26.0

99.9

最適化時間 (s)

3.39

14.26

近傍探索なし (topk − U )

0.03

46.5

99.9

利得

1.17G

1.00G

近傍探索なし (topk − F )

0.03

37.7

99.9

実体化ビュー作成時間 (h)

13.11

3.27

提案手法 (topk − E)

8.12

46.4

99.9

実体化ビュー使用時のワークロード実行時間 (h)

7.57

8.77

提案手法 (topk − U )

6.05

56.1

99.9

削減実行時間 (h)

12.98

11.77

提案手法 (topk − F )

7.61

45.0

99.9

表 14

表 11

提案手法 (topk-E)

BIGSUBS実験 3 − 1 結果 (容量制約:100GB)

実験 2 − 1 結果 (容量制約:10GB)

容量制約:10GB

高スケールな環境においても，近傍探索を行うことにより，実行時間 (s)合計利得 (G)

使用容量 (%)

近傍探索なし (topk − E)

10.1

26.0

100

性能改善がされていることを確認できた．特に，容量制約が 10近傍探索なし (topk − U )

8.1

26.0

100

近傍探索なし (topk − F )，100GB の実験においては近傍探索により大きく性能改善が可

54.2

22.1

100

提案手法 (topk − E)

55.0

27.6

98.6

能であった．しかし，容量制約が 1000GB の実験においては他

提案手法 (topk − U )

63.0

27.8

96.6

2 つの容量制約下の実験と比較して改善幅は少なかった．この提案手法 (topk − F )

593

27.4

99.9

容量制約下では近傍探索を行なった場合，指定された容量を使

表 12

実験 2 − 2 結果 (容量制約:10GB)

ケールな場合，頻度の高いサブクエリは多くのクエリ内で共有されていることなり，整数計画問題へと入力される変数が多くなるためだと考えられる．
また，利得に着目すると，容量制約 10GB では BIGSUBSが優位であった．このことから BIGSUBS は高スケールな環境で良い性能を持つことがわかった．しかし，他の容量制約では提案手法が優位であった．高スケールな環境においても提案手法は良い性能を持つことがわかった．BIGSUBS では解が振動することや，利得，実行時間の観点から総合的に見ると，高スケールな環境においても提案手法は BIGSUBS より優位であると言える．

4. 3. 4 実験 2 − 1: 近傍探索の効果確認
この実験は提案手法における近傍探索の有効性を確かめるた
めに行った．初期解のみに整数計画問題を適用した総利得と，近傍探索と整数計画問題を繰り返すことにより得られる総利得を比較する．実験環境は表 2 である．それぞれの結果を表 10，11 に示す． 各近傍探索なし topk と比較して大幅に利得を改善していることから提案手法における局所探索法の有用性が示された．初期解群に注目すると，必ずしも同じ種類の topk が一番良い結果を示すとは限らないことも分かった．このため，適切な top − k を選択する手法，もしくは初期解群選択手法を選択する必要がある．

4. 3. 5 実験 2 − 2: 高スケールにおける近傍探索の効果確認
この実験は高スケールなデータベース，ワークロードにおいて，提案手法における近傍探索の有効性を確かめるために行った．つまり，実験 2 − 1(4. 3. 4 節) を高スケールで行ったもの

い切っていない．このことから，初期解を選択した時点で大量の冗長なサブクエリが選択されており，近傍探索では，初期解にはない少量のサブクエリを探索するのみで，利得の改善が他に比べて少なかったものと考えた．

4. 3. 6 実験 3 − 1: 実体化ビューの実際の効果確認
この実験は，高スケールなデータベースにおいて，提案手法
や BIGSUBS によって選ばれた実体化ビューの効果を実際に測定するために行った．提案手法はこれまでの実験で良い結果を残す傾向にあった topk − E を用いる．両方の手法における最適化時間，予測削減コストと，実体化ビュー作成時間，実体化
ビュー使用時のワークロード実行時間，削減実行時間を測定した．実験環境は表 3 である．実験結果を表 14 に示す．天文台
データベースを用いて，500 クエリで整数計画問題を解いた場
合でも，提案手法が BIGSUBS より高い利得を得ることができた．実体化ビュー作成時間では，BIGSUBS はその容量を使い切らないという特徴から，実体化するサブクエリの数が少なく，短い実体化ビュー作成時間を達成している．BIGSUBS では実体化するサブクエリが少ないにも関わらず，高い利得を得ている．これは BIGSUBS が重複を優先して効率の良いサブクエリを選択しているためだと考えた．実体化ビュー使用時のワーク
ロード実行時間と削減実行時間で見ると，提案手法が利得と同様に良い結果を得ている．ワークロードが複数回実行される環境を想定すれば，実体化ビュー作成時間，実体化ビュー使用時のワークロード実行時間の和を考えても提案手法が有利になるだろう．

5 関連研究である．??節と同様の理由でこの実験では，N ILP による最データベース上のクエリ処理を高速化するために適切な実体

適解は導出していない．実験環境は表 1 である．それぞれの結化ビューを選択する研究が行われており，提案手法と同様に整果をそれぞれの結果を表 12，13 に示す．

数計画問題を用いた手法 [2] [4] が提案されている．

BIGSUBS [2] では二部グラフのラベリング問題を用いること

実験 4. 3. 6 で行なった実験はクエリ数が 500 とまだ拡張の余地

で，整数計画問題を細分化し，確率的なアルゴリズムを導入すがあるものとなっている．このクエリ数に応じて，提案手法，

ることで整数計画問題で扱う変数を削減する．まず，確率的なBIGSUBS の有効性がどのように変化するか確認する必要があ

手法を用いて，実体化するサブクエリに 1，実体化しないサブ

る．提案手法ではクエリの実行プランは QueryOptimizer からクエリに 0 のラベル付けを行う．この確率は，(1) サブクエリ

出力される最適な実行プランしか考慮していない．別の実行プの処理結果を保持するために必要な容量が少ないほど，(2) サ

ランも考慮することでより高い利得が得られると考えられる．

ブクエリを実体化した場合のコスト削減程度が大きいほど，高しかし，入力するサブクエリの個数が増加すると，整数計画問

くなるように定義されている．次に，クエリワークロード内の題に要する時間も増加する．このトレードオフも考慮した実行

クエリが，1 のラベルが付いたどのサブクエリを利用するかをプランの列挙を行いたい．

整数計画問題を利用して決定する．つまり，式 (4) を満たすように zj を確率を用いて決定し，式 (3) の目的関数を (5) と (6)を満たすように qi ごとにそれぞれ整数計画問題を解く．この確率的なラベル付けと整数計画問題を削減コストが向上しなくなるまで繰り返すことで最終的な実体化ビューを決定する．この手法では整数計画問題において，処理される変数の数を大幅に削減しているために整数計画問題の処理時間を低減できる．そのため，この手法は大規模なクエリワークロードに対しても有効な手法とされており，実際に論文内ではこれまでの研究では考慮されていない規模のクエリワークロードに対しても適用可能であるとされている．

Wide-deep [4] は上記の BIGSUBS 改良版とされており，実体化ビュー選択問題について二つの課題を挙げている．一つ目はあるクエリに対して実体化ビューを用いることによって得られる利得をどう評価するか，二つ目は実体化ビューとするサブ
クエリをどう選択するかである．一つ目の解決策としてクエリに対して実体化ビューを利用した利得を推定するためにニュー
ラルネットワークベースの手法を提案している．具体的には，オペレーターや変数などクエリの重要な特徴を抽出し，これらの特徴を効率的に hidden representation に変換するためのencoding model を設計している．二つ目は BIGSUBs [2] と同様に整数計画問題と確率的なラベル付を行うが，この方法では解の収束を保証できないとし，この問題をマルコフ決定過程を用いた深層強化学習モデルを使用して解決している．エージェ
ントは実体化ビュー群を管理しており，全ての実体化候補の中からフリップ (0 と 1 を入れ替える) る zj を選択しする．選択された zj をフリップした後，yij を整数計画問題によって求める．こうすることで得られた新たな利得を reward として学習を繰り返す．

6 結論

提案手法はワークロード内のサブクエリの利得，容量，頻度を考慮して解候補を削減し，整数計画問題を近傍探索を行いながら繰り返し解く．この手法により，最新技術である BIGSUBSと比較して，高速に，高い利得をもたらすことができた．また，実際に実体化ビューを作成することで実用した際に得られる効果を確認することができた．今後の課題として，以下の点が考
えられる．

•

ワークロードを拡張した場合での実体化ビュー効果•

最適実行プラン以外の実行プラン内のサブクエリ

7 謝

辞

この成果は，国立研究開発法人新エネルギー・産業技術総合開発機構（ＮＥＤＯ）の委託業務（JPNP16007) の結果得られたものです．
文

献[1] H.Lan, Z.Bao, and Y.Peng. A survey on advancing thedbms query optimizer: Cardinality estimation, cost model,
and plan enumeration. In Data Science and Engineering,pp. 86–101, 2021.
[2] Alekh Jindal, Konstantions Karanasos, Siram Rao, andHiren Patel. Selecting subexpressions to materialize at datacenter scale. In PVLDB, pp. 800–812, 2018.
[3] R.Ramakrishnan, B.Sridharan, J.R. Douceur, P.Kasturi,
B.Krishnamachari-Sampath, K.Krishnamoorthy, P.Li, M.Manu,
S.Michaylov, R.Ramon, N.Sharman, Z.Xu, Y.Barakat,
C.Douglas, R.Draves, S.S.Naidu, S.Shastry, A.Sikaria,
S.Sun, and R.Venkatesan. Azure data lake store: A hyperscale distributed ﬁleservice for big data analytics. In
SIGMOD, pp. 51–63, 2017.
[4] Haitao Yuan, Guoliang Li, Ling Feng, Ji Sun, and Yue
Han. Automatic view generation with deep learning andreinforcement learning. In ICDE, pp. 1501–1512, 2020.
[5] Y.N.Silva, P.Larson, and J.Zhou. Exploiting commonsubexpressions for cloud query processing. In ICDE, pp. 1337–
1348, 2012.
[6] J.Zhou, P.Larson, J.C.Freytag, and W. Lehner. Eﬃcient
exploitation of similar subexpressions for query processing.
In SIGMOD, pp. 533–544, 2007.
[7] 野々部宏司, 柳浦睦憲. 局所探索法とその拡張-タブー探索法を中心として. 特集 メタヒューリスティクスの新潮流, pp. 493–499,
2009.
[8] Viktor Leis, rey Gubichev, Atanas Mirchev, Peter Boncz,
Alfons Kemper, and Thomas Neumann. How good arequery optimizers, really? In VLDB, pp. 204–215, 2015.
[9] Postgresql: The world s most advanced open source
database. In https://www.postgresql.org/.
[10] Ivm (incremental view maintenance) development for postgresql. In https://github.com/sraoss/pgsql-ivm/.
[11] 長田悠吾, 星合拓馬, 石井達夫, 三島健, 増永良文. Postgresql
におけるビューの増分メンテナンス機能の実装とその評価. In
DEIM, 2021.
[12] https://hsc-release.mtk.nao.ac.jp/doc/index.php/database2/.