JPH04213111A - データソート方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】

【０００１】

【技術分野】本発明はデータソート方式に関し、特に主
記億装置内に一度読込むことができない量のデータをワ
ークファイルを用いてソートするデータソート方式に関
するものである。

【０００２】

【従来の技術】主記憶装置内に一度に読込むことができ
ないデータ量を、ワークファイルを用いてソートするソ
ート処理では、主記憶装置内にレコードを１つづつ読込
みつつソートの中間結果であるストリングと称する順序
付けられたレコード列を複数本作成し、しかる後にこの
うちの何本かのストリングを互いにマージし、新たなス
トリングを作成する。そして、上記処理を繰返して最終
的に１本のストリングとするマージ作業を行うようにな
っている。

【０００３】更に詳しく述べると、ストリング同士を互
いにマージして新たなストリングを作成する場合、先ず
ワークファイル内の各ストリングの先頭レコードから主
記憶装置内のソートメモリ領域へ１つづつレコードを入
力し、これ等の各レコードをソートしてあるレコードが
勝者になると、このレコードをワークファイルへ出力す
る。そして、このレコードが属していたストリングから
次のレコードをソートメモリ領域へ入力し、再びソート
メモリ領域内のレコード同士をソートして勝者を決定す
る。この勝者のレコードをワークファイル内の前の勝者
レコードの後に書込んで新たなストリングを作成する。

【０００４】以上の処理を繰返すことで複数のストリン
グを１本のストリングにまとめるのがマージ処理作業で
ある。

【０００５】このマージ処理作業中に、１本のストリン
グを除いて全てのストリングのレコードを処理し終って
も、主記憶装置内のソートメモリ領域にレコードが残っ
ているストリングからレコードをソートメモリ領域へ入
力し、レコードがなくなったストリングの代わりに無限
大のキーを有するダミーデータをソートメモリ領域内の
レコードと対戦させることにより、勝者レコードを決定
してワークファイルへ出力するようになっている。

【０００６】また、ワークファイル内の全てのストリン
グを１度にマージし、ソート結果を出力するソートの終
了処理においても、１本のストリングを除き全てのスト
リングのレコードを処理し終っても、ソートメモリ領域
にレコードが残っているスリトングからレコードを入力
して、レコードのなくなったストリングのデータの代り
に、無限大のキーを持つダミーデータをメモリ内のレコ
ードと対戦させることにより勝者レコードを決定し、出
力ファイルへ出力している。

【０００７】上述したような従来の技術の方式を用いて
ソート処理を行った場合、ストリングのマージ処理時、
レコードの残っているストリングが１本だけになっても
、このレコードをダミーデータと対戦させることでソー
トを行うことになるため、余分な処理時間がかかるとい
う欠点がある。

【０００８】また、ストリングをマージして新規ストリ
ングを作成する際、レコードの残っているストリングが
１本だけになっても、主記憶に残りのレコードを入力し
てからワークファイルに出力することにもなるため、ワ
ークファイルへの入出力回数が多くなり、性能が低下す
るという欠点がある。

【０００９】

【発明の目的】本発明の目的は、ソート処理時間を短縮
してソート性能を向上させることが可能なワークファイ
ルを用いたデータソート方式を提供することである。

【００１０】

【発明の構成】本発明によるデータソート方式は、主記
憶装置内にレコードを１つづつ読込みつつソートの中間
結果であるストリングと称する順序付けられたレコード
列を複数本作成し、このうちの何本かのストリングをマ
ージして新たなストリングを作成するソート中間処理を
含むデータソート方式であって、前記ストリングを格納
しておくためのランダムアクセス可能なワークファイル
と、ソートの対象となるレコードを一時記憶するために
主記憶内に設けられたソートメモリ領域と、前記ワーク
ファイル上でストリング同士を互いにリンクするストリ
ング手段と、ソート処理を行うソート主処理手段とを設
け、前記ソート主処理手段は、前記ソート中間処理のマ
ージ作業中に、１本のストリングを除いた全てのストリ
ングのレコードのマージが終了すると、前記ソートメモ
リ領域内に残っているレコードを前記ワークファイルへ
出力した後、レコードが残っている前記１本のストリン
グを作成中のストリングの後に前記ワークファイル上で
リンクする様前記ストリングリング手段を制御するよう
にしたことを特徴とする。

【００１１】本発明による他のデータソート方式は、主
記憶装置内にレコードを１つづつ読込みつつソートの中
間結果であるストリングと称する順序付けられたレコー
ド列を複数本作成し、このうちの何本かのストリングを
マージして新たなストリングを作成し、上記作業を繰返
して最終的に１本のストリングとするソート最終処理を
含むデータソート方式であって、前記ストリングを格納
しておくためのランダムアクセス可能なワークファイル
と、ソート対象となるレコードを一時記憶するために主
記憶装置内に設けられたソートメモリ領域と、マージさ
れたレコードを１つづつ書込む出力ファイルと、ソート
処理を行うソート主処理手段とを設け、前記ソート主処
理手段は、マージ作業中に１本のストリングを除いた全
てのストリングのレコードのマージが終了すると、前記
ソートメモリ領域内に残っているレコードを前記出力フ
ァイルへ出力してこのマージ作業を終了せしめ、前記ワ
ークファイル内のレコードの残っているストリングから
前記ソートメモリ領域へ順次書込み、この書込んだレコ
ードを前記出力ファイルへ順次出力してソート最終処理
を行うようにしたことを特徴とする。

