JPH06103459B2 - ソート処理方法および装置 - Google Patents

Description

【発明の詳細な説明】 〔発明の技術分野〕 本発明は、ディスクパック装置などの直接アクセスの外
部記憶に格納されているデータセットの中のレコードを
ソートする方法および装置に関するものである。

〔従来技術と問題点〕

外部記憶装置上のデータを与えられた順序関係規約（ソ
ート・ルール）に従って、ソートすることを一般に外部
ソート（external sort）と呼ぶ。外部ソートは、バン
キング・アプリケーションを筆頭に、諸事務計算、デー
タベース・アプリケーション、その他の分野で日常よく
行われる処理である。外部ソートの処理のために、汎用
のソート／マージプログラムが提供されているが、どの
ソート／マージアルゴリズムを採用するにせよ、外部記
憶に記録されたデータは外部記憶制御装置、チャネル装
置を経由して主記憶上に転送され、また送りもどされる
というプロセスが必要になっている。ソートのためのチ
ャネル使用の率は、実行環境により違うが、事務計算や
データベースがらみの処理の分野においては、２割以上
を占めているのではなかろうかといわれている。外部ソ
ートのためのチャネル占有率が減少すれば、相対的に他
の目的のためのチャネル使用効率が高まることになる。
また、外部ソートの性能を左右する主なファクターが、
データの転送回数（アクセス回数）であり、転送回数を
最小にするアルゴリズムが良い外部ソート・アルゴリズ
ムであるとも考えられている。

しかし、中央演算装置と主記憶装置を用いた外部ソート
方法である限り、チャネル経由のデータ転送回数を減少
させるには限界がある。むしろ、チャネルと外部記憶装
置の中間に外部ソート専用の装置を置いて、チャネルを
使用せずに、外部ソートが達成できれば、（１）専用装
置によるソート処理の高速化、（２）チャネルの外部ソ
ートのための占有率減少の一挙両得になるのではないか
と考えられる。また、仮にもし、そのような専用の装置
ができたとしても、装置が複雑で高価なものになるよう
であれば、ソート処理の高速化と、チャネル占有率の減
少分の努力が実らないことになる。したがって、もしそ
のような装置ができたとしても単純なもので、安価なも
のでなければならない。ましてや、その新しい装置のた
めにさらに巨大なソフトウェア開発が必要になったり、
多大のソフトウェア変更が生じるのではこまる。

現在の汎用の外部ソート・プログラムは、入力ファイ
ル、作業用ファイル、出力ファイルの３本のファイルを
開設した後に、入力ファイルから作業用ファイルへ、作
業用ファイルから出力ファイルへの読み込み、書き出し
処理を行いながらソート処理を実現している。この処理
内容をそのまゝハードウェア化するというも考えられる
が、しかし、複数のファイルを１つの装置が同時に制御
するという実行環境は、ハードウェア化する場合、ロジ
ックが複雑になるし、スペース不足の場合にどうするか
など、余計な世話もしなくてはならなくなり、単純な装
置として実現するという方針からはずれる。さらに、既
存の汎用ソート・プログラムの設計思想は、データ・ア
クセス回数最小という要請に応えようとするところに力
点があり、単純化しようという思想とは多少ずれてい
る。特に、ファイルのスペース管理という、本来ソフト
ウェアによってサポートされているシステムと情報交換
が必要になることは、ハードウェア化する際のネックに
なる可能性が大きい。したがって、ソートされるべきデ
ータの物理的空間が最初から最後まで、明確に定義され
ているようなソート方法を前提にしたほうがハードウェ
ア化が容易になろう。

今、仮に、外部記憶装置とチャネルの間にしかるべき、
外部ソート装置を設置したとしよう。その場合の運用状
況としては、『せっかく、外部ソート装置を設置したの
だから』という気持が作用して、その外部ソート装置に
つながるデータセット群は、常にソート済みとして用い
るようなマスターファイル群や、その他のサブファイル
群であろう。すなわち、かような外部ソート装置に連結
されたファイルの多くは、常にソート済みの状況にある
ような運用になろう。とすれば、その外部ソート装置の
特性として、ソート済みの状態にあるファイルへのデー
タの追加、あるいは、ほぼソート済みに近い部分的に未
ソートな状態のもののソートなどが容易に処理できる必
要があろう。

