パーティショニング最適化

Irenka

めも。

クエリ内のプレースホルダを制約パーティショニングして、2つ以上のパーティションができたらそれらはそれぞれ独立している。そしたら別々に制約エンジン走らせて後で直積集合作ると最適っぽい。


現在の実装はNFA作ってバックトラックしまくりなので、パーティションA、パーティションBがそれぞれカーソルベースで10lineずつの候補を持っていた場合、どちらかのパーティションは10回同じ計算を行うことになる。パーティションの計算コストを高々m, パーティションがn個とした場合、計算量はO(m^n)。これはひどい。

対して、パーティションごとに候補を持ち寄って、結果のラインが partition-A = {a, b}, partition-B = {c, d} とか(a..dは結果のrowsetだと思っていただければ)になるとする。partition-Aの各カラムで束縛されたプレースホルダと、partition-Bの各カラムで束縛されたプレースホルダは互いに素(それこそがパーティションの定義)なので、それぞれは独立して計算しても互いに影響が出ない。分割して計算した結果をそれぞれmemoizeしといて、あとでそれぞれの結果セットをjoinすればよさげ。

  • partition-A は2ライン分の計算
  • partition-B は2ライン分の計算
  • 結果は join(a, c), join(a, d), join(b, c), join(b, d) の4ライン

入力数m, 制約数nに対して、計算量がO(m^n)だったのが、パーティショニングすれば、nを最大の制約を持つパーティションの制約数まで落とせる。(ちなみに、入力数mは型推論でかなり落としてるつもり)

ただ、2つ以上のパーティションが発生させるクエリ自体がレアかも知れぬorz。用途が思いつかないレベルで。

検討の価値*1はありそう。ということでめもめも。

*1:これくらいはルールベース言語でふつーにやってそうだ。論文読まねば