(57)【要約】本願は、コスト最適化装置、コスト推定の方法およびそのデバイスを提供し、取得された統計情報が不備であると判断すれば、第１操作タイプのコスト推定方式を確定し、前記コスト推定方式に基づき、統計情報に依存する操作ツリーの操作タイプである前記第１操作タイプの第１コスト推定を確定し、該第１コスト推定、および統計情報に依存しない操作ツリーの操作タイプである第２操作タイプのコスト推定に基づき、操作ツリーの累積したコスト推定を確定する。
2021504852.tif 000002
【特許請求の範囲】
【請求項１】
取得された統計情報が完備であるか否かを判断し、前記統計情報が不備であれば、前記統計情報に依存する操作ツリーの操作タイプである第１操作タイプのコスト推定方式を確定することと、
前記コスト推定方式に基づいて前記第１操作タイプの第１コスト推定を確定することと、
前記第１コスト推定、および前記統計情報に依存しない操作ツリーの操作タイプである第２操作タイプの第２コスト推定に基づき、前記操作ツリーの累積したコスト推定を確定することと、
を含む、コスト推定の方法。
【請求項２】
前記第１操作タイプは、テーブルスキャン操作、フィルタリング操作、結合操作および集計操作を含む、請求項１に記載の方法。
【請求項３】
前記累積したコスト推定に基づいて構造化照会言語（ＳＱＬ）の語句に対応する実行計画を最適化することを更に含む、請求項１に記載の方法。
【請求項４】
前記コスト推定方式に基づいて前記第１操作タイプの第１コスト推定を確定することは、
データセットのレコード数に基づいてテーブルスキャン操作のコスト推定を確定することと、
フィルタリング述語のタイプに基づいてフィルタリング条件の選択率を確定し、前記選択率に基づいてフィルタリング操作のコスト推定を確定することと、
確定された結合結果セットのレコード数に基づいて結合操作のコスト推定を確定することと、
集計フィールドおよび集計関数に基づいて集計フィールドの集計率を確定し、前記集計率に基づいて集計操作のコスト推定を確定することと、
を含む、請求項２に記載の方法。
【請求項５】
フィルタリング述語のタイプに基づいてフィルタリング条件の選択率を確定することは、
フィルタリング述語のタイプに対応する、選択率を計算するオブジェクトが取得可能であるか否かを判断し、前記選択率を計算するオブジェクトが取得不可であれば、前記フィルタリング条件の選択率Ｓ＝１／指定値である、請求項４に記載の方法。
【請求項６】
フィルタリング述語のタイプに対応する、選択率を計算するオブジェクトが取得可能であるか否かを判断し、前記選択率を計算するオブジェクトが取得不可であれば、前記フィルタリング条件の選択率Ｓ＝１／指定値であることは、
フィルタリング述語のタイプがイコール述語である場合、前記フィルタリング操作の異値数が取得可能であるか否かを判断し、前記フィルタリング操作の異値数が取得不可であれば、前記フィルタリング条件の選択率Ｓ＝１／指定値であることと、
フィルタリング述語のタイプが範囲述語である場合、述語のフィールドの極値または異値数が取得不可であれば、前記フィルタリング条件の選択率Ｓ＝１／指定値であることと、
フィルタリング述語のタイプが空判別述語である場合、述語フィールドの空値数が取得可能であるか否かを判断し、前記述語フィールドの空値数が取得不可であれば、前記フィルタリング条件の選択率Ｓ＝１／指定値であることと、
を含む、請求項５に記載の方法。
【請求項７】
フィルタリング述語のタイプに基づいてフィルタリング条件の選択率を確定することは、
フィルタリング述語のタイプがｌｉｋｅである場合、前記フィルタリング条件の選択率Ｓ＝１／指定値であることと、
フィルタリング述語のタイプがＡＮＤカスケード述語である場合、カスケード述語の選択率の積およびＡＮＤカスケード述語におけるフィルタリング率の最小値に基づいて前記フィルタリング条件の選択率を確定することと、
フィルタリング述語のタイプがＯＲカスケード述語である場合、前記ＯＲカスケード述語に対応するカスケード述語の選択率に基づいて前記フィルタリング条件の選択率を確定することと、
を含む、請求項４に記載の方法。
【請求項８】
確定された結合結果セットのレコード数に基づいて結合操作のコスト推定を確定する前に、
結合された左テーブルおよび右テーブルの結合フィールドの異値数が取得不可であれば、結合フィールドの結合タイプに基づいて結合結果セットのレコード数を確定することを含む、請求項４に記載の方法。
【請求項９】
結合フィールドの結合タイプに基づいて結合結果セットのレコード数を確定することは、
結合フィールドの結合タイプが主キー−外部キー形式の結合である場合、外部キーフィールドのレコード数および主キーフィールドのフィルタリング条件の選択率に基づいて結合結果セットのレコード数を確定することと、
結合フィールドの結合タイプが内部結合である場合、結合された左テーブルのレコード数および右テーブルのレコード数のうちの最大値を結合結果セットのレコード数とすることと、
結合フィールドの結合タイプがクロス結合である場合、結合された左テーブルのレコード数と右テーブルのレコード数との積を結合結果セットのレコード数とすることと、
結合フィールドの結合タイプが左外部結合である場合、結合された左テーブルのレコード数を結合結果セットのレコード数とし、結合フィールドの結合タイプが右外部結合である場合、結合された右テーブルのレコード数を結合結果セットのレコード数とすることと、
結合フィールドの結合タイプが完全結合である場合、結合された左テーブルのレコード数および右テーブルのレコード数の累積を結合結果セットのレコード数とすることと、
を含む、請求項８に記載の方法。
【請求項１０】
集計フィールドおよび集計関数に基づいて集計フィールドの集計率を確定することは、
集計フィールドのセットに少なくとも１つの主キーが存在する場合、集計フィールドの集計率Ｒａｇｇ＝１であることと、
集計フィールドに対応する集計関数が単純な集計関数である場合、集計フィールドの集計率Ｒａｇｇは、
（式１）
【数１】
2021504852.tif 000041
であることと、
（ただし、ｎは集計フィールドのセットにおける集計フィールドの個数である）
集計フィールドに対応する集計関数がＲｏｌｌｕｐである場合、集計フィールドの集計率Ｒａｇｇは、
（式２）
【数２】
2021504852.tif 000042
であることと、
（ただし、ｎは集計フィールドのセットにおける集計フィールドの個数であり、ｋは正の整数である）
集計フィールドに対応する集計関数がＣｕｂｅである場合、集計フィールドの集計率Ｒａｇｇは、
（式３）
【数３】
2021504852.tif 000043
であることと、
（ただし、ｎは集計フィールドのセットにおける集計フィールドの個数であり、ｋは正の整数である）
を含む、請求項４に記載の方法。
【請求項１１】
取得された統計情報が完備であるか否かを判断し、前記統計情報が不備であれば、前記統計情報に依存する操作ツリーの操作タイプである第１操作タイプのコスト推定方式を確定するように構成される判断装置と、
前記コスト推定方式に基づいて前記第１操作タイプの第１コスト推定を確定するように構成される確定装置と、
前記第１コスト推定、および前記統計情報に依存しない操作ツリーの操作タイプである第２操作タイプに対応する第２コスト推定に基づき、前記操作ツリーの累積したコスト推定を確定するように構成される推定装置と、
を備える、コスト推定のデバイス。
【請求項１２】
前記第１操作タイプは、テーブルスキャン操作、フィルタリング操作、結合操作および集計操作を含む、請求項１１に記載のデバイス。
【請求項１３】
前記累積したコスト推定に基づいて構造化照会言語（ＳＱＬ）の語句に対応する実行計画を最適化するように構成される実行装置を更に含む、請求項１１に記載のデバイス。
【請求項１４】
前記確定装置は、
データセットのレコード数に基づいてテーブルスキャン操作のコスト推定を確定し、
フィルタリング述語のタイプに基づいてフィルタリング条件の選択率を確定し、前記選択率に基づいてフィルタリング操作のコスト推定を確定し、
確定された結合結果セットのレコード数に基づいて結合操作のコスト推定を確定し、
集計フィールドおよび集計関数に基づいて集計フィールドの集計率を確定し、前記集計率に基づいて集計操作のコスト推定を確定するように構成される、請求項１２に記載のデバイス。
【請求項１５】
前記確定装置は、
フィルタリング述語のタイプに対応する、選択率を計算するオブジェクトが取得可能であるか否かを判断し、前記選択率を計算するオブジェクトが取得不可であれば、前記フィルタリング条件の選択率Ｓ＝１／指定値であるように構成される、請求項１４に記載のデバイス。
【請求項１６】
前記確定装置は、
フィルタリング述語のタイプがイコール述語である場合、前記フィルタリング操作の異値数が取得可能であるか否かを判断し、前記フィルタリング操作の異値数が取得不可であれば、前記フィルタリング条件の選択率Ｓ＝１／指定値であり、
フィルタリング述語のタイプが範囲述語である場合、述語のフィールドの極値または異値数が取得不可であれば、前記フィルタリング条件の選択率Ｓ＝１／指定値であり、
フィルタリング述語のタイプが空判別述語である場合、述語フィールドの空値数が取得可能であるか否かを判断し、前記述語フィールドの空値数が取得不可であれば、前記フィルタリング条件の選択率Ｓ＝１／指定値であるように構成される、請求項１５に記載のデバイス。
【請求項１７】
前記確定装置は、
フィルタリング述語のタイプがｌｉｋｅである場合、前記フィルタリング条件の選択率Ｓ＝１／指定値であり、
フィルタリング述語のタイプがＡＮＤカスケード述語である場合、カスケード述語の選択率の積およびＡＮＤカスケード述語におけるフィルタリング率の最小値に基づいて前記フィルタリング条件の選択率を確定し、
フィルタリング述語のタイプがＯＲカスケード述語である場合、前記ＯＲカスケード述語に対応するカスケード述語の選択率に基づいて前記フィルタリング条件の選択率を確定するように構成される、請求項１４に記載のデバイス。
【請求項１８】
前記確定装置は、
結合された左テーブルおよび右テーブルの結合フィールドの異値数が取得不可であれば、結合フィールドの結合タイプに基づいて結合結果セットのレコード数を確定するように構成される、請求項１４に記載のデバイス。
【請求項１９】
前記確定装置は、
結合フィールドの結合タイプが主キー−外部キー形式の結合である場合、外部キーフィールドのレコード数および主キーフィールドのフィルタリング条件の選択率に基づいて結合結果セットのレコード数を確定し、
結合フィールドの結合タイプが内部結合である場合、結合された左テーブルのレコード数および右テーブルのレコード数のうちの最大値を結合結果セットのレコード数とし、
結合フィールドの結合タイプがクロス結合である場合、結合された左テーブルのレコード数と右テーブルのレコード数との積を結合結果セットのレコード数とし、
結合フィールドの結合タイプが左外部結合である場合、結合された左テーブルのレコード数を前記結合結果セットのレコード数とし、結合フィールドの結合タイプが右外部結合である場合、結合された右テーブルのレコード数を結合結果セットのレコード数とし、
結合フィールドの結合タイプが完全結合である場合、結合された左テーブルのレコード数および右テーブルのレコード数の累積を結合結果セットのレコード数とするように構成される、請求項１８に記載のデバイス。
【請求項２０】
前記確定装置は、
集計フィールドのセットに少なくとも１つの主キーが存在する場合、集計フィールドの集計率Ｒａｇｇ＝１であり、
集計フィールドに対応する集計関数が単純な集計関数である場合、集計フィールドの集
計率Ｒａｇｇは、
（式４）
【数４】
2021504852.tif 000044
であり、
（ただし、ｎは集計フィールドのセットにおける集計フィールドの個数である）
集計フィールドに対応する集計関数がＲｏｌｌｕｐである場合、集計フィールドの集計率Ｒａｇｇは、
（式５）
【数５】
2021504852.tif 000045
であり、
（ただし、ｎは集計フィールドのセットにおける集計フィールドの個数であり、ｋは正の整数である）
集計フィールドに対応する集計関数がＣｕｂｅである場合、集計フィールドの集計率Ｒａｇｇは、
（式６）
【数６】
2021504852.tif 000046
であるように構成される、
（ただし、ｎは集計フィールドのセットにおける集計フィールドの個数であり、ｋは正の整数である）
請求項１４に記載のデバイス。
【請求項２１】
元の実行計画を生成することと、
取得された統計情報が完備であるか否かを判断し、前記統計情報が完備であれば、前記統計情報の第１コスト推定モデルに基づいてコストを推定し、前記統計情報が不備であれば、第２コスト推定モデルに基づいてコストを推定することと、
前記第１コスト推定モデルにより推定されたコストまたは前記第２コスト推定モデルにより推定されたコストに基づき、前記元の実行計画を最適化し、最適な実行計画を生成することと、
を含む、コスト最適化装置。
【請求項２２】
前記第２コスト推定モデルは、
前記統計情報に依存する操作ツリーの操作タイプである第１操作タイプのコスト推定方式を確定することと、
前記コスト推定方式に基づいて前記第１操作タイプの第１コスト推定を確定することと、
前記第１コスト推定、および前記統計情報に依存しない操作ツリーの操作タイプである第２操作タイプに対応する第２コスト推定に基づき、前記操作ツリーの累積したコスト推
定を確定することと、
を含む、請求項２１に記載のコスト最適化装置。
【請求項２３】
プロセッサと、
コンピュータ実行可能指令を記憶するように構成されるメモリと、
を備える計算に基づくデバイスであって、
前記実行可能指令が実行されると、前記プロセッサは、
取得された統計情報が完備であるか否かを判断し、前記統計情報が不備であれば、前記統計情報に依存する操作ツリーの操作タイプである第１操作タイプのコスト推定方式を確定し、
前記コスト推定方式に基づいて前記第１操作タイプの第１コスト推定を確定し、
前記第１コスト推定、および前記統計情報に依存しない操作ツリーの操作タイプである第２操作タイプの第２コスト推定に基づき、前記操作ツリーの累積したコスト推定を確定する、計算に基づくデバイス。
【請求項２４】
請求項１〜１０のいずれか１項に記載の方法を実行するためのコンピュータ実行可能指令が記憶されている、コンピュータ可読記憶媒体。
【発明の詳細な説明】
【関連出願の相互参照】
【０００１】
本願は、２０１７年１１月２２日に中国専利局に出願された出願番号が２０１７１１１７５３４９．９である中国特許出願に対して、優先権の利益を主張するものであり、該出願の全ての内容を引用により本願に援用する。
【技術分野】
【０００２】
本願は、コンピュータ分野に関し、例えば、コスト最適化装置、コスト推定の方法およびそのデバイスに関する。
【背景技術】
【０００３】
コスト最適化装置（ＣＢＯ、Ｃｏｓｔ  Ｂａｓｅｄ  Ｏｐｔｉｍｉｚｅｒ）は、データベースシステムにおけるコア部材であり、データベースシステムの性能への影響が著しいため、現代データベースシステムにおいて重要な地位を占めている。コスト最適化装置のコアはコスト推定モデルであり、データベースシステムが生成した実行計画に対してコストを推定することにより、最適な実行計画を選択するために用いられる。推定モデルの良否は、最終的な実行計画の優劣に影響を及ぼす。コスト最適化装置は、ターゲットデータの統計情報に基づいて実行計画を最適化し、統計情報の完全性および精度は、推定モデルによる実行計画の推定に直接影響を及ぼす。
【０００４】
コスト最適化を行うには統計情報が必要となるため、完全かつ正確な統計情報を収集することは、全てのコスト最適化装置の不可欠な環節である。コスト最適化装置を最適化することは、最適な実行計画を生成するためである。データベースシステムにおいて、実行計画は、一般的に、操作ツリーで示され、操作ツリーは異なるタイプの操作により構成され、１本の操作ツリーに含まれる操作タイプは、テーブルスキャン、選択、フィルタリング、集計（ａｇｇｒｅｇａｔｅ）、結合、投影等であってもよい。統計情報に基づき、コスト最適化装置は、コスト推定モデルを介して実行計画の各操作に対してコストを推定し、全ての可能な実行計画からコスト全体が最も小さいものを最終的な実行計画として選択することにより、コスト最適化の全過程を完了することができる。これにより、コスト最適化装置のコアは統計情報に基づくコスト推定であり、統計情報がコスト最適化装置の基礎であることが分かる。
【０００５】
コスト最適化装置は統計情報を必要とし、必要な統計情報が不足している場合に、コスト最適化を完了ことができない。例えば、動作時に作成される一時テーブルまたはサブ検索が存在するシーンにおいて、コンパイル段階ではその統計情報が確定できないため、コスト最適化を完了することができない。一方、コスト最適化装置が大量データを処理するためにビッグデータシステムに使用されると、大量データの統計情報の収集コストが大きいため、該大量データの統計情報を収集することは、コスト最適化装置の適用のボトルネックとなる。所定のデータセットに対し、全量データの統計情報を収集する必要がなく、一部の統計情報に基づいて最適な計画を得る可能性もある。統計情報が不完全または取得不可である場合、関連技術におけるコスト最適化装置は無効になる。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本願は、統計情報が不備である場合にコスト推定を行うことができないという問題を解決できるコスト最適化装置、コスト推定の方法およびそのデバイスを提供する。
【課題を解決するための手段】
【０００７】
本願の一態様によれば、取得された統計情報が完備であるか否かを判断し、統計情報が不備であれば、第１操作タイプのコスト推定方式を確定することと、前記コスト推定方式に基づき、前記統計情報に依存する操作ツリーの操作タイプである前記第１操作タイプの第１コスト推定を確定することと、第１コスト推定、および前記統計情報に依存しない操作ツリーの操作タイプである第２操作タイプの第２コスト推定に基づき、前記操作ツリーの累積したコスト推定を確定することとを含むコスト推定の方法を提供する。
【０００８】
本願の別の態様によれば、判断装置と、確定装置と、推定装置とを備えるコスト推定のデバイスを更に提供する。
【０００９】
判断装置は、取得された統計情報が完備であるか否かを判断し、統計情報が不備であれば、前記統計情報に依存する操作ツリーの操作タイプに基づき、対応するコスト推定方式を確定するように構成される。
【００１０】
確定装置は、前記コスト推定方式に基づき、前記操作タイプに対応するコスト推定を確定するように構成される。
【００１１】
推定装置は、前記統計情報に依存する操作タイプに対応するコスト推定、および統計情報に依存しない操作タイプに対応するコスト推定に基づき、前記操作ツリーの累積したコスト推定を確定するように構成される。
【００１２】
本願の更なる態様によれば、元の実行計画を生成し、取得された統計情報が完備であるか否かを判断し、統計情報が完備であれば、統計情報の第１コスト推定モデルに基づいてコストを推定し、統計情報が不備であれば、第２コスト推定モデルに基づいてコストを推定し、前記第１コスト推定モデルにより推定されたコストまたは前記第２コスト推定モデルにより推定されたコストに基づき、最適な実行計画を生成するように構成されるコスト最適化装置を更に提供する。
【００１３】
本願の更なる態様によれば、プロセッサと、コンピュータ実行可能指令を記憶するように構成されるメモリとを備える計算に基づくデバイスであって、前記実行可能指令が実行されると、前記プロセッサは、取得された統計情報が完備であるか否かを判断し、統計情報が不備であれば、前記統計情報に依存する操作ツリーの操作タイプに基づき、対応するコスト推定方式を確定し、前記コスト推定方式に基づき、前記操作タイプに対応するコスト推定を確定し、前記統計情報に依存する操作タイプに対応するコスト推定、および統計情報に依存しない操作タイプに対応するコスト推定に基づき、前記操作ツリーの累積したコスト推定を確定する計算に基づくデバイスを更に提供する。
【００１４】
本願の更なる態様によれば、上記コスト推定の方法を実行するためのコンピュータ実行可能指令が記憶されているコンピュータ可読記憶媒体を更に提供する。
【発明の効果】
【００１５】
本願では、取得された統計情報が不備であると判断すれば、前記統計情報に依存する操作ツリーの操作タイプに基づいて対応するコスト推定方式を確定し、前記コスト推定方式に基づき、前記操作タイプに対応するコスト推定を確定し、前記統計情報に依存する操作タイプに対応するコスト推定および統計情報に依存しない操作タイプに対応するコスト推定に基づき、前記操作ツリーの累積したコスト推定を確定する。これにより、従来のコスト最適化装置が、動作時に作成される一時テーブルおよびサブ検索に対してコストを推定することができず、大量データのシーンに対してデータ規模に制限されるという問題を解決する。また、前記累積したコスト推定に基づいて構造化照会言語（Ｓｔｒｕｃｔｕｒｅｄ  Ｑｕｅｒｙ  Ｌａｎｇｕａｇｅ、ＳＱＬ）の語句に対応する実行計画を最適化するこ
とは、データベースシステムにおけるＳＱＬの最適化に適用でき、ＳＱＬのコスト最適化装置のコスト推定の正確性を向上させ、性能がより良好な実行計画を生成する。
【図面の簡単な説明】
【００１６】
【図１】本願の一態様によるコスト推定の方法のフローチャートを示す。
【図２】本願における一実施例の１本の操作ツリーの模式図を示す。
【図３】本願の別の態様によるコスト推定のデバイスの構造模式図を示す。
【図４】本願の更なる態様による改良されたコスト最適化装置の模式図を示す。
【００１７】
図面において、同じまたは類似する符号は、同じまたは類似する部材を表す。
【発明を実施するための形態】
【００１８】
本願の１つの実施例において、端末、サービスネットワークのデバイスおよび信頼できるパーティ（ｕｎｔｒｕｓｔｅｄ  ｐａｒｔｉｅｓ）は、いずれも１つまたは複数のプロセッサ（例えば、中央処理装置（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ、ＣＰＵ））、入力／出力インタフェース、ネットワークインタフェースおよびメモリを含む。
【００１９】
メモリは、コンピュータ可読記憶媒体における非永久的メモリ、ランダムアクセスメモリ（Ｒａｎｄｏｍ−Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ、ＲＡＭ）および／または不揮発性メモリ等の形式を含む可能性があり、例えば、読み出し専用メモリ（Ｒｅａｄ−Ｏｎｌｙ  Ｍｅｍｏｒｙ、ＲＯＭ）またはフラッシュメモリ（ｆｌａｓｈ  ＲＡＭ）を含む。メモリはコンピュータ可読記憶媒体の例である。
【００２０】
コンピュータ可読記憶媒体は、永久的および非永久的、リムーバブルおよび非リムーバブルを含み、任意の方法または技術により情報の記憶を実現することができる。情報は、コンピュータ可読指令、データ構造、プログラムのモジュールまたは他のデータであってもよい。コンピュータ記憶媒体の例は、相変化メモリ（Ｐｈａｓｅ  ＲＡＭ、ＰＲＡＭ）、スタティックランダムアクセスメモリ（Ｓｔａｔｉｃ  ＲＡＭ、ＳＲＡＭ）、ダイナミックランダムアクセスメモリ（Ｄｙｎａｍｉｃ  ＲＡＭ、ＤＲＡＭ）、他のタイプのランダムアクセスメモリ（ＲＡＭ）、読み出し専用メモリ（ＲＯＭ）、電気的に消去・記録が可能な読み出し専用メモリ（Ｅｌｅｃｔｒｉｃａｌｌｙ−Ｅｒａｓａｂｌｅ  Ｐｒｏｇｒａｍｍａｂｌｅ  ＲＯＭ、ＥＥＰＲＯＭ）、フラッシュメモリまたは他のメモリ技術、コンパクトディスク読み出し専用メモリ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ  ＲＯＭ、ＣＤ−ＲＯＭ）、デジタルバーサタイルディスク（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｃ、ＤＶＤ）または他の光学記憶装置、磁気テープカセット、磁気テープ・磁気ディスク記憶装置または他の磁気記憶デバイス、または任意の他の非伝送媒体を含んでもよいが、これらに限定されず、計算装置がアクセス可能な情報を記憶するために使用できる。本明細書における定義によれば、コンピュータ可読記憶媒体は、変調されたデータ信号およびキャリアのような非一時記憶コンピュータ可読媒体（ｔｒａｎｓｉｔｏｒｙ  ｍｅｄｉａ）を含まない。
【００２１】
図１は、本願の一態様によるコスト推定の方法のフローチャートを示し、前記方法はＳ１１〜Ｓ１３を含む。
【００２２】
Ｓ１１において、取得された統計情報が完備であるか否かを判断し、取得された統計情報が不備であれば、前記統計情報に依存する操作ツリーの操作タイプに基づき、対応するコスト推定方式を確定する。
【００２３】
１本の操作ツリーは、複数種の操作タイプを含んでもよく、例えば、統計情報に依存す
る操作タイプおよび統計情報に依存しない操作タイプを含む。本願において、統計情報に依存する操作ツリーの操作タイプを第１操作タイプと呼び、第１操作タイプのコスト推定を第１コスト推定と呼び、統計情報に依存しない操作ツリーの操作タイプを第２操作タイプと呼び、第２操作タイプのコスト推定を第２コスト推定と呼ぶ。
【００２４】
Ｓ１２において、前記コスト推定方式に基づいて第１操作タイプの第１コスト推定を確定する。
【００２５】
Ｓ１３において、前記統計情報に依存する操作タイプに対応するコスト推定（すなわち、第１操作タイプの第１コスト推定）、および統計情報に依存しない操作タイプに対応するコスト推定（すなわち、第２操作タイプの第２コスト推定）に基づき、前記操作ツリーの累積したコスト推定を確定する。
【００２６】
上記方法は、動作時に作成される一時テーブルおよびサブ検索に対してコストを推定することができないシーン、または大量データのシーンに対してデータ規模により制限され、従来のコスト最適化装置がコスト最適化を行うことができないという問題を解決できる。
【００２７】
１つの好ましい例において、本願に係る方法は、前記累積したコスト推定に基づいて構造化照会言語語句に対応する実行計画を最適化することを含む。本願に係るコスト推定の方法は、データベースシステムにおけるＳＱＬの最適化に適用され、ＳＱＬのコスト最適化装置のコスト推定の正確性を向上させることにより、性能がより良好な実行計画を生成する。
【００２８】
本願の一実施例において、不備な統計情報に基づいて実行計画に対してコストを最適化することができる。統計情報が完備である場合、関連技術におけるコスト推定モデルを用いて推定し、推定結果に基づいて最適な実行計画を生成し、統計情報が不備である場合、本願に係るコスト推定の方法により、応じる操作に対してコストを推定して推定結果を取得し、推定結果に基づいて最適な実行計画を生成する。
【００２９】
Ｓ１１において、取得された統計情報が完備であるか否かを判断し、統計情報が不備であれば、前記統計情報に依存する操作ツリーの操作タイプ（すなわち、第１操作タイプ）に基づき、対応するコスト推定方式を確定する。前記統計情報に依存する操作ツリーの操作タイプは、テーブルスキャン操作、フィルタリング操作、結合操作および集計操作を含んでもよい。ここで、１本の操作ツリーは異なる操作子により構成され、１種の操作子は１種の操作タイプを表し、該操作タイプは、テーブルスキャン、フィルタリング、結合、投影、集計、選択等を含んでもよい。図２に示す１本の操作ツリーの模式図のように、操作ツリーにおける操作タイプを調整し、各種の操作タイプのコストを推定し、最終的に累積コストが最も小さい１本の操作ツリーを生成し、実行計画を生成する。異なる操作タイプのコストの統計情報に対する依存が異なり、例えば、テーブルスキャン操作、フィルタリング操作、結合操作および集計操作のコストは統計情報に依存する必要があり、すなわち、テーブルスキャン操作、フィルタリング操作、結合操作および集計操作に対応する完全な統計情報が取得されただけで、テーブルスキャン操作、フィルタリング操作、結合操作および集計操作のコスト推定を確定することができる。一方、投影操作および選択操作のコストは統計情報に依存せず、すなわち、投影操作および選択操作に対応する完全な統計情報を取得しなくても、投影操作および選択操作のコスト推定を確定することができる。そのため、操作ツリーの操作タイプを確定し、操作タイプに対応するコスト推定方式を用いて各種の操作タイプのコスト推定を確定する必要がある。本願では、取得された統計情報が完備であるか否かを判断し、統計情報が不備であれば、統計情報に依存する操作タイプのコスト推定の方法を改良する。
【００３０】
Ｓ１２において、統計情報に依存する操作タイプのコスト推定方式を確定し、コスト推定方式に基づいて該統計情報に依存する操作タイプのコスト推定を確定する。
【００３１】
Ｓ１３において、前記統計情報に依存する操作タイプのコスト推定（すなわち、第１操作タイプの第１コスト推定）および統計情報に依存しない操作タイプに対応するコスト推定（第２操作タイプの第２コスト推定）に基づき、前記操作ツリーの累積したコスト推定を確定する。
【００３２】
例えば、統計情報に依存するテーブルスキャン操作、フィルタリング操作、結合操作および集計操作のコスト推定と、統計情報に依存しない投影操作および選択操作のコスト推定とを累積して操作ツリーのコスト推定を取得し、更に最適な実行計画を生成する。
【００３３】
本願の一実施例において、Ｓ１２で、データセットのレコード数に基づいてテーブルスキャン操作のコスト推定を確定し、フィルタリング述語のタイプに基づいてフィルタリング条件の選択率を確定し、前記選択率に基づいてフィルタリング操作のコスト推定を確定し、確定された結合結果セットのレコード数に基づいて結合操作のコスト推定を確定し、集計フィールドおよび集計関数に基づいて集計フィールドの集計率を確定し、前記集計率に基づいて集計操作のコスト推定を確定する。
【００３４】
テーブルスキャン操作のコストはデータセットのサイズ（データセットのレコード数ともいう）に関連し、データセットが大きいほど、テーブルスキャンコストは高いため、データセットのレコード数に基づいてテーブルスキャン操作のコスト推定を確定することができる。
【００３５】
フィルタリング操作のコストはフィルタリング条件の選択率に関連し、選択率は更にフィルタリング条件に応じて計算され、フィルタリング述語のタイプが異なる場合、フィルタリング条件の選択率の確定方式も異なる。
【００３６】
結合操作のコストは結合に関与するデータセットのサイズに関連し、結合後の結合結果セットのサイズにも関連し、そのため、結合結果セットのレコード数を確定してから、結合結果セットのレコード数に基づいて結合操作のコスト推定を確定する。
【００３７】
集計操作のコストは集計に関与するデータ量のサイズおよび集計フィールドの集計率に関連し、集計フィールドの集計率は、集計フィールドの異値数に基づいて計算する必要があるため、集計操作のコストを確定するとき、集計フィールドの異値数を計算する必要がある。
【００３８】
本願の一実施例において、データセットのレコード数をＲＣ（Ｒｏｗ  Ｃｏｕｎｔ）と記し、データセットのサイズ（Ａと記す）はＲＣと比例関係にあり、すなわち、Ａ∝ＲＣであり、そのため、本願実施例において、ＲＣを用いてデータセットのサイズを表すことができ、テーブルスキャン操作のコスト推定ｃｏｓｔは以下のとおりである。
（式７）
【数１】
2021504852.tif 000003
【００３９】
該式は、データセットのレコード数ＲＣに基づいてテーブルスキャン操作のコスト推定を確定することができることを示し、ただし、前記Ｏｐは、コストを推定しようとするターゲット操作を表し、ｇｅｔＯｒｉｇｉｎａｌＣｏｓｔは、関連技術の方法およびＲＣを
用いてコストを推定することを表す。
【００４０】
本願の一実施例において、フィルタリング操作で、フィルタリング操作のコスト推定はフィルタリング述語の選択率に関連し、異なるタイプのフィルタリング述語の選択率の推定アルゴリズムは異なる。フィルタリング述語のタイプに対応する、選択率を計算するオブジェクトが取得可能であるか否かを判断することにより、フィルタリング条件の選択率を確定することができる。フィルタリング述語のタイプに対応する、選択率を計算するオブジェクトが取得不可であれば、フィルタリング条件の選択率Ｓ＝１／指定値である。ここで、フィルタリング述語のタイプに対応する、選択率を計算するオブジェクトは、異値数、述語フィールドの極値および述語フィールドの空値数を含み、指定値は具体的な実際応用に応じて決定され、１よりも大きい正数であり、異なるフィルタリング述語のタイプにおいて、該指定値は同じであってもよく異なってもよく、例えば、Ｓ＝１／５、Ｓ＝１／９等である。
【００４１】
１つの好ましい例において、フィルタリング操作のコストはフィルタリング条件の選択率に関連し、フィルタリング条件の選択率は更にフィルタリング条件に応じて計算され、本願の実施例において、フィルタリング条件の選択率Ｓ＝結果セットのレコード総数／フィルタリング操作に関与するレコード総数であると定義する。フィルタリング述語のタイプに対応する、選択率を計算するオブジェクトが取得不可であれば、フィルタリング述語のタイプに基づいてフィルタリング条件の選択率を確定することは、以下のように検討される。
【００４２】
フィルタリング述語のタイプがイコール述語である場合、前記フィルタリング操作の異値数が取得可能であるか否かを判断し、フィルタリング操作の異値数が取得不可であれば、フィルタリング条件の選択率Ｓ＝１／指定値であり、ここで、イコール述語（Ｅｑｕａｌ、＝）の場合、異値数（ｎｕｍｂｅｒ  ｄｉｓｔｉｎｃｔ  ｖａｌｕｅ、ＮＤＶ）が取得可能であれば、フィルタリング条件の選択率Ｓ＝１／ＮＤＶであり、異値数が取得不可であれば、Ｓ（イコール述語）＝１／１０であり、ここで、Ｓ（イコール述語）＝１／１０は経験値により確定され、他の指定値であってもよい。
【００４３】
フィルタリング述語がノットイコール述語（Ｎｏｎ−Ｅｑｕａｌ、！＝）である場合、イコール述語とノットイコール述語とは一対の相補的述語であり、すなわち、イコール述語とノットイコール述語とのフィルタリング条件の選択率の和は１であり、そのため、ノットイコール述語の選択率は、Ｓ（ノットイコール述語）＝１−Ｓ（イコール述語）である。
【００４４】
フィルタリング述語のタイプが範囲述語である場合、ここで、範囲述語は、一辺区間範囲（例えば、＞、＜、＞＝、＜＝）、２値区間範囲（例えば、ｂｅｔｗｅｅｎ）、セット内にあるか否か（例えば、Ｉｎ）を含む。範囲述語のフィールドの極値または異値数が取得不可であれば、フィルタリング条件の選択率Ｓ＝１／指定値である。範囲述語が＞、＜、＞＝、＜＝である場合、フィルタリング条件の選択率は範囲述語フィールドの極値に基づいて確定され、極値が取得不可であれば、フィルタリング条件の選択率Ｓ＝１／３であると定義する。範囲述語がｂｅｔｗｅｅｎである場合、すなわち、フィルタリング条件が２値の間にあり、極値が取得不可であれば、フィルタリング条件の選択率Ｓ＝１／９であると定義する。範囲述語がＩｎである場合、Ｃ＝｛ｖ１，ｖ２，……，ｖｎ｝であり、すなわち、フィルタリング条件ｃｏｌ  ＩＮは以下のとおりである。
（式８）
ｃｏｌ  ＩＮ（ｖ１，ｖ２，……，ｖｎ），ｎ＝｜Ｃ｜
ただし、ｖ１、ｖ２、……、ｖｎはフィルタリング値であり、Ｃはフィルタリング値のセットであり、ｎはセットＣにおけるフィルタリング値の個数であり、フィルタリング時に
フィルタリング待ちのデータが該セットＣ内の値に属しているか否かを判断する。異値数が取得不可であれば、フィルタリング条件の選択率Ｓ＝１／５であると定義する。
【００４５】
フィルタリング述語のタイプが空判別述語である場合、空判別述語フィールドの空値数が取得可能であるか否かを判断し、空判別述語フィールドの空値数が取得不可であれば、前記フィルタリング条件の選択率Ｓ＝１／指定値であることを確定する。フィルタリング述語のタイプが空判別述語である場合、選択率は空判別述語フィールドの空値数に基づいて推定する必要があり、空値数が取得不可であれば、フィルタリング条件の選択率Ｓ＝１／１０であると定義する。フィルタリング述語のタイプが非空述語である場合、非空述語と空判別述語とは相補的述語であるため、フィルタリング条件の選択率Ｓ非空述語＝１−Ｓ空判別述語である。
【００４６】
フィルタリング述語のタイプは、以下のいくつかの場合を更に含む。フィルタリング述語のタイプがｌｉｋｅである場合、前記フィルタリング条件の選択率は、Ｓ＝１／指定値である。フィルタリング述語のタイプがｌｉｋｅである場合、選択率Ｓ＝１／５であると定義する。フィルタリング述語のタイプがＡＮＤカスケード述語である場合、カスケード述語の選択率の積およびＡＮＤカスケード述語におけるフィルタリング率の最小値に基づいてフィルタリング条件の選択率を確定する。
【００４７】
Ａｎｄカスケードのフィルタリング述語の場合、ＡＮＤカスケードのフィルタリング述語を
（式９）
【数２】
2021504852.tif 000004
と記し、推定誤差がカスケードにより増幅されることを防止するために、本願の実施例において以下の方式によりフィルタリング条件の選択率を推定する。
（式１０）
【数３】
2021504852.tif 000005
ただし、αはＡｎｄカスケードのフィルタリング述語のフィルタリング率の最小値を定義し、実際の場合に応じてαの値を調整することができ、ｓｅｌｅｃｔｉｖｉｔｙは選択率であり、上記式は、Ａｎｄカスケードのフィルタリング述語のカスケードの選択率値とＡｎｄカスケードのフィルタリング述語のフィルタリング率の最小値とのうちの最大値を、該フィルタリング条件の選択率とすることを示す。
【００４８】
フィルタリング述語のタイプがＯＲカスケード述語である場合、前記ＯＲカスケード述語に対応するカスケード述語の選択率に基づいてフィルタリング条件の選択率を確定する。ここで、ＯＲカスケードのフィルタリング述語を以下のように記す。
（式１１）
【数４】
2021504852.tif 000006
【００４９】
フィルタリング条件の選択率を以下の方式に従って確定する。
（式１２）
【数５】
2021504852.tif 000007
【００５０】
異なるタイプのフィルタリング述語に対してその対応するフィルタリング条件の選択率を検討し、確定された選択率に基づいてフィルタリング操作のコストを計算することができる。
（式１３）
【数６】
2021504852.tif 000008
【００５１】
なお、当業者であれば、上記実施例に現れたＳ＝１／指定値における数値は例に過ぎず、且つ、上記実施例における各種のフィルタリング述語に対応するフィルタリング条件の選択率は、実際の場合に応じて調整されてもよく、パラメータ伝達等の方式により動的に変更されてもよいことが理解できるべきである。
【００５２】
本願の一実施例において、確定された結合結果セットのレコード数に基づいて結合操作のコスト推定を確定する前に、結合された左テーブルおよび右テーブルの結合フィールドの異値数に基づいて結合結果セットのレコード数を確定する。ここで、結合に関与する左テーブルをＴｌｅｆｔと記し、そのレコード数がＲＣｌｅｆｔであり、異値数がＮＤＶｌｅｆｔであり、結合に関与する右テーブルをＴｒｉｇｈｔと記し、そのレコード数がＲＣｒｉｇｈｔであり、異値数がＮＤＶｒｉｇｈｔであり、結果セットのレコード数をＲＣｒｅｓｕｌｔと記す。結合に関与する左、右テーブルは、いずれも選択操作、フィルタリング操作、テーブルスキャン操作等の操作により構成され、左テーブルおよび右テーブルは、それぞれ左側操作ツリーおよび右側操作ツリーを構成し、操作ツリーにおける各種の操作タイプのコスト推定はいずれも推定され得るため、結合に関与する左テーブルおよび右テーブルのデータセットのサイズ（すなわち、ＲＣｌｅｆｔおよびＲＣｒｉｇｈｔ）は、左テーブルおよび右テーブルに含まれる操作タイプに対する推定および既存の計算方法により計算され得る。
【００５３】
本願の一実施例において、結合された左テーブルおよび右テーブルの結合フィールドの異値数が取得不可であれば、結合フィールドの結合タイプに基づいて結合結果セットのレコード数を確定する。以下、どのように結合フィールドの結合タイプに基づいて結合結果セットのレコード数を確定するかについて検討する。
【００５４】
左テーブルおよび右テーブルの結合フィールドの結合タイプが主キー（ＰＫ）−外部キー（ＦＫ）形式の結合である場合、外部キーフィールドのレコード数および主キーフィールドのフィルタリング条件の選択率に基づいて結合結果セットのレコード数を確定する。ここでの左テーブルおよび右テーブルの結合フィールドの結合タイプが主キー−外部キー形式の結合であることとは、左テーブルの結合フィールドの結合タイプが主キー形式の結合であり、右テーブルの結合フィールドの結合タイプが外部キー形式の結合であることを指してもよく、左テーブルの結合フィールドの結合タイプが外部キー形式の結合であり、右テーブルの結合フィールドの結合タイプが主キー形式の結合であることを指してもよい。
【００５５】
左テーブルの結合フィールドの結合タイプが主キー形式の結合であり、右テーブルの結合フィールドの結合タイプが外部キー形式の結合であれば、結合結果セットのレコード数
ＲＣｒｅｓｕｌｔは以下のとおりである。
（式１４）
【数７】
2021504852.tif 000009
ただし、ＲＣｆｋはＲＣｌｅｆｔおよびＲＣｒｉｇｈｔの１つであり、外部キーフィールドレコード数を表し、ｓｅｌｅｃｔｉｖｉｔｙ（ＰＫ）は主キーフィールドのフィルタリング条件の選択率を表す。主キーフィールドにフィルタリング条件が存在すれば、最終的な結合の結果も該フィルタリング条件に影響されるため、結合結果セットのレコード数を計算するとき、外部キーフィールドのレコード数に主キーフィールドのフィルタリング条件の選択率を乗算する必要がある。主キーフィールドにフィルタリング条件が存在しない場合、主キーフィールドのフィルタリング条件の選択率ｓｅｌｅｃｔｉｖｉｔｙ（ＰＫ）＝１である。
【００５６】
左テーブルおよび右テーブルの結合フィールドの結合タイプが非主キー−外部キーの結合である場合、更に以下の場合１〜場合４に分けることができる。
【００５７】
場合１：左テーブルおよび右テーブルの結合フィールドの結合タイプが内部結合である場合、結合された左テーブルのレコード数および右テーブルのレコード数のうちの最大値を結合結果セットのレコード数とし、ここで、本願の一実施例において、結合結果のレコード数を左テーブルの結合レコード数および右テーブルの結合レコード数の最大値として推定し、すなわち、
（式１５）
【数８】
2021504852.tif 000010
である。すなわち、結果レコード数は、ＲＣｌｅｆｔおよびＲＣｒｉｇｈｔのうちの最大値である。
【００５８】
場合２：左テーブルおよび右テーブルの結合フィールドの結合タイプがクロス結合である場合、結合された左テーブルのレコード数と右テーブルのレコード数との積を結合結果セットのレコード数とし、クロス結合の場合、その結合結果セットのレコード数は結合レコード数の積であり、すなわち、
（式１６）
【数９】
2021504852.tif 000011
である。
【００５９】
場合３：左テーブルの結合フィールドの結合タイプが左外部結合、または右テーブルの結合フィールドの結合タイプが右外部結合である場合、対応する結合された左テーブルのレコード数または右テーブルのレコード数を結合結果セットのレコード数とする。結合フィールドの結合タイプが左外部結合である場合、結合結果セットのレコード数がＴｌｅｆｔのレコード数Ｒｌｅｆｔであり、すなわち、
（式１７）
【数１０】
2021504852.tif 000012
である。結合フィールドの結合タイプが右外部結合である場合、結合結果セットのレコード数はＴｒｉｇｈｔのレコード数Ｒｒｉｇｈｔであり、すなわち、
（式１８）
【数１１】
2021504852.tif 000013
である。
【００６０】
場合４：左テーブルおよび右テーブルの結合フィールドの結合タイプが完全結合である場合、結合された左テーブルのレコード数および右テーブルのレコード数の累積を結合結果セットのレコード数とする。ここで、結合フィールドの結合タイプが完全外部結合である場合、結合結果セットのレコード数はＴｌｅｆｔとＴｒｉｇｈｔのレコード数の和であり、すなわち、
（式１９）
【数１２】
2021504852.tif 000014
である。
【００６１】
最終的には、結合操作のコスト推定は以下のとおりである。
（式２０）
【数１３】
2021504852.tif 000015
【００６２】
本願の一実施例において、集計操作の過程については、集計操作のコスト推定は集計に関与するデータ量のサイズおよび集計フィールドの集計率に関連し、集計率Ｒａｇｇを以下のように定義することができる。
（式２１）
【数１４】
2021504852.tif 000016
【００６３】
集計フィールドの集計率は、集計フィールドの異値数により計算する必要があり、集計フィールドの異値数が取得不可である場合、以下のように検討される。
【００６４】
集計フィールドのセットＣを
（式２２）
【数１５】
2021504852.tif 000017
と記し、ただし、ｃ１、ｃ２およびｃｎは集計フィールドであり、ｎは集計フィールドの
セットにおける集計フィールドの個数である。
【００６５】
集計フィールドのセットＣに少なくとも１つの主キーが存在する場合、集計フィールドの集計率Ｒａｇｇは１であり、すなわち、
【数１６】
2021504852.tif 000018
である。
【００６６】
集計フィールドに対応する集計関数が単純な集計関数Ｇｒｏｕｐ  Ｂｙである場合、集計フィールドの集計率Ｒａｇｇは以下のような区分関数である。
（式２３）
【数１７】
2021504852.tif 000019
ただし、ｎは集計フィールドのセットにおける集計フィールドの個数である。
【００６７】
集計フィールドに対応する集計関数がＲｏｌｌｕｐである場合、集計フィールドの集計率Ｒａｇｇは以下のとおりである。
（式２４）
【数１８】
2021504852.tif 000020
ただし、ｎは集計フィールドのセットにおける集計フィールドの個数であり、ｋは正の整数である。
【００６８】
集計フィールドに対応する集計関数がＣｕｂｅである場合、集計フィールドの集計率Ｒａｇｇは以下のとおりである。
（式２５）
【数１９】
2021504852.tif 000021
ただし、ｎは集計フィールドのセットにおける集計フィールドの個数であり、ｋは正の整数である。
【００６９】
以上をまとめ、統計情報が正確ではないまたは完全ではない場合、本願に係る実施例におけるコスト推定の方法により操作ツリーのコスト推定を行うことができ、本願に係るコスト推定の方法は、動作時に作成される一時テーブルおよびサブ検索、並びに大量データのシーンに適用できる。データ規模に制限されずにコスト推定を迅速に行うことができる。一方、本願に係るコスト推定の方法に基づいて関連技術におけるコスト最適化装置を改良し、不備な統計情報に基づいて実行計画に対してコストを最適化することができる。統計情報が完備である場合、関連技術におけるコスト推定モデルは、応じる操作のコストを
推定し、推定結果に基づいて最適な実行計画を生成することができる。統計情報が不備である場合、関連技術におけるコスト最適化装置は応じる操作に対してコストを推定することができないと、本願に係るコスト推定モデル（すなわち、操作ツリーの関連操作のコスト推定の方法を改良したもの）を用いて応じる操作に対してコストを推定し、推定結果に基づいて最適な実行計画を生成することができる。
【００７０】
図３は、本願の別の態様によるコスト推定のデバイスの構造模式図を示し、前記デバイスは、判断装置１１と、確定装置１２と、推定装置１３とを備える。
【００７１】
判断装置１１は、取得された統計情報が完備であるか否かを判断し、統計情報が不備であれば、前記統計情報に依存する操作ツリーの操作タイプに基づき、対応するコスト推定を確定するように構成される。
【００７２】
確定装置１２は、前記コスト推定方式に基づいて前記操作タイプに対応するコスト推定を確定するように構成される。
【００７３】
推定装置１３は、前記統計情報に依存する操作タイプに対応するコスト推定し、および統計情報に依存しない操作タイプに対応するコスト推定に基づき、前記操作ツリーの累積したコスト推定を確定するように構成される。
【００７４】
上記装置を用い、関連技術におけるコスト最適化装置が動作時に作成される一時テーブルおよびサブ検索に対してコストを推定することができず、大量データのシーンに対してデータ規模により制限されるという問題を解決することができる。
【００７５】
１つの好ましい例において、前記デバイスは、前記累積したコスト推定に基づいて構造化照会言語の語句に対応する実行計画を最適化するように構成される実行装置を更に備える。本願に係るコスト推定の方法は、データベースシステムにおけるＳＱＬの最適化に適用され、ＳＱＬのコスト最適化装置のコスト推定の正確性を向上させることにより、性能がより良好な実行計画を生成する。
【００７６】
本願の一実施例において、本願のコスト最適化装置を用い、不備な統計情報に基づいて実行計画に対してコストを最適化することができる。統計情報が完備である場合、関連技術におけるコスト推定モデルを用いて推定し、推定結果に基づいて最適な実行計画を生成し、統計情報が不備である場合、本願に係るコスト推定の方法により、応じる操作に対してコストを推定し、推定結果に基づいて最適な実行計画を生成する。
【００７７】
判断装置１１は、取得された統計情報が不備であると判断すると、前記統計情報に依存する操作ツリーの操作タイプに基づき、対応するコスト推定方式を確定するように構成される。前記統計情報に依存する操作ツリーの操作タイプは、テーブルスキャン操作、フィルタリング操作、結合操作および集計操作を含む。ここで、１本の操作ツリーは異なる操作子により構成され、各種の操作子は1種の操作タイプを表し、１本の操作ツリーの操作
タイプは、テーブルスキャン、フィルタリング、結合、投影、集計、選択等の操作を含んでもよい。図２に示す１本の操作ツリーの模式図のように、操作ツリーにおける操作タイプを調整し、各種の操作タイプのコストを推定し、最終的に累積コストが最も小さい１本の操作ツリーを生成し、実行計画を生成し、異なる操作タイプのコストの統計情報に対する依存が異なる。例えば、テーブルスキャン操作、フィルタリング操作、結合操作、集計操作のコスト推定は統計情報に依存する必要がある一方、投影操作、選択操作のコスト推定は統計情報に依存しない。そのため、操作タイプを確定し、対応するコスト推定方式を用いて各種の操作タイプのコスト推定を行う必要がある。取得された統計情報が不備であると判断すると、統計情報に依存する操作タイプのコスト推定の方法を改良する。
【００７８】
確定装置１２は、統計情報に依存する操作タイプのコスト推定方式を確定し、更に操作タイプのコスト推定を確定するように構成される。
【００７９】
推定装置１３は、前記統計情報に依存する操作タイプに対応するコスト推定、および統計情報に依存しない操作タイプに対応するコスト推定に基づき、前記操作ツリーの累積したコスト推定を確定するように構成される。例えば、統計情報に依存するテーブルスキャン操作、フィルタリング操作、結合操作および集計操作のコスト推定と、統計情報に依存しない投影操作および選択操作のコスト推定を累積して操作ツリーのコスト推定を取得し、更に最適な実行計画を生成する。
【００８０】
本願の一実施例において、確定装置１２は、データセットのレコード数に基づいてテーブルスキャン操作のコスト推定を確定し、フィルタリング述語のタイプに基づいてフィルタリング条件の選択率を確定し、前記選択率に基づいてフィルタリング操作のコスト推定を確定し、確定された結合結果セットのレコード数に基づいて結合操作のコスト推定を確定し、集計フィールドおよび集計関数に基づいて集計フィールドの集計率を確定し、前記集計率に基づいて集計操作のコスト推定を確定するように構成される。
【００８１】
ここで、テーブルスキャン操作のコストはデータセットのサイズ（データセットのレコード数ともいう）に関連し、データセットが大きいほど、そのテーブルスキャンコストは高いため、データセットのレコード数に基づいてテーブルスキャン操作のコスト推定を確定することができる。
【００８２】
フィルタリング操作のコストはフィルタリング条件の選択率に関連し、選択率は更にフィルタリング条件に応じて計算され、フィルタリング述語のタイプが異なる場合、選択率の確定方式も異なる。
【００８３】
結合操作のコストは結合に関与するデータセットのサイズに関連し、結合後の結果セットのサイズにも関連し、そのため、結合結果セットのレコード数を確定してから、結合結果セットのレコード数に基づいて結合操作のコスト推定を確定する。
【００８４】
集計操作のコストは集計に関与するデータ量のサイズおよび集計フィールドの集計率に関連し、集計フィールドの集計率は、集計フィールドの異値数に基づいて計算する必要があるため、集計フィールドの異値数を計算する必要がある。
【００８５】
本願の一実施例において、データセットのレコード数をＲＣ（Ｒｏｗ  Ｃｏｕｎｔ）と記し、データセットのサイズ（Ａと記す）はＲＣと比例関係にあり、すなわち、Ａ∝ＲＣであり、そのため、本願の実施例において、ＲＣを用いてデータセットのサイズを表すことができ、テーブルスキャン操作のコスト推定ｃｏｓｔは以下のとおりである。
（式２６）
【数２０】
2021504852.tif 000022
【００８６】
該式は、データセットのレコード数ＲＣに基づいてテーブルスキャン操作のコスト推定を確定することができることを示し、ただし、前記Ｏｐは、コストを推定しようとするターゲット操作を表し、ｇｅｔＯｒｉｇｉｎａｌＣｏｓｔは、関連技術の方法およびＲＣを用いてコストを推定することを表す。
【００８７】
本願の一実施例において、フィルタリング操作で、フィルタリング操作のコスト推定は
フィルタリング述語の選択率に関連し、異なるタイプのフィルタリング述語の選択率の推定アルゴリズムは異なる。フィルタリング述語のタイプに対応する、選択率を計算するオブジェクトが取得可能であるか否かを判断することにより、フィルタリング条件の選択率を確定することができる。フィルタリング述語のタイプに対応する、選択率を計算するオブジェクトが取得不可であれば、フィルタリング条件の選択率Ｓ＝１／指定値である。ここで、フィルタリング述語のタイプに対応する、選択率を計算するオブジェクトは、異値数、述語フィールドの極値および述語フィールドの空値数を含み、指定値は具体的な実際応用に応じて決定され、１よりも大きい正数であり、異なるフィルタリング述語のタイプにおいて、該指定値は同じであってもよく異なってもよく、例えば、Ｓ＝１／５、Ｓ＝１／９等である。
【００８８】
１つの好ましい例において、フィルタリング操作のコストはフィルタリング条件の選択率に関連し、フィルタリング条件の選択率は更にフィルタリング条件に応じて計算され、本願の実施例において、フィルタリング条件の選択率Ｓ＝結果セットのレコード総数／フィルタリング操作に関与するレコード総数であると定義する。フィルタリング述語のタイプに対応する、選択率を計算するオブジェクトが取得不可であれば、フィルタリング述語のタイプに基づいてフィルタリング条件の選択率を確定することは、以下のように検討される。
【００８９】
フィルタリング述語のタイプがイコール述語である場合、前記フィルタリング操作の異値数が取得可能であるか否かを判断し、フィルタリング操作の異値数が取得不可であれば、フィルタリング条件の選択率Ｓ＝１／指定値であり、ここで、イコール述語（Ｅｑｕａｌ、＝）の場合、異値数（ＮＤＶ）が取得可能であれば、フィルタリング条件の選択率Ｓ＝１／ＮＤＶであり、異値数が取得不可であれば、Ｓ（イコール述語）＝１／１０であり、ここで、Ｓ（イコール述語）＝１／１０は経験値により確定され、他の指定値であってもよい。
【００９０】
フィルタリング述語がノットイコール述語（Ｎｏｎ−Ｅｑｕａｌ、！＝）である場合、イコール述語とノットイコール述語とは一対の相補的述語であり、すなわち、イコール述語とノットイコール述語とのフィルタリング条件の選択率の和は１であるべきであり、そのため、ノットイコール述語の選択率は、Ｓ（ノットイコール述語）＝１−Ｓ（イコール述語）である。
【００９１】
フィルタリング述語のタイプが範囲述語である場合、ここで、範囲述語は、一辺区間範囲（例えば、＞、＜、＞＝、＜＝）、２値区間範囲（例えば、ｂｅｔｗｅｅｎ）、セット内にあるか否か（例えば、Ｉｎ）を含む。範囲述語のフィールドの極値または異値数が取得不可であれば、フィルタリング条件の選択率Ｓ＝１／指定値である。範囲述語が＞、＜、＞＝、＜＝である場合、フィルタリング条件の選択率は範囲述語フィールドの極値に基づいて確定され、極値が取得不可であれば、フィルタリング条件の選択率Ｓ＝１／３であると定義する。範囲述語がｂｅｔｗｅｅｎである場合、すなわち、フィルタリング条件が２値の間にあり、極値が取得不可であれば、フィルタリング条件の選択率Ｓ＝１／９であると定義する。範囲述語がＩｎである場合、Ｃ＝｛ｖ１，ｖ２，……，ｖｎ｝であり、すなわち、フィルタリング条件ｃｏｌ  ＩＮは以下のとおりである。
（式２７）
ｃｏｌ  ＩＮ（ｖ１，ｖ２，……，ｖｎ），ｎ＝｜Ｃ｜
ただし、ｖ１、ｖ２、……、ｖｎはフィルタリング値であり、Ｃはフィルタリング値のセットであり、ｎはセットＣにおけるフィルタリング値の個数であり、フィルタリング時にフィルタリング待ちのデータが該セットＣ内の値に属しているか否かを判断する。異値数が取得不可であれば、フィルタリング条件の選択率Ｓ＝１／５であると定義する。
【００９２】
フィルタリング述語のタイプが空判別述語である場合、空判別述語フィールドの空値数が取得可能であるか否かを判断し、空判別述語フィールドの空値数が取得不可であれば、前記フィルタリング条件の選択率Ｓ＝１／指定値であることを確定する。フィルタリング述語のタイプが空判別述語である場合、選択率は空判別述語フィールドの空値数に基づいて推定する必要があり、空値数が取得不可であれば、フィルタリング条件の選択率Ｓ＝１／１０であると定義する。フィルタリング述語のタイプが非空述語である場合、非空述語と空判別述語とは相補的述語であるため、フィルタリング条件の選択率Ｓ非空述語＝１−Ｓ空判別述語である。
【００９３】
フィルタリング述語のタイプは、以下のいくつかの場合を更に含む。フィルタリング述語のタイプがｌｉｋｅである場合、前記フィルタリング条件の選択率は、Ｓ＝１／指定値である。フィルタリング述語のタイプがｌｉｋｅである場合、選択率Ｓ＝１／５であると定義する。フィルタリング述語のタイプがＡＮＤカスケード述語である場合、カスケード述語の選択率の積およびＡＮＤカスケード述語におけるフィルタリング率の最小値に基づいてフィルタリング条件の選択率を確定する。
【００９４】
Ａｎｄカスケードのフィルタリング述語の場合、ＡＮＤカスケードのフィルタリング述語を
（式２８）
【数２１】
2021504852.tif 000023
と記し、推定誤差がカスケードにより増幅されることを防止するために、本願の実施例において以下の方式によりフィルタリング条件の選択率を推定する。
（式２９）
【数２２】
2021504852.tif 000024
ただし、αはＡｎｄカスケードのフィルタリング述語のフィルタリング率の最小値を定義し、実際の場合に応じてαの値を調整することができ、ｓｅｌｅｃｔｉｖｉｔｙは選択率であり、上記式は、Ａｎｄカスケードのフィルタリング述語のカスケードの選択率値とＡｎｄカスケードのフィルタリング述語のフィルタリング率の最小値とのうちの最大値を、該フィルタリング条件の選択率とすることを示す。
【００９５】
フィルタリング述語のタイプがＯＲカスケード述語である場合、前記ＯＲカスケード述語に対応するカスケード述語の選択率に基づいてフィルタリング条件の選択率を確定する。ここで、ＯＲカスケードのフィルタリング述語を以下のように記す。
（式３０）
【数２３】
2021504852.tif 000025
【００９６】
フィルタリング条件の選択率を以下の方式に従って確定する。
（式３１）
【数２４】
2021504852.tif 000026
【００９７】
異なるタイプのフィルタリング述語に対してその対応するフィルタリング条件の選択率を検討し、確定された選択率に基づいてフィルタリング操作のコストを計算することができる。
（式３２）
【数２５】
2021504852.tif 000027
【００９８】
なお、当業者であれば、上記実施例に現れたＳ＝１／指定値における数値は例に過ぎず、且つ、上記実施例における各種のフィルタリング述語のフィルタリング条件の選択率は、実際の場合に応じて調整されてもよく、パラメータ伝達等の方式により動的に変更されてもよいことが理解できるべきである。
【００９９】
本願の一実施例において、確定された結合結果セットのレコード数に基づいて結合操作のコスト推定を確定する前に、結合された左テーブルおよび右テーブルの結合フィールドの異値数に基づいて結合結果セットのレコード数を確定する。ここで、結合に関与する左テーブルをＴｌｅｆｔと記し、そのレコード数がＲＣｌｅｆｔであり、異値数がＮＤＶｌｅｆｔであり、結合に関与する右テーブルをＴｒｉｇｈｔと記し、そのレコード数がＲＣｒｉｇｈｔであり、異値数がＮＤＶｒｉｇｈｔであり、結果セットのレコード数をＲＣｒｅｓｕｌｔと記す。結合に関与する左、右テーブルは、いずれも選択操作、フィルタリング操作、テーブルスキャン操作等の操作を有し、左テーブルおよび右テーブルは、それぞれ左側操作ツリーおよび右側操作ツリーを構成し、操作ツリーにおける各種の操作タイプのコスト推定はいずれも推定され得るため、結合に関与する左テーブルおよび右テーブルのデータセットのサイズ（すなわち、ＲＣｌｅｆｔおよびＲＣｒｉｇｈｔ）は、左テーブルおよび右テーブルの操作タイプに対する推定および既存の計算方法により計算され得る。
【０１００】
本願の一実施例において、結合された左テーブルおよび右テーブルの結合フィールドの異値数が取得不可であれば、結合フィールドの結合タイプに基づいて結合結果セットのレコード数を確定する。以下、どのように結合フィールドの結合タイプに基づいて結合結果セットのレコード数を確定するかについて検討する。
【０１０１】
結合フィールドの結合タイプが主キー−外部キー形式の結合である場合、外部キーフィールドのレコード数および主キーフィールドのフィルタリング条件の選択率に基づいて結合結果セットのレコード数を確定する。左テーブルの結合フィールドの結合タイプおよび右テーブルの結合フィールドの結合タイプがそれぞれ主キー−外部キー形式の結合であれば、結合結果セットのレコード数ＲＣｒｅｓｕｌｔは以下のとおりである。
（式３３）
【数２６】
2021504852.tif 000028
ただし、ＲＣｆｋはＲＣｌｅｆｔおよびＲＣｒｉｇｈｔの１つであり、外部キーフィールドレコード数を表し、ｓｅｌｅｃｔｉｖｉｔｙ（ＰＫ）は主キーフィールドのフィルタリング条件の選択率を表す。主キーフィールドにフィルタリング条件が存在すれば、最終
的な結合の結果も該フィルタリング条件に影響されるため、結合結果セットのレコード数を計算するとき、外部キーフィールドのレコード数に主キーフィールドのフィルタリング条件の選択率を乗算する必要があり、主キーフィールドにフィルタリング条件が存在しない場合、主キーフィールドのフィルタリング条件の選択率ｓｅｌｅｃｔｉｖｉｔｙ（ＰＫ）＝１である。
【０１０２】
結合フィールドの結合タイプが非主キー−外部キー結合である場合、更に以下の場合１〜場合４に分けることができる。
【０１０３】
場合１：結合フィールドの結合タイプが内部結合である場合、結合された左テーブルのレコード数および右テーブルのレコード数のうちの最大値を結合結果セットのレコード数とし、ここで、本願の一実施例において、結合結果のレコード数を左テーブルの結合レコード数および右テーブルの結合レコード数の最大値として推定し、すなわち、
（式３４）
【数２７】
2021504852.tif 000029
である。すなわち、結果レコード数は、ＲＣｌｅｆｔおよびＲＣｒｉｇｈｔのうちの最大値である。
【０１０４】
場合２：結合フィールドの結合タイプがクロス結合である場合、結合された左テーブルのレコード数と右テーブルのレコード数との積を結合結果セットのレコード数とし、クロス結合の場合、その結合結果のレコード数は結合レコード数の積であり、すなわち、
（式３５）
【数２８】
2021504852.tif 000030
である。
【０１０５】
場合３：結合フィールドの結合タイプが左外部結合または右外部結合である場合、対応する結合された左テーブルのレコード数または右テーブルのレコード数を結合結果セットのレコード数とする。結合フィールドの結合タイプが左外部結合である場合、結合結果セットのレコード数がＴｌｅｆｔのレコード数Ｒｌｅｆｔであり、すなわち、
（式３６）
【数２９】
2021504852.tif 000031
である。結合フィールドの結合タイプが右外部結合である場合、結合結果セットのレコード数はＴｒｉｇｈｔのレコード数Ｒｒｉｇｈｔであり、すなわち、
（式３７）
【数３０】
2021504852.tif 000032
である。
【０１０６】
場合４：結合フィールドの結合タイプが完全結合である場合、結合された左テーブルの
レコード数および右テーブルのレコード数の累積を結合結果セットのレコード数とする。ここで、結合フィールドの結合タイプが完全外部結合である場合、結合結果セットのレコード数はＴｌｅｆｔとＴｒｉｇｈｔのレコード数の和であり、すなわち、
（式３８）
【数３１】
2021504852.tif 000033
である。
【０１０７】
最終的には、結合操作のコスト推定は以下のとおりである。
（式３９）
【数３２】
2021504852.tif 000034
【０１０８】
本願の一実施例において、集計操作の過程については、集計操作のコスト推定は集計に関与するデータ量のサイズおよび集計フィールドの集計率に関連し、集計率Ｒａｇｇを以下のように定義することができる。
（式４０）
【数３３】
2021504852.tif 000035
【０１０９】
集計フィールドの集計率は、集計フィールドの異値数により計算する必要があり、集計フィールドの異値数が取得不可である場合、以下のように検討される。
【０１１０】
集計フィールドのセットＣを
（式４１）
【数３４】
2021504852.tif 000036
と記し、ただし、ｃ１、ｃ２およびｃｎは集計フィールドであり、ｎは集計フィールドのセットにおける集計フィールドの個数である。
【０１１１】
集計フィールドのセットＣに少なくとも１つの主キーが存在する場合、集計フィールドの集計率Ｒａｇｇは１であり、すなわち、
【数３５】
2021504852.tif 000037
である。
【０１１２】
集計フィールドに対応する集計関数が単純な集計関数Ｇｒｏｕｐ  Ｂｙである場合、集計フィールドの集計率Ｒａｇｇは以下のような区分関数である。
（式４２）
【数３６】
2021504852.tif 000038
ただし、ｎは集計フィールドのセットにおける集計フィールドの個数である。
【０１１３】
集計フィールドに対応する集計関数がＲｏｌｌｕｐである場合、集計フィールドの集計率Ｒａｇｇは以下のとおりである。
（式４３）
【数３７】
2021504852.tif 000039
ただし、ｎは集計フィールドのセットにおける集計フィールドの個数であり、ｋは正の整数である。
【０１１４】
集計フィールドに対応する集計関数がＣｕｂｅである場合、集計フィールドの集計率Ｒａｇｇは以下のとおりである。
（式４４）
【数３８】
2021504852.tif 000040
ただし、ｎは集計フィールドのセットにおける集計フィールドの個数であり、ｋは正の整数である。
【０１１５】
本願の更なる態様によれば、元の実行計画を生成し、取得された統計情報が完備であるか否かを判断し、統計情報が完備であれば、統計情報に基づく第１コスト推定モデル（すなわち、関連技術におけるコスト推定モデル）によりコストを推定し、統計情報が不備であれば、第１コスト推定モデルに基づいて最適化された第２コスト推定モデル（すなわち、本願におけるコスト推定モデル）によりコストを推定し、前記第１コスト推定モデルにより推定されたコストまたは前記第２コスト推定モデルにより推定されたコストに基づき、最適な実行計画を生成するように構成されるコスト最適化装置を更に提供する。
【０１１６】
本願の一実施例において、図４に示すコスト最適化装置のように、不備な統計情報に基づいて実行計画に対してコストを最適化することができる。完備な統計情報が存在する場合、第１コスト推定モデルを用いてコストを推定し、ここで、第１コスト推定モデルは関連技術におけるコスト推定モデルであり、関連技術におけるコスト推定モデルがコスト最適化を行うとき、統計情報を必要とするため、完全かつ正確な統計情報を収集する必要がある。データベースシステムにおいて、実行計画は、一般的に、操作ツリーで示され、操作ツリーは異なる操作タイプにより構成され、該操作は、テーブルスキャン、選択、フィルタリング、集計、結合、投影等を含んでもよい。完全な統計情報が存在する場合、該統計情報に基づき、コスト最適化装置は、コスト推定モデルを介して実行計画の各種の操作タイプに対してコストを推定し、全ての可能な実行計画からコスト全体が最も小さいものを最終的な実行計画として選択することにより、コスト最適化の全過程を完了することができる。完備な統計情報が存在しない場合、第１コスト推定モデルを最適化した第２コス
ト推定モデルを用いてコストを推定し、すなわち、本願のコスト推定モデルを用いてコストを推定し、推定結果に基づいて最適な実行計画を生成する。ここで、本願のコスト推定モデルは、前記統計情報に依存する操作ツリーの操作タイプ（すなわち、第１操作タイプ）に基づいて対応するコスト推定方式を確定し、前記コスト推定方式に基づいて前記操作タイプに対応するコスト推定（すなわち、第１操作タイプの第１コスト推定）を確定し、前記統計情報に依存する操作タイプに対応するコスト推定、および統計情報に依存しない操作タイプに対応するコスト推定（すなわち、第２操作タイプに対応するコスト推定）に基づき、前記操作ツリーの累積したコスト推定を確定するように構成される。
【０１１７】
以上をまとめ、統計情報が正確ではないまたは完全ではない場合、本願に係る実施例におけるコスト推定のデバイスで実行する方法により、操作ツリーのコスト推定を行うことができ、本願に係るコスト推定のデバイスは、動作時に作成される一時テーブルおよびサブ検索、並びに大量データのシーンに適用でき、データ規模に制限されずにコスト推定を迅速に行うことができる。一方、本願に係るコスト推定のデバイスに基づいて得られたコスト最適化装置は、不備な統計情報に基づいて実行計画に対してコストを最適化することができる。統計情報が完備である場合、関連技術におけるコスト推定モデルは、応じる操作のコストを推定し、推定結果に基づいて最適な実行計画を生成することができる。統計情報が不備である場合、関連技術におけるコスト最適化装置は応じる操作に対してコストを推定することができないと、本願のコスト推定モデル（すなわち、操作ツリーの関連操作のコスト推定の方法を改良したもの）を用いて応じる操作に対してコストを推定し、推定結果に基づいて最適な実行計画を生成する。
【０１１８】
本願の一実施例において、プロセッサと、コンピュータ実行可能指令を記憶するように構成されるメモリとを備える計算に基づくデバイスを更に提供する。
【０１１９】
前記実行可能指令が実行されると、前記プロセッサは、取得された統計情報が完備であるか否かを判断し、統計情報が不備であれば、前記統計情報に依存する操作ツリーの操作タイプ（第１操作タイプ）に基づいて対応するコスト推定方式を確定し、前記コスト推定方式に基づいて前記操作タイプに対応するコスト推定（すなわち、第１操作タイプの第１コスト推定）を確定し、前記統計情報に依存する操作タイプに対応するコスト推定（第１操作タイプの第１コスト推定）、および統計情報に依存しない操作タイプに対応するコスト推定（すなわち、第２操作タイプに対応する第２コスト推定）に基づいて前記操作ツリーの累積したコスト推定を確定する。
【０１２０】
なお、本願は、ソフトウェアおよび／またはソフトウェアとハードウェアとの組み合わせで実施でき、例えば、専用の集積回路（ＡＳＩＣ）、汎用コンピュータまたは任意の他の類似するハードウェアデバイスで実現できる。１つの実施例において、本願のソフトウェアプログラムは、プロセッサにより実行されることにより、上述したステップまたは機能を実現することができる。同様に、本願のソフトウェアプログラム（関連するデータ構造を含む）は、ＲＡＭメモリ、磁気ドライブもしくは光ドライブ、またはフレキシブルディスクおよび類似するデバイスのようなコンピュータ可読レコード媒体に記憶されてもよい。また、本願のいくつかのステップまたは機能は、ハードウェアにより実現でき、例えば、プロセッサと協働して各ステップまたは機能を実行する回路として実現できる。
【０１２１】
また、本願の一部はコンピュータプログラム製品として適用でき、例えば、コンピュータプログラム指令としてコンピュータにより実行されると、該コンピュータの操作により、本願による方法および／または技術案を呼び出すまたは提供することができる。本願の方法を呼び出すプログラム指令は、固定または移動可能な記録媒体に記憶され、および／またはブロードキャストまたは他の信号ベアラ媒体におけるデータストリームにより伝送され、および／または前記プログラム指令に応じて動作するコンピュータデバイスのワー
クメモリに記憶される可能性がある。ここで、本願による一実施例は、コンピュータプログラム指令を記憶するためのメモリとプログラム指令を実行するためのプロセッサとを備える装置を含み、ここで、該コンピュータプログラム指令が該プロセッサにより実行されると、前述した本願による複数の実施例に基づく方法および／または技術案を実行するように該装置をトリガする。
【０１２２】
当業者にとって、本願は、上記例示的な実施例の詳細に限定されない。そのため、実施例を例示的かつ非限定的なものと見なすべきである。特許請求の範囲における任意の符号を、関する特許請求の範囲を限定するものと見なすべきではない。また、「含む」という用語は、他のユニットまたはステップを排除するものではなく、単数は複数を排除するものではない。装置の特許請求の範囲に記載される複数のユニットまたは装置は、１つのユニットまたは装置でソフトウェアまたはハードウェアにより実現されてもよい。第１、第２等の語は、名称を表すためのものであり、特定の順序を表すものではない。
【図１】
2021504852.tif 000047
【図２】
2021504852.tif 000048
【図３】
2021504852.tif 000049
【図４】
2021504852.tif 000050
【手続補正書】
【提出日】令和2年7月8日(2020.7.8)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
コスト推定の方法であって、
取得された統計情報が完備であるか否かを判断し、不備であれば、前記統計情報に依存する操作ツリーの操作タイプに基づいて対応するコスト推定方式を確定することと、
前記コスト推定方式に基づいて前記操作タイプに対応するコスト推定を確定することと、
前記統計情報に依存する操作ツリーの操作タイプに対応するコスト推定および統計情報に依存しない操作ツリーの操作タイプに対応するコスト推定に基づき、前記操作ツリーの累積したコスト推定を確定することと、
を含み、
前記統計情報に依存する操作ツリーの操作タイプは、テーブルスキャン操作、フィルタリング操作、結合操作および集計操作を含み、前記統計情報に依存しない操作ツリーの操作タイプは、投影操作、選択操作を含む、コスト推定の方法。
【請求項２】
前記累積したコスト推定に基づいて構造化照会言語の語句に対応する実行計画を最適化することを更に含む、請求項１に記載の方法。
【請求項３】
前記コスト推定方式に基づいて前記操作タイプに対応するコスト推定を確定することは、
データセットのレコード数に基づいてテーブルスキャン操作のコスト推定を確定することと、
フィルタリング述語のタイプに基づいてフィルタリング条件の選択率を確定した後、前記選択率に基づいてフィルタリング操作のコスト推定を確定することと、
確定された結合結果セットのレコード数に基づいて結合操作のコスト推定を確定することと、
集計フィールドおよび集計関数に基づいて集計フィールドの集計率を確定し、前記集計率に基づいて集計操作のコスト推定を確定することと、
を含む、請求項１に記載の方法。
【請求項４】
フィルタリング述語のタイプに基づいてフィルタリング条件の選択率を確定することは
、
フィルタリング述語のタイプに対応する、選択率を計算するオブジェクトが取得可能であるか否かを判断し、取得不可であれば、Ｓ＝１／指定値であると指定することを含む、請求項３に記載の方法。
【請求項５】
フィルタリング述語のタイプに対応する、選択率を計算するオブジェクトが取得可能であるか否かを判断し、取得不可であれば、Ｓ＝１／指定値であると指定することは、
フィルタリング述語のタイプがイコール述語である場合、前記フィルタリング操作の異値数が取得可能であるか否かを判断し、取得不可であれば、Ｓ＝１／指定値であると指定することと、
フィルタリング述語のタイプが範囲述語である場合、述語のフィールドの極値または異値数が取得不可であれば、Ｓ＝１／指定値であることと、
フィルタリング述語のタイプが空判別述語である場合、述語フィールドの空値数が取得可能であるか否かを判断し、取得不可であれば、前記フィルタリング条件の選択率がＳ＝１／指定値であることを確定することと、
を含む、請求項４に記載の方法。
【請求項６】
フィルタリング述語のタイプに基づいてフィルタリング条件の選択率を確定することは、
フィルタリング述語のタイプがｌｉｋｅである場合、前記フィルタリング条件の選択率Ｓ＝１／指定値であることと、
フィルタリング述語のタイプがＡＮＤカスケード述語である場合、カスケード述語の選択率の積およびＡＮＤカスケード述語におけるフィルタリング率の最小値に基づいてフィルタリング条件の選択率を確定することと、
フィルタリング述語のタイプがＯＲカスケード述語である場合、前記ＯＲカスケード述語に対応するカスケード述語の選択率に基づいてフィルタリング条件の選択率を確定することと、
を含む、請求項３に記載の方法。
【請求項７】
確定された結合結果セットのレコード数に基づいて結合操作のコスト推定を確定する前に、
結合された左テーブルおよび右テーブルの結合フィールドの異値数が取得不可であれば、結合フィールドの結合タイプに基づいて結合結果セットのレコード数を確定することを含む、請求項３に記載の方法。
【請求項８】
結合フィールドの結合タイプに基づいて結合結果セットのレコード数を確定することは、
結合フィールドの結合タイプが主キー−外部キー形式の結合である場合、外部キーフィールドのレコード数および主キーフィールドのフィルタリング条件の選択率に基づいて結合結果セットのレコード数を確定することと、
結合フィールドの結合タイプが内部結合である場合、結合された左テーブルのレコード数および右テーブルのレコード数のうちの最大値を結合結果セットのレコード数とすることと、
結合フィールドの結合タイプがクロス結合である場合、結合された左テーブルのレコード数と右テーブルのレコード数との積を結合結果セットのレコード数とすることと、
結合フィールドの結合タイプが左外部結合又は右外部結合である場合、対応する結合された左テーブルのレコード数又は右テーブルのレコード数を結合結果セットのレコード数とすることと、
結合フィールドの結合タイプが完全結合である場合、結合された左テーブルのレコード数および右テーブルのレコード数の累積を結合結果セットのレコード数とすることと、
を含む、請求項７に記載の方法。
【請求項９】
集計フィールドおよび集計関数に基づいて集計フィールドの集計率を確定することは、
集計フィールドのセットに少なくとも１つの主キーが存在する場合、集計フィールドの集計率は１であることと、
集計フィールドに対応する集計関数が単純な集計関数である場合、
（式１）
【数１】
2021504852.tif 000051
であることと、
（ただし、Ｒａｇｇは集計フィールドの集計率であり、ｎは集計フィールドのセットにおける集計フィールドの個数である）
集計フィールドに対応する集計関数がＲｏｌｌｕｐである場合、
（式２）
【数２】
2021504852.tif 000052
であることと、
（ただし、Ｒａｇｇは集計フィールドの集計率であり、ｎは集計フィールドのセットにおける集計フィールドの個数であり、ｋは正の整数である）
集計フィールドに対応する集計関数がＣｕｂｅである場合、
（式３）
【数３】
2021504852.tif 000053
であることと、
（ただし、Ｒａｇｇは集計フィールドの集計率であり、ｎは集計フィールドのセットにおける集計フィールドの個数であり、ｋは正の整数である）
を含む、請求項３に記載の方法。
【請求項１０】
コスト推定のデバイスであって、
取得された統計情報が完備であるか否かを判断し、不備であれば、前記統計情報に依存する操作ツリーの操作タイプに基づいて対応するコスト推定方式を確定するために用いられる判断装置と、
前記コスト推定方式に基づいて前記操作タイプに対応するコスト推定を確定するために用いられる確定装置と、
前記統計情報に依存する操作ツリーの操作タイプに対応するコスト推定および統計情報に依存しない操作ツリーの操作タイプに対応するコスト推定に基づき、前記操作ツリーの累積したコスト推定を確定するために用いられる推定装置と、
を備え、
前記前記統計情報に依存する操作ツリーの操作タイプは、テーブルスキャン操作、フィルタリング操作、結合操作および集計操作を含み、前記統計情報に依存しない操作ツリー
の操作タイプは、投影操作、選択操作を含む、コスト推定のデバイス。
【請求項１１】
前記累積したコスト推定に基づいて構造化照会言語の語句に対応する実行計画を最適化するために用いられる実行装置を更に含む、請求項１０に記載のデバイス。
【請求項１２】
前記確定装置は、
データセットのレコード数に基づいてテーブルスキャン操作のコスト推定を確定し、
フィルタリング述語のタイプに基づいてフィルタリング条件の選択率を確定した後、前記選択率に基づいてフィルタリング操作のコスト推定を確定し、
確定された結合結果セットのレコード数に基づいて結合操作のコスト推定を確定し、
集計フィールドおよび集計関数に基づいて集計フィールドの集計率を確定し、前記集計率に基づいて集計操作のコスト推定を確定するために用いられる、請求項１０に記載のデバイス。
【請求項１３】
前記確定装置は、
フィルタリング述語のタイプに対応する、選択率を計算するオブジェクトが取得可能であるか否かを判断し、取得不可であれば、Ｓ＝１／指定値と指定するために用いられる、請求項１２に記載のデバイス。
【請求項１４】
前記確定装置は、
フィルタリング述語のタイプがイコール述語である場合、前記フィルタリング操作の異値数が取得可能であるか否かを判断し、取得不可であれば、Ｓ＝１／指定値であると指定し、
フィルタリング述語のタイプが範囲述語である場合、述語のフィールドの極値または異値数が取得不可であれば、選択率Ｓ＝１／指定値であり、
フィルタリング述語のタイプが空判別述語である場合、述語フィールドの空値数が取得可能であるか否かを判断し、取得不可であれば、前記フィルタリング条件の選択率Ｓ＝１／指定値であることを確定するために用いられる、請求項１３に記載のデバイス。
【請求項１５】
前記確定装置は、
フィルタリング述語のタイプがｌｉｋｅである場合、前記フィルタリング条件の選択率Ｓ＝１／指定値であり、
フィルタリング述語のタイプがＡＮＤカスケード述語である場合、カスケード述語の選択率の積およびＡＮＤカスケード述語におけるフィルタリング率の最小値に基づいてフィルタリング条件の選択率を確定し、
フィルタリング述語のタイプがＯＲカスケード述語である場合、前記ＯＲカスケード述語に対応するカスケード述語の選択率に基づいてフィルタリング条件の選択率を確定するために用いられる、請求項１２に記載のデバイス。
【請求項１６】
前記確定装置は、
結合された左テーブルおよび右テーブルの結合フィールドの異値数が取得不可であれば、結合フィールドの結合タイプに基づいて結合結果セットのレコード数を確定するために用いられる、請求項１２に記載のデバイス。
【請求項１７】
前記確定装置は、
結合フィールドの結合タイプが主キー−外部キー形式の結合である場合、外部キーフィールドのレコード数および主キーフィールドのフィルタリング条件の選択率に基づいて結合結果セットのレコード数を確定し、
結合フィールドの結合タイプが内部結合である場合、結合された左テーブルのレコード数および右テーブルのレコード数のうちの最大値を結合結果セットのレコード数とし、
結合フィールドの結合タイプがクロス結合である場合、結合された左テーブルのレコード数と右テーブルのレコード数との積を結合結果セットのレコード数とし、
結合フィールドの結合タイプが左外部結合又は右外部結合である場合、対応する結合された左テーブルのレコード数又は右テーブルのレコード数を結合結果セットのレコード数とし、
結合フィールドの結合タイプが完全結合である場合、結合された左テーブルのレコード数および右テーブルのレコード数の累積を結合結果セットのレコード数とするために用いられる、請求項１６に記載のデバイス。
【請求項１８】
前記確定装置は、
集計フィールドのセットに少なくとも１つの主キーが存在する場合、集計フィールドの集計率は１であり、
集計フィールドに対応する集計関数が単純な集計関数である場合、
（式４）
【数４】
2021504852.tif 000054
であり、
（ただし、Ｒａｇｇは集計フィールドの集計率であり、ｎは集計フィールドのセットにおける集計フィールドの個数である）
集計フィールドに対応する集計関数がＲｏｌｌｕｐである場合、
（式５）
【数５】
2021504852.tif 000055
であり、
（ただし、Ｒａｇｇは集計フィールドの集計率であり、ｎは集計フィールドのセットにおける集計フィールドの個数であり、ｋは正の整数である）
集計フィールドに対応する集計関数がＣｕｂｅである場合、
（式６）
【数６】
2021504852.tif 000056
であるために用いられる、
（ただし、Ｒａｇｇは集計フィールドの集計率であり、ｎは集計フィールドのセットにおける集計フィールドの個数であり、ｋは正の整数である）
請求項１２に記載のデバイス。
【請求項１９】
プロセッサと、
コンピュータ実行可能指令を記憶するように構成されるメモリと、
を備える計算に基づくデバイスであって、
前記実行可能指令が実行されると、前記プロセッサは、
取得された統計情報が完備であるか否かを判断し、不備であれば、前記統計情報に依存
する操作ツリーの操作タイプに基づいて対応するコスト推定方式を確定し、
前記コスト推定方式に基づいて前記操作タイプに対応するコスト推定を確定し、
前記統計情報に依存する操作ツリーの操作タイプに対応するコスト推定および統計情報に依存しない操作ツリーの操作タイプに対応するコスト推定に基づき、前記操作ツリーの累積したコスト推定を確定し、
前記前記統計情報に依存する操作ツリーの操作タイプは、テーブルスキャン操作、フィルタリング操作、結合操作および集計操作を含み、前記統計情報に依存しない操作ツリーの操作タイプは、投影操作、選択操作を含む、計算に基づくデバイス。
【国際調査報告】
2021504852.tif 000057
2021504852.tif 000058
2021504852.tif 000059
2021504852.tif 000060