JPH0738165B2

JPH0738165B2 - デ−タベ−ス管理方法

Info

Publication number: JPH0738165B2
Application number: JP60137052A
Authority: JP
Inventors: 和洋佐藤; 正士土田
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 1985-06-25
Filing date: 1985-06-25
Publication date: 1995-04-26
Anticipated expiration: 2010-04-26
Also published as: JPS61296426A

Description

【発明の詳細な説明】〔発明の利用分野〕本発明は、データベース処理装置、なかんずくデータベ
ース管理機構に関し、特にリレーシヨナルデータベース
に適した、問合せの処理と、問合せ処理手順に基づくバ
ツフアの管理に関する。

〔発明の背景〕

データベース管理システム（以下DBMSと略記）、特にリ
レーシヨナルDBMSは、非手続的な言語で表現された外部
からの問合せを処理して、内部処理手順を決定し、実行
する。従来の問合せ処理の主な方法には、固定的で、し
かも、データベース等に関する統計情報を考慮しない、
純論理的な観点に立つルールに基づいて、直接に単一の
内部処理手順を決定するもの（例えば、Smith,J.M.及び
Chang,P.Y.T.“Optimizing the Performance of a Rela
tional Database Interface"C.ACM Vol.18,No.10,Oct.1
975,pp.568〜579）と、各種統計情報を用いて選定され
た複数の候補処理手順から、コスト評価により、最適と
思われるものを決定するもの（例えば、Selinger,P.G.e
t al.“Access Path Selection in a Relational Datab
ase Management System"Proc.ACM−SIGMOD,1979,pp.23
〜34）とがある。しかし、前者は、処理手順作成のため
の負荷は小さいけれども、一律的に設定されたルールの
妥当性に問題があり、後者は、最適な処理手順を与える
可能性は大きいが、各種統計情報の管理と、複数の候補
手順の作成及びそれらのコスト評価のための負荷が大き
い。

また、多くのDBMSにおいて、アクセスコストの低減のた
め、外部記憶装置に格納されたデータベースの部分的な
写しを保持するバツフア（データベースバツフア）を、
主記憶装置内に用意することが行なわれている。処理対
象としてデータベースバツフアーに一旦取出されたデー
タを、当面の処理が終つた後も残しておけば、再度その
データが必要になつたときに、高価なアクセスコストを
伴う外部記憶装置へのアクセスを省略できるから、シス
テム性能が向上する。しかし、データベースバツフアの
容量には限りがあるから、その内容の入替え（リプレー
ス）が必要となり、その巧拙は、システムの性能を左右
する。したがつて、リプレースに際してどのようなデー
タを残すべきかを決めるための、選定基準が重要であ
る。

可能な選定基準の一つは、一般のバツフア記憶装置にお
いて周知の、LRU（Least Recently Used）アルゴリズム
である。このアルゴリズムは、最後のアクセスから現在
までの期間が長いデータほど、再びアクセスされる可能
性が小さいという仮定に、その基礎を置く。しかし、デ
ータベース処理においては、データベースデータに逐次
的にアクセスする型の処理と、ランダムにアクセスする
型の処理とが混在し、その場合には、前記の仮定はしば
しば破られる。したがつて、データベースバツフアにお
いては、単純なLRUアルゴリズムにのみ依存するのは得
策でない。この問題の解決を目指す従来技術に、ヒツト
率に応じてバツフアサイズを管理するものがあるが、未
だ充分なものとはいえない（特開昭59−5483号公報,G.
M.Sacco et al.“A Mechanism for Managing the Buffe
r Pool in a Relational Database System Using the H
ot Set Model"Proceedings of the 8th International
Conference on Very Large Database,1982）。

〔発明の目的〕

本発明の目的は、DBMSにおいて、問合せ処理のための内
部処理手順の決定ルールを自動的に改修することによ
り、問合せ処理性能を改善し、更に、個々の内部処理手
順をリプレース制御に反映させることにより、データベ
ースバツフアの効率を改善することにある。

〔発明の概要〕

本発明による問合せ処理においては、実行の対象となる
内部処理手順は、単一の内部処理手順を与える第１ルー
ルベースによつて選定され、このルールベースは、デー
タベースシステムの統計情報（システム特性，データベ
ース特性，処理方式特性などについての情報）を、内部
処理手順の選定に利用するものである。これと並行し
て、比較の目的で、別のルールベースにより、いくつか
の内部処理手順が選定される。このルールベースも、デ
ータベースシステムの統計情報を利用するものである
が、ただ、それにより選択される内部処理手順は１個に
限定されない。これら２系統の処理により選択されたす
べての内部処理手順は、例えばコスト評価などの評価を
受けて比較され、そして、その結果に応じて、第１ルー
ルベースが修正される。例えば、最低コストの内部処理
手順を与えるように、ルールの追加又は修正が行なわれ
る。これにより、システムは自己学習的に性能の改善を
継続する。

また、本発明によるバツフア管理においては、問合せ処
理最適化過程において決定された内部処理手順から得ら
れるデータベース参照特性情報（アクセスの型や頻度、
各ページへの予想アクセス回数など）が、バツフア制御
情報として用いられ、リプレースの対象となるバツフア
の選定に際して参照される。例えば、LRUアルゴリズム
の下で、予定アクセス回数に達したページが優先的にリ
プレースされる。これにより、ヒツト率が向上し、バツ
フアの効率が改善される。

