JPS6162134A - ソ−ト前処理装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 ［発明の技術分野］ この発明は、特にソート処理の効率化のために、ソート
処理の対象レコードに前処理を施すソー１〜前処理装置
に関する。

［発明の技術的背景］ 関係データベースなどのデータベース処理における主た
る処理の１つにソート処理がある。このソート処理は、
特定のファイル中の複数のレコードの並びを、レコード
中の指定されたキーフィールドの値に従って所定の順序
に並び賛えることである。上記したソート処理は、汎用
電子計（５１１でも実行可能である。しかし、汎用電子
計算機が取出中、「データベース処理や文書処理を高速
化するサーチ／ソート・ハードウェアの動向」、「日経
エレクトロニクスｊ　、　１９８３年８月　１日号、　
ｐｐ。

１４１−１７８　、に示される（特にｐｐ、　１６４−
１６５　、　）ようなマージソート方式のソート処理装
置が知られている。このソート処理装置は、一般に多段
に縦続接続された複数のソート・セルからなる。ｎ段目
のソート・セルは、前段のソート・セルまででソートさ
れている２ｎ　−１個のレコードを２組入力し、２ｎ個
のレコードをソートし、次段に出力する機能を有してい
る。このソート・セルのソート処理においては、各組か
らその入力順にそれぞれ１個のレコードが選択され、２
個のレコード間のキーフィールドの比較が行なわれ、そ
の比較結果に応じて出力すべきレコードが確定される。

このため、上記したソート処理装置においては、キとす
る欠点があった。また、指定されたキーフィてからキー
フィールドの比較が終了するまでに長時間を要し、ソー
ト処理速度が低下する欠点もあった。

［発明の目的］ この発明は上記事情に鑑みてなされたものでその目的は
、ソート対象レコードに前処理を施し、指定されたキー
フィールドをレコードの先頭に３動させることにより、
ソート処理においてレコードの先頭で比較処理が行なえ
、もってソート処理装置におけるソート処理の高速化が
図れ、且つキーフィールドに先行するデータをバッファ
リングするためのメモリを不要にできるソート前処理装
置を提供することにある。

段は、このメモリを、ソート処理において比較対比され
たデータ（即ち、その先頭に指定キーフィールドが移動
されたレコード）は、ソート処理対象データ（レコード
）としてソート処理装置に供給される。

［発明の実施例］ 第１図はこの発明の一実施例に係るソート前処理装置の
構成を示す。このソート前処理装置は、ソート処理装置
の入力側に置かれる。第１図において、１１はソート処
理の対象となるルコード分のデータを一時格納するメモ
リ、１２はメモリ１１に接続されるデータ入力ライン、
１３はメモリ１１に接続されるデータ出力ラインである
。１４はメモリ１１に対する書込みアドレスＷＡを保持
するアドレスレジスタ、１５はメモリ１１に対する読出
しアドレスＲＡを保持するアドレスレジスタである。ア
ドレスレジスタ１４．　Ｉｓはカウンタ機能を有する。

１６はメモリ１１に対する読出し開始アドレスＩＡＰ）
と−１との加算を行なう加算器である。１８はフサ、１
９はアドレスレジスタ１４．１５の各内容（ＷＡ、ＲＡ
）のいずれか一方を、メモリ１１に対するアドレスとし
て選択するマルチプレクサである。

２０はソート処理の対象となるレコードのレコード長Ｒ
８Ｚ　（実際にはＲ３Ｚ−１、単位はバイト）を保持す
るサイズレジスタ、２１はアドレスレジスタ１４および
サイズレジスタ２０の各内容（ＷＡ、Ｒ８Ｚ）を比較し
て一致を検出する比較器である。

２２はアドレスレジスタ１５およびサイズレジスタ２０
の各内容（ＲＡ、Ｒ８Ｚ）を比較して一致を検出する比
較器、２３はアドレスレジスタ１５および−１回路１７
の各内容（ＲＡ、ＩＡＰ−１）を比較して一致を検出す
る比較器、２４は制御回路である。制御回路２４は、比
較器２１〜２３からの一致検出信号に応じて、マルチプ
レクサ１８．１９の切換え制御、更には上位装置（図示
せず）への終了割込みなどを行なう。