【００１２】

【実施例】以下、図面を用いて本発明の実施例を説明す
る。

【００１３】図１は本発明の実施例の機能ブロック図で
ある。１はソートの中間結果であるストリングと呼ぶ順
序付けられたレコード列を格納しておくための補助記憶
装置上のランダムアクセス可能なワークファイル、１１
、１２、１３はワークファイル１に出力された各ストリ
ング、２はソート結果を出力する出力ファイル、３はソ
ート主処理手段、４は主記憶装置、４１はソートの対象
となるレコードを読込むための主記憶装置４上のソート
メモリ領域、５はワークファイル１内のストリングより
１レコードをソートメモリ領域４１に読込むワークファ
イル入力手段、６はソートメモリ領域４１より１レコー
ドをワークファイル１にストリングとして書込むワーク
ファイル出力手段、７はワークファイル１内のストリン
グとストリングをリンクするストリングリンク手段、８
はソートメモリ領域４１より１レコード出力ファイル２
に出力する出力手段である。

【００１４】始めに、図１を用いてソート主処理手段３
の処理手順の概要を説明する。ソート主処理手段３はソ
ートするレコードを順次ソートメモリ領域４１へ読込み
つつソートして行き、ワークファイル１にストリングを
複数個出力し、ワークファイル入力手段５によって、こ
れらのストリングからレコードを再びソートメモリ領域
４１に読込んで、マージすることでソートを行う。

【００１５】このとき、ワークファイル１内に作成され
ているストリングを全て１度にマージできるソートメモ
リ領域４１がない場合、これらのストリングのうち、何
本かづつをマージして、ワークファイル出力手段６によ
り、新たにストリングをワークファイル１に出力し、ス
トリングの本数を減らしていく。

【００１６】最終的に、ワークファイル１内のストリン
グが全て１度にマージできる本数になったとき、出力手
段８によって、このマージ結果のレコードを出力ファイ
ル２に順次出力する。

【００１７】次に、ソート主処理手段３の処理のうち、
何本かのストリングをマージして、新しいストリングを
作成していく処理、およびこの処理で用いられるワーク
ファイル入力手段５、ワークファイル出力手段６、スト
リングリンク手段７の動作について、図２を参照しなが
ら詳細に説明する。

【００１８】ここではストリングリンク手段７として、
ストリングのワークファイル１内位置及びリンクされた
ストリングへのポインタを持つストリング情報テーブル
２１０　を用意し、これを操作することでストリングの
リンク処理を行うものとする。

【００１９】図２（Ａ）に示す如く、ストリングのマー
ジ処理に移る時点で、それまでに作成したストリング２
０１　〜２０３　のワークファイル内の各位置ａ、ｂ、
ｃがストリング情報テーブル２１０　に格納されている
とする。

【００２０】まず、現在マージすべきワークファイル１
の各ストリングのアドレスａ、ｂ、ｃをストリング情報
テーブル２１０　から取出し、各々のストリングの先頭
レコードを、ワークファイル入力手段４を用いてソート
メモリ領域４１へ入力し、これらのレコードを対戦させ
てソートする。

【００２１】ソートの結果、図２（Ｂ）に示す如く最も
強いレコード（本例ではストリング２１０　のレコード
）をワークファイル出力手段６を用いてワークファイル
１へ出力する。新規作成ストリング２０４　のワークフ
ァイル１内位置ｄはストリング情報テーブル２１０　に
格納される。 さらに、このレコードの属していたストリング２０１　
から次のレコードを入力する。

【００２２】以降、順次勝者レコードをワークファイル
１に出力し、そのレコードが属していたストリングより
レコードを入力し、ソートメモリ領域４１内のレコード
と対戦させることで、ストリングのマージ処理を行って
いく。

【００２３】図２（Ｃ）に示す如く、ストリング２０１
　、２０２　のレコードを全てソートメモリ領域４１へ
入力し、レコードの残っているストリングが２０３　だ
けになったとき（ハッチングで示すレコードが処理終了
レコードである）、ソートメモリ領域４１に残ったレコ
ードを全てソートして、ワークファイル１内のストリン
グ２０４　へつなぐ。

【００２４】次にストリングリンク手段７を呼出し、ス
トリング２０３　に残っているレコードのワークファイ
ル１内位置ｅをストリング情報テーブル２１０　に格納
し、更にこのエリアへ、ストリング情報テーブル２１０
　内のストリング２０４　の続きとしてポインタを付け
る。これにより、ストリング２０３　の残りのレコード
をストリング２０４　にリンクすることがでる。