〔発明の実施例〕

第１図は、本願の第１発明が適用されたDBMSの一例の概
要を示す。DBMS2は、システム全体の管理・制御に加え
て入出力の管理を行なうシステム制御部３と、問合せを
解析して適切な内部処理手順コードを生成するデータベ
ース論理処理部４と、生成された処理手順コードに従つ
てデータベース７へのアクセスその他を実行するデータ
ベース物理処理部５を含む。問合せの入力とそれに対す
る回答（処理結果）の出力は、入出力部１を介して行な
われる。データベース論理処理部４は、問合せの解析を
行なう問合せ解析部41と、解析結果に所定のルールを適
用して最適処理手順を決定する最適化部42と、決定され
た最適処理手順を実現するための処理コードを作成する
とともに、関連する所要の処理を行なうコード生成・論
理処理実行部43とからなる。

最適化部42で適用されるルールは、データベースシステ
ムに関する各種統計情報（後述するシステム特性，デー
タベース特性，処理方式特性など）を用いて、実行すべ
き単一の処理手順を指定する。例えば、このルールは、
述語選択率，処理対象データサイズ，アクセスパス、及
びアクセスパスデータサイズの値の種々の組合せと、各
組合せと一対一に対応する一群の処理手順情報とからな
るテーブルの形をなし、問合せの解析結果として得られ
る前記諸項目の特定の値の組合せから、対応する処理手
順が決定される。このようなルールの集合をルールベー
スと呼び、その管理は、ルールベース管理部421によつ
て行なわれる。

最化部42は、コスト評価最適化部６と接続される。コス
ト評価最適化部６は、最適化部42と並行して、問合せの
主要部について、コスト評価による最適化を行ない、そ
の結果と、最適化部42で作成された処理手順のコストを
比較し、必要に応じて、最適化部42のルールベースを改
修する。第２図に示されるように、コスト評価最適化部
６は、問合せの等価変換や解析を行なう問合せ解析部6
1、解析結果からいくつかの処理手順候補を選定する処
理手順候補生成部62、及び処理手順候補のコスト評価を
外部記憶アクセス回数、CPU使用時間等に関して行なう
コスト評価部63、並びにこれらに必要な情報を供給する
処理方式管理部66、システム特性管理部67、データベー
ス特性管理部68、及びルールベース管理部69を含む。処
理方式管理部66は、利用可能な処理機能（論理処理機
能，ハツシング機能等）に関する情報を管理し、処理手
順候補生成部62に供給する。システム特性管理部67は、
計算機システムの特性（バツフアサイズ、CPUや主記憶
の速度等）に関する情報を管理し、コスト評価部63に供
給する。データベース特性管理部68は、データベース特
性（データベース中の各種データサイズ，データベース
の物理構造，インデクスやリンクなどのアクセスパスの
種類や有無等）に関する情報を管理し、コスト評価部63
に供給する。ルールベース管理部69は、問合せ解析部61
での等価変換と処理手順候補生成部62における処理手順
候補の選定のためのルールベースを管理する。処理手順
候補の選定のためのルールベースは、基本的には前述し
た最適化部42のためのルールベースと同じてあつて、た
だ、選定される処理手順が複数存在しうる点が異なる
（同様なルールベースの例は、特願昭59−173387号（特
開昭61−52′号にも開示されている）。

コスト評価部63は、また、最適化部42により決定された
処理手順を、前処理部65を介して受取つて、そのコスト
評価を行なう。前処理部65は、最適化部42からの処理手
順情報に対して、コスト評価部63での処理に適合するよ
うに、コードその他の形式に関する変換を行なう。最適
手順選択部64は、コスト評価部63での評価結果から最小
コストの処理手順を決定する。レポート出力部70は、処
理手順候補生成部62、コスト評価部63、及び最適手順選
択部64の処理を、必要に応じて出力するためのものであ
り、ライン103は、各種管理部66〜69の初期設定のため
のものである。

第３図は、前記の各部が本発明に従つて行なう処理のフ
ローチャートである。ユーザからの問合せが、入出力部
１からライン100を通つてDBMSに与えられる（第３図20
0）と、システム制御部３は、その問合せの処理の管理
に必要な情報（問合せ識別コード等）を作成し、以後の
処理の管理を行なう（201）。問合せ解析部41は、シス
テム制御部３から受取つた問合せに対して、構文解析と
意味解析を行ない（202）、その結果を受けた最適化部4
2は、ルールベース管理部421を参照することによつて、
統計情報に基づく最適処理手順を決定する（203）。

他方、同じ問合せは、コスト評価最適化部６にも送ら
れ、問合せ解析部61は、この問合せの主要部（コスト評
価による最適化に必要な部分）に対して、構文解析と意
味解析を施し、かつ、ルールベース管理部69からの等価
変換ルールに基づき、条件式の適当な管理・変形を行な
う（204）。次いで、処理手順候補生成部62は、処理方
式管理部66から適用可能な処理方式の情報を得るととも
に、ルールベース管理部69からの処理手順候補選定ルー
ルを適用して、いくつかの処理手順候補を選定する（20
5）。コスト評価部63は、こうして生成されたいくつか
の処理手順候補のそれぞれについて、システム特性管理
部67からのシステム特性情報と、データベース特性管理
部68からのデータベース特性情報とを用いて、コスト
（外部記憶のアクセス回数、CPU使用時間等）を算出し
（206の）、最適手順選択部64は、これら処理手順候
補のコストを比較して、コストが最小の処理手順を決定
する（207）。

