JPH04141726A

JPH04141726A - ソート処理方式

Info

Publication number: JPH04141726A
Application number: JP26573890A
Authority: JP
Inventors: Yoichi Ueda; 洋一上田
Original assignee: NEC Corp
Current assignee: NEC Corp
Priority date: 1990-10-03
Filing date: 1990-10-03
Publication date: 1992-05-15
Anticipated expiration: 2011-10-09
Also published as: JP2541006B2

Abstract

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

Description

【発明の詳細な説明】〔産業上の利用分野〕本発明は、一般には、主記憶装置内に一度に読み込むこ
とができない量のデータを、ワークファイルを用いてソ
ートするソート処理方式に関する。

〔従来の技術〕

従来、主記憶装置内に一度に読み込むことができない量
のデータを、ワークファイルを用いてソートするソート
処理においては、主記憶装置内にデータを一度に読み込
むことができなかった場合、たとえそれまでにワークフ
ァイルに出力したストリングが１本で、かつ主記憶装置
内に次のストリングのレコードとしてレベル付けられた
レコードが存在しない場合でも、−旦主記憶装置内に残
っているレコードをストリングとしてワークファイルに
全て掃き出してからマージフェーズに移り、マージフェ
ーズにおいて、そのストリングを読み込み出力ファイル
に出力していた。

〔発明が解決しようとする課題〕

上述したように、従来の技術においては、主記憶装置内
にデータを一度に読み込むことができなかった場合、た
とえそれまでにワークファイルに出力したス）　ＩＪソ
ング１本で、かつ主記憶装置内に次のストリングのレコ
ードとしてレベル付けられたレコードが存在しない場合
でも、−旦主記憶装置内に残っているレコードをストリ
ングとしてワークファイルに全て掃き出してからマージ
フェーズに移り、マージフェーズにおいて、そのストリ
ングを読み込み出力ファイルに出力していたため、主記
憶装置に入りきれなかったデータが、主記憶装置の容量
に比べてごく少量であるような場合でも、主記憶装置に
入りきれなかったデータだけでなく入力した全データを
ワークファイルに書き出し、そのあと同量のデータをワ
ークファイルから読み込まなければならないため、ワー
クファイルへの入出力回数が急増し、それがシステムの
性能低下を引ぎ起こしてしまう欠点があった。

