(57)【特許請求の範囲】
【請求項１】
関数に基づく比較を有する元の条件を含むクエリのためにインデックスを用いる、コンピュータにより実施される方法であって、前記コンピュータは行及び列を含むデータベースを備え、
コンピュータが、前記データベース内の特定の列の値に関する比較を表す関数を元の条件として受け取るステップと、
前記特定の列についてインデックスがある場合、前記コンピュータが、前記関数の逆関数に基づいて、比較する列に対する値の範囲を識別する境界を決定する黙示条件を特定するステップであって、前記範囲が少なくとも全ての所望の行を含む、ステップと、
前記コンピュータが、前記クエリに含まれる実際のパラメータ値及び前記黙示条件に基づいて動的間隔を決定するステップと、
前記コンピュータが、前記比較する列に対してインデックスを得るステップと、
前記コンピュータが、前記インデックス及び前記決定された動的間隔を用いて前記クエリを実行するステップと、
を備えた方法。
【請求項２】
請求項１記載の方法において、前記範囲は、上側境界および下側境界を含む、方法。
【請求項３】
請求項１記載の方法において、前記範囲は、最小数の冗長行を含む、方法。
【請求項４】
関数に基づく比較を有する元の条件を含むクエリのためにインデックスを用いる方法を機械に実行させる命令を有する機械読み取り可能媒体であって、前記機械は行及び列を含むデータベースを備え、前記方法が、
前記データベース内の特定の列の値に関する比較を表す関数を元の条件として受け取るステップと、
前記特定の列についてインデックスがある場合、前記関数の逆関数に基づいて、比較する列に対する値の範囲を識別する境界を決定する黙示条件を特定するステップであって、前記範囲が少なくとも全ての所望の行を含む、ステップと、
前記クエリに含まれる実際のパラメータ値及び前記黙示条件に基づいて動的間隔を決定するステップと、
前記比較する列に対してインデックスを得るステップと、
前記インデックス及び前記決定された動的間隔を用いて前記クエリを実行するステップと、
を備えた、機械読み取り可能媒体。
【請求項５】
請求項４記載の機械読み取り可能媒体において、前記範囲は、上側境界および下側境界を含む、機械読み取り可能媒体。
【請求項６】
請求項５記載の機械読み取り可能媒体において、前記範囲は、セーフおよびタイトである、機械読み取り可能媒体。
【請求項７】
関数に基づく比較を有する元の条件を含むクエリのためにインデックスを用いるシステムであって、
行及び列を含むデータベースと、
前記データベース内の特定の列の値に関する比較を表す関数を元の条件として受け取るモジュールと、
前記特定の列についてインデックスがある場合、前記関数の逆関数に基づいて、比較する列に対する値の範囲を識別する境界を決定する黙示条件を特定するモジュールであって、前記範囲が少なくとも全ての所望の行を含む、モジュールと、
前記比較する列に対してインデックスを得るモジュールと、
前記インデックス及び前記決定された動的間隔を用いて前記クエリを実行するモジュールと、
を備えたシステム。
【請求項８】
関数に基づく比較を有する元の条件を含むクエリのためにインデックスを用いる、コンピュータにより実施される方法であって、前記コンピュータは行及び列を含むデータベースを備え、
コンピュータが、前記データベース内の特定の列の値に関する比較を表す関数を元の条件として受け取るステップと、
前記特定の列についてインデックスがある場合、前記コンピュータが、前記関数の逆関数に基づいて、比較する列に対する値の範囲を識別する境界を決定する黙示条件を特定するステップと、
前記コンピュータが、複数の行を有する列についての前記クエリに含まれる実際のパラメータ値に、前記黙示条件を適用して、動的間隔を決定するステップと、
前記コンピュータが、前記動的間隔を満たす値を有する全ての行に対するインデックスを得るステップと、
前記コンピュータが、前記インデックスに対し前記クエリを実行するステップと、
を備えた方法。
【請求項９】
請求項８記載の方法において、前記範囲は、上側境界および下側境界を含む、方法。
【請求項１０】
請求項９記載の方法において、前記境界をパラメータ化し、実行時において値の置換を可能とする、方法。
【請求項１１】
請求項８記載の方法において、前記インデックスは最小数の冗長行を含む、方法。
【請求項１２】
請求項８記載の方法において、前記関数は、タイプ変換および非線形関数から成るグループから選択した関数を含む、方法。
【請求項１３】
請求項８記載の方法において、前記動的間隔は、境界式を含む、方法。
【請求項１４】
請求項８記載の方法において、前記境界式は、演算子、全行認定、全非ヌル行認定、および全行認定せずの内少なくとも１つを含む、方法。
【請求項１５】
請求項８記載の方法において、例外が発生した場合、前記列全体に対して前記クエリを実行する、方法。
【請求項１６】
複数の行を有するテーブルに対するクエリのためにインデックスを用いる方法を機械に実行させる命令を有する機械読み取り可能媒体であって、前記クエリは関数に基づく比較を有する元の条件を含み、前記機械は前記テーブルを含むデータベースを備え、前記方法が、
前記テーブル内の特定の列の値に関する比較を表す関数を元の条件として受け取るステップと、
前記特定の列についてインデックスがある場合、前記関数の逆関数に基づいて、比較する列に対する値の範囲を識別する境界を決定する黙示条件を特定するステップと、
列についての前記クエリに含まれる実際のパラメータ値に、前記黙示条件を適用して、動的間隔を決定するステップと、
前記動的間隔を満たす値を有する全ての行に対するインデックスを得るステップと、
前記インデックスに対し前記クエリを実行するステップと、
を備えた、機械読み取り可能媒体。
【請求項１７】
関数に基づく比較を有する元の条件を含むクエリのためにインデックスを用いるシステムであって、
行及び列を含むデータベースと、
前記データベース内の特定の列の値に関する比較を表す関数を元の条件として受け取る手段と、
前記特定の列についてインデックスがある場合、前記関数の逆関数に基づいて、比較する列に対する値の範囲を識別する境界を決定する黙示条件を特定する手段であって、前記範囲が少なくとも全ての所望の行を含む、手段と、
列についての前記クエリに含まれる実際のパラメータ値に、前記黙示条件を適用して、動的間隔を決定する手段と、
前記動的間隔を満たす値を有する全ての行に対するインデックスを得る手段と、
前記インデックスに対し前記クエリを実行する手段と、
を備えたシステム。
【請求項１８】
関数に基づく比較を有する元の条件を含むクエリのためにインデックスを用いる、コンピュータにより実施される方法であって、前記コンピュータは行及び列を含むデータベースを備え、
コンピュータが、前記データベース内の特定の列の値に関する比較を表す関数を元の条件として受け取るステップと、
前記特定の列についてインデックスがある場合、前記コンピュータが、前記関数の逆関数に基づいて、比較する列に対する値の範囲を識別する境界を決定する黙示条件を特定するステップと、
前記コンピュータが、所望の列に対してインデックスを選択するステップと、
前記コンピュータが、前記インデックスについての前記クエリに含まれる実際のパラメータ値に前記黙示条件を適用し、前記黙示条件を満たす行の範囲を得るステップと、
を備えた方法。
【請求項１９】
請求項１８記載の方法において、前記範囲は、上側境界および下側境界を含む、方法。
【請求項２０】
請求項１８記載の方法において、前記関数は、タイプ変換および非線形関数から成るグループから選択した関数を含む、方法。
【請求項２１】
請求項１８記載の方法であって、更に、境界式を用いるステップを含む、方法。
【請求項２２】
請求項２１記載の方法において、前記境界式は、全ての行を認定するか、全ての非ヌル行を認定するか、およびいずれの行も認定しないかの内少なくとも１つを特定する、方法。
【請求項２３】
請求項１８記載の方法であって、更に、前記コンピュータが、テーブルを用いて、関数に基づく各比較に対し、前記境界をどのように決定するか特定するステップを含む、方法。
【請求項２４】
請求項１８記載の方法において、前記クエリは、前記黙示条件に影響を及ぼす少なくとも１つのパラメータを含む、方法。
【請求項２５】
関数に基づく比較を有する元の条件を含むクエリのためにインデックスを用いる方法を機械に実行させる命令を有する機械読み取り可能媒体であって、前記機械は行及び列を含むデータベースを備え、前記方法が、
前記データベース内の特定の列の値に関する比較を表す関数を元の条件として受け取るステップと、
前記特定の列についてインデックスがある場合、前記関数の逆関数に基づいて、比較する列に対する値の範囲を識別する境界を決定する黙示条件を特定するステップと、
所望の列に対してインデックスを選択するステップと、
前記インデックスについての前記クエリに含まれる実際のパラメータ値に前記黙示条件を適用し、前記黙示条件を満たす行の範囲を得るステップと、
を備えた、機械読み取り可能媒体。
【請求項２６】
関数に基づく比較を有する元の条件を含むクエリを実行する、コンピュータにより実施される方法であって、前記コンピュータは行及び列を含むデータベースを備え、
コンピュータが、前記データベース内の特定の列の値に関する比較を表す関数を元の条件として受け取るステップと、
前記特定の列についてインデックスがある場合、前記コンピュータが、前記関数の逆関数に基づいて、比較する列に対する値の範囲を識別する境界を決定する黙示条件を特定するステップと、
前記コンピュータが、前記クエリ内に含まれる実際のパラメータ値及び前記黙示条件に基づいて動的間隔を決定することにより、クエリ実行計画を得るステップと、
前記コンピュータが、前記動的間隔に基づいて、インデックス内においてセーフ範囲を識別するステップと、
前記コンピュータが、前記インデックスによって識別した行に、前記元の条件を適用するステップと、
を備えた方法。
【請求項２７】
関数に基づく比較を有する元の条件を含むクエリを実行する、コンピュータにより実施される方法であって、前記コンピュータは行及び列を含むデータベースを備え、
コンピュータが、前記データベース内の特定の列の値に関する比較を表す関数を元の条件として受け取るステップと、
前記特定の列についてインデックスがある場合、前記コンピュータが、前記関数の逆関数に基づいて、比較する列に対する値の範囲を識別する境界を決定する黙示条件を特定するステップと、
前記コンピュータが、前記クエリ内に含まれる実際のパラメータ値及び前記黙示条件に基づいて動的間隔を決定することにより、クエリ実行計画を得るステップと、
前記コンピュータが、前記動的間隔に基づいて、インデックス内においてセーフ範囲およびタイト範囲を識別するステップと、
前記コンピュータが、前記インデックスによって識別した行に、前記元の条件を適用することによって前記クエリを実行するステップと、
前記コンピュータが、前記クエリの実行中に発生した例外を処理するステップと、
を備えた方法。
【請求項２８】
請求項２７記載の方法において、例外は、前記インデックスを使用せずに、前記クエリを実行させる、方法。
【請求項２９】
請求項２７記載の方法であって、更に、前記コンピュータが、どのように例外を処理するかを特定するフラグをセットするステップを含む、方法。
【請求項３０】
請求項２９記載の方法において、前記フラグが、未満、以下、以上、等しい、全行認定、全非ヌル行認定、および全行認定せずから成るグループから選択した演算を表わす、方法。
【請求項３１】
請求項２７記載の方法において、セーフ範囲およびタイト範囲を識別するステップは、前記コンピュータが、前記実行計画において識別したパラメータを、前記クエリからの値と置換するステップを含む、方法。
【請求項３２】
関数に基づく比較を有する元の条件を含むクエリを実行する方法を機械に実行させる命令を有する機械読み取り可能媒体であって、前記機械は行及び列を含むデータベースを備え、前記方法が、
前記データベース内の特定の列の値に関する比較を表す関数を元の条件として受け取るステップと、
前記特定の列についてインデックスがある場合、前記関数の逆関数に基づいて、比較する列に対する値の範囲を識別する境界を決定する黙示条件を特定するステップと、
前記クエリ内に含まれる実際のパラメータ値及び前記黙示条件に基づいて動的間隔を決定することにより、クエリ実行計画を得るステップと、
前記動的間隔に基づいて、インデックス内においてセーフおよびタイト範囲を識別するステップと、
前記インデックスによって識別した行に、前記元の条件を適用することによって前記クエリを実行するステップと、
前記クエリの実行中に発生した例外を処理するステップと、
を備えた、機械読み取り可能媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一般的に、コンピュータの分野に関し、特に関数に基づく比較を有するクエリのためのインデックスの使用に関する。
【０００２】
【従来の技術】
この特許文書の開示内容の一部は、著作権の保護対象となる題材を含む。著作権者は、本特許文書または特許開示内容の、特許商標庁における特許ファイルまたは記録に現れる通りのファクシミリ再生については、いずれの者による場合であっても異議を唱えないが、それ以外についてはあらゆる著作権を保存することとする。以下の通知は、以下および図面に記載するソフトウエアおよびデータに適用されるものとする。著作権c２０００年Microsoft Corporation、版権所有。
【０００３】
リレーショナル・データベースは、データの行即ちタプル（tuple）の集合である。各行は、番号、名称、アドレス等のような情報を収容する１つ以上の列を有することができる。例えば、列は、税金を支払う人の名前を、住所、社会保証番号、およびその他の列に収容されている他の情報と共に収容する場合もある。行内の情報は全て同じ人に関係がある。クエリを書くことによって、データベースから情報を要求することができる。このようなクエリの１つは、年齢に関係付けることもできる。クエリは、ある年の人全ての平均収入を求めることと関係付けることも可能である。
【０００４】
インデックスは、所与の条件を満たす行を見つけるために一般的に用いられている。前述の例では、インデックスは年齢に基づくことができる。このようなインデックスは、年齢の昇順で行のリストをソートすることができる。インデックスがあれば、データベースは、年齢がある年齢よりも大きい行のグループだけを見ることによって、クエリの実行を高速化することができる。また、年齢基準を満たさない行をデータベースが飛ばすことも可能にする。
【０００５】
インデックスの使用は、非常に強力なクエリ実行技法であり、実行時間および手間を劇的に改善することができる。インデックスは、ある参照構造を与え、所与のテーブルのあらゆる行を検査しなければならない代わりに、具体的な列の値が与えられれば、１つの行に直接アクセスすることを可能にする。前者をテーブル全体のスキャンと呼んでいる。列＜ｃｏｌ＞上のインデックスを用いて、形態＜ｃｏｌ＞＜ｃｍｐ＞＜ｅｘｐｒ＞の条件を満たす行を見つけることができる。例えば、列Ｔ．ａ上のインデックスを用いて、Ｔ．ａ＝５またはＴ．ａ＞１０という条件を満たす行を検索することができる。
【０００６】
条件が形態Ｔ．ａ＝Ｒ．ｂであるときに、同じインデックスを用いてテーブルの結合を実行することができる。この場合、Ｒの各行について、Ｔ．ｂに具体的な値を決定し、このような値を有するＴの行全てを、インデックスを通じて見つけ出す。
【０００７】
【発明が解決しようとする課題】
列上で直接比較を行なわないが、ある計算上で行なう場合、列上のインデックスは通常適用できず、インデックスによって実行を高速化することは、市販の製品では多くの場合不可能である。例えば、列Ｔ．ａのインデックスは、大抵の場合、条件Ｔ．ａ＊Ｔ．ａ＞２５を満たす行を突き止めるために利用できない。尚、５．０よりも大きい値および−５．０よりも小さい値はこの条件を満たすことを注記しておく。通常、形態ｆ（＜ｃｏｌ＞）＜ｃｏｍ＞＜ｅｘｐｒ＞の比較のために（列の値を用いる関数であり、結果を別の式と比較する）、＜ｃｏｌ＞上のインデックスを用いて、認定した行を突き止めることはできない。
【０００８】
タイプ変換は、インデックスが通常用いられない関数の共通な例の１つである。浮動小数点から整数への変換は、タイプ変換の一例である。この文書では以降、‘ＣＯＮＶＥＲＴ（ｃｏｌｕｍｎ，ｔｙｐｅ）’を用いてタイプ変換を示すことにする。ＣＯＮＶＥＲＴ（＜ｃｏｌ＞）＜ｃｏｍ＞＜ｅｘｐｒ＞を含むクエリに至るには、異なる複数の方法がある。ユーザは、条件をこのような形態で直接書くことができ、あるいはシステムによって、整数や浮動小数点のような比較可能なタイプに対して動作するときに、暗示的な変換を導入することもできる。この種の比較を導入する別の方法は、他の条件からの推論によるものである。
【０００９】
【課題を解決するための手段】
列に対して関数に基づく比較を有する元の条件を含むクエリに、インデックスを用いる。列に対して黙示条件（implied condition）を最初に特定し、列を制限するために適用し、インデックスからフェッチする。最後に、元の条件を用いて、制限した行の集合に対してクエリを実行する。
【００１０】
黙示条件は、少なくとも１つの不等号の境界、不等号の上側境界および下側境界、および非線形関数を特定する。境界または複数の境界は、元の条件を満たす潜在的な可能性がある全ての行を含むように、そしてできるだけ元の条件を満たさない行を含まないように計算する。
【００１１】
黙示条件は、一旦パラメータ値がわかれば、実行時に完全に決定される。動的な間隔が、どの境界を適用すべきかを示すフラグを与え、上側境界、下側境界、または全行認定（all-rows-qualify）、認定行無し（no-rows-qualify）、または非ヌル認定（non-nulls-qualify）のような特殊な間隔を示す。黙示境界条件の計算中に例外に遭遇した場合、動的間隔全行認定を用いれば、全ての行を考慮するので、常に安全である。
【００１２】
本発明の更に別の態様では、多数の関数に対して黙示条件を識別する。境界は、黙示条件に基づいて計算され、クエリ内に含まれるパラメータに基づく。
【００１３】
【発明の実施の形態】
以下の本発明の実施形態の一例の詳細な説明では、その一部をなす添付図面を参照する。図面では、本発明を実施可能な具体的な実施形態の例を、例示として示す。これらの実施形態は、当業者が本発明を実施することができるように十分詳細に説明してあり、更に、他の実施形態も利用可能であり、論理的、数学的、電気的およびその他の変更も、本発明の精神または範囲から逸脱することなく行なえることは理解されよう。したがって、以下の詳細な説明は、限定的な意味で捕らえてはならず、本発明の範囲は添付した特許請求の範囲によってのみ定義されることとする。
【００１４】
詳細な説明は多数の章に分かれている。第１章は、本発明を実現するコンピュータ・システムの動作について説明する。続いて、条件に基づく比較を有するクエリのためにどのようにしてインデックスを生成するかについての高度な説明に移る。次に、インデックスに対する境界をどのように構築するか、および実行時の例外を処理するためにフラグをどのように用いるかに関して更なる詳細を提示する。これに続いて、いくつかの潜在的な利点を説明し、更に別の代替実施形態を説明する結論に至る。
ハードウエアおよび動作環境
本発明を実現するシステム例は、図１における計算デバイス１００のような計算デバイスを含む。その最も基本的な構成では、計算デバイス１００は、典型的に、少なくとも１つの演算装置１０２およびメモリ１０４を含む。計算機の正確なコンフィギュレーションおよび形式に応じて、メモリ１０４は、揮発性（ＲＡＭのような）、不揮発性（ＲＯＭ、フラッシュ・メモリ等のような）、またはこれら２つの何らかの組み合わせとなる場合もある。この最も基本的なコンフィギュレーションを、図１における破線１０６で示す。
【００１５】
デバイス１００は、追加の機構／機能性を含むこともできる。例えば、デバイス１００は、磁気または光ディスクまたはテープを含むがこれらには限定されない、追加のストレージ（リムーバブルおよび／または非リムーバブル）を含むことができる。このような追加のストレージは、図１では、リムーバブル・ストレージ１０８および非リムーバブル・ストレージ１１０によって例示されている。コンピュータ記憶媒体は、揮発性および不揮発性、リムーバブルおよび非リムーバブル媒体を含み、コンピュータ読み取り可能命令、データ構造、プログラム・モジュールまたはその他のデータのように、情報格納技術のあらゆる方法で実現されている。メモリ１０４、リムーバブル・ストレージ１０８および非リムーバブル・ストレージ１１０は、全てコンピュータ記憶媒体の例である。コンピュータ記憶媒体は、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュ・メモリ、またはその他のメモリ技術、ＣＤ−ＲＯＭ、ディジタル・バーサタイル・ディスク（ＤＶＤ）またはその他の光ストレージ、磁気を用いたストレージ、あるいは所望の情報を格納するために使用可能であり、デバイス１００がアクセス可能なその他のあらゆる媒体を含むが、これらに限定される訳ではない。このようなコンピュータ記憶媒体はいずれも、デバイス１００の一部となり得る。
【００１６】
また、デバイス１００は通信接続部１１２も内蔵し、当該デバイスは他のデバイスと通信することができる。通信媒体は、典型的に、読み取り可能命令、データ構造、プログラム・モジュール、あるいは搬送波またはその他の輸送機構のような変調データ信号におけるその他のデータを具体化し、あらゆる情報配信媒体を含む。「変調データ信号」という用語は、信号内に情報をエンコードするように変更された、１つ以上のその特性集合を有する信号を意味する。限定ではなく一例として、通信媒体は、有線ネットワークまたは直接配線接続のような有線媒体や、音響、ＲＦ、赤外線およびその他のワイヤレス媒体のようなワイヤレス媒体を含む。ここで用いる場合、コンピュータ読み取り可能媒体とは、記憶媒体および通信媒体双方を含むこととする。
【００１７】
また、デバイス１００は、キーボード、マウス、ペン、音声入力デバイス、接触入力デバイス等のような入力デバイス１１４を有することもできる。ディスプレイ、スピーカ、プリンタ等のような出力デバイス１１６も含ませることができる。これらのデバイスは、当技術では周知である。
【００１８】
本発明は、１つ以上のコンピュータまたはデバイス１１０のようなその他のデバイスによって実行する、プログラム・モジュールのようなコンピュータ実行可能命令のコンテクストにおいて説明するとよい。通常、プログラム・モジュールは、ルーチン、プログラム、オブジェクト、コンポーネント、データ構造等を含み、特定のタスクを実行するか、または特定の抽象的データ・タイプを実装する。典型的に、プログラム・モジュールの機能性は、種々の実施形態に、必要に応じて組み合わせたりあるいは分散することができる。
【００１９】
オブジェクト指向プログラミング言語を含む多くの異なる方法を用いて、ソフトウエアを設計することができる。Ｃ＋＋およびＪａｖａ（登録商標）は、オブジェクト指向プログラミングに関連する機能性を与える、共通のオブジェクト指向コンピュータ・プログラミング言語の２つの例である。オブジェクト指向プログラミング方法は、データ・メンバ（変数）、および当該データ上で動作し、クラスと呼ばれる単一のエンティティを形成するメンバ関数（メソッド）をカプセル化する手段を与える。また、オブジェクト指向プログラミング方法は、既存のクラスに基づいて新たなクラスを作成する手段も与える。
【００２０】
オブジェクトとは、クラスのインスタンスである。オブジェクトのデータ・メンバは、コンピュータ・メモリ内部に格納されている属性であり、メソッドは、このデータ上で、潜在的に与えることができる他のサービスと共に作用する、実行可能なコンピュータ・コードである。本発明では、発明の態様を一実施形態においてオブジェクトとして実現するというオブジェクトの観念を利用する。
【００２１】
インターフェースとは、名前のあるユニットに編成された、関連する関数のグループである。各インターフェースは、ある識別子によって一意に識別することができる。インターフェースはインスタンス化（instantiation）を有さない。即ち、インターフェースは定義のみであり、当該インターフェースが指定するメソッドを実装するため実行可能コードを必要としない。オブジェクトは、インターフェースが指定するメソッドに実行可能コードを与えることによって、インターフェースを支援することができる。オブジェクトが供給する実行可能コードは、インターフェースが指定する定義を満たさなければならない。オブジェクトは追加のメソッドを与えることもできる。インターフェースは、オブジェクト指向プログラミング環境における、またはオブジェクト指向プログラミング環境による使用に限定される訳ではないことを、当業者は認めよう。
【００２２】
本発明は、機能ブロックを含むフローチャートを用いて説明する。ブロックは、必要に応じて、１つ以上のソフトウエアまたはハードウエア・モジュールで実現することができ、データベース・システムのコンテクストにおいて、計算デバイス１００上で実行する。
インデックスの使用
場合によっては、クエリは、列を異なるタイプの式と比較するので、比較の前にタイプ変換を行なう必要がある。式は、非線形関数である場合もあり、クエリに答えるためにインデックスを用いることは難しい。何故なら、条件は、列上ではなく、列の関数上で述べられているので、条件を満たすインデックスにおいて、特定の行をどのようにして突き止めるかわからないからである。
【００２３】
タイプ変換の一例では、ｆｌｏａｔ（Ｔ．ａ）＞＝２．１である。比較値は、定数、クエリ・パラメータ、別のテーブルからの列、または、総計のようなある計算の結果、またはサブクエリ（subquery）とすることができる。結局、列を異なるタイプの値と比較することになり、適正な比較には、列上でのタイプ変換が必要となる。この問題を解決するために、実際の認定範囲よりは多少広い有効範囲（covering range）を生成し、このような行を直接得るために、インデックスを用いる。
【００２４】
プロセス全体を図２Ａおよび図２Ｂに示す。元の条件を２１０において受け取る。形態は、変換（列）＜比較＞＜式＞とすることができる。例えば、列Ａ上にインデックスがあるとする。２２０において、元の条件において用いた列上にインデックスがあるか否か確認するためにチェックを行なう。例えば、列Ａ上にインデックスがある。次に、２３０において、特定のインデックス化した列に関連する黙示条件を識別する。その形態は、変換（列）＜比較＞＜式＞とすることができる。黙示条件を用いて、値の範囲を識別する境界を決定する。これは、値の列における実際の認定範囲よりも多少広くして、認定行を識別するようにする。実行中、黙示条件を評価して境界を生成し、列上のインデックスを用いて、認定行集合を突き止める。２４０において、実行計画を設定し、コンパイル時に、特定のインデックス上に、黙示条件に対して動的間隔を構築する。
【００２５】
２５０において開始する実行時では、実際のパラメータ値に基づいて、動的間隔を計算する。用いる具体的な動的間隔を決定する間に、例外が発生する。例外処理は、動的間隔決定の「内部」であり、必要であれば（例えば、例外があった場合）、全行認定を示す。動的間隔は、「Ａ＞１０およびＡ＜２０となる全てのＡを得る」と言うことができ、あるいは「全行認定」と言うことができ、あるいは「認定行なし」と言うことができる。動的間隔を決定するロジックは、実際のパラメータ値に基づき、クエリ計画（query plan）に含まれる。次に、インデックス・スキャン／参照コード２６０に動的間隔を渡し、実際の行を検索する。インデックスを用い、動的間隔結果に基づいて、行を突き止める。次に、２７０において元の条件を、検索した行に適用する（黙示条件が元の条件と同等でない場合）。
【００２６】
減少した行集合、即ち、構築した範囲は次のようになるはずである。
ｉ）全ての認定行が含まれることを意味するセーフ、および
ｉｉ）あるとしても、少数の冗長行が含まれることを意味するタイト。
【００２７】
これは、セーフおよびタイト範囲の導出例である。
元の条件：CONVERT(Aint,float)>2.5
黙示条件：Aint>2
元の条件はクエリの一部とすることができ、図３のフローチャートにおける３１０で受け取られる。図３は、コンパイル時および実行時双方におけるコンポーネントを含む。実行時よりもコンパイル時にできるだけ多くの分析を行なう方が有利である。何故なら、１回のコンパイルに対する実行が多い可能性が高いからである。一実施形態では、ブロック３１０および３２０は、コンパイル時に行われ、３３０，３４０，３５０は実行時に行われる。これは、逆関数を調べた結果が実行時に受け渡され、実行計画を通じて行われることを暗示する。
【００２８】
３２０において、逆関数のテーブルから調べることができる元の関数の逆を用いて、黙示条件を計算する式を構築する。Ａｉｎｔ上のインデックスは、元の条件を満たす行を直接発見するために用いることはできないが、黙示条件Ａｉｎｔ＞２はインデックス参照のために用いることができる。比較のための値は定数である必要はないので、構築した式から実行時に正確な境界を決定し、３３０に示すようにコンパイル時にこれらを計算する必要がある。言い換えると、先に示した値「２．５」は、実際には「ｚ」のようなパラメータとすることもでき、コンパイルしたクエリを実行するときに実際の値が与えられるだけである。
【００２９】
以下のクエリを一例として用いる。
【００３０】
【数１】
Select * from T where convert (A, float) > @f
ここで、@fは、浮動小数点パラメータとして定義する。Ｔは、整数である少なくとも１つの列Ａ、および多数の行を有するテーブルである。逆関数または境界を｛Ａ＞変換（＠ｆ，ｉｎｔ）−１｝として識別する。また、これをシーク述語（seek predicate）とも呼ぶ。「−１」を加算して、認定した行全てが範囲内にあること、即ち、範囲がセーフであることを確実にする。これは、本質的に、タイプまたは他の関数のドメインにおける次に小さい数値である。これは、逆関数の実行中に浮動小数点値が切り捨てられるときに、このような比較に何が発生するか注視することによって得られる。
【００３１】
黙示条件の計算における例外を処理し、ユーザには渡さないようにする必要がある。何故なら、黙示条件は元のクエリの一部ではなかったからである。次に、３４０において例外を識別する。例外が発生する可能性があるのは、識別した値の範囲からは、もはや所望のタイプではない値が生ずる場合があるからである。これを、タイプのドメインの外側にあると言う。範囲が前述のセーフであったことを確保することによって、「−１」を減算する。これによって、タイプ整数ドメインの外側にある数値に至る可能性がある（０から２５０、または−３６５００から＋３６５００のように、タイプのドメインに関して制限がある可能性があり、範囲の外側に該当する場合、セーフではない）。他の例外も起こる可能性があり、動的範囲との関連において以下で更に詳しく説明する。一旦例外を識別したなら、３５０においてフラグをセットし、例外のタイプに応じて所望の方法でクエリの実行中に例外を処理する。
【００３２】
先のクエリを変更して等式を含ませる場合、
【００３３】
【数２】
Select * from T where convert (A, float) = @f
上側の境界も生成しなければならない。この場合、上側の境界を｛Ａ＜ｃｏｎｖｅｒｔ（＠ｆ，ｉｎｔ）＋１｝として識別する。「＋１」を加算して、上側の境界を広げ、範囲をセーフにする。これは、本質的に、タイプまたは他の関数のドメインにおける次に大きな数値である。これは、下側の境界に対する「−１」の加算と同様である。これは、元の条件に含まれる変換関数に応じて変化する。これは、他の定数、または実行時に評価される実際の関数とすることもできる。上側の境界は、前述の不等式では必要ではなかった。また、下側の境界が必要でない場合もあることがわかる。
【００３４】
通常、前述のように、等式には２つの黙示条件が発生する。各下側および各上側の境界毎に黙示条件が発生する。元の比較が、例えば、下側の境界のみである場合、黙示の上側境界はなく、これは発生しない。変換比較が等式である場合、双方の境界が生ずる。例えば、
元の条件：CONVERT (Aint, float) = 2.5
黙示下側境界：Aint > TRUNCATE(2.5) - 1.0 = 1
黙示上側境界：Aint>TRUNCATE(2.5) + 1.0 = 3
図４は、パラメータ化した元の条件に対する境界の導出を示す。４１０において、元の条件を、タイプＴ１の列「ｃｏｌＴ１」として記述する。これは、タイプＴ２に変換され、次いでタイプＴ２のある「ｖａｌｕｅＴ２」と比較される。元の比較から開始して、黙示比較ＣＬｏｗｅｒおよびＣＵｐｐｅｒを、それぞれ、４２０および４３０において定義する。
【００３５】
ここで、新たに得られた比較は直接列上にあり、既存のインデックスを直ちに適用することができる。黙示条件が元の条件と同等であるという保証はないので、インデックスから検索した全ての行に、元の条件をなおも適用する。しかしながら、この時点において、考慮すべき行数は、黙示比較によって減少している。
動的間隔
前述の黙示境界が十分ではない可能性があるという状況もあり得る。境界式は、オーバーフローまたはアンダーフローの問題を招く場合がある。したがって、単に比較を加算すると、無効な実行エラーが生ずる虞れがある。この問題に取り組み、更に生成した計画を最適化するために、クエリ実行時に動的間隔を生成する。ＳＱＬにおいて直接タイプ入力するもののような、正規の比較とは異なり、実行時比較フラグを生成する。このような比較フラグは、標準的な比較演算子、および３つのそれ以外の選択肢（alternative）がある。
【００３６】
・未満（ＬＴ）、以下（ＬＴＥ）、超過（ＧＴ）、以上（ＧＴＥ）等。
・全行認定（ＣＭＰＡＬＬ）
・非ヌル行全認定（ＣＭＰＮＯＴＮＵＬＬ）
・認定行無し（ＣＭＰＦＡＬＳＥ）
比較は、実行時に作成され、これらの中からどれを使用するか決定する。特定の列に対する各参照範囲は、境界値、および比較フラグによって構成され、各々実行時に動的に計算される。図５は、黙示境界の図を更に詳細化したものである。元の条件は、５１０において、タイプＴ１の列ｃｏｌＴ１として記述されており、これをタイプＴ２に変換し、次いである値Ｔ２と比較する。元の比較から開始し、黙示比較ＣＬｏｗｅｒおよびＣＵｐｐｅｒを、それぞれ、５２０および５３０において定義する。下側および上側境界に対して、それぞれ、５４０および５５０においてフラグを定義する。
【００３７】
１対の境界およびフラグをインデックス参照コードにおいて用い、指定した行を検索する。例えば、等式の場合は更に以下のように詳細化する。
元の条件：CONVERT(Aint, float) = 2.5
下側境界：TRUNCATE(2.5) = 2
下側境界フラグ：IF CONVERT(TRUNCATE(2.5), float) = 2.5 THEN GTE
ELSE FALSE
上側境界：TRUNCATE(2.5) = 2
下側境界フラグ：IF CONVERT(TRUNCATE(2.5), float) = 2.5 THEN LTE
ELSE FALSE
基本的に、比較すべき浮動小数点数（float）が「整数と整合した」場合、対象の特定値を調べる。それ以外の場合、変換の後一致する整数はないので、いずれの行も検索しない。最初の場合、得られる間隔は次のようになる。
【００３８】
【数３】
TRUNCATE(value) <= column <= TRUNCATE(value)
二番目の場合、変換が一致せず、次の境界が得られ、これは空である。
【００３９】
【数４】
TRUNCATE(value)CMPFALSE column
コンパイル時に式がわかっている場合、これらを実行し、特定の間隔に減少させることができる。しかし、通常、全てのパラメータ値がわかっている場合、これらはクエリ実行時に解き、評価しなければならない。間隔は実行時に動的に解明されるので、異なる値のパラメータによって、適正なインデックスの参照が行われる。
【００４０】
前述のプロセスを実行するようにクエリ・プロセッサを変更する。以下に示すのは、前述の方法を実行するコードにおける変更の概要である。
ｉ）インデックス処理コードは自動的に前述の形態の述語をシーク可能として識別する。
【００４１】
ｉｉ）比較およびそれに伴うタイプに応じて、境界を構築する。例えば、ｃｏｎｖｅｔ（ｃｏｌｕｍｎ）＝＜ｅｘｐｒ＞は、形態ｃｏｌｕｍｎ＞ｌｏｗｅｒｂｏｕｎｄおよびｃｏｌｕｍｎ＜ｕｐｐｅｒｂｏｕｎｄのシーク述語に変換する。
【００４２】
ｌｏｗｅｒｂｏｕｎｄは、実行時に評価される式によって設定され、＜ｅｘｐｒ＞を列のタイプに変換し、次いでタイプのドメインにおいて境界がセーフであることを保証する次に小さい値に到達する。したがって、整数列を浮動小数点式と比較するために、浮動小数点式を整数に切り捨て、「１」を減算する。ｕｐｐｅｒｂｏｕｎｄは、同様に、ｅｘｐｒを列のタイプに変換し、次いでタイプのドメインにおいて境界がセーフであることを保証する、次に大きい値に到達することによって構築する。
【００４３】
ｉｉｉ）境界の評価中にオーバーフローおよびアンダーフローのような実行時例外を捕らえるための機構を設け、この場合、比較フラグをＣＭＰＡＬＬにセットする。これは、関与するタイプに対するドメイン境界が交差するという稀な場合において、一定の意味を保証する。
【００４４】
ｉｖ）前述のような整数から浮動小数点数への変換の等式のような、一層精巧な関数を用いて公開およびフラグを計算することによって、対象となる特殊事例に対応する。
【００４５】
ｖ）元の述語を常に残余述語として結び付け、シークを満たし得る異質の行を全て排除する。何故なら、境界は不正確であり、境界の構築中に例外があり、シークはスキャンに変換されたからである。残余述語を適用することによるオーバーヘッドは、インデックスを使用可能とすることによって動的に減少した、適切な行をフェッチする際の実際のコストと比較すれば、無視し得る程度である。
結論
本願は、本発明のあらゆる改作および変形をも包含することを意図している。本発明は、特許請求の範囲およびその均等物によってのみ限定されることを、明白に意図している。関数に基づく比較を有する元の条件を含むクエリに、インデックスを用いる。インデックスは、作成してもよく、または所望の列に対する既存のインデックスを使用してもよい。最初に黙示条件を識別し、元の条件も満たす全ての行を認定するが、インデックス参照に用いることができる形態とする。黙示条件を満たす値を有する行を認定するために、インデックスを用いる。最後に、元の条件を用いて、識別した行に対しクエリを実行する。
【００４６】
尚、フラグを用いて例外を処理したが、クエリ実行計画における例外処理コードの使用を含む、他の構成も使用可能である。整数および浮動小数点のタイプ変換の例を用いたが、本発明は、時間や、異なる精度の数値のような他のタイプ変換や、ストリングの比較にも適用できることは理解されよう。
【図面の簡単な説明】
【図１】本発明を実現するコンピュータ・システムのブロック図である。
【図２】図２Ａは、本発明にしたがって、コンパイル時にクエリに対してインデックスを用いる動作全体を示すフローチャートである。図２Ｂは、本発明にしたがって実行時にクエリに対してインデックスを用いる動作全体を示すフローチャートである。
【図３】コンパイルおよび実行時における範囲の計算を示すフローチャートである。
【図４】元の条件および黙示条件の間の関係を示すブロック図である。
【図５】元の条件および黙示条件の間の関係、およびフラグの使用を示すブロック図である。
【符号の説明】
１００    計算デバイス
１０２    演算装置
１０４    メモリ
１０６    基本的コンフィギュレーション
１０８    リムーバブル・ストレージ
１１０    非リムーバブル・ストレージ
１１２    通信接続部
１１４    入力デバイス
１１６    出力デバイス
【図１】
0004879425.tif 000002
【図２】
0004879425.tif 000003
【図３】
0004879425.tif 000004
【図４】
0004879425.tif 000005
【図５】
0004879425.tif 000006