こうして決定された最小コストを〔Ａ〕とする。

その頃、最適化部42で決定（203）された処理手順は、
ライン101を通つて前処理部65に至り、そこで形式変換
を受けてから、コスト評価部63に渡される。コスト評価
部63は、この処理手順についても、前述したのと同様に
してコスト評価を行なう（206の）。これにより算出
されたコストを〔Ｂ〕とする。最適手順選択部64は、
〔Ａ〕と〔Ｂ〕を比較する（208,209）。

〔Ａ〕＜〔Ｂ〕の場合、最適化部42がルールベース管理
部421を参照して決定した処理手順は、最適とはいい難
い。そこで、コスト〔Ａ〕の処理手順を生じるルール
が、ルールベース管理部69から、ライン102を通り、ル
ールベース管理部421に転送されて、このルールの追加
のためのルールベースの修正が行なわれ、また、必要に
応じて、ライン104を経て、ルールベース管理部69が管
理するルールベースの修正も行なわれる（210）。更
に、必要があれば、最適化部42内に保持されている各種
統計情報の加除修正が行なわれる（211）。

これに対して、〔Ａ〕≧〔Ｂ〕の場合、最適化部42によ
り生成された処理手順は最適なものと考えてよいから、
前記の処理（210）は省略し、処理（211）のみが行なわ
れる。

問合せ処理の実行は、本実施例においては、いずれの場
合でも、最適化部42により生成された処理手順に従つ
て、通常の手順（212〜214）により遂行される。この方
法によれば、〔Ａ〕が〔Ｂ〕より小さい場合に、最適で
ない処理手順による問合せ処理が実行されるが、ルール
ベースの修正後に最適化を再度行なうのは、多くの場
合、不経済であるから、実用上はこれで支障がない。ル
ールベース修正の効果は、次回以降の問合せ処理におい
て発揮される。しかし、ルールベースの修正後に最適化
を再度行なう方法も、設計条件によつては採用すること
ができる。

コスト評価最適化処理を付加したことにより、負荷が増
大することは否めない。しかし、処理経歴を積むにつれ
てルールベースの改善が進み、修正の頻度は低下する。
したがつて、適当な時点で、ルールベース修正処理ある
いはコスト評価最適化処理全体を、間欠的に抑止した
り、あるいは永久的に無効にし、更には除去することが
できる。

コスト評価最適化部６は、負荷が過大にならなければ、
最適化部42の内部に埋込んでもよい。

第４図は、本願の第２発明が適用されるDBMSの一例を示
す。図中、第１図におけると同じ符号は同等の要素を示
す。ただし、最適化部42は、第１図のコスト評価最適化
部６を内蔵するものとする。データベース物理処理部５
は、バツフア制御部51を含む。データベースバツフア８
は、複数のバツフアからなり、実際には主記憶の一部で
ある。データベース７は、リレーシヨナルデータベース
であり、それは、論理上、いくつかのリレーシヨンから
なり、各リレーシヨンは複数のローの集合である。デー
タベース７は、常時は外部記憶装置に格納されており、
アクセス要求があると、該当する部分を含む一定範囲の
データブロック（ページと呼ばれる）が、データベース
バツフア８に連送されて、空きバツフアがあれば、そこ
に格納され、空きバツフアがなければ、後述するアルゴ
リズムに従つて選ばれたバツフアの内容を置換（リプレ
ース）する。アクセス要求のあつたデータを含むページ
がデータベースバツフア８内に存在すれば、それが用い
られ、外部記憶装置へのアクセスは不要となる。

最適化部42は、前述のようにして、統計情報を用いて、
問合せの処理のための内部処理手順を決定する。この内
部処理手順は、指定されたリレーシヨンの評価順序、結
合条件評価方法、問合せ条件評価方法などを含み、これ
らに基いて、各リレーシヨンについての参照特性、すな
わち、アクセスの型（ランダムか順序か）、順序、頻
度、時期など、及びこれらから導かれる、各リレーシヨ
ンについてバツフアに保存しておくのが望ましいページ
数（保証ページ数）と予想されるローアクセス回数、更
に、それぞれのページについて予想されるページアクセ
ス回数などを、推定することができる。これらの参照特
性情報は、本発明により、リプレースの制御に利用され
る。

第５図は、バツフア制御部51が管理するバツフア制御情
報を模式的に示す。バツフアエントリ（以下BEと略記）
300,310,320は、使用されるバツフアのそれぞれに対応
して用意される管理情報群である。バツフア制御ブロツ
ク（以下BCBと略記）330は、使用されるバツフアの全体
についての管理情報群である。リレーシヨン制御ブロツ
ク（以下RCBと略記）340は、処理対象である諸リレーシ
ヨン中のいくつかのものについて、一対一対に対応して
用意される管理情報群である。

