JPH05128164A - データベース処理装置 - Google Patents

Abstract

(57)【要約】 【目的】 機能レベル並列化を利用してデータベース動
作の全体的な処理速度を従来技術によるデータベース処
理装置により達成されるもの以上に高める。 【構成】 中央処理複合体に付加されたコプロセッサと
して機能する処理装置３００は、ホストメモリシステム
においてフィールドをソート、マージ、ジョイン、サー
チ及び操作するようなデータベース処理に必要とされる
機能を効率的に実行する。メモリインターフェイス及び
フィールドエキストラクタ／アセンブラ３０８、述語評
価器３０４、組み合わされたソート／マージ／ジョイン
ユニット３０２、ハッシュコード発生器３０６、並びに
マイクロコード化されたコントロールプロセッサ３１０
のような特別な機能ユニットは全て、区分されたワーキ
ングストア３１２を中心に構成される。各機能ユニット
は、それが実行する機能に従ってパイプライン化及び最
適化され、その照会の部分を効率的に実行する。全ての
機能ユニットは、コントロールプロセッサ３１０のもと
で同時に実行し、所望の結果が得られる。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】この発明は、データベース処理に
関する。

【０００２】

【従来の技術】データベース処理は、データ処理の分野
の、広く知られた商業的に重要な一形態である。データ
ベースは、レコードに組織化されたデータの集合であ
る。これらのデータレコード上で、又はこれらのデータ
レコードを用いて実行されるコンピュータ動作は、デー
タベース処理と呼ばれる。データベース管理プログラム
は、データベースにアクセスし、動作するために用いら
れるデータベース処理動作のパッケージである。

【０００３】データベース処理は通常、ソート（分
類）、マージ（併合）、サーチ（探索）およびジョイン
（結合）のような動作を含む。合併、共通部分および差
のような集合演算もまた、データベース処理の共通の特
徴である。従来、これらの動作は、非常に長いプロセッ
サ実行時間を必要とするソフトウェアアルゴリズムによ
って実行されていた。大規模なデータベースにおいて
は、プロセッサ実行時間は法外なものとなり、ソフトウ
ェアのデータベース管理プログラムの性能を著しく劣化
させる。

【０００４】データベース処理の１つの形態は、ある基
準を満たすレコードのサーチを含む。例えば、あるサー
チは、データベースの全てのレコードをスキャンし、あ
る値に等しい列‘Ｘ’を持つ全てのレコードを再生す
る。より複雑な場合には、サーチは、多くの列および値
を含む述語方程式に基づいてレコードをスキャンし、再
生する。データベースは非常に大規模（例えば、数億個
のレコード）であることがあるので、従来のソフトウェ
アデータベース管理システムで用いられるサーチアルゴ
リズムでは処理に何時間もかかることがある。

【０００５】データベース処理の他の形態は、データベ
ースレコードからのソートキーおよびサーチフィールド
の抽出を含む。ソートおよびサーチの応用では、サーチ
が定義されるソートキー又はフィールドはしばしばレコ
ード全体に拡張されてしまい、動作が進行する前に使用
可能なフォーマットに抽出されなければならない。ソー
トに関しては、このことは、各キーフィールドを得て、
１つの大きなキーとして扱うことができるようにそれら
を優先順位で連結することを意味する。サーチに関して
は、サーチされるテーブルの列が行から抽出されなけれ
ばならない。従来、これらおよび多くの他のデータベー
ス動作は、非常に長いＣＰＵ時間を使用するものであっ
た。

【０００６】データベース処理タスクのうちのいくつか
についてＣＰＵの負担をなくす解決策を得るための多く
の試みがなされてきた。そのような解決策の１つは、コ
ンピュータシステムに、もしそうでなければＣＰＵによ
り実行されるソートタスクを取り扱うための特別のソー
トプロセッサを設けることであった。図１はそのような
従来技術によるソートプロセッサを示す。

【０００７】図１のソートプロセッサ１００は、メイン
メモリバス１０２を中央処理装置１０４と共用する。メ
インメモリ１０６は、第１の組の通信ライン１０８を介
して中央処理装置１０４と通信し、第２の組の通信ライ
ン１１０を介してソートプロセッサ１００と通信する。
中央処理装置１０４およびソートプロセッサ１００は、
スタート制御ライン１１２および割込みライン１１４に
より相互に接続されている。

【０００８】データベース処理の間、周辺ファイル１１
６に記憶されたランダムなレコードは、メインメモリ１
０６に転送される。その後、制御プログラムは、ソート
プロセッサ１００の動作を開始させる。ファームウエア
制御のもとでは、キーワードがメインメモリ１０６から
ソートプロセッサ１００に転送され、その後ソートされ
る。ソートプロセッサ１００の自律的な動作は、中央処
理装置時間を節約し、プログラミングの労力を簡単化お
よび減少させる。

【０００９】図１のソートプロセッサ１００は並列ソフ
トウェアデータベース処理装置よりも優れているが、そ
れによる解決は部分的なものに過ぎなかった。ソートは
データベース処理の一形態に過ぎない。サーチ、テーブ
ルのジョイン、集合演算等の他の動作もまた、多くのＣ
ＰＵ時間がかかる。さらに、図１のソートプロセッサは
システムの他の部分から比較的自律的に動作するが、そ
の内部ソートアルゴリズムはマイクロコードにインプリ
メントされていた。従って、図１のソートプロセッサ
は、ＣＰＵにより実行されるソートプログラムと同一の
多くの制約によって制限されていた。

【００１０】図１のソートプロセッサ１００はまた、メ
インメモリ１０６を中央処理装置１０４と共用している
が、優先順位は低く、メモリバス１０２も１つしかない
ため、性能上の制約を受ける。単一のバス経路に沿って
のメインメモリアクセス時間の競合（もっとも、ソート
プロセッサを持たないシステムに対しては減少している
が）は、メインメモリ１０６とソートプロセッサ１００
との間のデータトラフィックに対するボトルネックを引
き起こす。

【００１１】データベース処理の他のアプローチは、伝
統的にＣＰＵによって取り扱われていたデータベース処
理タスクのうちのいくつかをベクトル処理エレメントに
負担させている。図２は、ベクトルプロセッサを利用し
た、そのような従来技術によるリレーショナルデータベ
ース管理システムの１つを示す。中央処理装置２００
は、スカラープロセッサ２０２およびベクトルプロセッ
サ２０４を含む。ベクトルおよびスカラープロセッサの
両者は、メインメモリ２０６および補助記憶装置２０８
にアクセスする。

【００１２】動作時には、アプリケーションプログラム
２１０から発生されたデータベースコマンドは、リレー
ショナルデータベース管理プログラム２１２により検査
される。データベース管理プログラム２１２は、コマン
ドを識別し、それを解析し、その後、決められた処理手
順を指定するコードを生成する。データベース処理の
間、必要なデータは、補助記憶装置２０８のページ領域
から、メインメモリ２０６のデータバッファ領域２１４
にロードされる。処理手順コードの制御のもとで、バッ
ファ領域２１４のデータは、ベクトル構造の形式に再配
置される。その結果得られるベクトルデータエレメント
は、ベクトル領域２１６に記憶される。

【００１３】処理手順コードがベクトルデータの処理を
示すとき、ベクトル命令のシーケンスがベクトルプロセ
ッサ２０４により実行される。このベクトル命令の制御
のもとで、ベクトルプロセッサ２０４は、指定された処
理手順に従ってベクトル領域２１６のデータを処理す
る。

【００１４】図２のデータベース管理システムの１つの
制約は、ベクトル処理に依拠している結果、データベー
スは、処理前にベクトル形式で生成され或いはベクトル
形式に変換されなければならないということである。こ
の変換処理は、それ自身、非常に多くの時間がかかり、
データベース処理動作を遅らせる。

【００１５】図２のデータベース管理システムの第２の
制約は、付随するベクトル処理ハードウェアが、命令レ
ベルでプログラムされるということである（すなわち、
データベース処理機能を実行させるために必要とされる
命令基本要素を書くことはプログラマに任されてい
る）。これらの命令は、ベクトル処理ハードウェアによ
り、データベース管理プログラム内で同期的に実行され
る。従って、データベース管理プログラムは、命令が実
行される間、単一のタスクのために使用される。更に、
各基本命令が実行されるときには、ＣＰＵ時間を必要と
する。従って、ＣＰＵは、基本要素の全ての系列が実行
されるまで、データベース処理から完全に解放されるこ
とはない。

【００１６】更に、図２のデータベース管理システムの
第３の制約は、ベクトル処理アプローチが、データベー
ス処理動作に間接レベルを付加することである。ベクト
ル形式のデータベースにおいては、関心のある実際のデ
ータを位置付けるために一連のポインタが用いられる。
あるテーブルにおける位置は、他のテーブルにおける他
の位置を指している、等々である。このような間接性な
いし連鎖は、データベース動作の処理時間を増大させ
る。

【００１７】

【発明が解決しようとする課題】この発明の１つの目的
は、機能レベル並列化を利用してデータベース動作の全
体的な処理速度を従来技術によるデータベース処理装置
により達成されるもの以上に高めることにある。

【００１８】この発明の他の目的は、システムメモリの
帯域幅速度において又はその近傍でデータベース動作を
処理することにある。

【００１９】この発明の更に他の目的は、付加処理装置
環境において、従来のソフトウェアデータベース処理プ
ログラムにより生成されるコマンドリストを処理するこ
とにある。

【００２０】

【課題を解決するための手段】これらの目的に従って、
本発明者らは、基本的なデータベース機能のための高速
処理を可能とするデータベース処理装置（従来のデータ
ベース処理装置と区別するため、以下データベースエン
ジンＤＢＥという）を提供した。好ましい実施例では、
データベースエンジンは、システムメモリにアクセス
し、そこから処理すべきデータを抽出するエキストラク
タ／メモリインターフェイスと、処理すべきデータを一
時的に記憶するためのローカルワーキングメモリと、そ
れぞれ特別なデータベース処理機能を実行する複数の自
律的処理エレメントと、データベース管理プログラムか
らのデータベースコマンドを部分機能に分解し、これら
の部分機能を処理エレメントに分散させるコントロール
プロセッサとを含む。

【００２１】基本的なデータベース機能の処理を支援
し、加速するためのハードウェアを設けることにより、
データベースエンジンは、多くのデータベース動作の実
行時間を著しく減少させることができる。

【００２２】このデータベースエンジンは、従来技術に
よるデータベース処理装置の多くの制約を克服すること
ができるという利点がある。図２のシステムと対照的
に、このデータベースエンジンは、ベクトル形式のレコ
ードを必要としない。従って、このデータベースエンジ
ンは、図２のシステムに存在する、処理コストの多くを
節減することができる。更に、図２のベクトルプロセッ
サと異なり、このデータベースエンジンは、中央処理装
置命令レベルプログラミングを必要とする代わりに、マ
クロコマンドで制御することができるものである。

【００２３】図１のシステムと異なり、このデータベー
スエンジンは、共通のデータバスによって、メインメモ
リのアクセス時間のためにＣＰＵと競合する必要がな
い。１つの実施例においては、このデータベースエンジ
ンは、システムページ記憶装置と接続される。このペー
ジ記憶装置は、データベースエンジンのための直接アド
レス可能なメインメモリとして働くが、システムの中央
処理装置に対してはページングメモリとしてのみ現れ
る。これによって、大規模なデータベースをページング
メモリに固定し、メインメモリアクセスのための中央処
理装置との競合を最小とすることができる。

【００２４】

【実施例】

ａ．データベースエンジン データベースエンジン（ＤＢＥ）は、リレーショナルデ
ータベースを迅速に評価するとともに、データの高速な
ソートを可能とするために設計されている専用のプロセ
ッサである。このデータベースエンジンは、ソート、マ
ージ、ジョイン、サーチおよびフィールドの操作を含む
データベースの処理で要求される中心的な機能を実行す
る。このデータベースエンジンは、専用のハードウェア
の装備で得られる、処理およびメモリアクセスの間のオ
ーバーラップを利用することで、同一の問題に対する周
知のソフトウェア手法の多くのもの以上に性能を向上す
ることができる。

【００２５】データベースエンジンの全体的な構成が図
３に示される。データベースエンジン３００は、５個の
ハードウェア処理エレメント（参照符号３０２〜３１０
で示される）とワーキングストア３１２からなる。２個
の内部のマルチビットのデータバス３１６、３１８によ
ってワーキングストア３１２および処理エレメント３０
２〜３１０間のデータの流れが形成される。内部のマル
チビットのコントロールバス３２０が処理エレメント間
のコントロールデータの経路を形成する。システムメモ
リバス３２２がエキストラクタ／メモリインターフェイ
スユニット３０８およびシステムメモリ（図３では示さ
れない）間に、外部的に設けられている。

【００２６】処理エレメント３０２〜３１０とワーキン
グストア３１２は、共同して働き、データベースの照会
を処理する。ソート／マージユニット３０２は、ソー
ト、マージ、ジョインおよび集合演算を行う。サーチ
は、述語評価器３０４によりなされる。ハードウェアの
ハッシュコード発生器３０６は、二つのデータベース上
の等結合の性能の改良のために設けられている。レコー
ドフィールドの抽出（エキストラクション）およびメモ
リアクセスの機能は、エキストラクタ／メモリインター
フェイスユニット３０８でなされる。前述の処理エレメ
ントでなされる動作は、コントロールプロセッサ３１０
の制御のもとで開始される。

【００２７】ホストシステム上で走るデータベースのア
プリケーションソフトウェアと関連してデータベースエ
ンジン３００が動作する。そのようなソフトウェアの一
例は、ＤＢ２（ＭＶＳの下で走る、ＩＢＭのデータベー
スアプリケーションプログラム）である。このアプリケ
ーションソフトウェアは、システムメモリへデータベー
スを読み込むのに必要なＩ／Ｏの全てを行う。また、こ
のアプリケーションソフトウェアは、データベースエン
ジンのコマンド、データベースオブジェクト記述子およ
び述語を作成し、そして、これらをデータベースエンジ
ン３００でアクセス可能なシステムメモリ内へ入れる。

【００２８】図４は、例示的なシステム環境におけるデ
ータベースエンジン３００のシステム接続を示す。この
図４のシステムでは、３個の中央処理装置（ＣＰ）４０
２〜４０６、Ｉ／Ｏチャンネル４０８およびシステムメ
モリ（主記憶装置４１０およびページ記憶装置４１２）
を有するマルチプロセッサシステムに組込まれたデータ
ベースエンジン３００が示されている。ページ記憶装置
は、中央処理装置（ＣＰ）４０２〜４０６に対するペー
ジメモリとして動作する。データのページは、中央処理
装置４０２〜４０６の制御の下で、ページ記憶装置から
主記憶装置へメモリデータバス４１４により転送され
る。そして、中央処理装置は、スイッチ或いはシステム
コントローラ４１６を介して主記憶装置内のデータをア
クセスする。そのようなシステムの一例は、米国特許第
４，４７６，５２４号および米国特許第４，３９４，７
３１号に開示されている。

【００２９】スイッチ４１６は、自己経路選択型の非閉
塞クロスバー形式のものである。すなわち、このスイッ
チ４１６は、主記憶装置４１０およびシステムエレメン
ト（３００、４０２〜４０８）のいずれかの間に、並び
にページ記憶装置４１２およびシステムエレメントの他
のいずれかの間に、同時的なマルチビットのデータ経路
を形成する。例えばスイッチ４１６は、ページ記憶装置
４１２およびデータベースエンジン３００間に第１のデ
ータ経路を形成し、一方、同時に中央処理装置４０２〜
４０６の１つおよび主記憶装置４１０間に第２のデータ
経路を形成する。

【００３０】変形例として、システムメモリ（主記憶装
置４１０およびページ記憶装置４１２）は、マルチポー
ト構成とされ、データベースエンジン３００およびシス
テムメモリ（４１０、４１２）間のデータ転送を直接的
に接続された広帯域のバス４２０、４２２によって行っ
ても良い。更に、参照符号４２４で示すようなＣＰデー
タバスを通るポートを通じて主記憶装置を中央処理装置
がアクセス可能としても良い。同様の接続をシステムメ
モリおよびＩ／Ｏチャンネル４０８間に設けることがで
きる。このような実施例では、スイッチ４１６は、削除
することができる。

【００３１】図４の構成により、要求を発生するため
に、中央処理装置を通る必要なしに、データベースエン
ジン３００がシステムメモリ（４１０、４１２）を直接
的にアクセスすることができる。従って、データベース
エンジンがメインメモリとしてページ記憶装置４１２を
アクセスできる。上述のように、図４のシステムでは、
ページ記憶装置４１２がＣＰ４０２〜４０６に対するペ
ージングメモリとして機能する。この構成により、デー
タベースエンジンがＣＰへの最小限の影響でもって、シ
ステム中で論理的に非同期なプロセッサとして動作でき
る。

【００３２】主記憶装置４１０およびページ記憶装置４
１２の両者への直接アクセスを設けているので、コマン
ドおよびデータレコードをデータベースエンジンがアク
セスするための多数の経絡が可能である。例えばデータ
ベースが主記憶装置からアクセスでき、部分が必要に応
じてページインできる。他のものとして、データベース
がページ記憶装置４１２に固定され、また、直接的にア
クセス可能としても良く、これにより、直接アクセス記
憶装置（ＤＡＳＤ）に対してデータベースを保管および
復元するのに伴うＩ／Ｏコストを回避できる。いずれに
しても、性能の要求、メモリの大きさおよび特定のシス
テムで利用できるメモリのタイプは、システムメモリ内
でデータベースがどこに位置すべきかを決定するのに考
慮すべきファクターである。

【００３３】図４のシステム環境に関して、データベー
スエンジン３００により必要とされるデータは、スター
ト信号が出されるより前にオペレーティングシステムに
よって、システムメモリ（主記憶装置４１０或いはペー
ジ記憶装置４１２のいずれか）に固定される。そして、
システムメモリ内（４１０、４１２）のどこにデータが
位置しているか、また、各固定されたブロックをどのよ
うな順序でアクセスするかを知らせるために、データベ
ースエンジンに対してページ或いはレコードのアドレス
のリストが与えられる。

【００３４】データベースエンジンの動作は、データベ
ースアプリケーションプログラムで構成されるコマンド
の系列によって始められる。このコマンドの系列は、デ
ータベースの動作を呼び出す前にオペレーティングシス
テムによりシステムメモリに置かれる。データベースエ
ンジン３００が一旦、起動されると、中央処理装置４０
２〜４０６のいかなる割込みもなしに、適宜に、コマン
ド、記述子およびデータを（システムメモリの外へ）ア
クセスする処理を非同期で行う。動作が完了する時に、
呼び出しプログラムに対して割込みがなされる。

【００３５】データベースエンジン３００の動作につい
て、ソート付きサーチコマンドの処理の例によって、図
３および図４を参照してより詳細に説明する。スタート
信号の受信によって、ホストＣＰＵが受けたデータベー
スコマンドがシステムメモリに存在することがコントロ
ールプロセッサ３１０に対して合図される。このスター
トの合図は、エキストラクタ／メモリインターフェイス
ユニット３０８のメモリインターフェイス部分によりな
され、また、システムメモリ中のデータベースコマンド
ブロック（他で詳細に説明する）のアドレスを含む。ス
タートＤＢＥ信号を受信すると、コントロールプロセッ
サ３１０がシステムメモリからデータベースコマンドを
フェッチし、これを内部に蓄える。

【００３６】次に、コントロールプロセッサ３１０がデ
ータベースコマンド情報を他の処理エレメント３０４〜
３０８の各々のためのセットアップおよび処理情報に分
解する。データベース記述子およびフィールド情報は、
エキストラクタ／メモリインターフェイスユニット３０
８のエキストラクタ／アセンブラの機能を初期化するた
めに使用され、選択述語が述語評価器３０４内の命令お
よび定数テーブルにロードされ、また、ソートキーがソ
ート／マージユニット３０２をセットアップするのに使
用される。要求される情報（機能および初期化データ）
が各処理エレメントに一旦ロードされると、実行フェー
ズが始まる。