、イヒにより、アドレスレジスタ１４がクリアされ、■
１；−１ Ａ’Ｐレジスタ１６に読出し開始アドレスｒＡＰがセッ
トされる。この読出し開始アドレスＩＡＰには、ソート
対象となる各レコードにおける比較対象データ、即ちキ
ーフィールドの位置（レコード゛の先頭からのバイト位
置）を示す情報が用いられる。

また、サイズレジスタ２０に、ソート対象レコードのレ
コード長Ｒ８Ｚがセットされる。以上の初期化処理が行
なわれると、データ入力ライン１２を介してソート対象
レコードがメモリー１に導ｈ１れる。

しかして、制御回路２４の制御の下で、マルチプレクサ
１９によりアドレスレジスター４．１５のうちのアドレ
スレジスター４が選択され、アドレスレジスタ１４から
の書込みアドレスＷＡに基づいて、メモ１ノ１１への書
込み動作が行なわれる。アドレスレジスタ１４は１バイ
ト書込みごとに＋１され、これによりデータ入力ライン
１２上のレコードが、メモリー１の「０」番地から始ま
る連続領域に１バイ１−１１位すると、その旨を制御回
路２４に通知する。制御口！１ ；路２４は、メモリーに対するレコードの書込みモード
において、比較器２１から一致が通知されると、−ルー
コードの最終バイトの書込みとなるものと￥Ｊ１断し、
そのサイクルの終了時に書込みモード力＼ら　　　　Ｊ
ｌ＋読出しモードに変更する。このとき、メモ１ノ１１
のｒＯＪ番地からｒＲ８Ｚ−ＩＪ番地の領域（こ警よ、
第２図（ａ）に示すようにルコード分のデータが書込ま
れている。また、レコード中の（指定された）キーフィ
ールドの先頭バイトは、ｒＩＡＰＪ番地に書込まれてい
る。

制御回路２４は、読出しモードにおいて、まずマルチプ
レクサ１８を制御し、ＩＡＰレジスタ１６からの読出し
開始アドレスＩＡＰ、または固定値゛０″（０番地を示
すアドレス）のうち、読出し開始アドレスＩＡＰを選択
せしめ、同ＩＡＰをアドレスレジスタ１５にセットする
。なお、この動作を、上記した初期化時に行なうことも
可能である。そして、制御回路２４は、マルチプレクサ
１９を制御して、メモリ１１に対するアドレスを、アド
レスレジスタ３理装置（図示せず）に導かれる。

ニー“１１．比較器２２．よ、アｔ’　Ｌ／２　Ｌ／、
：）、　９１５カ、ら、７）読出。

アドレスＲＡとサイズレジスタ２０からのレコード。

長Ｒ８Ｚとを比較しており、ＲＡがＲ８Ｚに一致すると
、その旨を制御回路２４に通知する。制御回路２４は、
メモリ１１からのレコードの読出しモードにおいて比較
器２２から一致が通知されると、ルーコードの最終バイ
トの読出しとなるものと判断し、マルチプレクサ１８を
切換え制御する。そして、制御回路２４は、マルチプレ
クサ１８から新たに選択された固定値゛０゛′を、その
サイクルの終了時に、アドレスレジスタ１５にセットせ
しめる。これにより、メモリ１１に対する読出しアドレ
スＲＡはｒＯＪ番地に戻り、メモリ１１の「０」番地か
ら順に１バイト単位でデータが読出される。即ち、（キ
ーフィールドの先頭バイトから）レコードの最終バイト
までが読出されることが検出されると、次のすしている
。−１回路１７からの出力値は、ＩＡＰし＋！−’ｐ：
スタ１６の保持内容である読出し開始アドレス１１： ′　ＡＰから１を減じたＩＡＰ−１である。比較器２３
１．：。