バツフアのリプレースは、基本的にはLRUアルゴリズム
によつて制御される。このLRU制御のために、BE300〜32
0は、BCB330を含むLRUチエインに組込まれる。すなわ
ち、BCB330のLRU先頭ポインタ331は、最も新しいアクセ
スのあつたバツフアに対応するBEをポイントする。これ
はBE300であるとする。BE300のLRU前方ポインタ301は、
次に新しいアクセスのあつたバツフアに対応するBEをポ
イントし、以下同様にして、図示の例では、BE300、31
0、320が、この順でLRU前方チエインを形成している。
これとは逆に、BCB330のLRU末尾ポインタ332は、最も古
いアクセスのあつたバツフアに対応するBEをポイント
し、これは、図示の例ではBE320である。BE320のLRU後
方ポインタ322は、次に古いアクセスのあつたバツフア
に対応するBEをポイントし、かくして、BE320,310,300
が、この順でLRU後方チエインを形成している。

前記のLRUチエインに重ねて、RCB340が割当てられた各
リレーシヨンについては、そのリレーシヨンのページを
保持するバツフアに対応するBEが、それぞれのリレーシ
ヨンLRUチエインに組込まれる。すなわち、RCB340のリ
レーシヨンLRU先頭ポインタ341は、そのリレーシヨンの
ページを保持するバツフアの中で、最も新しいアクセス
があつたものに対応するBEをポイントし、これをBE310
とすれば、そのリレーシヨンLRU前方ポインタ313は、次
に新しいアクセスのあつたバツフアに対応するBEをポイ
ントし、これは、図示の例ではBE320である。RCB340の
リレーシヨンLRU末尾ポインタ342と、BE320,310のリレ
ーシヨンLRU後方ポイタ324,314は、BCB330のLRU末尾ポ
インタ332に始まるLRU後方チエインと同様にして、リレ
ーシヨンLRU後方チエインを形成する。図示の例では、B
E300のリレーシヨンLRU前方ポインタ303と、リレーシヨ
ンLRU後方ポインタ304は使用されていない。RCB340は、
比較的短期間に順次アクセスが行なわれるリレーシヨン
に割当てられる。例えば、リレーシヨンＡとＢを対象と
するjoin（結合）演算において、リレーシヨンＡの各ロ
ーごとにリレーシヨンＢの全ローが順次アクセスされる
とすれば、リレーシヨンＢにRCB340が割当てられる。

BE300,310,320のバツフアポインタ305,315,325は、対応
する各バツフアをポイントする。ページアクセスカウン
タ306,316,326は、対応するバツフアに保持されている
ページについて予想されるページアクセス回数（ページ
全体としてのアクセスの回数）を示す。この値は、“0"
又は正の整数をとることができ、処理対象となるページ
のそれぞれについて、初期設定処理により適当な制御ブ
ロツク中に設定されて、そのページと同時に入替えら
れ、“0"になるまでは、そのページがバツフアから掃出
されるたびに“1"が減じられる。この値が正のページ
は、後刻再びアクセスされるはずなので、なるべくバツ
フアに残しておくことが望ましい。BCB330の空バツフア
ポインタ333は、空いているバツフアの一つをポイント
する。エントリバツフア数334は、LRUチエインに組込ま
れたバツフア（すなわち、使用中の全バツフア）の数を
示す。

RCB340のエントリバツフア数343は、そのRCBが管理する
リレーシヨンLRUチエインに組込まれたバツフアの数を
示す。保証ページ数344は、バツフアに保存しておくの
が望ましい対応リレーシヨンの数を保持する。リレーシ
ヨンLRUチエインに含まれるページの数を少なくとも保
証ページ数に等しく保つことにより、いわゆるスラツシ
ング現象（データ要求のたびに外部記憶装置へのアクセ
スを生じる現象）を防止できる。ローアクセスカウンタ
345は、対応リレーシヨンのローの予想されるアクセス
回数を示し、そのリレーシヨンのいずれかのページのロ
ーにアクセスがあるたびに“1"が減じられる。この値が
“0"になれば、そのRCBが管理するリレーシヨンLRUチエ
インは、維持する必要がなく、したがつて、解放され、
この解放により、一部のリレーシヨンによるバツフア群
の占拠が防止される。

これらの他に、図示されていないが、各バツフアに保持
されているデータがデータベースのどのページであるか
を示すデイレクトリが、通常のバツフアメモリにおける
のと同様に、バツフア制御部51中に用意される。

第６図ａ〜ｅは、データ読出（FETCH−DATA）動作に際
して、バツフア制御部51により行なわれるバツフアの制
御の手順の一例を示す。第６図ａは、FETCH−DATA制御4
00の全体を示す。まず、要求されたページがバツフアに
存在するか否かが、デイレクトリを参照して調べられる
（401）。所要ページがバツフアに存在すれば、それへ
のアクセスが行なわれることになる。したがつて、その
バツフアがリレーシヨンLRUチエインのどれかに含まれ
るか否かが調べられて（402）、含まれていれば、対応
するBEはそのリレーシヨンLRUチエインの先頭に置か
れ、チエインが更新される（403）。しかし、所要ペー
ジを保持するバツフアが発見されなければ、バツフア獲
得（GET−BUFFER）処理410により、バツフアが獲得され
て、そこに、所要ページが外部記憶装置から転送され
る。この処理については、後で詳述する。