〔発明の目的〕

本発明は、上記の考察に基づくものであって、ソートす
べきデータセットの中でソート処理を行い得ること、略
ぼソート済みのデータセットのソートの場合に効果が大
きいこと、使用するメモリ領域の少ないこと及びハード
ウェア化が容易なこと等の特徴を有するソート処理方法
および装置を提供することを目的としている。

〔発明の構成〕

そしてそのため、本発明の第１番目の発明のソート処理
方法は、 それぞれがＮ個のレコードを持つ第１ブロック，第２ブ
ロック，…，第ｎブロックより構成されたソート済みブ
ロック列に,N個のレコードを持つソート済みの第ｎ＋１
ブロックを追加し、第１ブロックから第ｎ＋１ブロック
までをソートするソート処理方法であって、 第ｎブロックを第１バッファに格納し、第ｎ＋１ブ
ロックを第２バッファに格納し、 第１バッファの内容と第２バッファの内容をマージ
し、マージ結果をソート・ルールにしたがって第１バッ
ファおよび第２バッファに格納し、 マージ後の第１バッファに格納されているレコード
列において、マージ前の第１バッファに格納されていた
レコード列の先頭レコードより前方に位置するレコード
列が存在するか否かを調べ、 存在しない場合には、ソートを終了し、 存在する場合には、第１バッファの内容を第２バッ
ファに移動し、ソート済みブロック列における１つ前の
ブロックを第１バッファに格納し、再びの処理を行う ことを特徴とするものである。

本発明の第２番目の発明のソート処理装置は、 それぞれがＮ個のレコードよりなるＭ個のブロックを持
つデータセットを格納する外部記憶ユニットと、 バッファ・リードの指令を受取ったとき上記外部記憶ユ
ニットから指定されたブロックを読出して指定されたバ
ッファに格納すると共にライトの指令を受取ったとき指
定されたバッファのデータを指定された外部記憶ユニッ
トのブロックに書込むブロック入出力コントローラと、 内部ソート指令を受取ったとき指定されたバッファの内
容を内部ソートする内部ソータと、 マージを行うと共にスパン長を求めることを支持するス
パン・スライダ指令を受取ったとき指定された第ｐバッ
ファおよび第ｑバッファに格納されているソート済デー
タをスパン長に基づいてマージする処理、マージ前とマ
ージ後におけるデータの移動の有無を出力する処理、マ
ージ処理の結果得られるレコード列における，マージ前
の第ｐバッファに格納されていたレコード列の先頭レコ
ードより前方に位置するレコード列の長さを示すスパン
長を出力する処理を行う２ブロック・スパン・スライダ
と、 制御手段と を具備し、 上記制御手段は、上記データセットの全ブロックのそれ
ぞれを内部ソートする処理を行った後、 ブロック番号ｉを初期値に設定し、 ｉ＋１をｉに設定し、 ブロック番号ｉがＭより大であるか否かを調べ、No
の場合には次にの処理に移行し、Yesの場合は終了と
し、 スパン長をＮに、ブロック番号ｉをｋに設定すると
共に、第ｋブロックのデータを第ｑバッファに格納すべ
きことを上記ブロック入出力コントローラに指令し、 ｋ−１をｋに設定し、 ｋが１より小さいか否かを調べ、Yesの場合には
の処理に戻り、Noの場合には次のの処理を行い、 第ｋブロックのデータを第ｑバッファに読込むべき
ことを上記ブロック入出力コントローラに指令すると共
に、第ｐバッファおよび第ｑバッファの内容をマージす
べきこと、マージ処理の結果得られるレコード列におけ
るスパンの長さをスパン長格納域にセットすべきこと、
並びにマージ前とマージ後でデータの移動があったか否
かを示す移動有無情報を出力すべきことを上記２ブロッ
ク・スパン・スライダに指令し、 移動有無情報が移動なしを示しているか否かを調
べ、移動なしの場合にはの処理に移行し、移動ありの
場合にはの処理に移行し、 第ｐバッファのデータを第ｋブロックに書込むべき
こと及び第ｑバッファのデータを第ｋ＋１ブロックに書
込むべきことを上記ブロック入出力コントローラに指令
し、 スパン長が零であるか否かを調べ、Yesの場合には
の処理に移行し、Noの場合にはの処理に移行し、 第ｐバッファと第ｑバッファのデータを交換した
後、上記の処理を行うよう構成されている ことを特徴とするものである。