〔課題を解決するための手段〕本発明は、主記憶装置内に一度に読み込むことができな
い量のデータを、補助記憶装置上のワークファイルを用
いてソートするソート処理方式において、ソートすべき
レコードの格納された補助記憶装置上のソート入力ファ
イルと、ソート結果を格納する前記補助記憶装置上のソ
ート出力ファイルと、ソートの中間結果であるストリン
グと呼ぶ順序付けられたレコード列を格納する前記補助
記憶装置上のソートワークファイルと、主記憶装置上の
メモリ領域であって、ソートキーの比較によりソートさ
れる前記レコードを格納するレコード領域と前記レコー
ド領域内のレコード群のながの前記ソートキーの順序で
最も早く出方される最上位レコードのアドレスを格納す
る勝者レコードアドレス領域からなるソートメモリ領域
と、ソート処理を行うソート主処理手段と、前記ソート
入力ファイルから、前記ソートメモリ領域にレコードを
１件読み込む入力処理手段と、前記ソートメモリ領域か
ら、前記ソート出力ファイルにレコードを１件書き込む
出力処理手段と、前記ソートワークファイルから、前記
ソートメモリ領域にレコードを１件読み込むワークファ
イル入力処理手段と、前記ソートメモリ領域がら、前記
ソートワークファイルにレコードを１件書き込むワーク
ファイル出力処理手段と、前記レコード領域内に格納さ
れている定められたレコード群のなかの前記最上位のレ
コードを決定する内部ソート処理手段とから構成され、
前記ソート主処理手段は、前記ソート入力ファイルから
前記入力処理手段を用いて前記レコード領域内にレコー
ドを一件ずつ入力し、前記内部ソート処理手段を用いて
それまでに前記レコード領域内に入力されているレコー
ドの中の前記最上位のレコードを決定し、決定した前記
最上位レコードのアドレスを前記勝者レコードアドレス
領域に設定する処理を繰り返す第一の手段と、前記第一
の手段にて前記レコード領域が前記レコードで満杯とな
る前に前記入力レコードが終了した場合は、前記勝者レ
コードアドレス領域にアドレスが設定されている前記最
上位のレコードを前記出力処理手段を用いて前記ソート
出力ファイルへ出力し、次に前記レコード領域内に出力
′されずに残っている前記レコードがなくなるまで前記
レコードの中の前記最上位レコードを前記内部ソート処
理手段を用いて決定し前記決定された最上位レコードを
前記出力処理手段を用いて前記ソート出力ファイルに出
力する処理を繰り返す第二の手段と、前記第一の手段に
て前記レコード領域がレコードで満杯となった時点で前
記入力レコードが終了していない場合は、作成中ストリ
ングのレベルと次のストリングの前記レベルの２つのレ
ベルを設け、前記レコード領域内にすでに格納されてい
るレコードを、前記作成中ストリングにレベル付け、前
記レコード領域内に前記作成中ストリングとしてレベル
付けられた前記レコードがなくなるまで、前記勝者レコ
ードアドレス領域にアドレスが格納されている前記最上
位レコードを前記作成中ストリングのレコードとして前
記ワークファイル出力処理手段を用いて前記ソートワー
クファイルへ出力する出力処理と、次に前記レコード領
域内に残っているレコードの中の前記最上位レコードを
前記内部ソート処理手段を用いて決定し前記アドレスを
前記勝者レコードアドレス領域に設定する前記最上位１
ノコードの決定処理と、前記ソート入力ファイルから前
記入力処理手段を用いて前記レコード領域へレコードを
１件入力し、前記入力したレコードと前記勝者レコード
アドレス領域に前記アドレスが設定されている前記最上
位レコードと前記ソートキーを比較し、前記最上位レコ
ードが上位の場合は、入力した前記レコードを前記作成
中ストリングのレベルのレコードとし、前記入力したレ
コードが上位の場合は、入力した前記レコードを前記次
のストリングの前記レベルのレコードとしてそれぞれレ
ベル付ける前記レコードのレベル付け処理を順番に繰り
返す第一の掃き出し処理を行い次に前記次のストＩＪン
グとしてレベル付けられている前記レコード領域内のレ
コード群を前記作成中ストリングのレコードとしてレベ
ル付けし再び前記第一の掃き出し処理を繰り返して実行
する第三の手段と、前記第三の手段にて前記レコード領
域が満杯となった後に、前記入力レコードが終了した場
合で前記終了までに作成した前記ストリングの本数が２
本以上または、前記次のストリングとしてレベル付けら
れた前記レコードが前記レコード領域に存在している場
合に、前記レコード領域内に残っている前記レコードの
内まず、前記作成中ストリングとしてレベル付けられて
いる前記レコード群を対象として、前記レコード群のレ
コードが全て前記ストリングとして出力され前記レコー
ド領域からなくなるまで前記勝者レコードアドレス領域
にアドレスが設定されている前記最上位レコードの前記
ソートワークファイルへの前記ワークファイル出力処理
手段を用いた出力処理と、前記内部ソート処理手段を用
いた前記レコード領域内に残っているレコード群の前記
最上位レコードの決定と前記決定されたアドレスの前記
勝者レコードアドレス領域への設定の処理を繰り返す第
二の掃き出し処理を実行し、前記次のストリングとして
レベル付けられた前記レコード群があれば前記レコード
群を再び前記作成中ストリングとしてレベル付け前記レ
コード群に対して前記第二の掃き出し処理を縁り返し次
に前記ワークファイル入力処理手段を用いて、前記ワー
クファイルより前記ソートメモリ領域に前記ストリング
を読み込みながらマージし１本のス）　ＩＪソングまと
めて前記出力処理手段を用いて前記ソート出力ファイル
へ出力する第四の手段と、前記第三の手段にて前記レコ
ード領域が満杯となった後に、前記入力レコードが終了
した場合で、前記ス）　ＩＪソング本数が１本でかつ前
記レコード領域内に前記次のストリングとしてレベル付
けられている前記レコードが存在しないならば、前記勝
者レコードアドレス領域に前記アドレスが設定されてい
るレコードを、前記ワークファイル出力処理手段を用い
て前記ソートワークファイルへ出力し次に、前記ソート
ワークファイルに出力された前記ストリングの全レコー
ドについて前記ワークファイル入力処理手段を用いて前
記レコードを１件ずつ前記レコード領域内に入力し入力
した前記レコードを前記出力処理手段を用いて前記ソー
ト出力ファイルに出力し、最後に前記レコード領域に残
存している前記レコードが１件もなくなるまで、前記内
部ソート処理手段により残存している前記レコード群の
なかの前記最上位レコードを決定し前記最上位アドレス
を前記勝者レコードアドレス領域に設定する処理と、前
記出力処理手段により前記勝者レコードアドレス領域に
アドレスが設定されている前記最上位レコードを前記ソ
ート出力ファイルに出力する処理を繰り返す第五の手段
とから構成されることを特徴とする。