このようにして今回のアクセスの対象とされたバツフア
は、再度、リレーシヨンLRUチエインのどれかに含まれ
るか否かが調べられて（404）、含まれていれば、対応
するRCBのローアクセスカウンタは“1"を減じられ（40
5）、次いで、その結果のローアクセスカウンタが“0"
以下であるか否かが調べられる（406）。これが“0"以
下であれば、そのRCBの管理するリレーシヨンLRUチエイ
ンに含まれる各BEのページアクセスカウンタが“0"に設
定され、そして、そのリレーシヨンLRUポインタをすべ
てリセツトすることにより、そのリレーシヨンLRUチエ
インは解放される（407）。最後に、所要ページを保持
するバツフアに対応するBEがLRUチエインの先頭に置か
れ、チエインが更新される（408）。しかし、処理404に
おいて、問題のバツフアがどのリレーシヨンLRUチエイ
ンにも含まれないことが判明すれば、直ちに処理408に
移る。

GET−BUFFER処理410の詳細は、第６図ｂに示される。こ
の処理において、まず、空きバツフアの有無が調べられ
（411）、空きバツフアがあれば、その一つが新来ペー
ジに割当てられる（415）。しかし、空きバツフアがな
ければ、リプレースの対象となるバツフアが、本発明に
従つて、次のようにして選択される。まず、各RCBのエ
ントリバツフア数343と保証ページ数344が比較される
（412）。すべてのRCBのエントリバツフア数が保証ペー
ジ数に等しいかそれより小さい場合、LRUチエインにお
いて、ページアクセスカウンタが“0"であるBEがあれ
ば、それらの内でチエインの末尾に最も近いものが選択
され、ページアクセスカウンタが“0"のBEがなければ、
チエインの末尾のものが選択される（413）。他方、あ
るRCBのエントリバツフア数が保証ページよりも大きい
場合には、そのRCBが管理するリレーシヨンLRUチエイン
において、ページアクセスカウンタが“0"のBEがあれ
ば、それらの内でチエインの末尾に最も近いものが選択
され、ページアクセスカウンタが“0"のBEがなければ、
チエインの末尾のものが選択される（414）。処理413及
び414の後には、それぞれページ出力（PAGE−OUT）処理
420が続き、これらと処理415の後にページ入力（PAGE−
IN）処理430が行なわれて、GET−BUFFER処理410が終
る。

PAGE−OUT処理420の詳細は、第６図ｃに示される。ま
ず、リプレースのために選択されたバツフアがリレーシ
ヨンLRUチエインのどれかに含まれるか否かが調べられ
（421）、含まれていなければ、直ちにそのバツフアに
保持されていたページが外部記憶装置に出力される（42
4）。しかし、問題のバツフアがリレーシヨンLRUチエイ
ンのどれかに含まれていれば、そのバツフアに対応する
BEのページアクセスカウンタが０よりも大きいか否かが
調べられ（422）、０よりも大きくなければそのまま、
また、０よりも大きければ“1"が減じられた（423）後
に、ページ出力処理424が行なわれる。この時、ページ
アクセスカウンタの値は、対応する制御ブロツクに移さ
れる。

PAGE−IN処理430は、第６図ｄに示される。まず、所要
ページが外部記憶装置から選択されたバツフアに転送さ
れ、その間、そのページのページアクセスカウンタ値が
対応制御ブロツクから移される（431）。次いで、この
新来ページが属するリレーシヨンはRCBのどれかの管理
を受けるべきものか否かが調べられ（432）、管理を受
けるべきものでなければ、そのままPAGE−IN処理を終
り、管理を受けるべきものであれば、そのページを受け
たバツフアに対応するBEは、該当するリレーシヨンLRU
チエインの先頭に置かれ、チエインが更新される（43
3）。

第６図ｅは、バツフア初期化（INIT）処理440を示す。B
CB・BE初期化処理441においては、BCB、BE及び他の制御
ブロツクの割当てとそれらの内容の初期化が行なわれ
る。RCB処理化処理442においては、RCBの割当てとそれ
らの内容の初期化が行なわれ、最適化部42により決定さ
れた内部処理手順から得られるデータベース参照特性に
基づいて、保証ページ数344とローアクセスカウンタ345
が設定され、また、各処理対象ページに対応して、それ
ぞれのページアクセスカウンタ値が、適当な制御ブロツ
ク中に設定される。本実施例では、リレーシヨンLRUチ
エインを形成しないリレーシヨンのページアクセスカウ
ンタの初期設定値は、“0"である。

次に、具体的な問合せの例を用いて、総合的な説明を行
なう。第７図に示される２組のリレーシヨン“リゾー
ト”及び“レジヤー”がデータベース中に用意されてお
り、前者はページR11とR12に収容され、後者はページR2
1とR22に収容されているとする。このデータベースか
ら、「ゴルフができて、交通費が３千円以上５千円以下であ
り、かつ、海の幸を名物とする観光地の、名前とその所
在県名」を入手することが望まれる。この要求は、次の問合せ文
により表現される。

Select リゾート．名前，リゾート．県名 from リゾート，レジヤー where レジヤー．名前＝‘ゴルフ’ and （リゾート．運賃＞＝３ and リゾート．運賃＜＝５） and リゾート．名物＝‘海の幸’ and リゾート．名前＝レジヤー．リゾート名この問合せに対して、DBMS2の最適化部42により決定さ
れた処理手順は、概略次のようなものであるとする。

１）リレーシヨン“リゾート”から、カラム“運賃”
の値が“3"以上“5"以下で、かつ、カラム“名物”の内
容が‘海の幸’であるローを一つ索出する。