〔発明の実施例〕

以下、本発明を図面を参照しつつ説明する。ファイル
（データセットと同義）Ｆは、下記のようにレコードｒ
〔１〕、ｒ〔２〕、…ｒ〔Ｐ〕、…ｒ〔Ｋ〕の並びとし
て考えることが出来る。

また、ファイルＦは、下記のようにブロックの並びとし
て考えることも出来る。

各ブロックは固定長のものであり、ブロックBiは下記の
ようにＮ個のレコードから構成されている。

ここで、▲Ｒⁱ _j▼は第ｉ番目のブロックの第ｊ番目のレ
コードを意味している。また▲Ｒⁱ _j▼は ▲Ｒⁱ _j▼＝ｒ〔Ｎ・（ｉ−１）＋ｊ〕 である。なお、ブロックとは、入出力の単位である。

次に本明細書で使用する記号の定義について説明する。
ｒ′およびｒをレコードとすると、 ｒ′←ｒ は、レコードｒ′がレコードｒの前に位置すべきことを
意味している。また、 ｒ〔ｐ〕ｒ〔ｑ〕 は、レコードｒ〔ｐ〕からｒ〔ｑ〕までがソートされた
ことを意味している。ただし、ｐ＜ｑである。

同様に、 ▲Ｒⁱ _j▼▲Ｒ^ｉ′ _ｊ′▼ ただし、Ｎ・（ｉ−１）＋ｊ＜Ｎ・（ｉ′−１）＋ｊ′
は、レコード▲Ｒⁱ _j▼からレコード▲Ｒ^ｉ′ _ｊ′▼まで
がソートされたことを意味している。

次に、本発明のソート処理方式のアルゴリズムについて
説明する。ソート処理は、 given:file Ｆ target:▲Ｒ¹ ₁▼▲Ｒ^M _N▼ と書くことが出来る。これを問題０という。本発明にお
ける解法レベル１は、 for ｉ＝1,M ▲Ｒ¹ ₁▼▲Ｒⁱ _N▼ を行うことである。上式は、ｉを１から１刻みでＭまで
変化させながら、 ▲Ｒ¹ ₁▼▲Ｒⁱ _N▼ を実行せよ、ということを意味している。第１図は上記
の解法レベル１の処理を説明するものである。即ち、先
ずブロックB₁をソートされた状態にする。次に、ブロッ
クB₁からB₂までをソートされた状態にする。同様な処理
を繰返してブロックB₁からBi_-1までをソートされた状態
にする。ソートされた状態にあるブロックB₁からBi_-1ま
での並びにブロックBiを加え、しかる後にブロックB₁か
らBiまでをソートされた状態にする。同様な処理を繰返
し、ブロックB₁からブロックB_Mまでをソートされた状態
とする。

上記の処理を行うためには、ソートされた状態にあるブ
ロックB₁からBi_-1の並びにブロックBiを加える、しかる
後にブロックB₁からBiまでをソートされた状態にしなく
てはならない。これを問題１とすると、問題１は given:▲Ｒ¹ ₁▼▲Ｒ^i-1 _N▼,Bi target:▲Ｒ¹ ₁▼▲Ｒⁱ _N▼ と書くことが出来る。この問題１の解法を解法レベル２
とすると、解法レベル２は Internal Sort Bi Merge Bi and＜B₁,B₂,………,Bi_-1＞ と書くことが出来る。ここで問題となることは、上記の
マージを如何にして行うかと言うことである。これを問
題２とすると、問題２は、 given:▲Ｒ¹ ₁▼▲Ｒ^i-1 _N▼，▲Ｒⁱ ₁▼▲Ｒⁱ _N▼ target:▲Ｒ¹ ₁▼▲Ｒⁱ _N▼ と書くことが出来る。この問題２に対する解法を解法レ
ベル３とすると、解法レベル３は、下記の式で与えられ
る。

