講演情報
[3C-03]局所探索法を用いた実体化ビュー選択によるクエリワークロード処理の高速化
*アンダーソン 圭那1、鬼塚 真1、佐々木 勇和1、Yohanes Yohanie Fridelin Panduman1 (1. 大阪大学)
発表者区分：学生
論文種別：ロングペーパー
インタラクティブ発表：あり
論文種別：ロングペーパー
インタラクティブ発表：あり
キーワード：
データベース、局所探索法、整数計画問題、実体化ビュー
クエリ数が膨大なワークロードにおいて高速なクエリ処理のために，実体化ビューの利用が有効である． 実体化する部分クエリの選択が重要となるが，クエリ数が膨大な場合，実体化する最適な部分クエリ群を選択する問題を整数計画問題として解くことは解の探索空間が膨大であることと扱う変数の数が膨大になるため実行が困難である． 本論文では，利得の高い部分クエリの近傍の部分クエリは同様に利得が高い傾向があるという性質を活用して，最適な実体化ビュー選択の問題を局所探索法を用いて解決する．有効な局所探索法のためには，適切な初期解を設定して局所解に陥らないようにするため，ワークロードにおける様々な統計情報を用いて $top-k$ の部分クエリを決定し初期解として利用する． 初期解選択後，近傍探索により解候補を近傍クエリに拡大し，新たな解候補に対し整数計画問題を解き，得られた解に対して再び近傍探索を行うという処理を繰り返すことで最適解へと漸近する． 実験ではjoinクエリの評価でよく利用されるベンチマークである Join Order Benchmarkでの実験により，既存技術である BIGSUBS の問題点を明確にすると共に，提案手法の有効性を示した．