【００３７】データベース全体が処理されるまで、パイ
プライン形式で各処理エレメントによりデータブロック
を処理することによって、データベースコマンドが実行
される。ソート付きサーチの場合では、エキストラクタ
／メモリインターフェイスユニット３０８のエキストラ
クタ部分によりデータがまず処理され、ワーキングスト
ア３１２に必要なデータが入れられる。次に、選択述語
に合ったものを選択するために、ワーキングストア３１
２中のレコードを述語評価器３０４が処理する。そし
て、ソート／マージユニット３０２がキーに基づいた順
序に選択されたレコードをソートする。

【００３８】ソートおよび述語評価の動作は、ワーキン
グストア３１２の大きさのブロック内でなされ、データ
ベース全体が処理されるまで繰り返される。例えばコマ
ンドのソート部分が大きなデータベースをマージするこ
とを可能とするためにいくつかのマージのパスを取るか
もしれない。そのような場合には、エキストラクタ／メ
モリインターフェイスユニット３０８のアセンブラ機能
がシステムメモリ内の一時的なメモリ領域へ中間的な結
果を書くのに使用される。最終的なマージパスでは、エ
キストラクタ／メモリインターフェイスユニット３０８
のアセンブラ機能により、出力レコードが正しいフォー
マットへアセンブルされ、また、出力レコードがコマン
ドで指定された出力メモリ領域へ書き込まれる。

【００３９】最後のレコードがアセンブルされ、システ
ムメモリ内へ置かれると、コントロールプロセッサ３１
０が動作上或いはエラーのステータスを集め、これをシ
ステムメモリ内のステータス領域内へ入れる。そして、
コントロールプロセッサ３１０は、開始ホストＣＰＵに
対して動作が完了したことを知らせる。そして、データ
ベースエンジン３００は他のコマンドを処理できるよう
になる。

【００４０】都合が良いことに、データベースエンジン
のシステムメモリアクセスは、データベース処理時間と
オーバーラップできる。まだ、他のレコードが処理中で
ある間に、データベースエンジン３００によりデータベ
ースのレコードがアセンブルされ、システムメモリへこ
のレコードが戻されることが可能である。また、ワーキ
ングストアの複数の区画へ同時にアクセスできるよう
に、機能が分割されているならば、コントロールプロセ
ッサ３１０によって起動されると、他の処理エレメント
３０４〜３０８の各々が並列に動作可能である。このよ
うに、データベースエンジンは、システムメモリのアク
セスレートに極めて近いレートで、データベース照会を
実行することができる。

【００４１】なお、上述の例は、ソート付きサーチであ
るが、同じデータブロックパイプライン形式で全て実行
するサーチ、ソート、マージ、ジョイン等を含む多くの
異なる動作を行うことができる。

【００４２】データベースエンジンのコマンドセット
は、データベース照会を処理するのに使用される中心的
なリレーショナルデータベース機能を含む。これらの機
能は、照会の基本的な要素であって、１つの複合データ
ベース照会を作成するために、連鎖することができる。
データベースエンジンにより実現される中心的な機能は
下記のものである。

【００４３】１．ソート。データベースは、与えられた
列或いは列の結合に基づいてソートされ、ソートの順序
で戻される。ソートキーは、いかなる長さでも良い（こ
の実施例では、３２ｋバイトの長さ迄とされる）。

【００４４】２．サーチ。データベースが評価され、そ
の結果は与えられた述語と合う行に限定される。例えば
列１＝‘ｘｙｚ’である全てのレコードを見つけるの
は、サーチ動作である。データベースの中から、‘ｘｙ
ｚ’に等しい列１を全てのレコードが持つサブセットが
戻される。「列１＝‘ｘｙｚ’」が述語と称され、この
場合のように単純、又は複雑でありうる。データベース
エンジンでは、使用される比較演算子としては、「等し
い」「以上」「以下」「等しくない」「より小さい」
「より大きい」が可能である。複雑な述語は、ＡＮＤ、
ＯＲ、ＮＯＴおよび他の論理演算子で結合された単純な
述語からなる。

【００４５】３．選択。データベース中の列のサブセッ
トがデータベースから選択されて戻される。選択操作
は、データベースの列の垂直のサブセットを戻す。

【００４６】４．集合演算。集合演算は、合併、共通部
分、差およびクロス積を含む。これらは、一般の集合理
論で定義されているように実行される。

【００４７】５．ジョイン動作。ジョイン動作は、ジョ
インのタイプに従って実行される。ジョイン演算子とし
ては、「等しい」「以上」「以下」「等しくない」「よ
り小さい」「より大きい」、或いは論理演算子ＡＮＤ、
ＯＲ、ＮＯＴにより結合された上述のものの組合せから
なる。結果として大きなデータベースを作るが、外結合
も実行できることに注意されたい。

【００４８】ｂ．コマンドフォーマット コマンドブロックは、データベースエンジンに対するコ
マンドおよびアドレス情報の両者を提供するデータ構造
である。コマンドブロックは、データベースのアプリケ
ーションソフトウェアにより構成され、システムメモリ
を通って初期化の期間にデータベースエンジン３００に
パスされる。データベースエンジン３００は、スタート
ＤＢＥコマンドの受信により、システムメモリ内にコマ
ンドブロックが存在していることを知らされる。コマン
ドブロックには、以下の情報が含まれる。

【００４９】１．実行されるべきコマンドの種類、すな
わち、ソート、マージ、ジョイン、選択、サーチ、合
併、共通部分、差、クロス積又は除算である。 ２．メモリ中のデータベース記述子のアドレス。２個の
入力と１つの出力との３個迄の記述子が使用できる。処
理中は出力領域が一時的な作業領域としても使用でき
る。 ３．コマンド処理で使用される述語のアドレス。 ４．コマンドのために使用されるデータベースからのフ
ィールドと、与えられる出力フィールド。 ５．インデックスが利用可能ならば、コマンドブロック
内でそれが指定される。

【００５０】データベース記述子が特定のデータベース
を識別するのに種々のコマンドにより使用される。例え
ばＭＥＲＧＥコマンドは、入力として任意数のデータベ
ース（この実施例では、１２８まで）を持つことがで
き、出力として１つのデータベースを持つことができ
る。残りの各コマンドは、入力として１個或いは２個の
データベースを処理し、出力として第３のものを持つの
が好ましい。データベースエンジンはこれらのデータベ
ースの各々をデータベース記述子により識別する。各記
述子は下記の情報を有する。

【００５１】Ａ．データベースのスタートアドレス Ｂ．データベースのフォーマット、すなわち、ＤＢ２
か、コンパクトか。 データベースエンジンは、任意のノンインデックスコマ
ンドについて、ＤＢ２ページセットフォーマットを処理
できる。しかしながら、若し、その代わりにコンパクト
な順次フォーマットを使用すれば、性能が改善されるこ
とになる。データベースエンジンにより使用される全て
の作業スペースおよび一時的なデータベースは、メモリ
中に順次に置かれたレコードと共に記憶される。最終の
結果は、いずれのフォーマットで記憶しても良い。 Ｃ．データベース中のレコード数。 Ｄ．データベースのフォーマット、すなわち、フィール
ド数、フィールド内に含まれるデータの種類、および最
大長。

【００５２】上述のように、コマンド処理で使用すべき
述語のアドレスは、コマンドブロックの一部としてデー
タベースエンジンにパスされる。この述語は、出力レコ
ードを元のデータベースのサブセットに制限するブール
論理式である。これは、たった１つの項でも良く、多数
でも良く、また、好ましくは、データベースエンジンが
より早く処理できるために、逆ポーランド記法で表現さ
れる。逆ポーランド記法は、元のＳＱＬ照会中に存在す
るどんな括弧も取り除き、スタックプロセッサを使用し
て、照会が順次に処理される。一例として、下記のもの
がＳＱＬでの照会である。

【００５３】 SELECT POSITION, MANAGER FROM EMPLOYEES where AGE < ■ 25' and LOCATION = ■TRENTON' and VACATION < ■ 10' and GRADE < ■ ＜ 85' ;

【００５４】ｗｈｅｒｅ節が述語であり、次の逆ポーラ
ンド形式に変換することができる。 AGE, ■ 25', <, LOCATION, ■TRENTON', =& VACATION, ■ 10', <&, GRADE, ■ 85', <&

【００５５】データベースエンジンの動作が開始する前
に、ＳＱＬ照会をこの形式に変換するのは、呼び出し手
続きによる。データベースエンジンに対して述語が与え
られる前に、英語の名前を各々に関連したデータベース
およびフィールド番号に置き換えることも、呼び出しプ
ログラムによりなされる。

【００５６】データベースエンジンは、キャラクタ又は
整数フィールドに関する述語を評価する。許容される演
算は、等しい、より小さい、より大きい、以下、以上、
および等しくないである。これらの比較は、論理演算子
のＯＲ、ＡＮＤおよびＮＯＴを使用することによって、
より複雑な照会へ組み合わせることができる。どんな組
み合わせ、整数或いはキャラクタの比較も、上述の演算
子により作成することができる。

【００５７】ｃ．処理エレメント 前述のように、５個のデータベースエンジンのエレメン
トは、機能のオーバーラップおよびパイプライン化を可
能な限り利用して、当面の問題を解くのに共同して動作
する。再び、図３を参照すると、これらは、 １．コントロールプロセッサ（ＤＢＣＰ）３１０； ２．ワーキングストア３１２； ３．述語評価器（ＤＢＰＥ）３０４； ４．ソート／マージユニット（ＤＢＳＭ）３０２； ５．ハッシュコード発生器（ＤＢＨＧ）３０６；および ６．エキストラクタ／メモリインターフェイスユニット
（ＤＢＥＭ）３０８である。

【００５８】ｄ．コントロールプロセッサ コントロールプロセッサ３１０（図３）は、データベー
スエンジンを使用するアプリケーションおよびオペレー
ティングシステムプログラムと通信する唯一のエレメン
トである。コントロールプロセッサ３１０の機能は、メ
モリからコマンドおよびデータベースの情報の全てを得
て、データベースエンジンの他のエレメントの各々をス
ケジュールおよび制御することと、呼び出しプログラム
へステータスを伝達することである。これらの機能が複
雑なために、データベースエンジンの残りと並列的にア
ドレスおよび制御情報を計算できるプロセッサが必要で
ある。

【００５９】コントロールプロセッサ３１０は、好まし
くは、データベースエンジンの機能のための拡張が加え
られた８０１プロセッサを使用することで実現される。
なお、ワーキングストアバス３１６、３１８、コントロ
ールバス３２０およびデータベースエンジンが付加され
るコンピュータシステムへのインターフェイスを備えて
さえいれば、他の従来のプロセッサアーキテクチャを必
要な処理機能の実行のために使用できる。

【００６０】コントロールプロセッサ３１０は、データ
ベースエンジンにおけるコマンド処理および制御機能の
全てを実行する。これらの機能は、コマンドを最良に処
理する仕方を決定するのと同様に、各機能エレメントお
よびセットアップの制御を有する。下記のものは、コン
トロールプロセッサ３１０で実行される機能のリストで
ある。

【００６１】１．実行すべき機能を決定するためにデー
タベースエンジンのコマンドブロックをシステムメモリ
から読み出す。各コマンドとこれに関連するデータ記述
子が実行される処理系列に変換される。一例として、ソ
ートコマンドは、ワーキングストア３１２へのデータベ
ースのブロックのロードをスケジュールし、データベー
ス全体が多数のブロックへソートされる迄ソート／マー
ジユニット３０２で各ブロックをソートさせ、最終出力
レコードを作成するために、ソート／マージユニット３
０２でこれらのブロックのマージを実行させ、そして、
エキストラクタ／メモリインターフェイスユニット３０
８にこれらのレコードをシステムメモリへ書き込ませる
ことにより、実行される。

【００６２】２．データ記述子のフェッチと評価。これ
によって、データのフォーマット、エキストラクタ／メ
モリインターフェイスユニットによるアクセスの仕方、
ワーキングストア３１２内への列の抽出順序が決定され
る。

【００６３】３．各コマンドに対する述語をフェッチ
し、それを述語評価器が実行するプログラムへ変換す
る。この変換は、列の番号を対応するワーキングストア
のオフセット（ここにデータがエキストラクタでロード
される）へ変換すること、並びに各命令の次命令フィー
ルドを計算することからなる。述語評価器プログラムの
作成の後に、述語評価器の命令および定数テーブルがコ
ントロールバス３２０を介してロードされる。

【００６４】４．システム内の他の全てのエレメントの
調整。この機能の実行のために、コントロールプロセッ
サ３１０は、コントロールバス３２０を使用し、他の処
理エレメントのコントロールレジスタへの書き込みを行
い、処理を開始し、処理エレメントのステータスを読
む。各処理エレメントは、コントロールバス３２０を介
してコントロールプロセッサ３１０により直接的に制御
されうる。データベースエンジンの処理エレメント間の
全ての通信は、コントロールバス３２０上を送られる。
コントロールプロセッサ３１０は、他の処理エレメント
３０２〜３０８と並列に動作する。これにより、他のエ
レメントがそれらのデータを処理している間に、コント
ロールプロセッサがバックグランド内の処理を実行でき
る。コントロールプロセッサ３１０は、エレメントが処
理用の新たなデータブロックを必要とする時或いはエラ
ーを有する時のみ、介在する。

【００６５】コントロールプロセッサ３１０の機能は、
コントロールプロセッサ３１０が内部のローカルワーキ
ングストア５１０（図５）に処理のために必要とする情
報の全てを保持しているので、データベースエンジンの
処理エレメントの他のものと衝突することなく動作され
うる。ローカルワーキングストア５１０は、アドレスお
よびコマンドデータの全てを保持するのに必要なスペー
スを提供する。このように、コマンド情報が一旦読まれ
ると、コントロールプロセッサ３１０とシステムメモリ
とのそれ以上の対話がない。

【００６６】コントロールプロセッサ３１０のハードウ
ェア構成が図５および図６に示される。コントロールプ
ロセッサ３１０は、６４ｋバイトのマイクロストアと３
２ｋバイトのローカルワーキングストアとを有する８０
１プロセッサで設計される。８０１命令の全てがデータ
ベースエンジンの機能に対して適用可能であるわけでは
ないので、８０１命令のサブセットのみが使用される。
コントロールプロセッサのハードウェアは、データベー
スエンジンのシステム残りに対する信号および保守用の
インターフェイスを含む。

【００６７】図５および図６は、従来の８０１アーキテ
クチャ（浮動小数点ロジックを有しない）を使用して具
体化されたコントロールプロセッサが示されている。コ
ントロールプロセッサ３１０は、コントロールバス３２
０からコントロールプロセッサ３１０へ読み出されたデ
ータをバッファするコントロールバス入力レジスタ（Ｃ
ＢＩＲ）５０２と、コントロールプロセッサ３１０から
コントロールバス３２０へ書き出されるデータをバッフ
ァするコントロールバス出力レジスタ（ＣＢＯＲ）５０
４とを有する。また、コントロールプロセッサ３１０に
は、記憶データ入力レジスタ（ＳＤＩＲ）５０６と記憶
データ出力レジスタ（ＳＤＯＲ）とが設けられている。
記憶データ入力レジスタ５０６と記憶データ出力レジス
タ５０８は、ワーキングストアバス３１６、３１８の読
み出しおよび書き込みバッファを形成する。記憶データ
入力レジスタ５０６は、ワーキングストア３１２からコ
ントロールプロセッサ３１０へ読み出されるデータをバ
ッファする。記憶データ出力レジスタ５０８は、コント
ロールプロセッサ３１０からワーキングストア３１２へ
書き込まれるデータをバッファする。

【００６８】演算実行とコントロールプロセッサのデー
タのための内部記憶装置がローカルワーキングストア
（ＬＷＳ）５１０に設けられる。ローカルワーキングス
トア５１０のデータはワーキングストア３１２或いはコ
ントロールプロセッサの論理演算ユニット５１２から記
憶データ入力レジスタ５０６を介して供給される。コン
トロールストア５１４は、コントロールロジック５１６
で実行されるコントロールプログラムを含む。

【００６９】コントロールロジック５１６はコントロー
ルプロセッサ３１０の順序づけおよび制御を行う。コン
トロールロジック５１６は、命令レジスタ（ＩＲ）５１
８および命令カウンタ（ＩＣ）５２０を含む従来のマイ
クロシーケンサである。命令レジスタ５１８は現在実行
中の命令を保持し、一方、命令カウンタ５２０は現在実
行中の命令のアドレスを保持する。

【００７０】コントロールプロセッサは、オペランドお
よびプログラムデータの記憶用の３２個の汎用レジスタ
（ＧＰＲ）５２２を有する。また、３個の一時ソースレ
ジスタ５２４〜５２８が現在実行中の命令のオペランド
の格納用に設けられている。第１の一時ソースレジスタ
（ＲＡ）５２４は現在実行中の命令の第１オペランドを
一時的に蓄えるために設けられる。第２の一時ソースレ
ジスタ（ＲＢ）５２６は現在実行中の命令の第２オペラ
ンドを一時的に蓄えるために設けられる。第３の一時ソ
ースレジスタ（ＲＴ）５２８は、ロテータ５３０および
アンド反転マスクユニット（ＡＩＭ）に対する入力とし
て、現在実行中の命令の第２オペランドを一時的に蓄え
るために設けられる。また、第３の一時ソースレジスタ
（ＲＴ）３２８は、乗算および他の演算の部分結果を保
持する。

【００７１】論理演算ユニット（ＡＬＵ）５１２はコン
トロールロジック５１６の制御の下で、ＲＡレジスタ５
２４およびＲＢレジスタ５２６中のオペランドに基づく
計算および論理演算を行う。アドレス加算器５３４は、
ＲＡレジスタ５２４およびＲＢレジスタ５２６からのオ
ペランド、命令レジスタ５１８の現在の命令、命令カウ
ンタ５２０からの現在の命令のアドレスを受け取り、命
令分岐のためのアドレス計算を行う。

【００７２】ロテータ５３０は、ＲＴレジスタ５２８の
内容を左右にシフトするバレルシフタである。シフトさ
れた結果がアンド反転マスクユニット５３２によりマス
ク発生器５３６の出力とＡＮＤされる。

【００７３】マスク発生器５３６はスタートアドレスレ
ジスタ（ＳＡＲ）５４０およびエンドアドレスレジスタ
（ＥＡＲ）５４２からその入力を受け取る。ＳＡＲ５４
０およびＥＡＲ５４２は、コントロールロジック５１６
により供給されたマスク発生器５３６のスタートビット
アドレスとエンドビットアドレスをそれぞれ保持する。

【００７４】アンド反転マスクユニット（ＡＩＭ）５３
２はＲＴレジスタ５２８の内容に対して回転およびマス
ク動作を行う。ＡＩＭの４個の入力の１つが乗数／商
（ＭＱ）レジスタ５３８である。このＭＱレジスタ５３
８は、８０１エンジンの乗算ステップ命令の部分積を保
持し、また、シフト、ロテートおよび記憶命令のオペラ
ンドである。

【００７５】信号／Ｑバス／割込みロジック５４４がコ
ンピュータシステムのインターフェイスを提供する。こ
のロジック５４４を通じて、コンピュータシステムがデ
ータベースエンジンの動作を開始、完了させる。

【００７６】上述の構成要素は従来の８０１エンジンで
実現されている。ワーキングストアバス３１６、３１８
とコントロールバス３２０への経路が追加されている。
コンピュータシステムへのインターフェイスは、８０１
エンジンにおいて具体化された従来の形式のものであ
る。８０１エンジンは、より詳細には、"THE 801 MINIC
OMPUTER"、George Radin著、1982年 ACM 0-89791-066-4
82/03/0039 に述べられている。