〔実施例〕

次に本発明について、図面を参照して説明する。

第１図は、本発明の一実施例を示すブロック図である。

第１図において、１はソートすべきレコードの格納され
た補助記憶装置上のソート入力ファイル、２はソート結
果を出力するための補助記憶装置上のソート出力ファイ
ル、３はソートの中間結果であるストリングと呼ぶ順序
付けられたレコード列を格納しておくための補助記憶装
置上のソートワークファイル、４はソートの対象となる
レコードを読み込むための主記憶装置上のメモリ領域で
あり、レコード領域４１、勝者レコードアドレス領域４
２からなるソートメモリ領域、５はソート主処理手段、
６はソート入力ファイル１から、ソートメモリ領域４に
レコードを１件読み込むための入力処理手段、７はソー
トメモリ領域４からソート出力ファイル２にレコードを
１件書き込むための出力処理手段、８はソートワークフ
ァイル３から、ソートメモリ領域４にレコードを１件読
み込むためのワークファイル入力処理手段、９はソート
メモリ領域４から、ソートワークファイル３にレコード
を１件書き込むためのワークファイル出力処理手段、１
０はレコード領域４１内に格納されている、定められた
レコード群のなかの、最上位のレコードを決定するため
の内部ソート処理手段である。

本実施例で説明するソート主処理手段５は、大きく分け
て４つの部分からなる。

以下、それぞれの部分の処理の詳細について説明する。

第１の部分は、ソート入力ファイル１からレコードを１
件ずつレコード領域４１に入力していきレコード領域４
１が満杯になるまでの処理、及びレコード領域４１が満
杯になる前に入力レコードが終了したときの処理の部分
である。

第２図は、ソート主処理手段５の第１の部分の処理ステ
ップを示す図である。

ソート主処理手段５はまずステップ２０１において、生
成したストリングの本数をカウントするための制御変数
りを１に、レコード領域４１内のレコードで作成中スト
リングに出力されるべきレコードとしてレベル付けられ
ているレコードの数を示すための制御変数Ｎに０を、レ
コード領域４１内のレコードで次のストリングに出方さ
れるべきレコードとしてレベル付けられているレコード
の数を示すための制御変数Ｍに０をそれぞれ初期値とし
て設定し、ステップ２０２でレコード領域４１内に入力
できるレコードの件数をＴに設定しソートを開始するた
めの準備を終了する。

ステップ２０３から実際のソートの処理に入り、まずス
テップ２０３において入力処理手段６を呼び出しソート
久方ファイルエがらレコード領域４１ヘレコードを１件
入力し、ステップ２０４で入力すべきレコードが尽きた
旨入力処理手段６から通知されたかをチエツクし、入力
すべきレコードが尽きた旨入力処理手段６から通知され
ていたならばステップ２０９以降のメモリ内ソートの処
理に分岐する。

第１の部分は、レコード領域４１が満杯になるまでの処
理であり、入力されたレコードはすべて作成中（最初の
）ストリングのレコードとしてレベル付ける。そのため
ステップ２０３で入力レコードがあった場合にはステッ
プ２０５においてＮに１を加算し、ステップ２０６では
入力したレコードのレベルをＬに設定する。

