【DBiD】5 リレーショナル代数 (その4）

** 5.6 式の変換
 - リレーショナル式を同値な別のリレーショナル式に
   変換していく。それがオプティマイザの役割のひと
   つでもある。
 - 式の変換の例。
   - 「部品P2を供給するサプライヤを、供給する部品
     数とともに取得する」クエリ。

     ((S JOIN SP) WHERE PNO = PNO('P2')) {ALL BUT PNO}

   - 濃度について、S:100、SP:100万、SPのうちP2であ
     るのが500という状況を考える。
   - この式を単純に評価すると次の手順となる。
     - 1. SとSPを結合する。
       - Sをread。(100タプル read)
       - SひとつごとにSPをread。(100万タプル read)
       - 結果として100万個のタプルをwrite。(100万タ
         プル write)
     - 2. 1の結果を制限する。
       - 結果としての100万個のタプルをread。(100万
         タプル read)
       - 制限として500個がピックアップされ、それは
         writeせずにメモリ保持と見做す。
     - 3. 2の結果を射影する。
       - これはメモリ上の処理。
   - この手順でのタプルI/O数は、次の計算のとおり。
     (+ 100
        (* 100 1000000)
        1000000
        1000000) ; => 102000100
   - 別の手順を考える。
     - 1. SPを部品P2のタプルだけに制限する。
       - SPで100万タプルread。
       - 結果の500タプルはメモリ保持。
     - 2. 1の結果とSを結合。
       - Sで100タプルread。
       - 結合してできた500タプルはメモリ保持。
     - 3. 2の結果を射影する。
       - これはメモリ上の処理。
   - この手順でのタプルI/O数は、次の計算のとおり。
     (+ 1000000
        100) ; => 1000100
   - I/Oの差。
     (/ 102000100.0 1000100) ; => 101.98990100989901
   - 2つめの手順を素直に表すように式を書き換える。
     
     ((S JOIN SP) WHERE PNO = PNO('P2')) {ALL BUT PNO} ; もともと
     (S JOIN (SP WHERE PNO = PNO('P2'))) {ALL BUT PNO} ; 変更版

   - オプティマイザというのはこういうことを知って
     いて、その知識をもとに式変換を実施する。

   - 式変換に使えるのはリレーショナル代数の演算子
     どうしの性質である。
     - 分配則
     - 可換則
     - 結合則
     などがある。
   - リレーショナル代数における最適化はDBの実装(物
     理構造)によらない。

牛歩のごとくだなぁ。
こつこつ。