【００７７】ｅ．ワーキングストア ワーキングストア３１２（図３）は、好ましくは、デー
タベースエンジンにより処理されているデータを保持す
るために用いられる、少なくとも１２８ｋバイトのメモ
リからなる。ワーキングストア３１２は、２つの４倍長
ワード（１６バイト）バス３１６、３１８を通じて、２
つの等しい区画として同時にアクセス可能である。読み
出しおよび書き込みの両者が１サイクルを必要とし、従
って、ワーキングストア３１２は各サイクルで２個の４
倍長ワードをアクセス（読み出し或いは書き込み）でき
る。なお、１２８ｋバイトは、最小限の好ましい大きさ
である。コストおよび設計の面で許容できるならば、よ
り大きなワーキングストアでも良い。良いとは言えない
が、より少ないメモリ量でも、使用できる。

【００７８】ワーキングストア３１２は２個の４倍長ワ
ードバス３１６、３１８を使用してデータベースエンジ
ンの全エレメントにより直接的にアクセス可能である。
各バスは、パリティ付きの１６バイトのデータと、１６
ビットのアドレスおよびコントロール信号を有してい
る。従って、各バスのラインは１７６本で、合計で３５
２本である。

【００７９】ｆ．述語評価器 述語評価器（ＤＢＰＥ）３０４の構成および動作につい
て、図３、図７および図８を参照して説明しよう。述語
評価器３０４は、ワーキングストア３１２にある２つの
４倍長ワード（１６バイト）を２サイクルで比較する
か、又は定数とワーキングストア３１２の１つの４倍長
ワードを１サイクルで比較する。述語評価器３０４は、
コントロールプロセッサ３１０で作成された逆ポーラン
ド述語を処理する論理スタックを使用したスタックプロ
セッサである。命令がコントロールプロセッサ３１０に
より、コントロールバス３２０を介して命令テーブル６
０２にロードされる。述語評価器３０４は、そのレコー
ドの数が尽きるまで、ループ方式で命令を実行する。

【００８０】述語評価器３０４はサーチおよびジョイン
の照会をいくつかの理由で高速に処理できる。述語評価
器は、ワーキングストア３１２からの２つの４倍長ワー
ドオペランドを２サイクル毎に比較できる。４倍長ワー
ドよりも長いサーチキーは、一度に４倍長ワードで比較
される。更に、サーチの実行プロセスがメモリアクセス
プロセスとオーバーラップする。具体的には、エキスト
ラクタ３０８がワーキングストア３１２の１つの区画に
書き込んでいるのと同時に、述語評価器３０４が他の区
画からのデータを処理する。最終的に、述語評価器の命
令は「次フィールド」を含み、これは、現在の結果が一
義的にサーチ結果を規定するならば、現述語項又は述語
全体から早く出ることを可能にする。例えば一連のＡＮ
Ｄの項のうちの最初の項が誤りである場合、他の項を評
価する必要はない。それらが何であっても、結果は誤り
である。

【００８１】述語評価器３０４は４倍長ワードオペラン
ドの比較を行い、一時的な結果を保持するのにスタック
６３２を使用する。述語評価器３０４はワーキングスト
アバス３１６、３１８を通じてワーキングストア３１２
をアクセスする。レコードオペランドがワーキングスト
ア３１２からフェッチされ、定数が定数テーブル６０４
からフェッチされ、結果がワーキングストア３１２に書
き戻される。

【００８２】定数テーブル（ＣＴ）６０４は、比較定数
とワーキングストアのアドレスを保持するのに使用され
る４倍長ワード定数のアレイである。定数テーブル６０
４は比較動作のために、一時に４倍長ワードずつ比較器
６３０に読み込まれる。アドレス定数に関しては、最下
位の１６ビットのみが４倍長ワードから使用される。定
数テーブル６０４は、コントロールプロセッサ３１０に
より、一時に２倍長ワード（ダブルワード）ずつ書き込
まれる。定数テーブル６０４はコントロールバス３２０
を使用してコントロールプロセッサ３１０により初期化
される。定数テーブルの典型的な大きさは、１２８ビッ
トの幅で、深さが２Ｋである。

【００８３】命令テーブル６０２は、実行されるサーチ
プログラムがコントロールプロセッサ３１０によりロー
ドされるダブルワード幅の命令アレイである。命令テー
ブル６０２は命令カウンタ（ＩＣ）６０６によりアドレ
スされ、命令が命令レジスタ（ＩＲ）６０８へ読み込ま
れる。命令テーブルの典型的な大きさは、６４ビットの
幅で、深さが２Ｋである。

【００８４】命令レジスタ（ＩＲ）６０８は、実行中の
命令を保持するダブルワードのレジスタである。これ
は、次のサブフィールドを有する。 Ａ、Ｂ、Ｄ それぞれベースＡ、ＢおよびＤレジスタからのオフセッ
トであり、ワーキングストアのオペランドフェッチアド
レス又は結果（Ｄ）の宛先アドレスの生成に使用され
る。また、Ａ、Ｂ、Ｄフィールドは定数テーブルのアド
レスを指定できる。 Ｃ 命令タイプフィールドである。 Ｆ フラグである。このフィールドは、演算、スタックのポ
ストＡＮＤ又はポストＯＲ、ダブルワードより長い比較
のためのルーピング、および次フィールド分岐の制御を
行うフラグビットを有する。 Ｎ０、Ｎ1 （次フィールド） このフィールドは、現命令の結果が真或いは偽の場合の
分岐先の命令アドレスを指定する。Ｆフィールド内でこ
の選択が特定される。次フィールドにより、述語評価器
は、照会が早く終わる時を識別し、実行される必要がな
い命令を避けた分岐を取ることできる。これは、実行時
間を短縮し、性能を改善する。パイプライン長と次フィ
ールド分岐を取ることで生じる２サイクルの遅延とのた
めに、次フィールド分岐は、実行不要な命令が３以上で
あれば性能を改善するが、さもなければ、次フィールド
を使用すべきでない。

【００８５】Ｉ加算器６１０は、１ずつインクリメント
することにより、命令レジスタからＭＵＸ（マルチプレ
クサ）６１２を介して供給される次フィールドを加算す
ることにより、又はゼロへリセットすることにより、命
令カウンタ６０６を更新する２進加算器である。命令カ
ウンタ６０６はコントロールバス３２０を通じてコント
ロールプロセッサ３１０により、任意のアドレスへリセ
ットされうる。加算器の典型的な大きさは、１１ビット
である。

【００８６】述語評価器は、ベースＡレジスタ６１４、
ベースＢレジスタ６１６、ベースＤレジスタ６１８を有
する。これらのベースレジスタは、オペランドＡ、オペ
ランドＢおよび結果の宛先（Ｄ）のベースアドレスを保
管するのに用いられる。これらのレジスタにオフセット
を加算して、ワーキングストア３１２のアドレスを生成
することにより、オペランドがフェッチされる。

【００８７】また、２個の長さレジスタ６２０および６
２２が設けられている。長さレジスタは、比較される４
倍長ワードの数（すなわち、オペランドの長さ）をロー
ドされ、これがゼロになって、比較が完了したことを示
すまで、ループ形式でディクレメントされる。レコード
計数レジスタ６２４は、処理されるレコードの数を含
む。

【００８８】２個の１６ビット加算器（共に参照符号６
２６で示す）は、長さレジスタ、ベースレジスタ又はレ
コード計数レジスタを命令の実行中に更新するのに使用
される。また、これらの加算器６２６は、ゼロの長さ或
いはレコード計数の状態を識別するために試験されるゼ
ロ状態フラグを発生する。加算器の出力は出力レジスタ
６２８へ供給される。出力レジスタ６２８は、述語評価
器３０４からワーキングストア３１２（図３）へ書き込
まれるデータのためのステージングレジスタである。述
語評価器３０４が選択されたレコードに対するポインタ
をワーキングストア３１２へ書き込み、これにより他の
処理エレメントがポインタを使用できる。

【００８９】比較器６３０は、３入力の比較器であり、
２つの４倍長ワードを比較し、そしてスタック６３２か
らの先頭要素（ＴＯＳ）と論理結果を比較する。先頭要
素が有効にポップされ、そして、結果がスタックにプッ
シュされる。比較器６３０へのオペランドは、Ａレジス
タ６３４およびＢレジスタ６３６から供給される。Ａレ
ジスタ６３４およびＢレジスタ６３６は命令毎にワーキ
ングストア３１２からロードされる。但し、Ａレジスタ
６３４を定数テーブル６０４に含まれるアドレスと比較
する命令は、Ｂレジスタ６３６をロードしない。

【００９０】比較器６３０はＡおよびＢレジスタ（又は
定数テーブル）の値に対し次の比較を行う。すなわち、
より大きい、より小さい、以下、以上、等しい、等しく
ない。また、比較器６３０は次の論理演算を行う。すな
わち、Ａ／Ｂレジスタ（定数テーブル）の比較結果及び
ＴＯＳ、又はスタックの２個の先頭要素のＡＮＤ、ＯＲ
およびＮＯＴ。前者の場合には、ＴＯＳがポップされ、
そして結果がスタックにプッシュされる。後者の場合に
は、両方の先頭要素がポップされ、そして結果がスタッ
クにプッシュされる。結果の値はコントロールおよびシ
ーケンスロジック６３８にも送られ、次の分岐が取られ
るかどうかが判定される。

【００９１】スタック６３２は、１ビットの幅で、後入
れ／先出し（ＬＩＦＯ）のスタックであり、照会の処理
中に一時的な値を保持するのに使用される。２個の先頭
要素は、何時でも、処理のために比較器６３０が利用で
きる。

【００９２】コントロールおよびシーケンスロジック６
３８は、従来のマイクロシーケンサであって、述語評価
器３０４の内で動作の順序づけおよび分岐を制御する。
述語評価器３０４は、好ましくは、命令の開始毎に１サ
イクル又は２サイクルで動作する３サイクルパイプライ
ンを使用する。

【００９３】述語評価器３０４の命令セットは、９個の
命令タイプを含む。 １．先頭要素（ＴＯＳ）との比較およびＡＮＤ ２個のオペランド、すなわち、ＡおよびＢレジスタ６３
４、６３６、又はＡレジスタ６３４と定数テーブル６０
４からの定数とが比較され、その結果がＴＯＳの値とＡ
ＮＤされる。この動作の論理結果が以前のＴＯＳの値に
代えてスタック６３２にプッシュされる。有効な比較の
演算子は、より大きい、より小さい、以下、以上、等し
い、等しくないである。

【００９４】２．先頭要素（ＴＯＳ）との比較およびＯ
Ｒ ２個のオペランド、すなわち、ＡおよびＢレジスタ６３
４、６３６、又はＡレジスタ６３４と定数テーブル６０
４からの定数とが比較され、その結果がＴＯＳの値とＯ
Ｒされる。この動作の論理結果が以前のＴＯＳの値に代
えてスタック６３２にプッシュされる。有効な比較の演
算子は、より大きい、より小さい、以下、以上、等し
い、等しくないである。

【００９５】３．比較およびプッシュ ＡおよびＢレジスタ６３４、６３６、又はＡレジスタ６
３４と定数テーブル６０４からの定数とが比較され、そ
の論理結果がスタック６３２へプッシュされる。有効な
比較の演算子は、より大きい、より小さい、以下、以
上、等しい、等しくないである。

【００９６】４．加算又は減算 ２個のオペランドが加算器６２６により加算又は減算さ
れ、その結果が識別された宛先レジスタに記憶される。
有効なソースオペランドは、ベースＡ／Ｂ、長さＡ／
Ｂ、レコード計数、ベースＤ、および定数（定数テーブ
ル６０４から）である。結果は、上述のどれにも行くこ
とができ、出力レジスタ６２８へも行ける。加算および
減算はコントロールおよびシーケンスロジック６３８の
コントロールフラグをセットして、結果がゼロになった
ことを示すことができる。

【００９７】５．ワーキングストア（ＷＳ）のアクセス
命令：ＷＳ読み出しおよびＷＳ書き込み 読み出しは、データをＡレジスタ６３４又はＢレジスタ
６３６へ置く。書き込みは、出力レジスタ６２８の値を
指定されたワーキングストアのアドレスに書き込む。ア
ドレスは、いずれかのベースレジスタから生成される。

【００９８】６．スタック動作：プッシュおよびポップ これらの命令はスタックに値をプッシュし、又はスタッ
ク６３２から値をポップする。

【００９９】７．スタック論理動作：ＡＮＤ、ＯＲおよ
びＮＯＴ スタック６３２の２個の先頭要素は、比較器６３０によ
りＡＮＤ又はＯＲされることができ、その結果がスタッ
クにプッシュされる。ＮＯＴ ＴＯＳ命令は、ＴＯＳを
反転する。

【０１００】８．再スタート 再スタート命令は、プログラムの最初のアドレスへ分岐
させ、スタックポインタをゼロ（空のスタック）にリセ
ットし、更に、ベースＡおよびＢレジスタをインクリメ
ントする。この命令は、レコードがサーチされた後で使
用され、次のレコードの評価を開始する。レコード計数
レジスタ６２４およびベースＤレジスタ６１８はこの命
令の実行前に更新される。

【０１０１】９．停止およびステータスの送出 この命令は、述語評価器３０４の実行を停止し、また、
コントロールプロセッサ３１０へステータスワードを送
出する。ステータスワードは、フラグおよび命令からの
情報を有する。これは、コントロールプロセッサに対し
て、述語評価器がレコードの１ブロックの処理を終了し
たこと、出力領域が一杯であるか、エラーが生じたこと
を知らせる。

【０１０２】述語評価器の命令は、３種類の機能を実行
する。すなわち、述語評価器３０４のポインタの更新、
オペランドの比較およびワーキングストア３１２への結
果の書き込みである。比較されるレコードの各々のため
に、ベースＡレジスタ６１４およびベースＢレジスタ６
１６にポインタが維持され、レコードが処理される都
度、ポインタが更新される。レコードは、順番にワーキ
ングストア３１２に記憶される。ポインタはレコードの
ベースアドレスを与え、そのレコード中の比較されるべ
き列は命令のオフセットフィールドにより示される。ベ
ースＤレジスタ６１８で与えられるワーキングストア３
１２のアドレスに対して、結果が書き込まれる。また、
ベースＤレジスタ６１８は、結果が発生する都度、更新
される。ベースＡ、ベースＢおよびベースＤレジスタ
は、長さＡ／Ｂレジスタ６２０、６２２又は定数テーブ
ル６０４内の定数によりインクリメントされる。

【０１０３】命令は、命令テーブル６０２から命令レジ
スタ（ＩＲ）６０６へフェッチされる。命令のフェッチ
および復号は、１サイクルかかる。その後で、１或いは
２サイクルのオペランドフェッチがあり、最終的に実行
に１サイクルかかる。従って、実行パイプラインは、３
サイクルの長さであり、命令が１或いは２サイクル毎に
開始する。ワーキングストアの２つのオペランドを有す
る命令はオペランドフェッチのために２サイクルかか
り、従って、命令開始の間に２サイクルを必要とする。
ワーキングストアオペランドと定数テーブルオペランド
を持つ命令は、両者を並列に読み出せるので、オペラン
ドを読むのに１サイクルだけで良く、従って、これらの
命令はサイクル毎に開始できる。

【０１０４】命令テーブル６０２に格納されるプログラ
ムは、コマンドで与えられる照会の述語からコントロー
ルプロセッサ３１０によって作成される。これは、ワー
キングストア３１２のレコード格納場所およびそれらの
フォーマットを考慮した述語の翻訳である。一般的に、
照会の処理の概略は、以下のものである。

【０１０５】１．コントロールプロセッサ３１０がコマ
ンド、データ記述子および実行される述語を読み、評価
のためにレコードをどのようにワーキングストア３１２
に格納するかを決定する。比較を容易とするために、レ
コードの内で関係のある列がまとめて置かれるように、
レコードが抽出される。コントロールプロセッサ３１０
は、記憶装置アクセスと、抽出動作とを開始し、レコー
ドの最初のブロックがワーキングストア３１２にロード
される。

【０１０６】２．最初のレコードがロードされている
間、コントロールプロセッサ３１０は、ワーキングスト
ア３１２のレコードのフォーマットと必要なフィールド
に基づいて、述語を述語評価プログラムへ翻訳する。そ
して、述語評価器３０４が可能な時に述語から早く出ら
れるように、プログラムを評価し、次フィールドをセッ
トする。

【０１０７】３．プログラムが作成されると、述語評価
器の命令テーブル６０２にロードされる。必要な定数が
定数テーブル６０４にロードされる。そして、ベース、
長さおよび計数レジスタ６１４〜６２４がワーキングス
トア３１２の正しい位置を指示する値をロードされる。
これは、ワーキングストア３１２がレコードの最初のブ
ロックをロードされている間に、コントロールバス３２
０を介して全てなされる。

【０１０８】４．最初のブロックがロードされると、コ
ントロールプロセッサ３１０が述語評価器３０４に処理
開始を指示する。同時に、エキストラクタ／メモリイン
ターフェイスユニット３０８がセットアップされ、ワー
キングストア３１２の他方の区画にレコードの次のブロ
ックがロードされる。このロード動作は、述語評価器３
０４による最初のブロックの処理と並列にランするよう
に開始される。サーチが完了するか、ワーキングストア
の出力領域が一杯となり、メモリへ書く必要があるか、
又はエラーが生じるまで、このようにして処理が続けら
れる。

【０１０９】５．サーチが完了した時に、エキストラク
タ／メモリインターフェイスユニット３０８が残ってい
る結果レコードをシステムメモリへ書くように命令さ
れ、動作が終了する。

【０１１０】ｇ．ソート／マージユニット ソート／マージユニット（ＤＢＳＭ）３０２は、ソー
ト、マージおよびジョインの動作を行う。更に、ソート
／マージユニットは、キーのリストに対する合併、共通
部分、差およびクロス積の集合演算を行う。これらのオ
ペレーションの類似性により、これらを同じハードウェ
アエレメントで効率的に行うことができる。動作の全て
は、排他的にワーキングストア３１２（図３）をアクセ
スし、システムの主記憶装置４１０或いはページ記憶装
置４１２（図４）からロードされたデータのブロックを
処理していく。これは、システム記憶装置の負担を減少
し、キーへの１サイクルアクセスを提供する。

【０１１１】このソート／マージユニットハードウェア
は、図９を参照することにより、より理解される。ソー
トおよびマージ動作は、ワーキングストア３１２からの
２つの４倍長ワード（１６バイト）のオペランドを読み
出しサイクル毎に比較する比較器７０２（キー比較器）
を用いて行われる。２つのオペランドの各々は、２つの
ワーキングストアバス３１６、３１８のうちの１つを経
由して比較器７０２に入る。好ましくは、一方のオペラ
ンドは、２つの独立してアドレス可能なワーキングスト
ア区画の一方から供給され、他方のオペランドは他方の
区画から供給される。この構成は、両方のオペランドに
同時にアクセスできるようにすることで、ソート動作を
より加速する。

【０１１２】キー比較器７０２は、「等しい」、「より
小さい」、又は「より大きい」状態として比較の結果を
識別する２ビットの結果を生成する。この２ビットの結
果は、コントロールおよびシーケンスロジック７０４に
送られる。この動作は、後述される。

【０１１３】比較される２つのオペランドのためのワー
キングストアアドレスは、それぞれ、ベースＡレジスタ
７０６およびベースＢレジスタ７０８に保持される。２
つのオペランドのアドレスＡ、Ｂは、２つの独立してア
ドレス可能なメモリアレイ（ポインタアレイ）７１２、
７１４を含む内部メモリ７１０から得られる。ポインタ
アレイ７１２、７１４には、データバス７１６を経由し
て、オペライドのワーキングストアアドレスがロードさ
れる。ポインタアレイ７１２、７１４は、第１アドレス
バス７１８および第２アドレスバス７２０を経由して、
コントロールおよびシーケンスロジック７０４から与え
られるアドレスによって、それぞれ、独立してアドレス
可能とされる。ワーキングストアアドレスは、エキスト
ラクタ／メモリインターフェイスユニット３０８（図
３）のエキストラクタ部分から得られる。