次にステップ２０７において、内部ソート処理手段１０
を用いてレコード領域４１内のレベルＬのレコード（こ
の時点は全レコードがレベルしてある）のなかの最上位
レコードを決定し、決定した最上位レコードのアドレス
を勝者レコードアドレス領域４２へ設定する。

次にステップ２０８ては、ＮとＴとを比較してレコード
領域４１か満杯になったかをチエツク、Ｎが１以上なら
ばレコード領域４１は満杯であるので第２の部分へ進み
、ＮがＴより小ならばステップ２０３へ戻り次のレコー
ドを入力する。

ステップ２０９以降は、レコード領域４１が満杯になる
前に入力レコードか終了した場合の処理（メモリ内ソー
トの処理）であり、ステップ２０９で入力レコード件数
Ｎが０であるかチエツクし、０であればソートを終了す
る。

入力レコード件数が０でない場合は、ステップ２１０に
おいて、勝者レコードアドレス領域４２にそのアドレス
か設定されている最上位レコードを、出力処理手段７を
用いてソート出力ファイル２へ出力した後、ステップ２
１１てＮを１減算する。

次にステップ２１２てまた出力されずにレコード領域４
１に残っているレコード数Ｎか０かチエツクし、０なら
ばソートを終了し、０でなければステップ２１３で、残
っているレコードのなかの最上位レコードを内部ソート
処理手段１０を用いて決定、そのアドレスを勝者レコー
ドアドレス領域４２に設定した後、ステップ２１０に戻
りそのレコードを出力、以下ステ、ツブ２１３，２１Ｃ
ＩＮがＯになるまで繰り返すことによりレコード領域４
１内に残っているレコードをソートしながらソート出力
ファイル２へ出力していく。

ソート主処理手段５の第２の部分は、レコード領域４１
が満杯になってから、入力レコードが終了するまでの間
の処理の部分である。

第３図は、ソート主処理手段５の第２の部分の処理ステ
ップを示す図である。

ソート主処理手段５は、ステップ３０１て、勝者レコー
ドアドレス領域４２にそのアドレスか設定されている、
それまでの対戦での最上位レコードをワークファイル出
力処理手段９を用いてソートワークファイル３へ出力し
、ステップ３０．２ではレコード領域４１内の、作成中
ストリングへ出力すべきレコードとしてレベル付けられ
ているレコード数を示す制御変数Ｎから１を減算する。

ステップ３０１でレコード領域４１からレコードを１件
出力したため、後述のステップ３０５で次のレコードを
１件入力するための空き領域がレコード領域４１に確保
されたことになる。

次にステップ３０３でＮがＯであるかを判断し、レコー
ド領域４１内に、作成中ストリングに出力すべきレコー
ドとしてレベル付けられているレコードがまた残ってい
るか調へ、残っていなければ、ステップ３１３からステ
ップ３１６まてのス）　ＩＪソング切り替えの処理を実
行した後ステップ３０４へ移行する。

作成中ストリングに出力すべきレコードとしてレベル付
けられているレコードかまた残っていれば、ステップ３
０４において、レコード領域４１内のレベルＬのレコー
ド（作成中ストリングに出力すべきレコードとしてレベ
ル付けられているレコード）のなかの最上位レコードを
内部ソート処理手段１０を用いて決定、そのアドレスを
勝者レコードアドレス領域４２へ設定し、ステップ３０
５で入力処理手段６を呼び出し、次の入力レコードを、
レコード領域４１へ入力する。

次にステップ３０６において、入力すべきレコードが尽
きた旨入力処理手段６から通知されたかをチエツクし、
入力すべきレコードが尽きた旨入力処理手段６から通知
されていたならばステップ３１７以降の第２の部分の最
終処理へ分岐する。

入力レコードがまだあったならば、ステップ３０７にお
いて、入力レコードと、勝者レコードアドレス領域４２
にアドレスが設定されている最上位レコードとを対戦さ
せる。

