米国特許情報 | 欧州特許情報 | 国際公開(PCT)情報 | Google の米国特許検索
 
     特許分類
A 農業
B 衣類
C 家具
D 医学
E スポ−ツ;娯楽
F 加工処理操作
G 机上付属具
H 装飾
I 車両
J 包装;運搬
L 化学;冶金
M 繊維;紙;印刷
N 固定構造物
O 機械工学
P 武器
Q 照明
R 測定; 光学
S 写真;映画
T 計算機;電気通信
U 核技術
V 電気素子
W 発電
X 楽器;音響


  ホーム -> 計算機;電気通信 -> 株式会社日立製作所

発明の名称 データベース処理方法
発行国 日本国特許庁(JP)
公報種別 公開特許公報(A)
公開番号 特開平6−4587
公開日 平成6年(1994)1月14日
出願番号 特願平4−157032
出願日 平成4年(1992)6月16日
代理人 【弁理士】
【氏名又は名称】富田 和子
発明者 中野 幸生 / 根岸 和義 / 安良岡 フミエ / 市川 湖菜美
要約 目的


構成
DBMS110内コンパイル処理111にて、入力されるコマンド100について問合せ解析112を行い、処理手順候補選出113にて条件に変数を含む場合、変数の値により最適となり得る処理手順全てを候補として登録しておき、問合せ実行時に、実行要求116、解釈、実行117で登録した全ての処理手順を同時に並列に実行させ、結果受け取り制御118で一番速く得られた結果をユーザに返す。
特許請求の範囲
【請求項1】デ−タベースに対するユーザからの変数を含む問合せに対して、そのコンパイル時の過程として、前記問合せの解析を行う過程と、該解析の結果に応じて複数の内部処理手順候補を選出する過程と、該候補に選出された内部処理手順を作成する過程と、前記問合せの実行時の過程として、同時に複数の処理手順を実行できるマルチプロセッサ環境において前記作成した複数の内部処理手順全てを同時に並行して実行する過程と、一番早く得られた内部処理手順の実行結果をユーザに返す過程とを備えたことを特徴とするデータベース処理方法。
【請求項2】前記解析を行う過程と複数の内部処理手順を作成する過程とは、複数のプロセッサのうちの1つで処理し、前記並行して実行する過程は複数のプロセッサで処理することを特徴とする請求項1記載のデータベース処理方法。
【請求項3】問合せに変数を含むか否かを判定する過程と、変数を含まない問合せに対してデータベースシステムの統計情報に基づき前記複数の内部処理手順候補の各々の処理コストを算出する過程とをさらに備え、変数を含まない問合せに対しては、前記内部処理手順を作成する過程では最小の処理コストを有する内部処理手順候補の内部処理手順を生成し、前記実行する過程では当該生成された単一の内部処理手順を前記複数のプロセッサのうちの1つで実行することを特徴とする請求項1記載のデータベース処理方法。
【請求項4】デ−タベースに対するユーザからの変数を含む問合せに対して、そのコンパイル時の過程として、該問合せの解析を行う過程と、該解析の結果に応じて複数の内部処理手順候補を選出する過程と、データベースシステムの統計情報に基づき変数値範囲に応じた各内部処理手順候補の処理コストを算出する過程と、該処理コスト算出の結果、変数値範囲に応じて選択すべき内部処理手順を定めた内部処理手順選択基準を作成する過程と、問合せ実行処理時に選択基準を用いて内部処理手順を選ぶための処理コストと前記選択基準の各コストとの和を求める過程と、該処理コストの和と前記各内部処理手順候補の処理コストとを比較する過程と、該比較の結果、いずれかの前記内部処理手順候補の処理コストが前記処理コストの和より優る場合、当該内部処理手順候補を登録し、優らない場合、前記複数の内部処理手順候補すべてを登録する過程と、該登録された候補の内部処理手順を生成する過程と、問合せの実行時の過程として、生成された内部処理手順が1つか否かを判定する過程と、複数あれば、与えられた変数値を前記選択基準に照らしあわせることにより当該複数の内部処理手順のうちの1つを選択する過程と、選択された内部処理手順を実行する過程とを備えたことを特徴とするデータベース処理方法。
【請求項5】前記登録する過程において、前記処理コストの和より優る処理コストを有する内部処理手順候補が複数存在する場合には、各内部処理手順候補の処理コストにつき前記処理コストの和に対する差分の平均を求め、該差分の平均が最大となる1つの内部処理手順候補を登録することを特徴とする請求項4記載のデータベース処理方法。
【請求項6】コンパイル時に前記変数が各値を取る確率が与えられている場合、前記比較する過程および登録する過程に代えて、前記選択基準の各変数値範囲に対して処理コストが最小となる変数値が入力される確率を求め、該確率を内部処理手順毎に合計する過程と、該合計値をしきい値と比較する過程と、いずれの合計値もしきい値より小さい場合、すべての内部処理手順候補を登録し、合計値のいずれかがしきい値より大きい場合、その中で合計値が最も大きい内部処理手順候補を登録する過程とを備えたことを特徴とする請求項4記載のデータベース処理方法。
【請求項7】コンパイル時に変数が各値を取る確率が与えられている場合、前記比較する過程および登録する過程に代えて、前記選択基準の各変数値範囲に対して処理コストが最小となる変数値が入力される確率を求める過程と、前記処理コストと前記処理コストの和との差分による改善コストを求める過程と、該改善コストと前記確率を求める過程で求められた確率とから改善コストの期待値を各処理手順毎に求める過程と、該期待値をしきい値と比較する過程と、いずれの期待値もしきい値より小さい場合、すべての内部処理手順候補を登録し、期待値のいずれかがしきい値より大きい場合、その中で期待値が最も大きい内部処理手順候補を登録する過程とを備えたことを特徴とする請求項4記載のデータベース処理方法。
発明の詳細な説明
【0001】
【産業上の利用分野】本発明は、デ−タベ−ス処理装置に関し、特にリレ−ショナルデ−タベ−ス管理システムに適した問合せの処理に好適なデ−タベ−ス処理方法に関する。
【0002】
【従来の技術】従来、リレーショナルデータベース管理システム(DBMS)においてユーザからの問合せを解析して対応する内部処理手順を決定しそれを実行するためには、特開平1−194028号公報に示されているように、コンパイル時に複数の内部処理手順を選定し、問合せ実行時に代入される値から、最適な内部処理手順を選択して実行する方式が採用されていた。コンパイル時に値が確定せず実行時に設定される変数として、ユーザからの問合せに含まれる変数、実行時のプロセッサ性能などがある。
【0003】
【発明が解決しようとする課題】従来技術では、これら変数等を含む問合せについて、検索条件式を満足するデ−タの割合等をコンパイル時に見積もることができず、最適な処理手順をコンパイル時に生成するのは困難であった。そのため、前述のように内部処理手順を予め単一あるいは複数の実行形式に展開しておき、検索実行時に最適な処理手順を選択し実行していた。しかし、(1)検索実行時毎に前記最適処理手順選択処理を行わなければならない、(2)処理手順選択処理の負荷のために却って処理性能が低下する場合がある、等の問題があった。
【0004】本発明は、上記従来技術についての問題を解決し、問合せ処理の性能向上を実現することができるデータベース処理方法を提供することにある。
【0005】
【課題を解決するための手段】本発明によるデータベース処理方法は、デ−タベースに対するユーザからの変数を含む問合せに対して、そのコンパイル時の過程として、前記問合せの解析を行う過程と、該解析の結果に応じて複数の内部処理手順候補を選出する過程と、該候補に選出された内部処理手順を作成する過程と、前記問合せの実行時の過程として、同時に複数の処理手順を実行できるマルチプロセッサ環境において前記作成した複数の内部処理手順全てを同時に並行して実行する過程と、一番早く得られた内部処理手順の実行結果をユーザに返す過程とを備えたものである。
【0006】本発明による他のデータベース処理方法は、デ−タベースに対するユーザからの変数を含む問合せに対して、そのコンパイル時の過程として、該問合せの解析を行う過程と、該解析の結果に応じて複数の内部処理手順候補を選出する過程と、データベースシステムの統計情報に基づき変数値範囲に応じた各内部処理手順候補の処理コストを算出する過程と、該処理コスト算出の結果、変数値に応じて選択すべき内部処理手順を定めた処理手順選択基準を作成する過程と、問合せ実行処理時に選択基準を用いて内部処理手順を選ぶための処理コストと前記選択基準の各コストとの和を求める過程と、該処理コストの和と前記各内部処理手順候補の処理コストとを比較する過程と、該比較の結果、いずれかの前記内部処理手順候補の処理コストが前記処理コストの和より優る場合、当該内部処理手順候補を登録し、優らない場合、前記複数の内部処理手順候補すべてを登録する過程と、該登録された候補の内部処理手順を生成する過程と、問合せの実行時の過程として、生成された内部処理手順が1つか否かを判定する過程と、複数あれば、与えられた変数値を前記選択基準に照らしあわせることにより当該複数の内部処理手順のうちの1つを選択する過程と、当該内部処理手順を実行する過程とを備えたものである。
【0007】
【作用】本発明の第1の方法による問合せの検索実行処理では、複数の内部処理手順を同時に並列に実行させるので、実行時に複数の内部処理手順から最適なものを選択して実行するのと比較して、複数の処理を並列に実行できる環境を必要とするが、検索実行のための前処理(検索実行時毎の最適処理手順選択処理)の負荷を削除できる。
【0008】また、本発明の第2の方法では、変数の各値に対して各処理手順の実行コストのうち最小のものを見積り、それに実行時の選択に要するコストを加えたコストと、ある処理手段を場合の変数の各値に対するコストの最大値を比較し、前者が大なら後者の固定的な処理手順を採用し、実行時にはその処理手順を実行する。この方法によれば、検索実行時に処理手順選択処理の負荷のために却って処理性能が低下するような事態を回避することができる。
【0009】
【実施例】以下、本発明の実施例を図面に基づいて詳細に説明する。
【0010】図2に、本発明の第1の実施例のハードウエア構成を示す。本実施例は、並列実行を実現するためにマルチプロセッサ構成とする。具体的には主記億210を共有する複数のプロセッサ1(240)〜プロセッサn(260)からなる処理装置200とディスク装置(DISK)230とからなる。処理装置200内の各プロセッサからのDISK230へのデータアクセス要求は経路220を介して行われ、その際、データ転送、制御データ交換が行われる。主記億210内にはリレーショナルデータベース管理システム(DBMS)110が格納されており、プロセッサ1(240)〜プロセッサn(260)において、並列に実行することができる。DISK230内には、テーブル、統計情報等を含むデータベース140が蓄積されている。
【0011】図1に、第1の実施例におけるDBMSの処理の概要を模式的に示す。図1のコマンド例100は、2つの選択条件「C1=?」と「C2=?」とが論理積で結合された検索条件式から成る。選択条件式の「?」は、実行時に値が代入されることを示す。本実施例では条件として指定できるものを、論理積(AND)で結合した=、<=のような比較条件に限定して以下説明を行う。
【0012】DBMS110の処理は、問合せ実行前に行われるコンパイル処理111と問合せ実行時に行われる問合せ実行処理115とから成っている。またDBMS110の処理は、特定のプロセッサ1で実行される部分161、およびプロセッサ1以外のプロセッサ2〜4でそれぞれ実行される部分162〜164よりなっている。コンパイル処理111は、入力されたコマンドの解析を実行する問合せ解析112と、処理手順の候補を選出する処理手順候補選出113、前過程で選出された候補を実行形式に展開する処理手順生成114とから成る。
【0013】処理手順候補選出113の詳細は下記の通りである。(1)コマンドで出現する各種条件式から条件を満足するデ−タの割合(これを、述語選択率、あるいは単に選択率とも言う)を後述する条件選択率表120により推定する。(2)予め設定している規則を利用し、デ−タベ−ス特性(デ−タベ−ス中の各種デ−タサイズ、デ−タベ−スの物理構造、インデクスの種類や有無等)やシステム特性(バッファサイズ、プロセッサ性能等)に関する情報を用いて有効な処理手順候補を絞る。(3)入出力回数、プロセッサ使用時間等コスト評価を行い、処理手順の候補を作成する。
【0014】問合せ実行処理115は、実行時に代入された値を各処理手順に反映し、上記過程114で作成された全ての処理手順について実行を要求する実行要求116と、実行要求のあった処理手順を解釈、実行する解釈実行処理117a〜c、実行結果を受け取りユーザに返す結果受け取り制御118とから成る。解釈実行処理117a〜cはそれぞれプロセッサ2〜3により各処理手順毎に並列に独立して実行される。
【0015】デ−タベ−ス140には、テ−ブル141及び統計情報管理テ−ブル142が蓄積されている。統計情報管理テ−ブル142は、テーブルのサイズ、テーブル内データ数、テ−ブルを構成するカラム値の出現回数情報を設定している。条件選択率表120は、コマンド例100で出現する条件式の選択率(テーブル中の条件式を満たすデータの割合)を評価した結果である。処理手順候補表130は、処理手順候補選出113で選択された処理手順を登録している。内部処理手順150は、過程114で生成された複数の処理手順1,2,3(151,152,153)である。
【0016】次に具体的なコマンドの処理フローを図3,図4に示し、図1,図15〜図17を参照しながら説明する。
【0017】コマンド例100がDBMSに入力され、コンパイル処理111がプロセッサ1上で実行される。この例では、カラムC1、C2ともインデクスが存在するものとする。図3(a)の問合せ解析112では、コマンドの構文解析、意味解析処理を行う。構文解析では問合せ文をキーワードに分割し(301)、本DBMSで定められた構文規則通りに記述されているか検査を行い(302)、構文規則に反していればエラーを返す(303)。キーワードに分割された問合せは、解析木と呼ぶ図16(a)の木構造の形式に変換する(304)。コマンド例100では、図16(b)の様な解析木に変換される。意味解析では、解析木に現れるテーブル、カラム等が実際に存在するものかチェックする(305,306)。図16(b)では、テーブルT、カラムC1,C2が指定されているので、それぞれが実際に存在するかチェックする。存在しないテーブル、カラムが指定されていたならば、エラーを返す(307)。解析木中の条件を条件選択率表120に登録する(308)。コマンド例100では、二つの条件式C1=?,C2=?が登録される。
【0018】次に、図3(b)の処理手順候補選出113が行われる。処理手順候補選出113では、まず条件選択率表120に登録された条件式の選択率が算出される。条件式のカラムについて統計情報があるかチェックし(311)、各条件式に定数が出現するかをチェックする(312)。条件式のカラムについて統計情報があり、変数を含まない条件であれば、選択率が決定できる(313)。コマンド例100では、両選択条件式とも変数を含むので、図1の条件選択率表120に示すように選択率が決定できない。
【0019】選択率が決定できる場合の選択率の算出は、統計情報142のカラム値出現回数を使って求める。カラム値出現回数は、カラム全体を等間隔に分割して、分割した区間毎に、区間内の最大値、最小値、ユニークな値の数を取得したものである。ユニークな値が小さいほど、重複したカラム値が多いことになる。図15に一例として示したC1カラムについてのカラム値出現回数は、150個のデータを50個(値数)毎に3分割したものである。最初の50個の区間についてみれば、最小値が0、最大値が50であり、50個のうちユニークな値が48個あることを示す。この情報より、=条件の選択率は、最小値≦条件の値≦最大値となる区間を求め、(区間のデータ数/ユニークな値)を全体の個数で割ることにより求める。図15でC1=10という条件であれば、10が含まれる第1の区間の値により選択率は(50/48)/150であり、C1=60という条件であれば選択率は(50/23)/150といった様になる。このように求められた選択率は、後述する処理手順候補のコスト値算出に用いられる。
【0020】図3に戻り、次に、入力されたコマンドを実行するのに用いる処理手順を選出する。本処理は、その問合せ実行に有効な可能性のある処理手順を選びだすものである。まず、問合せ中の各条件カラムについてのインデクスを使ったアクセスが候補となる(315)。そして、テーブル全体のアクセスを最後に加える(316)。インデクスを使ったアクセスは、そのカラムについてのインデクスが存在する必要があるので、インデクスの存在をチェックし、インデクスがなければそのインデクスを使ったアクセスは候補としない。この例では、C1インデクス、C2インデクスが存在するので処理手順候補として、C1インデクスを利用して条件評価を行うC1インデクスアクセス、C2インデクスを利用するC2インデクスアクセス、テーブルT全体をアクセスをして条件評価を行うテーブルアクセスの3つのアクセスを処理手順候補とする。次に、各処理手順候補の処理コストの値を算出する(317)。処理コストは、問合せを実行した際のステップ数、I/O回数、処理時間等により定まる。本実施例ではステップ数をコストとして説明を行う。コスト算出式は、プログラムの解析、トレース情報などをもとに、射影カラム数、条件選択率、テーブル全体のサイズ、条件数等を変数として予め作成しておく。コスト算出時にこれらの変数に値を割り当てることにより、コスト値が求められる。なお、条件に変数を含む場合、このコスト算出はできない。本発明では、条件に変数を含む場合を前提としているので、このコスト算出式の具体的な説明は割愛する。条件に変数を含まない問合せであれば(318)、処理コストが最も小となる処理手順を選出する(320)。この例では、条件選択率表120において両条件式の選択率が決定できないのでコスト値は算出できない。そこで3つの処理手順をすべて処理手順候補表130に登録する(319)。
【0021】図4に移り、最後に処理手順生成114で、処理手順候補表130を基に、処理手順を生成する。すなわち、各処理手順候補を実行するのに必要なバッファサイズを算出し(331)、処理手順の実行形式を生成する(332〜337)。バッファサイズは、検索結果を格納するためのバッファのサイズである。本サイズの見積りは、テーブルサイズと全ての条件を合わせた選択率より求める。テーブルサイズ*選択率で求められる。この選択率は条件全てを合わせた選択率であるので、条件選択率表120に設定した全ての選択率の積により求める。ただし、変数を含む問合せは選択率が求められないので、テーブルサイズをバッファサイズとする。処理手順の実行形式は、各アクセス方式毎に予め作成してある図17のような実行形式の基本型に、本問合せの情報を代入することにより作成される(333−1,333−2)。テーブルアクセスの処理手順には、射影カラム(334−2)、アクセスするテーブル(335−2)、アクセス条件(336−2)を設定し、インデクスアクセスの処理手順には、射影カラム(334−1)、アクセスするインデクス(335−1)、インデクスアクセス時に評価する条件(336−1)、その他の条件(337)を設定する。図1のC1インデクスアクセスに対応する処理手順1(151)は、インデクスアクセスの基本型(図17(b))に、射影するカラム:C1、アクセスするインデクス:C1インデクス、インデクスアクセス時の条件:C1=?、その他の条件:C2=?を設定したものである。C2インデクスアクセスに対応する処理手順2(152)はC1インデクスアクセスと同様の処理により作成される。テーブルアクセスに対応する処理手順3(153)は、テーブルアクセスの基本型(図17(a))に射影カラム:C1、アクセスするテーブル:T、条件:C1=? & C2=?を設定したものである。
【0022】次に、図4(d)〜(f)により問合せ実行処理115について説明する。ユーザより検索要求が指示されると、図4(d)に示すように実行要求116において、コンパイル時に作成した処理手順の実行要求を行う(341)。図2のハード構成上で考えると、プロセッサ1上で動作している実行要求116に応答して、図4(e)に示すように解釈実行117a〜cへの実行要求が行われ、プロセッサ2,3,4において、それぞれ所定のバッファを取得した後(351)、処理手順1,2,3が解釈実行117a〜cにより並行に実行される(352)。処理手順を一通り実行し終わると検索結果が得られる。検索結果を得ると、結果とともに検索終了を結果受け取り制御118に連絡する(353)。最初にプロセッサ2の処理手順1の実行が終わったとすると、プロセッサ2からりプロセッサ1の結果受け取り制御118に対して実行の終了が報告される。結果受け取り制御118は、図4(f)に示すように、各解釈実行117a〜cからの終了連絡を待ち(361)、一番最初に受け付けた終了連絡の実行結果のみをユーザに返す(362)ので、プロセッサ2より受け付けた結果をユーザに返し、後から送られてくるプロセッサ3,プロセッサ4の結果を無効にする(363)。
【0023】次に本発明の第2の実施例に関し、図5〜図9により説明する。本実施例は、第1の実施例と異なり、単一のプロセッサを用いるものである。
【0024】図9に、本発明が適用されるハードウエア構成の一例を示す。本システムは、主記億710とプロセッサ740とを備える処理装置700と、ディスク(DISK)730とからなる。処理装置700内プロセッサ740からのDISK730へのデータアクセス要求は経路720を介して行なわれ、データ転送、制御データ交換が行われる。主記億710内にDBMS410が格納されている。DISK730内には、テーブル、統計情報等のデータベース440が蓄積されている。
【0025】図5に、本実施例におけるDBMS410の処理の概要を模式的に示す。コマンド例400が、DBMS410に入力され、コンパイル処理411が実行される。コンパイル処理411では、まず、入力されたコマンドの問合せ解析412を行い、次に処理手順候補の選出413を行い、最後に、選出された処理手順候補を実行手順に展開する処理手順生成414を行う。
【0026】処理手順候補選出413では、次の処理(1)〜(7)を行う。
(1)、コマンドに出現する条件の選択率を求める。
(2)、予め設定している規則を利用して、データベース特性やシステム特性に関する情報を用いて有効な処理手順候補を絞る。
(3)、入出力回数、プロセッサ使用時間等に基づくコスト評価を行い、処理手順の候補を作成する。
(4)、問合せが変数を含む場合、処理手順を絞り込めないので、変数値によりどの処理手順を実行するかを定める判定基準を作成する。
(5)、(4)で作成した判定基準を評価するためのコスト値を算出し、各処理手順実行のコスト値と合計する。
(6)、(3)のコスト評価表より、(4),(5)で求めた判定基準評価のコスト値を含めた変数値の各値ごとの最適コスト値と比較して、変数値の全ての値でコスト値が小さくなる処理手順をさがしだす。
(7)、(6)の条件を満たす処理手順が見つかった場合、その処理手順のみを登録する。それ以外の場合は、判定基準に設定した処理手順を全て候補とする処理が行われる。
【0027】問合せ実行処理415では、実行時に代入された値を処理手順に反映し、登録されている処理手順が1個ならばその処理手順を解釈、実行する。すなわち、処理手順が複数登録されているなら、選択基準表と変数の値より、最適な処理手順を選び出し(処理手順選出416)、選ばれた処理手順を解釈、実行する(解釈、実行処理417)。処理手順実行により得られた結果をユーザに返す。
【0028】次に具体的なコマンドの処理フローを図7、図8により説明する。コマンド例400がDBMSに入力され、コンパイル処理411が実行される。この例ではC1、C2ともインデクスが存在するものとする。
【0029】まず、図7(a)に示す問合せ解析412で、実施例1と同様の解析処理が行われる。この各過程601〜608は、図3(a)に示した各過程301〜308と同一なので説明を省略する。
【0030】次に図7(b)に示す処理手順候補選出413では、まずコマンドに出現する条件式の選択率が算出される。そのために条件式のカラムについて統計情報があるかチェックし(611)、各条件式に定数が出現するかをチェックする(612)。条件式のカラムについて統計情報があり、変数を含まない条件であれば、選択率が決定できる(613)。コマンド例400では、両選択条件式とも、変数を含むので条件選択率表420(図5)に示すように選択率が決定できない(614)。次に、入力されたコマンドを実行するのに用いる処理手順を選出する。処理手順の候補は、各条件カラムのインデクスを利用するインデクスアクセス(615)、テーブル全体をアクセスするテーブルアクセス(616)を候補とする。そして、条件に変数を含まない問合せであれば、各候補の処理コストを求め(617,618)、処理コストが最も小となる処理手順を優先的に選出する(620)。しかし、この例では、条件選択率表420において両条件式の選択率が決定できないので処理コストが算出できず、次の3つの処理手順を処理手順候補表430(図5)に登録する。すなわち、C1インデクスを利用して条件評価を行うC1インデクスアクセス(処理手順1)、同様にC2インデクスを利用するC2インデクスアクセス(処理手順2)、テーブルT441全体をアクセスし条件評価を行うテーブルアクセス(処理手順3)の3つである。次に、統計情報442(図5)のカラム値出現回数を利用して、カラム値区間毎の各処理手順のコスト値を算出し、区間毎にコスト値が最小となる処理手順を処理手順選択基準に登録する(619)。
【0031】例えば、図6(a)に示すようなコスト評価結果が得られた場合、C1の変数値が0〜50,C2の変数値が60〜100のときと、C1の変数値が50〜90,C2の変数値が60〜100のときは処理手順1が最小の処理コストを有する。C1の変数値が0〜50,C2の変数値が0〜60のときと、C1の変数値が50〜90,C2の変数値が0〜60のときと、C1の変数値が90〜100,C2の変数値が0〜90のときは処理手順2が最小処理コストを有する。さらに、C1の変数値が90〜100,C2の変数値が60〜100のときは処理手順3が最小処理コストを有する。したがって、それぞれの場合に最小処理コストを有する処理手順を選ぶとよいことがわかる。この結果を処理手順選択基準450(図5)とする。なお、問合せ実行時に処理手順を選び出す処理にも時間を要するので、そのコストを10とする。このコストを加えた各処理手順実行コストは図6(b)のようになり、変数の値に応じて最適な処理手順を選択した場合のコスト値は図6(c)のようになる(図7,621)。
【0032】図8のフローへ移行し、図6(a)の各処理手順の各コスト値が図6(c)の対応する最小コスト値より全て小さくなる(または同じ)処理手順がないか、チェックする(622)。これは、選択処理のコストまで考慮すると、却って選択処理を行わない場合より結果が悪くなる場合があるからである。図6(c)のすべての最小コスト値を超えないコスト値をもつ処理手順が存在しない場合は、処理手順候補全てを登録する(624)。そのような処理手順が1つだけあれば(628)、その処理手順のみを登録する(625)。本例の場合には、図6(a)の処理手順1の各コスト値はいずれも図6(c)の対応するコスト値を超えない。図6(a)の処理手順2も同様である。すなわち、図6(c)の全ての最小コスト値より小さいコスト値を有する処理手順が複数存在する。このような場合、図6(a)の各処理手順について、その各コスト値と図6(c)の対応するコスト値の差分をとり、その差分の平均値を図6(d)のように求める(626)。次にその平均の最も大きなものを登録する(627)。本例では、処理手順1の差分平均値の方が処理手順2のそれより大きいので処理手順1が選択され、登録される。
【0033】図8(c)の処理手順生成414では、登録された処理手順候補について、必要なバッファサイズを算出し(631)、実行形式を生成する(632)。上記例では、処理手順1についてのみ実行形式が生成される。選択率、コスト算出処理及び処理手順生成処理の詳細は第1の実施例の処理と同様である。
【0034】続く問合せ実行処理415では、まず図8(d)の処理手順選出416で、処理手順候補の数を調べる(641)。候補が1個の場合その処理手順を実行させる。複数の候補がある場合、変数値と処理手順選択基準により最適処理手順を選出する(642)。上記例では、処理手順1一個なので処理手順1が実行される。以下、図8(e)の解釈実行417で、前記選ばれた処理手順につきバッファが取得され(651)、解釈、実行され(652)、実行結果がユーザに返される(653)。上記例では処理手順1の実行結果がユーザに返される。
【0035】次に、図5,図10,図11により、第2の実施例の拡張である第3の実施例を説明する。
【0036】まず、ユーザより各変数の各変数値(変数値範囲)の入力される確率、後述する確率の合計値のしきい値を得ておき、第2の実施例同様に、問合せ解析412、処理手順選出413の処理手順選択基準作成まで行い(図7フロ−611〜621)、コスト評価結果は、各処理手順の処理コストを図11(a)のように求め、処理手順選択基準とその処理コストに問合せ実行時に処理手順選択処理実行に必要な処理のコストを加算したものを図11(b)のように求める(図7の(621))。以下、図7、図8のフロ−を変更して、図12のフローのようにユーザより入力された変数値の入力される確率より、各変数値の組合せが指定される確率を求める(1001)。図10(a),(b)のように、C1,C2の変数値入力確率が与えられた場合、図10(c)のように組合せの確率が求まる。各変数値に対してその処理手順のコストが最小となる変数値が入力される確率の合計値を出す(1002)。この合計値が、その処理手順を実行した場合にある変数の値の組合せについて、最小コストの処理手順になる確率である。処理手順1について考えてみると、処理手順1のコストは、C1が0〜50でC2が60〜90と90〜100のときと、C1が50〜90でC2が60〜90と90〜100のとき小さくなる。各値が入力される確率はそれぞれ0.02であるので、合計0.08になる。同様に処理手順2、3についても計算を行うとそれぞれ0.80,0.12といった結果になる(図10(d))。ここで、この値がユーザの指定したしきい値より大きい処理手順が存在するか否かを調べ(1003)、存在する場合、合計値が最も大きい処理手順のみを候補として登録する(1005)。しきい値より大きい合計値がなければ、処理手順候補全てを登録する(1004)。登録された処理手順について、処理手順生成が行われる。図10(d)の結果の例では、しきい値に0.80以下の値が設定されたとすると、処理手順2のみが候補として登録される。
【0037】問合せ実行時には、登録された処理手順が1個であれば、その手順を解釈、実行し、複数の処理手順が指定されていれば選択基準より最適な処理手順を選択し、選択した処理手順を解釈実行する。
【0038】なお、ユーザよりしきい値を与えるのではなく、予め定めた値として処理を行う方式も考えられる。
【0039】図13、図14により、第3の実施例の変形である第4の実施例について説明する。第3の実施例における図12のかわりに図13の処理を行う。各変数の組合せの確率を図10(c)のように求める(1101)。次に、変数の値毎に改善コストを図11の(b)と(a)の差分を計算することにより、図14(a)のように求める(1102)。図14(a)の改善コストと図10(c)の各変数の組合せの確率を掛け合わせることにより、各処理手順の改善コスト期待値を図14(b)のように求める(1103)。この期待値がユ−ザにより与えられたしきい値より大の時(1104)、そのうち最も大きな期待値を授けられる処理手順(図14(b)の例では処理手順2)を登録し(1106)、そうでない時、処理手順候補全てを登録する(1105)。上記以外は実施例3と同じ処理を行う。
【0040】
【発明の効果】本発明によれば、マルチプロセッサ環境を利用して、コンパイル時に作成した複数の処理手順を同時に実行し、一番早く得た結果をユーザに返すことにより、また、シングルプロセッサ環境では、それに実行時の選択処理に要するコストをも加味した処理コストの導入により、問合せ実行時に余分の負荷をかけることなく、問合せ処理の性能向上させるデータベース処理方法を実現できる。




 

 


     NEWS
会社検索順位 特許の出願数の順位が発表

URL変更
平成6年
平成7年
平成8年
平成9年
平成10年
平成11年
平成12年
平成13年


 
   お問い合わせ info@patentjp.com patentjp.com   Copyright 2007-2013