←【ファイルとデータベース】シラバスへ

第12回講義内容へ→

←講義のツボメニューへ

格納したデータを引き出すしくみ（続々）

【2000.06.23 １限　第10回】

今回の主な参照箇所：文献[3]の第９回「問い合わせ処理」のＰ．１６９〜１８８。

最適化

• 「問い合わせ処理（query processing）」＝ユーザがデータ操作言語で書いた問い合わせをＤＢＭＳが解釈、実行すること。
• （データベースにおける）「最適化（optimization）」＝ユーザによって入力された問い合わせ文を、それと同等でしかももっと早く実行出来る問い合わせ文にＤＢＭＳが変換する事。
• 問い合わせ処理の大半は、最適化に費やされる。
• 「オプティマイザ（optimizer）」＝ＤＢＭＳのうち、最適化を行う部分のこと。
• オプティマイザの出来の善し悪しにより問い合わせの処理速度がまったく変わってくる。データベース化するような大量のデータの取り扱いでは、商品の差別化として、重要なポイントになる。
• cf.「ベンチマークテスト」＝ＤＢＭＳ商品の相対比較に使われる物で、データベーススキーマ、リレーション、タプル数、問い合わせ、問い合わせの条件が満たされる確立などをある一定条件に定めて、コストパフォーマンス（価格性能比）などを定量的に評価する。
  ＴＰＣ（トランザクション処理性能評議会）ベンチマークが有名で、ＴＰＣ−Ａベンチマーク、ＴＰＣ−Ｂベンチマーク、ＴＰＣ−Ｃベンチマークと進化を続けている。
  ※自社製品に都合の良いバラバラな条件設定ばかりでは、相対比較ができないことから始まった。

内部表現への変換
　内部表現として関係代数／リレーショナル代数を使う場合で考える。
ex）「扱っている人が”井沢”で、商品ＩＤが”ｃ”で始まる商品を１００個以上注文している項目を含む発注書の発注番号」を求めるＳＱＬ文：
図１の２通りが考えられる。これを関係代数で表現したのが図９−２。
ここでの記法は、

• JOIN：ナチュラルジョイン（自然結合）。以降「ジョイン」と略すこともある。どの属性で結合するかは、省略している。
• PROJ：射影
• [　]：選択
• （　）については、内側ほど先に評価する。

よって、処理手順としては、

1. ＣとＤでジョイン。
2. さらにＢをジョイン。
3. これをＢ上の条件で選択
4. さらにＣ上の条件で選択。
5. さらにＤ上の条件で選択。
6. これを属性”発注番号”で射影 これを問い合わせ木（query tree）で表現すると、図９−３。
   ※最初にジョインをすると途中の表が大きくなるのでブロック転送の回数が増え、処理速度が出にくい。
   
   同等な内部表現への変換
   （方法１）：選択をジョインより先に行う。
   ※条件に見合わないタプルを、出来る限り早く捨てるという考え方。
   
   （方法２）：射影をジョインより先に行う。
   ジョインに使われる属性と、後で注目される属性以外は、早く捨てるという考え方。
   
   Ｑ．この考え方に従って改良した関係代数式と問い合わせ木を書け
   
   
   （方法３）：意味を考えた最適化。
   
   ※以上（方法１）〜（方法３）などのように、処理手順を工夫する事により問い合わせ処理速度の向上が図れる。
   
   アクセスパスの選択
   
   • 最適化を考える上では、インデックスの有無や、データの格納状態に対する考慮も重要。
   • これら低レベルの情報を用いて、より細かくアクセス手順を選択することを、「アクセスパスの選択」という。
   
   
   ジョインのアルゴリズム
   
   • 問い合わせ処理で最も負荷がかかるのは、ジョインである。（射影や選択より負荷が高い。）
   • ジョインの最適化の優劣が、勝敗を分ける。
   • ３つの代表的なジョインのアルゴリズム
     1. ネストループ／入れ子ループ（nested loop）方式
        • 単純に２重ループを回すもの
        • 表ＡのタプルごとにＢの全タプルとの比較処理を行うので、コストは２つの表のタプル数の席に比例する。すなわち、O(m*n)
     2. ソートマージ（sort-merge）方式
        • (a)のネストループ方式の改良版。
        • 各表について、結合する属性であらかじめソートしておく。
        • 両方の表にポインタを持ち、上から下へ順にスキャン死ながらマージしていく。
        • １回だけのスキャンで済むのが特徴。すなわち、O(m+n)
        • もちろん、表ごとのソートのコストも加える必要もあるが、それでも一般にネストループ方式よりは低コスト。
        • ソートは、タプルそのものをソートする他に、インデックスをソートしてもよい。
     3. ハッシュクラスタリング（hash-clustering）方式
        • 結合する属性の値で２つの表の両方のタプルをハッシュし、それぞれk個の固まり（クラスタ）に分割する。
        • ハッシングではこの固まりのことを「バケット」という。
        • ２つの表で同じ数だけバケットができる。
        • 同じバケット同士でジョイン。
        • O((m1*n1)+(m2*n2)+...+(mi*ni))
   • 一般には、(a)＜(b)＜(c)の順で処理速度が速い。（(c)が最速）
   • mとnが極端に違う場合や、mとnが十分小さいときには、(a)のネストループ方式が優位になる場合もある。 ※要するに、データベースの状態に依存して変化する。
   
   
   アクセスプラン
   
   • ここまでで示してきた技術を組み合わせて、問い合わせ処理を実行する手続きを何通りか作る。
   • そして、もっともコストが小さいものを選択する。
   • しかしながら、最適化自体に処理時間がかかりすぎては意味がない。
   • 通常、最速となり得るものに絞って比較検討する。
   • このあたりの取捨選択が、企業秘密であり、差別化の根幹となる。
   
   

   ---

   ←【ファイルとデータベース】シラバスへ

   第12回講義内容へ→

   ←講義のツボメニューへ
   ←鈴木研究室ホームへ