講演情報
[3C-04]パーティション化されたテーブルの結合演算の計画における同値類処理とPostgreSQLでの高速化手法
*渡 佑也1 (1. NTTソフトウェアイノベーションセンタ)
発表者区分：一般
論文種別：ロングペーパー
インタラクティブ発表：あり
論文種別：ロングペーパー
インタラクティブ発表：あり
キーワード：
結合演算、同値類、計画、パーティショニング、PostgreSQL
本論文では，オープンソースの関係データベース管理システム（RDBMS）であるPostgreSQLにおける結合演算の計画について同値類との関連を論じ，テーブルが多数のパーティションに分割されているときの計画性能を向上させる手法を提案する．結合演算を含む問合せを計画するにあたっては，より高速に実行できる結合順序を見出すことが求められる．そのためには，問合せからは自明でない結合条件による結合順序も探索する必要があり，そうした条件を導出するために同値類の概念が活用される．また，運用性向上などのためにテーブルをパーティション化することがあるが，PostgreSQLには同値類の処理に非効率性があるために，そのようなテーブルを結合する問合せの計画にパーティション数に対して二乗の時間計算量を要する問題が存在する．本稿では，計画の代表的な手法であるSystem Rアルゴリズムを同値類との関連を中心に論じ，PostgreSQLにおける実行計画器の構造を明らかにする．そして，同値類の処理に関する計算量を二乗から線形に削減する手法を提案し，評価実験を通じて提案手法が計画時間を大幅に短縮することを示す．