２）リレーシヨン“レジヤー”を走査して、前記１）
で索出されたリレーシヨン“リゾート”のローのカラム
“名前”の内容と同一内容をカラム“リゾート名”に持
つリレーシヨン“レジヤー”のローの索出する。

３）前記２）で索出されたリレーシヨン“レジヤー”
のローのカラム“名前”が‘ゴルフ’であれば、前記
１）で索出されたリレーシヨン“リゾート”のローを保
存し、そうでなければ捨てる。

４）前記１）〜３）を、リレーシヨン“リゾートのロ
ーが尽るまで繰返す。

５）前記３）で保存されたローのカラム“名前”と
“県名”を抽出する。

このような処理手順に基づいて、ページアクセスの対象
はR11、R12、R21、及びR22であり、使用されるバツフア
面数は“3"で、リレーシヨン“レジヤー”にリレーシヨ
ンLRUチエインの形成のためにRCB340が割当てられ、そ
の保証ページ数は“2"で、ローアクセスカウンタ値は
“6"であり、そして、ページアクセスカウンタ値は、リ
レーシヨン“レジヤー”については“4"で、同“リゾー
ト”については“0"であることが、それぞれ決定された
とする。

この問合せの処理のために、ページアクセスがR11,R12,
R21,R12の順で行なわれる場合について、バツフア制御
部51により実行されるバツフア制御の順序を、第５図及
び第６図を参照しつつ説明する。

ステツプ0: バツフア初期化処理440により、BCB330、BE300,310,320
などの制御ブロツクの割当てと初期化が行なわれ（44
1）、次いで、RCB340がリレーシヨン“レジヤーに割当
てられて、その保証ページ数344とローアクセスカウン
タ345がそれぞれ“2"と“6"に設定され、かつ、リレー
シヨン“レジヤー”の各ページR21,R22に対応する制御
ブロツクに、ページアクセスカウンタ値“4"が設定され
る（442）。リレーシヨン“リゾート”の各ページR11,R
12に対応する制御ブロツクには、いずれも“0"が設定さ
れる。

あステツプ1: まず、R11へのアクセスが要求されると、FETCH−DATA処
理400（第６図ａ）が起動される。まず、R11を保持する
バツフアの有無が調べられ（401）、存在しないので、G
ET−BUFFER処理410（第６図ｂ）が起動される。そこ
で、空きバツフアが存在するか否かが調べられ（41
1）、それは存在することが判明し、空きバツフアが１
面獲得される（415）。これはBE300に対応するバツフア
であるとする。

そこで、PAGE−IN処理430（第６図ｄ）が起動され、要
求されたページR11が外部記憶装置から前記の獲得され
た（BE300に対応する）バツフアに転送されるととも
に、対応するページカウンタ値“0"がページカウンタ30
6に設定される（431）。次に、それがリレーシヨンLRU
チエインを形成すべきページか否か、すなわち、リレー
シヨン“レジヤー”のページか否かが調べられ（43
2）、そうではないので、PAGE−IN処理430は終了し、そ
れによりGET−BUFFER処理410が終了する。第６図ａに戻
り、BE300がRCB340の管理するリレーシヨンLRUチエイン
に含まれているか否かが調べられ（404）、含まれてい
ないので、直ちに、BE300をLRUチエインの先頭に置く処
理408が行なわれる。

この時点において、BCB330のLRU先頭ポインタ331とLRU
末尾ポインタ332は共にBE300をポイントし、エントリバ
ツフア数334は“1"であり、BE300のページアクセスカウ
ンタ306は“0"である。RCB340の内容には変更なく、リ
レーシヨンLRUチエインは形成されていない。

ステツプ2: 次に、R21へのアクセスが要求されると、FETCH−DATA処
理400が起動される。R21を保持するバツフアは存在しな
いので（401）、GET−BUFFER処理410が起動される。空
きバツフアが存在するので（411）、空きバツフアが１
面獲得される（415）。これはBE320に対応するバツフア
であるとする。

そこで、PAGE−IN処理430が呼ばれ、R21はBE320に対応
するバツフアに格納されるとともに、対応するページア
クセスカウンタ値“4"がページアクセスカウンタ326に
設定される（431）。R21は、リレーシヨン“レジヤー”
に属し、リレーシヨンLRUを形成すべきページである（4
32）。したがつて、BE320はRCB340の管理するリレーシ
ヨンLRUチエインの先頭に置かれる（433）。第６図ａに
戻り、BE320はリレーシヨンLRUチエインに含まれている
ので（404）、ローアクセスカウンタ345は“1"を減じら
れ（405）、その結果、ローアクセスカウンタ345の値は
“5"となり、“0"より大である（406）。したがつて、
直ちにLRUチエインが更新され、BE320はその先頭に置か
れる（408）。

この時点において、BCB330のLRU先頭ポインタ331に始ま
るLRU前方チエイン〔→BE320→BE300〕と、LRU末尾ポイ
ンタ332に始まるLRU後方チエイン〔→BE300→BE320〕と
が形成されている。エントリバツフア数334は“2"であ
り、ページアクセスカウンタ306は“0"で、同326は“4"
である。また、RCB340のリレーシヨンLRU先頭ポインタ3
41と同末尾ポインタ342は共にBE320をポイントし、エン
トリバツフア数343は“1"で、ローアクセスカウンタ345
は“5"である。

