(57)【要約】  いくつかの実施形態では、データベースシステムのクエリオプティマイザは、第１のクエリを実施するために利用可能なの実行計画のセットの選択を制限する第１の制約を含む第１のクエリを受信する。第１の制約が、第１のクエリ内の句を実施するために少なくとも第１のオプションおよび第２のオプションを識別する。クエリオプティマイザが、第１の制約に基づいて、第１のオプションのパフォーマンスを含む第１の実行計画および第２のオプションのパフォーマンスを含む第２の実行計画を評価する。クエリオプティマイザが、評価に基づいて、第１のクエリを実施するために第１の実行計画と第２の実行計画のうちの１つを選択する。クエリオプティマイザが、選択した実行計画の実行を引き起こす。
2021515923.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータシステムに動作を実施させることができるプログラム命令を記憶した非一時的コンピュータ可読媒体であって、前記動作は、
データベースシステムのクエリオプティマイザによって、第１のクエリを実施するために利用可能な実行計画のセットの選択を制限する第１の制約を含む前記第１のクエリを受信することであって、前記第１の制約は、少なくとも、前記第１のクエリ内の句を実施するために第１のオプションおよび第２のオプションを識別する、受信することと、
前記クエリオプティマイザによって、前記第１の制約に基づいて、前記第１のオプションのパフォーマンスを含む第１の実行計画および前記第２のオプションのパフォーマンスを含む第２の実行計画を評価することと、
前記クエリオプティマイザによって、前記評価に基づいて、前記第１のクエリを実施するために前記第１の実行計画および前記第２の実行計画のうちの１つを選択することと、
前記クエリオプティマイザによって、前記選択した実行計画の実行を引き起こすことと、を含む、コンピュータ可読媒体。
【請求項２】
前記句が、前記データベースシステムからのデータの選択を要求し、前記第１のオプションが、前記選択を実行する際に使用される第１のインデックスを識別し、前記第２のオプションが、前記選択を実行する際に使用される第２のインデックスを識別する、請求項１に記載のコンピュータ可読媒体。
【請求項３】
前記句が、前記データベースシステム内の複数のテーブルからコンテンツを結合することを要求し、前記第１のオプションが、前記コンテンツを結合するために実行可能な第１のタイプの結合動作であり、前記第２のオプションが、前記コンテンツを結合するために実行可能な第２のタイプの結合動作である、請求項１に記載のコンピュータ可読媒体。
【請求項４】
前記第１のタイプの結合動作が、ハッシュ結合であり、前記第２のタイプの結合動作が、ネストされたループ結合である、請求項３に記載のコンピュータ可読媒体。
【請求項５】
前記句が、前記データベースシステム内の複数のテーブルからコンテンツを結合することを要求し、前記第１のオプションが、前記複数のテーブルからコンテンツを結合するための第１の順序であり、前記第２のオプションが、前記複数のテーブルからコンテンツを結合するための第２の順序である、請求項１に記載のコンピュータ可読媒体。
【請求項６】
前記動作が、さらに、
前記クエリオプティマイザによって、第２の制約を含む第２のクエリを受信することであって、前記第２のクエリが、結合動作を要求し、前記第２の制約は、前記結合動作がインデックスを使用するネストされたループ結合で実施されることを示す、受信することと、
前記クエリオプティマイザによって、前記第２の制約に基づいて、前記インデックスを使用した前記ネストされたループ結合のパフォーマンスを含む実行計画を評価することと、を含む、請求項１に記載のコンピュータ可読媒体。
【請求項７】
前記クエリオプティマイザによって、第２の制約を含む第２のクエリを受信することであって、前記第２の制約が、前記第２のクエリで指定されるテーブルのカーディナリティを識別する、受信することと、
前記クエリオプティマイザによって、前記識別したカーディナリティに基づいて複数の実行計画を評価することと、を含む、請求項１に記載のコンピュータ可読媒体。
【請求項８】
前記第１のクエリが、第２の制約を含む第２のクエリを含み、
前記動作が、さらに、
前記第１のクエリおよび前記第２のクエリを単一のクエリにマージすることであって、前記第１の制約および前記第２の制約を単一の制約にマージすることを含む、マージすることを含む、請求項１に記載のコンピュータ可読媒体。
【請求項９】
前記動作が、さらに、
前記クエリオプティマイザによって、第２の制約を含む第２のクエリを受信することと、
前記クエリオプティマイザによって、前記第２の制約を満たす実行計画が存在しないことを決定することと、
前記決定に応答して、前記クエリオプティマイザは前記第２の制約を満たす実行計画を決定することができないことを示す表示を提供することと、を含む、請求項１に記載のコンピュータ可読媒体。
【請求項１０】
前記動作が、さらに、
前記クエリオプティマイザによって、前記第２の制約を満たさない別の実行計画を選択することと、
前記クエリオプティマイザによって、前記選択した別の実行計画の実行を引き起こすことと、を含む、請求項９に記載のコンピュータ可読媒体。
【請求項１１】
データベースシステムのクエリオプティマイザによって、第１のクエリのための実行計画を実施するための複数のオプションを指定する第１の制約を含む前記第１のクエリを受信することと、
前記クエリオプティマイザによって、前記複数のオプションに対応する複数の実行計画を評価する分析を行うことと、
前記クエリオプティマイザによって、前記分析に基づいて、前記第１のクエリを実施するために前記複数の実行計画のうちの１つを選択することと、
前記クエリオプティマイザによって、前記選択した実行計画を実行するために前記データベースシステムの実行エンジンに前記選択した実行計画を提供することと、を含む方法。
【請求項１２】
前記第１の制約は、前記選択した実行計画が、第１の制約で識別された少なくとも２つのインデックスのうちの１つに基づくインデックススキャンを含むことを示す、請求項１１に記載の方法。
【請求項１３】
前記第１の制約は、前記選択した実行計画が、第１の制約で識別された少なくとも２つのタイプの物理結合動作のうちの１つを含むことを示す、請求項１１に記載の方法。
【請求項１４】
前記第１の制約は、前記選択した実行計画が、前記第１の制約で少なくとも部分的に指定された順序でテーブルの結合を行うことを示す、請求項１１に記載の方法。
【請求項１５】
第２のクエリための実行計画を実施するための複数のオプションを指定する第２の制約を含む前記第２のクエリを受信することと、
前記データベースシステムによって、前記第２の制約に対して実行計画が決定することができないことを示すエラーメッセージを提供することと、を含む請求項１１に記載の方法。
【請求項１６】
１つ以上のプロセッサと、
動作を行うデータベースを実施するために前記１つ以上のプロセッサによって実行可能なプログラム命令が記憶されたメモリと、を含み、前記動作は、
前記データベースのクエリを行うために第１の要求を受信することであって、前記第１の要求が、前記クエリの一部を実施するための複数のオプションを示す第１の制約を含む、受信することと、
前記複数のオプションのうちの少なくとも１つのパフォーマンスを含む複数の実行計画を分析することと、
前記分析に基づいて、前記クエリを実施するために前記複数の実行計画のうちの１つを選択することと、
前記クエリを行うために前記選択した実行計画を実行することと、を含むコンピュータシステム。
【請求項１７】
前記第１の制約は、前記第１の制約で指定された少なくとも２つのインデックスのうちの１つを使用して前記クエリが行われることを示す、請求項１６に記載のコンピュータシステム。
【請求項１８】
前記第１の制約は、前記第１の制約で指定された少なくとも２つの物理結合動作のうちの１つを使用して前記第１の要求で指定された結合が行われることを示す、請求項１６に記載のコンピュータシステム。
【請求項１９】
前記第１の制約は、前記第１の制約によって許可されたテーブルを結合するための少なくとも２つの順序のうちの１つを使用して前記第１の要求で指定された結合が行われることを示す、請求項１６に記載のコンピュータシステム。
【請求項２０】
前記動作が、さらに、
前記データベースのクエリを行うために第２の要求を受信することであって、前記第２の要求が第２の制約を含む、受信することと、
前記第２の制約を満たすことができないことを前記データベースのユーザに示すことと、を含む、請求項１６に記載のコンピュータシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、一般に、データベースシステムに関し、より具体的には、データベースクエリオプティマイザに関する。
【背景技術】
【０００２】
クエリがデータベースに提出されるとき、クエリの結果をどのように取得するかではなく、クエリの結果が何であるべきかを表すことができる。したがって、複数の異なるアプローチを使用してクエリを実行することが可能であることがある。たとえば、テーブルＡ、Ｂ、およびＣの結合を要求するクエリは、１）ＡとＢの結合の後にその結果とＣの結合、２）ＢとＣの結合の後にその結果とＡの結合、として実行されることがある。現在の関係データベースシステムは、典型的には、パースされたクエリ（parsed  query）を受信し、クエリを実行するための計画を決定するために異なる実行計画を評価するクエリオプティマイザを使用する。この評価は、推定された計算コストおよび記憶コストに基づいて各計画のスコアを決定することと、最良のスコアを有する計画を選択することとを含むことがある。したがって、クエリオプティマイザが、ＢとＣを結合する結果が、ＡとＢを結合する結果よりも小さな一時テーブルを生成する場合、上記の第２の計画に対してより良いスコアを提供するかもしれない。
【図面の簡単な説明】
【０００３】
【図１】クエリオプティマイザ制約をサポートするように構成されているデータベースシステムの一実施形態を示すブロック図である。
【図２】インデックス制約の一実施形態を示すブロック図である。
【図３】物理結合制約の一実施形態を示すブロック図である。
【図４】論理結合制約の一実施形態を示すブロック図である。
【図５】パラメタライズ制約の一実施形態を示すブロック図である。
【図６】カーディナリティ制約の一実施形態を示すブロック図である。
【図７】制約マージャの一実施形態を示すブロック図である。
【図８Ａ】データベースクエリにサービスを提供するための方法の実施形態を示すフロー図である。
【図８Ｂ】データベースクエリにサービスを提供するための方法の実施形態を示すフロー図である。
【図９】例示的なコンピュータシステムの一実施形態を示すブロック図である。
【発明を実施するための形態】
【０００４】
本開示は、「一実施形態」または「ある実施形態」への言及を含む。「一実施形態において」または「ある実施形態において」という語句が現れても、必ずしも同じ実施形態を指すわけではない。特定の特徴、構造、または特徴は、本開示と矛盾しない任意の適切な方式で組み合わせてもよい。
【０００５】
本開示の範囲内では、異なるエンティティ（様々に「ユニット」、「回路」、その他構成要素などと呼ばれる）が、１つ以上のタスクまたは動作を行うように「構成されている」ものとして説明または請求項に記載されることがある。この定式化−［１つ以上のタスクを行う］するように構成されている［エンティティ］−は、本明細書では、構造（すなわち、電子回路などの物理的なもの）を指すために使用される。より具体的には、この定式化は、この構造が、動作中に１つ以上のタスクを行うようにアレンジされていることを示すために使用される。構造は、その構造が現在動作中でなくても、いくつかのタスクを行うように「構成されている」と言うことができる。「データをテーブルに記憶するように構成されているデータベースシステム」は、例えば、コンピュータシステムが現在使用されていなくても（例えば、電源が接続されていない）、動作中にこの機能を行うためのプログラム命令を有する１つ以上のプロセッサおよびメモリを有するコンピュータシステムをカバーすることを意図している。したがって、いくつかのタスクを行うように「構成されている」と説明または規定されるエンティティは、デバイス、回路、そのタスクを実施するために実行可能なメモリ記憶プログラム命令などの物理的なものを指す。この語句は、本明細書では、無形のものを指すために使用されない。したがって、「構成されている」構造は、本明細書では、アプリケーション・プログラミング・インターフェース（ＡＰＩ）などのソフトウェア・エンティティを指すためには使用されない。
【０００６】
「構成されている」という用語は、「構成可能である」を意味することを意図していない。例えば、プログラムされていないＦＰＧＡは、いくつかの特定の機能を行うように「構成されている」とみなされないが、その機能を行うように「構成可能である」としてもよく、プログラミング後にその機能を行うように「構成されている」としてもよい。
【０００７】
添付の特許請求の範囲において、ある構造が１つ以上のタスクを行うように「構成されている」ことを規定することは、その請求項の要素に対して特米国許法第１１２条（ｆ）を連想させないことを明確に意図している。従って、本出願の請求項のいずれも、ミーンズ・プラス・ファンクション要素を有するものとして解釈されることは意図していない。万が一出願人が手続中に同第１１２条（ｆ）を連想させることを希望する場合、それは、［機能を行う］「ための手段」構造を使用して請求項の要素を規定する。
【０００８】
本明細書で使用されているように、「第１の」、「第２の」という用語などは、それらが先行する名詞のラベルとして使用されており、具体的に述べられない限り、いかなる種類の順序（例えば、空間的、時間的、論理的など）も示唆しない。例えば、データベースシステムが第１の要求と第２の要求を受信する場合、これらの要求は、いかなる順序でも受信することができる。言い換えると、「第１の」要求は、例えば、最初の要求に限定されない。
【０００９】
本明細書において、「に基づく」という用語は、決定に影響を及ぼす１つ以上の要因を説明するために使用される。この用語は、追加的要因が決定に影響を及ぼす可能性を排除しない。すなわち、決定は、特定の要因のみに基づいてもよいし、特定の要因および他の特定されていない要因に基づいてもよい。「Ｂに基づいてＡを決定する」という用語を考慮する。この用語は、ＢがＡを決定するために使用されるか、または、Ａの決定に影響を及ぼす要因であることを特定する。この用語は、Ａの決定が、Ｃのようないくつかの他の要因にも基づいてもよいことを排除しない。この用語はまた、ＡがＢのみに基づいて決定される実施形態をカバーすることを意図している。本明細書において使用されているように、「に基づく」という用語は、したがって、「少なくとも部分的に基づいて」という用語と同義である。
【００１０】
クエリオプティマイザは、所与のクエリに対して最も望ましい実行計画を必ずしも選択しないことがある。これは、クエリオプティマイザによって評価される様々なコストメトリックが誤った情報を含み得るという事実に起因することがある。たとえば、所与のテーブル（または列）に対して維持されている統計値は、古いか欠損していることがある。また、複数の述部（predicate）を含む複雑なクエリのコストを正確に推定することも困難であることがある。対照的に、ユーザ（またはアプリケーション）は、提出されているクエリだけでなく、データベースに記憶されているデータについても、より深い洞察を有することがある。さらに、ユーザは、特定のクエリに対してクエリオプティマイザによって選択されている実行計画が期待以下であり、改善することができると決定することができることがある。したがって、クエリオプティマイザは、この追加的な洞察から利益を得てもよい。
【００１１】
本開示は、データベースシステムのクエリオプティマイザが、所与のクエリを実施すると考えられる実行計画のセットを制限する指示（以下、クエリオプティマイザ制約と呼ぶ）を受信するように動作可能である実施形態を説明する。以下に説明するように、１つ以上の埋め込み制約を含むクエリが提出されることがある。次いで、これらの制約は、クエリの様々な実行計画を評価し、制約に準拠する計画を選択しようと試みるクエリオプティマイザに提供されてもよい。例えば、クエリは、スキャン、結合などの特定の種類を含む計画を選択するようにオプティマイザに指示する制約を含んでもよく、従って、ユーザは、クエリオプティマイザが、例えば、問題のある結合動作を含む計画を選択することを防止することができる。同様に議論されるように、様々な実施形態において、クエリオプティマイザは、クエリの句／部分を実施するための複数のオプションを識別する制約を受信することができる。次いで、クエリオプティマイザは、オプションに関連する実行計画を評価し、オプションのうちの１つを含む計画を選択できる。例えば、特定のスキャンが、制約内で識別される可能性のあるインデックスのうちの１つまたは２つを使用して行われるべきであることを示す制約が提出されてもよい。次いで、クエリオプティマイザは、第１のインデックスを使用するスキャンを含む計画と第２のインデックスを使用するスキャンを含む計画を評価し、その評価に基づいて計画のうちの１つを選択してもよい。従って、ユーザは、どの計画がクエリオプティマイザによって考慮されているか制限することができるが、複数の好ましいオプション間で選択するためにクエリオプティマイザのインテリジェンスを依然として活用してもよい。様々な実施形態では、クエリオプティマイザが、所与のクエリにおける制約を満たす計画を識別できない場合、クエリオプティマイザは、制約を満たすことができなかった理由の表示を依然として提供してもよく、いくつかの実施形態では、クエリオプティマイザは、準拠しない計画を選択し、その計画を実行させて、クエリが依然としてサービスされるようにする。
【００１２】
次に、図１を参照すると、クエリオプティマイザ制約１０４を有するクエリ１０２をサポートするように構成されているデータベースシステム１０のブロック図が示されている。図示された実施形態では、データベースシステム１０は、パーサ１１０、クエリオプティマイザ１２０、実行エンジン１３０、およびテーブル１４０を含む。いくつかの実施形態では、データベースシステム１０は、示されているものとは異なるように実施されてもよい。例えば、システム１０は、より多くの構成要素を含んでもよく、クエリ１０２は、異なる構文を使用して表現されてもよい。
【００１３】
データベースシステム１０は、任意の適切なデータベースシステムに対応してもよい。いくつかの実施形態では、システム１０は、リレーショナルデータベース管理システム（ＲＤＢＭＳ）であり、例えば、Ｏｒａｃｌｅ（登録商標）、ＭｙＳＱＬ（登録商標）、Ｍｉｃｒｏｓｏｆｔ（登録商標）  ＳＱＬ  Ｓｅｒｖｅｒ、ＰｏｓｔｇｒｅＳＱＬ、ＩＢＭ（登録商標）  ＤＢ２などを使用して実施されてもよい。従って、システム１０は、クエリ１０２をサービスするために１つ以上のデータテーブル１４０Ａにデータを記憶するように構成されてもよい。システム１０はまた、データテーブル１４０Ａからのデータの取り出しを容易にするために使用可能な１つ以上のインデックス１４０Ｂを維持し、クエリ１０２をサービスすることに応答して一時テーブル１４０Ｃを生成してもよい。図示された実施形態では、クエリ１０２は、構造化クエリ言語（ＳＱＬ）を使用して表現され、他の実施形態では、他のクエリ宣言型言語がサポートされてもよい。
【００１４】
パーサ１１０は、様々な実施形態において、１つ以上の制約１０４を含み得る提出されたクエリ１０２を解析するように動作可能である。いくつかの実施形態では、この構文解析は、クエリ１０２内の句の構文解析を行うことと、クエリオプティマイザ１２０によって処理され得るデータ構造（例えば、式ツリー）を組み立てることを含んでもよい。パーサ１１０はまた、任意の制約１０４をクエリ１０２から分離してもよい。図１の例示の実施形態では、パーサ１１０は、区切り文字／＊！  ．．．  ＊／の存在に基づいて制約１０４を識別する。ここで、．．．は制約のコンテンツである。他の実施形態では、異なる区切り文字（または技術）を使用して、制約１０４をクエリ１０２内の他のコンテンツから区別することができる。図７に関して説明するように、いくつかの実施形態では、パーサ１１０はまた、サブクエリを含む場合、クエリ１０２を平坦化しようと試みてもよい。この平坦化は、複数の制約１０４がクエリおよびそのサブクエリに対して指定されている場合、クエリおよびサブクエリを単一のクエリにマージすること、ならびに制約１０４を一緒にマージすることを含んでもよい。
【００１５】
クエリオプティマイザ１２０は、様々な実施形態において、所与のクエリ１０２に対する実行計画１１２を生成するように動作可能であり、これは種々の実行計画１２２を評価することと、クエリ１０２を実行するために１つを選択することを含む。オプティマイザ１２０は、任意の適切なアルゴリズムを使用して、計画１２２を評価および選択することができる。いくつかの実施形態において、オプティマイザ１２０は、実行計画１２２がオプティマイザ１２０に提供される規則のセットに基づいて評価されるヒューリスティックアルゴリズムを使用してもよい。他の実施形態では、オプティマイザ１２０は、コストベースのアルゴリズムを使用し、ここでは、オプティマイザ１２０は、推定されたプロセッサ消費量、推定されたメモリ消費量、推定された実行時間などに基づいて、実行計画１２２にスコアを割り当てることを含むコスト分析を行う。これらの推定値は、さらに、テーブル列内の重複しない値の数、述部の選択性（述部が修飾する行の割合）、図６に関して説明されるように、評価されるテーブル１４０Ａのカーディナリティ（例えば、行カウント）などの種々のメトリックに基づいてもよい。スコアに基づいて、オプティマイザ１２０は、次いで、最良のスコアを有する実行計画１２２を選択してもよい。さらに他の実施形態では、オプティマイザ１２０は、ヒューリスティックアルゴリズムとコストベースアルゴリズムとの組み合わせを使用してもよい。
【００１６】
上述のように、様々な実施形態では、クエリオプティマイザ１２０は、クエリ１０２に含まれる制約１０４に基づいて実行計画１２２を評価し、制約１０４に準拠する計画１２２を選択するようにさらに動作可能である。例えば、いくつかの実施形態では、クエリオプティマイザ１２０は、選択されることを排除するために、制約１０４に適合しない任意の実行計画１２２に好ましくないスコアを割り当てることがある（またはスコアさえ付けないことがある）。上述し、図１に示すように、様々な実施形態において、所与の制約１０４は、許容可能な実行計画１２２のために複数のオプション１０６を指定してもよい。例えば、図２に関して後述するように、図１に示される制約１０４は、オプティマイザ１２０に対して、クエリ１０２を実施するために、インデックスｉｄｘ１（オプション１０６Ａとして示される）を使用するインデックススキャン、またはインデックスｉｄｘ２（オプション１０６Ｂとして示される）を使用するインデックススキャンを含む計画１２２を選択するように指示する。（２つのオプション１０６Ａおよび１０６Ｂが図１およびその後のいくつかの図に示されているが、任意の数のオプション１０６が、様々な実施形態で指定されてもよい。）従って、オプティマイザ１２０は、選択のために、オプション１０６Ａを含む計画１２２およびオプション１０６Ｂを含む計画１２２を考慮し、オプション１０６Ａおよびオプション１０６Ｂのいずれも保持しない計画１２２（例えば、インデックススキャンを含まない計画１２２）を考慮しなくてもよい。制約１０４の様々な例は、図２〜図６に関して以下により詳細に説明される。これらの制約１０４は、例えば、どのようにスキャンが行われるかを制限する制約、どのように結合が行われるかを制限する制約、オプティマイザ１２０によって評価されるメトリックを上書きする制約などを含んでもよい。
【００１７】
様々な実施形態では、クエリオプティマイザ１２０が、所与のクエリ１０２に対する制約１０４を満たす実行計画１２２を選択できない場合、クエリオプティマイザ１２０は、図１のエラー１２４として示された対応する表示を提供するように動作可能である。いくつかの実施形態では、このエラー１２４は、制約１０４を満足するための計画１２２が存在しないことを示すだけでなく、複数の制約１０４がクエリ１０２で指定された場合には満足できない特定の制約１０４を識別することもできる。いくつかの実施形態では、クエリオプティマイザ１２０は、依然として実行計画１２２（制約１０４に準拠しないものでも）を選択し、それを計画実行エンジン１３０に提供してもよく、従って、ユーザは結果１３２を依然として受信するが、結果１３２が提供した制約１０４と矛盾する方式で得られたことを認識してもよい。しかしながら、他の実施形態では、クエリオプティマイザ１２０はエラー１２４を提供してもよく、クエリ１０２を実施するためのいかなる計画１２２を選択しなくてもよい。
【００１８】
実行計画１２２が選択されると、実行エンジン１３０は、様々な実施形態において、選択された計画１２２を実行するように動作可能となる。従って、エンジン１３０は、１つ以上のデータテーブル１４０Ａ、インデックス１４０Ｂ、および／または一時テーブル１４０Ｃにアクセスすることを含み得る計画１２２に列挙された種々のアクションを行ってもよい。次いで、エンジン１３０は、クエリ１０２にサービスするために任意の結果１３２を返してもよい。
【００１９】
次に、図２を参照すると、インデックス制約用法２００のブロック図が示されている。示されるように、データベースシステム１０は、テーブルから１つ以上の基準を満たすコンテンツを選択するクエリ１０２の要求を受信してもよい。図２に示された特定のクエリ１０２において、列ｂ１内の値が１０未満である行をテーブルｔ１から選択し、選択した行の数をカウントする要求がなされている。このようなクエリ１０２が受信されると、データベースシステム１０は、指定された基準を満たす行を識別するために、複数のタイプのスキャン動作をサポートすることができる。例えば、データベースシステム１０は、実行エンジン１３０が列ｂ１内の各値を検討し、それが１０未満であるかどうかを決定することを行ごとに見回る逐次スキャンをサポートしてもよい。データベースシステム１０はまた、インデックスが関心のある特定の行を識別するように参照されるインデックススキャンをサポートしてもよい。例えば、所与の値を列ｂ１内の値を有する各行にマッピングするインデックス１４０Ｂが存在してもよい。従って、このインデックスに基づくインデックススキャンを使用することは、例えば、９、８、７などの値を有する行が、１０を超える値を有する行を考慮する必要なく、インデックスを使用して識別され得るので、より効率的であり得る。
【００２０】
図示された実施形態では、クエリオプティマイザ１２０は、クエリオプティマイザ１２０に、インデックススキャンのための複数のオプション１０６の１つを含む計画１２２を選択するように指示するインデックス制約１０４をサポートする。図２に示す具体例において、オプション１０６Ａ「ＩＮＤＥＸ（ｔ１  ｉｄｘ１）」は、テーブルｔ１のインデックスｉｄｘ１を使用するインデックススキャンが許容可能であることを示す。オプション１０６Ｂ「ＩＮＤＥＸ（ｔ２  ｉｄｘ２）」は、テーブルｔ１のインデックスｉｄｘ２を使用するインデックススキャンも許容可能であることを示す。したがって、これらの２つのオプション１０６Ａおよび１０６Ｂに基づいて、クエリオプティマイザ１２０は、逐次スキャンｔ１を含む実行計画１２２Ａを考慮しなくてもよく、オプション１０６Ａを含む実行計画１２２Ｂおよびオプション１０６Ｂを有する実行計画１２２Ｃを評価する。この評価に基づいて、オプティマイザ１２０は、次に、実行エンジン１３０による実行のために計画１２２Ｂおよび１２２Ｃのうちの好ましいものを選択する。
【００２１】
次に、図３を参照すると、物理結合制約用法３００のブロック図が示されている。示されるように、２つ以上のテーブルからのコンテンツの結合を要求するクエリ１０２が受信されてもよい。図３に示された特定のクエリ１０２において、ｔ１の列ａ１の値がｔ２の列ａ２の値と一致する場合、テーブルｔ１およびｔ２の行を結合する要求がなされる。
【００２２】
クエリにおける結合の表現は、本明細書では「論理結合」と呼ばれることがある。論理結合は、実行エンジン１３０が論理結合を実施するために行われる動作である「物理結合」とは対照的である。様々な実施形態では、データベースシステム１０は、「ネストされたループ結合」、「ハッシュ結合」、「マージ結合」などの複数のタイプの物理結合をサポートする。本明細書で使用されるように、「ネストされたループ結合」という語句は、その通常の意味および確立された意味に従って解釈される。この意味には、左関係（または右関係）にある各要素が、左関係（または右関係）にあるすべての行に対して一度にスキャンされる結合が含まれる。例えば、列ａ１の各値は、列ａ２のすべての値に対してスキャンされる。本明細書で使用されるように、「ハッシュ結合」という語句は、その通常および確立された意味に従って解釈される。この意味には、１）右関係（または左関係）が最初にスキャンされ、ハッシュキーとして結合属性を使用して、ハッシュテーブルに読み込まれ、２）左関係（または右関係）がスキャンされ、見つかったすべての行の適切な値がハッシュキーとして使用されて、テーブル内の一致する行に位置させる、結合が含まれる。本明細書で使用されているように、「マージ結合」という語句は、通常の意味および確立された意味に従って解釈される。この意味には、１）各リレーションが結合開始前に結合属性でソートされ、２）２つの関係が並行にスキャンされ、３）一致する行が組み合わされて結合行を形成する、結合が含まれる。
【００２３】
図示された実施形態では、クエリオプティマイザ１２０は、オプション１０６によって示される複数のタイプの物理結合のうちの１つを含む計画１２２を選択するようにクエリオプティマイザ１２０に指示する物理結合制約１０４をサポートする。図３に示す具体例において、オプション１０６Ａ「ＨＡＳＨ＿ＪＯＩＮ（ｔ１  ｔ２）」は、テーブルｔ１とテーブルｔ２のハッシュ結合を望むことを示す。オプション１０６Ｂ「ＭＥＲＧＥ＿ＪＯＩＮ（ｔ１  ｔ２）」は、テーブルｔ１とテーブルｔ２のマージ結合を望むことを示す。従って、これらの２つのオプション１０６Ａおよび１０６Ｂに基づいて、クエリオプティマイザ１２０は、テーブルｔ１およびｔ２のネストされたループ結合を含む実行計画１２２Ａを考慮しなくてもよく、代わりに、オプション１０６Ａに対応するハッシュ結合を含む実行計画１２２Ｂおよびオプション１０６Ｂに対応するマージ結合を含む実行計画１２２Ｃを評価する。この評価に基づいて、オプティマイザ１２０は、次に、実行エンジン１３０による実行のための計画１２２Ｂおよび１２２Ｃのうちの好ましい１つを選択する。
【００２４】
次に、図４を参照すると、論理結合制約用法４００のブロック図が示されている。背景技術で上述したように、３つ以上のテーブル間の結合は、複数の異なる順序を使用して実施されてもよい。いくつかの実施態様において、クエリオプティマイザ１２０は、テーブルを結合するための全体の順序を表現せずに、部分順序４０２をオプティマイザ１２０に表現することができる論理制約１０４をサポートし、それによりオプティマイザが複数の順序オプションの間で選択することを可能にする。
【００２５】
図示された実施形態では、部分順序４０２は、結合されるテーブルに優先値４０４が割り当てられる文法を使用して表現される。（他の実施形態では、異なる文法が、部分順序４０２を表現するために使用されてもよい）。例えば、示されるように、テーブルｔ１およびｔ２は、優先値１を割り当てられ、他のテーブルは、優先値０を割り当てられる。いくつかの実施形態では、より大きな優先値を割り当てられたテーブルは、より早く行われるが、同じ値を割り当てられたテーブルは、任意の順序で実行されてもよい。したがって、このような実施形態では、値１を有するテーブルｔ１およびｔ２は、値０を有するテーブルｔ３およびｔ４よりも結合において早い順とされるが、テーブルｔ１またはテーブルｔ２のいずれかが、順序における最初のテーブルであってもよい。したがって、ｔ１、ｔ２、ｔ３、およびｔ４の順序４０６Ｂおよびｔ２、ｔ１、ｔ４、ｔ３の順序４０６Ｃは、図４に示される部分順序４０２に準拠する。ただし、ｔ４、ｔ３、ｔ２、ｔ１の順序４０６Ａは、この例では、ｔ１、ｔ２の優先値よりもｔ４、ｔ３の優先値の方が低いため、準拠していない。その結果、クエリオプティマイザ１２０は、準拠しない順序４０６Ａを有する実行計画１２２Ａを考慮せず、準拠する順序４０６Ｂおよび４０６Ｃを有するこれらの計画１２２Ｂおよび計画１２２Ｃのみを評価してもよい。
【００２６】
次に、図５を参照すると、パラメタライズ制約用途５００のブロック図が示されている。図３で上述したように、クエリ１０２は、クエリ１０２で指定された結合を実施するために使用される物理結合のタイプを示す物理結合制約１０４を含んでもよい。ネストされたループ結合が指定された場合、ネストされたループ結合は、逐次スキャンまたはインデックススキャンを使用して実施されてもよい。
【００２７】
いくつかの実施形態では、クエリオプティマイザ１２０は、インデックススキャンが使用されることを示すために、パラメタライズ制約１０４をサポートする。図５に示される特定の例において、「ＰＡＲＡＭ（ｔ２（ｔ１））」は、ｔ１の値がパラメータ化され、結合の対応する行を識別するためにｔ２に対するインデックスに供給されることを示す。たとえば、ｔ１の値がａ１に対して１，２および３であるとする。インデックススキャンが行われるときに、ａ１に対する値１が列ａ２に対するインデックスｔ２へのインデックススキャン述部入力となるようにｔ１がスキャンされる。次いで、一致する行が、ネストされたループ結合によって形成および出力される。次に、このプロセスは、ａ１の値２および３について繰り返される。インデックススキャンでは、述部で値が置き換えられるため、このタイプの計画は、パラメメタライズ計画と呼ばれる。
【００２８】
次に、図６を参照すると、カーディナリティ制約用法６００のブロック図が示されている。上述のように、テーブル１４０のカーディナリティ（すなわち、テーブルのサイズ）は、クエリオプティマイザ１２０による様々な実行計画１２２Ａの評価に影響することがある。いくつかの実施形態では、テーブルのカーディナリティは、（オプティマイザ１２０にデータベースカタログからカーディナリティを読み込ませるのとは対照的に）クエリ１０２においてカーディナリティ制約１０４を提供することによって、オプティマイザ１２０に表現され得る。例えば、図６に示されるように、カーディナリティ制約１０４「ＢＡＳＥ＿ＣＡＲＤ（ｔ１  ｔ２  ５００）」は、テーブルｔ１およびｔ２が５００行を含むことを示す。特に、図示された実施形態では、同じ制約１０４が、クエリ１０２のためにアクセスされる複数のテーブルのカーディナリティを指定するために使用される。この情報に基づいて、クエリオプティマイザ１２０は、９９行が、ネストされたループ結合を望ましくないものにするのに十分に大きい場合に、ネストされたループ結合が行われる実行計画１２２Ａを考慮しないと決定してもよい。代わりに、クエリオプティマイザ１２０は、ハッシュ結合を含む実行計画１２２Ｂ、またはマージ結合を含む実行計画１２２Ｃを、これらの物理結合が、テーブルｔ１のサイズに対してより効率的であり得るとして選択してもよい。いくつかの実施形態では、クエリオプティマイザ１２０は、クエリ１０２の結果として生成されるテーブルのカーディナリティを示すカーディナリティ制約１０４もサポートする。例えば、図６に示されたクエリ１０２において、制約１０４「ＣＡＲＤ（ｔ１  ９９）」を含めることは、ｔ１とｔ２の結合から生成されたテーブルが９９行を有することをオプティマイザ１２０に示してもよい。この情報に基づいて、オプティマイザ１２０は、異なる実行計画１２２を選択してもよい。
【００２９】
次に、図７を参照すると、計画制約マージャ７００のブロック図が示される。上述し、図７に示されるように、別のクエリ１０２Ｂを含むクエリ１０２Ａが受信されてもよい。さらに、クエリ１０２Ａおよび１０２Ｂは、それぞれ、複数の制約１０４Ａおよび１０４Ｂを含んでもよい。図示された実施形態では、パーサ１１０は、これらのネストされたクエリ１０２を識別し、それらを一緒にマージできるかどうかを決定するように動作可能である。（別の実施形態では、この分析は、クエリオプティマイザ１２０によって実行されてもよい）この決定に基づいて、パーサ１１０は、クエリ１０２Ａおよび１０２Ｂから単一のマージされたクエリ１０２Ｃ、ならびに制約１０４Ａおよび１０４Ｂから単一のマージされた制約１０４Ｃを生成してもよい。
【００３０】
次に、図８Ａを参照すると、データベースクエリを実行するための方法８００のフローチャートが示されている。一実施形態では、方法８００は、クエリオプティマイザ１２０のようなデータベースシステムのクエリオプティマイザによって行われる。いくつかの例において、方法８００のパフォーマンスは、より大きなユーザ制御およびより良好な実行計画が潜在的に選択されることを可能にする。
【００３１】
ステップ８１０において、第１のクエリを実施するために利用可能な実行計画のセット（例えば実行計画１２２）の選択を制限する第１の制約（例えば制約１０４）を含む第１のクエリ（例えばクエリ１０２）が受信される。様々な実施形態では、第１の制約は、少なくとも、第１のクエリ内の句を実施するために第１のオプション（例えば、オプション１０６Ａ）および第２のオプション（例えば、オプション１０６Ｂ）を識別する。いくつかの実施形態では、句は、データベースシステムからのデータの選択を要求し（例えば、インデックス制約用法２００におけるＳＱＬ  ＳＥＬＥＣＴ）、第１のオプションは、選択を実行する際に使用される第１のインデックスを識別し、第２のオプションは、選択を実行する際に使用される第２のインデックスを識別する。いくつかの実施形態では、句は、データベースシステム内の複数のテーブルからコンテンツを結合することを要求し（例えば、物理結合制約用法３００におけるＳＱＬ  ＪＯＩＮ）、第１のオプションは、コンテンツを結合するために実行可能な第１のタイプの結合動作（例えば、ハッシュ結合）であり、第２のオプションは、コンテンツを結合するために実行可能な第２のタイプの結合動作（例えば、マージ結合）である。いくつかの実施形態では、句は、データベースシステム内の複数のテーブルからコンテンツを結合することを要求し（例えば、論理結合制約使用法４００におけるＳＱＬ  ＪＯＩＮ）、第１のオプションは、複数のテーブルからコンテンツを結合するための第１の順序（例えば、順序４０４Ａ）であり、第２のオプションは、複数のテーブルからコンテンツを結合するための第２の順序（例えば、順序４０４Ｂ）である。
【００３２】
ステップ８２０において、第１のオプションのパフォーマンスを含む第１の実行計画と、第２のオプションのパフォーマンスを含む第２の実行計画が、第１の制約に基づいて評価される。
【００３３】
ステップ８３０において、評価に基づいて、第１のクエリを実施するために第１の実行計画および第２の実行計画のうちの１つが選択される。
【００３４】
ステップ８４０において、選択した実行計画の実行が引き起こされる。様々な実施形態では、引き起こすことは、クエリオプティマイザが実行のための実行エンジンに選択した実行計画を提供することを含む。
【００３５】
いくつかの実施形態では、方法８００は、さらに、第２の制約（例えば、パラメータ制約１０４）を含む第２のクエリを受信することを含み、第２のクエリは、結合動作を要求し、第２の制約は、結合動作がインデックスを使用するネストされたループ結合で実施されることを示す。このような実施形態では、方法８００は、第２の制約に基づいて、インデックスを使用するネストされたループ結合のパフォーマンスを含む実行計画を評価することを含む。いくつかの実施形態では、方法８００は、第２の制約（例えば、カーディナリティ制約１０４）を含む第２のクエリを受信することを含み、第２の制約は、第２のクエリで指定されたテーブルのカーディナリティを識別する。このような実施形態では、方法８００は、識別したカーディナリティに基づいて複数の実行計画を評価することを含む。いくつかの実施形態では、第１のクエリ（例えば、制約１０４Ａを含む）は、第２の制約（例えば、制約１０４Ｂ）を含む第２のクエリを含み、方法８００は、第１のクエリおよび第２のクエリを単一のクエリにマージすることを含み、第１の制約および第２の制約を単一の制約（例えば、マージされた制約１０４Ｃ）にマージすることを含む。いくつかの実施形態では、方法８００は、第２の制約を含む第２のクエリを受信することと、クエリオプティマイザによって、第２の制約を満たす実行計画が存在しないことを決定することと、決定に応答して、クエリオプティマイザが第２の制約を満たす実行計画を決定することができない旨の表示（例えば、エラー１２４）を提供することと、を含む。いくつかの実施形態では、方法８００は、さらに、第２の制約を満たさない別の実行計画を選択することと、選択した別の実行計画の実行を引き起こすことと、を含む。
【００３６】
次に、図８Ｂを参照すると、データベースクエリを行うための方法８５０のフローチャートが示されている。一実施形態では、方法８００は、データベースシステム１０によって埋め込まれたデータベースのようなオプティマイザ制約を受信することができるデータベースのクエリオプティマイザによって行われる。いくつかの例において、方法８００のパフォーマンスは、より大きなユーザ制御およびより良好な実行計画が潜在的に選択されることを可能にする。
【００３７】
方法８５０は、データベースのクエリ（例えば、クエリ１０２）を行うために第１の要求を受信するステップ８６０において開始し、第１の要求は、クエリの一部を実施するための複数のオプション（例えば、オプション１０６）を示す第１の制約（例えば、制約１０４）を含む。いくつかの実施形態では、第１の制約（例えば、インデックス制約１０４）は、クエリが、第１の制約で指定された少なくとも２つのインデックスのうちの１つを使用して行われることを示す。いくつかの実施形態では、第１の制約（例えば、物理結合制約１０４）は、第１のリクエストで指定された結合が、第１の制約で指定された少なくとも２つの物理結合動作のうちの１つを使用して行われることを示す。いくつかの実施形態では、第１の制約（例えば、論理結合制約１０４）は、第１のリクエストで指定された結合が、第１の制約によって許可されたテーブルを結合するための少なくとも２つの順序のうちの１つを使用して行われることを示す。ステップ８７０において、複数のオプションのうちの少なくとも１つのパフォーマンスを含む複数の実行計画が分析される。ステップ８８０において、分析に基づいて、複数の実行計画のうちの１つが、クエリを実施するために選択される。ステップ８９０において、選択した実行計画がクエリを行うために実行される。いくつかの実施形態では、方法８５０は、さらに、データベースのクエリを行うために第２の要求を受信することを含み、第２の要求は、第２の制約を含み、（例えば、エラー１２４を介して）データベースのユーザに、第２の制約を満たすことができないことを示す。
【００３８】
例示的なコンピュータシステム
図９を参照すると、データベースシステム１０を実施することができる例示的なコンピュータシステム９００のブロック図が示されている。コンピュータシステム９００は、相互接続９６０（例えば、システムバス）を介してシステムメモリ９２０およびＩ／Ｏインターフェース９４０に結合されているプロセッササブシステム９８０を含む。Ｉ／Ｏインターフェース９４０は、１つ以上のＩ／Ｏデバイス９５０に結合されている。コンピュータシステム９００は、サーバ・システム、パーソナル・コンピュータシステム、デスクトップ・コンピュータ、ラップトップ・コンピュータまたはノートブック・コンピュータ、メインフレーム・コンピュータシステム、タブレット・コンピュータ、ハンドヘルド・コンピュータ、ワークステーション、ネットワーク・コンピュータ、携帯電話、音楽プレーヤ、パーソナル・データ・アシスタント（ＰＤＡ）などの消費者デバイスを含むが、これらに限定されない、様々なタイプのデバイスのいずれかであってもよい。便宜上、単一のコンピュータシステム９００が図９に示されているが、システム９００は、一緒に動作する２つ以上のコンピュータシステムとして実施されてもよい。
【００３９】
プロセッササブシステム９８０は、１つ以上のプロセッサまたは処理ユニットを含んでもよい。コンピュータシステム９００の様々な実施形態において、プロセッササブシステム９８０の複数のインスタンスが相互接続９６０に結合されてもよい。様々な実施形態において、プロセッササブシステム９８０（または９８０内の各プロセッサユニット）は、キャッシュまたはオンボード・メモリの他の形態を含んでもよい。
【００４０】
システムメモリ９２０は、システム９００に本明細書で説明される様々な動作を行わせる、プロセッササブシステム９８０によって実行可能なプログラム命令を記憶するように使用可能である。システムメモリ９２０は、ハード・ディスク・ストレージ、フロッピー・ディスク・ストレージ、リムーバブル・ディスク・ストレージ、フラッシュ・メモリ、ランダム・アクセス・メモリ（ＲＡＭ−ＳＲＡＭ、ＥＤＯ  ＲＡＭ、ＳＤＲＡＭ、ＤＤＲ  ＳＤＲＡＭ、ＲＡＭＢＵＳ  ＲＡＭなど）、リード・オンリー・メモリ（ＰＲＯＭ、ＥＥＰＲＯＭなど）のような、異なる物理的なメモリ媒体を使用して実施されてもよい。コンピュータシステム９００内のメモリは、メモリ９２０のような一次ストレージに限定されない。むしろ、コンピュータシステム９００はまた、プロセッササブシステム９８０内のキャッシュメモリおよびＩ／Ｏデバイス９５０上の二次ストレージ（例えば、ハード・ドライブ、ストレージ・アレイなど）のような他の形態のストレージを含んでもよい。いくつかの実施形態において、これらの他の形態のストレージはまた、プロセッササブシステム９８０によって実行可能なプログラム命令を記憶してもよい。いくつかの実施形態において、上述のデータベースシステム１０の一部は、システムメモリ９２０を含んでもよい（またはシステムメモリ９２０内に含まれてもよい。）。
【００４１】
Ｉ／Ｏインターフェース９４０は、様々な実施形態に従って、他のデバイスに結合し、かつ他のデバイスと通信するように構成されている様々なタイプのインターフェースのいずれかであってもよい。一実施形態では、Ｉ／Ｏインターフェース９４０は、フロントサイドから１つ以上のバックサイドバスへのブリッジチップ（例えば、サウスブリッジ）である。Ｉ／Ｏインターフェース９４０は、１つ以上の対応するバスまたは他のインターフェースを介して１つ以上のＩ／Ｏデバイス９５０に結合されてもよい。Ｉ／Ｏデバイス９５０の例は、ストレージデバイス（ハード・ドライブ、光学ドライブ、リムーバブル・フラッシュ・ドライブ、ストレージ・アレイ、ＳＡＮ、またはそれらに関連するコントローラ）、ネットワークインターフェースデバイス（例えば、ローカルまたはワイドエリアネットワークへ）、または他のデバイス（例えば、グラフィックス、ユーザ・インターフェース・デバイスなど）を含む。一実施形態では、コンピュータシステム９００は、ネットワークインターフェースデバイス９５０（例えば、Ｗｉ−Ｆｉ、Ｂｌｕｅｔｏｏｔｈ（登録商標）、Ｅｔｈｅｒｎｅｔ（登録商標）などを介して通信するように構成されている）を介してネットワークに結合される。
【００４２】
特定の実施形態が上述されたが、これらの実施形態は、たとえ単一の実施形態が特定の特徴に関して説明されている場合でも、本開示の範囲を制限することを意図していない。本開示において提供される特徴の例は、特に指定がない限り、限定的ではなく例示的であることを意図している。上記の説明は、本開示の利益を有する当業者に明らかなように代替、修正、および等価物をカバーすることを意図している。
【００４３】
本開示の範囲は、本明細書で対処される問題のいずれかまたは全部を緩和するかどうかにかかわらず、本明細書に開示されている任意の特徴もしくは特徴の組み合わせ（明示的または暗示的のいずれか）、またはその任意の一般化を含む。従って、新たなクレームは、このような特徴の組み合せについて本出願の手続中に定式化されることがある。特に、添付の特許請求の範囲を参照すると、従属請求項からの特徴は、独立クレームの特徴と組み合わせてもよく、各独立請求項からの特徴は、添付の特許請求の範囲に列挙された特定の組み合わせだけでなく、任意の適切な方式で組み合わせてもよい。
【図１】
2021515923.tif 000003
【図２】
2021515923.tif 000004
【図３】
2021515923.tif 000005
【図４】
2021515923.tif 000006
【図５】
2021515923.tif 000007
【図６】
2021515923.tif 000008
【図７】
2021515923.tif 000009
【図８Ａ】
2021515923.tif 000010
【図８Ｂ】
2021515923.tif 000011
【図９】
2021515923.tif 000012
【国際調査報告】
2021515923.tif 000013
2021515923.tif 000014
2021515923.tif 000015