fot ｕ＝i,2,−１ ▲Ｒ^u-1 ₁▼▲Ｒⁱ _N▼ 上式は、ｕをｉから−１刻みで２まで変化させながら ▲Ｒ¹ ₁▼▲Ｒⁱ _N▼ を実現せよ、ということを意味している。上記の解法レ
ベル３を実行するためには、下記の問題を解く必要があ
る。

given:▲Ｒ^u-1 ₁▼▲Ｒ^u-1 _N▼，▲Ｒ^u ₁▼▲Ｒⁱ _N▼ target:▲Ｒ^u-1 ₁▼▲Ｒⁱ _N▼ これを問題３とすると、問題３はｕ−１で示されるブロ
ックBu_-1がソートされ、且つブロックBuからBiまでソー
トされた状態の下で、ブロックBu_-1からBiまでソートせ
よということを意味している。

最初の状態ではｕ＝ｉであるので、問題３は、 given:▲Ｒ^i-1 ₁▼▲Ｒ^i-1 _N▼，▲Ｒⁱ ₁▼▲Ｒⁱ _N▼ target:▲Ｒ^i-1 ₁▼▲Ｒⁱ _N▼ となる。第２図は第１ステップの問題３の解法を説明す
るものである。ブロックBi_-1は既にソートされた状態で
あり、その先頭のレコード▲Ｒ^i-1 ₁▼の内容がａ、そ
の最後のレコード▲Ｒ^i-1 _N▼の内容がｂであるとす
る。同様に、ブロックBiは既にソートされた状態にあ
り、その先頭レコード▲Ｒⁱ ₁▼の内容はｃ、最後のレ
コード▲Ｒⁱ _N▼の内容はであるとする。ブロックBi_-1
とBiをマージすると、図示のようにCase1ないし４の状
態が生ずる。Case1は、マージ結果とマージ前の状態が
変化しなかった場合を示している。Case2は、マージ結
果においてマージ前のレコード▲Ｒⁱ ₁▼が前方に移され
た場合を示している。Case3は、マージ結果の状態がマ
ージ前のブロックBi_-1とBiとを交換した状態になる場合
を示している。Case4は、マージ結果においてマージ前
のレコード▲Ｒⁱ ₁▼が先頭に位置し、マージ前のレコー
ド▲Ｒ^i-1 ₁▼がそれより後方に位置する場合を示してい
る。Case3は、Case4の特別の場合と考えることも出来
る。マージ結果がCase1となる予想される場合には、何
も行わない。即ち、既にブロックB₁からBiまでソートが
行われた状態にある。マージ結果がCase2になると予想
される場合には、ブロックBi_-1とBiとの２ブロック・マ
ージを行い、その後の処理は行わない。即ち、上記の２
ブロック・マージを行うと、ブロックB₁からBiまでがソ
ートされた状態となる。マージ結果がCase3になると予
想される場合は、マージを行いマージ後のBiが完成され
たものとし、次に given:▲Ｒ¹ ₁▼▲Ｒ^i-2 _N▼，▲Ｒ^i-1 ₁▼▲Ｒ^i-1 _N▼ target:▲Ｒ¹ ₁▼▲Ｒ^i-1 _N▼ なる問題を解く。マージ結果がCase4になると予想され
る場合には、マージを行い、マージ後のBiおよび▲Ｒ
^i-1 _k+1▼▲Ｒⁱ _N▼が完成されたものとし、次に given:▲Ｒ¹ ₁▼▲Ｒ^i-2 _N▼，▲Ｒ^i-1 ₁▼▲Ｒ^i-1 _k▼ target:▲Ｒ¹ ₁▼▲Ｒ^i-1 _k▼ なる問題を解く。なお、ｋ＋１はマージ後において内容
ａをもつレコード（マージ前のレコード▲Ｒ^i-1 ₁▼）
のブロックBi_-1上の位置を示している。