【０１１４】オペランドのフェッチをより効率的にする
ために、次のキーアドレスがベースキーアドレスと同じ
読み出しサイクルでポインタアレイ７１２、７１４から
読み出される。次キーアドレスは、現（ベース）キーア
ドレスと共にベースＡレジスタ７０６およびベースＢレ
ジスタ７０８に記憶される。複数４倍長ワードのキーの
比較を可能にするために、ベースＡアドレスがＡアドレ
スカウンタ７１９にロードされ、ベースＢアドレスがＢ
アドレスカウンタ７２１にロードされる。ＡおよびＢア
ドレスカウンタ７１９、７２１は、キーを４倍長ワード
単位でアドレスするために、コントロールロジック７０
４により、一度に４倍長ワードアドレス分インクリメン
トさせることができる。そのため、複数４倍長ワードの
キーは、４倍長ワードずつ比較器７０２により比較され
る。図９の実施例では、ＡおよびＢアドレスは、それぞ
れ、ＡおよびＢアドレスカウンタ７１９、７２１の出力
を経由して、ワーキングストア３１２に与えられる。複
数４倍長ワードのキーが使用されない場合は、ベースＡ
およびベースＢレジスタは、ワーキングストアを直接ア
ドレスするのに使うことができる。

【０１１５】関連データのアドレスを追跡するため、ソ
ート／マージユニットは、多数のポインタを使う。ソー
ト動作の各パスの間、ポインタアレイの１つがソース
（読み出し）アレイとして割当られ、他方が宛先（書き
込み）アレイとして割当られる。ｉカウンタ７２２およ
びｊカウンタ７２４によりそれぞれ生成されたｉおよび
ｊポインタは、ソースアレイのためのアドレシングを行
う。ｋカウンタ７２６により生成されたｋポインタは、
宛先アレイのためのアドレシングを行う。ｍカウンタ７
２７は、トーナメントツリーマージソート（詳細は後に
説明する）のためのベースノードアドレスを追跡するの
に用いられる。ｉ、ｊ、ｋおよびｍカウンタ７２２〜７
２７には、コントロールおよびシーケンスロジック７０
４を経由して、コントロールプロセッサ３１０（図３）
により初期値がロードされる。各カウンタは、コントロ
ールおよびシーケンスロジック７０４により、インクリ
メントされることができる。

【０１１６】ソート／マージユニットは、キーをリスト
のグループとして処理し、一度に２つのリストに対して
２分マージ／ソートを行う。ｑカウンタ７２８およびｒ
カウンタ７３０によりそれぞれ生成されたｑおよびｒポ
インタは、この２つのリストのそれぞれでの要素の残り
の数を追跡する。ｑおよびｒカウンタ７２８、７３０に
は、コントロールおよびシーケンスロジック７０４によ
り、初期値がロードされ、そして、コントロールおよび
シーケンスロジックにより、デクリメントさせることが
できる。第１および第２の比較器（ｑ／０およびｒ／０
比較器）７３２、７３４がｑおよびｒカウンタの出力を
それぞれ受け取るために接続される。比較器７３２、７
３４は、ｑおよびｒカウンタがいつゼロまでデクリメン
トされたかを検出する。比較器７３２、７３４のそれぞ
れは、「等しい」或いは「等しくない」の状態としての
比較の結果を識別する１ビットの２値出力を生成するタ
イプのものである。比較結果は、コントロールおよびシ
ーケンスロジック７０４に送られる。

【０１１７】マージされる２つのリストの初期長さｐが
コントロールバス３２０を介してコントロールプロセッ
サ３１０により与えられ、そして、ｐレジスタ７３６に
保持される。ソートされるキーの初期数ｎもまた、コン
トロールプロセッサ３１０により与えられ、ｎレジスタ
７３８に保持される。第３の比較器（ｊ／ｎ比較器）７
４０は、ｊポインタ（ｊカウンタ７２４からの）の値と
ｎの値（ｎレジスタ７３８からの）とを比較し、そし
て、ｊ＞ｎの時にコントロールおよびシーケンスロジッ
ク７０４に情報を与える。同じように、第４の比較器
（ｋ／ｎ比較器）７４２は、ｋポインタ（ｋカウンタ７
２６からの）値とｎの値（ｎレジスタ７３８からの）と
を比較し、そして、ｋ＞ｎの時にコントロールおよびシ
ーケンスロジックに情報を与える。第３および第４の比
較器７４０、７４２は、「等しい」、「より大きい」、
或いは「より小さい」という比較結果を２ビットで出力
して知らせるタイプのものである。第５の比較器７４３
は、ｐレジスタ７３６中の値とｎレジスタ７３８中の値
とを比較し、ｐ＞＝ｎかどうかを識別する１ビットの結
果を生成する。

【０１１８】コントロールおよびシーケンスロジック７
０４は、ソート／マージユニット３０２中の全ての加算
器、比較器、およびポインタアレイを順序づける。コン
トロールアルゴリズム（以下に詳述する）は、実行され
る各動作に関して似ているが、異なるシーケンスが要求
される。エレメントの全てを調整することは、コントロ
ールおよびシーケンスロジック７０４の機能である。

【０１１９】コントロールおよびシーケンスロジック７
０４は、好ましくは、ソート／マージユニットアルゴリ
ズム（以下に述べる）を履行するためにデザインされた
プログラマブルロジックアレイとして実現される。代わ
りとしては、コントロールおよびシーケンスロジック７
０４は、上述したハードェアを用いたソート／マージユ
ニットアルゴリズムをマイクロコードプログラムの制御
の下に行う通常のマイクロプロセッサとして実現でき
る。

【０１２０】コントロールおよびシーケンスロジック７
０４の動作とソート／マージユニットの動作の概要は、
実例により、より理解される。図１０は、８つのキー
（Ｅ，Ｈ，Ｄ，Ｃ，Ａ，Ｆ，Ｂ，Ｇ）の昇順ブロックソ
ート（２分マージ／ソート）の例を示している。

【０１２１】ブロックソートの最初のパスの間、キーは
それぞれが１つのキーの長さを持つ８つのリスト８０２
〜８１６として処理され、比較は各キーのペア（Ｅ，Ｈ
Ｄ，Ｃ Ａ，Ｆ Ｂ，Ｇ）毎に行われる。比較の結果
として、８つのオリジナルキーが２つのキーをそれぞれ
含む４つの新たなリスト８１８〜８２４中に置かれる。
４つのリストの各々は、比較の「勝者」が「敗者」の前
に位置するようになっている。図１０の例では、Ｅ，Ｈ
Ｃ，Ｄ Ａ，Ｆ Ｂ，Ｇとなる。

【０１２２】２分マージ／ソートの第１のパスが完了し
た後、第２のパスが行われる。第２のパスの間、それぞ
れ２つのキーを含む４つのリスト８１８〜８２４が比較
される。つまり、リストＥ，ＨがリストＣ，Ｄと比較さ
れ、リストＡ，ＦがリストＢ，Ｇと比較される。それぞ
れの「勝者」が決定されると、それは新たなマージされ
るリストに書き込まれる。比較の第２のパスの結果とし
て、キーは各４つのキー、すなわち、Ｃ，Ｄ，Ｅ，Ｈお
よびＡ，Ｂ，Ｆ，Ｇの２つのリスト８２６、８２８に再
配列される。

【０１２３】第２のパスが完了した後、第３のマージ／
ソートパスが２つのリスト８２６、８２８上で行われ
る。２つのリストで比較が行われる（すなわち、ＣがＡ
と比較され、そして、Ａが「勝者」となり、それから、
ＣがＢと比較され、Ｂが「勝者」となる等）。各勝者が
決定されたら、それは最終リスト８３０に書き込まれ
る。最終リスト８３０は、昇順で、すなわち、Ａ，Ｂ，
Ｃ，Ｄ，Ｅ，Ｆ，Ｇ，Ｈの順で、８つのキーの長さを持
つ単一リストである。２分マージ／ソートを完了するの
に必要とされるパスの数は、ソートされるキーの数のＬ
ＯＧ₂ に等しい（少数は切り上げ）。

【０１２４】上述の昇順ソート動作を行うために、ソー
ト／マージユニットは、このデータベースエンジンの他
の機能エレメントと協力して動作する。最初に、コント
ロールプロセッサ３１０（図３）は、ポインタアレイの
１つ（例えば図９の７１２）をソース（読み出し）アレ
イとして指定する。他のアレイ（例えば図９の７１４）
は、最初に宛先（書き込み）アレイとして指定される。
ワーキングストア３１２および読み出しアレイには、そ
れぞれ、入力されたキーの数（ｎ）およびこれらの対応
するワーキングストアアドレスがロードされる。ソート
キーは、エキストラクタ／メモリインターフェイスユニ
ット３０８により、ワーキングストア３１２に供給され
る（図３）。エキストラクタ／メモリインターフェイス
ユニット３０８は、ページ記憶装置４１２（図４）から
レコードを読み出し、キーを抽出し、そして、それをワ
ーキングストアバス３１６、３１８を経由して、ワーキ
ングストア３１２に書き込む。

【０１２５】図１０の昇順ソートの例のためのワーキン
グストア３１２の初期状態は、図１１で説明される。Ａ
〜Ｈの各キーは、キーのソースになっているデータベー
スレコードを識別するレコード識別番号（ＲＩＤ）と共
に記憶される。キーがワーキングストア３１２に書き込
まれると、対応するワーキングストアアドレスが指定さ
れた読み出しアレイに書き込まれる。図１１では、第１
のポインタアレイ７１２が、最初にブロックソートの第
１のパスのための読み出しアレイとして指定される。参
照符号７１２（１）は、第１のパスのために初期化され
る状態にある第１のポインタアレイ７１２を示す。

【０１２６】ワーキングストア３１２およびソースポイ
ンタアレイが初期化された時、コントロールプロセッサ
３１０は、コントロールバス３２０を経由して、ソート
／マージユニット３０２に、昇順ソート開始（ＳＡＳ）
コマンドを送る。ＳＡＳコマンドに呼応して、コントロ
ールおよびシーケンスロジック７０４は、図１２および
図１３で説明されているアルゴリズムを実行する。図１
２および図１３で使われているＷＳ（Ａ）およびＷＳ
（Ｂ）は、それぞれ、ワーキングストア３１２中のアド
レスＡおよびＢに記憶されるキーを示す。同じように、
ＲＥＡＤ（ｉ）およびＲＥＡＤ（ｊ）は、それぞれ、指
定された読み出しポインタアレイのアドレスｉおよびｊ
に記憶されたワーキングストアアドレスを示す。ＷＲＩ
ＴＥ（ｋ）は、指定された書き込みアレイのアドレスｋ
を示す。

【０１２７】図１２および図１３のアルゴリズムは、図
１１の昇順ソート例および図９のソート／マージユニッ
トを参照して説明される。ステップ１００２では、ポイ
ンタが以下のようにセットされる。ｐレジスタ７３６が
１の初期リスト長にセットされる。ｉカウンタ７２２は
１にセットされ、その結果第１番目のリストの第１番目
のキーＥのワーキングストアアドレス００を指す。ｊカ
ウンタ７２４は２（すなわちｐ＋１）にセットされ、そ
の結果第２番目のリストの第１番目のキーＨのワーキン
グストアアドレス０８を指す。ｑおよびｒカウンタ７２
８、７３０は、初期リスト長（すなわち１）にセットさ
れる。そして、ｋカウンタ７２６は、書き込みアレイ
（最初は７１４（１））の第１番目のアドレスを指すよ
うに、セットされる。これが完了すると、ベースＡレジ
スタ７０６には、ＲＥＡＤ（１）（それは００）がロー
ドされ、そして、ベースＢレジスタ７０８は、ＲＥＡＤ
（２）（それは０８）にセットされる。

【０１２８】ステップ１００４で、Ｅキー（ＷＳ（０
０））がキー比較器７０２でＨキー（ＷＳ（０８））と
比較される。キー比較器７０２は、コントロールおよび
シーケンスロジック７０４に、ＥはＨより小さいことを
合図する。「より小さい」信号に応答して、コントロー
ルおよびシーケンスロジック７０４は、ステップ１００
６の動作を行う。特に、キーＥのアドレス（００）が宛
先書き込みアレイ７１４（１）のアドレス１（ｋカウン
タ７２６により特定される）に書き込まれる。ｉカウン
タ７２２が２にインクリメントされ、ｋカウンタ７２６
が２にインクリメントされ、ｑカウンタ７２８が０にデ
クリメントされ、そして、ベースＡレジスタ７０６がＲ
ＥＡＤ（２）（０８）にセットされる。ステップ１００
８がそれから行われる。

【０１２９】ステップ１００８で、ｋ／ｎ比較器７４２
は、ｋカウンタ７２６からの書き込みポインタｋと、ソ
ートされるキーの数の総計ｎ（ｎレジスタ７３８にあ
る）とを比較する。この場合には、書き込みポインタｋ
が２に等しく、そして、ソートされるキーの数の総計ｎ
が８に等しいので、ｋ／ｎ比較器は、「以下」条件をコ
ントロールおよびシーケンスロジック７０４に知らせ
る。この条件に応答して、コントロールおよびシーケン
スロジック７０４は、ステップ１０１０を実行する。

【０１３０】ステップ１０１０で、コントロールおよび
シーケンスロジック７０４は、第１番目のリスト中に残
りの要素があるかどうかを判断するために、ｑ／0 比較
器の出力を使う。元のリスト長さｐは１であり、そし
て、第１のリストからの１つの要素（すなわち、キー
Ｅ）は、既に、比較されているので、第１のリスト中の
残りの要素はゼロである。ｑ／0 比較器７３２からの
「等しい」条件に応答して、コントロールおよびシーケ
ンスロジック７０４は、ステップ１０１２を実行する。

【０１３１】ステップ１０１２で、コントロールおよび
シーケンスロジック７０４は、第２番目のリストの残余
カウントは０に等しい（ｒ＝０）かどうか、又は、第２
番目のリストポインタ（ｊカウンタ７２４により決定さ
れる）はソートされるキーの総数より大きい値にセット
されているかどうかを判断するために、ｊ／ｎ比較器７
４０およびｒ／０比較器７３４の出力を読み出す。第２
番目のリストは、まだ、Ｈキーを含んでいるので、ｒカ
ウンタ７３０の値は１に等しく、そして、ｒ／0 比較器
７３４は、ｒが０に等しくないことを、コントロールお
よびシーケンスロジック７０４に示す。同じように、第
２番目のリストポインタは、まだ、２にセットされてい
るので（ワーキングストアアドレス０８を指してい
る）、リスト長ｎは８に等しく、ｊ／ｎ比較器７４０は
「以下」条件を示す。ｊ＜＝ｎ条件およびｒ≠０条件
（ｊ＞ｎ又はｒ＝０が存在しない）の双方が存在するの
に応答して、コントロールおよびシーケンスロジック７
０４は、ステップ１０１４を実行する。

【０１３２】ステップ１０１４で、Ｈキーのワーキング
ストアアドレスＢ＝０８がｋカウンタ７２６により指定
されるｋポインタアドレスを用いて宛先書き込みアレイ
に書き込まれる。これが成し遂げられたら、ｊカウンタ
７２４が３にインクリメントされる。ｒカウンタ７３０
が０にデクリメントされ、ｋカウンタ７２６（書き込み
アレイアドレス）が３にインクリメントされる。そし
て、第２番目のリスト中のキーのためのワーキングスト
アアドレスＢ＝１０が読み出しポインタアレイのＲＥＡ
Ｄ（２）から読み出される。コントロールおよびシーケ
ンスロジック７０４は、それから、ステップ１０１６を
実行する。

【０１３３】ステップ１０１６で、コントロールおよび
シーケンスロジック７０４は、書き込みアレイアドレス
がソートされるキーの数を越えたかどうかを判断するた
めに、ｋ／ｎ比較器７４２の出力を使う。ソートされる
キーの数ｎは８であり、そして、書き込みアレイアドレ
スが３なので、ｋ／ｎ比較器７４２は、「以下」条件を
示唆する。この条件に応答して、コントロールおよびシ
ーケンスロジック７０４は、再びステップ１０１２を実
行する。

【０１３４】前と同様に、コントロールおよびシーケン
スロジック７０４は、それぞれ、第２番目のリストの残
余キーカウントが０に等しいかどうか（ｒ＝０）、又は
第２番目のリストポインタ（ｊカウンタ７２４により決
定される）がソートされるキーの総数より大きい値にセ
ットされているかどうかを判断するために、ｊ／ｎ比較
器７４０およびｒ／０比較器７３４の出力を読み出す。
第２番目のリストからのＨキーは、今、書き込みアレイ
に読み出されているので、ｒカウンタの値は０に等し
く、そして、ｒ／０比較器７３４は、ｒが０に等しいこ
とをコントロールおよびシーケンスロジック７０４に示
す。ｒ＝０の条件があることに応答して、コントロール
およびシーケンスロジック７０４は、ステップ１０１８
を実行する。

【０１３５】ステップ１０１８で、コントロールおよび
シーケンスロジック７０４は、次の２つのリストのマー
ジ／ソートのために、ポインタをセットアップする。こ
の例では、最初の２つのリストはＥおよびＨキーを含ん
でいた。従って、次の２つのリストはＤおよびＣキーを
含んでいる。次の２つのリストの処理のための準備で、
ｉカウンタ７２２は、現在の値とリスト長さとを加算し
たもの（ｉ＝ｉ＋ｐ）で再初期化される。従って、ｉポ
インタは３に等しくなり、読み出しアレイ７１２（１）
中のワーキングストアアドレス１０を指す。同様に、ｊ
カウンタ７２４は、（ｊ＋ｐ）の値に再初期化される。
従って、ｊカウンタ７２４は４に等しくなり、指定され
たアレイ７１２（１）中のワーキングストアアドレス１
８を指す。ｑおよびｒカウンタ７２８、７３０は、両方
とも、１のリスト長に初期化される。更に、ベースＡレ
ジスタ７０６には、Ｄキーのアドレス１０（ＲＥＡＤ
（３））がロードされ、一方、ベースＢレジスタ７０８
には、Ｃキーのアドレス１８（ＲＥＡＤ（４））がロー
ドされる。コントロールおよびシーケンスロジック７０
４は、それから、ステップ１０２０を実行する。

【０１３６】ステップ１０２０で、コントロールおよび
シーケンスロジック７０４は、ｊリストが空かどうかを
判断するために、ｊ／ｎ比較器７４０の出力を読み出
す。ソートされるキーの総数は８に等しく、そして、ｊ
ポインタは４に等しいので、ｊ／ｎ比較器７４０は、
「以下」結果を生成する。この結果に応答して、コント
ロールおよびシーケンスロジック７０４は、新たなリス
トのために、再びステップ１００４を実行する。

【０１３７】ステップ１００４の２回目の繰り返しで
は、Ｄキー（ＷＳ（１０））は、キー比較器７０２で、
Ｃキー（ＷＳ（１８））と比較される。キー比較器７０
２は、コントロールおよびシーケンスロジック７０４
に、ＤがＣより大きいことを合図する。「より大きい」
という信号に応答して、コントロールおよびシーケンス
ロジック７０４は、ステップ１０２２の動作を行う。

【０１３８】ステップ１０２２から１０３２は、ステッ
プ１００６から１０１６と同じようなやり方で実行され
ることが理解されよう。実際のカウンタの操作および比
較器の利用は、図１２および図１３から明白になろう。
例えば、ステップ１０２２で、Ｃキーが宛先書き込みア
レイ７１４のアドレス３（ｋカウンタ７２６により指定
される）に書き込まれる。ｊカウンタは、それから、５
にインクリメントされ、ｋカウンタ７２６は４にインク
リメントされ、ｒカウンタ７３０は０にデクリメントさ
れ、そして、ベースＢレジスタ７０８は、ワーキングス
トアアドレス２０を含むＲＥＡＤ（５）にセットされ
る。後に、１０３０の実行の結果として、Ｄキーが書き
込みポインタアレイ５１４（１）のアドレス４に書き込
まれる。

【０１３９】ステップ１００４から１０３０は、全ての
４対のリストＥ，Ｈ Ｄ，Ｃ Ａ，Ｆ Ｂ，Ｇがマージ
され、そして、第１番目のパスにおける書き込みポイン
タアレイ７１４（１）に示されるようになるまで、反復
的に繰り返される。