ステップ３０８ではステップ３０７の対戦結果を判定し
、勝者レコードアドレス領域４２てボされる最上位レコ
ードが勝ったならば、ステップ３０９で入力レコードの
レベルをＬに設定しステップ３１０てＮに１加算するこ
とにより、入力レコードのレベルを、作成中ストリング
へ出力すべきレコードとしてレベル付け、入力レコード
が勝ったならば、ステップ３１１で入力レコードのレベ
ルをＬ＋１（次のストリング）に設定し、ステップ３１
２でＭに１を加算することにより入力レコードのレベル
を、次のストリングへ出力すべきレコードとしてレベル
付けた後、ステップ３０１へ戻り、勝者レコードアドレ
ス領域４２にアドレスが設定されている最上位レコード
をソートワークファイル３へ出力する。

ステップ３１３からステップ３１６は、ストリングの切
り替えの処理であり、まずステップ３１３で、作成中ス
トリングに出力すべきレコードとしてレベル付けられて
いるレコード数を示す制御変数Ｎに、次のストリングに
出力すべきレコードとしてレベル付けられているレコー
ド数を示す制御変数Ｍの値を設定することにより次のス
トリングを作成中ストリングとした後、ステップ３１４
でＭにＯを再設定、ステップ３１５で、ストリングカウ
ントＬに１を加算した後、ステップ３１６でストリング
の切り替えを行った後、ステップ３０５へ移行し新しい
ストリングの処理に移る。

ステップ３１７以降は、第２の部分の最終処理であり、
ステップ３１７でそれまでにソートワークファイル３へ
生成したストリング数りが１か判定し１でなければ、第
３の部分に制御を移行し、１であればステップ３１８に
おいて、ＭがＯか判断することにより、次のストリング
に出力すべきレコードとしてレベル付けられたレコード
がレコード領域４１内に存在しないかを判断し、存在し
ない（ＭがＯ）ならば第４の部分に制御を移行し、存在
する（Ｍが０てない）ならば第３の部分に制御を移行す
る。

ソート主処理手段５の第３の部分は、入力レコードが終
了した時点までに生成したストリングの本数が２本以上
であった場合の入力レコード終了からソート終了までの
処理の部分である。

第４図は、ソート主処理手段５の第３の部分の処理ステ
ップを示す図である。

入力レコードか終了するとソート主処理手段５はまずス
テップ４０１で勝者レコードアドレス領域４２にそのア
ドレスか設定されている、作成中ストリングに出力すべ
きレコードとしてレベル付けられたレコードの最上位レ
コードをワークファイル出力処理手段９を用いてソート
ワークファイル３へ出力し、ステップ４０２でＮを１減
算する。

次にステップ４０３で、Ｎが０かを判断することにより
作成中ストリングに出力すべきレコードとしてレベル付
けられたレコードがレコード領域４１に残っているか判
断し、残っている（ＮがＯでない）ならば、ステップ４
０９で、レコード領域４１内に残っているレベルＬのレ
コード（作成中ストリングへ出力するレコード）の最上
位レコードを内部ソート処理手段１０を用いて決定、そ
のアドレスを勝者レコードアドレス領域４２へ設定した
後ステップ４０１へ戻り、作成中ストリングに出力すべ
きレコードとしてレベル付けられたレコードがレコード
領域４１に残っていない（ＮがＯ）ならば、ステップ４
０４へ移行する。

ステップ４０４ではＭがＯか判断することにより次のス
トリングへ出力すべきレコードとしてレベル付けられた
レコードがレコード領域４１内に存在するかを判断し、
存在しない（ＭがＯ）ならば、ステップ４１０のストリ
ングのマージフェーズヘ移行し、存在する（ＭがＯてな
い）ならば、ステップ４０５からステップ４０８までの
ストリング切り替えの処理を実行した後、ステップ４０
９へ移行し、ステップ４０９，４０１，４０２゜４０３
を、Ｎが０になるまでくりかえすことにより、最後のス
トリングを生成する。