次に、スパン・スライドなる概念について説明する。第
３図において、レコード▲Ｒ^u ₁▼ないし▲Ｒ^u _k▼をスパ
ンという。即ち、スパンとは、前方に位置するレコード
列（▲Ｒ¹ ₁▼，…，▲Ｒ^u-1 _N▼）よりも前方に位置すべ
きレコードを含んでいる可能性のあるレコードのまとま
り（▲Ｒ^u ₁▼，…，▲Ｒ^u _k▼）である。これは、第２図
のCase4におけるＣからａ（たゞしａは含まず）
までに対応する。第３図において、▲Ｒ¹ ₁▼▲Ｒ^u-2 _N
▼，▲Ｒ^u-1 ₁▼▲Ｒ^u-1 _N▼，▲Ｒ^u ₁▼▲Ｒ^u _k▼，▲
Ｒ^u _k+1▼▲Ｒⁱ _N▼であり、且つ▲Ｒ^u-1 _N▼←▲Ｒ^u _k+1
▼である。ブロックBu_-1とブロックBuとをマージする
と、第２図のCase1ないし４の場合が生ずる。Case1、２
の場合にはスパンは消滅し、Case3、４の場合は新たな
スパンが生成される。２個のブロックをマージして、ス
パンを求めることを、スパン・スライドという。Case
3、４の場合には、ｕの値を−１した後、ブロックBu_-1
とブロックBuとのスパン・スライドを行う。ブロックBu
_-1とブロックBuとをマージする場合、ブロックBu_-1とブ
ロックBuのスパン部分（RuないしRuの部分）とをマージ
する。

第４図は本発明の１実施例のブロック図である。第４図
において、１はソート処理装置、２は外部記憶ユニッ
ト、３はスパン・ソート・スーパバイザ、４は２ブロッ
ク・スパン・スライダ、５はブロック内部ソータ、６は
ブロック入出力コントローラ、７はレコード比較器、８
−１ないし８−３はブロック・バッファ、BPはバッファ
・プールをそれぞれ示している。なお、白の太線はブロ
ック・アクセス、黒の太線はレコード・アクセス、実線
は制御信号の流れをそれぞれ示している。ブロック入出
力コントローラ６は、スパン・ソート・スーパバイザ３
から何れのブロックを何れのブロック・バッファに読込
むべきか、或は何れのブロック・バッファの内容を何れ
のブロックに書出すべきかを指示されて、その指示どお
りブロック単位の入出力を行う。ブロック内部ソータ５
は、スパン・ソート・スーパバイザ３から何れのブロッ
ク・バッファの内容を内部ソートすべきかを指示され
て、その指示どおりブロック・バッファ内部のレコード
に関するソーティングを行う。ソーティングに必要なレ
コードとレコードの比較には、レコード比較器７を用い
る。２ブロック・スパン・スライダ４は、スパン・ソー
ト・スーパバイザ３から何れの２個のブロック・バッフ
ァの内容をスパン・スライド（マージ）するかを指示さ
れて、その指示どおりスパン・スライドを行う。レコー
ド比較器７は、２つのレコードが入力されると、それら
の順序を判定し、目的とする順なら真、そうでなければ
偽の値を出力する。スパン・ソート・スーパバイザ３
は、２ブロック・スパン・スライダ４、ブロック内部ソ
ータ５、ブロック入出力コントローラ６に指令を与え
る。このため、スパン・ソート・スーパバイザ３に、外
部記憶ユニット２上のソート対象データセットのブロッ
ク番地の先頭と最後を予め設定しておき、また、スパン
・スライドの制御の初期値を与えておく必要がある。ソ
ート処理装置１をプロセッサで実現する場合には、スパ
ン・ソート・スーパバイザ３、２ブロック・スパン・ス
ライダ４、内部ブロック・ソータ５、ブロック入出力コ
ントローラ６及びレコード比較器７は、ソフトウェアで
実現される。勿論、これらを全て純ハードウェア構成と
することも出来る。