【０１４０】第１番目のパスの完了は、最後の２つのキ
ーのマージの結果がＷＳ（Ａ）＜＝ＷＳ（Ｂ）の経路を
取るか、又はＷＳ（Ａ）＞ＷＳ（Ｂ）の経路を取るかに
応じて、ステップ１０１６又は１０３２で判断される。
最後の２つのキーＢ，Ｇの比較結果はＷＳ（Ａ）＜＝Ｗ
Ｓ（Ｂ）の経路を取るので、第１番目のパスの最後は、
ステップ１０１６で検出される。

【０１４１】最後の要素に対してステップ１０１４が実
行されると、ｋカウンタ７２６は９にセットされる。ｋ
＝９であり、そして、要素の数がｎ＝８であるので、ｋ
／ｎ比較器７４２は、ｋがｎより大きいことを示す。こ
れに応答して、コントロールおよびシーケンスロジック
は、ステップ１０３４を実行する。

【０１４２】ステップ１０３４で、２分マージの第２番
目のパスのために、カウンタおよびレジスタが再初期化
される。図１１から分かるように、第１のポインタアレ
イ７１２（２）がマージアドレスを供給し、第２のポイ
ンタアレイ７１４（１）がワーキングストアアドレスを
供給するように、読み出しおよび書き込みアレイがスワ
ップされる。

【０１４３】読み出しおよび書き込みポインタアレイの
スワッピングに加えて、カウンタおよびレジスタが以下
のように初期化される。リスト長ｐは、各２つのキーの
４つのリストが形成されるように（例えば、ＥＨ，Ｃ
Ｄ，ＡＦ，ＢＧ）、２倍にされる。ｊ、ｑ、およびｒカ
ウンタは、ｊ＝３、ｑ＝２、およびｒ＝２となるよう
に、更新されたリスト長を基に再初期化され、そして、
第１のリストポインタ（ｉカウンタ）が１にリセットさ
れる。最終的には、ベースＢレジスタに第２番目のリス
ト中の最初のキーＣのワーキングストアアドレス１８が
ロードされ、ベースＡレジスタ７０６には第１番目のリ
スト中の最初のキーＥのワーキングストアアドレス（０
０）がロードされる。それから、ステップ１０３６が実
行される。

【０１４４】ステップ１０３６は、ソートが完了したか
どうかを判断するために実行される。コントロールおよ
びシーケンスロジック７０４は、ソートされるキーの数
（ｎレジスタ７３８中の値）と各リストのキーの数（ｐ
レジスタ７３６に保持されている）とを比較する。この
場合、リスト長ｐ＝２およびソートされるキーの数は８
に等しいので、ソートは完了していない。ソートが完了
していないという判断の基に、コントロールおよびシー
ケンスロジック７０４は、最後の２つのリスト中の最後
の２つのキーＦおよびＧが比較され、マージされるま
で、ステップ１００４から１０３２までの適当なステッ
プを反復的に実行する。マージの第２番目の繰り返しの
結果、ワーキングストアアドレスは、参照符号７１２
（２）で示されるように、書き込みポインタアレイに書
き込まれる。

【０１４５】第２番目のパスが完了した時（Ｆ＞Ｇなの
でステップ１０３２で判断される）、ステップ１０３４
が再び実行される。第３番目すなわち最後のパス８０６
で、読み出しおよび書き込みアレイは、７１２（２）が
読み出しアレイとなり７１４（２）が書き込みアレイに
なるように、再びスワップされる。リスト長ｐが再び２
倍にされて４となり、長さ４の２つのリストが、例えば
ＣＤＥＨおよびＡＢＦＧについて処理される。そして、
カウンタおよびレジスタは、ブロック１０３４に示され
るように、適宜にセットされる。

【０１４６】第３番目のパスの最後で、書き込みアレイ
７１４（２）は、図１１に示されるようになる。第３番
目のパスの後に、ステップ１０３２がもう１度実行さ
れ、そして、リスト長ｐが８にセットされる。

【０１４７】ソート動作の最後は、ステップ１０３６に
より判断される。リスト長ｐがソートされるキーの総数
ｎ以上になるとソートは完了する。ソート／マージユニ
ットは、コントロールバス３２０にそれを表明する信号
を与えることにより、コントロールプロセッサ３１０に
ソートの完了を知らせる。コントロールプロセッサ３１
０は、ソート完了信号を受けると、エキストラクタ／メ
モリインターフェイスユニット３０８のアセンブラ機能
に、レコードをワーキングストア３１２からシステムメ
モリに移すよう命じる。レコードは、ワーキングストア
からのキーを最終書き込みポインタアレイ（例えば図１
１の７１４（２））中に示される順序でアドレシングす
るメモリインターフェイスユニットにより、ソートされ
たフォーマットでシステムメモリに記憶される。

【０１４８】前述したように、ソート／マージユニット
３０２のソート機能は、２分マージソートをハードウェ
アで実現したものが好ましい。２分マージソートの技術
は、"Sorting and Sort System"、 Harold Lorlin著、A
ddison-Wesley PublishingCompany, Inc., Library of
Congress Catalog Card No.73-2140, 1975年の本中に詳
細に検討されている。そして、それは以下のようなもの
である。２分マージソートは、ワーキングストアの大き
さのキーブロックに対し、各サイクル毎に４倍長ワード
比較の割合で行われる。各キーブロック中に含まれるキ
ーの数は、キー長さに依存する。

【０１４９】キーのより長いリストはソートされたブロ
ックをマージすることにより作られる。マージは、２又
はそれ以上の整列リストを１つの整列リストに結合する
行為である。マージは、置換／選択アルゴリズムを用い
た１２８ウェイの「トーナメントツリー」を実現するハ
ードウェアにより実現される。１２８ウェイマージは、
各サイクル毎に７階層のツリーで４倍長ワードの比較を
行って、７サイクル毎に結果を出力する。ハードウェア
によるトーナメントツリーのマージの構成や動作は、図
９および図１５〜図２０を参照することにより、より理
解されるであろう。

【０１５０】図１５は、通常の８ウェイトーナメントツ
リーの説明である。８ウェイトーナメントツリーは、１
５のノード１〜１５を持っており、３階層の比較を行
う。マージされる８つのリストからのキーがツリーのベ
ース（ノード８〜１５）に入る。勝った方のキーがツリ
ーを介して上向きに進める。比較の第３の階層の勝者
は、ノード１でツリーから取り出され、そして、最終の
マージリストに置かれる。

【０１５１】図１６は、ハードウェアトーナメントツリ
ー動作のためのコントロールプロセッサ３１０によるワ
ーキングストア３１２およびポインタアレイ７１２、７
１４の初期化の説明である。マージされるリストの数に
基づいて、コントロールプロセッサは、トーナメントツ
リーの幅（ベースノードの数）と高さ（比較の階層の
数）を計算する。ツリーの幅（ｍ）は、次に大きい２の
べき乗に丸められたマージすべきリストの数と等しい。
ツリーでの比較の階層の数（Ｌ）は、幅（ｍ）のｌｏｇ
₂ と等しい。

【０１５２】図１６の例では、ワーキングストア３１２
中に、６つのリスト１３０２〜１３１２がある。リスト
１３０２〜１３１２は、エキストラクタ／メモリインタ
ーフェイスユニット３０８により、コントロールプロセ
ッサ３１０からの開始コマンドに応答して、ワーキング
ストア３１２に運ばれる。６つのリストがあるので、コ
ントロールプロセッサ３１０は、そのツリーの幅（ｍ）
を８と計算し、比較の階層の数（Ｌ）を３（８のｌｏｇ
₂ ）と計算する。従って、コントロールプロセッサ３１
０は、ポインタアレイ７１２、７１４を論理的に４つの
領域１３１４〜１３２０に分ける。そのうちの３つは、
比較の３つの階層にそれぞれ割り当てられ、残り１つは
ベース用である。

【０１５３】最初に、コントロールプロセッサ３１０
は、ポインタアレイ７１２、７１４の比較階層領域１３
１４〜１３１８に自動的勝者１３２２（すなわち、比較
で他のキーに負けることのないキー）に対するポインタ
をロードする。ベース領域１３２０には、最初に、ワー
キングストア３１２に保持される各入力リスト１３０２
〜１３１２からの第１のキーに対するポインタがロード
される。空のリストは、自動的敗者１３２４に対するポ
インタを、ベース領域１３２０の対応する位置に入れて
ある。ワーキングストア３１２およびポインタアレイ７
１２、７１４の初期化が完了されると、ソート／マージ
ユニット３０２のコントロールおよびシーケンスロジッ
ク７０４は、トーナメントツリーを充てんする処理を始
める。

【０１５４】図１５の８ウェイツリーを用いた昇順マー
ジのツリー充てん処理は、図１９で説明される。図１９
の処理は、置換選択マージアルゴリズムを含んでいる。
図１９に記載された各変数は、図９のソート／マージユ
ニットのハードウェア中に保持される。特に、変数Ａお
よびＢは、それぞれ、ＡおよびＢアドレスレジスタ７１
９、７２１中に保持されるワーキングストアアドレスに
対応する。変数ｉ（親ノードを決定するために、図１９
の処理で使われる）は、ｉカウンタ７２２に保持され
る。変数ｍ（ベースノードを指すために、図１９の処理
で使われる）は、ｍカウンタ７２７中に保持される。変
数「敗者」は、一時記憶位置（そのために、ｐレジスタ
７３６が利用できる）である。図１９において、ＷＳ
（ｎ）はワーキングストア３１２の位置ｎの内容を示し
ており、ＷＲＩＴＥ（ｎ）は指定された書き込みポイン
タアレイの位置ｎの内容を示し、ＲＥＡＤ（ｎ）は指定
された読み出しポインタアレイの位置ｎの内容を示す。

【０１５５】ステップ１４０２で、処理変数が初期設定
され、そして、読み出しおよび書き込みアレイの初期指
定が行われる。図１９に示すように、ベース（ノード８
〜１５）を保持しているポイタアレイ７１４が書き込み
アレイとして指定され、そして、ベースの上の階層（ノ
ード４〜７）を保持しているポインタアレイ７１２が読
み出しアレイとして指定される。更に、アレイの幅、こ
の場合８がｍカウンタ７２７にセットされ、そして、開
始親ノード番号ＩＮＴ（ｍ／２）＝４がｉカウンタ７２
２にセットされる。これが完了すると、Ａレジスタ７１
９には、ＲＥＡＤ（４）にあるワーキングストアアドレ
スがロードされ、Ｂレジスタ７２１にはＷＲＩＴＥ
（８）にあるワーキングストアアドレスがロードされ
る。

【０１５６】最初、ＷＲＩＴＥ（８）はキー「Ａ」のワ
ーキングストアアドレス（１）を含み、ＲＥＡＤ（４）
は自動的勝者のワーキングストアアドレス（１６）を含
む。ポインタアレイ７１２、７１４に構成されたトーナ
メントツリーのノードは、キー自身というよりは、キー
に対するポインタを保持することが理解されよう。

【０１５７】ステップ１４０４で、比較器７０２によ
り、ＷＳ（Ａ）のキーがＷＳ（Ｂ）のキーと比較され
る。このため、キー「Ａ」（ＷＳ（１）にある）が自動
的勝者（ＷＳ（１６）にある）と比較される。比較器７
０２による判断、すなわちＷＳ（Ａ）＜＝ＷＳ（Ｂ）に
応答して、コントロールおよびシーケンスロジック７０
４は、ステップ１４０６を実行する。

【０１５８】ステップ１４０６で、挑戦者のノードアド
レス（８）が「敗者」と呼ばれる一時記憶領域（例え
ば、ｐレジスタ７３６）に記憶され、そして、Ｂレジス
タ７２１には親ノードのアドレス（４）がロードされ
る。代わりに、もし、ＷＳ（Ａ）＞ＷＳ（Ｂ）なら、ス
テップ１４０７が実行され、「敗者」にはＡがロードさ
れ、Ｂレジスタの内容はそのままの状態とされることが
図１９から分かるだろう。

【０１５９】ステップ１４０８で、読み出しおよび書き
込みポインタアレイの指定がスワップされ、そして、比
較の敗者がツリーに書き込まれる。つまり、ポインタア
レイ７１４が読み出しアレイになり、そして、ポインタ
アレイ７１２が書き込みアレイになる。この例では、敗
者「Ａ」のワーキングストアアドレス（８）は、書き込
みアレイ７１２のアドレスｉ（＝４）にロードすること
により、ツリーに書き込まれる。ｉカウンタは、それか
ら、ＩＮＴ（ｉ／２）を再びロードされ、そして、ステ
ップ１４１０が実行される。

【０１６０】ステップ１４１０で、最初の勝利キーが見
つけられたかどうかを判断するために、ｉの値が０と比
較される。もし、ｉが０に等しくなければ、それから、
ステップ１４１２が実行される。

【０１６１】ステップ１４１２で、次に高い階層での親
ノードのポインタ内容がＡレジスタ７１９にロードされ
る。ｉ＝２なので、Ａレジスタには、自動的勝者のアド
レス（１６）であるＲＥＡＤ（２）がロードされる。ス
テップ１４０４がそれから実行され、そして、ＷＳ
（Ａ）およびＷＳ（Ｂ）のキーが比較器３０２で比較さ
れる。ＷＳ（１６）＝自動的勝者なので、それから、Ｗ
Ｓ（Ａ）＜＝ＷＳ（Ｂ）となり、そして、ステップ１４
０６〜１４１０が再び実行される。

【０１６２】前述から、ステップ１４０４から１４１２
は、ステップ１４１０で、ｉ＝０となる判断による割り
込みがあるまで、反復的に実行されるのが明白に分かる
だろう。図１７は、ステップ１４１０でのｉ＝０の最初
の判断でのポインタアレイ７１２、７１４の状態を示し
ている。

【０１６３】ｉ＝０であることが検出された時、ツリー
への次のキーローディングを始めるために、ステップ１
４１４が実行される。ステップ１４１４で、ベースノー
ドアドレス（ｍ）が１つインクリメントされ、親ノード
アドレス（ｉ）がＩＮＴ（ｍ／２）にセットされ、ポイ
ンタアレイ７１２が読み出しアレイとして指定され、ポ
インタアレイ７１４が書き込みアレイとして指定され
る。それから、ステップ１４１６が実行される。

【０１６４】ステップ１４１６では、ツリー充てん処理
が完了されたかどうかを判断するために、ｍの値がチェ
ックされる。ｍの値がツリーの幅の２倍に等しければ
（８×２＝１６）、ツリー充てん処理が完了される。ツ
リーが充てんされれば、ワーキングストアアドレスＢ
（第１番目の勝者のアドレス）は、エキストラクタ／メ
モリインターフェイスユニット３０８のアセンブラ機能
に送られ、そして、ベース領域には、勝者が出たリスト
にある次のキーが再ロードされる。図２０のマージ動作
がそれから実行される。もし、充てん処理が完了しなけ
れば、ステップ１４１８が実行される。

【０１６５】ステップ１４１８では、Ｂレジスタ７２１
には、ＷＲＩＴＥ（ｍ）中のワーキングストアアドレス
がロードされ、そして、Ａレジスタ７１９には、ＲＥＡ
Ｄ（ｉ）からのワーキングストアアドレスがロードされ
る。ｍ＝９、およびｉ＝４（ＩＮＴ（９／２））なの
で、それから、Ｂレジスタには３がロードされ（ポイン
タアレイ７１４、アドレス９）、そして、Ａレジスタに
は１がロードされる。ノード９で示されるキーＣのため
のステップ１４０４〜１４１２が反復的に実行される。

【０１６６】図１９から明らかなように、ツリーに各ベ
ースノードがロードされ、全ての自動的勝者が置き換え
られ、そして、最初の勝利キーが決定されるまで、ステ
ップ１４０４〜１４１８が反復的に実行される。図１８
は、ステップ１４１６で判断された際の、ツリー充てん
処理の最後でのポインタアレイの状態を示す。ステップ
１４１６の後、勝者のリストからの次の要素をベースに
ローディングする代わりに、リスト中の先行要素がツリ
ー上を進む際に、そのリスト中の次の要素をローディン
グすることにより、充てん処理の間にベースを再充てん
することができる。

【０１６７】図２０は、トーナメントツリー動作を説明
するフローチャートである。図２０から、実際のツリー
動作１４２２〜１４３８のステップは、ツリー充てん処
理１４０２〜１４１８に似ていることが明らかであろ
う。２つの動作の間の根本的な違いは、比較の経路の判
断である。図１９のツリー充てん処理では、ツリーは、
ｍポインタを使って、ベースを左から右に充てんされて
いく（ステップ１４１４で示される）。これに対して、
図２０のツリー動作の間では、比較される次のキー、つ
まり、比較の経路が、前の勝者により決定される。エキ
ストラクタは、勝者のオリジナルリストを追跡している
ので、新たな勝者が決定される毎に適切なベース開始点
（ｉ）がエキストラクタにより送られる。図１９と同様
に、図２０での割算は、整数割算である（すなわち、結
果の整数部分だけが調べられる）。

【０１６８】トーナメントツリー動作の間に、もし、リ
ストが空になったら、エキストラクタは、ソート／マー
ジユニットを停止するか、ツリーに自動的敗者をロード
できる。どちらの動作が選択されるかは、実行されるマ
ージのタイプに依存する。

【０１６９】全てのリストが空になるまでマージ動作が
実行される場合は、自動的敗者がロードされる。さもな
ければ、マージは停止されることになる。自動的敗者が
勝者になると（なぜなら、ツリーに残されたキーは自動
的敗者だけであるから）、マージが完了する。２つのキ
ーが等しい場合、任意にその一方を勝者とすることがで
きる（例えば、ワーキングストアアドレスＡからのキー
は、いつも、ワーキングストアアドレスＢからの等しい
キーに勝つ）。

【０１７０】ジョイン処理は、ソート／マージジョイン
アルゴリズムを用いて行われる。２つのテーブルをジョ
インするには、これらが両方とも同じソート順であり
（例えば昇順、降順）、そして、ジョインが定義される
列が等しいフォーマットとされることを必要とする。ソ
ート順は、ジョインの基準に依存する。等しい、より大
きい、又は、等しくない、が指定されると、昇順が使わ
れる。より小さいが基準の時には、降順が使われる。従
って、リストは、最初に、ソート／マージユニット３０
を使ってソートされ、それから、ジョインされる。

【０１７１】ジョインは、ジョイン基準が満たされるま
で、第１番目のリストＬ１と第２番目のリストＬ２をマ
ージすることにより、実行される。等しい、より大き
い、又は、等しくないという基準が指定される時には、
昇順のマージが行われる。より小さいという基準が指定
される時には、降順のマージが行われる。ジョイン基準
が満たされるとき、対応するキーのレコードＩＤがペア
としてワーキングストア３１２の結果領域に書き込まれ
る。キーＩＤが一度ワーキングストア３１２に書き込ま
れると、第１番目のリストＬ１を一度に１キーずつステ
ップし、第２番目のリスト中のキーのウィンドウと比較
していくことにより、ジョインが続けられる。ウィンド
ウは、Ｌ１リスト中の任意の１つの要素と比較した時、
ジョイン基準を満たすＬ２リスト中のキーの全てにより
定義される。キーＬ１（ｉ）に対し、マッチするキーＬ
２（ｊ）〜Ｌ２（ｋ）がある（ｊはｋ以下）。マッチン
グキーのレコードＩＤは、ワーキングストア３１２の結
果領域にペアとして書き込まれる。ウィンドウの最後に
達した時（例えば、ジョイン基準がもはや満たされな
い）、第１番目のリストＬ１がＬ１（ｉ＋１）までステ
ップされ、第２番目のリストＬ２がＬ２（ｊ）（すなわ
ち、ウィンドウの最初）にリセットされる。ジョイン動
作は、ジョイン基準が再び満たされて、新たなウィンド
ウが作られるまで、第１番目および第２番目のリストの
２ウェイマージとして続けられる。