ステツプ3: 次に、R22へのアクセスが要求されると、ステツプ３と
同じ順序を経て、処理415においてBE310に対応するバツ
フアが獲得され、処理431においてそのバツフアにR22が
格納され、処理433においてBE310がリレーシヨンLRUチ
エインの先頭に置かれ、処理405でローアクセスカウン
タ345から“1"が減じられ、そして、処理408においてBE
310がLRUチエインの先頭に置かれる。

この時点において、BCB330のLRU先頭ポインタ331に始ま
るLRU前方チエイン〔→BE310→BE320→BE300〕と、LRU
末尾ポイタ332に始まるLRU後方チエイン〔→BE300→BE3
20→BE310〕とが形成されている。エントリバツフア数3
34は“3"であり、ページアクセスカウンタ306は“0"、
同316及び326は共に“4"である。他方、RCB340において
は、リレーシヨンLRU先頭ポインタ341に始まるリレーシ
ヨンLRU前方チエイン〔→BE310→BE320〕と、リレーシ
ヨンLRU末尾ポインタ342に始まるリレーシヨンLRU後方
チエイン〔→BE320→BE310〕とが形成されている。エン
トリバツフア数343は“2"で、ローアクセスカウンタ345
は“4"である。

ステツプ4: 次に、R12へのアクセスが要求されると、前記諸ステツ
プと同様にしてGET−BUFFER処理410が起動され、空きバ
ツフアの有無が調べられる（411）。今回は空きバツフ
アが存在しない。そこで、RCB340のエントリバツフア数
343と保証バツフア数344が比較される（412）。両者は
等しく“2"である。したがつて、処理413により、BCB33
0が管理するLRUチエインにおいて、ページアクセスカウ
ンタが“0"であるBEの探索が、チエインの末尾から始め
られ、該当するBE300が発見される。

そこで、PAGE−IN処理420が呼ばれ、このBE300はリレー
シヨンLRUチエインに含まれていないので（421）、直ち
に対応するバツフアの内容が出力されて（424）、PAGE
−IN処理（430）に進みR12がBE300に対応するバツフア
に入力される（431）。このページはリレーシヨン“リ
ゾート”のページであり、リレーシヨンLRUチエインに
組込まれるべきものではないので（432）、直ちにPAGE
−IN処理は終わり、したがつてGET−BUFFER処理も終わ
る。そして、このBE300はリレーシヨンLRUチエインに含
まれていないので（404）、RCB340はそのままにして、B
E300はLRUチエインの先頭におけれる。

この時点において、BCB330のLRU先頭ポインタ331に始ま
るLRU前方チエイン〔→BE300→BE310→BE320〕と、LRU
末尾ポインタ332に始まるLRU後方チエイン〔→BE320→B
E310→BE300〕とが形成されている。エントリバツフア
数334は“3"であり、ページアクセスカウンタ306は
“0"、同316と326は共に“4"である。他方、RCB340にお
いては、リレーシヨンLRU先頭ポインタ341に始まるリレ
ーシヨンLRU前方チエイン〔→BE310→BE320〕とリレー
シヨンLRU末尾ポインタ342に始まるリレーシヨンLRU後
方チエイン〔BE320→BE310〕とが形成されている。エン
トリバツフア数343は“2"で、ローアクセスカウンタ345
は“2"である。第５図は、この時点における前記諸チエ
インを示す。

以上に述べた例における条件を変えて、もしも保証ペー
ジ数が“1"であつたとすれば、ステツプ４のGET−BUFFE
R処理410における判断412に際して、エントリバツフア
数343は“2"で、保証ページ数“1"よりも大きい。その
結果、処理413の代りに処理414に進み、リレーシヨンLR
Uチエイン〔→BE310→BE320〕の中で、ページアクセス
カウンタが“0"のBEが探索される。しかし、ページアク
セスカウンタ316,326は共に“4"なので、末尾にあるBE3
20が選択される。したがつて、PAGE−OUT処理420におい
て、BE320のページアクセスカウンタ326が“1"を減じら
れて、“3"になり（421〜423）、このBE320に対応する
バツフアがリプレース（424,431）の対象となる。

また、もしもローアクセスカウンタ345の初期設定値が
“2"であつたとすれば、ステツプ３における処理405の
結果、ローアクセスカウンタ345は“0"になり、したが
つて、処理406,407により、リレーシヨンLRUチエインが
解放され、ページアクセスカウンタ316,326は共に“0"
に設定される。この場合、ステツプ４の遂行に際して、
リレーシヨンLRUチエインは存在しないから、RCBのエン
トリバツフア数343の値の如何にかかわらず、処理412,4
13により、LRUチエインからリプレース対象バツフアが
選択される。

本発明のバツフア管理方法は、統計情報を用いたルール
とコスト評価との併用に限らず、適当なデータベース参
照特性情報を与える内部処理手順が得られるものであれ
ば、他の方法（例えば、コスト評価のみ、ヒユーリステ
イツクス、コスト評価とヒユーリステイツクスの併用な
ど）による最適化処理を行なうDBMSにも適用できる。

いずれの発明も、大型計算機のソフトウエアシステムを
介して実現することも、また、各部のために専用プロセ
ツサが用意された複合プロセツサシステムを介して実現
することも、可能である。

〔発明の効果〕

本発明の問合せ処理方法によれば、問合せ処理手順決定
のためのルールベースが、新しい問合せを処理するたび
にダイナミツクに改善を重ねることにより、システムの
利用環境に適合するように補充・整備され、したがつ
て、固定的なルールによるものと比較して、大幅な性能
向上が期待できる。