本発明のソート処理は、第１フェーズおよび第２フェー
ズに分けることが出来る。第１フェーズとは、データセ
ットの全ブロックのそれぞれをブロック内部についてソ
ート済みの状態にするためのフェーズである。第５図は
第１フェーズの概要を説明するものである。ブロック入
出力コントローラ６は、スパン・ソート・スーパバイザ
３のリード指令を受けて、外部記憶ユニット２の中のブ
ロックをリードし、これをブロック・バッファ８−１に
書込む。ブロック・バッファ８−１のブロックの書込み
が終了した後、スパン・ソート・スーパバイザ３は、ブ
ロック内部ソータ５に対してブロック・バッファ８−１
の内容を内部ソートすべきことを指令する。この内部ソ
ート指令を受取ると、ブロック内部ソータ５は、レコー
ド比較器７を使用しながらブロック・バッファ８−１の
ブロック・データについての内部ソートを行い、そのソ
ート結果をスパン・ソート・スーパバイザ３に通知す
る。ブロック内部ソータ５によるブロック・データの内
部ソートが完了すると、スパン・ソート・スーパバイザ
３は、必要に応じてブロック・バッファ８−１のブロッ
ク・データを外部記憶ユニット６の元のブロック位置に
ライトすべきことをブロック入出力コントローラ６に指
令する。このライト指令を受取ると、入出力コントロー
ラ６は、ブロック・バッファ８−１の中のブロック・デ
ータを外部記憶ユニット２内の元のブロック位置にライ
トする。以下、同様な処理が繰返される。

第６図はソート処理の第２フェーズの概要を説明するも
のである。スパン・ソート・スーパバイザ３は、最初に
外部記憶ユニット２内の連続せる２個のブロックをブロ
ック・バッファ８−１、８−２に読込むべきことをブロ
ック入出力コントローラ６に指令する。ブロック入出力
コントローラ６は、このリード指令を受取ると、外部記
憶ユニット２の中の連続せる２個のブロックをブロック
・バッファ８−１、８−２に読込む。このリード指令の
実行が完了した後、スパン・ソート・スーパバイザ３
は、ブロック・バッファ８−１、８−２のブロック・デ
ータについてスパン・スライドすべきことを２ブロック
・スパン・スライダ４に対して指令する。２ブロック・
スパン・スライダ４は、このスパン・スライド指令を受
取ると、ブロック・バッファ８−１、８−２内の２個の
ブロック・データをスパン・スライドし、スパン・スラ
イドの結果をスパン・ソート・スーパバイザ３に対して
通知する。スパン・スライド指令の実行完了後、スパン
・ソート・スーパバイザ３は、必要に応じてブロック・
バッファ８−１、８−２のブロック・データを外部記憶
ユニット２の中の元のブロック位置にライトすると同時
にこれらのブロック・データを外部記憶ユニット２の中
の作業記憶域にライトすべきことをブロック入出力コン
トローラ６に指令する。ブロック入出力コントローラ６
は、このライト指令を受取ると、ブロック・バッファ８
−１、８−２のブロック・データを外部記憶ユニット２
にライトする。以下、同様な処理が繰返される。

スパン・ソート・スーパバイザ３からブロック入出力コ
ントローラ６への指令には、下記のようなものがある。

BIOC（Read,i,p） BIOC（Write,i,p） ブロック入出力コントローラ６は、前者の指令を受取る
と、第ｉブロックのデータを第ｐバッファに読込み、後
者の指令を受取ると、第ｐバッファのデータを第ｉブロ
ックに書込む。なお、バッファとはブロック・バッファ
のことである。スパン・ソート・スーパバイザ３からブ
ロック内部ソータ５への指令は、下記のような形式をも
つ。

BIS（p,c） ブロック内部ソータ５は、この指令を受取ると、第ｐバ
ッファのデータを内部ソートし、このときソート前とソ
ート後とでデータの並びが不変であればｃ＝０、変化し
ていればｃ＝１を出力する。スパン・ソート・スーパバ
イザ３から２ブロック・スパン・スライダ４への指令
は、下記のような構成をもつ。

2BSS（p,q,sp,c） ２ブロック・スパン・スライダ３は、この指令を受取る
と、第ｐバッファと第ｑバッファをマージし、終了後の
スパン長を指定領域spに出力し、処理前と処理後とでバ
ッファ内データの移動がなかったならばｃ＝０、移動が
あったならばｃ＝１を出力する。なお、開始直前におい
て第ｑバッファがスパン長spのスパン・ブロックである
とし、終了後は第ｐバッファがスパン・ブロックになる
ものとする。