ステップ４０５からステップ４０８までは、第２の部分
のステップ３１３から３１６と同様なストリングと切り
替え処理であり、ステ２．プ４０５でＮにＭを設定、ス
テップ４０６で、Ｍに０を再設定、ステップ４０７でＬ
に１を加算した後、ステップ４０８でストリングの切り
替え処理を実行し、ステップ４０９へ移行する。

ステップ４１０は、ソートワークファイル３に生成した
ストリングをマージする処理であり、ワークファイル入
力処理手段８を用いて、ソートワークファイル３からス
トリングをソートメモリ領域４へ入力しながらマージし
ていき、最終的に１本のストリングにまとめられるまで
繰り返しマージし、最終的な１本のストリングを出力処
理手段７を用いてソート出力ファイル２へ出力して％ｓ
き、ソート処理を終了する。

ソート主処理手段５の第４の部分は、入力レコードが終
了した時点までに生成したストリングの本数が１本であ
った場合の、入力レコード終了からソート終了までの処
理の部分である。

第５図は、ソート主処理手段５の第４の部分の処理ステ
ップを示す図である。

入力レコードが終了するとソート主処理手段５はまずス
テップ５０１で、勝者レコーＩＺアドレス領域４２にそ
のアドレスか設定されてしする、作成中ストリングに出
力すべきレコードとしてレベル付けられたレコードの最
上位レコードをワークファイル出力処理手段９を用いて
ソートワークファイル３へ出力してストリングを終了さ
せ、ステ・ツブ５０２へ移行する。

ステップ５０２ではワークファイル入力処理手段８を用
いて、ソートワークファイル３（こ生成した１本のスト
リングのレコードを１件レコード領域４１内に入力（ス
テップ５０１てレコードを出力したのでレコード１件分
空き領域はある）し、ステップ５０３で、ストリングの
レコードはもうない旨ワークファイル入力処理手段８か
ら通知されたかを判断し、ストリングのレコードはもう
ない旨ワークファイル入力処理手段８から通知されたな
らば、ステップ５０５以下の、レコード領域４１内に残
っているレコードの出力処理へ移行し、ストリングのレ
コードがまたあれば、ステップ５０４において、ステッ
プ５０２で入力したレコードを出力処理手段７を用いて
ソート出力ファイル２へ出力し、ステップ５０２へ戻る
。

ステップ５０５以下の処理は、レコード領域４１内に残
っているレコードをソートしなから出力していく処理で
ある。

ステップ５０５ては、Ｎにレコード領域４１内の残りレ
コード数Ｔ−１を設定しくＴはレコード領域４１内に入
るレコード数で第１の部分て設定済み）、ステップ５０
６において、レコード領域４１内に残っているレベルＬ
のレコード（この場合、全レコードがレベルＬのはずで
ある）の最上位レコードを、内部ソート処理手段１０を
用いて決定、そのアドレスを勝者レコードアドレス領域
４２に設定し、ステップ５０７ではステップ５０６でア
ドレスを設定した最上位レコードを出力処理手段７を用
いてソート出力ファイル２へ出力する。

次にステップ５０８でＮを１減算し、ステップ５０９で
Ｎか０か判断することによりレコード領域４１内にまた
出力されずに残っているレコードがあるか判断し、残っ
ているレコードかまたあれば（ＮかＯてない）ならばス
テップ５０６へ戻り次の出力レコードの決定と出力の処
理をＮが０になるまで繰り返し、残りレコードかなけれ
ば（ＮがＯ）ならばソート処理を終了する。

〔発明の効果〕

上述したように本発明は、一般には、主記憶装置内に一
度に読み込むことかできない量のデータを、ワークファ
イルを用いてソートするソート処理において、ワークフ
ァイルに生成したソートの中間結果であるストリングが
１本たけであった場合には、入力レコード終了時にメモ
リ内に残っているレコードをストリングとしてワークフ
ァイルに書き出すことをせす、生成した１本のストリン
グからレコードを一件ずつ読み込み出力ファイルに出力
していった後、メモリ内に残っているレコードをソート
しながら出力ファイルに出力していくようにすることに
より、入力レコードの全てではなく、入力レコードのな
かでメモリに入り切れなかった分のみをワークファイル
に出力するだけでソートを行うことができるため、ソー
ト処理実行時間を短縮し、特に入力レコードがメモリに
入り切らなくなった際の性能の低下を防止することがで
きるという効果かある。