また、本発明のバツフア管理方法によれば、バツフアの
リプレース制御が個々の問合せの処理手順に適合した手
順で行なわれ、その結果、バツフアの効率が改善され、
ひいては、問合せの処理を、従来よりも高速・低コスト
で行なうことができる。

【図面の簡単な説明】

第１図は第１発明の一実施例が適用されたデータベース
管理システムのブロツクダイヤグラム、第２図は第１図
中のコスト評価最適化部のブロツクダイヤグラム、第３
図は第１図と第２図に示されたデータベース管理システ
ムにより行なわれる問合せ処理のフローチヤート、第４
図は第２発明の一実施例が適用されたデータベース管理
システムのブロツクダイヤグラム、第５図は第４図中の
バツフア制御部が管理するバツフア制御情報の模式図、
第６図は第４図中のバツフア制御部により行なわれるバ
ツフア制御のフローチヤート、第７図は実施例の説明に
用いられるリレーシヨンの模式図である。２……データベース管理システム、４……論理処理部、
41……問合せ解析部、42……問合せ処理最適化部、42a
……第１ルールベース管理部、43……コード生成・論理
処理実行部、５……物理処理部、51……バツフア制御
部、６……コスト評価最適化部、69……第２ルールベー
ス管理部、７……データベース、８……データベースバ
ツフア。

Claims

【特許請求の範囲】

【請求項１】データベースに対するユーザからの問合せ
を解析して回答に必要な情報を前記データベースから得
るための内部処理手順を決定しそれを実行するデータベ
ース処理装置において行なわれる、データベースシステ
ムの統計情報と問合せの解析結果とから単一の内部処理
手順を与える第１ルールベースにより単一の実行される
べき内部処理手順を選定する第１の選定過程と、データ
ベースシステムの統計情報と問合せの解析結果とから個
数に制約なしに内部処理手順を与える第２ルールベース
により少なくとも一つの擬似内部処理手順を選定する第
２選定過程と、前記第１及び第２選定過程で選定された
内部処理手順を評価比較する過程と、前記評価比較の結
果に応じて前記第１ルールベースを前記第２ルールベー
スの内容に基づいて修正する過程とを含む、データベー
ス管理方法。
【請求項２】特許請求の範囲第１項において、その統計
情報はデータベースシステムの処理能力を示すシステム
特性とデータベースの構成を示すデータベース特性と利
用可能な処理機能を示す処理方式特性とに関する情報を
含み、その内部処理手順の評価比較は各内部処理手順の
実行にかかるコストについて行なわれる、データベース
管理方法。
【請求項３】データベースに対するユーザからの問合せ
を解析して所要情報を前記データベースから得るための
内部処理手順を決定し、それを外部記憶装置に蓄積され
たデータベースデータの一部を写しを一時的に保持する
バツフア群を用いて実行するデータベース処理装置にお
いて行なわれる、データベースシステムの統計情報と問
合せの解析結果とから最適内部処理手順を決定する過程
と、前記の決定された内部処理手順から得られるデータ
ベースアクセスの態様を示すデータベース参照特性情報
をバツフア制御情報として設定する過程と、前記の設定
されたバツフア制御情報を用いて前記バツフア群のリプ
レースを制御するリプレース制御過程とを含む、データ
ベース管理方法。
【請求項４】特許請求の範囲第３項において、そのデー
タベースは複数のリレーシヨンを含むリレーシヨナルデ
ータベースであつて、各リレーシヨンは複数のローから
なり、前記外部記憶装置と前記バツフア群の間のデータ
授受が所定サイズのデータブロツクであるページを単位
として行なわれ、そのリプレース制御過程は、処理対象
リレーシヨンのうちで相対的に短期間に順次アクセスさ
れるリレーシヨンのページを保持するバツフアをそれぞ
れのリレーシヨンに対応して形成されるリレーシヨンLR
Uチエインに組込む過程と、何らかのページを保持する
バツフアのすべてを単一のLRUチエインに組込む過程
と、前記リレーシヨンLRUチエインのどれかに含まれる
ページの数が前記バツフア制御情報に含まれる予め定め
られた値よりも大きいときにそのリレーシヨンLRUチエ
インに含まれるバツフアからリプレースの対象を選択
し、さもなければ前記単一のLRUチエインに含まれるバ
ツフアからリプレースの対象を選択する過程を含む、デ
ータベース管理方法。
【請求項５】特許請求の範囲第４項において、そのバツ
フア制御情報は各ページについて予想されるページアク
セス回数を含み、そのリプレース制御過程は各ページが
リプレースされるたびに対応する前記ページアクセス回
数を１だけ減ずる過程を含み、リプレースの対象を選択
する過程において、前記ページアクセス回数が０のペー
ジが優先的に選択される、データベース管理方法。
【請求項６】特許請求の範囲第５項において、そのバツ
フア制御情報は前記リレーシヨンLRUチエインのそれぞ
れに含まれるページについて予想されるローアクセス回
数を含み、そのリプレース制御過程は各リレーシヨンLR
Uチエインに含まれるページにアクセスがあるたびに対
応する前記ローアクセス回数を１だけ減じてそれが０に
なつた時にそのリレーシヨンLRUチエインを解放する過
程を含む、データベース管理方法。