(57)【要約】　　　（修正有）【課題】（１）スタースキーマのジョインを効率よく実行する。（２）処理性能とデータベースメンテナンスコストとのバランスを制御する機構を提供する。【解決手段】ファクト表１０５のカラム値から対応するレコードを引くインデックスの一つ（１０３）と、ディメンジョン表１０４のカラム値から対応するレコードを引くインデックスの一つ（１０２）を少なくとも含む複数インデックスの組合せを定義する仮想連結インデックス１０１をデータベース中に記憶し、表のジョインを要する問合せの処理の際に対応する仮想連結インデックス１０１が示すインデックス１０２、１０３を順次アクセスしてジョイン処理を実行する。【選択図】　図１
2004110219.tif 000002
【特許請求の範囲】
【請求項１】
第１の表と、該第１の表の結合対象である第２の表とを含むスタースキーマのデータベースを格納する記憶装置と、該データベースへのクライアントからの問合せを受け付け、該問合せに対する結果を該クライアントに返す管理手段を含むデータ処理システムであって、
前記第１の表の複数カラムのそれぞれ対応して、それぞれカラム値から前記第１の表のレコードを引くための第１のインデックス群を備え、
前記第２の表の複数カラムにそれぞれ対応して、それぞれカラム値から前記第２の表のレコードを引くための第２のインデックス群を備え、
前記第１のインデックス群のうちの一つと、上記第２のインデックス群のうちの一つとを少なくとも含むインデックスの組合せ特定して順次アクセスすべきインンックス群として定義した仮想連結インデックスを備え、
かつ、前記クライアントからの問合せが前記仮想連結インデックスに対応する場合に、前記仮想連結インデックスが示すインデックス群を順次アクセスして前記問合せに合致する前記第１の表のレコードをポイントし、該レコードを読み出す問い合わせ処理部を有することを特徴とするデータ処理システム。
【請求項２】
前記問合せ処理部は、前記問合せが前記仮想連結インデックスに対応するとき、前記第１の表と前記第２の表との間の結合カラムと、該問合せ処理で必要な前記結合カラム以外の前記第２の表のカラムとを構成要素とするカラムマッピングテーブルを作成する手段を有する請求項１のデータ処理システム。
【請求項３】
前記問合せ処理部は、前記問合せが前記仮想連結インデックスに対応し、前記第１の表と第２の表との間の結合カラムが前記第２の表でキーとなっていることが保証されており、かつ該問合せの処理に結合カラム以外の前記第２の表のカラムを必要としない場合に、前記第２の表で前記結合カラムをアクセスして前記第１の表のレコードＩＤリストを作成することを特徴とする請求項１のデータ処理システム。
【請求項４】
第１の表と、該第１の表の結合対象である第２の表とを含むスタースキーマのデータベースを格納する記憶装置と、該データベースへのクライアントからの問合せを受け付け、該問合せに対する結果を該クライアントに返す管理手段を含むデータ処理システムであって、
前記第１の表の複数カラムのそれぞれ対応して、それぞれカラム値から前記第１の表のレコードを引くための第１のインデックス群を備え、
前記第２の表の複数カラムにそれぞれ対応して、それぞれカラム値から前記第２の表のレコードを引くための第２のインデックス群を備え、
前記第１のインデックス群のうちの一つと、上記第２のインデックス群のうちの一つとを少なくとも含むインデックスの組合せを特定して順次アクセスすべきインデックス群として定義した仮想連結インデックスと、
予め限定された範囲内のカラム値のそれぞれに対応して、前記仮想連結インデックスの示すインデックス群を順次アクセスして生成した第１の表のレコードＩＤのリストである実体化した仮想連結インデックスとを備え、
かつ、前記クライアントからの問合せが前記仮想連結インデックスに対応する場合に、前記前記仮想連結インデックスが示すインデックス群を順次アクセスして前記問合せに合致する第１の表のレコードをポイントし、さらに、前記クライアントからの問合せの指定条件であるカラム値が前記指定された範囲内である場合に、前記実体化した仮想連結インデックスを優先して使用して第１の表のレコードをポイントし、ポイントされたレコードを読み出す問合せ処理部を有することを特徴とするデータ処理システム。
【請求項５】
第１の表に前記問合せ処理に使用可能な仮想連結インデックスが存在する場合に、
第１の表および該第１の表の前記仮想連結インデックスをアクセスし、
第２の表のレコードＩＤと、第１の表と第２の表の結合対象のカラムである結合カラムと、該問合せ処理で必要な第１の表の結合カラム以外のカラムを構成要素とする、カラムマッピングテーブルを作成する手段を有する、
請求項４記載のデータ処理システム。
【請求項６】
複数カラムのそれぞれに対応して、それぞれカラム値からレコードを引くための第１のインデックス群を備えるる第１の表と、
前記第１の表に対する結合対象であり、複数カラムのそれぞれに対応して、それぞれカラム値からレコードを引くための第２のインデックス群を備える第２の表とを含むスタースキーマのデータベースを対象とするジョイン処理方法であって、
前記第１のインデックス群うちの一つと、前記第２のインデックス群うちの一つとを少なくとも含むインデックスの組合せを仮想連結インデックスとして定義して記憶する仮想連結インデックス形成ステップと、
前記データベースへの問合せを受けたとき、前記仮想連結インデックスの利用が可能か否かを判定し、利用可能な場合に、前記仮想連結インデックスの指定する組合せのインデックスを順次アクセスすることにより特定される前記第１の表のレコードをポイントし、ポイントされたレコードを読み出す問合せ処理ステップとを有することを特徴とするデータベースのジョイン処理方法。
【請求項７】
請求項６記載のジョイン処理方法において、予め限定された範囲のカラム値のそれぞれを順次指定して前記記憶された仮想連結インデックスが示すインデックス群を順次アクセスし、これにより特定される前記第１の表のレコードＩＤのリストを前記カラム値のそれぞれに対応して記憶することにより前記仮想連結インデックスの一部を実体化するステップを、前記問合せ処理ステップに先立つステップとして更に有することを特徴とするデータベースのジョイン処理方法。
【請求項８】
受けた問合せが指定するカラム値が前記限定された範囲内にあるとき、前記仮想連結インデックスが指定する組合せのインデックスの順次アクセスに替えて前記実体化された前記仮想連結インデックスのアクセスを行うことを特徴とする請求項７記載のデータベースのジョイン処理方法。
【請求項９】
前記問合せ処理ステップは、前記第１の表と前記第２の表との間の結合カラム、前記問合せの処理に必要な前記結合カラム以外の前記第２の表のカラムとを構成要素とするカラムマッピングテーブルを作成するステップを有する請求項６記載のデータベースのジョイン処理方法。
【請求項１０】
前記カラムマッピングテーブル中から第２の表のレコードＩＤを取り出して、該レコードＩＤを用いて第２の表のレコード中の前記問合せの結果生成に必要なカラムの値を取り出し、
該カラムマッピングテーブルから、同じく該問合せの結果生成に必要なカラムの値を取り出し、
これらのカラムの値を連結して該問合せ処理結果とすることを特徴とする請求項９記載のデータベースのジョイン処理方法。
【請求項１１】
第１の表と、該表とジョインされる少なくとも２つ以上のジョイン対象表とのジョイン処理方法において、
第１の表のレコードＩＤと、第１の表と前記ジョイン対象表の結合対象のカラムである結合カラムが、該ジョイン対象表でキーとなっていることが保証されており、かつ前記問合せ処理で結合カラム以外の該ジョイン対象表のカラムを必要としない場合に、第１の表のレコードＩＤリストを作成するステップと、
それ以外の場合には、第１の表のレコードＩＤと、第１の表と前記ジョイン対象表の結合対象のカラムである結合カラムと、該問合せ処理で必要な該ジョイン対象表の結合カラム以外のカラムを構成要素とする、カラムマッピングテーブルを作成するステップと、
該ジョイン対象表に関する前記カラムマッピングテーブルが存在する場合には、該マッピングテーブル中のレコードＩＤを取り出してレコードＩＤのリストを作成するステップと、
該レコードＩＤのリストと、該ジョイン対象表に関する前記レコードＩＤリストが存在する場合には、該レコードＩＤリストとに前記問合せの条件を適用して結果となるレコードＩＤリストを作成するステップと、
該ＩＤを用いて第１の表のレコード中の前記問合せの結果生成に必要なカラムの値を取り出すステップと、
前記カラムマッピングテーブルが存在する場合には、該カラムマッピングテーブルから、同じく該問合せの結果生成に必要なカラムの値を取り出すステップと、これらのカラムの値を連結して該問合せ処理結果を生成するステップと、
を有することを特徴とするジョイン処理方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、データベースシステムのジョイン処理に係り、特にそのためのインデックス定義方法、およびそのインデックスを用いたジョイン処理の実行方法に関する。
【０００２】
【従来の技術】
業務システムのデータを格納するデータベースを設計する際に、日々追加される売上データ（レシート情報）を格納するファクト表（テーブル）と、該ファクト表の各々の属性を定義するディメンジョン表で構成されるスタースキーマを用いることが多い。スタースキーマは前記ファクト表を中心として、該ファクト表からリンクされる複数のディメンジョン表がスター型（星型）を形成することにその名前の由来があり、例えばＨｅｃｔｏｒ　Ｇａｒｃｉａ−Ｍｏｌｉｎａ，Ｊｅｆｆｒｅｙ　Ｄ．　Ｕｌｌｍａｎ，Ｊｅｎｎｉｆｅｒ　Ｗｉｄｏｍ著“Ｄａｔａｂａｓｅ　Ｓｙｓｔｅｍ　Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ”，ＰｒｅｎｔｉｃｅＨａｌｌ，ＩＳＢＮ　０１３０４０２６４８，１１．３．３節（文献１）にその構造および特徴が開示されている。
図９を用いてスタースキーマの特徴を簡単に説明する。図９に示した例では、スタースキーマは１つのファクト表ＦＴ（９０１）と、複数のディメンジョン表ＤＴ１〜ＤＴ４（９０２〜９０５）で構成されている。ファクト表ＦＴ上のカラムｃ１１〜ｃ４１は、それぞれディメンジョン表ＤＴ１〜ＤＴ４上の同名のカラムに対応し、ディメンジョン表、ファクト表間で主キー−外部キーの関係となっているのが普通である。
好適な実現例としては、ディメンジョン表ＤＴ１が製品を管理するデータを格納する表、そしてファクト表ＦＴが製品の各店舗での売上を管理するレシートデータを格納する表である構成があげられる。ＤＴ１が製品を管理するデータである場合、例えばｃ１１は製品を一意に識別する製品ＩＤで、ｃ１２以降のカラムに製品名や製品発表日などの各製品の属性が続く。製品を管理するＤＴ１上のデータは、新しい製品が開発され、販売されるタイミングで更新される。これに対して、ファクト表ＦＴは製品の各店舗での売上を管理するレシートデータであるので、情報であるとすると、店舗で１つ製品が売れるたびにＦＴに情報が追加されることとなり、その更新頻度はＤＴ１と比較して非常に高く、しかもその規模は非常に大きくなる。
実業務で蓄積されたデータに対して各種の解析処理を施し、経営戦略等の有用な情報を抽出しようとする、情報系システムが多くの企業で用いられつつある。例えば、地区Ａ内の各店舗での月単位の製品別売上を解析することにより、季節ごとの各店舗での販売戦略を検討するなど、販売データを経営戦略に直接リンクすることによって、意思決定を効率化するというのが１つの好適な例である。
実業務データを格納するスキーマの形態として、スタースキーマが用いられることが多いことから、スタースキーマを対象とした場合の解析処理の効率向上が課題となっていた。
ところが、例えば前述の製品別の売上解析を考えた場合、製品データを蓄積するディメンジョン表ＤＴ１と、店舗データを蓄積するディメンジョン表ＤＴ２と、レシートデータを蓄積するファクト表ＦＴを突合せて処理する必要がある。ここでの表同士の突合せ処理とは、突合せ対象のカラムとその突合せ条件を指定し、条件に合致したレコード（行）同士を連結して出力する処理を指す。この処理はデータベースシステムではジョイン処理と呼ばれ、非常に処理コストが高い。しかも、スタースキーマでのジョイン処理は、（１）各々のディメンジョン表はファクト表のみとしかジョインできないこと、（２）ファクト表が巨大であることから、効率的な処理が難しかった。
例えば、製品データを蓄積するディメンジョン表ＤＴ１と、店舗データを蓄積するディメンジョン表ＤＴ２と、売上データを蓄積するファクト表ＦＴの３表のジョイン処理を行うためには、直感的に以下の３つの方法が考えられる。
（１）第１のディメンジョン表ＤＴ１とファクト表ＦＴ、および第２のディメンジョン表ＤＴ２と前記ファクト表ＦＴをそれぞれジョインし、さらにその結果同士をジョインして最終結果を生成する方法。
（２）第１のディメンジョン表とファクト表ＦＴをジョインし、該ジョイン結果と第２のディメンジョン表をジョインする方法。
（３）第１のディメンジョン表と第２のディメンジョン表の直積を生成し、該直積結果とファクト表を結合する方法。
ファクト表は通常非常にサイズが大きい。（１）および（２）の方法では、第１のディメンジョン表とファクト表のジョイン結果である中間結果が非常に大きくなってしまう場合に、該中間結果同士、もしくは該中間結果と他のディメンジョン表のジョイン処理コストが大きくなってしまい、性能が極端に低下してしまうという問題があった。
一方（３）の方法は、直積を生成するディメンジョン表の数が少なく、しかも該ディメンジョン表に対する絞込み条件により、ディメンジョン表上のジョイン対象の行数が少なくなった場合には、該直積結果とファクト表を１回だけジョインすればよいため効率が良い。しかしながら、ジョイン対象のディメンジョン表数、もしくはサイズが大きくなると直積は急激に大きくなるため、性能が極端に悪化するという問題があった。
米国特許５８６４８４２号（文献２）は、ファクト表と該ファクト表にジョインされる複数のディメンジョン表間のジョイン実行方式として、Ｈａｓｈ　Ｓｔａｒ　Ｊｏｉｎ　Ｏｐｅｒａｔｉｏｎ（以下、ＨＳＪＯ）を開示している。ＨＳＪＯはファクト表をジョインカラムでハッシュ分割し、複数のディメンジョン表を１度にジョインするという特徴がある。ところが、この方式ではファクト表のジョインカラムでのハッシュ分割処理時にファクト表のスキャンを行う必要があるため、ファクト表が巨大で１回のスキャン処理も不可となる条件下では使用できないという問題がある。
米国特許ＵＳ５９６０４２８号（文献３）は、ファクト表のジョインカラムにインデックスがあり、かつディメンジョン表が条件によって強く絞り込まれる場合に有効なジョイン方式を開示している。このジョイン方式では、絞り込んだディメンジョン表のジョインカラムを取り出し、その値でファクト表のインデックスをひいてレコードＩＤを取り出し、該操作をディメンジョン表毎に繰り返して、全ディメンジョン表の条件を満足するレコードＩＤの組を作成した後に、ディメンジョン表と再度ジョインする。本方式では、ディメンジョン表の結合対象カラムの各値に対してその都度ファクト表のインデックスを引く必要がある点、およびファクト表を絞り込んだ後に絞込みを行ったファクト表とディメンジョン表を再度ジョインする必要がある点で性能改善の余地が残されている。
米国特許５８４８４０８号（文献４）は、ディメンジョン表から抽出した値でファクト表上のビットマップインデックスを利用できるように問合せを変換する、Ｓｔａｒ　Ｔｒａｎｓｆｏｒｍａｔｉｏｎ方式を開示している。この方式ではファクト表上のビットマップインデックスの存在を前提としており、適用箇所が限定されてしまうという問題、そしてディメンジョン表の更新が起こった場合の前記ビットマップインデックスのメンテナンスコストが非常に高いという問題がある。
“Ａｄｍｉｎｉｓｔｒａｔｏｒ”ｓ　Ｇｕｉｄｅ　Ｉｎｆｏｒｍｉｘ　Ｒｅｄ　Ｂｒｉｃｋ　Ｄｅｃｉｓｉｏｎ　Ｓｅｒｖｅｒ，　Ｖｅｒｓｉｏｎ　６．１”の４−６〜４−８ページ（文献５）にはスターインデックス機構が開示される。スターインデックスとは、主キーと外部キー間の参照を持つ表の間に作成するインデックスであり、ディメンジョン表のカラムの値を用いてファクト表の行を検索することができる。このスターインデックスは、ディメンジョン表とファクト表の間に主キー−外部キー制約を必要とすることと、ファクト表の更新に対するメンテナンスコストが高いという問題がある。
【０００３】
【発明が解決しようとする課題】
業務データを有効活用するための解析処理を効率よく行うために、スタースキーマでのジョイン処理を効率よく実行することが課題となっていた。さらに、データの追加および更新に伴うデータベースメンテナンスコストを削減することも課題となっていた。
本発明の第１の目的は、スタースキーマのジョインを効率よく実行することである。また、本発明の第２の目的は、性能とデータベースメンテナンスコストとのバランスを調整する機構を提供することである。
【０００４】
【課題を解決するための手段】
本発明の代表的な実施の形態では、スタースキーマのデータベースを構成するファクト表とディメンジョン表のカラムに対応してそれぞれ設けられ、それぞれのカラム値から対応するレコードを引くためのインデックスの中から、表のジョインを要する問合せ処理の際に順次アクセスすべきファクト表のインデックスとディメンジョン表のインデックスとの組合せを仮想連結インデックスとして定義してデータベースに記憶し、問合せの処理時に対応する仮想連結インデックスがあれば、その仮想連結インデックスが示す複数のインデックスを順次アクセスしてその問合せの条件に合致するファクト表のレコードを特定することによりジョイン処理を実行する。
仮想結合インデックスは典型的には各ディメンジョン表の各カラム毎に定義することになる。実際にアクセスする実インデックスとは別に、実インデックスの組合せを定義する仮想結合インデックスを記憶したことでデータベースの更新時の処理の低減の効果がある。つまり、ファクト表の更新もしくはレコード追加に対してはファクト表のカラムの実インデックスのみを更新すれば良く、ディメンジョン表のインデックスの内容も、仮想結合インデックスの内容も更新する必要がない。
また別の実施の形態では、上記の仮想結合インデックスを問合せの処理に先立ち指定したカラム値の範囲に限って実体化するステップを有する。つまり指定した範囲内の各カラム値について仮想結合インデックスの示すディメンジョン表のインデックスのアクセス、その結果を用いたファクト表のインデックスのアクセスを実行し、各カラム値に対応するファクト表のレコードＩＤのリストを予め作成して記憶する。問合せ処理時に問合せの指定するカラム値が上記指定した範囲内にあれば、実体化した連結インデックスのアクセスのみ問合せの条件に合致するファクト表のレコードをポイントすることができる。よって、スタースキーマのデータべースの問合せ処理が極めて高速になる。またカラム値の範囲を限定した部分的な実体化であるため、データの更新追加時のインデックスメンテナンスのコストを小さくできる。つまり、ファクト表もしくはディメンジョン表の更新頻度、及びジョイン処理に必要とされる性能に応じて、仮想連結インデックスの実体化の割合を変化させ、データベースの処理性能とデータベースメンテナンスコストのバランスを適切に制御することが可能となる。
【０００５】
【発明の実施の形態】
仮想連結インデックスの実施の形態について説明する。図１の仮想連結インデックスＩｄｃ２＿ｆｃ１（１０１）は、ディメンジョン表ＤＴ１（１０４）のカラムｃ１２の値から、ファクト表ＦＴ（１０５）のレコードＩＤを引くことができるインデックスである。例えば、ＤＴ１．ｃ１２＝４という条件でＩｄｃ２＿ｆｃ１を引くと、ＦＴ上のｆｔｉｄ＝３のレコードをアクセスすることができる。本発明の仮想連結インデックスは、ディメンジョン表およびファクト表上の既存のインデックスを組合せて定義する。この定義の好適な実施例として、図２に仮想連結インデックス定義文を示す（２０１）。該定義文では、前記仮想連結インデックスＩｄｃ２＿ｆｃ１を、ディメンジョン表ＤＴ１上のインデックスＩｄｃ２（１０２）とファクト表上のインデックスＩｆｃ１（１０３）の組合せで定義している。
図１１は実施例のシステム構成を示す。データベース１１０７は
データベース管理システム（以下ＤＢＭＳと略称する）１１０１に管理される。外部ネットワーク経由でネットワークインターフェース部１１０に入力するデータベースへの問合せは問合せ処理部１１０３に導かれる。問合せ処理部１１０３は、問い合わせ最適化モジュール１１０を含み、ここで最適化された問合せが問合せ実行モジュール１１０５により実行される。上述の定義文で定義された仮想連結インデックスＩｄｃ２＿ｆｃ１は、データベース１１０７中にテーブル１１０９として格納され、問合せ処理で利用される。
仮想連結インデックスの定義された仮想連結インデックスのＤＢＭＳ内での実現方式について、ＤＴ１．ｃ１１＝ＦＴ．ｃ１１というジョイン条件でファクト表とディメンジョン表をジョインする場合を例にあげて、図３および図１１を用いて説明する。説明を簡単にするため、ディメンジョン表内の１レコードであるＤＴ１．ｃ１２＝４をジョインする場合を説明する。前記仮想連結インデックスＩｄｃ２＿ｆｃ１に対してＤＴ１．ｃ１２＝４という条件でアクセスした場合、該アクセスはＤＢＭＳ内の問合せ最適化モジュール１１０４によって、ディメンジョン表ＤＴ１（３０３）のインデックスＩｄｃ２（３０１）と、ファクト表ＦＴのインデックスＩｆｃ１（３０２）へのアクセスに変換される。
一般に、最適化時に考慮されるインデックスの組合せは、組合せ爆発による最適化実行時間を押さえるために、その考慮対象数が制限されてしまうため、最適な組合せを見つけることは困難である。それに対して、本発明の仮想連結インデックス定義を用いることにより、前記最適化モジュールは適切なインデックスを優先的に選択することができ、実行時間短縮のみならず最適化時間をも短縮することができる。
前記最適化モジュールが決定したインデックスの組合せに従って、問合せ実行モジュール１１０５が実際にインデックスアクセスを行って問合せを処理する。いま、Ｉｄｃ２に対してＤＴ１．ｃ１２＝４という条件でアクセスすると、ディメンジョン表ＤＴ１では、カラムｃ１２の値が４のレコード３０５がポイントされ、ファクト表ＦＴとのジョインの対象となるディメンジョン表のカラム（以下、結合カラム）ｃ１１の値として２を取得する。問合せ実行モジュールはｃ１１＝２の値を用いてファクト表のインデックスＩｆｃ１にアクセスし、ファクト表レコードＩＤ（ｆｔｉｄ）＝３のレコード３０６を取得する。
以上のステップで、仮想連結インデックスの動作について説明したが、前記仮想連結インデックス利用のファクト表のレコード取得では、１回のディメンジョン表のインデックスＩｄｃ２へのアクセス、ディメンジョン表のレコード３０５取得のためのデータページへのアクセス、ファクト表上のインデックスＩｆｃ１へのアクセス、そしてファクト表のレコード３０６取得のためのデータページアクセスが必要であった。
ディメンジョン表、ファクト表の更新頻度が小さく、インデックスメンテナンスコストを考慮しなくてもよい場合、もしくはシステム設計の第１の目的が参照性能の向上である場合には、前記仮想連結インデックスの実体化を行うことによって、仮想連結インデックスアクセスによるファクト表行取得のコストを削減することができる。仮想連結インデックスの実体化とは、仮想連結インデックスに連結対象と定義されたインデックスを、問合せ実行に先立って順次アクセスし、その結果を実際にデータとしてＤＢＭＳ内に格納しておくことであり、文献５のスターインデックスに相当する。実体化した仮想連結インデックスを用いれば、ファクト表のレコードをポイントするのは仮想連結インデックスに対する１回のアクセスのみでよく、実行効率を高めることができる。
但し、実体化を行うとデータの変更に伴うインデックスメンテナンスコストが著しく増大する上に、実体化したインデックスを格納するディスクスペースも必要となるという問題がある。そこで、本発明では、図５に示すように仮想連結インデックスの部分的な実体化を可能とする。図５の仮想連結インデックスＩｄｃ２＿ｆｃ１（５０１）では、全体のうち横線の付加された左側半分が実体化されていることを示しており、実体化された範囲のインデックスへのアクセスでは１回のアクセスでファクト表のレコードをポイントすることができる。仮想連結インデックスの実体化の定義例を図４の４０１に示す。４０１では、仮想連結インデックスＩｆｃ２＿ｆｃ１のうち、ＤＴ１．ｃ１２＞２を満たす部分のみを実体化する。
ここで上記の仮想連結インデックスの実体化の定義例に沿って、実体化の具体的手順を述べる。上記定義例では実体化の限定範囲がディメンジョン表ＤＴ１のカラムｃ１２が２より大の範囲なので、カラムｃ１２のインデックス３０１を参照して限定範囲内の全てのカラム値（図３の例ではカラム値３と４）についてインデックス３０１を順次引く。これによりそれぞれ特定されたレコードから結合カラムｃ１１のカラム値１と２を得る。これら結合カラムのカラム値をそれぞれ用いて仮想連結インデックスで定義する結合されるべきインデックス３０２を引き、ファクト表のレコードをそれぞれ特定し、これらレコードからファクト表のレコードＩＤであるｆｔｉｄの値を読出す。読み出したｆｔｉｄ　の値を、先の範囲限定されたディメンジョン表のカラム値のそれぞれに対応づけたファクト表のレコードＩＤリストの形で記憶する。図３の例では、ディメンジョン表のカラムｃ１２のカラム値３に対応してｆｔｉｄ＝１とｆｔｉｄ＝２が、またカラム値４に対応してｆｔｉｄ＝３が記憶される。
このように仮想連結インデックスを予め部分的に実体化した構成を採用した場合は、仮想連結インデックスを利用可能な問合せの処理の際に、その問合せが指定するカラム値が実体化定義の限定範囲内か否かを判定する。限定範囲内なら仮想連結インデックスが指定する個々のインデックスの順次アクセスに替え、実体化した連結インデックスの一回のアクセスで、つまり記憶したファクト表のレコードＩＤリストの読み出しでレコードのポイントが可能となる。
次に、本発明による仮想連結インデックスを用いたジョイン処理方式を図８のフローチャートを用いて説明する。本フローチャートで示した処理は、ＤＢＭＳ内の問合せ処理部１１０３内の問合せ最適化モジュール１１０４、および該問合せ処理部内の問合せ実行モジュール１１０５で行われるのが普通であるが、実装の方式によりこれらとは異なるモジュールで実行しても差し支えない。以下の実施例では、実行の主体を前記問合せ処理部とする。
ジョイン処理の最初のステップでは、前記問合せ処理部が仮想連結インデックスの利用可否をチェックする（８０２）。仮想連結インデックスの利用が不可と指定されている場合（ステップ８０２でＹｅｓが選択された場合）には、仮想連結インデックスを用いない従来のジョイン処理を実行し（ステップ８０９）、ジョイン処理を終了する（ステップ８１０）。利用可能な仮想連結インデックスが存在する場合には、必ず該インデックスの利用を考慮するという場合には、ステップ８０２は省略することも可能である。
仮想連結インデックスの利用を考慮する場合（ステップ８０２でＮｏが選択された場合）、前記問合せ処理部は問合せ処理で利用が可能な仮想連結インデックスの存在の有無をチェックする（ステップ８０３）。利用可能な仮想連結インデックスが存在しない場合（ステップ８０３でＮｏが選択された場合）には、仮想連結インデックスを用いない従来のジョイン処理を実行し（ステップ８０９）、ジョイン処理を終了する（ステップ８１０）。
利用可能な仮想連結インデックスが存在する場合（ステップ８０３でＹｅｓが選択された場合）、ファクト表とディメンジョン表の結合カラムが、ディメンジョン表側のキーとなっていることを保証できるか否かをチェックする（ステップ８０４）。ここで、結合カラムとはジョインされる２つの表で値の突合せが行われるカラムを指す。例えば、図５の問合せ５０６では、ジョイン条件はＤＴ１．ｃ１１＝ＦＴ．ｃ１１であるので、結合カラムはＤＴ１．ｃ１１およびＦＴ．ｃ１１となる。また、カラムｃが表Ｔのキーとなっているとは、カラムｃの値が表Ｔ中でユニークであること、すなわち同じカラムｃには同じ値が現れないことを表す。例えば、図５のディメンジョン表ＤＴ１ではカラムｃ１１の値はＤＴ１中で全て異なるため、キーとなっているといえる。制約チェック機構を備えるＤＢＭＳでは、表Ｔのカラムｃにユニーク制約を付与し、チェック機構を有効とすることで、カラムｃがキーとなっていることを保証できる。
ディメンジョン表の結合カラムがキーとなっていることを保証できる場合（ステップ８０４でＹｅｓが選択された場合）には、本ジョイン処理以降の問合せ処理にディメンジョン表の結合カラム以外のカラム値が必要か否かをチェックする（ステップ８０５）。例えば図５の問合せＱ１（５０６）は、ＳＥＬＥＣＴ句にＤＴ１．ｃ１２が指定されているため、問合せ処理に結合カラム以外のカラム値が必要な場合である。一方、同図の問合せＱ２（５０７）は、ＳＥＬＥＣＴ句にディメンジョン表のカラムは指定されておらず、ジョイン処理以降の問合せ処理でも該カラムを必要としないため、問合せ処理には結合カラムのみがあればよい場合である。ある処理以降にどのカラムが必要となるかのチェック機構は、問合せに現れるカラムをチェックすることで簡単に実現でき、多くの商用ＤＢＭＳでサポートされている公知技術である。
問合せ処理にディメンジョン表の結合カラムのみが必要な場合（ステップ８０５でＮｏが選択された場合）には、仮想連結インデックス利用により、ファクト表レコードＩＤリストを生成する（ステップ８０６）。ファクト表レコードＩＤリストとは　　の６０４に示すように、ジョイン条件を満足するファクト表のレコードＩＤのみを取り出したリストを指す。例えば問合せが図５のＱ２（５０７）の場合には、該ファクト表レコードＩＤリストには３のみが格納される。
ディメンジョン表の結合カラムがキーであることが保証できない場合（ステップ８０４でＮｏが選択された場合）、もしくは問合せ処理にディメンジョン表の結合カラム以外のカラムが必要な場合（ステップ８０５でＹｅｓが選択された場合）には、仮想連結インデックス利用およびディメンジョン表アクセスにより、カラムマッピングテーブルを生成する（ステップ８１１）。カラムマッピングテーブルとは図７の７０４に示すように、ジョイン条件を満足するファクト表のレコードＩＤ、結合カラム、そして問合せ処理に必要な結合カラム以外のカラムを格納する表である。問合せが図５のＱ１（５０６）である場合には、カラムマッピングテーブルは、ファクト表レコードＩＤであるｆｔｉｄ、結合カラムｃ１１、および問合せ処理で必要となるカラムｃ１２で構成され、格納されるレコードは｛ｆｔｉｄ，ｃ１１，ｃ１２｝＝｛（３，２，４）｝の１レコードとなる。
ジョイン対象の各ディメンジョン表に対して、ファクト表レコードＩＤリスト、もしくはカラムマッピングテーブルを生成した後、問合せ処理部は、問合せの全ての条件を満足するファクト表レコードＩＤ集合を生成する（ステップ８０７）。本処理ステップを図１０に基づいて説明する。
図１０に示す環境では、データベースはファクト表ＦＴ（１００９）と２つのディメンジョン表ＤＴ１（１００３）およびＤＴ２（１００７）の計３つの表で構成されている。該データベースに対して、問合せＱ３（１０１２）が発行されたとすると、該問合せを処理するためには、ＦＴ、ＤＴ１、およびＤＴ２のジョイン処理が必要となる。ＦＴとＤＴ１、ＦＴとＤＴ２の結合カラムはそれぞれ、ｃ１１、ｃ２１である。まずＤＴ１とＦＴのジョインに関しては、問合せＱ３でジョイン処理以降にＤＴ１の結合カラム以外のカラムを必要としないため、Ｑ３のＷＨＥＲＥ句に指定されているＦＴ１．ｃ１２＝４の条件で仮想連結インデックスＩｄｃ２＿ｆｃ１（１００１）を引き、ファクト表レコードＩＤリスト１００４を生成する。次に、ＤＴ２とＦＴのジョインに関しては、Ｑ３でＳＥＬＥＣＴ句に結合カラム以外のＤＴ２．ｃ２３が指定されているため、Ｑ３のＷＨＥＲＥ句に指定されているＤＴ２．ｃ２３＜３の条件で仮想連結インデックスＩｄｃ３＿ｆｃ２（１００５）を引き、カラムマッピングテーブル１００８を生成する。Ｑ３ではＷＨＥＲＥ句に指定された条件はＡＮＤで結合されているため、前記ファクト表レコードＩＤリスト（１００４）と、前記カラムマッピングテーブル（１００８）から抽出したレコードＩＤのリストをＡＮＤ条件で結合し（１０１０）、問合せの条件を満足するファクト表レコードＩＤ集合１０１１を生成する。図８に戻って、問合せの条件を満足するファクト表レコードＩＤ集合が生成された後、処理中の問合せでカラムマッピングテーブルを作成したか否かをチェックする（ステップ８０８）。カラムマッピングテーブルが存在しない場合（ステップ８０８でＮｏが選択された場合）、前記問合せの結果はファクト表のみで生成できるため、ステップ８０７で生成したファクト表レコードＩＤリストに対応するファクト表のレコードを取り出して結果を生成し（ステップ８１４）、ジョイン処理を終了する（８１３）。
カラムマッピングテーブルが存在する場合（ステップ８０８でＹｅｓが選択された場合）、ステップ８０７で生成したファクト表レコードＩＤリストに対応するファクト表のレコードを取り出し、カラムマッピングテーブルとの突合せにより結果を生成する（ステップ８１２）。例えば図１０の例では、問合せの条件を満足するファクト表レコードＩＤ集合ｆｔｉｄ＝｛３｝であるので、該ｆｔｉｄの値でファクト表ＦＴのインデックスＩｆｔを引いてｆｔｉｄ＝３であるレコード（１０１３）にアクセスし、該レコードからファクト表から問合せＱ３のＳＥＬＥＣＴ句に指定されており、問合せ処理に必要となっているカラムＦＴ．ｆｃの値３００００を取り出す。同様にして、カラムマッピングテーブル（１００８）でｆｔｉｄ＝３のレコードにアクセスし、Ｑ３のＳＥＬＥＣＴ句に指定されており、問合せ処理に必要となっているカラムＤＴ２．ｃ２３の値２を取り出す。該処理ステップにより、問合せＱ３の結果として、｛ＦＴ．ｆｃ１，ＤＴ２．ｃ２３｝＝｛（３００００，２）｝を生成することができる。
本実施例では、ファクト表レコードＩＤをリストとして保持する方法を示したが、ビットマップとして保持する方法でも差し支えない。また本実施例では、カラムマッピングテーブルを作成するディメンジョン表に関してはファクト表レコードＩＤリストを作成しない方法を示したが、該ディメンジョン表に対してカラムマッピングテーブルとファクト表レコードＩＤリストの両方を作成してももちろん差し支えない。さらに、該ファクト表レコードＩＤリストおよびカラムマッピングテーブルは、メモリ上に一時的に作成しても、データベース（１１０７）内にテーブル（１１０８）として作成しても差し支えない。
【０００６】
【発明の効果】
本発明を用いることにより、スタースキーマのジョイン処理の効率を高めることができ、さらに加えてデータベースの処理性能とデータベースメンテナンスコストのバランスを適切に制御することが可能となる。
【図面の簡単な説明】
【図１】本発明における仮想連結インデックスを示す図。
【図２】本発明における仮想連結インデックス定義例を示す図。
【図３】本発明における仮想連結インデックス利用時のデータアクセスパスを示す図。
【図４】本発明における仮想連結インデックスの実体化指定例を示す図。
【図５】本発明における仮想連結インデックスの部分的実体化および問合せ例を示す図。
【図６】本発明における仮想連結インデックス利用によるファクト表レコードＩＤリスト生成例を示す図。
【図７】本発明における仮想連結インデックス利用によるカラムマッピングテーブル生成例を示す図。
【図８】本発明におけるジョイン処理ステップを示すフローチャート。
【図９】スタースキーマ説明のための例を示す図。
【図１０】本発明における仮想連結インデックス利用のジョイン処理ステップを示す図。
【図１１】本発明のＤＢＭＳ構成を説明するための図。
【符号の説明】
１０１、５０１、６０１、７０１、１００１、１００５…仮想連結インデックス、
１０２、１０３、３０１、３０２、５０２、５０３、６０２、７０２、１００２、１００６…インデックス、
１０４、３０３、５０４、６０３、７０３、９０２、９０３、９０４、９０５、１００３、１００７…ディメンジョン表、
１０５、３０４、５０５、９０１、１００９…ファクト表、
６０４、１００４…ファクト表レコードＩＤリスト、
７０４、１００８…カラムマッピングテーブル、
１１０８、１１０９…テーブル。
【図１】
2004110219.tif 000003
【図２】
2004110219.tif 000004
【図３】
2004110219.tif 000005
【図４】
2004110219.tif 000006
【図５】
2004110219.tif 000007
【図６】
2004110219.tif 000008
【図７】
2004110219.tif 000009
【図８】
2004110219.tif 000010
【図９】
2004110219.tif 000011
【図１０】
2004110219.tif 000012
【図１１】
2004110219.tif 000013