１・′１は、ＲＡがＩＡＰ−１に一致したことを検出す
ると、その旨を制御回路２４に通知する。制御回路２４
は、メモリー１からのレコードの読出しモードにおいて
比較器２３から一致が通知されると、キーフィールドの
直前バイトの読出しとなるものと判断し、次のサイクル
で上位装置にルーコードの処理終了を示す割込みを発し
、メモリー１からの読出しを停止する。そして、第１図
のソート前処理装置では、上位装置からの指示により、
次のルーコードについての前処理が再び行なわれる。

上記したように、第１図のソート前処理装置では、ソー
ト処理対象レコードを−Ｈメモリー１に書込んだ後、Ｉ
ＡＰで示されるバイト位置からレコードエンドまでのデ
ータ、即ちソート処理対象レコード中の指定されたキー
フィールドの先頭バイトから同レコードの最終バイトま
でが、１バイ１〜単位で読出し出力され、次に残りのデ
ータ、即ち移動されたソート処理対象レコードが供給さ
れる。

下、゛こ− °パなお、前記実施例では、まずキーフィールドの仝←
バイトからレコードの最終バイトまでを読出！じ、；次
にレコードの先頭バイトからキーフィールドの直前バイ
トまでを読出す場合について説明したが、これに限るも
のではない。例えば、まずキーフィールドを読出し、次
にレコードの先頭バイトからキーフィールドの直前バイ
トまでを読出し、最後にキーフィールドの次のバイトか
らレコードの最終バイトまでを読出すようにしてもよく
、要はキーフィールドがレコード先頭に移動されるよう
に処理が施されればよい。但し、この場合には、指定キ
ーフィールドのフィールド長ＶＤＬを保持するレジスタ
、このレジスタの内容と読出しアドレスＲＡとによりキ
ーフィールドの最終バイトが読出されることを検出する
手段、更にはキーフィールドの次のバイトからの読出し
に際し、ＩＡＰ＋ＶＤＬを読出しアドレスＲＡとして設
定する手段等が必要となる。

［発明の効果］ 以上詳述したようにこの発明によれば、ソート処理装置
に供給することにより、ソート処理装置では、キーフィ
ールドの比較結果をいちはやく確定できるので、ソート
処理速度が向上する。また、キーフィールドがレコード
の先頭にあることから、従来のようにキーフィールドが
到来するまで（比較対象とならない）データを保持する
必要がなく、したがってそのためのバッファメモリなど
が不要となる。なお、２１１１のレコード間でのキーフ
ィールドの比較は、その先頭から所定バイト単位で比較
結果が確定するまで行なわれるが、値が等しいときは２
個のレコードのいずれの比較データを出力してもよいの
で、一致判定された比較済みデータを比較結果が確定す
るまで保持しておく必要がない。したがって、ソート処
理装置において上記したバッフ７メモリを持たない場合
の不都合はない。

【図面の簡単な説明】

第１図はこの発明の一実施例に係るソート前処理装置の
ブロック構成因、第２図は第１図の装置の動作を説明す
る図である。 １１・・・メモリ、１４．１５・・・アドレスレジスタ
、１６・・・ＩＡＰレジスタ、２０・・・サイズレジス
タ、１８．１９・・・マルチプレクサ、２１〜２３・・
・比較器、２４・・・制御回路。

Claims (1)

【特許請求の範囲】
1. ソート処理の対象となる１レコード分のデータを所定ア
   ドレスから始まる連続領域に格納するメモリと、このメ
   モリを、ソート処理において比較対象となる指定キーフ
   ィールドの先頭位置に対応するアドレスから順にリード
   アクセスして上記キーフィールドを読出す第１読出し手
   段と、上記メモリ内の残りデータを読出す第２読出し手
   段とを具備し、上記メモリから読出されるデータをソー
   ト処理対象データとしてソート処理装置に供給すること
   を特徴とするソート前処理装置。