JPS62179026A - ソ−トブロツク先読み方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 （産業上の利用分野） 本発明は、電子計算機において補助記憶装置を用いて行
われるソート処理に関し、特にソートプログラムの補助
記憶装置に対する入力に関する。

（従来の技術） 従来、補助記憶装置上用いてソート処理を行うソートプ
ログラムにおいては、補助記憶ｔｔ置から複数のス）　
ＩＪタング読込んで併合処理上行つ場合、ストリングの
ブロックを読込むための記憶部をブロック単位に配置さ
れた入力バッファに分割した後、分割によって設定した
バッファの数と、補助記憶装置の内部のストリング数と
ｔもとに１各バツフアｔそれぞれ単位ストリングに割当
てるｌバッファ方式、あるいは２個のバッファｔそれぞ
れ単位ストリングに割当てる２バッファ方式かのいずれ
かの方式を選択してい次。

（発明が解決しようとする問題点ン 前述した２つの方式では１バッファ方式の場合、１回の
併合処理で併合することのできるストリング数は多くな
るが、入力バッファへのブロック入力要求を発行してか
ら入力が完了するまでの間、処理を中断しなければなら
ず、ノート実行処理効率を低下させる要因となっている
。

２バッファ方式の場合、入力バッファへのブロック入力
完了待ちによる処理中断は存在しないが、併合するスト
リング１個につき２個の入力バッファ全使用するため、
ソートに使用できるメモリ容量の制限から１回の併合処
理で併合することのできるストリング数が少なくなり、
併合処理の回数が多くなるという欠点がある。

本発明の目的は、補助記憶襞ｔを用いてソート処理を行
うソートプログラムにおいて、補助記１．ｉ！装置から
複数のストリングを読込み併合処理に際して併合するス
トリングの個数と同数の入力バッファと、１個の予備バ
ッファとを使用してストリングのブロック先読みを行う
ことにより、上記欠点を除去し、ソート処理効率を向上
できるように構成したソートブロック先読み方式全提供
することにある。

（問題点を解決するための手段） 本発明によるソートブロック先読み方式は補助記憶装置
と、記憶部と、入力処理手段と、併合処理手段と、先読
み制御処理手段と全具備して構成し念ものである。

補助記憶装置はレコード會ソートするソート処理で、中
間結果として得られた複数個のストリングを格納するた
めのものである。

記憶部は、ストリングの併合処理を行う友め複数個のブ
ロックより成るストリングのレコード會ブロック単位に
記憶しておくためのものである。

入力処理手段は、補助記憶装置から記憶部へストリング
をブロック単位で読込む几めのものである。

併合処理手段は、記憶部の内部のブロックからレコード
を取出して併合処理手段うためのものである。

先読み制御処理手段は、ストリングのブロック先読みを
制御する念めのものである。

（実施　例） 次に、本発明について図面を参照して詳細に説明する。

第１図は、本発明によるソートブロック先読み方式を実
現する友めの一実施例を示すブロック図である。第４図
において、１はソート処理の中間結果であるストリング
全格納しておくための補助記憶装置、２は補助記憶装置
ｌｌからストリングをブロック単位で読込む念めの入力
処理手段である。３はストリングを併合する友めにスト
リングのレコード會ブロック単位で格納する念めの記憶
部であり、本実施例では４個のブロックを格納できる大
きさ會もっている。

４．５．６はそれぞれ、記憶部３を分割して設定し友人
カバツファであり、本実施例では３個の入カバツファケ
設定している。７ｉ１１．予備バッファ、８はストリン
グ１個合するための併合処理手段、９はストリングのブ
ロック先読みを行うための先読み制御処理手段である。

１０　、１１．１２゜１３はそれぞれストリングである
。

主ソートプログラムの最初の処理の結果、補助記憶装置
１に順序付けられ几レコードを含む複数のブロックから
成る複数個のストリング１０゜１１　、１２．１３が格
納される。主ソートプログラムは全レコードをストリン
グとして補助記憶装置ｌに格納した後、併合処理手段８
に制ａ１に渡してストリングの併合処理を行わせる。第
１図は、主ソートプログラムの最初の処理後の、併合処
理時における構成を説明したブロック図である。

まず、併合処理手段８は併合処理に先立って先読み制御
処理手段９に制御を渡し、ストリングのブロックと同一
の大きさに記憶部３を分割し、複数の入力バッファと、
１個の予備バッファとを設定せしめる。

次に、併合処理手段８は各併合処理の最初に、再び先読
み制御処理手段９に制？Ｂ１’に渡す。先読み制御処理
手段９は、入力処理手段２を用いて補助記憶装［１から
各ストリングの先頭ブロックを人力バッファへ読込ませ
た後、各入カバッファに読込んだブロックのなかの最後
のレコードを取出してソートキイ全比較し、ソートキイ
に従って順序付は全行う。併合処理の結果、最も早くブ
ロック内の全レコードを併合し終るブロックが、上記順
序付けによって判定される。

その後、先読み制御処理手段９は、最も早く併合処理を
完了するブロックが属するストリングから予備バッファ
７へ、次のブロックを入力処理手段２を用いて読込み、
併合処理手段８へ制御を戻す。

併合処理手段８は、各人力バッファに読込まれているス
トリングのブロックからレコードを取出し、併合処理を
行って１個のストリングにまとめ、再び補助記憶装［１
へ書出す。しかし、成る１個の入力バッファに読込まれ
ているブロック内しコード七すべて併合し終ると、再び
先読み制御処理手段９へ制御を渡丁。