【０１７２】ジョイン動作の疑似コードの例は、以下に
示される。 5 Two way merge L1(i);L2(j) ; ２ウェイマージを行う ; 10 On L1(i), L2(j) meet ; もし、ジョイン基準が満たさ selected join criteria ; れたら、以下のステップを行 (any of >,<,=,NE) ; う。さもなければ、２ウェイ ; マージを続ける。 ; 20 output L1(i), L2(i) ; L1(i), L2(i) のレコードＩ ; Ｄをワーキングストアに書き ; 込む。 ; 30 k=j ; ポインタを初期化 ; 40 k=k+1 ; ウィンドウポインタを ; インクリメント ; 50 compare L1(i):L2(K) ; ジョイン基準が満たされたか ; どうかをチェック ; 60 if join criteria is met ; output L1(i), L2(k) and ; go to 40 ; ; 70 i=i+1 ; ; 80 Return to 50 ; マージを再開

【０１７３】ソート／マージ／ジョインアルゴリズムの
より詳細な記述は、C.J. Data, "AnIntroduction to Da
tabase System", Addison-Wesley PublishingCompany,
1983年に見ることができる。

【０１７４】ソート／マージユニット３０２は、ジョイ
ンの初期比較を行う。他の述語の項は、述語評価器３０
４（図３）により行われる。この理由から、ジョインで
の最も制限的な述語は、ソート／マージユニット３０２
により行われ、残りが述語評価器３０４により行われる
ことになる。この方法は、最速の処理をし、述語評価器
３０４で評価される述語の数を最小にするという結果を
生じる。

【０１７５】合併、共通部分、および差の集合演算もま
た、ソート／マージアルゴリズムを使って行われる。こ
れらと、ジョイン演算との相違は、出力レコードの選択
および構成の方法にある。ジョインは、２つのレコード
を、その両レコードからの列を含む１つのレコードに組
み合わせる。集合演算は、同じフォーマット（すなわ
ち、列の数およびタイプが同じ）を持つデータベースで
のみ定義される。合併、差および共通部分の集合演算の
出力は、入力として、同じフォーマットを持つ。クロス
積は、このルールの例である。クロス積は、本質的に、
制限的でないジョインであるので、データベース中の全
てのレコードは、他のデータベース中の全てのレコード
とジョインされる。

【０１７６】合併演算は、２つの入力テーブル中の全て
の一意レコードのコピーを含む出力テーブルを作る。す
なわち、もし、比較動作が等しくないという結果を生じ
たら、両方の入力テーブルレコードが書き込まれる。も
し、２つの入力レコードが等しければ、１つだけが出力
テーブルに書き込まれる（いずれかのテーブルから）。
合併演算の疑似コードの例は、以下に示される。

【０１７７】合併演算 COMPARE L1(i):L2(j) IF L1(i) < L2(j), OUTPUT L1(i), i=i+1 IF L1(i) > L2(j), OUTPUT L2(j), j=j+1 IF L1(i) = L2(j), OUTPUT L1(i), i=i+1, j=j+1 CONTINUE

【０１７８】共通部分演算は、等しいレコードのコピー
を１つだけ書込み、一方、差演算は、比較が等しくない
時にＡテーブルからのレコードだけを書き込む。従っ
て、これら３つの集合演算の相違は、どの条件が出力の
書き込みを行わせるかにある。共通部分および差演算の
疑似コードは、以下に示される。

【０１７９】共通部分演算 COMPARE L1(i):L2(j) IF L1(i) < L2(j), i=i+1 IF L1(i) > L2(j), j=j+1 IF L1(i) = L2(j), OUTPUT L1(i), i=i+1, j=j+1 CONTINUE

【０１８０】差演算 COMPARE L1(i):L2(j) IF L1(i) < L2(j), OUTPUT L1(i), i=i+1 IF L1(i) > L2(j), j=j+1 IF L1(i) = L2(j), i=i+1, j=j+1 CONTINUE

【０１８１】ソート／マージユニット３０２に対する更
なる改良は、従来の置換選択型のトーナメントソート
に、Harold Lorin著、 "Sorting and Sort System"、ch
apter5.4 （先に引用している）に述べられているよう
なハードウェア符号語技術（オフセット値符号化ともい
う）を適用することである。オフセット値符号化の利用
は、キー間の順番を決定するために比較されるバイトの
数を減少する。

【０１８２】オフセット値符号化ハードウェアは、比較
動作が前の勝利キーとは異なる結果を生じた場合のキー
中のワードのオフセットを識別する。各符号語は、オフ
セットおよびワードを含む。符号語は、いつも、前の勝
利キーを基にされているので、符号語は、あるキーがも
う１つのキーより大きいかどうかを判断するために比較
される必要があるだけである。もし、キーが等しけれ
ば、両方のキーは、どこに差が存在するのか又はキーが
全く同じであるかを判定するために更にスキャンされる
（左から右に）。

【０１８３】置換選択ソーティングに対するオフセット
値符号化の適用の検討は、ＩＢＭTechnical Disclosure
Bulletin,Vol.20,NO.7,December1977,PP 2832〜2837に
見られる。

【０１８４】符号語の比較は（直接なキーの比較より
も）、ソート処理中で、キーの最も左の部分がたった１
度しか比較されないという有利さがある。これは、符号
語は、最後の比較動作からの差の位置を維持しているか
らである。従って、最小数の比較が実行され、各キー比
較においてキーの先行ワードを比較しなければならない
アルゴリズムが改善される。

【０１８５】図１４は、符号語技術を置換選択型トーナ
メントソートに適用するための付加ハードウェアを使っ
たソート／マージユニットの例である。図１４のハード
ウェアは、図９のハードウェアに付加されるものである
ことが理解されるであろう。

【０１８６】符号語技術を実現するために、２つの８Ｋ
×４ビットのオフセットアレイ１１０２、１１０４が備
えられ、これらは、図９のソート／マージユニットの例
のポインタアレイ７０２、７０４と連結される。図１４
の符号語トーナメントツリーソートハードウェアはま
た、図９のＡおよびＢアドレスレジスタ７０６、７０８
を補うベースＡおよびベースＢアドレスレジスタ１１０
６、１１０９を含んでいる。現キーのためのオフセット
のアドレスを保持するのに加えて、ベースＡおよびベー
スＢアドレスレジスタは、ＡおよびＢベースオフセット
と同一の読み出しサイクルで、Ａ＋１、Ｂ＋１オフセッ
ト（すなわち、比較される次の２つのキーのオフセッ
ト）を記憶するようになっている。

【０１８７】ＡおよびＢオフセットアドレスカウンタ１
１１０、１１１２は、比較されている現キーの符号語の
ためのオフセットアレイアドレスを含む。ＡおよびＢオ
フセットアドレスカウンタ１１１０、１１１２には、ベ
ースＡオフセットおよびベースＢオフセットレジスタ１
１０６、１１０９からのベースキーアドレスがロードさ
れ、そして、複数の４倍長ワードから成るキーの４倍長
ワードサイズのセクションのオフセットを比較するため
に、一度に４倍長ワードアドレスずつインクリメントさ
れる。この特徴を使う理由は、キーを４倍長ワードより
大きくできる一方で、ワーキングストア３１２が４倍長
ワード単位でアクセスされるからである。

【０１８８】ＡおよびＢオフセットレジスタ１１１４、
１１１６は、比較されている現キー（４倍長ワードサイ
ズキーのセクション）のオフセットを含む。これらのオ
フセットは、２つのキーが相違しているかどうかの情報
をコントロールロジックに与える比較器１１１８によ
り、比較される。オフセットが等しくなければ、最も高
い方の値のオフセットが勝ちになり、キーを比較する必
要はなくなる。オフセットが等しければ、オフセットに
よってアドレスされた２つのキーの４倍長ワードが、勝
者を決定するために、比較される。もし、比較された２
つの４倍長ワードが等しければ（複数の４倍長ワードか
ら成るキー中で）、コントロールおよびシーケンスロジ
ック７０４は、対応するキーの次の２つの４倍長ワード
を比較させるために、ＡおよびＢオフセットカウンタを
インクリメントする。対応する４倍長ワードキー比較が
勝者を決めるまで、シーケンスロジック７０４は、Ａお
よびＢオフセットカウンタをインクリメントし続ける。

【０１８９】図１４の例もまた、２つのマルチビット加
算器１１２０、１１２２を含んでいる。加算器１１２
０、１１２２は、オフセットのポイントでキーが比較さ
れるように、ＡおよびＢアドレスにオフセットを加算す
る。

【０１９０】ｈ．ハッシュ発生器 ハッシュ発生器（ＤＢＨＧ）３０６は、８バイトのキー
を取り上げ、その内容から、ハッシュコードを作るハー
ドウェアエレメントである。ハッシュコードは、８つの
サブコードを付加することにより作られる９ビットの値
である。ハッシュコード発生器は、等結合処理のために
使われる。なぜなら、類似のキーが同じハッシュコード
値バケットにまとめられることになるからである。類似
のキーをバケットにまとめておくと、ソート／マージジ
ョインアルゴリズムは、ハッシュコードバケット毎に実
行する必要があるだけであるから、ハッシュコードジョ
インアルゴリズムは、前に検討したジョインアルゴリズ
ムの範囲を狭くする。ハッシングおよびハッシュコード
は、"THE ART OF COMPUTER PROGRAMMING, Volume 3, So
rting And Searching"、Donald E. Knuth 著、Addison-
Wesley PublishingCompany (1973 年) 中に、詳細に検
討されている。

【０１９１】等結合のハッシュコード機能を遂行するた
めには、各コードのバケットを作るために、両方のテー
ブルがハッシュされなければならない。バケットは、ハ
ッシングによって同じ値が生じるキーのグループであ
る。両方のテーブル中のキーのハッシングがなされる
と、両方のテーブルからの同じバケットがキーによりソ
ートされ、それから、前に検討したようなジョインがな
される。殆どの場合、テーブルのハッシングは、ワーキ
ングストア３１２のサイズより小さいハッシュコードバ
ケットを生じさせる結果となる。これらのテーブルは、
それから、それ以上のシステムメモリアクセスを行わず
に、ＷＳにロードされ、ソートされ、ジョインされる。
このように、これらのハッシュコードバケットでは、ソ
ートのマージステップが必要とされないので、メモリ動
作の数が減る。等結合のパフォーマンスは、システムメ
モリアクセスの減少により、実質的に改善される。

【０１９２】ＤＢＨＧハードウェアは、図２１を参照し
て説明される。ＤＢＨＧハードウェアは、９ビットハッ
シュコード値の２５６×８ルックアップテーブル１５０
２と、８入力加算器１５０４とを含む。入力キー中の各
バイトに対して、２５６要素のコードアレイがある。レ
ジスタ１５０６に保持されている入力キーは、アレイ１
５０２をインデックスし、２５６コードのうちの１つを
選択させる。このようなやり方で生成された８コードの
合計が、このキーに対するハッシュコードバケット番号
とされる。キーはこのバケットに書き込まれ、そして、
それから、次のキーが読み出される。

【０１９３】長いキーは、それを８バイト長のサブキー
に分割し、そして、各サブキーに対するハッシュコード
を作ることにより、処理される。全てのサブキーハッシ
ュコードは一緒に加算され、それにより最終ハッシュコ
ードが生成される。８バイトよりも長いキーに対処する
ために、ハッシュコード発生器３０６には、キーアドレ
スレジスタ１５０８、長さレジスタ１５１０、加算器１
５１２、および保管レジスタ１５１４が備えられる。ハ
ッシングの開始に先立って、保管レジスタ１５１４はゼ
ロに初期化され、そして、長さレジスタ１５１０には、
サブキー長（図２１の例では８バイト）がロードされ
る。

【０１９４】キーをハッシュする時、そのベースワーキ
ングストアアドレスがキーアドレスレジスタ１５０８に
ロードされる。次いで、キーの最初の８バイトがキーレ
ジスタ１５０６にロードされる。結果のハッシュコード
は、保管レジスタ１５１４に保持される。キーの最初の
８バイト部分が生成されると、加算器１５１２により、
サブキー長がベースアドレスに加算され、次の８バイト
のサブキーがワーキングストア３１２から読み出され、
そして、処理される。この手続きは、８バイトの各サブ
キーのためのハッシュコードが生成されるまで、反復的
に行われる。

【０１９５】各サブキーからの結果ハッシュコードは、
発生の度に保管レジスタ１５１４において累積的に加算
される。サブキーの全てに対するハッシング動作の最後
では、保管レジスタ１５１４は、完全なキーのハッシュ
コードを保持することになる。

【０１９６】両方のテーブルからのキーの全てがハッシ
ュコードバケットにまとめられると、各バケットは、ソ
ート／マージジョインアルゴリズムを使ってジョインさ
れる。

【０１９７】これら全ての動作は、ハッシュコード発生
器３０６、エキストラクタ／メモリインターフェイスユ
ニット３０８、およびコントロールプロセッサ３１０に
より行われる。ハッシュコード発生器３０６は、２５６
のハッシュコードバケットおよび２つの入力テーブルに
対するマッピングを維持する。テーブルは、ブロックと
して読み込まれ、それから、ハッシュされ、そして、エ
キストラクタ／メモリインターフェイス３０８にバケッ
トおよびキーを与えることにより書き出される。エキス
トラクタ／メモリインターフェイスユニット３０８中の
マッピングテーブルは、バケットがシステムメモリ中の
どこにあるか、記憶が完了した時にどのように記憶位置
をインクリメントするかを追跡している。このように、
ハッシング動作全体は、コントロールプロセッサ３１０
の最小の介在で実現することができる。

【０１９８】ハッシングが完了すると、コントロールプ
ロセッサ３１０は各バケットのソート／マージジョイン
を開始する。バケットの各ペア（同じハッシュコードを
持っている２つの入力テーブルのそれぞれから１つず
つ）は、システムメモリからワーキングストア３１２に
フェッチされ、それから、ソート／マージユニット３０
２がセットアップされて、ソート／マージジョインを開
始する。ジョインされるテーブルは前のよりも小さい
が、ソート／マージジョインは、前のように実行され
る。

【０１９９】以下は、ハッシュジョインの動作のシーケ
ンスである。 １．テーブルＡから１つのレコードブロックをフェッチ
する。 ２．次のブロックがフェッチされている間に、前のブロ
ックをハッシュし、そして、各レコードを適切なハッシ
ュコードバケットに書き込む。 ３．テーブルＡ全体がハッシュされるまで、ステップ１
および２を繰り返す。 ４．テーブルＢについてステップ１、２および３を行
う。 ５．ｉをゼロにセットする。 ６．ＨＡ（ｉ）およびＨＢ（ｉ）に対しソート／マージ
ジョインアルゴリズムを実行する。 ７．ｉを１だけインクリメントし、もしｉ＜＝２５６な
ら、ステップ６に戻る。 ８．終了

【０２００】ｉ．エキストラクタ／メモリインターフェ
イスユニット エキストラクタ／メモリインターフェイスユニット（Ｄ
ＢＥＭ）３０８（図３）は、システムメモリ（主記憶装
置４１０又はページ記憶装置４１２；図４）からデータ
をフェッチし、又はシステムメモリへデータを記憶する
データベースエンジンの構成要素である。エキストラク
タ／メモリインターフェイスユニット３０８は、２つの
主機能を持っている。フェッチ又は記憶されるデータを
構成するフィールドの抽出および組立てと、ソートおよ
びマージの操作の間に使われるレコードのリストのため
のマッピング情報の維持である。

【０２０１】ソートやデータベースのアプリケーション
では、しばしば、サーチが定義されるソートキーあるい
はフィールドがレコード全体に広がり、操作を進める前
に、抽出によって使用可能なフォーマットにしなければ
ならない。ソートでは、これは、それぞれのキーフィー
ルドを得て順に連結し、１つの大きなキーとして取り扱
えるようにすることを意味する。データベース処理で
は、探索又は選択されているテーブルの列が処理可能な
ように行から抽出されなければならない。

【０２０２】ソーティングおよびデータベース処理で
は、種々の理由から、フィールド抽出がなされる。これ
らの理由のいくつかを列挙する。

【０２０３】１．１次および２次のキーフィールドを１
つのキーに結合することによって、有効ソートキーを作
るため。

【０２０４】２．ソート、サーチおよび出力生成で要求
されるフィールドのみが含まれるように、必要なフィー
ルドが抽出される。必要としないフィールドを取り去る
ことは、操作にメモリが使われているなら、メモリのト
ラフィックおよび容量の双方を減少する。

【０２０５】３．パターンマッチングがより簡単に行う
ことができるように、フィールドのサブセットを選択す
るため。

【０２０６】４．処理の出力フェーズのためにフィール
ドを正しい順序にするため。これは、キー順序と相反す
るものになるかも知れないし、或いはサーチやソートそ
れ自身とは異なるセットのフィールドを必要とするかも
知れない。本質的には抽出機能と同じであるが、この機
能はフィールド組立てと呼ばれることもある。

【０２０７】多くの通常のソフトウェアアプリケーショ
ンでは、抽出機能は、一連の長移動命令ＭＶＣＬにより
行われる。一般に、レコード中の抽出される各フィール
ド毎に１つのＭＶＣＬが実行される。フィールドは、実
際のサーチやソートを行う前に、全て抽出形式に集めら
れる。メモリアクセスの回数を考えると、全てのデータ
を移すのは効率的ではない。事前抽出メモリアクセスに
加えて、通常では、ソートやサーチの動作を行うため
に、抽出されたフィールドが再びフェッチされる。も
し、フィールドが１つの動作で抽出され、ソート（又は
サーチ）されることができたなら、パフォーマンスは著
しく改善されるであろう。なぜなら、メモリアクセスの
数が半分になるからである。

【０２０８】ＤＢ２により作られたレコードからのデー
タを効率良く比較される形にするために、エキストラク
タ／メモリインターフェイスユニット３０８の抽出機能
は、フェッチされたフィールドをコンパクトな形に再配
列する。この抽出過程は、ワーキングストア３１２（図
３）において、フィールドを固定の長さおよびストライ
ドで位置決めさせる。

【０２０９】エキストラクタ／メモリインターフェイス
ユニット３０８のマッピング機能は、ワーキングストア
アドレス、長さ、カウントおよびシステムメモリアドレ
スを含む一組のエントリ（マッピングテーブル）を使
う。Ｎウェイのマージやソート動作の間にフェッチされ
る各リストは、マッピングテーブル中に１つのエントリ
を持っている。ソート／マージユニット３０２は、リス
トから新たなエントリを要求する時、そのエントリを持
っているリストのＩＤ番号をエキストラクタ／メモリイ
ンターフェイスユニット３０８に送る。エキストラクタ
／メモリインターフェイスユニット３０８は、このＩＤ
番号を取り上げ、そして、抽出情報を含めて、そのフィ
ールドをフェッチするのに必要な全ての情報を見つける
ために、マッピングテーブルを調べる。同じフォーマッ
トが出力レコードにも使用され、読み出し／書き込み
（Ｒ／Ｗ）フラグが転送方向に示す。

【０２１０】エキストラクタ／メモリインターフェイス
ユニットの構成および動作は、図２２を参照することに
より、より理解されるであろう。エキストラクタ／メモ
リインターフェイスユニットは、メモリバッファ１６０
２、ワーキングストアバッファ１６０４、クロスポイン
トスイッチ１６０６、マッピングテーブル１６０８、お
よびシステムメモリバス３２２を介してシステムメモリ
（主記憶装置４１０およびページ記憶装置４１２；図
４）とインターフェイスしているメモリインターフェイ
ス１６１０を含んでいる。（メモリインターフェイス１
６１０を介して）システムメモリからフェッチされたレ
コードは、メモリバッファ１６０２にロードされ、そし
て、（クロスポイントスイッチ１６０６を介して）ワー
キングストアバッファ１６０４に一度に４倍長ワードず
つ書き込まれる。各４倍長ワードは、それから、処理の
ために、抽出されたフォーマットで、ワーキングストア
３１２（図３）に転送される。