第７図はスパン・ソート・スーパバイザ３の動作ロジッ
クを示すものである。スパン・ソート・スーパバイザ３
は、第１フェーズのための動作ロジックと、第２フェー
ズのための動作ロジックとを有している。先ず、第１フ
ェーズのための動作ロジックについて説明する。

ブロック番号ｉを０にする。

ｉ＋１をｉとする。

ｉがＭより大きいかを調べる。Yesの場合は第２フ
ェーズを開始し、Noの場合にはを行う。

BIOC（Read i,1）を発行する。

BIC（1,c）を発行する。

ｃが０であるか、否かを調べる。Yesの場合には
を行い、Noの場合にはを行う。

BIOC（Write,i,1）を行い、に戻る。第２フェー
ズのための動作ロジックは下記のような動作を行う。

ブロック番号ｉを１に、バッファ番号ｐを１に、バ
ッファ番号ｑを２にする。

ｉ＋１をｉにする。

ｉがＭより大きいか否かを調べる。Yesの場合には
第２フェーズ終了となり、Noの場合にはを行う。

Ｎをスパン長に、ｉをブロック番号ｋにし、そして
BIOC（Read,k,q）を発行する。

ｋ−１をｋにする。

ｋが１より小さいか、否かを調べる。Yesの場合に
はを行い、Noの場合にはを行う。

BIOC（Read,k,p）および2BSS（p,q,sp,c）を発行す
る。

ｃが０か、否かを調べる。Yesの場合にはを行
い、Noの場合にはを行う。

BIOC（Write M＋1,p）,BIOC（Write,M＋2,q）、BIO
C（Write,k,p）,BIOC（Write,k＋1,q）を発行する。
尚、前記２命令は、データ保全性確保のためのデータの
コピーである。

スパン長が０か、否かを調べる。Yesの場合はを
行い、Noの場合はを行う。

第ｐバッファの内容を第ｘバッファに移し、第ｑバ
ッファの内容を第ｑバッファに移し、第ｘバッファの内
容を第ｑバッファに移す。次にを行う。

第８図はスパン・ソートの状態遷移の例を示すものであ
る。なお、本発明によるソートをスパン・ソートとい
う。この例は、ブロック数が６の場合である。ステッ
プないしステップは第１フェーズである。ないし
ステップによって、第１ブロックないし第６ブロックが
それぞれ内部ソートされる。ステップにおいては、第
１、第２ブロックがスパン・スライドされ、第１ブロッ
クから第２ブロックまでがソートされた状態とされる。
ステップでは第２、第３ブロックがスパン・スライド
される。ステップの処理でスパンが存続した場合に
は、ステップで第１、第２ブロックのスパン・スライ
ドを行う。ステップが終了すると、第１ブロックから
第３ブロックまでがソートされた状態となる。同様な処
理がこの後も繰返される。

〔発明の効果〕

以上の説明から明らかなように、本発明によれば、 （イ） 同一のデータセット内で処理できるので、他の
ファイルを必要としないこと、 （ロ） 必要とするメモリ領域が少なくて済むこと、 （ハ） 線形ソートであるので、ファイルの管理が容易
なこと、 （ニ） 略ぼソート済みのデータセットのソートに効果
が大きいこと、 （ホ） 実行環境が対象データセットのみに限定できる
ので、ハードフェア化が容易なこと 等の顕著な効果を奏することが出来る。

【図面の簡単な説明】

第１図はブロックB₁からブロックB_Mまでをソートするた
めの基本的な手順を説明する図、第２図はソートされた
状態にあるブロックBi_-1ソートされた状態にあるブロッ
クBiをマージした後の状態を説明する図、第３図はスパ
ン・スライドを説明するための図、第４図は本発明の１
実施例のブロック図、第５図は実施例におけるソート処
理の第１フェーズの概要を示す図、第６図は実施例にお
けるソート処理の第２フェーズの概要を示す図、第７図
はスパン・ソート・スーパバイザの動作ロジックを示す
図、第８図はスパン・ソートの状態遷移例である。 １……ソート処理装置、２……外部記憶ユニット、３…
…スパン・ソート・スーパバイザ、４……２ブロック・
スパン・スライダ、５……ブロック内部ソータ、６……
ブロック入出力コントローラ、７……レコード比較器、
８−１ないし８−３……ブロック・バッファ、BP……バ
ッファ・プール。

