(57)【要約】  本発明は、データベース管理システム（ＤＢＭＳ）のようなコンピュータプログラムの性能を向上させるシステム及び方法に関する。前記方法は、プログラム表現（ＰＲ）に基づいて、前記ＤＢＭＳコードにおける変数の不変区間を識別するステップを含む。前記ＤＢＭＳ内のプログラム相互作用及びドメインアサーションは、前記ＰＲ及び前記ＤＢＭＳのエコシステム仕様に基づいて推定される。１つまたは複数の候補スニペットは、前記ＤＢＭＳコードにおける変数の前記不変区間、前記ＰＲ、前記ＤＢＭＳと関連付けられた１つまたは複数の実行サマリー、前記推定したプログラム相互作用、および前記推定したドメインアサーションに基づいて、識別される。Spiffsは前記１つまたは複数の候補スニペットに基づいて生成される。該spiffsは述語クエリspiff、ハッシュ結合クエリspiff、集約クエリspiff、ページstiff、及びストリングマシンstiffを含む。前記ＤＢＭＳコードはこれらspiffsから生成されたスペックコードに基づいて修正される。【選択図】図１
2018510445.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータプログラムコードの性能を向上させるコンピュータ実装方法であって：
プログラム表現（ＰＲ）すなわち前記コンピュータプログラムコードの抽象構文木等の具現化に基づいて、前記コンピュータプログラムコードにおける変数の不変区間を識別するステップと；
前記ＰＲおよび前記コンピュータプログラムのエコシステム仕様に基づいて、前記コンピュータプログラム内のプログラム相互作用を推定するステップと；
前記ＰＲ、前記コンピュータプログラムコードにおける変数の前記識別した不変区間、および前記推定したプログラム相互作用に基づいて、ドメインアサーションを推定するステップと；
前記コンピュータプログラムコードにおける変数の前記不変区間、前記ＰＲ、前記コンピュータプログラムと関連付けられた１つまたは複数の実行サマリー、前記推定したプログラム相互作用、および前記推定したドメインアサーションに基づいて、１つまたは複数の候補スニペットを識別するステップと；
前記１つまたは複数の候補スニペットに基づいて、特化コンピュータプログラムコードを生成するステップと、
前記生成した特化コンピュータプログラムコードに基づいて、前記コンピュータプログラムコードを修正するステップと、
前記特化コンピュータプログラムコードを隠すステップと、
を含む、コンピュータ実装方法。
【請求項２】
（ａ）前記識別した不変区間が複数の実行に及ぶ；
（ｂ）前記識別した不変区間が特定の変数の少なくとも一組の不変区間を含み、前記一組中のすべての不変区間が同じ開始ノードを共有する、
の少なくとも一方を含むことを特徴とする、請求項１に記載のコンピュータ実装方法。
【請求項３】
前記１つまたは複数の候補スニペットがそれぞれ、（ａ）前記ＰＲにより識別されたコード区間または（ｂ）一組の不変値および各変値の一組の考え得る値を含む、請求項１または２に記載のコンピュータ実装方法。
【請求項４】
前記１つまたは複数の候補スニペットがそれぞれ、当該候補スニペットの適当な寿命を含んでおり、前記１つまたは複数の候補スニペットがそれぞれ、当該候補スニペットの前記適当な寿命内で採用される推奨最適化を含むのが好ましい、請求項１乃至３のいずれかに記載のコンピュータ実装方法。
【請求項５】
特化コンピュータプログラムコードを生成する前記ステップが、（ａ）前記コンピュータプログラムの適所にコードを挿入して前記特化コンピュータプログラムコードを作成し、前記特化コンピュータプログラムコードを呼び出し、前記特化コンピュータプログラムコードを破壊するステップもしくは（ｂ）所与の文字列パターンに対して任意の文字列を照合する特化関数を作成するステップ、メタ特化器を使用して、インタープリットされたデータ構造およびホットスワッピングを検討することにより、既存の特化コンピュータプログラムコードを変換するステップ、クエリを呼び出すステップ、前記コンピュータプログラムコードの分岐を除去することにより前記コンピュータプログラムコードのサイズを小さくするステップ、数値を利用して領域内特化器（Ｓｐｉｆｆ）データ部のスラブ割り当てを行うステップであり、前記コンピュータプログラムコード内のすべての入力行にわたって対応する集約関数を演算することによりＳｐｉｆｆデータ部を再利用して、行単位のメモリ割り当てを除去するステップで、前記数値が、行単位でサポート可能な最大桁数によって規定される、ステップ、または前記コンピュータプログラムが格納されたディスクもしくはメモリページ内の不変値を利用し、前記ページが読み出されたらデータレイアウトを再構成し、データ局所性を最適化するステップを含む、請求項１乃至４のいずれかに記載のコンピュータ実装方法。
【請求項６】
前記特化コンピュータプログラムコードが、実行時に作成されて後で呼び出され、任意選択として、前記識別した不変区間の違反が所与の実行において発生するかを判定するステップをさらに含む、請求項１乃至５のいずれかに記載のコンピュータ実装方法。
【請求項７】
コンピュータプログラムの性能を向上させるように構成されたシステムであって：
前記コンピュータプログラムのプログラム表現（ＰＲ）に基づいて、前記コンピュータプログラムにおける変数の不変区間を識別する不変探索器と；
前記ＰＲおよび前記コンピュータプログラムのエコシステム仕様に基づいて、前記コンピュータプログラム内のプログラム相互作用を推定する相互作用推定器と；
前記ＰＲ、前記コンピュータプログラムコードにおける変数の前記識別された不変区間、および前記推定されたプログラム相互作用に基づいて、ドメインアサーションを推定するドメインアサーション推定器と；
前記コンピュータプログラムコードにおける変数の前記不変区間、前記ＰＲ、前記コンピュータプログラムと関連付けられた１つまたは複数の実行サマリー、前記推定されたプログラム相互作用、および前記推定されたドメインアサーションに基づいて、１つまたは複数の候補スニペットを識別するスニペット探索器と；
前記１つまたは複数の候補スニペットに基づいて、特化コンピュータプログラムコードを生成する領域内特化器（Ｓｐｉｆｆ）構成器と；
前記生成された特化コンピュータプログラムコードを受信し、前記生成された特化コンピュータプログラムコードに基づいて、前記コンピュータプログラムコードを修正する特化ソースと、
を備えた、システム。
【請求項８】
前記不変探索器が、前記ＰＲに関する静的解析を行って不変区間を識別する、請求項７に記載のシステム。
【請求項９】
前記識別された不変区間が特定の変数の少なくとも一組の不変区間を含み、前記一組中のすべての不変区間が同じ開始ノードを共有する、請求項７または８に記載のシステム。
【請求項１０】
前記識別された不変区間の違反が所与の実行において発生するかを判定する不変検査器をさらに備えた、請求項７乃至９のいずれかに記載のシステム。
【請求項１１】
前記１つまたは複数の候補スニペットがそれぞれ、一組の不変値および各変値の一組の考え得る値を含む、請求項７乃至１０のいずれかに記載のシステム。
【請求項１２】
前記１つまたは複数の候補スニペットがそれぞれ、当該候補スニペットの適当な寿命を含んでおり、前記１つまたは複数の候補スニペットがそれぞれ、当該候補スニペットの前記適当な寿命内で採用される推奨最適化を含むのが好ましい、請求項７乃至１１のいずれかに記載のシステム。
【請求項１３】
前記Ｓｐｉｆｆ構成器が、前記コンピュータプログラムの適所にコードを挿入して前記特化コンピュータプログラムコードを作成し、前記特化コンピュータプログラムコードを呼び出し、前記特化コンピュータプログラムコードを破壊すること、所与の文字列パターンに対して任意の文字列を照合する特化関数を作成すること、メタ特化器を使用して、インタープリットされたデータ構造およびホットスワッピングを検討することにより、既存の特化コンピュータプログラムコードを変換すること、スキーマによるクエリにおいて有効なクエリ不変値と生の不変値とを組み合わせること、前記コンピュータプログラムコードの分岐を除去することにより前記コンピュータプログラムコードのサイズを小さくすること、数値を利用して領域内特化器（Ｓｐｉｆｆ）データ部のスラブ割り当てを行うことであり、前記コンピュータプログラムコード内のすべての入力行にわたって対応する集約関数を演算することによりＳｐｉｆｆデータ部を再利用して、行単位のメモリ割り当てを除去することで、前記数値が、行単位でサポート可能な最大桁数によって規定される、こと、または前記コンピュータプログラムが格納されたディスクもしくはメモリページ内の不変値を利用し、前記ページが読み出されたらデータレイアウトを再構成し、データ局所性を最適化することを行うようにさらに構成された、請求項７乃至１２のいずれかに記載のシステム。
【請求項１４】
コンピュータ機器のプロセッサにより実行された場合に：
コンピュータプログラムのプログラム表現（ＰＲ）に関する静的解析によって、識別された不変区間内で値が不変の前記コンピュータプログラムにおける変数を決定することと；
前記コンピュータプログラムの適所にコードを生成して特化コンピュータプログラムコードを作成し、前記特化コンピュータプログラムコードを呼び出し、前記特化コンピュータプログラムコードを破壊することであり、特化コンピュータプログラムコードが少なくとも前記決定された変数に基づいて作成される；ことと、
前記特化コンピュータプログラムが呼び出された場合に、前記特化コンピュータプログラムコードで前記コンピュータプログラムの少なくとも一部を修正することと、
を前記コンピュータ機器に行わせるコンピュータ実行可能命令を含む持続性コンピュータ可読媒体。
【請求項１５】
前記特化コンピュータプログラムコードを生成することが、前記コンピュータプログラムと関連付けられたドメイン固有知識および予備ソース知識の少なくとも一方にさらに基づく、請求項１４に記載の持続性コンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は一般的に、コンピュータプログラムの性能を向上させる領域特化に関し、より詳細には、変数の不変区間を識別するとともに、識別した不変区間に少なくとも部分的に基づいて生成された特化コードを利用してＤＢＭＳコードを修正することにより、データベース管理システムの性能を向上させるシステムおよび方法に関する。
【背景技術】
【０００２】
データベース管理システム（ＤＢＭＳ）は、データの格納およびアクセスを管理するソフトウェアプログラムの集まりである。今日、生成されるデータ量が多くなっており、格納および効率的なアクセスが必要となっていることから、広範な用途領域全体でＤＢＭＳが採用されている。過去４０年にわたるこのようなユビキタス展開によって、ＤＢＭＳは、一般的にこのような領域に適用できる数個のデータモデルに基づいて、設計および運用がなされている。リレーショナルデータモデルは、市販のオープンソースＤＢＭＳに最も広く受け入れられているモデルの１つである。このデータモデルを効率的にサポートするため、かなりの労力が捧げられてきた。
【０００３】
リレーショナルデータモデルの一般性により、リレーショナルデータベース管理システム自体も、ユーザが指定する如何なるスキーマであれ、提示される如何なるクエリまたは修正であれ、これらを処理可能である点において一般性を有する。関係演算子は、本質的に如何なる関係にも作用するため、基本関係の任意の属性に指定された述語に対応する必要がある。効果的な索引構造、革新的な並行処理制御メカニズム、および洗練されたクエリ最適化法等の革新によって、今日利用可能なリレーショナルＤＢＭＳは、非常に効率的である。また、このような一般性および効率により、多くの領域に拡散して使用可能となっている。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
上記に関わらず、一般性は、複数の間接レイヤおよび洗練されたコードロジックにより実現される。このようなシステムの実行中に存在する不変値を利用することにより、ＤＢＭＳに関して効率をさらに増大可能である。本出願に開示の領域特化技術は、不変値を自動的に識別するとともに、不変値に基づいてコード特化を有効にするために開発したものである。
【課題を解決するための手段】
【０００５】
本開示の実施形態は、データベース管理システム（ＤＢＭＳ）の性能を向上させるシステムおよび方法を提供する。簡潔に説明するなら、この方法の一実施形態はとりわけ、以下のように実装可能である。ＤＢＭＳの性能を向上させるコンピュータ実装方法は、（i）ＤＢＭＳソースコードのコンパイル時間解析に基づいて、ＤＢＭＳコードにおける変数の不変区間を識別するステップと、（ii）ソースコードおよびＤＢＭＳのエコシステム仕様に基づいて、ＤＢＭＳ内のプログラム相互作用を推定するステップと、ソースコード、ＤＢＭＳコードにおける変数の識別した不変区間、および推定したプログラム相互作用に基づいて、いわゆるドメインアサーションを推定するステップと、（iii）ＤＢＭＳコードにおける変数の不変区間、ソースコード、さまざまなワークロードを用いて実行されたＤＢＭＳと関連付けられ１つまたは複数の実行サマリー、推定したプログラム相互作用、および推定したドメインアサーションに基づいて、１つまたは複数の候補スニペットを識別するステップと、（iv）識別した候補スニペットに基づいて、コンパイル時および実行時を含むさまざまな時点に特化ＤＢＭＳコードを生成するステップと、（v）利用可能なコードを挿入することにより、ＤＢＭＳを修正して、場合により実行時に特化コードの生成を実行し、その後、特化コードを呼び出すステップと、を含む。
【０００６】
本開示の他のシステム、方法、特徴、および利点については、以下の図面および詳細な説明を参照することによって、当業者に明らかとなるであろう。このような付加的なシステム、方法、特徴、および利点はすべて、本明細書に含まれ、本開示の範囲に含まれ、添付の特許請求の範囲によって保護されるものである。
【０００７】
以下の図面を参照することによって、本開示の多くの態様をより深く理解することができる。図面中の構成要素は、必ずしも縮尺通りではなく、本開示の原理を明示するために強調している場合がある。さらに、図面中においては、複数の図にわたって同じ参照番号が対応する部分を示している。
【図面の簡単な説明】
【０００８】
【図１】本開示が提供する例示的な一実施形態に係るＳｐｉｆｆツールアーキテクチャを示したブロック図である。
【図２】本開示が提供する例示的な一実施形態に係る領域特化プロセスのブロック図である。
【図３】本開示が提供する例示的な一実施形態によるコンピュータサイエンスのパラダイムを精緻化する領域特化を示した図である。
【発明を実施するための形態】
【０００９】
本開示の多くの実施形態は、プログラム可能なコンピュータが実行するアルゴリズム等のコンピュータ実行可能命令の形態であってもよい。ただし、本開示は、他のコンピュータシステム構成でも同様に実施可能である。本開示の特定の態様は、以下に記載のコンピュータ実行可能アルゴリズムのうちの１つまたは複数を実行するように具体的にプログラム、構成、または構築された専用コンピュータまたはデータプロセッサにおいて具現化可能である。
【００１０】
また、本開示は、分散コンピューティング環境においても実施可能であり、通信ネットワークを介して結合されたリモート処理機器によってタスクまたはモジュールが実行される。さらに、本開示は、インターネットベースまたはクラウドコンピューティング環境において実施可能であり、共有リソース、ソフトウェア、および情報がオンデマンドでコンピュータ等の機器に提供されるようになっていてもよい。分散コンピューティング環境においては、ローカルおよびリモートのメモリ記憶デバイス両者にプログラムモジュールまたはサブルーチンが配置されていてもよい。以下に記載の本開示の態様は、磁気および光学式可読および取り外し可能コンピュータディスク、固定磁気ディスク、フロッピーディスクドライブ、光ディスクドライブ、光磁気ディスクドライブ、磁気テープ、ハードディスクドライブ（ＨＤＤ）、半導体ドライブ（ＳＳＤ）、コンパクトフラッシュ（登録商標）等の不揮発性メモリ等のコンピュータ可読媒体のほか、クラウド等のネットワーク上で電子的に分散したコンピュータ可読媒体に格納または分散されていてもよい。本開示の態様に特有のデータ構造およびデータ伝送についても、本開示の範囲に含まれる。
【００１１】
本発明は、本明細書では主にリレーショナルＤＢＭＳに関して説明するが、このようなＤＢＭＳタイプには限定されない。本発明は、階層型、ネットワーク型、およびオブジェクト指向型のＤＢＭＳタイプ等、任意のＤＢＭＳタイプに適用可能であることが容易に了解されるが、これらに限定されない。さらに、本明細書においては主に、ＤＢＭＳに関して領域特化を開示するが、本明細書で提供する概念は、データ操作、特に、データに関する複雑な解析を実行する任意のプログラムに適用可能であることが了解されるものとする。具体的に、開示のシステムおよび方法は、高い実行時性能を要するとともに、同じデータに対して異なるパラメータまたはクエリでアプリケーションを複数回実行するコンピュータプログラムにも適用可能であることが了解される。領域内特化器を表すＳｐｉｆｆは、ＤＢＭＳ実行時に特化コードを動的に作成するコードである。「領域特化」は、実行時不変値を利用してＤＢＭＳがそれ自体を特化できるように、ＳｐｉｆｆをＤＢＭＳコードに挿入するプロセスである。特化コード（本明細書においては、「ｓｐｅｃｃｏｄｅ」と称する場合もある）は、元の非特化コードよりも高速で、一般的に小さい。領域特化は、「領域内」すなわちＤＢＭＳが展開されてエンドユーザ側で動作している際に特化コードが生成されて呼び出されるという事実により命名されたものである。Ｓｐｉｆｆは、実行時不変値（実行時に取得）の実際の値を用いることにより、当該実行時不変値の特定の値に対して特化されたコードを動的に生成する。
【００１２】
本出願が優先権を主張する本出願人の米国特許同時係属出願第１４／３６８，２６５号明細書において、用語「マイクロ特化」は、本明細書で使用する用語「領域特化」に相当し、用語「Ｂｅｅ」は、本明細書で使用する用語「Ｓｐｉｆｆ」に相当し、インスタンス化されたＢｅｅは、本明細書で使用する「特化コード」に相当し（Ｓｐｉｆｆの結果である）、ＨＲＥ（Ｈｉｖｅ実行時環境）は、本明細書で使用する「ＳＲＥ」（Ｓｐｉｆｆ実行時環境）に相当する。
【００１３】
アーキテクチャ
図１は、本開示が提供する例示的な一実施形態に係るＳｐｉｆｆツールアーキテクチャを示したブロック図である。
【００１４】
一実施形態において、本開示は、図１に示すように、以下のような３つの入力を前提として、任意のプログラムを自動的に領域特化するＳｐｉｆｆツールアーキテクチャを提供する：
当然の入力であるアプリケーションのソースコード、
１つまたは複数のワークロード、
エコシステム仕様。
【００１５】
したがって、このアーキテクチャでは、領域特化がアプリケーションソースコードを解析し、最終的に、これら３つの入力を利用した完全自動のプロセスとなって、セマンティクスは同一であるもののより高速に動作する特化アプリケーションを生成するものと仮定する。
【００１６】
目標
このアーキテクチャの目標は、以下の通りである。
１．ソースファイルをプログラムまたは一連の関連プログラムとするエンドツーエンドのソリューションを提供し、Ｓｐｉｆｆ生成、Ｓｐｉｆｆコンパイル、Ｓｐｉｆｆインスタンス化、Ｓｐｉｆｆ起動、およびＳｐｉｆｆガベージコレクションのコード等、上記ソースファイルを領域特化したものを自動的に提供する。
２．高並列グラフィック処理ユニット（ＧＰＵ）等、任意の従来アーキテクチャに対してコンパイルされた仮想的に任意のプログラムと当該アーキテクチャが協働する点において、ドメイン独立性を提供する。
３．ツールユーザが提供を要する情報を最小限に抑えるとともに、解析中のプログラムから抽出される情報を最大化する。
４．それぞれが概念的タスクを１つだけ実行する一連のツールへと解析を分割する。
５．各ツールが当該ツールの解析結果を捕捉するわずかな出力を生成するようにして、ツールのスケーラビリティを有効にする。
６．ツールを小さなプログラム上で最初にテストした後、現実的なプログラム上でテストできるように、漸進的開発を有効にする。
７．最初に部分的な最大限の解析（たとえば、不変値の一部のみまたは最小限の候補スニペットの探索）を行った後、各ツールを改良して、時間とともにより包括的な出力を生成できる点において、連続的な改良を有効にする。
８．Ｓｐｉｆｆにより導入される個々のコード変換の利益を動的および／または独立に評価可能であり、コード変換のすべての組み合わせを網羅的に評価するとともにそれぞれの実行時間を測定することなく、有効なコード変換および特定のワークロードの特性を考慮することによって、当該Ｓｐｉｆｆの全体利益を演算可能であることから、性能利益推定を有効にする。
【００１７】
ツール
図１に示すように、Ｓｐｉｆｆツールアーキテクチャには、多くのツールを含む。これらのツールとしては、不変探索器、追跡器、不変検査器、プログラム相互作用推定器、ドメインアサーション推定器、スニペット探索器、およびＳｐｉｆｆ構成器が挙げられるが、それぞれについては以下で詳しく説明する。図１に示す例示的なＳｐｉｆｆツールアーキテクチャにより、当業者であれば、本開示の主旨および原理から実質的に逸脱することなく、多くの変形および他の分割が可能であることが了解されよう。
【００１８】
この説明では、アプリケーションのソースコードの共通のコンピュータ可読構造化である抽象構文木（ＡＳＴ）等の特定のプログラム表現（ＰＲ）を利用する。また、本発明は、アプリケーションのテキストソースコード、ソースコードの低レベル中間表現（ＩＲ）、あるいはソースコードの同等アセンブリまたはマシンコード表現に対して直接、解析が代替的に実行される場合にも当てはまる。なお、ＰＲが利用する個々のプログラム構成は、プログラム表現（ＰＥ）と称する。ＡＳＴの場合はＰＥがＡＳＴノードであり、ＩＲの場合はＰＥがＩＲ命令であり、ソースコードの場合はＰＥが単文である。
【００１９】
不変探索器
不変探索器は、特化対象のＤＢＭＳのＰＲおよび追跡イベント（任意）を入力とし、ＰＲに対して静的解析を実行することにより、ゼロ個以上の不変区間を出力する。
【００２０】
いくつかの定義：
不変区間：単一の開始ＰＥ（または、ソースコード内の単一位置も同等）および１つまたは複数の考え得る実行中に開始ノードから到達可能な単一の終了ＰＲにより規定され、変数の特定の特性が持続する一組のパスである。このような特性の例は記載していない（区間は、単一のパスではなく、一組のパスから成り得る。たとえば、対象となっている変数を修正するｉｆ／ｅｌｓｅブロックの分岐はないため、この変数は、これらの分岐と関連付けられたすべてのコードパス上で不変のままである）。なお、不変区間は、開始ＰＥにおいて始まり（すなわち、変数が当該割り当て値となったら直ちに始まる（開始ＰＥは常に、変数の値を設定する文である））、値が再び設定される直前の終了ＰＥにおいて終わる。このパスに沿った各ＰＥにおいて、当該変数の値は、当該パスに沿った他の点と同じになるため、不変と称する。
不変区間セット：含まれるすべての不変区間が同じ開始ノードを共有する特定の変数の一組の不変区間である。区間は、当該ＰＥの実行後にも指定特性が持続することを解析によって確定し得ない場合、必要以上に終端となる点において、おそらく最大ではない。
値フロー木（ＶＦＴ）：ある変数の値の別の変数へのコピーを捕捉する木である。ＶＦＴは、変数Ｘによって変数Ｙの値が割り当てられている場合、Ｘの不変区間セットをＹの不変区間セットに接続する。
【００２１】
一例として、不変区間は、変数の値（すなわち、特性が値である）が持続する（たとえば、（ある定数Ｎについて）「変数がＮに等しい」）区間にわたって存在していてもよい。これにより、たとえば以下のような特定種類の最適化が省略される場合がある：
プログラム状態に基づく最適化（たとえば、集約演算におけるメモリ割り当て最適化）。
「変数がＮに等しい」という形態ではない特性に基づく最適化（たとえば、コードの一部if(p!=NULL)Sを前提とするなら、ポインタｐは、Ｓにおいて非ヌルの必要があり、たとえばＳから呼び出される関数において、冗長なヌルチェックを最適化により除去可能であるべきことが分かっている）。
コード中で明示されていない可能性がある導出値（たとえば、文字列の長さ）に基づく最適化。
ドメイン知識（たとえば、列中に現れ得る一組の値の濃度）に基づく最適化。
【００２２】
実施例１：ｉｆ文
以下に示すＥｘａｍｐｌｅ１を考える。
2018510445.tif 000003
【００２３】
ここで、不変探索器は、「ｉｆ」文が真偽いずれになるかを静的に把握しない。このため、不変探索器は、変数ｘに関して、以下の不変区間セットを出力するものとする：
簡略化のため、ＰＥ  ＩＤの代わりに行番号を用いて、ソース位置を識別する。また、閉開区間を使用する。
不変区間セット＃１：行１で始まり、１不変区間である：
不変区間＃１．１：行３で終わる
不変区間セット＃２：行１０で始まり、１不変区間である：
不変区間＃２．１：行１５（すなわち、プログラムの最後）で終わる
【００２４】
不変探索器は、ＸＭＬ等の何らかの構造化フォーマットで上記を出力するようにしてもよいが、本開示においては、簡略化のため、リストおよびサブリストが利用される。
【００２５】
不変探索器は、その精度が変動してもよいが、正確さは必要である。具体的に、不変探索器が生成する不変値は、正確であるべきものの、必ずしも網羅的である必要はない。たとえば、ｘは、行１〜行５および行１〜行９において実際に不変である。ただし、正確でもある（精度は低い）ため、たとえば、「ｉｆ」文の最初に区間を停止する。当然のことながら、低精度の区間では、スニペット探索器およびＳｐｉｆｆ構成器（以下に説明するツール）がアプリケーションを領域特化する機会はそれほど多くない。
【００２６】
不変探索器は、プログラム中のすべての変数に関して、このような不変区間セットを出力することも可能である。これを変数ｈについて考察する：
不変区間セット＃３：行１１で始まり、１不変区間である：
不変区間＃３．１：行１３で終わる
不変区間セット＃４：行１３で始まり、１不変区間である：
不変区間＃４．１：行１５で終わる
変数ｙについては、以下であるものとする：
不変区間セット＃５：行２で始まり、１不変区間である：
不変区間＃５．１：行１５で終わる
ｚについては、以下であるものとする：
不変区間セット＃６：行１２で始まり、１不変区間である：
不変区間＃６．１：行１５で終わる
最後に、変数ａについては、以下であるものとする：
不変区間セット＃７：行１４で始まり、１不変区間である：
不変区間＃７．１：行１５で終わる
【００２７】
変数ｈがどのようにその値を変数ｘから取得するか（ｘからの値の「フロー」）について言及する。これにより、ｚの値のｈからの「フロー」が生じる。そこで、すべてをまとめて試すために、ｘのＶＦＴは、以下のＥｘａｍｐｌｅ２に示すように、例示的な基準表現で与えられるものとする。
2018510445.tif 000004
【００２８】
「from」および「to」属性の数値は、上記の不変区間セット（ＩＩＳ）のうちの１つを表す。このため、指定の第１の行は、不変区間セット＃１〜不変区間セット＃４である。
【００２９】
実施例２：値渡し関数
変数「ａ」は、関数X()において不変であるものの、呼び出された関数Y(a)内で値が一時的に変化するものと仮定する。Y(a)が戻った時、「ａ」の値は、依然としてその（不変）値を有する。この状況は、変数の値を通過する関数呼び出しが当該値の別の変数へのコピーであり、それ自体の不変区間セットと関連付けられていることから対応がなされる。
【００３０】
実施例３：割り当てのないループ
以下のＥｘａｍｐｌｅ３のコードを考える：
2018510445.tif 000005
【００３１】
ループを理解するため、不変探索器は、実際にループを展開するものとする。もっと正確に言えば、ループ内の変数割り当てがあるかを確認するものとする。本実施例のように、割り当てがない場合は、当該ループに達する不変区間がループ全体に延びることになる：
不変区間セット＃１：行１で始まり、１不変区間である：
不変区間＃１．１：８で終わる
【００３２】
実施例４：既存の変数への割り当てがあるループ
ただし、Ｅｘａｍｐｌｅ４を参照して、ループにおける条件付き変数割り当てを考える：
2018510445.tif 000006
【００３３】
ここで、不変探索器は、以下の区間を作成することになる：
不変区間セット＃１：行１で始まり、１不変区間である：
不変区間＃１．１：２で終わる
不変区間セット＃２：行７で始まり、１不変区間である：
不変区間＃２．１：９で終わる
不変区間セット＃３：行９で始まり、１不変区間である：
不変区間＃３．１：１０で終わる
【００３４】
なお、この場合も、低精度ではあるが依然として正確な簡略化によって、潜在的に変数を表す可能性がある任意のループを除外している。さらに、関数呼び出しによってはｘの値を変更できず、むしろ、some_other_funcローカルの変数に値がコピーされることから、区間は行８で終了とならないことに留意するものとする。
【００３５】
実施例５：新たな変数の作成を伴うループ
Ｅｘａｍｐｌｅ５を参照して、ループにおける変数の作成を考える：
2018510445.tif 000007
【００３６】
ここで、不変探索器は、以下を作成することになる：
不変区間セット＃１：行４で始まり、１不変区間である：
不変区間＃１．１：８で終わる（すなわち、ループの最終反復の後）
【００３７】
不変探索器の例示的なアルゴリズム
不変探索器は、コールグラフの葉すなわち他の如何なる関数も呼び出さない関数を始点とする。そして、当該関数のＶＦＴを演算し、変数がコピーされた場合（たとえば、h=x;）にエッジを追加することも可能である。その後、葉関数のみを呼び出す関数を考慮した後、（xが渡された場合等に）ローカル変数のエッジを追加するとともに区間を統合することも可能である。そして、反復により、ＶＦＴが演算された関数のみを呼び出す関数を考慮することも可能である。
【００３８】
コールグラフ内の再帰関数およびサイクルには、別の注意を要する。コールグラフのボトムアップ走査は、プログラムの静的解析である。不変値がすべてのパスにおいて真であることが必要なため、不変探索器は、シグネチャを使用するとともに、その呼び出しシグネチャに一致する任意の関数の間接呼び出しが可能であるものと仮定する。
【００３９】
なお、ループ内のメモリ割り当ては、多くの異なる実行時配置を生じさせ得る。このような割り当てが起こると、当該変数が指すメモリは、変数が割り当てられるまで不変である。ループ内の割り当ては、（たとえば、アレイの）新たな要素への割り当てまたは変数の上書きとなる。
【００４０】
間接的な関数呼び出しの場合、不変探索器は、関数ポインタの値を伝搬させて各間接呼び出しの考え得る一組の対象を見つけ出す前方解析ステップと、上述の通りコールグラフのボトムアップに値フローを伝搬させる後方解析ステップとを交互に行うことができる。この交互実行は、一組の関数ポインタ対象が安定するまで反復可能である。
【００４１】
不変探索器は、変数がとり得る値をさらに識別するようにしてもよい。一例として、変数join_typeの場合は、当該変数に割り当てられる異なる値がごくわずかであり、すべて静的に把握されていてもよい。これは、変数の型（列挙）にて指定される場合があり、静的解析（たとえば、当該変数に割り当てられたすべての値の調査）によって発見可能となる場合がある。考え得る一組の値が小さい場合、不変探索器は、各値の不変区間を記録するようにしてもよい。
【００４２】
正確性
ツールにより戻された各不変区間は、正確であるものとする。すなわち、関連する変数が当該区間の開始と終了との間（終了は含まず）のすべてのパスにわたって不変であることが保証されるものとする。いずれかのパスにおいて間接的な割り当てが存在する場合、不変探索器ツールは、このようなすべての割り当てが指定変数の値を変化させることのないようにする必要がある。
【００４３】
解析は、２つの点において慎重であっていてもよい。第１に、検出漏れ（（ａ）区間セットまたは（ｂ）区間セット内の個々の区間として正確であるものの、ツールにより戻されていない区間）が存在していてもよい。変数が割り当てられている（すなわち、不変区間を開始している）もののツール（不明な区間セット）および不完全な区間セット（不明な個々の区間）によって解析されていない場所をツールが示している場合は許容範囲である。
【００４４】
第２に、非最大区間（無条件に値を変化させる文で終わらない区間）が存在していてもよい。これは、（ａ）実際には値を変化させない割り当てまたは（ｂ）値が不変であると判定するのに解析が十分正確ではない非割り当て（たとえば、当該文において値を変化させる可能性がある「ｆｏｒ」文）が原因とも考えられる。
【００４５】
また、正確性には、すべての値フロー木リンクが正しく、それぞれが値のコピーを表していることも必要である。ただし、これらのリンクは、ある区間セットの値が実際に別の区間セットに由来する場合であっても、区間セット同士のリンクが不要である点において、非最大となり得る。
【００４６】
追跡器
本明細書に開示の別のツールは、「追跡器」と称する。追跡器は、ワークロード下の実行ファイルを入力とし、一連の追跡イベントを出力する。追跡イベントの出力には通常、「ループ入り」、「変数読み出し」、または「関数呼び出し」等、プログラム内のデータフローに影響し得る命令の実行を記録している。
【００４７】
追跡イベントは、別のツール「要約器」により処理され、それぞれの実行統計と併せて関数、文、および変数を出力する実行要約を生成する。このような情報は、領域特化の利益を享受し得るアプリケーション内の「ホットスポット」を示す。
【００４８】
正確性が影響することとして、特定の関心活動が実行中に発生した場合、関連する追跡イベントが出力および／または記録され、あらゆる出力および／または記録追跡イベントが指定順で関心活動の発生に対応する。
【００４９】
不変検査器
別のツール「不変検査器」は、所与の実行の追跡イベントを用いることにより、識別された不変値の違反（たとえば、不変探索器により識別）が当該実行において発生しているか判定する（あるいは、開発者は、観察すべき重要な変数を示すことによって、不変検査器に指示を出すことができる）。理想としては、多くのワークロードにわたるＤＢＭＳ実行ファイルの多くの実行に関して、不変検査器が違反を見つけることはない（これにより、不変探索器が見つけた不変値が正しいものと確認する）。
【００５０】
不変検査器は、周期的な動作によって、（不変探索器および追跡器等の）他のツールによる解析をさらに検証するようにしてもよい。アプリケーションのユーザは、たとえば不変検査器を動作させ、違反が見つからなかった旨を示されるようになっていてもよい。一方、違反が見つかった場合、ユーザには、違反が見つかった旨が示され、さらに、テクニカルサポートに問い合わせて支援を仰ぐメッセージが与えられるようになっていてもよい。
【００５１】
不変検査器には、たとえば本明細書に記載のツールの開発者により採用され、静的解析（たとえば、不変探索器により識別された不変値）の正確性を保証するデバッグツールとしての別の用途がある。
【００５２】
プログラム相互作用推定器
ツール「プログラム相互作用推定器」は、ＰＲ（または、ソースコード、ＩＲコード、あるいはアセンブリもしくはマシンコード等の同等表現）およびエコシステム仕様を用いて、関連情報と併せたデータファイルのリストであるプログラム相互作用を推定する。基本的に、プログラム相互作用推定器は、プログラム中で値がファイルに格納される場所、値が後でファイルから読み出される場所、およびこれらの値がファイルから除去される（または、ファイル自体が除去される）場所を確定する。そして、これらの値は、ドメインアサーション誘導器内の長期不変値として決定されることになる。
【００５３】
エコシステム仕様は、（ａ）関与するデータ、（ｂ）固定されるデータファイルと変動し得るデータファイル、（ｃ）このデータを作成、アクセス、および破棄可能なプログラム、ならびに（ｄ）任意の並行処理要件を記述している。本開示においては、ファイルに焦点を当てているが、一般的に、この仕様は、外界からの読み出しおよび書き込みデータとより一般的に関係しており、ファイルが挙げられるものの、ユーザＩ／Ｏ、他のプロセスへのストリーム／他のプロセスからのストリーム、ならびにメモリ割り当ておよび文字符号化の処理等、プログラムによるデータおよびＯ／Ｓとの他の相互作用のための考え得る他の方法も挙げられる。ファイルが最も一般的な方法であり、本説明の中心であるが、本発明は、その他任意の上記のようなデータ形式も利用可能であることが了解されるものとする。
【００５４】
テーブルＳｐｉｆｆ使用事例
本明細書において提供するツールの説明の補助として、原型的ＤＢＭＳ（「ｍｉｎｉｄｂ」）との関連でいくつかの例を記載する。ｍｉｎｉｄｂ．ｈおよびｍｉｎｉｄｂ．ｃソースファイルからの抜粋をＥｘａｍｐｌｅ６に示すが、これは、繰り返し参照することになる。
2018510445.tif 000008
2018510445.tif 000009
2018510445.tif 000010
2018510445.tif 000011
2018510445.tif 000012
【００５５】
アプリケーションにおけるデータフロー操作に関する特定の関数の非自明な特徴を記述する設定ファイルとして開発者が提供可能なエコシステム仕様（例示的なエコシステム仕様を以下のＥｘａｍｐｌｅ７に示す）は、（ａ）データが空になり始め、ワークロードが標準入力またはファイルから読み込まれること、（ｂ）（ワークロード）データが変動し得ること、（ｃ）ｍｉｎｉｄｂだけがデータにアクセスすること、および（ｄ）任意特定のディレクトリ上で動作するのは多くても１つのｍｉｎｉｄｂインスタンスであることを記述することになる。エコシステム仕様は、スキーマがｍｉｎｉｄｂの実行の全体で不変であることを理解するのに必須である。
2018510445.tif 000013
2018510445.tif 000014
【００５６】
ｍｉｎｉｄｂは、テーブルの行を保持するファイルであるテーブルと、ＳＱＬ文を含むファイルであるワークロードという２種類のデータを使用する。種類の名称は、以下の説明においてこれらのファイルを区別するためだけのものである。各テーブルは、ディレクトリ（データベース）に存在する。
【００５７】
このエコシステムには、ｍｉｎｉｄｂという１つのプログラムが存在する。このプログラムは、テーブルデータファイルを作成する。この動作を実行するコードの行（たとえば、CreateTable関数の行３）を与えることにより、操作されているファイル（ここでは、コードの当該行に記述された特定ファイル）をドメインアサーション推定器に伝える。実施例にも用いられているＣｏｎｓｏｌａｓフォントは、ｍｉｎｉｄｂソースコードにおける関数の名称である。動詞「reads」は、アプリケーションによってディレクトリが作成されても除去されてもいないことを示す。テーブルデータファイルの場合、当該ファイルは、CreateTable()に受け渡されたファイルによって示される。動詞「creates」もまた、「opens」、「reads」、「writes」、および「removes」を示唆している（ドメインアサーション推定器は、各テーブルがデータベースディレクトリに存在することを見つけ出し得る場合があるため、inDirectory属性およびおそらくはディレクトリ要素全体が不要となる可能性があり、エコシステム仕様が１行だけ短くなる）。
【００５８】
このプログラムは、ワークロードデータファイルを開くが、これは「reads」を示唆する。ここで、ファイルは、GetNextCommand()に受け渡されたものである。あるいは、このファイルは、GetNextCommand()の行７において標準入力から読み出される可能性がある。ｍｉｎｉｄｂの複数の並列インスタンス化では、同じワークロードファイルを読み出す可能性があるものの、内部のデータベースディレクトリまたはテーブルファイルにアクセスしたりこれらを変更したりすることはない。
【００５９】
ＰＲから抽出されたプログラム相互作用（Ｅｘａｍｐｌｅ８参照）は、ｍｉｎｉｄｂがこのディレクトリでテーブルファイルを作成し、これらを読み書きした後、除去することを記述しており、ソースにおいてこれらのファイル動作がそれぞれ起こる場所を厳密に示している。さらに、ファイル内のテーブルヘッダは、ファイル内で決して変更されず、当該ファイルは、変数「data_file_name」によって一意に識別される。
2018510445.tif 000015
2018510445.tif 000016
【００６０】
テーブルデータファイルは、データベースディレクトリにおいて最初に作成される（この例では、ｍｉｎｉｄｂという１つのアプリケーションだけを使用しているため、データに対する追加、除去等の動作よりも、データファイルにおいてこれを指定可能である）。このファイルには、TableHeaderおよびそれぞれが行（文字列）を伴う複数の「RowHeaders」という３つのデータ構造を含む。後続のツールにおける解析では、包含構造を把握する必要はなく、書き込まれた後に読み出されるデータ構造のみが必要となる。当然のことながら、データは、ファイルに書き込まれると、消去される前に、おそらくは何回も読み出し可能である。
【００６１】
ファイルの寿命は、アプリケーションの個々の実行を超えて延びる。ある実行によってファイルが作成された後、別の実行によって当該ファイルにデータが書き込まれ、その後、別の実行によって当該データが読み出された後、別の実行によってファイルが除去される可能性がある。重要なセマンティクスとして、ファイルに書き込まれたデータは、後で当該ファイルから読み出されるデータと同じであり、その後、当該データがファイルから消去されるか、またはファイル自体が除去される。その他の重要なセマンティクスとして、ファイルに書き出された後に読み込まれる実際のＣ構造体がＰＲによって把握されている。
【００６２】
原型的ＤＢＭＳの詳細（すなわち、ｍｉｎｉｄｂ）に戻って、興味深いことに、消去は、実際にはファイル書き込みである。行の上書きが起こって、元の行の消去が有効となる。
【００６３】
ExecuteDelete()のロジックは特に複雑であり、一時ファイルが作成され、消去対象の行の前のタイル行が一時ファイルにコピーされ、消去対象の行の後の行がコピーされた後、一時ファイルの名称が変更される。プログラム相互作用推定器は、このようなロジックを含むことにより、これらの詳細を取り扱うようになっていてもよい。
【００６４】
テーブルＳｐｉｆｆインスタンス使用事例
テーブルＳｐｉｆｆインスタンスは、データベースの特定行と関連付けられており、その取り扱いは上述の通りである。
【００６５】
行Ｓｐｉｆｆ
「行」の概念は、かなりドメイン固有と考えられる。ただし、一般的な概念は、全体として読み出し、書き込み、および処理が行われるデータファイルの一部の概念である。また、各行におけるクエリ評価ループの概念も存在するが、これは、入力ファイルの各帰属部の処理に用いられるコードの部分としても一般化可能である。このように行Ｓｐｉｆｆを認識するには、入力ファイルの一部が処理されたタイミングを認識する必要があり、それぞれ同じ構造を有する異なる部分にも同じコードが繰り返し用いられる。
【００６６】
行Ｓｐｉｆｆの実装には、（i）データの分割に利用する不変値の決定、（ii）データにおけるＳｐｉｆｆＩＤの配置、および（iii）おそらくはＳｐｉｆｆＩＤにより決定可能なデータ値の除去が必要である。第１のステップでは、ワークロードに依拠したコストモデルを使用する。第２のステップでは、入力データの構造を実際に変更するため、エコシステムの各関連プログラム（データの当該部分の読み出しまたは書き込みを行う）を変更する必要がある。第３の課題についても同様に取り扱われることになる。
【００６７】
したがって、行Ｓｐｉｆｆの概念の固有観点は、（ａ）ユニットにおいて処理されるデータの部分を識別することおよび（ｂ）このデータにアクセスするプログラムにおいてより効率的に操作可能となるようにデータを変更することである。
【００６８】
クエリＳｐｉｆｆ使用事例
クエリＳｐｉｆｆは、クエリ、テーブル、および行不変値の組み合わせである。後者２つは上記で解決しているが、クエリ不変値は不変探索器が見つける。この場合、クエリ不変値は、ｍｉｎｉｄｂ実行全体では持続しない。クエリが由来するワークロードは、読み出されるだけであり、（たとえば、parallelAccessが可能なことから）複数のｍｉｎｉｄｂ具体化によって使用することも可能なためである。
【００６９】
プログラム相互作用推定器の例示的なアルゴリズム
図１に示すように、プログラム相互作用推定器には、エコシステム仕様およびＰＲという２つの入力がある。エコシステム仕様がデータを読み出して操作するプログラムに焦点を当てている一方、生成されたプログラム相互作用は、ファイルになされること、特に、プログラム内のデータ構造がファイルに対して書き込みおよび読み出しされる場所に焦点を当てている。このため、プログラム相互作用推定器すなわちＰＩＤは、ファイル操作システム呼び出し、特に、fopen()、fwrite()、およびremove()を解析する。また、その開始点として、エコシステム仕様により指定された<datafile>および<workload>を使用するが、この場合は、（たとえば、Ｅｘａｍｐｌｅ６に示すように）テーブルおよびワークロードを使用する（なお、ＰＩＤは、データベースも解析するが、これがOpenTable()により読み出されただけのディレクトリに過ぎないことをかなり迅速に見出す）。
【００７０】
これらのファイル操作呼び出し間において、ＰＩＤは、FILE*値のフローを観察する。
【００７１】
ワークロードファイルは、特に解析が容易である。エコシステム仕様は、このファイルがGetNextCommand():13で開かれる旨を規定する（ファイルは、標準入力から読み出すことも可能である）。ＰＩＤは、仕様が参照するソースコードを解析することによって、以下を決定する。
ファイルがquery_file_nameによって命名されていること、
ＦＩＬＥquery_fileおよびstdinと関連付けられていること、
このファイルの読み出しがGetNextCommand():8およびGetNextCommand():18で読み出された文字列だけであること。
【００７２】
したがって、プログラム相互作用推定器は、Ｅｘａｍｐｌｅ７に示すように、この決定された情報をプログラム相互作用ファイルに出力する。
【００７３】
テーブルファイルは、より複雑な挙動となる。エコシステム仕様は、参照ソースコードを解析することによって推定されたデータ構造TableHeader.table_fileに由来するdata_file_nameに従う必要があることを示すcreates="CreateTable():3”を記述している。このため、ＰＩＤは、
main():case'C'からCreateTable():2(fopen())への後
数行を経てWriteTableHeader():3(fwrite())を呼び出し
main()の後、（ケース「I」:fwrite()でWriteRow():3および6において）書き込まれた多くの行に戻り
（ケース「D」:fwrite()なし（これは検出が困難となる）でExecuteDelete():25において）消去された行、および、
参照ソースコードを調べることによって、main():57:remove()内で再び消去されたファイルが最終的に後続するフローとなり得る。
【００７４】
Ｃファイルtable_header.table_fileと関連付けられたテーブルdatafileに関するこの一連の全体動作から、ＰＩＤは、
TableHeaderデータ構造がWriteTableHeader():3でテーブルファイルに書き込まれた後、
0penTable():8で読み出される、
ことを推定することができる。
【００７５】
興味深いことに、これがTableHeaderで行われるすべてであり、一度だけ書き込まれてファイルから決して消去されない。
【００７６】
また、ＰＩＤは、RowHeaderデータ構造が、
WriteRow():3でテーブルファイルに追加された後、
SequentialScan():7で読み出され、
ExecuteDelete():25でファイルから除去される、
ことを決定可能である。
【００７７】
最終的に、ＰＩＤは、文字列が、
WriteRow():6でテーブルファイルに追加され、
SequentialScanO:15で読み出され、
ExecuteDeleteQ:15でファイルから除去される
ことを決定可能である。
【００７８】
このように、ＰＩＤが実行する解析では、ＦＩＬＥ型の変数の値に従って、以下を観察することにより、エコシステム仕様において識別された各ファイルを各プログラムが操作する様子を解析する：
１．ファイル名の由来する場所（また、プログラム内の変数）、
２．ファイルが開かれる場所、
３．そこからプログラム中でファイル値のフローが発生する場所、
４．ひいては、（i）書き込まれた後、（ii）ファイルから読み出され、その後、（iii）ファイルから消去されるデータ構造、および、
５．最終的に、当該ファイルが消去または閉じられる場所。
【００７９】
この解析は、全体が単一プログラムの単一実行の文脈内であることに留意するものとする。複数のプログラムが存在する場合は、それぞれが別個に解析される。各プログラムの実行が複数回の場合も多々あるが、この解析では、単一の実行だけを考慮する。
【００８０】
ＰＩＤ解析では、最初に：
ファイル変数を探索し、
このような値の値フローを計算し、
値フローに沿って、ファイル開閉、書き込み、および消去動作を識別し、
それぞれについて、プログラム相互作用に記録される特定の情報を識別する必要がある。
【００８１】
後述のドメインアサーション推定器は、ＰＩＤにより抽出された実行前挙動を取得して結合することにより、プログラムからファイルへのデータフローおよびその後のプログラム（おそらくは、後続の実行）に戻るデータフローの様子を全体的に理解することによって、従来のコンパイラ解析でできなかったプログラム実行全体の不変値フローを演算する。
【００８２】
ドメインアサーション推定器
ドメインアサーション推定器ツールは、ＰＲ、識別された不変値、およびプログラム相互作用を使用して、ドメインアサーションを推定する。テーブルＳｐｉｆｆの場合、プログラム相互作用は、不変となるスキーマ情報を示唆している。テーブルＳｐｉｆｆインスタンスの場合、プログラム相互作用は、プログラム中で行が作成、アクセス、更新、および消去される場所を理解するのに必須である。クエリＳｐｉｆｆは、従来のコンパイラ最適化技術の範囲内のより小さな範囲の不変値と併せて、スキーマ、行、およびワークロード生成不変値を利用可能である。ドメイン固有知識の指定では、これらの演算の一部を少し詳しく記述する。そして、ドメインアサーション推定器は、ファイルに対する読み出しおよび書き込みがなされた値に従って、おそらくはプログラムの複数の起動にわたり、不変区間を結合することにより、値の完全な寿命を導出した後、ドメインアサーションにて符号化する。ワークロードが完全である場合すなわちいくつかのバッチアプリケーションに当てはまり得るデータに対する可能な動作を完全に特性化している場合、ドメインアサーション推定器（ＤＡＤ）は、不変値の制限された一組の考え得る値を推定することもできる。この情報（ドメインアサーションおよびおそらくは一組の考え得る不変値）こそ、従来のコンパイラが有していないものである。
【００８３】
領域特化の重要な観点は、コンパイラが一般的に利用できない情報を利用することである。この情報は、（i）ドメイン固有知識および（ii）予備ソース知識という２つの形態である。両種の知識は、単一プログラムのソースコードを見るだけでコンパイラが発見または結論可能なものを超えていく。領域特化は、読み出しまたは操作を行うデータ、呼び出すプログラム、このデータの読み出しまたは操作も行う他のプログラム、関与するオペレーティングシステム、ネットワークルータ、およびストレージシステムといった特化対象のプログラムのはるかに広いエコシステムを考慮に入れる。このエコシステムは、特化対象のプログラム（および、そのデータ）の効率を向上させるために領域特化で利用可能な多くの情報を提供する。
【００８４】
やや包括的な予備ソース情報と比較して、ドメイン固有知識は、特定のドメインのプログラムにのみ当てはまる。ドメイン固有知識の一例として、「テーブルのスキーマのあらゆる変更が直列化可能となる」。直列化可能性は、データベース領域から生じた複雑な概念であるが、他の並列分散情報処理用途にも拡がっている。このような知識によれば、テーブルＳｐｉｆｆが作成されるべき場所および破壊されるべき場所を厳密に示すことを含めて、ＤＢＭＳを高速化するテーブルＳｐｉｆｆを作成可能である。
【００８５】
ドメイン固有知識の第２の形態は、プログラムのワークロードの形態である。一例として、「ＯＬＡＰ（オンライン解析処理）アプリケーションは、データ変動をほとんど示さず、（複雑な）クエリが日中に支配的となることが多く、更新は低頻度で通常は夜間である」。このような情報は、「この活動は他の活動よりも頻度が高い」という形態であるため、領域特化の指示を出すことにより、現時点ではワークを代償とした情報に基づくより良い決定が可能であって、後で何らかの高速化を行うことになる。
【００８６】
予備ソース知識の一例は、唯一のプログラムにより書き込みおよび読み出しがなされたファイルの特定部分であり、これは、当該部分を修正するコードまたはファイルを消去するコードが実行されるまで残留することになる。このような知識によれば、入力ファイルを繰り返し処理する任意のプログラムを高速化するＳｐｉｆｆを作成可能である。
【００８７】
ドメイン固有知識および予備ソース知識は、このような知識を形式的に記述するドメインアサーションおよび予備ソースアサーションを含むファイルをＳｐｉｆｆ探索器が読み出せるように形式化されているのが好ましい。そして、Ｓｐｉｆｆ探索器は、ＤＢＭＳソースコード（または、より一般的に、ドメイン仕様により記述されたドメインの任意のプログラムのソースコード）を含むファイルを読み出すとともに、Ｓｐｉｆｆ構成器で使用するＳｐｉｆｆ不変値を出力する。
【００８８】
テーブルＳｐｉｆｆ使用事例
プログラム相互作用からの情報をmain():table_header.num_columns上の不変区間と結合することにより、以下のＥｘａｍｐｌｅ９に示すドメインアサーションの生成にＤＡＤが必要とする情報が得られる。
2018510445.tif 000017
【００８９】
なお、ExecuteDelete():38は含まない。解析によって、それが名称変更であることが分かっているためである。
【００９０】
テーブルＳｐｉｆｆインスタンス使用事例
データベースのテーブル行は、テーブルごとに複数の行が存在する一方でスキーマは１つしか存在しない点において、スキーマと異なる。上記においては、テーブルと関連付けられたファイルに格納されたtable_header.num_columnsという１つの値が存在するが、この値は、最初にファイルに書き出された後、読み戻される。プログラム相互作用によれば、このことに加えて、row_dataというさまざまな異なる値が同じファイルに書き込まれることが分かる。
【００９１】
行は、データファイル中の存在場所すなわちファイル位置（行の第１のバイトのオフセット）によって見分けられる。
【００９２】
Ｅｘａｍｐｌｅ１０に示すように、ＤＡＤにより生成されたドメインアサーションは、読み出しまたは書き込み対象の指定ファイル内のプログラムの実行における現在位置が特定の値である場合にのみ関数依存性が有効となることを示す関数依存性の左側のキーワードOFFSETによって行を区別する。
2018510445.tif 000018
2018510445.tif 000019
【００９３】
直観的に、読み出しが発生する位置にデータが存在する一方、当該データは、セグメント開始により記述される当該位置に早く書き込まれたデータと同じである。ＤＡＤによれば、プログラム中の変数の複数の値は、同じファイルに書き込まれた後、OFFSETを用いてこれらの値を区別することが分かっている。なお、セグメント終了文のうちの１つには、OFFSETを含まないため、ファイルの消去時にファイル全体のすべての行不変値が終了となる。
【００９４】
ＤＡＤによれば、ケース「D」（ｓｗｉｔｃｈ／ｃａｓｅ文を用いたｍｉｎｉｄｂの実装において解釈されるｍｉｎｉｄｂコマンド）がファイル内のOFFSET間でデータパケットを移動させることも分かり得る。当業者であれば、このような移動への対応には、ドメインアサーションの形式を拡張しさえすればよいことが容易に理解されよう。
【００９５】
OFFSET以外に、行不変値は、テーブルのスキーマ不変値と同じ構造を有する。
【００９６】
さらに、アプリケーションに対して書き出しまたは読み込みされた各ファイルは、データパケットで構成されると考えられ、それぞれ、ユニットとして書き込みおよび読み出しがなされるプログラムのローカル変数における外部形式の値である。このため、ｍｉｎｉｄｂ．ｃは、ファイルにまずスキーマデータパケット（table_header.num_columnsの値を含む）を配置した後、一連の行データパケット（row_valuesの値を含む）を配置する。
【００９７】
クエリＳｐｉｆｆ使用事例（実施例１１）
２つの場合が存在する。第１は、ワークロード（すなわち、クエリ）が標準入力に由来する場合であり、この場合はドメインアサーションが推定不可能である。ユーザが何でも入力可能なためである（当然のことながら、依然としてＶＦＴを用いることにより、（多くの）不変値がクエリ中に活動的であることを判定可能であるものの、これは、先のステップにおいて不変探索器により実行済みである）。第２は、ワークロードがファイルすなわち起動引数において命名されたファイルに由来する場合であり、この場合は、OFFSETを処理する点において、ドメインアサーションが本質的に行不変値と同じである。この第２の場合は、ファイル名を用いることにより、実際のファイルをワークロードソースとして示す。これら２つの場合は、エコシステム仕様によって区別されるが、第２の場合には、特定のワークロードファイルの指定も可能であることが記述される。これに対して、ワークロードファイルの作成者は把握されていなくてもよく、このような場合は、当該ワークロードのクエリＳｐｉｆｆを作成できない。
2018510445.tif 000020
【００９８】
第２の場合は、ワークロード上の特化に用いられるようになっていてもよい。そして、クエリＳｐｉｆｆＩＤは、ワークロードに挿入されてもよいし、どこか他の場所に格納された関連付けとして配置されてもよく、当該ワークロードが実行された場合に用いられるようになっていてもよい。
【００９９】
以下では、クエリが読み込みまで把握されない第１の場合のみを考える。
【０１００】
なお、クエリ中に有効な不変値のみを含むクエリＳｐｉｆｆは、積極最適化コンパイラによって発見可能であるものとする。ただし、より重要なこととして、クエリＳｐｉｆｆは、このようなクエリ不変値をコンパイラが発見不可能なスキーマおよび行不変値と組み合わせる。このようなスキーマおよび行不変値には、ファイル読み書きのセマンティクスに関する知識を要するためである。クエリＳｐｉｆｆが真のＳｐｉｆｆとなるのは、このような観点である。
【０１０１】
ドメインアサーション推定器の例示的なアルゴリズム
追跡分割要素は、データファイルまたはデータファイルの構成要素（ここでは、テーブルヘッダおよび行）が作成、挿入、または消去されるプログラム相互作用に由来する。ドメインアサーション内の依存性は、ディレクトリおよびファイル名ならびに任意選択としてファイル内のOFFSETに由来する。不変値がこれらをつなぎ合わせるため、アプリケーション内の変数の値は、アプリケーションコードからファイルに流れ出た後、アプリケーションに戻るように見られることで、候補スニペットおよび最終Ｓｐｉｆｆを決定可能な長寿命不変値を確定することができる。
【０１０２】
ドメインアサーションにおいてtable_header.num_columnsが特性化されたテーブルＳｐｉｆｆ使用事例の場合、ＤＡＤは、以下を判定可能である：
main():ケース「C」がCreateTable()を呼び出すこと
これがWriteTableHeader()を呼び出すこと
これがテーブルヘッダをファイルに書き込むこと。
【０１０３】
テーブルヘッダは：
上記およびその後のプログラム起動によって読み出されるが、
これは、main():57でファイルが消去されるまでである。
【０１０４】
これは、テーブル<datafile>中のテーブルヘッダが一度だけ書き込まれプログラムにより決して修正されないことを示唆する。これを把握することにより、ＤＡＤは、適当な追跡分割要素を生成可能であり、テーブル<datafile>の追跡分割要素は作成および消去される。また、ＤＡＤは、table_header.num_columnsに関する依存性も作成可能である。
【０１０５】
テーブルＳｐｉｆｆインスタンス使用事例の場合、関連するデータパケットは、テーブル<datafile>に追加され、おそらくは当該ファイルから消去され、最終的にファイル自体が消去された場合に除去されるrow_dataおよびrow_valuesである。ＤＡＤは、ファイルが作成されると、プログラムがrow_dataの複数の値をファイルに格納することにより、それが存在するOFFSETによってこのような各パケットを識別可能である旨を判定する。
【０１０６】
上記観察は、ＤＡＤのアルゴリズムを提供する。プログラムにより作成または開かれた各FILEの場合、ＤＡＤは、ＶＦＴによって、当該ファイルが最初に作成された場所および当該ファイルの名称が由来する場所を見つけ出す。そして、当該ファイルに格納された各データ構造（これらは、プログラム相互作用における<data>要素である）について、ＤＡＤは、当該データ構造に対して実行されるファイル操作（データ構造のファイルへの追加、おそらくはデータ構造の変更または除去、および最終的なファイルの消去）を確定する。そして、これらの操作は、適当な追跡分割要素を示唆する。最終的には、これらの操作で用いられるプログラムデータ構造（ファイルに書き込まれたＣまたはＣ＋＋プログラムデータ構造）から、ＤＡＤは、ＶＦＴを検査して、このようなプログラムデータ構造中の値が由来する場所を決定することにより、依存性を示唆することができる。また、ＤＡＤは、プログラムを流れる際の各FILE変数に対する実行を追跡することによって、ファイルが含むデータパケットが（num_columnsの場合のように）１つだけか（row_dataの場合のように）複数かを判定するが、これはＶＦＴによっても判定可能である。複数のパケットには、ドメイン追跡分割および依存性におけるOFFSETが必要である。
【０１０７】
正確性
正確性が影響することとして、生成されたドメインアサーションは完全であり、入力ＰＲ、不変値、およびプログラム相互作用と一致する。
【０１０８】
スニペット探索器
図１に示すように、別のツール「スニペット探索器」は、以下を入力とする：
１つまたは複数の不変値
ＰＲ
１つまたは複数の実行要約
ドメインアサーションのプログラム相互作用、および、
コストモデル
【０１０９】
スニペット探索器は、１つまたは複数の<spiff>要素を出力するが、それぞれが１つまたは複数の候補スニペットを含んでおり、各候補スニペットが以下を含む：
ＰＥにより識別されたコードの区間
一組の不変値
各不変値の考え得る一組の値
各不変値の値が最初にファイルに書き込まれたソース位置、
当該値がファイルから除去されたソース位置、
値が時間ごとに読み出されるソース位置、
候補スニペットの適当な寿命すなわち関連Ｓｐｉｆｆを作成可能なタイミング（コンパイル時であれ実行時であれ）、および、
任意選択として、区間内で採用される推奨最適化。
【０１１０】
各ドメインアサーションは、単一のプログラム実行内の範囲を有する不変値に記録された区間に対して、たった１つのプログラム実行よりもほぼ確実に広い区間を示唆する。
【０１１１】
スニペット探索器は、ドメインアサーションを用いて、不変値の範囲を広げるとともに、各不変値の考え得る一組の値を改良する。各不変値の区間は、候補スニペットの区間と（一部または全体が）重なる。さらに、各候補スニペットの区間は、コストモデルによる調整によって、実行要約およびＳｐｉｆｆ呼び出しコストから引き出される最適化されたスニペットの実行コストとスニペット評価回数との積として計算される節約を最大化しつつ、区間のサイズを最小限に抑える。このため、スニペット探索器は、Ｓｐｉｆｆ構成器が実行する考え得る最適化およびこのような各最適化の利益（後者はコストモデルによる）との考えを有する必要がある。
【０１１２】
クエリＳｐｉｆｆ使用事例（実施例１２）
先に考察したクエリＳｐｉｆｆとテーブルＳｐｉｆｆとの間には、２つの大きな相違点がある。第１はこのステップで取り扱うが、スニペット探索器は、ドメインアサーション以外からの不変値を使用する。クエリが通例は存続しないためである（ただし、標準入力に与えられたワークロードに関する上記説明を参照）。第２は後で取り扱うが、Ｓｐｉｆｆ構成器は、実行時のＳｐｉｆｆコードのコンパイルとＳｐｉｆｆインスタンスのインスタンス化との間の境界の場所に関して、エコシステム仕様からの明示的な指示を必要とする。
【０１１３】
スニペット探索器は、以下を推定する：
SequentialScan():40（データパケットをrow_values[]に解凍した直後）からSequentialScan():59（方法の最後）までのコードの区間、
一組の不変値main().query、特に、テーブルＳｐｉｆｆ使用事例によるstdinおよびquery.schemaから読み出されたquery.executor_routine,query.executor_command、query.num_predicates,query.predicate_list、およびpredicates[]、
各不変値の考え得る一組の値（この場合、query.executor_routineは常にSequentialScan()、query.executor_commandは常にSCAN_FWDであり、各述語について、column_idは（BuildPredicates()の当該領域への割り当てから推定される）stdinから読み出された任意のintであり、constant_operandはstdinから読み出されたunsigned longであり、operator_functionは&EqualInt4または&LessThanInt8である）、
各不変値の値が最初に決定されたソース位置（クエリの値は、main():32すなわちBuildAndPlanQuery()の呼び出し直後に決定）。
クエリの値は、決してファイルに対する書き込みも除去も読み出しも行われない、
候補スニペットの適当な寿命（寿命はちょうど「S」スイッチ内であり、エコシステム仕様によれば、コンパイラを呼び出し不可能であることが分かるため、SequentialScan()としてのexecutor_routine、SCAN_FWDとしてのexecutor_command、１〜６のnum_predicatesについてはＳｐｉｆｆの予備コンパイルのみを行い、このような各述語について、operator_functionが&EqualInt4または&LessThanInt8である）、
schema->num_columnsの値により終端するSequentialScan():47でのｆｏｒループの展開。
2018510445.tif 000021
2018510445.tif 000022
【０１１４】
fromValueおよびtoValueの決定方法は不明確であるものの、生成されたコンパイル時クエリＳｐｉｆｆの数の境界を示すことと考えられる。
【０１１５】
スニペット探索器の例示的なアルゴリズム
スニペット探索器はまず、ファイルから読み出される変数およびこれらの値がファイルに挿入される場所を追跡することによって、不変値をプログラム実行全体に広げる。個の結果、複数の実行にまたがる不変区間が得られる。また、このツールでは、値が最初にファイルに書き込まれたタイミングおよび消去されるタイミングも追跡する必要がある。
【０１１６】
スニペット探索器のその他の課題は、コストモデルを用いてスニペットの境界を示すことである。そのため、このツールでは、Ｓｐｉｆｆ構成器がもたらし得る最適化および各最適化が実現可能となる条件を把握する必要がある。
【０１１７】
正確性
このツールの正確性が影響することとして、このツールにより生成された候補スニペットはそれぞれ、入力不変値、ＰＲ、実行要約、ドメインアサーション、プログラム相互作用、およびコストモデルと一致する。指定不変値は実際にスニペット上で不変であるものとし、推奨最適化はこれらの不変値およびＰＲにおけるそれぞれの操作と一致するものとし、考え得る値が実際に可能であるものとする。
【０１１８】
必須ではない望ましいこととして：
コストモデルを前提として、返されたスニペットが最も望ましい、
コストモデルにより、大型化がコスト増につながる点において、スニペットが最大である、
コストモデルにより、小型化がコスト増につながる点において、スニペットが最小である、
コストモデルを前提として、推奨最適化が有用となる。
【０１１９】
Ｓｐｉｆｆ構成器
図１に示すように、別のツール「Ｓｐｉｆｆ構成器」は、１つまたは複数の候補スニペットおよびＰＲを入力とし、特化ソースコードを出力として生成する。
【０１２０】
具体的に、各入力候補スニペットについて、Ｓｐｉｆｆ構成器は、以下のタスクを実行するものとする：
１．すべてのパターンパラメータおよびＳｐｉｆｆパターン関数を規定するＳｐｉｆｆパターンの．ｈファイルを作成する。
２．Ｓｐｉｆｆ実装宣言の．ｈファイルを作成する。
３．Ｓｐｉｆｆ実装定義の．ｃファイルを作成する。
４．コードを適当な場所に挿入することによって、（動的Ｓｐｉｆｆの）Ｓｐｉｆｆを作成し、Ｓｐｉｆｆを呼び出し、（ここでも動的Ｓｐｉｆｆの）Ｓｐｉｆｆを破壊する。
【０１２１】
各使用事例は、ｍｉｎｉｄｂの指定分岐と関連付けられており、正確性が確保される。各分岐には、当該構成を生成する候補スニペットを含む。
【０１２２】
実際の変換には、ＰＲ−ＰＲ変換として、ＴＸＬを使用するのが有益と考えられ、変換されたＰＥはその後、変換されてテキストソースコードに戻ることでＳｐｉｆｆを作成する。ＴＸＬにはパーザを含むが、ＰＥを直接取得し得る場合もある。また、ＴＸＬには、当該ＰＥと協働し得る構文木アンパーザも含む。
【０１２３】
Ｓｐｉｆｆ構成器が上述の通り機能するには、ドメイン知識に基づく何らかの指示が必要となる場合がある。具体的に、Ｓｐｉｆｆ構成器は、以下の付与／識別が必要となる場合がある：
生成対象のすべての静的実装の仕様（すなわち、特化する変数およびその場合の値）。
２つ以上の静的実装が当てはまる場合の曖昧性除去のルール
動的実装の作成のルール（とにかく許可されているか？、キャッシングされているか？、その場合はどのように？、メモリか？、ディスク上か？、キャッシュのサイズおよび管理ルールは？、生成された動的実装は完全に特化すべきか、または、一部のみを特化して、一部のパラメータを一般のままとするのが良いか？、必要に応じてオンザフライで動的実装をコンパイルすることが受け入れられるか、または、キャッシュにある場合にのみ動的実装を使用することが受け入れられるか？、これらの質問に対する答えが変化するか？
完全に一般の実装が作成されるべきか（そして、フォールバックとして使用されるべきか）？、あるいは、何らかの方法で一部の変数が常に特化されるか（これにより、データブロック中での表現が必要となる変数が決定されることになる）？
【０１２４】
一般的に、Ｓｐｉｆｆ構成器は、入力ファイルにおいて上記すべてが識別される。作成すべき静的実装の数、静的／動的のいずれとすべきか、特化する変数と特化しない変数等を見つけ出すのは、スニペット探索器の仕事である。作成すべき静的実装は１つだけとなり、当該単一の静的実装を常に呼び出すものとする。
【０１２５】
クエリＳｐｉｆｆ使用事例
Ｅｘａｍｐｌｅ１３を参照して、入力は以下の通りであり、スニペット探索器が指定するように、SCAN_FWDとしてのexecutor_command、１〜６のnum_predicatesについてコンパイル時クエリＳｐｉｆｆを示しており、このような各述語について、operator_functionが&EqualInt4または&LessThanInt8である。
2018510445.tif 000023
2018510445.tif 000024
【０１２６】
上述の通り、Ｓｐｉｆｆ構成器は、実行時のＳｐｉｆｆコードのコンパイルとＳｐｉｆｆインスタンスのインスタンス化との間の境界の場所に関して、エコシステム仕様からの明示的な指示を必要とする。このような境界指定がケース「S」、「I」、および「D」で起こり、これら３つのケースで呼び出されるいずれにおいてもＳｐｉｆｆがコンパイル不可能であることをエコシステム仕様が指定するものと仮定する（これは、ユーザが許容する遅延に関する知識を強調する。なお、特定の行に関して新たなＳｐｉｆｆをコンパイルするのは、全体として見れば、ワークロードの集まりを高速化するのに特に有益であるが、ユーザは依然として、コンパイルしないことを指定したいと考える。特定のワークロードは、領域特化によってそれ自体が高速動作する必要があるためである）。このため、Ｓｐｉｆｆ構成器は、エコシステム仕様を入力として含む。
【０１２７】
このように、Ｓｐｉｆｆ構成器は、SequentialScan()の一部についてＳｐｉｆｆを構成するが、query.executor_commandが常にSCAN_FWDであることから、コンパイル時にnum_columnsの各値に対して１つを構成する。各述語について、column_idは任意のintであり、constant_operandはstdinから読み出されたunsigned longであり、operator_functionは&EqualInt4または&LessThanInt8である（Ｓｐｉｆｆ０は、任意数のnum_columnsを取り扱い可能な非特化である）。関連する変換は、ループ展開および定数畳み込みである。Ｓｐｉｆｆ構成器は、num_predicates=2の場合、２３のＳｐｉｆｆＩＤに関してＳｐｉｆｆパターンを生成するが、以下の通り、第１がcolumn_id=2およびoperator_function=&EqualInt4、第２がcolumn_id=7およびoperator_function=&LessThanInt8である。なお、クエリＳｐｉｆｆＩＤの演算は通常、Ｓｐｉｆｆパターンパラメータの特定の値と関連付けられている。Ｓｐｉｆｆ構成器は、アプリケーション固有のＩＤ生成メカニズムを利用して、適正なＳｐｉｆｆＩＤを生成する。ただし、本実施例では、演算されたＳｐｉｆｆＩＤとして２３を仮定する。
【０１２８】
Ｓｐｉｆｆ構成器の例示的なアルゴリズム
Ｓｐｉｆｆ構成器は、不変値を示した後にコンパイラの最適化実行を許可するか、または、異なるコードの生成によって最適化を手動で実行するかの一方のみを決定する。
【０１２９】
そして、Ｓｐｉｆｆ構成器は、関連ＰＥ内のファイル名、行番号、および列数を用いた元のソースから特化ソースへのほぼ逐語的なコピーによって、生成されたファイルをつなぎ合わせる。このため、Ｓｐｉｆｆ構成器は、ごく限られた量の構文解析および構文構築を行う必要があり、その労力の大部分は、元のソースの適所から特化ソースの適所へのコードのコピーから成る。
【０１３０】
正確性
正確性が影響することとして、コードは、コンパイルおよび動作を行うが、セマンティクスにおいては、置き換えた元のコードと同一である一方、入力情報と一致する。
【０１３１】
以下の説明は、ＭｉｎｉＤＢテーブルＳｐｉｆｆおよびＭｉｎｉＤＢクエリＳｐｉｆｆの作成を実証する付加的な実施例を与えている。
【０１３２】
ＭｉｎｉＤＢテーブルＳｐｉｆｆ
以下の実施例では、Ｅｘａｍｐｌｅ４に示すSequentialScan()関数における不変値schema->num_columns==CONSTANTからのテーブルＳｐｉｆｆの作成を実証している。
【０１３３】
不変探索器
上記実施例において、不変探索器は、SequentialScan()::schema->num_columns変数に関して、以下の不変区間セットを識別するものとする：
不変区間セット＃１：行５２で始まり、１不変区間である：
不変区間＃１．１：行１１４で終わる
【０１３４】
また、不変探索器は、ＶＦＴを生成して、変数SequentialScan()::schema->num_columnsが値を得る場所を示すものとする：
SequentialScan()::schema->num_columnsは、ExecuteQuery()::query->schema->num_columnsから値を得る
ExecuteQuery()::query->schema->num_columnsは、main():query->schema->num_columnsから値を得る
main():query->schema->num_columnsは、main()::table_header->num_columnsから値を得る
main()::table_header->num_columnsは、OpenTable()のfread()から値を得る。
【０１３５】
このため、SequentialScan()::schema->num_columnsの値は最終的に、OpenTable()のfread()の呼び出しに由来する。
【０１３６】
不変検査器
不変検査器は、main()::table_header->num_columnsが一度だけ行６３４に割り当てられ、所与のワークロードの当該実行による特定の終端ノードを通してこの変数の値が決して変更されていないことを確認する。
【０１３７】
不変探索器の前にドメインアサーション推定器が実行されている場合、不変検査器は、実際の値が考え得る値に含まれている旨を確認することも可能である。これにより、当該解析を特定の値または変数に集中させることによって、不変探索器の範囲を抑えることも可能と考えられる。
【０１３８】
スニペット探索器
スニペット探索器は、コストモデルと併せた実行要約の解析によって、ケース「C」、「I」、および「D」がＳｐｉｆｆの作成には高価過ぎるものの、ケース「S」内の演算時間が当該ケースの特化の推奨には十分である旨を判定する。
【０１３９】
実行が固定回数またはある割合の回数未満であるＰＥ（または、他の同等な具現化）が特化されないことのみを記述する単純なコストモデルで開始するものとする。
【０１４０】
そして、このような場合、スニペット探索器は、ドメインアサーションによって、schema->num_columnsがSequentialScan()の全体で、データファイルの作成時から当該ファイルの除去までの範囲において不変であるため、ｍｉｎｉｄｂ．ｃ：５５３の直後に実行されるWriteTableHeader():3に列数が格納された場合に当該変数の値が最初にファイルに書き込まれたものと推定する。この値は、決してファイルから除去されていないものの、ファイル自体がmain():57で除去されている。これは、コンパイル時にＳｐｉｆｆを作成可能であることを示している。スニペットは、ExecuteTable():2θからExecuteTable():23を介して広がるものとする。これがnum_columns上で特化されたスニペットの範囲であり、num_columns上で特化可能な他の文を見て決定される（本質的に、num_columnsは使用頻度が低いため、この特化機会からは離れている）。ただし、別途の間接呼び出しは高価であるため、スニペット探索器は、行７にこの不変値の別の用途を有するExecuteQuery()の全体にこのスニペットを広げる。最後に、スニペット探索器は、この候補スニペットのループ展開を推奨するものとする。
【０１４１】
この場合、Ｓｐｉｆｆは、Ｅｘａｍｐｌｅ１４に示す<snippet>で示されるＳｐｉｆｆ関数を１つだけ有することになる。
2018510445.tif 000025
2018510445.tif 000026
【０１４２】
スニペット探索器は、ドメインアサーションによって、データパケットがmain()のケース「I」および「D」で作成され、ケース「P」および「D」で除去されるものと推定することも可能である。より具体的に、スニペット探索器は、以下を推定する：
SequentialScan():16（データパケットの読み込み直後）からSequentialScan():38（ループ用の解凍の最後）までのコードの区間、
一組の不変値（row_dataからの値および上記不変値解析によるスキーマ）、
各不変値の考え得る一組の値（この場合、num_columnsの値は３であり、第１列の値はハードコード化intおよびschemaであり、第１の列の型はint、第２の列の型はlong、第３の列の型はint、任意の文字のアレイである）、
各不変値が最初にファイルに書き込まれたソース位置（WriteRow():18およびWriteRow():25）、
当該値がファイルから除去されたソース位置（main():57およびExecuteDelete():25）、
値が時間ごとに読み出されるソース位置（main():SequentialScan():3）、
query.schema不変値を用いてテーブル規定時間に構築された候補スニペットの適当な寿命（挿入の可能性があるデータパケットを含むことから、Ｓｐｉｆｆが実行時にインスタンス化された場合はrow_valuesが与えられ、数クエリが動作した後、データパケットが除去されるため、高速である必要がある。また、row_valuesの可能性の数が非常に大きいためである）、
schema->num_columnsの値で終端するとともにrow_dataおよびshcema値を使用する場合のSequentialScan():16でのｆｏｒループの展開。
【０１４３】
なお、Ｅｘａｍｐｌｅ１５に示すように、解析では、より広い範囲のテーブル不変値をより狭い範囲の行不変値と組み合わせるとともに、それぞれについて異なる方法を採用する。テーブルＳｐｉｆｆが規定された場合に前者がコードを生成可能である一方、後者は、row_valuesアレイの値を与えることによる実行時のＳｐｉｆｆのインスタンス化を伴う。ＤＢＭＳの領域特化において、スキーマ不変値は、連続的に狭い範囲の不変値を含むテーブルＳｐｉｆｆインスタンスおよびクエリＳｐｉｆｆにおいて大きな役割を果たすことになる。
2018510445.tif 000027
【０１４４】
Ｓｐｉｆｆ構成器
これは、インスタンスが存在しないため、最も簡単な使用事例である。この事例について、４つの変形例を詳しく調べる。
【０１４５】
変形例１：単一の静的実装：
Ｅｘａｍｐｌｅ１６に示す静的なＳｐｉｆｆ実装となるｍｉｎｉｄｂの単一不変値に対応する以下の入力候補スニペットを考える。
2018510445.tif 000028
createAt="compileTime"は、このＳｐｉｆｆが静的実装を有すべきことを記述したものである。
valueRead="OpenTable():8"は、変数が外界から読み出される場所を記述しているため、Ｓｐｉｆｆが選択される可能性がある場所を示している。
existsFrom="WriteTableHeader():3"は、変数が外界に書き出される場所を記述しているため、動的Ｓｐｉｆｆが作成される可能性がある場所を示している。静的Ｓｐｉｆｆの場合は、安全に無視することができる。
existsTo="main():57"は、「外界」がファイルである場合に、ファイルが消去／除去される場所を記述しているため、動的Ｓｐｉｆｆのガベージコレクションが行われる可能性がある場所を示している。静的Ｓｐｉｆｆの場合は、安全に無視することができる。
replaceFunction="ExecuteQuery()"は、特化すべき関数を記述したものである。ここでは１つだけ存在するが、一般的には多数存在可能である。
value="3"は、Ｓｐｉｆｆを（この場合、静的に）生成すべき不変数の値を記述したものである。ここでは１つだけ存在するが、一般的には多数存在可能である。
【０１４６】
この入力は、１つのＳｐｉｆｆパターン関数がExecuteQuery()に基づくＳｐｉｆｆパターンの構成と、変数ExecuteQuery()::query->schema->num_columnsを単一のリテラル値３に特化する静的実装の構成とをＳｐｉｆｆ構成器に伝えている。
【０１４７】
変形例２：細粒度での特化
上記例は、関数（ExecuteQuery()）全体を置き換えるように適用されたＳｐｉｆｆを示している。実際のところは、当該関数のわずかなコードセグメントのみが不変値を含むことを観察可能である。その後、以下のスニペットに示すように、上記わずかなコードセグメントをＳｐｉｆｆに変換可能である。
【０１４８】
以下に示す（Ｅｘａｍｐｌｅ１７に示す）候補スニペットは、上記と酷似しているが、区間がExecuteQuery()関数全体よりもはるかに小さく、ｆｏｒループの３行だけである。したがって、replaceFunction属性が消えている。最後に、行２１の定数畳み込み推奨が省略されているのは、当該行が特化対象の区間内ではないためである（残しておくことも可能であるが、その場合は無視される）。
2018510445.tif 000029
2018510445.tif 000030
【０１４９】
変形例３：固定実装アレイの採用
特定の実施例においては、１バイト整数でのＳｐｉｆｆ実装の識別を決定する。したがって、同じＳｐｉｆｆパターンに計２５５個の実装を有することができ、num_columns変数がＳｐｉｆｆパターンパラメータとして動作することにより、１〜２５５の間で変動する（無効値を表す場合は０を選定）。このため、以下のＥｘａｍｐｌｅ４２に示す候補スニペットは、値３のみならず、１〜２５５のすべての値（すなわち、invariantIntervalSet要素のfromValueおよびtoValue属性）を有する。また、関数全置き換えに立ち戻る。
2018510445.tif 000031
2018510445.tif 000032
【０１５０】
変形例４：動的Ｓｐｉｆｆ
現実的に、テーブルの各列としては、特定のデータ型が可能である。８つのデータ型（int2、int4、char、varchar等）が存在するものと仮定すると、３列テーブルの静的なテーブルＳｐｉｆｆには、考え得る実装を要する。したがって、このシナリオでは、動的なテーブルＳｐｉｆｆの方が適している。
【０１５１】
以下に与える候補スニペット（Ｅｘａｍｐｌｅ１９参照）は、これをcreateAt属性で記述しているが、ここでは、Ｓｐｉｆｆが作成されるアプリケーション中の場所すなわちCreateTable()関数（createAt属性（先の実施例ではcompileTime））内の場所およびＳｐｉｆｆがインスタンス化される場所すなわちOpenTable()関数（instantiateAt属性）内の場所を指定する。スニペットがインスタンス化された場合にnum_columns値が供給されることから、invariantlntervalSet要素にはfromValue属性もtoValue属性も存在しない。先の実施例とのもう１つの重要な相違点は、column_definitions上での定数畳み込みの付加的な最適化推奨である。
2018510445.tif 000033
2018510445.tif 000034
【０１５２】
静的なＳｐｉｆｆの作成と異なり、動的なＳｐｉｆｆは、テーブルＳｐｉｆｆに関して、Ｓｐｉｆｆのコンパイル呼び出しをCreateTable()に挿入することによって、実行時に作成される。
【０１５３】
さまざまな種類のＳｐｉｆｆの設計
（ここでは、オープンソースＰｏｓｔｇｒｅｓ  ＤＢＭＳからの例を使用する）
述語クエリＳｐｉｆｆ
このＳｐｉｆｆは、o_orderdate>=date'19940801'等のクエリ内の一般述語およびo_orderkey=l_orderkey等の結合述語の両者を評価することによって利用される。
【０１５４】
これらの述語は、（Ｐｏｓｔｇｒｅｓの）ExecQual()関数によって評価される。具体的に、述語は通常、連結リストで表される。ExecQual()は、このリストを介して繰り返し適用されるとともに、個々の述語に対応する特定の評価関数を呼び出す。Ｅｘａｍｐｌｅ２０に提示のコード抜粋（ＰＧ９．３ｓｔｏｃｋ，ｓｒｃ／ｂａｃｋｅｎｄ／ｅｘｅｃｕｔｏｒ／ｅｘｅｃQｕａｌ．ｃ：５１２５）は、このようなロジックを示している。
2018510445.tif 000035
【０１５５】
述語ごとの評価関数は、変数項に格納されている。a>bの形態の各述語について、オペランド＃１、オペレータ、およびオペランド＃２という３つの構成要素が存在する。Ｐｏｓｔｇｒｅｓにおいては、関数ExecEvalOperによってオペレータが評価される。この関数（Ｅｘａｍｐｌｅ２１参照）は本質的に、オペレータのタイプに応じた検索を実行するとともに、実際のタイプ固有の比較関数のアドレスをフェッチする。また、ExecEvalOper()では、オペランドが別の連結リストに格納されている必要がある。多くの場合、このリストの長さは、２である。以下は、これらの場合における当該関数の特化の一例である。
2018510445.tif 000036
2018510445.tif 000037
【０１５６】
なお、ExecEvalOper()は、一度の実行だけで比較関数の検索を行うことにより最適化する。その後、異なる関数をxprstate.evalfuncに格納する。また、当該関数を一度呼び出して述語とする。オペレータの後続の評価は、ExecMakeFunctionResultNoSets()によって行われる（現在の特化範囲内で考えられるスカラー述語の場合）。
【０１５７】
その後、各オペランドについて、引数抽出関数を呼び出すことにより、オペランドのリストを通してExecMakeFunctionResultNoSets()が繰り返し適用される。
【０１５８】
ExecEvalExprは、ｓｒｃ／ｉｎｃｌｕｄｅ／ｅｘｅｃｕｔｏｒ／ｅｘｅｃｕｔｏｒ．ｈ：７２において以下のように規定されたマクロである。
#define ExecEvalExpr(expr,econtext,isNull,isDone)＼
((*(expr)>evalfunc)(expr,econtext,isNull,isDone))
【０１５９】
このため、オペランドが定数の場合は、ExecEvalConst()が呼び出され、最後に比較関数を呼び出すことになる。
【０１６０】
述語評価において見られるボトルネックとして、第１に、オペランドリスト中の２つの要素のみを通して繰り返し適用されるループと、第２に、個々のオペランドの抽出とがある。具体的には、一般述語に関して、一方のオペランドが通常はテーブル列であり、他方のオペランドが定数である。このような場合は、複数の関数を呼び出してフェッチする必要なく、定数の値（または、アドレス）をコードに直接「格納」可能である。また、元の実装では、複数の関数呼び出しによって、テーブル由来オペランドの列ＩＤを抽出する必要がある。同様に、この列ＩＤについても、特化コードに直接格納することができる。
【０１６１】
結合述語の場合は、両オペランドが非定数である。オペランドの起点としては、INNER_VAR(I)、0UTER_VAR(O)、およびscantuple(S)という３つのタイプのうちの１つが可能である。また、オペランドの起点は、クエリを前提とした不変値でもある。この不変値を把握することによって、実際のオペランドの値を抽出するルーチンをさらに簡略化することができる。なお、理論的には、２つのオペランドの起点として９つの組み合わせが考えられるが、現実的には、以下の組み合わせのみが可能である。
【表１】
2018510445.tif 000038
【０１６２】
ハッシュ結合クエリＳｐｉｆｆ
ファイルｓｒｃ／ｂａｃｋｅｎｄ／ｅｘｅｃｕｔｏｒ／ｎｏｄｅＨａｓｈｊｏｉｎ．ｃに規定された関数ExecHashJoin()においては、所与のクエリに関して、変数node->js.jointypeが不変である。これは、クエリに応じて、集合{JOIN_ANTI，JOIN_SEMI，JOIN_LEFT，JOIN_INNER}から１つの値を選定することになる。
【０１６３】
同じファイルおよび関数においては、所与のクエリに関して、変数List*joinqualも不変である。
【０１６４】
ハッシュ結合クエリＳｐｉｆｆは、コードの全分岐を取り除くことによって、ｉｆ文の数を抑えるとともに、より重要なこととして、コードのサイズを小さくする。
【０１６５】
解析では、ポインタおよびヒープ割り当て構造体を伴う複雑なデータ構造を取り扱える必要がある。たとえば、ExecHashJoin()のｆｏｒループ本体のｉｆ文を取り除くには、以下（Ｅｘａｍｐｌｅ２２）のような表現を判断できる必要がある。
2018510445.tif 000039
2018510445.tif 000040
【０１６６】
ページＳｐｉｆｆ
ページＳｐｉｆｆは、ＤＢＭＳがデータの格納を管理するディスク／メモリページ内の不変値を利用する。このような不変値としては、ページ上に格納された行の数、残留自由空間、およびページの空充が挙げられることが多い。Ｐｏｓｔｇｒｅｓのページスキャンルーチンにおいては、スキャン方向およびスキャンモード等の付加的な不変値が存在する（pageatatime）。
【０１６７】
より興味深いこととして、ページＳｐｉｆｆは、より積極的な最適化を有効にし得る。たとえば、ページＳｐｉｆｆは、ページがメモリに読み込まれたらデータレイアウトを認識して、データ局所性を最適化することができる。また、データレイアウトが変更となったら、別途プロセスにおける既存の関数呼び出しシーケンスに従う代わりに、ページＳｐｉｆｆは、これらの呼び出しを一度に１ブロックずつ行使することによって、命令局所性を同様に改善することができる。
【０１６８】
ページＳｐｉｆｆは、データをしばらく辞退して、最終的にデータアクセスとなる長い呼び出しシーケンスを特化可能であり、呼び出された関数の多くのコードをすべて特化することができる。
【０１６９】
ページＳｐｉｆｆの主な利点として、呼び出された関数のインライン化により、命令キャッシュに適合し得る単一の特化関数を生成することができる。この変換がなされると、その他３つの相互排他的な変換が利用可能となる。
１．GetColumnsToLongs()仕様コードルーチンの活発な起動（圧縮タプルがページから抽出されたら直ちに、解凍tupletableslotに変換した後、仕様コードルーチンが操作するアレイに格納する）。
２．活発な部分的解凍（特化コードを呼び出すコードに必要となる最大列を演算させて、この最大列までを解凍する）
３．低調な解凍（元のコードがGetColumnsToLong()を呼び出したいずれの場所においても、複数の解凍動作を実行する）。
【０１７０】
これの変形例では、選択肢の選択性を用いて決定する。選択性が高い場合は、数行のみが参照されることを意味するため、述語の適用前に低調な解凍を使用する。
【０１７１】
一般的には、実行によって命令キャッシュ局所性が最大となり得るように、GetColumnsToLong()の呼び出しを配置するのが最善である。
【０１７２】
集約クエリＳｐｉｆｆ
集約Ｓｐｉｆｆは、SUMおよびAVG集約関数の効率を向上させるように設計されている。特に、数値データ型による集約関数の評価においては、メモリ割り当ておよび割り当て解除の実行において、Ｐｏｓｔｇｒｅｓが有意なオーバヘッドを招くことが分かっている。特に、集約Ｓｐｉｆｆは、このようなメモリ管理オーバヘッドを回避する。
【０１７３】
Ｐｏｓｔｇｒｅｓにおいては、バイト文字列によって数値型が表され、各桁はNumericDigitのアレイに格納される。この表現によれば、非常に緻密な制御が可能であるものの、本質的に文字列に基づく算術演算の実行が必要になって、性能が犠牲になる。
【０１７４】
一般的な実装において、行ごとのメモリ割り当ての実行が必要となる理由は、各入力行について、各行の値に存在する桁数が異なり得るためである。特に、a*bの評価においては、結果としての値の範囲が入力値の範囲を大きく超える可能性がある。それにも関わらず、Ｐｏｓｔｇｒｅｓにおいては、数値に関して対応可能な最大桁数を規定する定数（NUMERIC_MAX_PRECISION）が存在する。集約Ｓｐｉｆｆは、この値を利用することにより、Ｓｐｉｆｆデータ部のスラブ割り当てを行うが、その後、すべての入力行にわたって対応する集約関数を演算することにより、これを再利用して行ごとのメモリ割り当てを排除する。
【０１７５】
なお、集約関数の評価は、２つのステップから成る。たとえば、集約関数SUM(a + b)を前提として、第１のステップでは、式a+bの結果を評価する。そして、第２のステップでは、すべての入力行について、a+bの値を累算する。ＰｏｓｔｇｒｅＳＱＬにおいては、numeric_add()関数を用いることにより、a+bおよびSUM()関数の両者が評価される。この関数は、２つの入力を取得する。a+bの場合、２つの入力はそれぞれ、aおよびbである。SUM(x)の演算の場合、第２の入力はxであり、本質的にはスキャン行に由来し得る。第１の入力は、この点までに処理された現在の行の合計である遷移値である。
【０１７６】
SUM()の評価
numeric_add()によれば、２つの入力が追加され、make_result()により割り当てられた戻りres変数に結果の値がコピーされる。その後、ｎｏｄｅＡｇｇ．ｃ内のadvance_transition_function()にresが戻され、この戻り値がpergroupstate->transValueにコピーされた後、戻り値が自由になる。次回のadvance_transition_function()は次の行を処理するように実行され、transValueは、以下のスニペットを介してnumeric_add()の第１の入力値にコピーされる。
fcinfo->arg[0]=pergroupstate->transvalue;
fcinfo->argnull[0]=pergroupstate->transValueIsNull;
【０１７７】
このロジックは、すべて行にわたって自由にすることなく、transValueを実際に共有可能であることを示している。したがって、EvaluateNumericAddＳｐｉｆｆのデータ部の場合は、集約評価の最初に、AllocateAggTempValues()を用いることによって、必要な変数すなわちagg_temp_values->result_valueおよびagg_temp_values->result_argが割り当てられる（なお、これら２つの変数は、同じ値を表すものの、Ｐｏｓｔｇｒｅｓにおいては、このような２つの変数がそれぞれ、戻り値および一時的演算引数である必要がある）。
【０１７８】
式の評価
上述の通り、numeric_add()の別の用途は、a+b等の算術式の演算である。この場合は、式の評価結果を格納する変数が再利用されるが、これは、make_result()によって先に割り当てられている。この変数は、agg_temp_values->expr_result_argとして、Ｓｐｉｆｆデータ部に追加される。
【０１７９】
第１の入力がＳｐｉｆｆデータ部内のagg_temp_values->result_valueに直接由来するSUM()の評価の場合と異なり、a+bの評価における両入力は、既存のＰｏｓｔｇｒｅｓの実装を用いて求める必要がある一般変数である。実際、a+bの評価においては、ｅｘｅＱｕａｌ．ｃ内のExecEvalOper()からnumeric_add()が呼び出される。このため、述語Ｓｐｉｆｆと同様に、ExecMakeFunctionResultNoSets()関数を特化するＳｐｉｆｆ（EvaluateAggregateExpression）が作成される。そして、このＳｐｉｆｆは、EvaluateNumericAddＳｐｉｆｆの式評価版を呼び出す。
【０１８０】
式には、＋のほかに、−、＊、および／等の他の演算子を含み得る。これらの演算子を評価する関数についても、numeric_add()と同様に特化される。
【０１８１】
EvaluateNumericAddＳｐｉｆｆのまとめとして、以下の不変値が考えられる。
１）numeric_add()を呼び出す側／実行パス。これは、ｅｘｅｃＱｕａｌ．ｃの式の評価またはｎｏｄｅＡｇｇ．ｃのSUM()関数の評価に由来し得る。
２）式の評価において、結果値のメモリ位置は、不変にすることができる。
３）SUM()の評価において、結果値のメモリ位置および第１の入力のメモリ位置はいずれも、不変にすることができる。また、これら２つの変数は、同じメモリ位置を共有することも可能である。
４）すべての行にわたって共通のメモリセグメントを共有することは、数値データ型の最高精度の境界を示す定数によって可能となる。
【０１８２】
文字列照合Ｓｐｉｆｆ
たとえば、文字列ｘを（ワイルドカード等の特殊文字を含む）別の文字列パターンyと照合するＣ関数matchが存在する。クエリの実行前に（クエリ定数と考えられる）文字列ｙを把握している場合は、この特定の文字列パターンに対して任意の文字列を照合する特化関数を作成可能である。
【０１８３】
特化の手法としては、まず、以下のクエリ特化コード（仕様コード）を作成することになる：
長さ１〜３２の一定文字列用のコード
%クエリ文字列の文字用のコード
そして、これら仕様コードのさまざまな組み合わせを一列に並べることにより、yに対して文字列を照合する特化関数を構成することも可能である。たとえば、パターン「%abc%defg%」があり、これに対して任意の文字列を照合する特化関数を作成したいものとする。そこで、以下の仕様コードを一列に並べることになる：
%仕様コード
「abc」を照合する３文字の仕様コード
%仕様コード（最初のコードと同じにすることも可能）
「defg」を照合する４文字の仕様コード、
終了%仕様コード
これらの仕様コードはそれぞれ、照合完了後にも文字列の多くの文字が残ることを前提としている。仕様コードのうちの１つの照合が終わったら、残りの文字列を列中の次の仕様コードに渡して照合プロセスを継続する。
【０１８４】
文字列の一定部分の照合は、longlong、long、short、およびcharの組み合わせを用いることにより達成される。
【０１８５】
任意のクエリ文字列を前提として、ローカル変数として格納されたＳｐｉｆｆＩＤを用いることにより、クエリＳｐｉｆｆ起動によって最後を除くそれぞれが次の段階を呼び出した一連のクエリＳｐｉｆｆ関数ポインタをインスタンス化するのは容易である。
【０１８６】
以下（Ｅｘａｍｐｌｅ２３）は、（疑似コードを用いた）文字列「%abc%defg%」に対する実現の様子の一例を示している。
2018510445.tif 000041
2018510445.tif 000042
【０１８７】
これらの仕様コードルーチンを作成したら、アレイとして一連の関数呼び出しを構築することにより、このパターンに対して文字列を照合する。アレイは、Ｅｘａｍｐｌｅ２４のようになる。
2018510445.tif 000043
【０１８８】
そして、これらの関数が順次呼び出されることにより、文字列を照合する。長さが３２を超える一定部分は、セグメントへの分割も可能であるため、長さ６５の文字列の場合は、３２文字、３２文字、および１文字という３つのインスタンス化仕様コードが必要となる。
【０１８９】
より一般的には、一部の引数が不変の方法が存在する。これらの不変値は、再帰呼び出しおよびループ内等、ｉｆ文の一部が決定論的になる。相互呼び出しする一連の仕様コードによって、このシーケンスを展開する。これによって、ループならびに再帰的および非再帰的呼び出しで作用する一般変換のようになる。
【０１９０】
呼び出される実際の一連の仕様コードが実行時まで把握されないことから（照合対象の実際のパターンが利用可能な場合）、Ｓｐｉｆｆインスタンス化器によって、呼び出す一連の仕様コードを指定する関数ポインタのアレイを埋めることも可能である。
【０１９１】
クエリごとのＳｐｉｆｆ順位付け
クエリごとのＳｐｉｆｆ順位付けでは、メタＳｐｉｆｆを用いて、インタープリットされたデータ構造およびホットスワッピングを検討することにより、コンパイラが出力する類似物へと既存の仕様コードを変換する。いくつかの実施形態においては、ホットスワッピングメカニズムの使用により、さまざまなケース間の関係に従って、実行時に結合可能な特化コードへとswitch／caseブロックを変換する。具体的には、実行中に、あるcaseに別の特定のcaseが後続する場合である。ホットスワッピングによって、分岐ベースのディスパッチャ呼び出しは、目標分岐へのジャンプに置き換わる。これは、一般的なディスパッチャおよび解釈的な実行モデルにも当てはまる。クエリプランをインタープリットして対応するプランノード固有関数を呼び出す代わりに、プランツリーを前提として、すべてのディスパッチャ呼び出しを子プランノードへの直接ジャンプで置き換えることができる。
【０１９２】
特化コードの格納
特化が呼び出された場合は、特化コード（仕様コード）が生成され、領域特化プロセスに沿ったさまざまな場所に格納されるようになっていてもよい。たとえば、仕様コードは、油田データ２２０および油田シミュレータ２３０の両者からの不変値を含んでいてもよい。仕様コードは、設定パラメータ２１０および油田シミュレータ２３０の両者からの不変値を含んでいてもよい。いくつかの実施形態において、仕様コードは、Ｌｉｎｕｘ（登録商標）オペレーティングシステム２３０に格納され、シミュレータおよび油田データからの不変値を含んでいてもよい。いくつかの実施形態において、仕様コードは、外部ルータまたは外部クラウドサービスに格納されていてもよい。
【０１９３】
シミュレータに格納された仕様コードは、油田データおよびシミュレータに由来していてもよく、また、基本的な領域特化によって識別されるようになっていてもよい。他のＳｐｉｆｆは、指定用途に含まれるオペレーティングシステム、ルータ、クラウド、および特化コードと格納されている。いくつかの実施形態において、仕様コードは、格納場所から呼び出し可能な場所（後で特化する際の特化候補を提供したアプリケーション）まで流れるようになっていてもよい。たとえば、油田データは、外部ルータにおいて呼び出し対象の仕様コードを格納していてもよい。いくつかの実施形態においては、仕様コード識別子がデータまたはアプリケーションとともに存在可能であり、また、後続のアプリケーションと連通して含まれることにより、（後で）呼び出す関連仕様コードを示すことができる。
【０１９４】
図３は、本開示が提供する例示的な一実施形態によるコンピュータサイエンスのパラダイムを精緻化する領域特化を示した図である。この図には、データとしてのデータ表現、データとしてのコード表現、コードとしてのデータ表現、およびコードとしてのコード表現というそれぞれのシナリオについて、４つの象限３１０、３２０、３３０、および３４０を含む。
【０１９５】
バベッジマシンから１９３０年代に至るコンピュータアーキテクチャの初期段階においては、データがコードと区別されていた。データは操作されるものであり、プログラムコードは、データを操作して演算を有効にする方法の命令であった。これは、コンピュータメモリまたは記憶装置においてバイナリフォーマットで表されるデータすなわちデータとして格納されたデータおよびその他何らかの方法（たとえば、パッチコード）で表されるソースコードすなわちコードとして表されるコードとして、図３の象限３１０に示している。
【０１９６】
１９４０年代には、数値、混合コード、およびデータとしてコンピュータのメモリにマシンコードのプログラムを格納する革命的なアーキテクチャをＪｏｈｎ  ｖｏｎ  Ｎｅｕｍａｎｎが提案した（実際、コードはデータとして操作可能であり、プログラムの実行中であっても変更可能である）。このアーキテクチャは、象限３２０に示しており、コード（マシン語命令）がデータとして表される。
【０１９７】
１９６０年代には、データ（たとえば、引数のうちの１つの値）を伴うＬｉｓｐ関数の形態のコード組み合わせに至るいくつかの初期的な展開があり、これは、当該パラメータの値と対を成すＬｉｓｐ関数（コード）であるＬｉｓｐ連続を生じるものであって、引数が１つ少ない関数である。これは、象限３３０に示すように、データをコードに格納／カプセル化する特別な方法である。
【０１９８】
１９８０年代には、ポストスクリプト言語が発明された。これは、実行された場合に画像を生成するコードである。象限３２０に示すように、ポストスクリプトは、データであるＭｉｃｒｏｓｏｆｔ（登録商標）ワードファイル等のドキュメントを取得し、再びプログラムに変換するフォーマッタにより生成されるデータとしてのコードである。Ｍｉｃｒｏｓｏｆｔ（登録商標）ワードファイルから生成されたポストスクリプトファイルは、直接印刷される画像ではなく、ドキュメントの各文字を描画する命令であるため、当該プログラムは、たとえばポストスクリプトプリンタにおける実行またはポストスクリプト変換プログラムによる実行によって、ドキュメントのビットマップ画像を生成することも可能である。
【０１９９】
領域特化は、この考え方をさらに進めたものである。領域特化では、不変値すなわちデータを取得し、これらの値を用いて、実行可能なコードであるＤＢＭＳ等のアプリケーションの一部の特化コード版を生成する。このため、関係仕様コードは、関係（データ）のスキーマを用いたＤＢＭＳコードの特化の結果である。タプル仕様コードは、タプル（テーブルの行）内でデータ値を用いた結果である。Ｏ／Ｓ仕様コードは、オペレーティングシステムのスニペット内の特定の不変値の特定のデータ値に基づく当該スニペットの特化であり、ルータ仕様コードの場合と同じである。
【０２００】
このコードとしてのデータ表現（象限３３０に示す）は、あるアプリケーションにおいて、当該アプリケーションまたは別のアプリケーションのスニペットから生成可能であり、アプリケーション間で受け渡し可能であり、また、必要に応じて、目標アプリケーションにより呼び出し可能であり。領域特化技術は、このような仕様コードが性能増大時に有効となるタイミング、これらを生成すべきタイミング、特化すべき不変値、アプリケーション間で連通可能な方法、および呼び出すべきタイミングを識別する手段を提供する。
【０２０１】
データファイル内の任意のコヒーレント領域について、当該領域内の不変値を確定し、アプリケーションコードのエリアまでこれらの値を追跡し、これらのエリアから仕様コードを構成した後、これらの仕様コードをそれぞれの領域に再び関連付け可能であることが示唆される。したがって、この視点は、コードで開始してこれを特化するのではなく、元のデータに焦点を当てている。
【０２０２】
本開示の上記実施形態、特に、任意の「好適な」実施形態は、実施態様の考え得る例に過ぎず、また、本開示の原理の明確な理解を目的として示したものに過ぎないことが強調されるものとする。本開示の上記実施形態は、本開示の主旨および原理から実質的に逸脱することなく、多くの変形および改良が可能である。このようなすべての改良および変形は、本開示の範囲内で本明細書に含まれ、以下の特許請求の範囲によって保護されるものである。
【図１】
2018510445.tif 000044
【図２】
2018510445.tif 000045
【図３】
2018510445.tif 000046
【国際調査報告】
2018510445.tif 000047
2018510445.tif 000048