【図面の簡単な説明】

第１図は、本発明の一実施例を示すソート処理のブロッ
ク図、第２図はソート主処理手段の第１の部分（レコー
ド領域か満杯になるまでの処理）の処理フローチャート
、第３図はソート主処理手段の第２の部分（レコード領
域が満杯になってから、入力レコードが終了するまでの
間の処理）の処理フローチャート、第４図はソート主処
理手段の第３の部分（入力レコードか終了した時点まで
に生成したストリングの本数が２本以上であった場合の
入力レコード終了からソート終了までの処理）の処理フ
ローチャート、第５図はソート主処理手段の第４の部分
（入力レコードが終了した時点までに生成したストリン
グの本数が１本であった場合の、入力レコード終了から
ソート終了までの処理）の処理フローチャートである。１・・・ソート入力ファイル、２・・・ソート出力ファ
イル、３−・・ソートワークファイル、４・・・ソート
メモリ領域、５・・・ソート主処理手段、６・・・入力
処理手段、７・・・出力処理手段、８・・・ワークファ
イル入力処理手段、９・・・ワークファイル出力処理手
段、１０・・・内部ソート処理手段。

Claims

【特許請求の範囲】

主記憶装置内に一度に読み込むことができない量のデー
タを、補助記憶装置上のワークファイルを用いてソート
するソート処理方式において、ソートすべきレコードの
格納された補助記憶装置上のソート入力ファイルと、ソ
ート結果を格納する前記補助記憶装置上のソート出力フ
ァイルと、ソートの中間結果であるストリングと呼ぶ順
序付けられたレコード列を格納する前記補助記憶装置上
のソートワークファイルと、主記憶装置上のメモリ領域
であって、ソートキーの比較によりソートされる前記レ
コードを格納するレコード領域と前記レコード領域内の
レコード群のなかの前記ソートキーの順序で最も早く出
力される最上位レコードのアドレスを格納する勝者レコ
ードアドレス領域からなるソートメモリ領域と、ソート
処理を行うソート主処理手段と、前記ソート入力ファイ
ルから、前記ソートメモリ領域にレコードを１件読み込
む入力処理手段と、前記ソートメモリ領域から、前記ソ
ート出力ファイルにレコードを１件書き込む出力処理手
段と、前記ソートワークファイルから、前記ソートメモ
リ領域にレコードを１件読み込むワークファイル入力処
理手段と、前記ソートメモリ領域から、前記ソートワー
クファイルにレコードを１件書き込むワークファイル出
力処理手段と、前記レコード領域内に格納されている定
められたレコード群のなかの前記最上位のレコードを決
定する内部ソート処理手段とから構成され、前記ソート
主処理手段は、前記ソート入力ファイルから前記入力処
理手段を用いて前記レコード領域内にレコードを一件ず
つ入力し、前記内部ソート処理手段を用いてそれまでに
前記レコード領域内に入力されているレコードの中の前
記最上位のレコードを決定し、決定した前記最上位レコ
ードのアドレスを前記勝者レコードアドレス領域に設定
する処理を繰り返す第一の手段と、前記第一の手段にて
前記レコード領域が前記レコードで満杯となる前に前記
入力レコードが終了した場合は、前記勝者レコードアド
レス領域にアドレスが設定されている前記最上位のレコ
ードを前記出力処理手段を用いて前記ソート出力ファイ
ルへ出力し、次に前記レコード領域内に出力されずに残
っている前記レコードがなくなるまで前記レコードの中
の前記最上位レコードを前記内部ソート処理手段を用い
て決定し前記決定された最上位レコードを前記出力処理
手段を用いて前記ソート出力ファイルに出力する処理を
繰り返す第二の手段と、前記第一の手段にて前記レコー
ド領域がレコードで満杯となった時点で前記入力レコー
ドが終了していない場合は、作成中ストリングのレベル
と次のストリングの前記レベルの２つのレベルを設け、
前記レコード領域内にすでに格納されているレコードを
、前記作成中ストリングにレベル付け、前記レコード領
域内に前記作成中ストリングとしてレベル付けられた前
記レコードがなくなるまで、前記勝者レコードアドレス
領域にアドレスが格納されている前記最上位レコードを
前記作成中ストリングのレコードとして前記ワークファ
イル出力処理手段を用いて前記ソートワークファイルへ
出力する出力処理と、次に前記レコード領域内に残って
いるレコードの中の前記最上位レコードを前記内部ソー
ト処理手段を用いて決定し前記アドレスを前記勝者レコ
ードアドレス領域に設定する前記最上位レコードの決定
処理と、前記ソート入力ファイルから前記入力処理手段
を用いて前記レコード領域へレコードを１件入力し、前
記入力したレコードと前記勝者レコードアドレス領域に
前記アドレスが設定されている前記最上位レコードと前
記ソートキーを比較し、前記最上位レコードが上位の場
合は、入力した前記レコードを前記作成中ストリングの
レベルのレコードとし、前記入力したレコードが上位の
場合は、入力した前記レコードを前記次のストリングの
前記レベルのレコードとしてそれぞれレベル付ける前記
レコードのレベル付け処理を順番に繰り返す第一の掃き
出し処理を行い次に前記次のストリングとしてレベル付
けられている前記レコード領域内のレコード群を前記作
成中ストリングのレコードとしてレベル付けし再び前記
第一の掃き出し処理を繰り返して実行する第三の手段と
、前記第三の手段にて前記レコード領域が満杯となった
後に、前記入力レコードが終了した場合で前記終了まで
に作成した前記ストリングの本数が２本以上または、前
記次のストリングとしてレベル付けられた前記レコード
が前記レコード領域に存在している場合に、前記レコー
ド領域内に残っている前記レコードの内まず、前記作成
中ストリングとしてレベル付けられている前記レコード
群を対象として、前記レコード群のレコードが全て前記
ストリングとして出力され前記レコード領域からなくな
るまで前記勝者レコードアドレス領域にアドレスが設定
されている前記最上位レコードの前記ソートワークファ
イルへの前記ワークファイル出力処理手段を用いた出力
処理と、前記内部ソート処理手段を用いた前記レコード
領域内に残っているレコード群の前記最上位レコードの
決定と前記決定されたアドレスの前記勝者レコードアド
レス領域への設定の処理を繰り返す第二の掃き出し処理
を実行し、前記次のストリングとしてレベル付けられた
前記レコード群があれば前記レコード群を再び前記作成
中ストリングとしてレベル付け前記レコード群に対して
前記第二の掃き出し処理を繰り返し次に前記ワークファ
イル入力処理手段を用いて、前記ワークファイルより前
記ソートメモリ領域に前記ストリングを読み込みながら
マージし１本のストリングにまとめて前記出力処理手段
を用いて前記ソート出力ファイルへ出力する第四の手段
と、前記第三の手段にて前記レコード領域が満杯となっ
た後に、前記入力レコードが終了した場合で、前記スト
リングの本数が１本でかつ前記レコード領域内に前記次
のストリングとしてレベル付けられている前記レコード
が存在しないならば、前記勝者レコードアドレス領域に
前記アドレスが設定されているレコードを、前記ワーク
ファイル出力処理手段を用いて前記ソートワークファイ
ルへ出力し次に、前記ソートワークファイルに出力され
た前記ストリングの全レコードについて前記ワークファ
イル入力処理手段を用いて前記レコードを１件ずつ前記
レコード領域内に入力し入力した前記レコードを前記出
力処理手段を用いて前記ソート出力ファイルに出力し、
最後に前記レコード領域に残存している前記レコードが
１件もなくなるまで、前記内部ソート処理手段により残
存している前記レコード群のなかの前記最上位レコード
を決定し前記最上位アドレスを前記勝者レコードアドレ
ス領域に設定する処理と、前記出力処理手段により前記
勝者レコードアドレス領域にアドレスが設定されている
前記最上位レコードを前記ソート出力ファイルに出力す
る処理を繰り返す第五の手段とから構成されることを特
徴とするソート処理方式。