データベースＳ 第11回 問い合わせ処理の最適化 システム創成情報工学科 尾下 真樹 今日の内容 • 問い合わせ処理の最適化 • 基本データ操作の実行方法 • 基本データ操作の処理コスト 教科書 • 「リレーショナルデータベース入門 」 増永良文 著、サイエンス社 （2,600円） – 8章 219～241ページ • 「データベースシステム」 北川 博之 著、昭晃堂 出版 （3,200円） – 7章 125～146ページ ※ 今回は、基本的にこちらの教科書に合わせた 説明になっている 問い合わせ処理の最適化 問い合わせ処理の最適化 • 問い合わせ処理 – SQLによる問い合わせの例 • 学籍番号が00100の学生の履修している各科目の 科目番号、科目名、成績を出力 SELECT FROM WHERE 科目.科目番号, 科目名, 成績 科目, 履修 科目.科目番号 = 履修.科目番号 AND 学籍番号 = ’00100’ – SQLでは、何を取り出すか（What）のみを指定し、 どうやって取り出すか（How）までは指定しない • 実際の処理方法によって速度は大きく異なる 問い合わせの実現方法 • 同じ問い合わせを実現するときでも、複数の 方法がある ①π科目.科目番号, 科目名, 成績（σ科目.科目番号＝履修.科目番号∧学籍 番号＝’00100’（科目×履修）） ②π科目番号, 科目名, 成績（σ学籍番号＝’00100’ （科目 科目.科目番号＝履修.科目番号履修）） ③π科目番号, 科目名, 成績（科目 科目.科目番号＝履修.科目番号 （σ学籍番号＝’00100’履修）） 科目 履修 問い合わせ方法による効率の変化 • 仮定 – 科目は１万タプル、履修は100万タプルとする – 学籍番号00100の学生は、50科目を履修 学籍番号00100の履修データ 50タプル 科目 1万タプル 履修 100万タプル 方法①での処理効率 • 方法①での処理効率 ①π科目.科目番号, 科目名, 成績（σ科目.科目番号＝履修.科目番号∧学籍 番号＝’00100’（科目×履修）） – 科目×履修の直積により100億タプルの中間 データ領域が必要 科目 × 履修 ・・・ 100億タプル 方法②での処理効率 • 方法②での処理効率 ②π科目番号, 科目名, 成績（σ学籍番号＝’00100’ （科目 科目.科目番号＝履修.科目番号履修）） – 科目と履修の等結合により、100万タプルの中 間データ領域が必要 科目 履修 100万タプル 方法③での処理効率 • 方法③での処理効率 π科目番号, 科目名, 成績（科目 科目.科目番号＝履修.科目番号（σ 学籍番号＝’00100’履修）） – 先に50個の履修のタプルを選択してから結合す るため、中間データ領域は50個分で良い 科目 履修 ※ ３通りの方法の中では最も効率的 最適化の原則 • なるべく処理すべき中間データを減らす – 問い合わせ結果に関与しないタプルを除去する ため、選択をできるだけ早い段階で適用する – 中間結果のデータ量を削減するため、射影によ る不要な属性の削除をできるだけ早い段階で行 う – 直積とその直後の選択が結合にまとめられる場 合は、そのようにする 処理木を使った最適化 • 処理の手順を木表現で表す π科目.科目番号, 科目名, 成績 σ科目.科目番号＝履修.科目番号 ∧ 学籍番号＝’00100’ × 科目 履修 処理木を使った最適化 • 処理木に最適化のためのルールを順番に 適用していくことで最適化を実現 1. 選択条件を分解 2. 選択を可能な限り下に移す 3. 連続する直積と選択を結合にまとめる 4. 射影を可能な限り下に移す 5. 連続した射影・選択をまとめて一つにする 処理木を使った最適化 • 1. 選択条件を分解 π科目.科目番号, 科目名, 成績 σ科目.科目番号＝履修.科目番号 σ学籍番号＝’00100’ × 科目 履修 処理木を使った最適化 • 2. 選択を可能な限り下に移す π科目.科目番号, 科目名, 成績 σ科目.科目番号＝履修.科目番号 × 科目 σ学籍番号＝’00100’ 履修 処理木を使った最適化 • 3. 連続する直積と選択を結合にまとめる π科目.科目番号, 科目名, 成績 科目.科目番号＝履修.科目番号 科目 σ学籍番号＝’00100’ 履修 処理木を使った最適化 • 4. 射影を可能な限り下に移す π科目.科目番号, 科目名, 成績 科目.科目番号＝履修.科目番号 π科目番号, 科目名 科目 π科目番号, 成績 σ学籍番号＝’00100’ 履修 処理木を使った最適化 • 5. 連続した射影・選択をまとめて一つにする π科目.科目番号, 科目名, 成績 ※ この例では不要 科目.科目番号＝履修.科目番号 π科目番号, 科目名 科目 π科目番号, 成績 σ学籍番号＝’00100’ 履修 基本データ操作の実行方法 基本データ操作 • 基本データ操作の方法 – 複雑な問い合わせも、選択や結合などの基本的 な操作の組み合わせによって実現される • 代数演算子を使った代数式で表される – それぞれの基本操作をどのように行うか？ • インデックスの有無や、条件の種類によって、最適な 処理方法は異なる • 基本データ操作 – 選択 – 結合 データ操作の最適化 • 最適化において注意すべき点 – データ量は、一般的には、ディスクに格納されて いると考えられる – データは、ページ単位でディスクから読み込んで くる必要がある – ディスクアクセスの速度は、メモリアクセスに比 べると著しく遅い – なるべくディクスアクセスの回数を減らすような 最適化が必要 ページ単位での読み書き • ページ配置の例 – データ（ソート有り or 無し） – １次インデックス付きデータ • インデックスとデータが同一ページに混在 – ２次インデックス 基本データ操作の実行方法 • 選択 • 結合 選択操作の方法 • 線形探索 • １次インデックスを用いた探索 • ２次インデックスを用いた探索 選択操作の方法 • 複数の条件が指定される選択の場合 – 複合インデックスを用いた探索 • あらかじめ複数の属性を組にしたキーを用いてインデックスを作 成しておく – 例：学生について（学科番号, 学籍番号）の組でインデックスを作成 – まず学科番号の順に並べる、学科番号が同じタプルについては 学籍番号の順に並べる – 学科単体でのインデックスとしても使用できる – 複数のインデックスを用いた探索 • 複数の２次インデックスを探索した結果の共通集合を求める – 複数のインデックスと線形探索の組み合わせた探索 • インデックスのある属性で探索した結果の共通集合を求める • 候補集合の各要素について線形探索 基本データ操作の実行方法 • 選択 • 結合 結合操作の方法 • 結合操作 – 問い合わせの中でも非常に手間がかかる処理 – 結合操作をいかに高速化するかが重要 • 結合操作の方法 – – – – 入れ子ループ結合 インデックスを用いた結合 マージ結合 ハッシュ結合 入れ子ループ結合 • ２つのリレーションの各タプル同士の組み合 わせを全てチェック – 実際には、各ページごとに処理 • ループが２重になるので、 入れ子ループと呼ぶ • 内側のリレーションの呼び 出しを繰り返し行う必要が ある – 非常に効率が悪い R S インデックスを用いた結合 • インデックスを用いた結合 – Rの各タプルごとに処理 • 結合対象のSのタプルをSの インデックスを用いて探索 R S マージ結合 • ２つのリレーションが結合する属性でソートさ れているとする – ２つのリレーションをそれぞれ 順番にたどりながら属性値の 同じタプル同士を結合 – 同じ値のデータが複数存在す る場合は、後戻りが必要 R S ハッシュ結合 • ハッシュを使った結合 • リレーションR の各タプルを、結合する属性でハッ シュを使用して分ける • リレーションS の各タプルごとに、同じハッシュ関数を 使用して、結合候補の R のタプルを探索 ハッシュ関数 R S 基本データ操作の処理コスト 処理コストの見積もり • ある処理を実現するために複数の方法が考 えられる – 状況によってどの方法が最も効率的かは異なる • 各種の統計情報を使って、処理コストを見積 もり、最適な方法を実行する – 例： 全レコード（タプル）数、１ページ中のレコー ド数、ページ数、各属性のとる値の種類、イン デックスの木の高さ、など • 見積もりは統計的な値なので、必ずしも正確 とは限らないことに注意する 基本データ操作の処理コスト • 選択 • 結合 選択 • 選択率 λ – 選択で得られるタプルの割合 – リレーションS 中に出現する、属性A の値の種類 の数 V（S,A）が重要になる • 例：リレーション「学生」の属性「学籍番号」が、00001 ～90000 ならば V（学生, 学籍番号）＝90000 – データが均一に分布していると仮定すると、 • 条件A=θの選択率は、λ＝ 1 / V（S,A） • 条件A>θの選択率は、値の範囲とθから判断 – 上の例で、学籍番号＞50000 であれば、 λ＝ 40000/ 90000 選択の処理効率 • インデックスがない場合の線形探索 – リレーションS のページ数をP とする – 線形探索では全データを見る必要があるので、 – 処理コスト（アクセスする必要のあるページ数） COST ＝ P – ただし、検索する属性がキー属性（重複なし）で、 検索条件がA=θの場合は、途中で求めるタプル が見つかったら停止して良いので COST ＝ P / 2 選択の処理効率 • インデックスを使った探索 – リレーションS がハッシュを持っている場合 COST ＝ 1 （ハッシュのバケツにオーバーフローがない場合） – B+-ツリーを持っており、条件が A=θ の場合 COST ＝ H ＋ 1 （Hはツリーの高さ、1 はデータを読み込む分） – B+-ツリーを持っており、条件が A>θ の場合 COST ＝ H ＋λP （λP はデータを読み込む分） – ２次インデックスの場合や、同一属性のデータ が複数ある場合は、さらにコストは高くなる 基本データ操作の処理コスト • 選択 • 結合 結合の処理効率 • 結合選択率 λj – 結合における選択率 • リレーションS のデータ数をNS （PSページ）、 リレーションR のデータ数をNR （PRページ）、 結合結果のデータ数を NSR • 結合選択率 λj＝ NSR / NS NR 結合の処理効率 • 入れ子ループ結合 – 外側のループ（リレーションR）を同時にMページ 処理できるとする – 内側のページは、［PR / M］回 スキャンする必要がある • ただし、［PR / M］は切り上げ – COST ＝ PR ＋ ［PR / M］PS – サイズの小さい方を外側に した法が効率的 R S 結合の処理効率 • インデックスを使った結合 – 主検索の場合 – Rの各データごとに、 Sのツリーの高さに応じた アクセスが発生する – COST ＝ PR ＋ NR （H＋1） – Sの同一属性が複数ある 場合などはさらにコストが 増える R S 結合の処理効率 • マージ結合 – それぞれのリレーションを上から順にアクセス – 両方のリレーションについて各ページを１度ずつ アクセスすれば良いので、 – COST ＝ PS ＋ PR R S 結合の処理効率 ハッシュ結合 – 両方のリレーションについて各ページを１度ずつ アクセスすれば良いので、 – COST ＝ PS ＋ PR ハッシュ関数 R S まとめ • 問い合わせ処理の最適化 • 基本データ操作の実行方法 • 基本データ操作の処理コスト
© Copyright 2024 ExpyDoc