【００２５】これで、ストリング２０１　、２０２　、
２０３　のマージ作業は終る。以降、上記で作成したス
トリング２０４　を別のストリングとマージするときは
、ストリング２０４　から順次レコードをソートメモリ
領域４１へ入力してソートし、ストリング２０４　のレ
コードが終了したら、ストリング情報テーブル２１０　
内のポインタによりストリング２０３　を取出し、スト
リング２０３　からレコードを入力していく。

【００２６】次にソート主処理手段３のうち、ワークフ
ァイル１内の全てのストリングをマージして、出力ファ
イル２にソート結果を出力するソート最終処理、および
この処理で用いられるワークファイル入力手段５、出力
手段８の動作について図３を参照しながら詳細に説明す
る。

【００２７】ます、図３（Ａ）に示す様に、ワークファ
イル１内の各々のストリング３０１　〜３０３　の先頭
レコードを、ワークファイル入力手段４を用いてソート
メモリ領域４１へ入力し、ソート主処理手段３によりこ
れらのレコードを対戦させてソートする。

【００２８】ソートの結果、図３（Ｂ）に示す如く最も
強いレコード（本例ではストリング３０１　のレコード
）を出力手段８を用いて出力ファイル２へ出力する。さ
らに、このレコードの属していたストリング３０１　か
ら次のレコードを入力する。

【００２９】以降、順次勝者レコードを出力ファイル２
へ出力し、そのレコードが属していたストリングよりレ
コードを入力し、ソートメモリ領域４１内のレコードと
対戦させることで、ソート結果を出力していく。

【００３０】ストリング３０１　、３０２　のレコード
を全てメモリ領域４１へ入力し、図３（Ｃ）に示す如く
レコードの残っているストリングが３０３　だけになっ
たとき、ソートメモリ領域４１に残ったレコードを全て
ソートして、出力ファイル２へ出力する。

【００３１】この後、図３（Ｄ）に示す如く、ストリン
グ３０３　より、残りのレコードをワークファイル入力
手段５を用いて、ソートメモリ領域４１へ順次入力し、
レコードを対戦させずにそのまま出力ファイル２へ出力
手段８を用いて出力する。

【００３２】

【発明の効果】以上述べた如く、本発明によれば、スト
リングのマージ処理時にレコードが残っているストリン
グが１本だけになった後、このストリングのレコードを
ダミーデータと対戦させることなく処理できるので、ソ
ート処理時間が短縮可能となり、またこの残りのレコー
ドのワークファイルへの入出力を行わなくて良いので、
ソート性能が向上するという効果がある。

【図面の簡単な説明】

【図１】本発明の実施例を示す機能ブロック図である。

【図２】本発明の実施例によるソート中間処理手順を説
明する図である。

【図３】本発明の実施例によるソート最終処理手順を説
明する図である。

Claims (2)

【特許請求の範囲】
1. 【請求項１】　　主記憶装置内にレコードを１つづつ読
   込みつつソートの中間結果であるストリングと称する順
   序付けられたレコード列を複数本作成し、このうちの何
   本かのストリングをマージして新たなストリングを作成
   するソート中間処理を含むデータソート方式であって、
   前記ストリングを格納しておくためのランダムアクセス
   可能なワークファイルと、ソートの対象となるレコード
   を一時記憶するために主記憶内に設けられたソートメモ
   リ領域と、前記ワークファイル上でストリング同士を互
   いにリンクするストリング手段と、ソート処理を行うソ
   ート主処理手段とを設け、前記ソート主処理手段は、前
   記ソート中間処理のマージ作業中に、１本のストリング
   を除いた全てのストリングのレコードのマージが終了す
   ると、前記ソートメモリ領域内に残っているレコードを
   前記ワークファイルへ出力した後、レコードが残ってい
   る前記１本のストリングを作成中のストリングの後に前
   記ワークファイル上でリンクする様前記ストリングリン
   グ手段を制御するようにしたことを特徴とするデータソ
   ート方式。
2. 【請求項２】　　主記憶装置内にレコードを１つづつ読
   込みつつソートの中間結果であるストリングと称する順
   序付けられたレコード列を複数本作成し、このうちの何
   本かのストリングをマージして新たなストリングを作成
   し、上記作業を繰返して最終的に１本のストリングとす
   るソート最終処理を含むデータソート方式であって、前
   記ストリングを格納しておくためのランダムアクセス可
   能なワークファイルと、ソート対象となるレコードを一
   時記憶するために主記憶装置内に設けられたソートメモ
   リ領域と、マージされたレコードを１つづつ書込む出力
   ファイルと、ソート処理を行うソート主処理手段とを設
   け、前記ソート主処理手段は、マージ作業中に１本のス
   トリングを除いた全てのストリングのレコードのマージ
   が終了すると、前記ソートメモリ領域内に残っているレ
   コードを前記出力ファイルへ出力してこのマージ作業を
   終了せしめ、前記ワークファイル内のレコードの残って
   いるストリングから前記ソートメモリ領域へ順次書込み
   、この書込んだレコードを前記出力ファイルへ順次出力
   してソート最終処理を行うようにしたことを特徴とする
   データソート方式。