【０２１１】ワーキングストアからシステムメモリへの
動作においては、反対の処理が起こる。すなわち、クロ
スポイントスイッチ１６０６を使って、ワーキングスト
アバッファ１６０４からフィールドが組み立てられ、そ
して、システムメモリに書き込まれる。

【０２１２】マージ動作においては、マッピングテーブ
ル１６０８の各エントリは、コントロールプロセッサ３
１０がフェッチ処理に関与する必要がないように、メイ
ンメモリ／ワーキングストアアドレス対、キー長さ、お
よびマージされている各リストのカウントを含む。ソー
ト／マージユニット３０２は、リストからもう１つの要
素を必要とする時、エキストラクタ／メモリインターフ
ェイスユニット３０８に（コントロールバス３２０，図
３、を介して）どのリストＩＤからのキーをフェッチす
るかの情報を与える。エキストラクタ／メモリインター
フェイスユニット３０８は、リストがメインメモリ中の
どこに記憶されていているかを決定し、それに従ってフ
ェッチするために、適当なマッピングテーブルエントリ
を読み出す。このフェッチ処理は、ワーキングストアア
クセスが必要とされる時に、ワーキングストア（ＷＳ）
バス３１６、３１８のサイクルスチールを行うことによ
り、ワーキングストア３１２を使って処理されているソ
ート／マージと同時に実行することができる。

【０２１３】図２３および図２４は、エキストラクタ／
メモリインターフェイスユニット３０８の実施例のより
詳細な図である。前述のように、エキストラクタ／メモ
リインターフェイスユニット３０８は、マッピングテー
ブル１７０２を含む。マッピングテーブル１７０２（図
２２のマッピングテーブル１６０８と対応する）は、シ
ステムメモリアドレスをワーキングストアアドレスにマ
ップする情報のテーブルである。マッピングテーブル１
７０２は、データベースエンジン３００で処理される各
レコードについて１つのエントリを含む。マッピングテ
ーブル１７０２は、要求の開始時点でコントロールプロ
セッサ３１０によりロードされ、そして、レコードが転
送される毎に更新される。マッピングテーブル１７０２
は、必要に応じて、コントロールプロセッサ３１０によ
り、再ロードされる。

【０２１４】クロスポイントスイッチ１７０４（図２２
のクロスポイントスイッチ１６０８と対応する）は、デ
ータ転送の間で、バイトの再配列を行う。クロスポイン
トスイッチ１７０４は、コントロールロジック１７０６
（後述する）の制御の下に、バイトをレコードに組み立
てる。

【０２１５】要求待ち行列１７０８は、現在実行されて
いる転送が完了するまで、要求の転送を待機させる。要
求待ち行列１７０８は、データベースエンジン３００中
の他の処理エレメントによりロードされ、そして、その
要求がエキストラクタ／メモリインターフェイスユニッ
ト３０８により処理される際に空にされる。要求待ち行
列１７０８の各要素は、マップテーブルエントリ識別番
号（ＩＤ）１７１０、要求されたレコードの数（Ａ）１
７１２、および要求元に返されるリスト番号（Ｌ）１７
１４を含む。Ｆフィールド１７１６は、必要な時に、ス
テータスフラグのために使われる。

【０２１６】メモリインターフェイス１７１８は、シス
テムメモリバス３２２とのインターフェイスと通信機能
とを備える。システムメモリ（主又はページ記憶装置）
から読み出された全てのデータ、又はシステムメモリに
書き込まれる全てのデータは、このエレメントを通過す
る。

【０２１７】マッピングテーブル入力レジスタ（ＭＴＩ
Ｒ）１７２０は、マッピングテーブル１７０２のための
ステージングレジスタである。マッピングテーブル入力
レジスタ１７２０は、コントロールバス３２０から或い
は、レコード処理中に内部的にロードされる。

【０２１８】マッピングテーブル出力レジスタ（ＭＴＯ
Ｒ）１７２４は、現在処理されているマッピングテーブ
ルエントリを保持する。各エントリのレコードには、次
のものが含まれる。

【０２１９】ａ．処理されるレコードのシステムメモリ
アドレス（ＭＡ）。 ｂ．処理される次のレコードを見つけるのに使われるシ
ステムメモリインクリメント（ＭＩ）。 ｃ．レコード長（ＲＬ）。 ｄ．レコードカウント（ＲＣ）、すなわち、このマッピ
ングテーブルエントリにより処理されるレコードの数。
レコードカウントは、ゼロになるまで、レコードが処理
される毎にデクリメントされる。ゼロになると、それ以
上のレコードはこのエントリにより処理されなくなる。
新たなエントリが処理を続けるために再ロードされなけ
ればならない。 ｅ．ワーキングストアアドレス（ＷＳＡ）、すなわち、
データが読み出し又は書き込みされるワーキングストア
３１２中のレコードのアドレス。 ｆ．ワーキングストア３１２から読み出されるか又はそ
こに書き込まれる次のレコードを見つけるのに使われる
ワーキングストアインクリメント（ＷＳＩ）。 ｇ．処理オプションを示すフラグ（Ｆ）（望ましくは１
バイト）。 ｈ．動作がシステムメモリの読み出しであるか（抽
出）、システムメモリに対する書き込みであるか（組立
て）を指定する読み出し／書き込みフラグ（Ｒ／Ｗ）。 ｉ．クロスポイントスイッチを介して処理されるバイト
を指定する抽出マスク（ＥＸＭ）。抽出マスク中のビッ
トは、クロスポイントのどのスイッチが付勢されるかを
示し、スイッチを介する任意のバイト間の接続を可能に
する。ＥＸＭフィールドは、クロスポイントスイッチ中
の各内部スイッチの接続状態を、デコーダ１７２５を介
して、コントロールする。 ｊ．マッピングテーブルエントリが有効であることを示
す有効ビット（Ｖ）。ワーキングストアデータレジスタ
（ＷＳＤ ＲＥＧ）１７２６は、ワーキングストアへ
の、およびワーキングストアからのデータをステージす
るのに使われる。ストレージバッファ（ＳＢＵＦ）１７
２８は、メモリ要求元への、およびメモリ要求元からの
データをステージするのに使われる。最後に、ワーキン
グストアアドレスレジスタ（ＷＳ ＡＤＲ）１７３０
は、処理されている現ワーキングストアアドレス（モジ
ュロ８）を保持する。このアドレスは、加算器１７３２
を使って、ＥＸＣ反復の度に１ずつインクリメントされ
る。

【０２２０】カウンタ１７３１は、コントロールロジッ
ク１７０６の制御の下に、クロスポイントスイッチ１７
０４を介して再配列されている、ストレージバッファ１
７２８中の４倍長ワードを追跡し、選択する（ＳＢＵＦ
デコーダ１７２９を介して）。カウンタ１７３１の出力
は、選択された４倍長ワードに対する抽出マスクの適当
な部分を選択するように、クロスポイントスイッチデコ
ーダ１７２５に対するコントロール入力としても使われ
る。

【０２２１】コントロールロジック１７０６は、エキス
トラクタ／メモリインターフェイスユニット中の他の各
エレメントの動作をコントロールする。コントロールロ
ジック１７０６は、マイクロコード制御の下で走るマイ
クロプロセッサ、通常のマイクロシーケンサ、或いは特
定用途向け集積回路（ＡＳＩＣ）の形のハードワイヤド
ロジックとすることができる。

【０２２２】加算器１７３４〜１７３８は、マッピング
テーブル出力レジスタ１７２４にロードされたマッピン
グテーブルエントリ中の種々のフィールドを操作するた
めに備えられる。これらの操作は、メモリインクリメン
ト（ＭＩ）をメモリアドレス（ＭＡ）に加算すること、
レコードカウント（ＲＣ）をデクリメントすること、そ
して、ワーキングストアインクリメント（ＷＳＩ）をワ
ーキンストアアドレスに加算することを含む。

【０２２３】エキストラクタ／メモリインターフェイス
ユニットの動作は、図２５、図２６および２７を参照す
ることにより説明される。図２５、図２６および図２７
は、エキストラクタ／メモリインターフェイスユニット
の動作のフローチャートである。ここに記載された動作
は、コントロールロジック１７０６の制御の下に行われ
る。このフローチャート化されたアルゴリズムは、マイ
クロコード化されたプログラムやＡＳＩＣのコントロー
ルロジックの部分で実現可能とされる。

【０２２４】前述したように、要求がエキストラクタ／
メモリインターフェイスユニット３０８で処理される前
に、コントロールプロセッサ３１０は、所与のデータベ
ースコマンドを処理するのに必要なマッピングテーブル
エントリ情報をマッピングテーブル１７０２にロードす
る。マッピングテーブル１７０２は、コントロールバス
３２０およびマッピングテーブル入力レジスタ（ＭＴＩ
Ｒ）１７１６を通って、コントロールプロセッサ３１０
によりロードされる。それぞれの抽出要求は、システム
メモリにある１グループのレコードに作用する。１つの
グループ中のレコードは、固定レコード長（ＲＬ）と、
それらの間の固定ストライドないしインクリメント（Ｍ
Ｉ）を持つと仮定される。同じように、レコードのアセ
ンブルされたグループは、固定のレコード長およびスト
ライドでもって、システムメモリに書き込まれる。

【０２２５】抽出又は組立ての各要求のために、コント
ロールプロセッサ３１０は、マッピングテーブル１７０
２中の対応するエントリを識別するＩＤ番号を割り当
て、適当に読み出し／書き込みビットをセットする。コ
ントロールプロセッサ３１０は、与えられた抽出／組立
て要求をクロスポイントスイッチ１７０４に実行させる
ように、抽出マスク（ＸＭ）を構築し、ロードする。メ
モリアドレス（ＭＡ）、メモリインクリメント（Ｍ
Ｉ）、レコードカウント（ＲＣ）、レコード長（ＲＬ）
は、ホストプロセッサから受け取られたデータベースエ
ンジンコマンドブロックの一部としてコントロールプロ
セッサ３１０に与えられる。

【０２２６】抽出の場合、ワーキングストアアドレス
（ＷＳＡ）およびワーキングストアインクリメント（Ｗ
ＳＩ）は、抽出されたレコードの長さと通常のメモリス
ペース割振り方法に基づいて、コントロールプロセッサ
により決定される。組立ての場合、ワーキングストアア
ドレスおよびインクリメントは、ワーキングストア３１
１２におけるレコードの実際の記憶位置とストライドか
ら決定される。

【０２２７】アイドル状態１８０２では、エキストラク
タ／メモリインターフェイスユニット３０８は、コント
ロールプロセッサ３１０が要求を要求待ち行列１７０８
に入れるのを待つ。コントロールロジック１７０６は、
要求が待ち行列１７０８に入ったことを確認すると、Ｉ
Ｄ１７１０を検査し、要求が有効かどうかを決定するた
めに、マッピングテーブル（これはコントロールプロセ
ッサ３１０により要求と共にエントリがロードされる）
中でＩＤに対応するエントリの有効ビット（Ｖ）を読む
（ステップ１８０４）。

【０２２８】もし、有効ビットがセットされていなけれ
ば（Ｖ＝０）、コントロールロジック１７０６は、コン
トロールプロセッサ３１０にエラーメッセージを送り
（ステップ１８０６）、レコードカウント加算器１７３
６を使ってレコードカウント（ＲＣ）をデクリメントす
る（ステップ１８０８）。コントロールロジック１７０
６は、それから、レコードカウントが０かどうかを判断
する（ステップ１８１０）。レコードカウントが０でな
ければ、コントロールロジック１７０６は、再びアイド
ル状態に入り（ステップ１８０２）、そして、次のレコ
ードを待つ。もし、レコードカウントが０なら、コント
ロールロジックは有効ビットを０にリセットし（ステッ
プ１８１２）、コントロールプロセッサ３１０に終了メ
ッセージを送り、そして、次の要求を待つために、アイ
ドル状態に入る（ステップ１８０２）。ステップ１８１
２で有効ビットが０にリセットされるのは、ポイントＡ
からこのアルゴリズムに入った場合に備えるためであ
る。

【０２２９】もし、有効ビットがセット（Ｖ＝１）され
ていると、要求が読み出し（抽出）か書き込み（組立
て）かを判断するために、コントロールロジック１７０
６はエントリのＲ／Ｗビットを読む（ステップ１８０
６）。

【０２３０】もし、要求が書き込みなら、エキストラク
タ／メモリインターフェイスユニット３０８は、組立て
処理を開始する。この処理の第１のステップとして、コ
ントロールロジック１７０６は、ｉカウンタ１７３１に
ゼロの初期値をロードする（ステップ１８１８）。それ
から、マッピングテーブル出力レジスタ１７２４にある
エントリ（これは要求のＩＤに対応するエントリであ
る）からのワーキングストアアドレス（ＷＳＡ）が、ワ
ーキングストアアドレスレジスタ（ＷＳ ＡＤＲ）１７
３０にロードされる（ステップ１８２０）。これが終わ
ると、ワーキングストアアドレス（レジスタ１７３０に
保持されている）からのワーキングストアデータがワー
キングストアデータレジスタ（ＷＳＤ ＲＥＧ）１７２
６にロードされる（ステップ１８２２）。それから、コ
ントロールロジック１７０６はクロスポイントスイッチ
１７０４をセットアップする。

【０２３１】クロスポイントスイッチ１７０４は、マッ
ピングテーブル出力レジスタ１７２４中の抽出マスクフ
ィールド（ＥＸＭ）によりセットアップされる（ステッ
プ１８２４）。抽出マスクは、レコードの各４倍長ワー
ドに対応するセクションを持っている。それぞれのセク
ションは、ｉカウンタでマスクをインデックスすること
により、個々にアクセスされる。所与の４倍長ワードの
ためのマスクセクションがデコードされ、そのデコード
値がクロスポイントスイッチをセットアップする。

【０２３２】クロスポイントスイッチ１７０４が所望の
接続にセットアップされたら、ワーキングストアデータ
レジスタ（ＷＳＤ ＲＥＧ）１７２８からのデータが、
ストアバッファ（ＳＢＵＦ）１７２８にアセンブルされ
る（ステップ１８２６）。ｉカウンタ１７３１がそれか
らインクリメントされ（ステップ１８２８）、そして、
当該レコード中に処理される必要がある４倍長ワードが
残っているかどうかを判断するために、ｉカウンタの値
（すなわち、４倍長ワード カウント）がマッピングテ
ーブル出力レジスタ１７２４中のレコード長（ＲＬ）と
比較される（ステップ１８３０）。

【０２３３】もし、処理される４倍長ワードがあるな
ら、コントロールロジック１７０６は、それぞれの４倍
長ワードに対して、ステップ１８２０〜１８３０のシー
ケンスを繰り返す。もし、処理される４倍長ワードがな
ければ、コントロールロジック１７０６は、マッピング
テーブル出力レジスタ１７２４から、レコードＩＤ、メ
モリアドレス（ＭＡ）、レコード長（ＲＬ）、および読
み出し／書き込みコントロールビット（Ｒ／Ｗ）を与え
て、メモリ要求元（ＭＲ）１７１８を初期化する（ステ
ップ１８３２）。初期化されると、メモリインターフェ
イス１７１８は、システムメモリアドレスＭＡを開始ア
ドレスとする、システムメモリへのＲＬ４倍長ワードの
書き込みを要求する（ステップ１８３４）。メモリアド
レスＭＡは、それから、アドレス加算器１７３４を用い
て、メモリインクリメント（ＭＩ）によりインクリメン
トされ、更新されたＭＡを持つエントリがマッピングテ
ーブル入力レジスタ１７１６を介してマッピングテーブ
ル１７０２に書き込まれる。更新されたエントリは、要
求ＩＤの下で、処理される次のレコードの処理の準備の
ために、マッピングテーブル１７０２に書き込まれる
（ステップ１８３６）。

【０２３４】マッピングテーブル中のエントリが次のレ
コードのためにセットアップされると、コントロールロ
ジック１７０６は、アイドルループ（ステップ１８３
８）に入り、メモリ要求が完了したことを示す信号がホ
ストシステムからメモリ要求元１７１８を介して送られ
てくるのを待つ。コントロールロジック１７０６は、要
求完了信号を受け取ると、メモリ要求元をリセットし
（ステップ１８４０）、そして、ポイントＡで再びこの
アルゴリズムに入る。

【０２３５】読み出し要求（抽出）は、書き込み要求
（組立て）とは逆の手順で扱われる。要求が読み出しで
あることを判断すると（ステップ１８１６）、コントロ
ールプロセッサは、レコードＩＤ、メモリアドレス（Ｍ
Ａ）、レコード長（ＲＬ）、および読み出し／書き込み
ビット（Ｒ／Ｗ）でメモリインターフェイス（ＭＲ）を
初期化する（ステップ１８４２）。メモリインターフェ
イスは、それから、メモリアドレスＭＡを開始アドレス
とする、システムメモリからのＲＬ４倍長ワードの読み
出しを要求する。次のレコードの処理の準備のために、
メモリインクリメント（ＭＩ）がメモリアドレスに加算
され、そして、更新されたエントリがマッピングテーブ
ルに再び書き込まれる（ステップ１８４６）。次に、コ
ントロールロジック１７０６はアイドルループに入り、
メモリ要求が完了するのを待つ（ステップ１８４８）。

【０２３６】メモリ要求が完了したことを知らされる
と、コントロールロジック１７０６は、ストアバッファ
（ＳＢＵＦ）１７２８にメモリインターフェイス（Ｍ
Ｒ）１７１８から受け取ったデータをロードし、そし
て、ｉカウンタ１７３１をゼロにリセットする（ステッ
プ１８５０）。コントロールロジック１７０６は、それ
から、ステップ１８２４で述べたのと同じような手順
で、抽出マスク（ＥＸＭ）でクロスポイントスイッチを
セットアップする（ステップ１８５２）。ストアバッフ
ァ１７２８からの４倍長ワードは、クロスポイントスイ
ッチ１７０４を介してワーキングストアデータレジスタ
（ＷＳＤ ＲＥＧ）１７２６に抽出される（ステップ１
８５４）。

【０２３７】ワーキングストアデータレジスタ１７２６
に抽出されたレコードデータはワーキングストア３１２
（図３）に書き込まれる。これは、ワーキングストアア
ドレス（ＷＳＡ）をマッピングテーブル出力レジスタ１
７２４からワーキングストアアドレスレジスタ（ＷＳ
ＡＤＲ）１７３０に書き込み（ステップ１８５６）、こ
のアドレスＷＳＡを用いて、ワーキングストアデータを
ＷＳＤレジスタ１７２６からワーキングストア３１２に
書き込む（ステップ１８５８）ことによりなし遂げられ
る。

【０２３８】最初の４倍長ワードがワーキングストア３
１２に書き込まれると、コントロールロジック１７０６
は、レコード中の次の４倍長ワードに備えて、エキスト
ラクタ／メモリインターフェイスユニットをセットアッ
プする。ＷＳアドレス加算器１７３２を使うことで、ワ
ーキングストアアドレスは、ワーキングストアインクリ
メントＷＳＩ（典型的には４倍長ワード）によりインク
リメントされ、そして、更新されたエントリがマッピン
グテーブル１７０２に書かれる（ステップ１８６０）。
更に、ｉカウンタの値が１だけインクリメントされる
（ステップ１８６２）。もし、ｉカウンタの値がまだマ
ッピングテーブル出力レジスタ１７２４中のレコード長
（ＲＬ）と等しくなければ（ステップ１８６４で判断さ
れる）、ステップ１８５２〜１８６４が、残りの４倍長
ワード分繰り返される。もし、レコード中の全ての４倍
長ワードが処理されたら、コントロールロジックは、メ
モリ要求元１７１８をリセットし（ステップ１８６
６）、そして、次のレコードの処理に備えて、ポイント
Ａから再び、このアルゴリズムに入る。

【０２３９】ｊ．拡張及び改良 データベースエンジンのソーティング性能は、データベ
ースエンジンハードウェアに対していくつかの修正をす
ることで、より一層改良できるであろう。