Claims (2)

【特許請求の範囲】
1. 【請求項１】それぞれがＮ個のレコードを持つ第１ブロ
   ック，第２ブロック，…，第ｎブロックより構成された
   ソート済みブロック列に,N個のレコードを持つソート済
   みの第ｎ＋１ブロックを追加し、第１ブロックから第ｎ
   ＋１ブロックまでをソートするソート処理方法であっ
   て、 第ｎブロックを第１バッファに格納し、第ｎ＋１ブ
   ロックを第２バッファに格納し、 第１バッファの内容と第２バッファの内容をマージ
   し、マージ結果をソート・ルールにしたがって第１バッ
   ファおよび第２バッファに格納し、 マージ後の第１バッファに格納されているレコード
   列において、マージ前の第１バッファに格納されていた
   レコード列の先頭レコードより前方に位置するレコード
   列が存在するか否かを調べ、 存在しない場合には、ソートを終了し、 存在する場合には、第１バッファの内容を第２バッ
   ファに移動し、ソート済みブロック列における１つ前の
   ブロックを第１バッファに格納し、再びの処理を行う ことを特徴とするソート処理方法。
2. 【請求項２】それぞれがＮ個のレコードよりなるＭ個の
   ブロックを持つデータセットを格納する外部記憶ユニッ
   トと、 バッファ・リードの指令を受取ったとき上記外部記憶ユ
   ニットから指定されたブロックを読出して指定されたバ
   ッファに格納すると共にライトの指令を受取ったとき指
   定されたバッファのデータを指定された外部記憶ユニッ
   トのブロックに書込むブロック入出力コントローラと、 内部ソート指令を受取ったとき指定されたバッファの内
   容を内部ソートする内部ソータと、 マージを行うと共にスパン長を求めることを支持するス
   パン・スライダ指令を受取ったとき指定された第ｐバッ
   ファおよび第ｑバッファに格納されているソート済デー
   タをスパン長に基づいてマージする処理、マージ前とマ
   ージ後におけるデータの移動の有無を出力する処理、マ
   ージ処理の結果得られるレコード列における，マージ前
   の第ｐバッファに格納されていたレコード列の先頭レコ
   ードより前方に位置するレコード列の長さを示すスパン
   長を出力する処理を行う２ブロック・スパン・スライダ
   と、 制御手段と を具備し、 上記制御手段は、上記データセットの全ブロックのそれ
   ぞれを内部ソートする処理を行った後、 ブロック番号ｉを初期値に設定し、 ｉ＋１をｉに設定し、 ブロック番号ｉがＭより大であるか否かを調べ、No
   の場合には次にの処理に移行し、Yesの場合は終了と
   し、 スパン長をＮに、ブロック番号ｉをｋに設定すると
   共に、第ｋブロックのデータを第ｑバッファに格納すべ
   きことを上記ブロック入出力コントローラに指令し、 ｋ−１をｋに設定し、 ｋが１より小さいか否かを調べ、Yesの場合には
   の処理に戻り、Noの場合には次のの処理を行い、 第ｋブロックのデータを第ｐバッファに読込むべき
   ことを上記ブロック入出力コントローラに指令すると共
   に、第ｐバッファおよび第ｑバッファの内容をマージす
   べきこと、マージ処理の結果得られるレコード列におけ
   るスパンの長さをスパン長格納域にセットすべきこと、
   並びにマージ前とマージ後でデータの移動があったか否
   かを示す移動有無情報を出力すべきことを上記２ブロッ
   ク・スパン・スライダに指令し、 移動有無情報が移動なしを示しているか否かを調
   べ、移動なしの場合にはの処理に移行し、移動ありの
   場合にはの処理に移行し、 第ｐバッファのデータを第ｋブロックに書込むべき
   こと及び第ｑバッファのデータを第ｋ＋１ブロックに書
   込むべきことを上記ブロック入出力コントローラに指令
   し、 スパン長が零であるか否かを調べ、Yesの場合には
   の処理に移行し、Noの場合にはの処理に移行し、 第ｐバッファと第ｑバッファのデータを交換した
   後、上記の処理を行うよう構成されている ことを特徴とするソート処理装置。