(57)【特許請求の範囲】
【請求項１】
マシンによって実現される、データベースクエリを処理する方法であって、
コプロセッサから独立して、データベースクエリの実行はデータベースオブジェクトデータのスキャン動作を伴うと判断することと、
前記データベースクエリの実行はスキャン動作を伴うという判断に応じて、スキャン動作コマンドを生成することとを含み、前記スキャン動作コマンドは、前記スキャン動作コマンドのパラメータとして、前記コプロセッサによって読出される入力データを識別するのに使用されるメモリアドレスデータと、前記入力データとの比較に使用される１つ以上の値とを含み、
前記スキャン動作コマンドを前記コプロセッサから独立したメモリに格納させることと、
前記コプロセッサによって前記スキャン動作コマンドを処理することとを含み、前記スキャン動作コマンドは、以下によって処理され、
前記スキャン動作コマンドを前記メモリから読出すこと、
前記メモリアドレスデータによって示される場所から前記入力データを読出させること、
前記入力データと前記１つ以上の値との比較を実行すること、
前記比較に基づいて結果データを生成すること、
前記結果データを格納させること、さらに、
前記結果データを用いて前記データベースクエリに対する結果を計算することを含み、
前記スキャン動作コマンドに含まれる前記メモリアドレスデータは、１つ以上の仮想アドレスを含み、
前記方法は、前記１つ以上の仮想アドレスを、前記コプロセッサが入力データを読出すのに使用する１つ以上の物理アドレスに置換えさせることをさらに含む、方法。
【請求項２】
マシンによって実現される、データベースクエリを処理する方法であって、
コプロセッサから独立して、データベースクエリの実行はデータベースオブジェクトデータのスキャン動作を伴うと判断することと、
前記データベースクエリの実行はスキャン動作を伴うという判断に応じて、スキャン動作コマンドを生成することとを含み、前記スキャン動作コマンドは、前記スキャン動作コマンドのパラメータとして、前記コプロセッサによって読出される入力データを識別するのに使用されるメモリアドレスデータと、前記入力データとの比較に使用される１つ以上の値とを含み、
前記スキャン動作コマンドを前記コプロセッサから独立したメモリに格納させることと、
前記コプロセッサによって前記スキャン動作コマンドを処理することとを含み、前記スキャン動作コマンドは、以下によって処理され、
前記スキャン動作コマンドを前記メモリから読出すこと、
前記メモリアドレスデータによって示される場所から前記入力データを読出させること、
前記入力データと前記１つ以上の値との比較を実行すること、
前記比較に基づいて結果データを生成すること、
前記結果データを格納させること、さらに、
前記結果データを用いて前記データベースクエリに対する結果を計算することを含み、
前記スキャン動作コマンドは、実行する動作のタイプを示す動作タイプデータをさらに含み、前記動作のタイプは、スキャン動作か、ルックアップ動作かのいずれかであり、
,
前記スキャン動作コマンドはさらに、前記動作タイプデータを先ず識別し前記動作のタイプを判断することによって、処理される、方法。
【請求項３】
前記動作タイプデータを用いて、前記入力データを解釈するのに使用されるロジックを判断することと、
前記入力データを、第１のデータタイプから、前記第１のデータタイプと異なる第２のデータタイプに変換することとをさらに含む、請求項２に記載の方法。
【請求項４】
前記入力データは、値データとカウントデータとを含み、
前記値データの中の入力値はデータ要素に対応し、前記データ要素の数は前記カウントデータの中のカウント値によって示され、
前記入力データと前記１つ以上の値との比較は、前記入力値と前記１つ以上の値との比較を含み、
前記結果データの生成は、前記入力値が前記１つ以上の値を満たすか否かを表示する結果表示を生成することを含み、
前記結果データの生成は、前記入力値と前記１つ以上の値とを前記数に等しい回数比較することなく行なわれる、請求項１〜３のいずれか１項に記載の方法。
【請求項５】
前記スキャン動作コマンドは、前記結果データを格納する場所を示す宛先データをさらに含む、請求項１〜４のいずれか１項に記載の方法。
【請求項６】
前記結果データを格納させることは、前記結果データをマイクロプロセッサのキャッシュに格納させることを含む、請求項１〜５のいずれか１項に記載の方法。
【請求項７】
前記結果データを格納させることは、前記スキャン動作コマンドが実行されたことを示す完了状態を格納させることをさらに含む、請求項１〜６のいずれか１項に記載の方法。
【請求項８】
前記データベースクエリの実行は前記スキャン動作と１つ以上のその他の動作とを含む複数の動作を伴うと判断し、
前記方法は、
前記結果データを記憶装置から取出すことと、
前記結果データを前記記憶装置から取出した後、前記１つ以上のその他の動作に対する入力として前記結果データを必要とする前記１つ以上のその他の動作を処理することとをさらに含む、請求項１〜７のいずれか１項に記載の方法。
【請求項９】
前記コプロセッサは、連続して接続された複数のコプロセッサのうちの第１のコプロセッサであり、
前記結果データを格納させることは、前記複数のコプロセッサのうちの第２のコプロセッサのバッファに前記結果データを送信させることを含み、
前記方法は、
前記第１のコプロセッサが前記データベースクエリの一部を実行している間に、前記第２のコプロセッサによって前記バッファから前記結果データを読出すことと、
前記結果データに基づいて、前記第２のコプロセッサによって第２の結果データを生成することとをさらに含む、請求項１〜８のいずれか１項に記載の方法。
【請求項１０】
前記判断するステップ、前記生成するステップ、および前記格納させるステップは、クエリ実行エンジンを実行する汎用マイクロプロセッサによって実行され、前記汎用マイクロプロセッサは前記コプロセッサから独立したものである、請求項１〜９のいずれか１項に記載の方法。
【請求項１１】
マシンによって実現される、データベースクエリを処理する方法であって、
コプロセッサから独立して、データベースクエリの実行はデータベースオブジェクトデータのスキャン動作を伴うと判断することと、
前記データベースクエリの実行はスキャン動作を伴うという判断に応じて、スキャン動作コマンドを生成することとを含み、前記スキャン動作コマンドは、前記スキャン動作コマンドのパラメータとして、前記コプロセッサによって読出される入力データを識別するのに使用されるメモリアドレスデータと、前記入力データとの比較に使用される１つ以上の値とを含み、
前記スキャン動作コマンドを前記コプロセッサから独立したメモリに格納させることと、
前記コプロセッサによって前記スキャン動作コマンドを処理することとを含み、前記スキャン動作コマンドは、以下によって処理され、
前記スキャン動作コマンドを前記メモリから読出すこと、
前記メモリアドレスデータによって示される場所から前記入力データを読出させること、
前記入力データと前記１つ以上の値との比較を実行すること、
前記比較に基づいて結果データを生成すること、
前記結果データを格納させること、さらに、
前記結果データを用いて前記データベースクエリに対する結果を計算することを含み、
スキャン動作コマンドを生成することは、前記スキャン動作を含む複数のスキャン動作コマンドを生成することを含み、
前記スキャン動作コマンドをメモリに格納させることは、前記複数のスキャン動作コマンドのうちの各スキャン動作コマンドについて、前記各スキャン動作コマンドを前記メモリに格納させることを含み、
複数のコプロセッサのうちの各コプロセッサが、前記複数のスキャン動作コマンドからスキャン動作コマンドを選択する、方法。
【請求項１２】
１つ以上の基準が満たされるか否か判断することをさらに含み、前記１つ以上の基準が満たされる場合のみ、前記スキャン動作コマンドを前記コプロセッサに送信させる、請求項１〜１１のいずれか１項に記載の方法。
【請求項１３】
前記１つ以上の基準は、前記コプロセッサが前記スキャン動作を実行するために読出すことが必要なデータの量に基づく、請求項１２に記載の方法。
【請求項１４】
マシンによって実現される、データベースクエリを処理する方法であって、
コプロセッサから独立して、データベースクエリの実行はデータベースオブジェクトデータのスキャン動作を伴うと判断することと、
前記データベースクエリの実行はスキャン動作を伴うという判断に応じて、スキャン動作コマンドを生成することとを含み、前記スキャン動作コマンドは、前記スキャン動作コマンドのパラメータとして、前記コプロセッサによって読出される入力データを識別するのに使用されるメモリアドレスデータと、前記入力データとの比較に使用される１つ以上の値とを含み、
前記スキャン動作コマンドを前記コプロセッサから独立したメモリに格納させることと、
前記コプロセッサによって前記スキャン動作コマンドを処理することとを含み、前記スキャン動作コマンドは、以下によって処理され、
前記スキャン動作コマンドを前記メモリから読出すこと、
前記メモリアドレスデータによって示される場所から前記入力データを読出させること、
前記入力データと前記１つ以上の値との比較を実行すること、
前記比較に基づいて結果データを生成すること、
前記結果データを格納させること、さらに、
前記結果データを用いて前記データベースクエリに対する結果を計算することを含み、
前記１つ以上の値は複数のデータ要素を含み、
前記入力データと前記１つ以上の値との比較は、同時に、前記入力データと前記複数のデータ要素とを比較することを含む、方法。
【請求項１５】
前記比較に基づいて結果データを生成することは、ビットベクトルを生成することを含み、前記ビットベクトルにおける各ビットは、比較から得られたものが真か偽かを示す、請求項１〜１４のいずれか１項に記載の方法。
【請求項１６】
コプロセッサであって、
スキャン動作コマンドを読出すステップを実行するように構成され、前記スキャン動作コマンドは、
（１）クエリの処理に関連する命令を実行するマイクロプロセッサによって生成されたものであり、
（２）前記スキャン動作コマンドのパラメータとして、前記コプロセッサによって読出される入力データを識別するのに使用されるメモリアドレスデータと、前記入力データとの比較に使用される１つ以上の値とを含み、前記スキャン動作コマンドに含まれる前記メモリアドレスデータは、１つ以上の仮想アドレスを含み、さらに、
前記１つ以上の仮想アドレスを、前記コプロセッサが入力データを読出すのに使用する１つ以上の物理アドレスに置換えさせるステップと、
前記入力データを前記物理アドレスによって示される場所から読出させるステップと、
前記入力データと前記１つ以上の値との比較を実行するステップと、
前記比較に基づいて結果データを生成することと、
前記マイクロプロセッサに前記結果データを通知するステップとを実行するように構成される、コプロセッサ。
【請求項１７】
データベースクエリを処理するためのシステムであって、
マイクロプロセッサと、
コプロセッサと、
前記マイクロプロセッサおよび前記コプロセッサに接続されたメモリとを備え、
前記マイクロプロセッサは、
前記コプロセッサから独立して、前記データベースクエリの実行はデータベースオブジェクトデータのスキャン動作を伴うと判断するように構成され、
前記データベースクエリの実行はスキャン動作を伴うという判断に応じて、スキャン動作コマンドを生成するように構成され、前記スキャン動作コマンドは、前記スキャン動作コマンドのパラメータとして、前記コプロセッサによって読出される入力データを識別するのに使用されるメモリアドレスデータと、前記入力データとの比較に使用される１つ以上の値とを含み、前記スキャン動作コマンドに含まれる前記メモリアドレスデータは、１つ以上の仮想アドレスを含み、
前記スキャン動作コマンドを前記コプロセッサから独立したメモリに格納させるように構成され、
前記コプロセッサは、前記スキャン動作コマンドを処理するように構成され、前記スキャン動作コマンドは、
前記スキャン動作コマンドを前記メモリから読出すこと、
前記１つ以上の仮想アドレスを、前記コプロセッサが入力データを読出すのに使用する１つ以上の物理アドレスに置換えさせること、
前記物理アドレスによって示される場所から前記入力データを読出させること、
前記入力データと前記１つ以上の値との比較を実行すること、
前記比較に基づいて結果データを生成すること、および
前記結果データを格納させることによって処理され、
前記結果データは、前記データベースクエリに対する結果を計算するために使用される、システム。
【請求項１８】
データベースクエリを処理するためのシステムであって、
マイクロプロセッサと、
コプロセッサと、
前記マイクロプロセッサおよび前記コプロセッサに接続されたメモリとを備え、
前記マイクロプロセッサは、
前記コプロセッサから独立して、前記データベースクエリの実行はデータベースオブジェクトデータのスキャン動作を伴うと判断するように構成され、
前記データベースクエリの実行はスキャン動作を伴うという判断に応じて、スキャン動作コマンドを生成するように構成され、前記スキャン動作コマンドは、前記スキャン動作コマンドのパラメータとして、前記コプロセッサによって読出される入力データを識別するのに使用されるメモリアドレスデータと、前記入力データとの比較に使用される１つ以上の値とを含み、
前記スキャン動作コマンドを前記コプロセッサから独立したメモリに格納させるよう
に構成され、
前記コプロセッサは、前記スキャン動作コマンドを処理するように構成され、前記スキャン動作コマンドは、
前記スキャン動作コマンドを前記メモリから読出すこと、
前記メモリアドレスデータによって示される場所から前記入力データを読出させること、
前記入力データと前記１つ以上の値との比較を実行すること、
前記比較に基づいて結果データを生成すること、および
前記結果データを格納させることによって処理され、
前記結果データは、前記データベースクエリに対する結果を計算するために使用され、
前記スキャン動作コマンドは、実行する動作のタイプを示す動作タイプデータをさらに含み、前記動作のタイプは、スキャン動作か、ルックアップ動作かのいずれかであり、
前記スキャン動作コマンドはさらに、前記動作タイプデータを先ず識別し前記動作のタイプを判断することによって、処理される、システム。
【発明の詳細な説明】
【技術分野】
【０００１】
優先権の主張および関連事件
本願は、２０１２年１０月２日に出願された米国仮出願第６１／７０９，１４２号に基づく優先権を主張する２０１３年２月２６日に出願された米国特許出願第１３／７７８，００９号に基づく優先権を主張し、上記出願の内容を本明細書にその全体が記載されているが如く引用により援用する。
【０００２】
本願は、２０１３年２月２６日に出願された米国特許出願第１３／７７８，０１３号に関連し、この出願の内容を本明細書にその全体が記載されているが如く引用により援用する。
【０００３】
発明の分野
本発明は、概してクエリの処理に関し、より具体的には、１つ以上のコプロセッサ内のカスタムハードウェアを用いて、クエリを処理することが要求される１つ以上の動作を実行することに関する。
【背景技術】
【０００４】
背景
このセクションで説明される手法は、遂行可能な手法であるが、必ずしも過去に考案または遂行された手法ではない。したがって、特に明示されない限り、このセクションで説明される手法のうちのいずれも、このセクションに含まれているというだけで先行技術とみなされるべきではない。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
データベースに対して発行されるクエリは通常、１つ以上の、リレーショナルテーブル等のデータベースオブジェクトを対象としている。リレーショナルテーブル内に配列されたデータへのアクセスは、このリレーショナルテーブルまたは少なくともその一部をスキャンすることを伴うことが多い。一般的なＳＱＬクエリは、データベーステーブルに対する以下のようなフィルタを要求するクエリである。
【０００６】
select EMPLOYEE from T_EMPLOYEES where HIRE_YEAR='2012'（雇用年度が２０１２年の被雇用者をT_EMPLOYEESから選択）
この例では、２０１２年に雇用された全被雇用者を求めて上記データベーステーブルT_EMPLOYEESが検索される。この検索（または「スキャン」）は、一連の命令を実行する１つ以上のマイクロプロセッサ上で走らせているソフトウェアによって、この例では「２０１２」という指定された値を求めてテーブルを検索するために行なわれる。大型のデータベース上で解析アプリケーションを走らせるとき、この最初のステップは通常、性能の障害となる。なぜなら、このステップは、数テラバイトの大きさの可能性があるテーブル全体に対して実行しなければならないからである。その後のステップは、スキャンにおいて設定された条件（上記例では２０１２年に雇用された被雇用者）を満たす、最初のスキャンステップでフィルタリングされたサブセットに対して実行される。したがって、単位時間当たりにマシンがフィルタリング可能な行の数は、このマシンにとって重要な性能基準である。この基準は「スキャンレート」と呼ばれている。
【０００７】
テーブルのスキャンを伴うクエリのようなクエリを処理するための手法は、汎用マイクロプロセッサ上で実行される（または「走らせる」）ソフトウェアのソフトウェア技術に頼っている。
【図面の簡単な説明】
【０００８】
【図１】ある実施形態に従う、テーブルスキャンを加速するためのコンピュータシステムの一例を示すブロック図である。
【図２】ある実施形態に従う、コプロセッサの一例を示すブロック図である。
【図３】ある実施形態に従う、クエリを処理するためのプロセスを示すフロー図である。
【図４】ある実施形態における、ルックアップベクトルの一例の一部を示すブロック図である。
【図５】本発明の実施形態が実装され得るコンピュータシステムを示すブロック図である。
【発明を実施するための形態】
【０００９】
詳細な説明
以下の記載では、本発明が十分に理解されるよう、数多くの具体的な詳細事項が説明のために述べられている。しかしながら、これらの具体的な詳細事項がなくとも本発明を実施し得ることは明らかであろう。他の場合では、本発明を不必要に曖昧にするのを避けるために、周知の構造および装置はブロック図の形式で示される。
【００１０】
全体の概要
ある実施形態において、クエリに関連するスキャン動作またはルックアップ動作は、汎用マイクロプロセッサと同一のチップ上に位置するコプロセッサ等のハードウェアにおいて実現される。このようにして、スキャン動作はカスタムハードウェアによって実行され、一方、クエリの他の部分はソフトウェアを実行する汎用マイクロプロセッサによって扱われる。異なるハードウェアコンポーネントに異なる動作を実行させる利点としては、カスタムハードウェアの方がスキャン動作またはルックアップ動作に必要な大量のデータを上手く扱うことができる点が挙げられる。また、カスタムハードウェアは、汎用マイクロプロセッサおよび関連するキャッシュを、クエリの他の部分に対する作業、またはさらにはクエリを処理するソフトウェアとは無関係の他のタスクに対する作業を行なえるよう、解放する。
【００１１】
本発明の実施形態は、特定のマイクロプロセッサまたはグラフィックス処理装置（ＧＰＵ）に限定されない。
【００１２】
以下の例では、スキャンされるデータオブジェクトとしてテーブルについて述べる。しかしながら、すべての実施形態がテーブルに限定されるとは限らない。テーブル以外のデータオブジェクトがスキャンされてもよい。
【００１３】
システムの概要
図１は、ある実施形態に従う、クエリの処理を加速するためのコンピュータシステム１００の一例を示すブロック図である。コンピュータシステム１００は、クエリ実行エンジン１１０と、ＯＳ／ハイパーバイザ１２０と、コプロセッサ１３０と、メモリ１４０とを含む。示されているのは１つのコプロセッサ１３０のみであるが、システム１００は複数のコプロセッサを含み得る。
【００１４】
クエリ実行エンジン１１０およびハイパーバイザ１２０は、メモリ（たとえばＤＲＡＭおよび／またはキャッシュメモリ）の中にあるプログラムであり、汎用マイクロプロセッサによって実行される命令を含む。クエリ実行エンジン１１０は、１つ以上のソフトウェアコンポーネントを含み、クエリを実行してこのクエリの結果を生成するために、クエリ実行エンジン１１０の一部ではない１つ以上のその他のソフトウェアコンポーネントと通信し得る。クエリ実行エンジン１１０は、クエリ（たとえばＳＱＬクエリ）を書換えてクエリ実行エンジン１１０が実行できる書換えられたクエリを生成するように構成されてもよい。これに代わるものとしては、別のソフトウェアコンポーネントが元のクエリを受け、この元のクエリに基づいて書換えられたクエリを生成し、書かれたクエリを処理のためにクエリ実行エンジン１１０に送る。
【００１５】
クエリ実行エンジン１１０をその処理のために構成し得るクエリの種類の非限定的な一例は、ＸＰａｔｈクエリおよびＸＱｕｅｒｙ等のＳＱＬクエリおよびＸＭＬクエリを含む。クエリ実行エンジン１１０をその処理のために構成する、少なくとも１つの種類のクエリは、オブジェクトまたはその一部のスキャンを要求するクエリである。先に述べたように、スキャンされるオブジェクトの非限定的な一例は、１つ以上の列と複数の行に論理的に配列されたリレーショナルテーブルである。データは、１つのテーブルに論理的に配列されてもよいが、ハードディスクドライブまたはフラッシュメモリ装置等の永続性記憶装置に全く異なるやり方で配列されてもよい。たとえば、テーブルのデータを区切ってもよく、テーブルのうちの異なる列を全く異なる格納場所に格納してもよい。
【００１６】
ハイパーバイザ１２０は、クエリ実行エンジン１１０とコプロセッサ１３０の間のインターフェイスとして機能する。言い換えると、クエリ実行エンジン１１０によってコプロセッサ１３０に対して発行されるコマンドは、ハイパーバイザ１２０を通して発行される。このため、クエリ実行エンジン１１０は、ハイパーバイザインターフェイスに対するコマンドを、ＯＳ／ハイパーバイザ１２０に対してＡＰＩコールを行なうことによって発行する。
【００１７】
ハイパーバイザは、ホストコンピュータ上で複数のオペレーティングシステム（「ゲスト」）を同時に走らせることができるようにするハードウェア仮想化技術である。ハイパーバイザは、ゲストオペレーティングシステムに対し、仮想オペレーティングプラットフォームを提供し、ゲストオペレーティングシステムの実行を管理する。さまざまなオペレーティングシステムの複数のインスタンスは、仮想化されたハードウェアリソースを共有し得る。ハイパーバイザは、それ自体サーバの役割を果たすゲストオペレーティングシステムを実行する機能を伴って、サーバハードウェア上にインストールされてもよい。
【００１８】
あるタイプのハイパーバイザは、ホストのハードウェア上で直接走らせることで、ハードウェアを制御し、ゲストオペレーティングシステムを管理する。このため、ゲストオペレーティングシステムは、ハイパーバイザよりも上の別のレベルで走らせる。別のタイプのハイパーバイザは、典型的なオペレーティングシステム環境の中で走らせる。ハイパーバイザレイヤが固有の第２のソフトウェアレベルであるとすると、ゲストオペレーティングシステムはハードウェアよりも上の第３のレベルで走らせる。言い換えると、第１のタイプのハイパーバイザはハードウェアの直接上で走らせるのに対し、第２のタイプのハイパーバイザは、ＦｒｅｅＢＳＤ、Ｌｉｎｕｘ（登録商標）、またはＷｉｎｄｏｗｓ（登録商標）等の別のオペレーティングシステムの上で走らせる。
【００１９】
したがって、要素１２０は「ＯＳ／ハイパーバイザ」という名称が与えられているが、オペレーティングシステムとハイパーバイザは異なるエンティティである。本明細書での説明のためにＯＳとハイパーバイザは同一のものとして扱われる。以下では要素１２０を「ハイパーバイザ１２０」と呼ぶ。
【００２０】
ハイパーバイザ１２０はコンピュータシステム１００の一部として示されているが、ある実施形態においてコンピュータシステム１００はハイパーバイザを含まない。この実施形態では、クエリ実行エンジン１１０が、コンピュータシステム１００のオペレーティングシステム（図示せず）を除くその他のソフトウェアコンポーネントによる処理を最初に要求することなく、直接コプロセッサ１３０に対してコマンドを発行する。
【００２１】
コプロセッサ１３０は、クエリ実行エンジン１１０およびハイパーバイザ１２０を実行する汎用プロセッサによって実行されるタスクとは別の１つ以上のタスクを実行するようにプログラムされたハードウェア要素である。コプロセッサ１３０は、クエリ実行エンジン１１０を実行する汎用プロセッサから独立したものであるが、コプロセッサ１３０を、クエリ実行エンジン１１０によって以前に実行された１つ以上のタスクをコプロセッサ１３０が実行するという意味においてクエリ実行エンジン１１０の一部とみなしてもよい。
【００２２】
ある実施形態において、コプロセッサ１３０は、指定された対象値（または値の対象範囲）をテーブルからの一連の入力値と比較するタスクを少なくとも実行する。このタスクはスキャン動作と呼ばれ以下で詳しく説明される。ある実施形態において、コプロセッサ１３０は、指定された複数の対象値（または指定された複数の対象範囲）を、テーブルからの一連の入力値またはデータ要素と比較することができる。
【００２３】
別の実施形態において、コプロセッサ１３０は、１つ以上の値が、特定の一組の値の中にあるか否か判断するタスクを少なくとも実行する。１つ以上の値を用いて特定の一組の値にインデックスを付けることで、上記１つ以上の値のうちの各値について特定の一組の値をスキャンする必要がなくなる。この実施形態において、コプロセッサ１３０は、ルックアップ動作を効率的に実行するようにプログラムされている。これについては以下で詳しく説明される。
【００２４】
クエリ実行エンジン１１０によって定められたまたは指示された初期パラメータの他に、コプロセッサ１３０は、スキャン動作および／またはルックアップ動作を、（開始コマンドによって示された）このスキャン動作および／またはルックアップ動作が完了するまでクエリ実行エンジン１１０またはその他のソフトウェアの介入を受けることなく、実行する。完了した時点で、コプロセッサ１３０は、この動作の結果を利用できることをクエリ実行エンジン１１０に信号で知らせる。この信号はフラグの設定の形態であってもよい。ハイパーバイザ１２０はこの信号を用いて新たなコマンドをコプロセッサ１３０のコマンドキューの中に挿入してもよい。
【００２５】
ある実施形態において、コプロセッサ１３０は、異なるデータ種類／フォーマットおよび要素サイズを扱うようにプログラムされる。たとえば、コプロセッサ１３０は、ストリングフォーマット、日付フォーマット、または数（整数または浮動）フォーマットのデータを処理し得る。また、コプロセッサ１３０が処理するデータ要素のサイズは、特定数のビット（たとえば７ビット）であっても特定数のバイト（たとえば２バイト）であってもよい。さらに、特定のソース（テーブル等）からのデータ要素は、可変長であっても固定長であってもよい。ある実施形態では、コプロセッサ１３０が（テーブル等の）オブジェクトから受けるデータ要素は１つのサイズであってもよく、コプロセッサ１３０は、データ要素から１バイト削除する、データ要素に９ビット追加する、またはデータ要素を圧縮解除するといった動作を、たとえばこのデータ要素を別のデータ要素と比較する前に実行することによって、データ要素のサイズを小さくまたは大きくする。
【００２６】
ある実施形態において、コプロセッサ１３０は、オンチップである、すなわち、クエリ実行エンジン１１０を実行する汎用マイクロプロセッサと同一のチップ上にある。コプロセッサ１３０は、（ａ）オンまたはオフチップメモリからコプロセッサ１３０へテーブルデータ（またはその他のデータ）をストリーミングするメモリインターフェイスと、（ｂ）スキャン動作および／またはルックアップ動作を実行する計算ブロックとを含む。たとえばスキャン動作の場合、計算ブロックは、テーブルデータに対して動作を行ない、指定された値または値の範囲がテーブルデータの中にあるか否か判断する。このため、一組のコンパレータを使用することにより、入来するストリームの各要素が、探している値に等しいかまたは探している値の範囲の中にあるか否か判断する。一組のコンパレータの各コンパレータが同時に比較動作を実行してもよい。このため、コプロセッサ１３０は、複数の比較動作を同時に行なってもよい。ある実施形態において、コプロセッサ１３０は、１つの４バイト比較、２つの２バイト比較、４つの１バイト比較、および／または１つの２バイト比較と１つの１バイト比較といったように、複数種類の比較を実行するように構成される。コプロセッサ１３０は、検索結果をメモリインターフェイスを通してオンチップメモリまたはオフチップメモリに送る。
【００２７】
図１に示されるように、メモリ１４０は、コマンド１４２、入力データ１４４、および出力データ１４６を格納する。コマンド１４２に反映されるコマンドは、（１）入力データ１４４の少なくとも一部を格納するメモリ１４０内の場所、および（２）コマンドに対応する動作の結果（コプロセッサ１３０によって生成される）が格納されることになる場所を示す。
【００２８】
ある実施形態において、コプロセッサ１３０は、１つ以上のコマンドの１つ以上のアドレスを格納したコマンドキューを含む。ビジーでないとき、コプロセッサ１３０は、メモリ（たとえばメモリ１４０）から１つ以上のコマンド（たとえばコマンド１４２に反映されている）を取出すために、（ハイパーバイザ１２０によって挿入された）１つ以上のアドレスをコマンドキューから選択する。
【００２９】
コプロセッサ制御ブロック
ある実施形態において、クエリ実行エンジン１１０は、汎用マイクロプロセッサ（図示せず）によって実行されてコプロセッサ制御ブロック（ＣＣＢ）を生成させる命令を含む。ＣＣＢは、クエリ実行エンジン１１０によって発行されるコマンドを表わすデータ構造であり、コプロセッサはこのデータ構造に含まれるデータを読出して処理するように構成される。ある実施形態において、ＣＣＢは、コプロセッサ１３０が実行しようとしている動作のタイプを示すコマンドタイプデータと、コマンドタイプデータによって示される動作に対応する１つ以上のオペランドとを含む。コプロセッサ１３０が１つの動作しか実行しない場合は、コマンドタイプデータはＣＣＢで利用できるオペランドではない場合がある。これに代わるものとしては、コプロセッサ１３０が１つの動作しか実行しないように構成されている場合、コプロセッサ１３０はコマンドタイプデータを無視してもよい。
【００３０】
コマンドタイプデータは、コプロセッサ１３０がコマンドの処理においてどのロジックを使用するかを示す。このため、異なるコマンドタイプは、コプロセッサ１３０によって実現される異なるロジックに対応する。たとえば、スキャン動作ではコプロセッサ１３０が第１のロジックを実行することが要求される一方で、ルックアップ動作ではコプロセッサ１３０が第１のロジックと異なる第２のロジックを実行することが要求される。
【００３１】
ＣＣＢにおいて示されるオペランドは、２つのタイプのうちの一方、すなわち即値オペランドまたは間接オペランドであればよい。即値オペランドとは、メモリルックアップ等の、オペランドの変換を最初に要求しない動作をコプロセッサが実行するときに、コプロセッサが即時使用することができるオペランドである。スキャン動作の場合の即値オペランドの一例は、テーブルデータからのデータ要素との比較を行なうために使用される４バイトの整数である。間接オペランドとは、指定された動作をコプレッサが実行するには、その前に、最初に変換またはルックアップされなければならないオペランドである。間接オペランドの一例は、スキャン動作であるかルックアップ動作であるかに関わらず、コプレッサが動作を実行するためのテーブルデータが格納されている場所（たとえばメモリ１４０の中）を示す物理アドレスである。
【００３２】
スキャン動作の場合、ＣＣＢに示される（スキャン動作の）オペランドは、（ａ）テーブルデータからのデータとの比較を行なうために使用されるデータを示す比較データと、（ｂ）テーブルデータがある場所を示す場所データ（たとえばメモリ１４０の中の入力データ１４４）とを含む。
【００３３】
比較データは、数、日付、文字、またはストリング等、どのような種類のデータであってもよい。比較データは、１つの値および／または値の範囲であってもよい。加えて、比較データは、複数の値および／または値の複数の範囲を示し得る。たとえば、クエリは、収入が３万ドル未満の被雇用者および収入が１０万ドルと１３万ドルの間の被雇用者の名前の閲覧を要求するものであってもよい。この例において、比較データは、０〜３０，０００という範囲および１００，０００〜１３０，０００という範囲を示す。
【００３４】
場所データは、１つのアドレスであってもよく、または、開始アドレスと終了アドレス、もしくは、開始アドレスと開始アドレスからのオフセットといったように、複数のアドレスであってもよい。場所データにおいて示される各アドレスは、仮想アドレス、実アドレス、または物理アドレスであってもよい。ある実施形態において、ハイパーバイザ１２０は、ＣＣＢに示される場所データを第２の場所データに置換える。一例として、（たとえばゲスト）オペレーティングシステムは、ＣＣＢに示される、仮想アドレスである場所データを識別し、この仮想アドレスを実アドレスに置換える。次に、このオペレーティングシステムは、ＣＣＢをハイパーバイザ１２０に送る。ハイパーバイザ１２０は、マッピングテーブルにおいて実アドレスにマッピングされている物理アドレスを探し、ＣＣＢの実アドレスを物理アドレスに置換える。
【００３５】
ある実施形態において、ＣＣＢは出力場所データも含む。出力場所データは、ＣＣＢによって示される動作の実行結果をコプロセッサ１３０が送るべき場所を示す。図１では、出力場所データはメモリ１４０内の出力データ１４６を示すであろう。複数のマイクロプロセッサが同一チップ上に集積されており各マイクロプロセッサが自身のプライベートキャッシュを有する場合、これは有用であろう。このため、クエリ実行エンジン１１０を実行する特定の汎用マイクロプロセッサが同一チップ上の複数の汎用マイクロプロセッサのうちの１つであり、かつ、各マイクロプロセッサが異なる（たとえばＬ３）キャッシュと関連付けられている場合、クエリ実行エンジン１１０は、ＣＣＢ内のパラメータとして、上記特定の汎用マイクロプロセッサに隣接または近接するキャッシュを指定すればよい。このように、コプロセッサ１３０は、動作の結果をＲＡＭに送るのではなく、（ＣＣＢに示される出力場所データに基づいて）結果をキャッシュだけでなくクエリ実行エンジン１１０に「最も近い」特定のキャッシュにも送ってもよい。このようにして、クエリ実行エンジン１１０が、（ａ）ＲＡＭからの、（ｂ）別のマイクロプロセッサの（またはコアの）キャッシュからの、または（ｃ）複数のコアによって共有されている共有キャッシュからの結果を要求する必要はなくなる。これらのうちどの場合も、マイクロプロセッサ自身の（プライベート）キャッシュからデータにアクセスするよりも遥かに遅いかもしれない。代わりに、クエリ実行エンジン１１０は、１つ以上のハードウェア要素（すなわちこの実施の形態ではコプロセッサ）によって実行された動作の結果を格納する場所を指示してもよい。
【００３６】
コプロセッサ
コプロセッサ１３０は、（たとえばＣＣＢの形態の）コマンドをハイパーバイザ１２０のインターフェイスを通して（またはクエリ実行エンジン１１０から直接）受けると、コマンドの発行元であるクエリ実行エンジン１１０のスレッドとは非同期で、このコマンドを実行する。コプロセッサ１３０は、複数のコマンドを受けた場合には、ラウンドロビン方式で実行するようにこれら複数のコマンドをスケジュールすればよい。いくつかのコマンドが並列に実行されてもよい。
【００３７】
ある実施形態において、コマンドに関する入力データ（たとえばリレーショナルデータ）は、（クエリ実行エンジン１１０に対する）インターフェイスを通してフェッチされ、コマンドの結果（すなわちこの入力データに基づいてコプロセッサ１３０が生成した結果）は、このインターフェイスを通して書出される。
【００３８】
ある実施形態において、コプロセッサ１３０は、各コマンドの終了時にインターフェイスを通して完了状態をこのインターフェイスの完了データ構造に書出させる。クエリ実行エンジン１１０は、完了データ構造を用いてクエリ実行エンジン１１０の１つ以上のスレッドと再度同期させてもよい。
【００３９】
図２は、ある実施形態に従う、コプロセッサ２００の一例を示すブロック図である。コプロセッサ２００は図１のコプロセッサ１３０であってもよい。コプロセッサ２００は、メモリインターフェイス２１０と、コマンドスケジューラ２２０と、デコンプレッサ２３０と、クエリパイプ２４０と、メッセージパイプ２５０とを含む。メッセージパイプ２５０は、メモリのコピーおよびメッセージの送達を扱う。クエリパイプ２４０は、デコンプレッサ２３０が圧縮された入力データ（たとえばリレーショナルテーブルからのデータ）を圧縮解除した後の、スキャンコマンドまたはルックアップコマンド等の、１つ以上のクエリコマンドを扱う。
【００４０】
デコンプレッサ２３０は、単一フォーマットで圧縮されたデータのみを圧縮解除するように構成されてもよい。これに代わるものとして、デコンプレッサ２３０は、あるフォーマットで圧縮されたデータおよび別のフォーマットで圧縮された他のデータを圧縮解除するように構成されてもよい。ある実施形態では、コプロセッサ２００はデコンプレッサ２３０を含まない。コプロセッサ２００がデータを受けたときに、コプロセッサ２００が受けたデータが圧縮されていない（たとえば既に圧縮解除されている）場合、圧縮解除は不要であろう。また、コンプレッサ２００が、圧縮されたデータを先ず圧縮解除せずに圧縮されたデータに対して直接作業を行なうように構成されている場合、データが圧縮されていても圧縮解除は不要であろう。
【００４１】
パイプ２４０および２５０は各々、異なる組のコマンドキューと、任意でコマンドフォーマットと、関連付けられている。ハイパーバイザ１２０は、（ＣＣＢに反映されている）コマンドが正しいパイプのコマンドキューに向けられるのを保証するように構成される。ＣＣＢの中のフラグビットが、ＣＣＢがメッセージコマンドなのかまたはクエリコマンドなのか示してもよい。
【００４２】
パイプ２４０および２５０は各々、マルチスレッド化されて複数のコマンドを一度に実行することが可能であってもよい。マルチスレッドの程度はソフトウェアに公開されていない。コマンドスケジューラ２２０は、コマンドは並列処理が可能であるという前提で、利用可能なスレッド上にコマンドをスケジュールしてもよい。あるコマンドを別のコマンドの後ろにシリアライズする必要がある場合は、これら２つのコマンドを同一のコマンドキューの中に入れて適切なシリアライズフラグを両方のコマンドにセットしてもよい。
【００４３】
図には示されていないが、コプロセッサ２００は、メモリインターフェイス２１０を通してストリーミングされているときのデータを格納、または、その一例がブルームフィルタであるルックアップベクトル等のルックアップ動作で使用されるデータを格納するための、一定量のメモリを含む。現代のチップは概ねメインコアまたは汎用マイクロプロセッサ用の１つ以上のキャッシュで構成されているので、コプロセッサ２００のメモリの大きさは極めて小さい場合がある（たとえば４ＫＢ）。
【００４４】
クエリ実行エンジン１１０はリレーショナルテーブルデータを「観察し」それに応じて動作を実行するが、コプロセッサ２００はベクトルまたは一次元配列のデータを「見る」またはそれに対して動作を行なうだけである。言い換えると、コプロセッサ２００は複数の列または行識別子を「観察」しない。むしろ、コプロセッサ２００は、如何にしてデータが論理的に配列または格納されているかということについては不確かである。したがって、コプロセッサ２００に命令を与えるとき、クエリ実行エンジン１１０は、コプロセッサ２００が実行する動作の出力が特定の順序で格納されることを保証する。そうでなければ、クエリ実行エンジン１１０は、出力がテーブルのどの部分に対応するのかわからないであろう。順序を保つ１つの方法は、クエリ実行エンジン１１０が、どのテーブルデータセットがどのＣＣＢに対応するのか追跡することであり、この場合の各ＣＣＢは固有のＣＣＢ識別子を含む。そうすると、特定のＣＣＢに基づいてコプロセッサ２００が生成した出力は、この特定のＣＣＢの識別子を含むことになり、クエリ実行エンジン１１０は、出力が論理テーブルのどの部分に対応するか判断することができる。たとえば、クエリ実行エンジン１１０は、テーブルＥｍｐｌｏｙｅｅの行１００１〜２０００をＣＣＢ識別子４３２８９９と対応付ける対応付けデータを格納してもよい。コプロセッサ２００は、識別子４３２８９９を有するＣＣＢを受けて処理することにより、特定の場所に格納される出力を生成する。
【００４５】
これに代わるものとして、クエリ実行エンジン１１０は、ＣＣＢ識別子を追跡する代わりに、テーブルのある部分（たとえばテーブルＥｍｐｌｏｙｅｅの行１００１〜２０００）を示すテーブルデータを、コプロセッサ２００によって生成された出力を格納すべき場所を示す出力場所データ（たとえば物理アドレス１２９８７３７＋４ＫＢ）と対応付ける、対応付けデータを格納する。その後、クエリ実行エンジン１１０がその格納場所に格納されている出力を調べるときに、クエリ実行エンジン１１０はこの対応付けデータを使用して、テーブルのどの部分がこの出力に対応しているか判断する。このように、コプロセッサ２００はその時々においてテーブルの異なる部分に対して動作を行なうが、また、クエリ実行エンジン１１０は複数のコプロセッサに対してテーブルの異なる部分に対して動作を行なうよう命令するかもしれないが、クエリ実行エンジン１１０は出力の順序を追跡することができる。
【００４６】
クエリの処理
図３は、ある実施形態における、スキャン動作を要求するクエリを処理するためのプロセス３００を示すフロー図である。ブロック３１０で、クエリ実行エンジン１１０は、１つ以上のテーブル等のデータオブジェクトを対象としこの１つ以上のデータオブジェクトのうちの少なくとも１つのスキャン動作を要求するクエリを受ける。たとえば、クエリ実行エンジン１１０は、ＳＱＬクエリを処理することにより、スキャン動作を含む１つ以上のデータベース動作を含む書換えられたクエリを生成してもよい。このクエリ実行エンジン１１０は、１つ以上の他のソフトウェアコンポーネントを実行するように、または、１つ以上の他のソフトウェアコンポーネントの実行を命令するように構成される。これに代わるものとしては、別のソフトウェアコンポーネントが、元のクエリを受け、クエリ実行エンジン１１０が処理するように構成されている、書換えられたクエリを生成する。
【００４７】
ブロック３２０で、クエリ実行エンジン１１０は、１つ以上の基準に基づいて、コプロセッサ１３０をクエリの処理に関与させるか否か判断する。この１つ以上の基準が示し得るものは、結果が過去に生成されキャッシュされたか否か、テーブル上にインデックスが存在しテーブルをスキャンする代わりにこのインデックスを用いてクエリに回答し得るか否か、テーブルのサイズ、その他である。たとえば、スキャンする必要があるテーブルのサイズが比較的小さい場合、コプロセッサ１３０を関与させると、コプロセッサ１３０を関与させずにクエリを実行するよりも、（たとえばクエリ実行エンジン１１０の命令を実行する汎用マイクロプロセッサを使用するという形で）より多くの作業が必要となる、または、より時間がかかるかもしれない。
【００４８】
これに加えてまたはこれに代えて、上記１つ以上の基準は、クエリ（または書換えられたクエリ）を異なるやり方で処理するのに要する相対コストを示してもよい。たとえば、クエリ実行エンジン１１０は、インデックスの使用、コプロセッサ１３０を使用せずにテーブルをスキャン、およびコプロセッサ１３０を使用してテーブルをスキャンといった異なる実行計画の下でクエリを実行するコストを推定するコスト推定要素を含んでいてもよい。その場合、クエリ実行エンジン１１０は、コストという観点で最も費用がかからない実行計画を選択する。「コスト」は、ＣＰＵの使用量、メモリの使用量、Ｉ／Ｏの使用量、およびネットワークＩ／Ｏの使用量といった、１つ以上のファクタに基づいていてもよい。
【００４９】
クエリ実行エンジン１１０が、コプロセッサ１３０をクエリの実行に関与させると判断した場合、プロセス３００はブロック３３０に進む。
【００５０】
ブロック３３０で、クエリ実行エンジン１１０は、ハイパーバイザ１２０に、１つ以上の命令のアドレス、入力データのアドレス、および出力データを格納する場所のアドレスを送る。上記１つ以上の命令は、クエリ実行エンジン１１０が生成するＣＣＢの形態であってもよい。ハイパーバイザ１２０は、このアドレスを仮想アドレスから物理アドレスに変換し、この物理アドレスを、コプロセッサ１３０のコマンドキューまたはバッファの中に置く。
【００５１】
クエリ実行エンジン１１０は、上記１つ以上の命令をメモリに格納させ（したがってこの命令はコプロセッサ１３０が読出すことができる）、その後、このクエリの実行に関連するまたは別のクエリに全体的に関連する他のタスクを実行してもよい。このようにして、コプロセッサ１３０によって行なわれる動作は、汎用マイクロプロセッサによって実行されるクエリ実行エンジン１１０が行なうタスクとは非同期で行なわれる。
【００５２】
先に述べたように、コンピュータシステム１００は複数のコプロセッサを含んでいてもよい。このため、クエリ実行エンジン１１０は命令（たとえばＣＣＢ）を複数のコプロセッサ各々に送ってもよい。このようにして、スキャン動作またはルックアップ動作を複数の「ミニ」動作に分割し、異なる「ミニ」動作をそれぞれのコプロセッサに実行させてもよい。たとえば、特定のテーブルが１０，０００行を含み１０個のコプロセッサがあるとする。その場合、クエリ実行エンジン１１０は互いに異なる１０個のＣＣＢを生成すればよく、各ＣＣＢは、この特定のテーブルの１，０００行からなる異なる１組の行にアクセスするための異なるアドレスを示す点を除いて、他のＣＣＢと同様である。このようにして、１０個のコプロセッサは、この特定のテーブルの異なる部分に対して並列に動作する。
【００５３】
これに加えてまたはこれに代えて、ブロック３３０は、クエリ実行エンジン１１０が、１つ以上の基準に基づいて、ＣＣＢの送り先として複数のコプロセッサからなるサブセットを選択することを含む。たとえば、クエリ実行エンジン１１０にとって必要なのは、各々スキャン動作を実行する（なおこのスキャン動作はそれぞれテーブルデータの異なる組に対して行なわれる）合計１０個のコプロセッサのうち、３つのコプロセッサのみの場合がある。１つ以上のコプロセッサを選択するためにクエリ実行エンジン１１０が使用する１つ以上の基準は、各コプロセッサの現在の負荷、各コプロセッサのレイテンシ、および／または各コプロセッサの処理履歴であってもよい。たとえば、クエリ実行エンジン１１０は、現在最も「負荷」が小さいまたは最も忙しくない３つのコプロセッサを選択する。コプロセッサの負荷は、コプロセッサの１つ以上のコマンドキューの中にあるコマンドの数に反映されていてもよい。その場合、特定のコプロセッサによる処理を待っているコマンドが多いほど、この特定のコプロセッサの負荷は大きい。
【００５４】
ブロック３４０で、コプロセッサ１３０は、上記１つ以上の命令を受け、この１つ以上の命令に反映されている１つ以上の動作を実行する。たとえば、コプロセッサ１３０は、ＣＣＢを受け、このＣＣＢに反映されている動作の種類を判断し、この動作を完了するのに必要なデータを読込み、この動作を実行し、（ブロック３５０で）動作結果をクエリ実行エンジン１１０に送らせる。コプロセッサ１３０によるコマンドの実行は、クエリ実行エンジン１１０（またはそのエージェントのうちの１つ）による、コプロセッサ１３０の１つ以上の内部レジスタへの書込によってトリガされてもよい。
【００５５】
スキャン動作
ある実施形態において、上記１つ以上の命令は、スキャン動作と、テーブルデータが格納されている１つ以上のアドレスを示す。コプロセッサ１３０は、テーブルデータを取出して、（上記１つ以上の命令において指定されている）値または値の範囲と、このテーブルデータを比較する。コプロセッサ１３０は、メモリ（たとえばメモリ１４０）を通してクエリ実行エンジン１１０からのテーブルデータを要求する。このメモリは、システム内のダイナミックＲＡＭでもチップ上のキャッシュメモリでもよい。テーブルデータは、ブロックに格納されていてもよく、６４ＫＢまたはそれ以上といったように比較的大きくてもよい。コプロセッサ１３０は、一次元配列としてのこれらのブロック各々にアクセスすればよい。列指向データベースでは、データは一次元アレイであり、コプロセッサ１３０はこれを容易に読出すことができる。行優先データベースの場合、データは、コプロセッサ１３０によって処理される前に、先ず列優先フォーマットに変換されてもよい。
【００５６】
テーブルデータが存在するブロックがメモリ内の不連続のブロックである場合、コプロセッサ１３０は（別々のジョブとして）各ブロックを別々に要求する。このような場合、クエリ実行エンジンは、（コプロセッサ１３０によって生成される）各ジョブの結果を「縫い合わせる」。たとえば、行優先データベースでは、データが跨っておりコプロセッサ１３０はＮ番目毎のデータを選択することになる。Ｎはコマンドにおいて指定されている。
【００５７】
コプロセッサ１３０は、比較を、「オン・ザ・フライ」で、すなわちテーブルデータがコプロセッサ１３０にストリーミングされているときに、実行してもよい。テーブル内のデータ要素が、１つ以上の命令において指定されている対象値または値の対象範囲と比較されると、コプロセッサ１３０は（直ちにまたは最後に）、このデータ要素を格納するのに使用されているメモリを、テーブルデータからの新たなデータ要素で上書きしてもよい。
【００５８】
コプロセッサが実行するように構成されている比較動作のタイプの例には、〜より大きい（＞）、未満（＜）、等しい（＝＝）、等しくない（！＝）、〜以上（＞＝）、〜以下（＝＜）が含まれる。
【００５９】
意味を認識した圧縮
ある実施形態において、コプロセッサ１３０は、圧縮されたデータに対して動作するように構成される。意味を意識しない（non-semantic-aware）１つ以上の圧縮技術を用いて圧縮されるデータと、意味を意識した（semantic-aware）１つ以上の圧縮技術を用いて圧縮されるデータがある。意味を意識しない圧縮技術を用いて圧縮されたデータは、先ず圧縮解除される必要があり、圧縮解除されたデータに対して動作を行なうことができる。意味を意識した圧縮技術を用いて圧縮されたデータは、動作（たとえば数またはストリングの比較）の実行前に圧縮解除する必要はない。意味を意識した圧縮技術の一例として、ランレングス符号化（run-length encoding）（ＲＬＥ）がある。
【００６０】
ＲＬＥは、データ圧縮の一形態であり、データの連なり（すなわち多数の連続するデータ要素における同一データ値の連続）を、元の連なりとしてではなく単一データとして格納しカウントする。このような連なりが多数含まれているデータにとってこれは最も有用である。一例として、テーブルの１つの列に、以下に示すシーケンスデパートメント識別子が含まれているとする。
【００６１】
ＡＡＡＡＡＡＢＢＢＣＣＣＣＣＣＣＣＣＤＤＤＤＤＡＡＡＡ
上記シーケンスにＲＬＥデータ圧縮アルゴリズムを適用すると、出力は、６Ａ３Ｂ８Ｃ５Ｄ４Ａとなる。このランレングス符号は、元の２６文字をわずか１０文字で表わしている。ＲＬＥでは、入力シーケンスにおける１つのデータ値の連なりが長いほど、大きく圧縮される。
【００６２】
ブロック３４０に戻ると、テーブルデータはランレングス符号化されてもよい。このため、コプロセッサ１３０に読込む必要があるテーブルデータの数、および、ランレングス符号化されたテーブルデータに対してコプロセッサ１３０が実行する必要がある比較の数は、テーブルデータがランレングス符号化されない場合と比較すると、相当に少なくなるであろう。上記例の場合、コプロセッサ１３０は、２６の比較（すなわち２６文字各々につき１つの比較）を実行する代わりに、５つの比較を実行するだけでよい。
【００６３】
ランレングス符号化されたデータに対するスキャン動作の実行結果は、それ自体がランレングス符号化されてもよい。この結果は最終的にクエリ実行エンジン１１０によって処理されてもよい。上記例の場合、特定のテーブルのある行が、デパートメント識別子「Ａ」を含むか否かについての判断の結果は、６Ｙ１６Ｎ４Ｙとなるであろう。このうちの「Ｙ」は判断の肯定結果を表わし、「Ｎ」は判断の否定結果を表わす。
【００６４】
これに代わるものとして、ランレングス符号化されたデータに対するスキャン動作の実行結果はランレングス符号化されなくてもよい。その代わりに結果は「圧縮解除」されてもよい。上記例の場合、特定のテーブルのある行が、デパートメント識別子「Ａ」を含むか否かについての判断の結果は、ＹＹＹＹＹＹＮＮＮＮＮＮＮＮＮＮＮＮＮＮＮＮＹＹＹＹとなるであろう。この実施形態では、スキャン動作の間、文字「Ｃ」に対し１つの比較が実行されているが、コプロセッサ１３０は、ランレングス符号化されたデータ要素に対して８つの否定表示（たとえば「Ｎ」または「０」）を生成する。
【００６５】
ルックアップ動作
ＳＱＬクエリは、データベース内の複数のテーブルを相互参照する必要があることが多い。このようなクエリの処理は通常、セット‐インターセクト動作を必要とする。現在、セット‐インターセクト動作は、汎用マイクロプロセッサ上で走らせているソフトウェアによって実行され、このソフトウェアは、関与しているテーブル列の基数が小さいときにはベクトルルックアップ（たとえばブルームフィルタルックアップ）を利用する。ある実施形態に従うと、ベクトルルックアップ（またはルックアップ動作）は、ハードウェアに実装され、これはソフトウェアで実装するよりも遥かに速いであろう。
【００６６】
このため、ある実施形態において、（ブロック３３０の）１つ以上の命令は、ルックアップ動作、テーブルデータが格納されている１つ以上のアドレス、および、ルックアップベクトルまたはアレイが格納されている１つ以上のアドレスを示す。テーブルデータ（またはルックアップベクトル）が格納されているこの１つ以上のアドレスは、２つのアドレス（たとえば開始アドレスと終了アドレス）であっても、オフセット付きの１つのアドレスであってもよい。コプロセッサ１３０は、このルックアップベクトルとテーブルデータをコプロセッサ１３０に送らせ、テーブルデータ内の各データ要素について、ルックアップベクトル内のデータ要素のルックアップを実行する。言い換えると、コプロセッサ１３０は、データ要素（またはデータ要素のハッシュ）を用いて、ルックアップベクトルにおける位置を識別しルックアップベクトルからその位置にあるデータを取出す。
【００６７】
ルックアップ動作を要求するクエリの例
ルックアップ動作を要求し得るクエリの一例として、「富裕層の」郵便番号に居住している「貧しい」人々に関する情報を要求するクエリがある。「貧しい」人を年収３万ドル未満の人と考えてもよく、「富裕層の」郵便番号を所得の中央値が１０万ドルを超える層の郵便番号と考えてもよい。この例において、コプロセッサ１３０は、少なくとも２つのデータオブジェクトから、すなわちルックアップベクトルと人物テーブルからのデータを必要とする。ルックアップベクトルは（たとえば１ビットで）郵便番号が「富裕層」のものか否かを示す。ルックアップベクトルは、予め（すなわちクエリを受ける前に）計算されていてもよく、クエリを受けたことに応じて計算されてもよい。
【００６８】
人物テーブルは、多数の人々に関する情報を含み、このテーブルは、少なくとも３つの列、すなわち、各個人の名前の列と、各個人の給与の列と、各個人の郵便番号の列とを含む。ある側面において、郵便番号が富裕層のものか貧困層のものかを示すデータはディメンションテーブルであり、各個人に関する情報を含む人物テーブルはファクトテーブルである。ディメンションテーブルは通常ファクトテーブルよりも遥かに小さい。この例において、ルックアップベクトルはディメンションテーブルに基づいて生成されてもよい。関連して、ファクトテーブルは複数のデータオブジェクト（たとえばテーブル）によって表されてもよい。すなわち、あるデータオブジェクトが各個人の給与に関する情報を含み別のデータオブジェクトが各個人の郵便番号に関する情報を含んでいてもよい。
【００６９】
ルックアップベクトル
ルックアップベクトルの一例はブルームフィルタである。ブルームフィルタは、要素が集合のメンバーであるか否かテストするのに使用される確率的データ構造である。ブルームフィルタを使用するとき、偽陽性（false positive）の可能性はあるが偽陰性（false negative）の可能性はない。ブルームフィルタは１つ以上のハッシュ関数と関連付けられ、各ハッシュ関数は、要素をブルームフィルタ内の配列位置のうちの１つにマッピングする。
【００７０】
しかしながら、ルックアップベクトルが確率的である必要はない。たとえば、存在し得る郵便番号が１０，０００個しかなく、各郵便番号が、その郵便番号が「富裕層の」ものか否かを示す１ビットと対応付けられているのであれば、ルックアップベクトルのサイズ（たとえば１．２５ＫＢ）はルックアップベクトル全体をコプロセッサ１３０のメモリ（たとえばＳＲＡＭ）に嵌め込むのに十分小さいであろう。したがって、サイズ削減のためには確率的ルックアップベクトルは不要である。
【００７１】
図４は、ルックアップベクトル４００の一例の一部を示すブロック図である。ルックアップベクトル４００内の位置はそれぞれ異なる郵便番号と対応付けられている。言い換えると、郵便番号は、ルックアップベクトル４００にインデックスを付けるために使用される。ルックアップベクトル４００内の各位置は、対応する郵便番号が「富裕層の」郵便番号（「１」）か「貧困層の」郵便番号（「０」）かを示す１ビットを含む。
【００７２】
コプロセッサ１３０のメモリにルックアップベクトル全体を嵌め込むことができない場合は、（確率的ルックアップベクトルを生成する以外に）（ａ）ルックアップベクトルを分裂させて（すなわち分割して）ルックアップベクトルの各部分に対してその都度コプロセッサ１３０がテーブルデータを読込むようにするか、または、（ｂ）複数のコプロセッサがある実施の形態において、それぞれのコプロセッサが、格納するルックアップベクトルの一部分に対して一度だけテーブルデータを読込むようにすればよい。
【００７３】
前者の場合において、コプロセッサ１３０がたとえばルックアップベクトルの四分の一しかそのメモリに嵌め込むことができないのであれば、コプロセッサ１３０は、個人の郵便番号を示すテーブルデータを４回読出す（すなわちコプロセッサ１３０が読込むルックアップベクトルの各部分につき一回）。ある個人の郵便番号がどの回でもテーブルデータにおいて識別されなければ、その個人についての結果は否定判定を示すであろう。毎回のテーブルデータの結果は、人物テーブルに示される各個人に対し、１つの長いビット配列であってもよい。
【００７４】
後者の場合において、４つの異なるコプロセッサがそれぞれルックアップベクトルの異なる四分の一を格納し、個人の郵便番号を示すテーブルデータを一度読込んでから、テーブルデータに反映されている各郵便番号を探してルックアップベクトルのルックアップを実行すればよい。この場合も、各コプロセッサからのルックアップ動作の結果は、人物テーブルに示される各個人に対する、１つの長いビット配列であってもよい。
【００７５】
スキャンまたはルックアップ動作の結果の生成
ある実施形態において、コプロセッサ１３０は、上記１つ以上の命令に反映されている１つ以上の動作を実行した結果として、特定の出力フォーマットを生成する。この特定の出力フォーマットの一例はビットベクトルであり、ビットベクトル内の各位置は真または偽を示す。たとえば、「１０」が対象とする値であり、比較が、この対象値がテーブルからのあるデータ値またはデータ要素よりも大きいか否か判断することであれば、比較の結果は、（ａ）データ値が１０よりも大きければ真であり、（ｂ）データ値が１０以下であれば偽である。
【００７６】
このベクトル内の各位置は、入力（たとえばテーブル）データから受けたデータ値またはデータ要素に対応する。たとえば、上記ルックアップ動作の例の場合、コプロセッサ１３０は、「富裕層の」郵便番号に居住している「貧困層の」人々を反映する１ビットベクトルを生成する。このビットベクトルを生成するために、コプロセッサ１３０は、人物テーブルの郵便番号列からデータを読込み、読込んだデータに示される各人物について、ルックアップベクトルに基づき、この人物が「富裕層の」郵便番号に居住しているか否か判断する。このビットベクトル内の各ビットは、人物テーブルの中の異なる人物が「富裕層の」郵便番号に居住しているか否かを示す。コプロセッサ１３０はその後、ビットベクトルを汎用マイクロプロセッサに送り、これはビットベクトルを用いて、「貧しい」とも考えられる人物を識別する。たとえば、（ビットベクトルに示される）富裕層の郵便番号に居住している各人物について、汎用マイクロプロセッサは人物テーブルの対応する行をルックアップしてその人物が「貧しい」か否か判断する。
【００７７】
ビットベクトルのサイズは比較的小さいので、汎用マイクロプロセッサによるこのビットベクトルの処理は比較的速く、汎用プロセッサが入力データを直接処理する場合よりも遥かに速い。さらに、このビットベクトルを格納するのに必要なキャッシュメモリスペースは、（データの大きな列等の）入力データを格納するのに必要なキャッシュメモリ空間よりも大幅に小さい。
【００７８】
スキャンまたはルックアップ動作の結果の生成
プロセス３００に戻って、ブロック３５０で、コプロセッサ１３０は、スキャン動作（またはルックアップ動作）の結果をクエリ実行エンジン１１０が利用できるようにする。ブロック３５０は、コプロセッサ１３０が、動作の結果を、その動作を開始したクエリ実行エンジン１１０からの１つ以上の命令に指定されているメモリに送ることを含み得る。たとえば、クエリ実行エンジン１１０は、ＣＣＢを生成し、このＣＣＢにおいて、対応する動作の結果が、たとえば、ＤＲＡＭ、共有Ｌ３キャッシュ、または（たとえばクエリ実行エンジンを実行する、または、元のコマンドを生成したマイクロプロセッサと異なる）特定のマイクロプロセッサのキャッシュに送られることになっていることを示す。
【００７９】
ブロック３５０はさらに、コプロセッサ１３０がフラグをセットすることを含み得る。このフラグはセットされると動作の完了を示す。このフラグ設定は、（１）ハイパーバイザ１２０が新たな要求をコプロセッサ１３０のコマンドキューに挿入し（２）クエリ実行エンジン１１０が結果を取出すよう合図する信号として機能する。
【００８０】
これに代えて、コプロセッサ１３０は、クエリ実行エンジン１１０にアクセス可能な特定のメモリ要素（ＲＡＭまたはキャッシュ）に動作結果を常に送るようにプログラムされる。
【００８１】
これに代わるものとして、コプロセッサ１３０は、スキャン動作の結果をクエリ実行エンジン１１０が利用できるようにする代わりに、結果を別のコプロセッサに送る。先に述べたように、コンピュータシステム１００は複数のコプロセッサを含み得る。複数のコプロセッサは連続して接続されてもよい。２つのコプロセッサ間の各接続がＦＩＦＯバッファを含み「生産」コプロセッサが「消費」コプロセッサによる結果処理速度よりも速く結果を生成できるようにしてもよい。最終的に、「チェーン」内の最後のコプロセッサが、クエリ実行エンジン１１０にアクセス可能なＲＡＭまたはキャッシュ内等の指定された宛先に、結果を送る。
【００８２】
ブロック３６０で、クエリ実行エンジン１１０は、結果を処理し、元のクエリの最終結果を生成するために１つ以上の他の動作を実行する。コプロセッサ１３０がスキャンまたはルックアップ動作を実行する間、クエリ実行エンジン１１０を実行する汎用マイクロプロセッサは、アイドル状態であってもよく、または、クエリ実行エンジン１１０もしくは別のプロセスによって利用されてもよい。たとえば、クエリ実行エンジン１１０は、クエリが要求する１つ以上の他の動作、または、そのクエリには全く関連性がないが別のクエリに関連する１つ以上の他の動作を実行してもよい。
【００８３】
スキャン動作の一例として、クエリは、特定範囲の日付の中で開始された購入注文のＩＤおよび価格を要求する場合がある。この例において、コプロセッサ１３０が実行するスキャン動作は、複数の購入注文の日付情報を読込むことを含み、この日付情報は、購入注文テーブルに反映されている。このスキャン動作の結果は一連のビット（たとえばビットベクトル）であってもよく、このビットは各々、対応する購入注文が、指定された日付範囲の中で開始されたか否かを反映する。コプロセッサ１３０は、クエリ実行エンジン１１０にアクセス可能なメモリにその結果を送り、クエリ実行エンジン１１０が定期的にチェックするフラグをセットすることによって、スキャン動作の完了をクエリ実行エンジン１１０に知らせてもよい。そうすると、クエリ実行エンジン１１０は、このビットを用い、購入注文テーブルにおいて、指定された日付範囲の中で開始された購入注文に対応するエントリを識別する。次に、クエリ実行エンジン１１０は、識別されたエントリにおいてＩＤおよび価格を識別し、この情報をクエリの結果として返す（たとえば表示する）。また、クエリは、クエリの結果が価格の降順で並べられるよう指定してもよい。このように、クエリ実行エンジン１１０は、コプロセッサ１１０によって実行されたスキャン動作の結果を受けた後に、１つ以上の動作を実行する。
【００８４】
ルックアップ動作の例として、クエリが、コプロセッサ１３０にルックアップ動作の実行を命令することに加えて、「富裕層の」郵便番号に居住している「貧しい」人々を識別しようとするものである場合、クエリ実行エンジン１１０は、コプロセッサ１３０（または別のコプロセッサ）に、人物テーブルに対してスキャン動作を実行して年収３万ドル未満の人すべてを識別するよう命令していてもよい。このスキャン動作の結果は（ルックアップ動作の結果と同様）一連のビット（たとえばビットベクトル）の形態であってもよく、このうちの各ビットは人物テーブルに示される異なる人物に対応する。ある実施形態において、クエリ実行エンジン１１０は、入力としてのスキャン動作の結果およびルックアップ動作の結果に対してＡＮＤ演算を実行する。これに代わるものとして、コプロセッサ１３０（または別のコプロセッサ）をＡＮＤ演算を実行するようプログラムしてもよい。この実施形態において、クエリ実行エンジン１１０は、ルックアップ動作の結果に対する（たとえば仮想）アドレスおよびスキャン動作の結果に対するアドレスをオペランドが含む別のＣＣＢを作成してもよい。
【００８５】
先に説明したように、ルックアップベクトルのサイズが、一度でコプロセッサ１３０のメモリに全体が嵌らないサイズの場合がある。先に述べた２つの場合のうちの一方において、ルックアップベクトルは４つの「ミニ」ベクトルに分割されコプロセッサ１３０は各ミニベクトルに対して別々に動作するので、コプロセッサ１３０が各人物について４回郵便番号データを（人物テーブルから）読込むことが必要である。このルックアップ動作を実行するコプロセッサ１３０によって生成された総合結果は、別々の４つのビットアレイを含み得る。これらは最終的にともにＯＲ演算されて１つのビットアレイ（この場合も人物テーブルに示される各人物について１つ）が生成される。このＯＲ演算ステップ（３つのＯＲ演算を含み得る）は、クエリ実行エンジン１１０が実行してもよい。これに代えて、コプロセッサ１３０がこのＯＲ演算を実行するようにプログラムされてもよい。
【００８６】
上記２つの場合のうちの他方では、クエリ実行エンジン１１０が、４つの異なるコプロセッサに、ルックアップベクトルの異なる部分をそれぞれ用いてルックアップ動作を実行するようにさせる。次に、コプロセッサのうちの１つからの結果を、それ以外のコプロセッサ各々からの結果とＯＲ演算することによって、１つのビットアレイ（人物テーブルに示される各人物について１つ）を生成する。この場合も、このＯＲ演算ステップは、クエリ実行エンジン１１０によって行なわれてもよく、またはコプロセッサのうちの１つによって行なわれてもよい。
【００８７】
上述のように、クエリ実行エンジン１１０は、どの人々が「富裕層の」郵便番号に居住しているか判断すると、その情報を用いて「貧困層」でもあると考えられる人々を判別する。
【００８８】
上記説明では、スキャン動作かルックアップ動作いずれかを実行すると述べているが、実施形態は、１つのコプロセッサが特定のクエリに対してスキャン動作を実行する一方で別のコプロセッサがこの特定のクエリに対してルックアップ動作を実行することを含み得る。このように、複数のコプロセッサが、同一のクエリに対して異なる動作を同時に実行してもよい。
【００８９】
本明細書に記載の実施形態の１つの利点は、データ量が多い動作を、汎用マイクロプロセッサから、このマイクロプロセッサから独立した１つ以上のコプロセッサに移すことによって、他のタスクのために使用できるようマイクロプロセッサを解放し得る点である。このため、コプロセッサは、コプロセッサに動作を実行させるクエリ処理ソフトウェアとは非同期で動作し得る。加えて、上記１つ以上のコプロセッサは、クエリ処理ソフトウェアを実行する汎用マイクロプロセッサよりも遥かに速く上記動作を実行し得る。
【００９０】
ハードウェアの概要
１つの実施形態によれば、ここに記載される技術は、１つ以上の特定用途向け演算装置によって実装される。特定用途向け演算装置は、ハードウェアによって技術を実装し得る、または技術を実装するように永続的にプログラミングされた１つ以上の特定用途向け集積回路（ＡＳＩＣ）もしくはフィールドプログラマブルゲートアレイ（ＦＰＧＡ）などのデジタル電子装置を含み得る、またはファームウェア、メモリ、他の記憶装置、もしくは組み合わせにおけるプログラムコマンドに従って技術を実装するようにプログラムされた１つ以上の汎用ハードウェアプロセッサを含み得る。このような特定用途向け演算装置は、技術を達成するために、カスタムプログラミングにカスタムハードワイヤードロジック、ＡＳＩＣ、またはＦＰＧＡを結合させ得る。特定用途向け演算装置は、デスクトップコンピュータシステム、ポータブルコンピュータシステム、携帯用デバイス、ネットワーキングデバイス、または、技術を実装するためにハードワイヤードロジックおよび／もしくはプログラムロジックを組み込んだ任意の他の装置であってもよい。
【００９１】
たとえば、図５は、本発明の実施形態が実装され得るコンピュータシステム５００を示すブロック図である。コンピュータシステム５００は、バス５０２または情報を通信するための他の通信機構と、情報を処理するためにバス５０２に結合されたハードウェアプロセッサ５０４とを含む。ハードウェアプロセッサ５０４は、たとえば、汎用マイクロプロセッサであってもよい。
【００９２】
コンピュータシステム５００は、情報およびプロセッサ５０４によって実行されるコマンドを格納するためにバス５０２に結合された、ランダムアクセスメモリ（ＲＡＭ）または他の動的記憶装置などのメインメモリ５０６も含む。メインメモリ５０６は、プロセッサ５０４によって実行されるコマンドの実行中に一時変数または他の中間情報を格納するためにも使用され得る。このようなコマンドは、プロセッサ５０４にアクセス可能な非一時的な記録媒体に格納されると、コマンドにおいて指定された動作を行なうようにカスタマイズされた特定用途向けマシンにコンピュータシステム５００を変える。
【００９３】
コンピュータシステム５００は、プロセッサ５０４のための静的情報およびコマンドを格納するためにバス５０２に結合された読出し専用メモリ（ＲＯＭ）５０８または他の静的記憶装置をさらに含む。磁気ディスク、光ディスク、またはソリッドステートドライブなどの記憶装置５１０が設けられ、情報およびコマンドを格納するためにバス５０２に結合される。
【００９４】
コンピュータシステム５００は、コンピュータのユーザに対して情報を表示するための陰極線管（ＣＲＴ）などのディスプレイ５１２にバス５０２を介して結合され得る。英数字および他のキーを含む入力装置５１４は、プロセッサ５０４に対して情報およびコマンド選択を伝えるためにバス５０２に結合される。別のタイプのユーザ入力装置は、方向情報およびコマンド選択をプロセッサ５０４に伝えるための、およびディスプレイ５１２上でのカーソル移動を制御するための、マウス、トラックボール、またはカーソル方向キーなどのカーソル制御５１６である。この入力装置は、通常、第１の軸（たとえばｘ）および第２の軸（たとえばｙ）という２つの軸において２つの自由度を有し、これによって面における位置をこの装置が指定できる。
【００９５】
コンピュータシステム５００は、カスタマイズされたハードワイヤードロジック、１つ以上のＡＳＩＣもしくはＦＰＧＡ、ファームウェアおよび／またはプログラムロジックをコンピュータシステムと組み合わせて使用してここに記載する技術を実装し、コンピュータシステム５００を専用マシンとする、または専用マシンへとプログラミングする。一実施形態によれば、ここでの技術は、メインメモリ５０６に含まれる１つ以上のコマンドの１つ以上のシーケンスをプロセッサ５０４が実行することに応答してコンピュータシステム５００によって行なわれる。このようなコマンドは、記憶装置５１０などの他の記録媒体からメインメモリ５０６に読込まれ得る。メインメモリ５０６に含まれるコマンドのシーケンスを実行することにより、ここに記載の処理ステップがプロセッサ５０４によって実行される。代替的な実施形態において、ハードワイヤード回路は、ソフトウェアコマンドの代わりに、またはソフトウェアコマンドと組み合わせて使用され得る。
【００９６】
ここで使用される用語「記録媒体」は、特定の方法でマシンを動作させるデータおよび／またはコマンドを格納する任意の非一時的な媒体をいう。このような記録媒体は、不揮発性の媒体および／または揮発性の媒体を含み得る。不揮発性の媒体は、たとえば、記憶装置５１０などの光ディスク、磁気ディスク、またはソリッドステートドライブを含む。揮発性の媒体は、メインメモリ５０６などの動的メモリを含む。記録媒体の一般的な形式は、たとえば、フロッピー(登録商標）ディスク、フレキシブルディスク、ハードディスク、ソリッドステートドライブ、磁気テープもしくは任意の他の磁気データ記録媒体、ＣＤ−ＲＯＭ、任意の他の光データ記録媒体、穴のパターンを伴う任意の物理媒体、ＲＡＭ、ＰＲＯＭ、およびＥＰＲＯＭ、ＦＬＡＳＨ−ＥＰＲＯＭ、ＮＶＲＡＭ、任意の他のメモリチップもしくはカートリッジを含む。
【００９７】
記録媒体は、伝送媒体とは異なるが、伝送媒体と併せて使用され得る。伝送媒体は、記録媒体間の情報の転送に関わる。たとえば、伝送媒体は、バス５０２を包含するワイヤを含む、同軸ケーブル、銅線、および光ファイバを含む。伝送媒体は、電波および赤外線データ通信時に生成されるような音波または光波の形式を取り得る。
【００９８】
さまざまな形式の媒体は、プロセッサ５０４が実行する１つ以上のコマンドの１つ以上のシーケンスの搬送に関わり得る。たとえば、コマンドは、リモートコンピュータの磁気ディスクまたはソリッドステートドライブ上に最初は担持され得る。リモートコンピュータは、そのダイナミックメモリにコマンドをロードし、モデムを用いて電話回線を介してコマンドを送ることができる。コンピュータシステム５００内のモデムは、電話回線上のデータを受け、赤外線送信器を使用してデータを赤外線信号に変換することができる。赤外線検知器は、赤外線信号で運ばれたデータを受けることができ、適切な回路によってこのデータをバス５０２上に置くことができる。バス５０２はデータをメインメモリ５０６に送り、このメインメモリからプロセッサ５０４はコマンドを取出して実行する。メインメモリ５０６が受けたコマンドは、プロセッサ５０４による実行の前または後に記憶装置５１０上に任意に格納され得る。
【００９９】
コンピュータシステム５００は、バス５０２に結合された通信インターフェイス５１８も含む。通信インターフェイス５１８は、ローカルネットワーク５２２に接続されたネットワークリンク５２０に結合する双方向データ通信を提供する。たとえば、通信インターフェイス５１８は、統合サービスデジタル網（ＩＳＤＮ）カード、ケーブルモデル、衛星モデム、またはモデムであり対応するタイプの電話回線へのデータ通信接続を提供してもよい。別の例として、通信インターフェイス５１８は、ローカルエリアネットワーク（ＬＡＮ）カードであり対応のＬＡＮへのデータ通信接続を提供してもよい。無線リンクも実装され得る。このような実装例において、通信インターフェイス５１８は、さまざまなタイプの情報を表わすデジタルデータストリームを運ぶ電気信号、電磁信号、または光信号を送信および受信する。
【０１００】
ネットワークリンク５２０は、１つ以上のネットワークを介して他のデータ装置へのデータ通信を通常は提供する。たとえば、ネットワークリンク５２０は、ローカルネットワーク５２２を介し、ホストコンピュータ５２４へ、または、インターネットサービスプロバイダ（ＩＳＰ）５２６によって運営されるデータ機器へ、接続を提供し得る。そうすると、ＩＳＰ５２６は、現在一般的に「インターネット」５２８と呼ばれている全世界パケットデータ通信網を介してデータ通信サービスを提供する。ローカルネットワーク５２２およびインターネット５２８はいずれも、デジタルデータストリームを運ぶ電気信号、電磁信号、または光信号を使用する。コンピュータシステム５００へおよびコンピュータシステム５００からデジタルデータを運ぶ、さまざまなネットワークを介する信号、および、ネットワークリンク５２０上の、通信インターフェイス５１８を介する信号は、伝送媒体の形態の例である。
【０１０１】
コンピュータシステム５００は、ネットワーク、ネットワークリンク５２０、および通信インターフェイス５１８を介して、メッセージの送信、およびプログラムコードを含むデータの受信を行ない得る。インターネットの例において、サーバ５３０は、インターネット５２８、ＩＳＰ５２６、ローカルネットワーク５２２、および通信インターフェイス５１８を介してアプリケーションプログラムのための要求されたコードを送信し得る。
【０１０２】
受信されたコードは、受信され次第プロセッサ５０４によって実行され得る、および／または記憶装置５１０に格納され得る、または、後で実行するために他の不揮発性記憶装置に格納され得る。
【０１０３】
上記明細書では、実装毎に異なり得る多数の具体的な詳細を参照しながら本発明の実施形態を説明している。このため、明細書および図面は、限定的ではなく例示的な意味で考慮されねばならない。発明の範囲の唯一かつ排他的な指標および出願人が意図する発明の範囲は、本願に由来する一組の請求項の、このような請求項の元になる特定の形式の、後の任意の修正が含まれる、文言上のかつ均等物の範囲である。
【図１】
0006320393.tif 000002
【図２】
0006320393.tif 000003
【図３】
0006320393.tif 000004
【図４】
0006320393.tif 000005
【図５】
0006320393.tif 000006