【０２４０】まず、ワーキングストア３１２は、フェッ
チ動作を同時に行える４つの分離した記憶ブロックに区
分することができる。４つの比較器と、４組のポインタ
アレイをもつソートエンジンを用いると、同時に４つの
キーブロックをソートすることができる。もし、比較器
が４ウェイ比較器なら、つまり、４つのキーが比較さ
れ、そのうちの１つのキーが勝者とされるなら、このエ
ンジンは、１クロックサイクルで、１６個のキーを比較
し、そして、４つの勝者を生成することができる。それ
ぞれの比較器とその関連するポインタアレイは、そのワ
ーキングストア区画にあるキーの４ウェイマージソート
を行う。エンジンの１つを介した最後のパス（ソートさ
れた４つのブロックの４ウェイマージ）は、キーの単一
整列リストを生成する。図３１は、４パイプ、４ウェイ
比較器ソートエンジンのブロック図である。

【０２４１】図２８で示したように、ソート／マージユ
ニットのソートエンジンは、フロントバックマージを行
うように修正することもできる。これはソート／マージ
ユニットエンジンの２分マージ性能を効率的に２倍にす
る。これは、ポインタアレイ１９０２〜１９０８および
キー比較器１９１２の２重化を必要とする。比較器およ
びポインタアレイの一方のセットはリストの始めから開
始して昇順でマージするように初期化される。他方のセ
ットは、リストの終わりから開始して降順でマージする
ように初期化される。このハードウェアは、通常のソー
トエンジンの半分の時間でワーキングストア３１２の並
列２分マージソートを行える。

【０２４２】ここで述べたように、ソート処理のマージ
パスは、キーのＮウェイマージを行うことにより改善さ
れる。ワーキングストア３１２は、常に、技術的な制約
により、サイズに限界があるので、ソートエンジンは、
ワーキングストアの大きさのキーブロックをソートし、
それをシステムメモリに書き込まなければならない。全
てのブロックがソートされると、最後のマージパスでキ
ーの１つの整列リストが作成される。１６ウェイマージ
は、２ウェイ比較器と、ポインタおよびオフセット（コ
ードワード）のツリーとから実現できる。２ウェイ比較
器なので、ツリーの深さは４階層となり、マージは長く
ても４サイクル毎に結果を生成する。より効果的な方法
は、図２９で示されるように、４ウェイ比較器を使っ
て、５つの４ウェイ比較器２００２〜２０１０から１つ
の１６ウェイマージツリーを作ることである。このよう
なツリーは、２サイクル毎に１つの結果を生成する。こ
のように、Ｎ個のキーを含む１６個のリストは、２×１
６×Ｎ＝３２Ｎサイクル（最小）でマージすることがで
きる。２ウェイ比較器および１６ウェイマージの場合
は、４×１６×Ｎ＝６４Ｎサイクルかかる。

【０２４３】図３０は、勝利キーの代わりに、４つの入
力キーに対するポインタの順序付けられたリストを生成
する４ウェイ比較器２１０２を示している。出力は、入
力ワードを昇順にも降順にも順序付けする４つの２ビッ
トポインタである。ソート／マージユニット（ＤＢＭ）
３０２で使われるようなポインタアレイとコントロール
ロジックを付加すると、出力は、ポインタアレイの更新
（１サイクル当たり４つのポインタを再配列）を制御す
るのに用いることができる。従って、図９および図１４
の実施例では１サイクル当たり１つのキーであるが、こ
こでは、４つのキーを１サイクルでソートすることがで
きる。この技術は、データを部分的に事前ソートするこ
とによって、２分マージソートの性能を改善する。従っ
て、この２分マージソートは、４のリスト長（図１２及
び図１３中のｐ）で開始でき、データを介する２つのパ
スを削減している。

【０２４４】

【発明の効果】この発明によれば、機能レベル並列化を
利用してデータベース動作の全体的な処理速度を従来技
術によるデータベース処理装置により達成されるもの以
上に高めることができる。また、システムメモリの帯域
幅速度において又はその近傍でデータベース動作を処理
することができる。更に、付加処理装置環境において、
従来のソフトウェアデータベース処理プログラムにより
生成されるコマンドリストを処理することができる。

【図面の簡単な説明】

【図１】従来技術によるソートプロセッサシステムのブ
ロック図である。

【図２】従来技術によるデータベース管理システムのブ
ロック図である。

【図３】この発明の好ましい一実施例によるデータベー
ス処理装置の総括ブロック図である。

【図４】ページングメモリおよびメインメモリを有する
コンピュータシステムへの図３のデータベース処理装置
の論理接続を示すブロック図である。

【図５】図３のコントロールプロセッサの一実施例を示
す図の上半分である。

【図６】図３のコントロールプロセッサの一実施例を示
す図の下半分である。

【図７】図３の述語評価器（ＤＢＰＥ）の一実施例を示
す図の上半分である。

【図８】図３の述語評価器（ＤＢＰＥ）の一実施例を示
す図の下半分である。

【図９】図３のソート／マージユニットの一実施例およ
びこのソート／マージユニットと図３のワーキングスト
アとの相互作用を示す図である。

【図１０】ブロックソートの一例を示す図である。

【図１１】図９のソート／マージユニットを用いたブロ
ックソートの間のワーキングストアおよびポインタアレ
イの状態を示す図である。

【図１２】図３のソート／マージユニット（ＤＢＳＭ）
により用いられる２分ソート／マージアルゴリズムのフ
ローチャートの上半分である。

【図１３】図９のソート／マージユニット（ＤＢＳＭ）
により用いられる２分ソート／マージアルゴリズムのフ
ローチャートの下半分である。

【図１４】トーナメントツリー符号語技術をインプリメ
ントする図９のソート／マージユニットへのハードウエ
アの付加を示す図である。

【図１５】従来のトーナメントツリーを示す図である。

【図１６】図９のワーキングストアにインプリメントさ
れたトーナメントツリー及びポインタアレイの状態を示
す図である。

【図１７】図９のワーキングストアにインプリメントさ
れたトーナメントツリー及びポインタアレイの状態を示
す図である。

【図１８】図９のワーキングストアにインプリメントさ
れたトーナメントツリー及びポインタアレイの状態を示
す図である。

【図１９】図１４の付加的なハードウエアを用いてイン
プリメントされた符号語技術を用いたソートアルゴリズ
ムのフローチャートである。

【図２０】図１４の付加的なハードウエアを用いてイン
プリメントされた符号語技術を用いたソートアルゴリズ
ムのフローチャートである。

【図２１】図３のハッシュコード生成器（ＤＢＨＧ）の
構造を示すより詳細な図である。

【図２２】図３のエキストラクタ／メモリ・インターフ
ェイスユニット（ＤＢＥＭ）のブロック図である。

【図２３】図３および図２２のエキストラクタ／メモリ
・インターフェイスユニット（ＤＢＥＭ）の構造を示す
より詳細な図の上半分を示す図である。

【図２４】図３および図２２のエキストラクタ／メモリ
・インターフェイスユニット（ＤＢＥＭ）の構造を示す
より詳細な図の下半分である。

【図２５】図２３および図２４のＤＢＥＭの動作のフロ
ーチャートである。

【図２６】図２３および図２４のＤＢＥＭの動作のフロ
ーチャートである。

【図２７】図２３および図２４のＤＢＥＭの動作のフロ
ーチャートである。

【図２８】フロントバックマージを実行するように改良
されたＤＢＳＭのブロック図である。

【図２９】４ウェイ比較器を有する１６ウェイマージツ
リーのブロック図である。

【図３０】４入力キーに対するポインタの順序づけられ
たリストを作成するための４ウェイマージソート比較器
の図である。

【図３１】４パイプ、４ウェイ比較器ソートエンジンの
図である。

【符号の説明】

３００ データベースエンジン ３０２ ソート／マージユニット ３０４ 述語評価器 ３０６ ハッシュコード発生器 ３０８ エキストラクタ／メモリインターフェイスユニ
ット ３１０ コントロールプロセッサ ３１２ ワーキングストア

フロントページの続き (72)発明者 グレン・アラン・ブレント アメリカ合衆国、ニユーヨーク州フイツシ ユキル、ウオードプレイス55 (72)発明者 ドナルド・ヘンダーソン・ギブソン アメリカ合衆国、ニユーヨーク州ソールト ポイント、レプレシヨーンレイン、アール デイー ナンバーワン、ボツクス387 (72)発明者 デビツド・ブルース・リンドキスト アメリカ合衆国、ニユーヨーク州ポキプシ ー、ヒリステラス106

Claims (18)

【特許請求の範囲】
1. 【請求項１】 コンピュータシステムからデータベース
   コマンドを受け取り、システムメモリにアクセスし、上
   記システムメモリから処理すべきデータを抽出するため
   のエキストラクタ手段と、 上記エキストラクタ手段に接続された、上記処理すべき
   データを一時的に記憶するためのローカルメモリ手段
   と、 上記エキストラクタ手段および上記ローカルメモリ手段
   に接続された、データベース処理機能を自律的に実行す
   るための複数の処理エレメント手段と、 上記エキストラクタ手段に接続された、上記処理すべき
   データ中のデータベースコマンドを識別し、上記データ
   ベースコマンドを部分機能に分解し、上記部分機能を上
   記処理エレメントに分散させるためのコントロールプロ
   セッサ手段とを有するデータベース処理装置。
2. 【請求項２】 内部コントロールバスと、 内部データバスと、 上記内部コントロールバスおよび上記内部データバスと
   通信するコントロールプロセッサと、 上記内部データバスと通信する内部メモリと、 上記内部コントロールバスおよび上記内部データバスと
   通信するシステムメモリインターフェイスと、 上記内部コントロールバスおよび上記内部データバスと
   通信するハッシュ手段と、 上記内部コントロールバスおよび上記内部データバスと
   通信する述語評価器と、 上記内部コントロールバスおよび上記内部データバスと
   通信するソート／マージユニットとを有し、 上記ソート／マージユニット、上記述語評価器および上
   記ハッシュ手段は上記コントロールプロセッサからのコ
   マンドに応答するデータベース処理装置。
3. 【請求項３】 上記ソート／マージユニットはトーナメ
   ントツリー符号語ソートを実行するための手段を有する
   請求項２記載のデータベース処理装置。
4. 【請求項４】 上記システムメモリインターフェイスは
   コンピュータシステムのページングメモリに接続され、
   上記システムメモリインターフェイスは上記ページング
   メモリに記憶されたデータを直接アドレスするための手
   段を更に有する請求項２記載のデータベース処理装置。
5. 【請求項５】 ホストシステムのシステムメモリに記憶
   されたデータベースレコードを、上記システムメモリに
   記憶され、データベース処理プログラムにより生成され
   たデータベース処理コマンドに応答して処理するための
   付加処理装置であって、 制御情報を伝送するための第１のバス手段と、 データを伝送するための第２のバス手段と、 上記システムメモリ、上記第１のバス手段および上記第
   ２のバス手段と通信する、上記システムメモリから上記
   レコードおよび上記コマンドを抽出するためのエキスト
   ラクタ手段と、 上記第１のバス手段および上記第２のバス手段と通信す
   る、上記コマンドに応答して上記第１のバス手段に制御
   情報を供給するための制御手段と、 上記第１のバス手段および上記第２のバス手段と通信す
   る、上記制御手段に応答してサーチ照会を処理するため
   のサーチ手段と、 上記第１のバス手段および上記第２のバス手段と通信す
   る、上記制御手段に応答して上記データベースレコード
   上でソートおよびマージ動作を実行するためのソート手
   段と、 上記制御手段に応答し、上記第１のバス手段および上記
   第２のバス手段と通信する、上記データベース処理コマ
   ンド中に設けられたキーからハッシュコードを発生する
   ためのハッシュコード発生手段と、 上記第２のバス手段と通信する、一時的に内部データを
   記憶するためのメモリ手段とを有することを特徴とする
   付加処理装置。
6. 【請求項６】 上記ソート手段は上記データベースレコ
   ードのトーナメントツリー符号語ソートを実行するため
   の符号語ツリー手段を有する請求項５記載の付加処理装
   置。
7. 【請求項７】 上記システムメモリは上記ホストシステ
   ムに接続されたページングメモリを有し、上記エキスト
   ラクタ手段は上記ページングメモリに直接アクセスする
   ための手段を有する請求項５記載の付加処理装置。
8. 【請求項８】 上記ページングメモリはマルチポートで
   あり、上記エキストラクタ手段は上記ページングメモリ
   の１つのポートに接続されたデータおよびアドレスバス
   を有する請求項７記載の付加処理装置。
9. 【請求項９】 上記ソート手段は上記データベースレコ
   ードのフロントバックマージを実行するための手段を有
   する請求項５記載の付加処理装置。
10. 【請求項１０】 上記ソート手段は上記データベースレ
    コードの４ウェイマージ／ソートを実行するための手段
    を有する請求項５記載の付加処理装置。
11. 【請求項１１】 中央処理装置と、 ページアドレス可能なデータを記憶するためのページ記
    憶手段と、 上記中央処理装置および上記ページ記憶手段に接続され
    た、直接アドレス可能なデータを記憶するための主記憶
    手段と、 上記中央処理装置の介在なしに上記ページアドレス可能
    なデータにアクセスするためのインターフェイス手段を
    有する、上記ページ記憶手段に接続されたデータベース
    処理装置とを有するコンピュータシステム。
12. 【請求項１２】 制御装置、ワーキングメモリおよび独
    立に制御可能な複数の処理エレメントを有する処理装置
    においてリレーショナルデータベース機能を実行する方
    法であって、 （ａ） ホストコンピュータのシステムメモリから、デ
    ータベースコマンドと、上記データベースコマンドの処
    理中に用いるべき述語の上記システムメモリにおける記
    憶位置とをフェッチする段階と、 （ｂ） 上記データベースコマンドを、実行すべき所定
    のデータベース処理動作のシーケンスに分解する段階
    と、 （ｃ） 段階（ｂ）で識別された上記データベース処理
    動作のそれぞれを実行するために上記処理エレメントを
    選択する段階と、 （ｄ） 上記選択された処理エレメントを上記ホストコ
    ンピュータと独立に制御して、所定のデータベース動作
    の上記シーケンスを実行する段階と、 （ｅ） 上記ワーキングメモリに段階（ｄ）の実行結果
    を一時的に収集する段階と、 （ｆ） 段階（ｅ）で収集された上記結果を上記システ
    ムメモリにアセンブルする段階と を有することを特徴とする方法。
13. 【請求項１３】 （ｇ） 上記システムメモリにおける
    上記記憶位置から上記述語を読み出す段階と、 （ｈ） 上記制御装置に述語評価命令を生成させる段階
    と、 （ｉ） 上記複数の処理エレメントのうちのあらかじめ
    選択された１つの処理エレメントに上記述語評価命令を
    ロードする段階と、 （ｊ） 上記あらかじめ選択された１つの処理エレメン
    トに、上記述語評価命令に従って上記述語を処理させる
    段階と を更に有する請求項１２記載の方法。
14. 【請求項１４】 外部処理装置から述語評価プログラム
    を受け取って記憶するための命令テーブル手段と、 上記命令テーブル手段に接続された、実行すべき命令を
    上記命令テーブル手段から受け取るための命令レジスタ
    手段と、 上記命令レジスタ手段に接続された命令制御手段に接続
    された、上記述語評価プログラムに従って動作シーケン
    スを制御するための内部処理装置手段と、 上記命令レジスタ手段に接続された、述語評価照会が解
    決されたときを決定し、上記内部処理装置手段に、上記
    照会を処理するための上記述語評価プログラムの命令の
    分岐を行わせるための分岐手段と、 上記述語評価プログラムの処理中にデータを一時的に保
    持するためのスタックと、 上記内部処理装置手段に接続された、上記スタックの先
    頭からの第１の値をワーキングストアから得られる第２
    の値と比較するための比較手段とを有する、述語評価を
    実行するための装置。
15. 【請求項１５】 複数のデータベースレコードに対応し
    た複数のエントリを有し、上記複数のエントリのそれぞ
    れが各上記データベースレコード中の少なくとも１つの
    フィールドを示す抽出ビットマスクと、 第１のメモリにおける上記データベースレコードの第１
    のアドレスと、 第２のメモリにおける第２のアドレスとを有するマッピ
    ングテーブル手段と、 上記マッピングテーブル手段に接続された、上記第１の
    メモリの上記第１のアドレスから上記複数のデータベー
    スレコードのうちの１つのデータベースレコードを読み
    出すためのメモリ要求手段と、 上記メモリ要求手段に接続された、上記１つのデータベ
    ースを記憶するための第１の記憶手段と、 上記第１の記憶手段および上記マッピングテーブル手段
    に接続された、上記抽出ビットマスクに応答して上記１
    つのデータベースレコードからデータを抽出するための
    クロスポイントスイッチ手段と、 上記クロスポイントスイッチ手段に接続された、上記ク
    ロスポイントスイッチ手段から抽出されたデータを受け
    取り、上記データを上記第２のメモリの上記第２のアド
    レスに書き込むための第２の記憶手段とを有するデータ
    ベースフィールドエキストラクタ。
16. 【請求項１６】 第１の処理装置から抽出要求を受け取
    り、待機させるための要求待ち行列手段と、 上記要求待ち行列手段および上記マッピングテーブル手
    段に接続された、上記要求待ち行列手段から１つの抽出
    要求を読み出し、上記１つの抽出要求中で識別されたデ
    ータベースレコードに対応した上記マッピングテーブル
    手段の１つのエントリをアドレスするための制御手段と
    を更に有し、 上記マッピングテーブル手段は上記制御手段によりアド
    レスされた上記エントリを受け取るための第３の記憶手
    段を更に有し、上記クロスポイントスイッチ手段は上記
    第３の記憶手段によって上記マッピングテーブル手段に
    接続されている請求項１５記載のデータベースフィール
    ドエキストラクタ。
17. 【請求項１７】 システムメモリを有するホストコンピ
    ュータに用いるためのデータベースフィールドエキスト
    ラクタであって、 複数のデータベースレコードに対応した複数のエントリ
    を有し、上記複数のエントリのそれぞれが各上記データ
    ベースレコード中の少なくとも１つのデータフィールド
    を示す抽出ビットマスクを保持するための制御フィール
    ドと、 第１のメモリにおける第１のアドレスを保持するための
    第１のアドレスフィールドと、 上記システムメモリにおける第２のアドレスを保持する
    ための第２のアドレスフィールドとを有するマッピング
    テーブルと、 第１のバッファと、 第２のバッファと、 上記第１のバッファおよび上記第２のバッファに接続さ
    れた、上記抽出ビットマスクを受け取るように上記マッ
    ピングテーブルに接続された制御入力を有するクロスポ
    イントスイッチとを有することを特徴とするデータベー
    スフィールドエキストラクタ。
18. 【請求項１８】 複数のキーをソートおよびマージする
    ための装置であって、 独立におよび同時にアクセス可能な第１および第２のア
    ドレス可能な領域を有する、上記複数のキーをそれぞれ
    のメモリアドレスに記憶するための第１のメモリアレイ
    手段と、 上記複数のキーのメモリアドレスを記憶するための第２
    のメモリアレイ手段と、 上記複数のキーのメモリアドレスを記憶するための第３
    のメモリアレイ手段と、 上記第２および第３のメモリアレイ手段を交互に書き込
    み可能とするための書き込み手段と、 上記第１のメモリアレイ手段に接続された、上記第１の
    アドレス可能な領域からの第１のキーを上記第２のアド
    レス可能な領域からの第２のキーと比較するための比較
    手段と、 上記第１のメモリアレイ手段、上記第２のメモリアレイ
    手段、上記第３のメモリアレイ手段、上記書き込み手
    段、カウンタ手段および上記比較手段に接続された、上
    記第２および第３のメモリアレイ手段のうちの書き込み
    可能とされていない一方から第１および第２のキーの第
    １および第２のアドレスを読み出し、上記第１のメモリ
    アレイ手段の上記第１および第２の領域を上記第１およ
    び第２のアドレスでアドレスし、上記比較手段によるキ
    ーの比較に応答して上記第２および第３のメモリアレイ
    手段のうちの書き込み可能とされた方に勝利キーを書き
    込むための制御手段とを有することを特徴とする装置。