先読み制御処理手段９は、併合を完了したブロックを格
納している入力バッファと予備バッファとを交換して、
新たに入力バッファとして設定したバッファの内部のブ
ロックを、次のブロックであるとして併合処理手段８に
通知する。

新几に入力バッファとして定義づけられたバッファの内
部のブロックと、併合ｔ’ｆＡ了していないブロックと
から、ブロック内の最後のレコード金取出してソートキ
イを比較し、再び順序付は七行う。その後、併合処理の
結果、最も早くブロック内の全しコードヶ併合し終える
ブロックを判定し、そのブロックが属するストリングか
ら１次のブロックを新たに予備バッファとし次バッファ
へ、入力処理手段２を用いて読込み、併合処理手段８へ
制御を戻す。

第２図は、ストリングのブロック先読みの制御を行う先
読み制御処理手段９の処理ステップを示す流れ図である
。

前述したように、併合処理手段８が先読み制御処理手段
９に制御１［すタイミングは、併合処理の前、各併合処
理の開始時、および併合処理の途中（成る１個の入力バ
ッファに読込まれているブロックの内部のレコード七す
べて併合し終った後）の３つのタイミングである。

まず、ステップ２０１では併合処理手段８がら制御を渡
されたタイミングを判定する。併合処理前の場合にはス
テップ２０２Ｊ−実行し友後、ストリングブロックの大
きさと同一の大きさ會有する複数の入力バッファＩｔ　
、　Ｉ２・・・・・・、ＩＮと予備バッファＩｙとに記
憶部３を分割する。七−の後、合併処理８へ制＃を戻丁
。

併合処理前でなければ、ステップ２０３によって併合処
理の開始時であるか、あるいは併合処理途中であるか全
判定する。併合処理の開始時であれば、ステップ２０４
によって入力処理手段２を用いて各人力バッファＩｌ、
Ｉ２・曲・、ＩＮ　に各ストリングの第１のブロックを
入力した後、ステップ２０９以降會実行する。

併合処理途中である場合には、ステップ２０５によって
併合を完了したブロックがストリングの最後のブロック
であれば、併合を完了したブロックに続く同一ストリン
グの内部のブロックは存在しない言上ステップ２０６に
より併合処理手段８に通知する。併合処理手段８に制御
金臭す併合を完了し九ブロックがス）ＩＪソング最後の
ブロックでなければ、ステップ２０７ｉ％行して、併合
全完了したブロックを格納していた入力バッファＩ、と
予備バッファＩｙとを交換する。ステップ２０８では、
新たに入力バッファとし之予備バッファＩｊの内部のブ
ロックが、併合を完了したブロックの属するストリング
の内部の次のブロックである旨を併合処理手段８へ通知
する。

ステップ２０９以降のステップに、ストＩＪングのブロ
ックを予備バッファＩｙへ先読みする処理のステップで
ある。まずステップ２０９では、入力バッファ１１．　
Ｉ２　、・・・・・・、ＩＮの内部のブロックが、すべ
てストリングの最後のブロックであるか否かを判定する
。すべて最後のブロックであるならば、ブロック先読み
ケ行う必要はないので併合処理手段８へ制仰ケ戻す。

入力バッファＩｆ、Ｉ２・・・・・・、ＩＮの内部のブ
ロックで、ストリングの最後のブロックではないブロッ
クが存在する場合には、ステップ２１０〜２１２ＩＪ！
行する。ステップ２１０では、ストリングの最後のブロ
ックではないブロックから、ブロック内の最後のレコー
ド全取出す。ステップ２１１では、取出したレコードの
ソートキイを比奴して順序付けを行う。ｉｌｌ序付けの
結果、第１位に順序付けられたレコードを含むブロック
が最も早く併＠−會児了するブロックである。またステ
ップ２１２では、上記ブロックの団するストリングから
、次のブロックを入力処理手段２ケ用いて予備バッファ
Ｉｙに入カレ、併合処理手段８へ制御を戻す。

（発明の効果〕 以上説明し友ように本発明は、補助記憶装置ケ用いてソ
ート処理を行うソートプログラムにおいて、補助記憶装
置から複数のストリング全読込み併合処理に際して併合
するストリングの個数と同数の入力バッファと、１個の
予備バッファとを使用してストリングのブロック先読み
ケ行うことにより、１回の併合処理で併合できるストリ
ングの個数全１バツフア方式に比較して１個減するだけ
で、入力バッファへのブロック入力完了待ちによる処理
の中断をなくし、ソート実行処理効率全向上させること
ができるという効果がある。

【図面の簡単な説明】

第１図は、本発明によるソートブロック先読み方式を実
現する一実施例ケ示すブロック図である。 第２図は、ストリングのブロック先読みの制御を行う先
読み制御処理の処理ステップを示す流れ図である。 １・・・補助記憶装置　　２・・・入力処理手段３・・
・記憶部　　４，５．６・・・入カバツファフ・・・予
備バッファ　　８・・・併合処理手段９・・・先読み制
御処理手段

Claims (1)

【特許請求の範囲】
1. レコードをソートするソート処理で中間結果として得ら
   れた複数個のストリングを格納するための補助記憶装置
   と、前記ストリングの併合処理を行うため複数個のブロ
   ックより成る前記ストリングのレコードをブロック単位
   に記憶しておくための記憶部と、前記補助記憶装置から
   前記記憶部へ前記ストリングをブロック単位で読込むた
   めの入力処理手段と、前記記憶部の内部の前記ブロック
   から前記レコードを取出して併合処理を行うための併合
   処理手段と、前記ストリングのブロック先読みを制御す
   るための先読み制御処理手段とを具備して構成したこと
   を特徴とするソートブロック先読み方式。