慶応義塾大学 政策・メディア研究科 修士課程2年
岩嵜 雄大
本年度の研究においては、高速RDFデータベースの研究のうち、特にSPARQLクエリにおけるBasic Graph Pattern最適化に関するの研究を主体として行った。
SPARQLクエリにおける最適化の1つに、Basic Graph Pattern（BGP）に含まれるトリプルパターンの並び替え（reorder）がある。クエリ処理のうち、多くの時間がトリプルパターンのJOIN処理に費やされるため、並び替えによるJOIN順序の最適化はクエリエンジンのパフォーマンスを決定づける大きな要因となる。
HPLabによるSPARQLクエリエンジンであるJena ARQは Markus Stocker et al. が [1] で紹介するBGP最適化アルゴリズムを元に実装されている。実際の実装は [1] に記述されているARQ/GSHとARQ/VCPの2つのアルゴリズムを組み合わせたものとなっている。具体的には、トリプルパターンに含まれる変数が1つの場合はARQ/VCPを用いた固定値によるセレクティビティを用い、変数が2つ以上含まれる場合にのみARQ/GSHによる統計（statics）を用いたセレクティビティ計算を行っている。
このアルゴリズムの組み合わせはRDFグラフに対する統計処理が十分に高速でない場合には一定の価値がある物と推測される。ソースコードに記述されているとおり、トリプルパターンに含まれる変数が1つの場合はパターンマッチの結果数が十分に小さくなる物と予想され、統計処理の効果で削減されるJOINの計算コストが統計処理自体のコストを下回る可能性がある。そのため、Jena ARQでは例えばSP?型のパターンでは2、?PO型のパターンでは3をセレクティビティの固定された推定値として用いている。なお、ここでいうセレクティビティはマッチングによる結果の数そのものを指す。
このアルゴリズムの組み合わせは多くの場合概ね妥当な効率を示すが、一方で特定の状況においてはセレクティビティに固定値が性能を大きく損なう可能性が存在する
固定値による性能低下の可能性を払拭するため、ARQ/GSHを改良したアルゴリズムを用いたBGP最適化を提案する。
ARQ/GSHではgraph statistics handler（GSH）と呼ばれる統計用のAPIを用いて、実際のグラフに含まれる値の数を求めている。例えば、あるURI参照がいくつ主語として含まれているか、あるいはあるリテラルがいくつ目的語として含まれているか、について実際の数を得ることが出来る。ただし、主語や述語、あるいは述語と目的語といった組み合わせを用いた統計には対応していないため、トリプルパターンに含まれる変数が1つの場合、つまりconcreteなcomponentが2つある場合は、主語、述語、目的語ごとに得られた値を使用して、トリプルパターン全体の値を推定する必要がある。しかし、既存のアルゴリズムでは変数が1つの場合はARQ/GSHのかわりにARQ/VPCを用いていたため、concreteな値の組み合わせが存在する場合にどのような手法でトリプルパターン全体の値を推測するかについては検討されていない。
そこで今回は以下のアルゴリズムを新たに提案する。
対象のグラフGに含まれるトリプルパターン T について、Subject S、Predicate P、Object O、と置き、NgをGに含まれる全トリプルの個数とする。Tの結果数の推定値Ntを以下の通り求める
Ntの値は必ずNmin以下となることは自明である。しかし、Ntが具体的にどの程度の割合でNminより減少するかを考える手がかりはN1およびN2しかない。そこで、N1/Ngにより、N1がどの程度の割合でグラフに含まれているのかを求め、Nminに係数として掛け、Nminからの減少率として用いる。ただし係数を直接掛けると極端な結果となる。なぜならば、例えばNminがNs、N1がNpである場合、N1/Ngはグラフ中に含まれる全述語のうちのPの割合である。しかしSに対してグラフに含まれる全述語が用いられていることはまれであり、実際には全体の内のごく一部のみが使用されている物と考えられる。そこで、このアルゴリズムでは定数Aを用いてN1による影響度を調整するものとしている。Aをいくつにするかはデータセットごとに最適値が異なるが、BSBM[2]で使用されるデータセットの場合、実験によると0.5程度が好ましいようである。なお、N2についてもN1と同様に係数として用いる。
表はNgが10000、A=0.5とした場合の計算例を示している（[]で囲まれた数字がNmin）。
| トリプルパターン | Ns | Np | No | Nt |
|---|---|---|---|---|
| ?s ?p ?o | [10000] | 10000 | 10000 | 10000 |
| :s ?p ?o | [51] | 10000 | 10000 | 51 |
| ?s :s :p | 10000 | 903 | [32] | 17.4448 |
既存のARQ/GSHとARQ/VCPを併用した場合と改良型ARQ/GSHのみを用いた場合の性能をBSBMにより比較した。BSBMデータセットのスケールファクターは1,000である。
| QMpH | Query 5 | Query 10 | |
|---|---|---|---|
| Conventional | 846.36 | 0.27 | 265.20 |
| Improved(A=0.5) | 1613.39 | 0.57 | 279.41 |
| Improbed(A=0) | 1464.62 | 0.55 | 112.67 |
得られた結果をまとめ、注目すべき値のみを抜粋したものが上の表である。
1時間あたりに処理可能Query Mix数（QMpH）は既存の実装に比べて改良型では約2倍に増加している。伸び率を個別のクエリごとに確認したところ、QMpHの増加のほとんどがQuery 5の処理速度上昇によるものであることが分かった。一方、Query 10の結果を見るとA=0.5の時は性能の低下が見られないが、A=0の場合は50%以上に性能が落ち込んでいる。
今回提案した改良型のARQ/GSHアルゴリズムは特定のクエリにおいて既存のARQ/GSHに対して著しい性能の上昇を示した。既存のARQ/GSHはセクション（実測による期待値の算出）で示したとおり、実際の結果が固定された期待値から外れるクエリにおいては極端な性能低下をしめす可能性があったが、改良型においては安定した性能を示すことが出来た。
今後の課題としては定数Aの値の最適化が上げられる。今回定数Aはヒューリスティックに実験から求めた値を使用したが、対象のデータセットによって異なる値が最適値になる物と思われる。適切なAが選択されない場合、Query 10のように性能の低下を招く可能性がある。Aの設定を自動化するなどして、より柔軟な最適化を可能にする必要が有るものと考える。