JPH0145648B2 - - Google Patents
Info
- Publication number
- JPH0145648B2 JPH0145648B2 JP16784580A JP16784580A JPH0145648B2 JP H0145648 B2 JPH0145648 B2 JP H0145648B2 JP 16784580 A JP16784580 A JP 16784580A JP 16784580 A JP16784580 A JP 16784580A JP H0145648 B2 JPH0145648 B2 JP H0145648B2
- Authority
- JP
- Japan
- Prior art keywords
- block
- file
- main memory
- sorted
- stored
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F7/22—Arrangements for sorting or merging computer data on continuous record carriers, e.g. tape, drum, disc
- G06F7/36—Combined merging and sorting
Landscapes
- Engineering & Computer Science (AREA)
- General Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Computer Hardware Design (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
Description
【発明の詳細な説明】
本発明は、ソート・マージの対象となるレコー
ド群を複数のブロツクに分け、各ブロツクを代表
する代表キーを求め、これらの代表キーを用いて
ソート・マージを行うようにしたソート・マージ
処理方式に関するものである。
ド群を複数のブロツクに分け、各ブロツクを代表
する代表キーを求め、これらの代表キーを用いて
ソート・マージを行うようにしたソート・マージ
処理方式に関するものである。
第１図は従来のソート・マージ処理方式を示す
ものであつて、Ｒは入力データ・レコード群、γ
は入力データ・レコード、STはストリングをそ
れぞれ示している。従来のソート・マージ処理方
式においては、先ず第１図イに示すように入力デ
ータ・レコード群Ｒをソート処理して複数のスト
リングSTに分割する。次に、第１図ロに示すよ
うに、これらのストリングSTをマージ処理して
より長い複数のストリングSTを作成する。これ
らのマージ処理を繰返して２本のストリングST
が作出されると、第１図ハに示すようにこれら２
本のストリングをマージ処理して１本のストリン
グを作り出す。
ものであつて、Ｒは入力データ・レコード群、γ
は入力データ・レコード、STはストリングをそ
れぞれ示している。従来のソート・マージ処理方
式においては、先ず第１図イに示すように入力デ
ータ・レコード群Ｒをソート処理して複数のスト
リングSTに分割する。次に、第１図ロに示すよ
うに、これらのストリングSTをマージ処理して
より長い複数のストリングSTを作成する。これ
らのマージ処理を繰返して２本のストリングST
が作出されると、第１図ハに示すようにこれら２
本のストリングをマージ処理して１本のストリン
グを作り出す。
通常、第１図イのソート処理で作り出されるス
トリングは直接アクセス記憶装置などの外部記憶
装置上に置かれ、その本数は入力データ・レコー
ドの件数と並べ換えに使用できる主記憶量との関
係で定まる。第１図ロのようにストリングをマー
ジするために、外部記憶装置と主記憶装置間のデ
ータの移動が行われ、データ移動の総量（アクセ
ス量）は第１図イで作成されたストリングの本数
と上記の主記憶量との関係で決定される。外部記
憶装置へのアクセスは主記憶へのアクセスに比べ
て非常に遅いので、ソート・マージ処理の処理速
度は外部記憶装置へのアクセス量（アクセス回
数）によつて殆んど決定される。
トリングは直接アクセス記憶装置などの外部記憶
装置上に置かれ、その本数は入力データ・レコー
ドの件数と並べ換えに使用できる主記憶量との関
係で定まる。第１図ロのようにストリングをマー
ジするために、外部記憶装置と主記憶装置間のデ
ータの移動が行われ、データ移動の総量（アクセ
ス量）は第１図イで作成されたストリングの本数
と上記の主記憶量との関係で決定される。外部記
憶装置へのアクセスは主記憶へのアクセスに比べ
て非常に遅いので、ソート・マージ処理の処理速
度は外部記憶装置へのアクセス量（アクセス回
数）によつて殆んど決定される。
本発明は、上記の考察に基づくものであつて外
部記憶装置へのアクセス量を減少でき、これによ
つてソート・マージ処理の処理速度を向上できる
ようにしたソート・マージ処理方式を提供するこ
とを目的としている。そしてそのため、本発明の
ソート・マージ処理方式は、 入力フアイルに格納されている入力データ・レ
コード群を、処理装置、主記憶、直接アクセス記
憶装置上の作業フアイルを有する計算機でソー
ト・マージ処理し、ソート・マージされたデー
タ・レコードの列を出力フアイルに格納するソー
ト・マージ処理方式において、 (a) 上記入力フアイルに格納れている入力デー
タ・レコード群を順次に上記主記憶に読込み、
上記処理装置で以て処理することにより、上記
入力データ・レコード群を、データ・レコード
の集合である所の複数のブロツクに分割して上
記作業フアイルに格納すると共に、各ブロツク
毎に昇順もしくは降順に従い代表キーを選択
し、作業フアイル上のブロツクのアドレスと当
該ブロツクの代表キーで以てブロツク毎の付属
情報を作成し、作成された付属情報の集合を上
記作業フアイルに格納し、 (b) 作業フアイル上の付属情報の集合を上記主記
憶に読込み、上記処理装置で以て代表キーに従
つてソート処理し、ソート処理された付属情報
の列を上記作業フアイルに格納し、 (c) ソート処理された付属情報の列に従い、上記
作業フアイルよりブロツクを上記主記憶に読込
み、該ブロツクから主記憶上にデータ・レコー
ド列を生成し、次に読込まれた代表キーに基づ
いて上記データ・レコード列を２分し、２個の
部分列の内の所定の部分列を上記出力フアイル
に格納し、残された部分列と次に読込まれたブ
ロツクのデータ・レコードとをマージして、新
たなレコードとして主記憶上に生成する ことを特徴とするものである。以下、本発明を図
面を参照しつつ説明する。
部記憶装置へのアクセス量を減少でき、これによ
つてソート・マージ処理の処理速度を向上できる
ようにしたソート・マージ処理方式を提供するこ
とを目的としている。そしてそのため、本発明の
ソート・マージ処理方式は、 入力フアイルに格納されている入力データ・レ
コード群を、処理装置、主記憶、直接アクセス記
憶装置上の作業フアイルを有する計算機でソー
ト・マージ処理し、ソート・マージされたデー
タ・レコードの列を出力フアイルに格納するソー
ト・マージ処理方式において、 (a) 上記入力フアイルに格納れている入力デー
タ・レコード群を順次に上記主記憶に読込み、
上記処理装置で以て処理することにより、上記
入力データ・レコード群を、データ・レコード
の集合である所の複数のブロツクに分割して上
記作業フアイルに格納すると共に、各ブロツク
毎に昇順もしくは降順に従い代表キーを選択
し、作業フアイル上のブロツクのアドレスと当
該ブロツクの代表キーで以てブロツク毎の付属
情報を作成し、作成された付属情報の集合を上
記作業フアイルに格納し、 (b) 作業フアイル上の付属情報の集合を上記主記
憶に読込み、上記処理装置で以て代表キーに従
つてソート処理し、ソート処理された付属情報
の列を上記作業フアイルに格納し、 (c) ソート処理された付属情報の列に従い、上記
作業フアイルよりブロツクを上記主記憶に読込
み、該ブロツクから主記憶上にデータ・レコー
ド列を生成し、次に読込まれた代表キーに基づ
いて上記データ・レコード列を２分し、２個の
部分列の内の所定の部分列を上記出力フアイル
に格納し、残された部分列と次に読込まれたブ
ロツクのデータ・レコードとをマージして、新
たなレコードとして主記憶上に生成する ことを特徴とするものである。以下、本発明を図
面を参照しつつ説明する。
第２図イ，ロ，ハは本発明のソート・マージ処
理方式の１例を説明する図、第３図は本発明を実
施するために必要な機器構成を示す図である。
理方式の１例を説明する図、第３図は本発明を実
施するために必要な機器構成を示す図である。
第２図および第３図において、Ｂはブロツク、
AIは付属情報、１は入力フアイル、２は処理装
置、３は主記憶、４は作業フアイル、５は出力フ
アイルをそれぞれ示している。
AIは付属情報、１は入力フアイル、２は処理装
置、３は主記憶、４は作業フアイル、５は出力フ
アイルをそれぞれ示している。
従来のソート・マージ処理方式においては、マ
ージ処理はストリング単位で行われるが、本発明
においては各ストリングを構成するブロツク単位
にマージ処理を行う。処理手順は下記の通りであ
る。
ージ処理はストリング単位で行われるが、本発明
においては各ストリングを構成するブロツク単位
にマージ処理を行う。処理手順は下記の通りであ
る。
入力データ・レコード群Ｒは入力フアイル１に
格納されているが、第２図イに示すように入力デ
ータ・レコード群Ｒを主記憶３上に順次読込んで
処理装置２でソート処理、ブロツク化処理および
付属情報作成処理を行い、その結果を作業フアイ
ル４に格納する。ソート処理とは複数のストリン
グを作成する処理であり、ブロツク処理とは各ス
トリングSTを複数のブロツクＢに分割する処理
である。ブロツクとは主記憶装置と外部記憶装置
との間におけるデータ転送の単位である。付加情
報作成処理とは、各ブロツクＢ毎に、代表キーお
よびそのブロツクの作業フアイル４のアドレスよ
り成る付加情報AIを作成し、その付加情報AIの
作業フアイルに書込む処理である。代表キーとし
ては、そのブロツクに属するレコードのキーのう
ち最も大きいもの或は最も小さいものが代表キー
として選択される。
格納されているが、第２図イに示すように入力デ
ータ・レコード群Ｒを主記憶３上に順次読込んで
処理装置２でソート処理、ブロツク化処理および
付属情報作成処理を行い、その結果を作業フアイ
ル４に格納する。ソート処理とは複数のストリン
グを作成する処理であり、ブロツク処理とは各ス
トリングSTを複数のブロツクＢに分割する処理
である。ブロツクとは主記憶装置と外部記憶装置
との間におけるデータ転送の単位である。付加情
報作成処理とは、各ブロツクＢ毎に、代表キーお
よびそのブロツクの作業フアイル４のアドレスよ
り成る付加情報AIを作成し、その付加情報AIの
作業フアイルに書込む処理である。代表キーとし
ては、そのブロツクに属するレコードのキーのう
ち最も大きいもの或は最も小さいものが代表キー
として選択される。
第２図イのソート処理、ブロツク化処理および
付属情報作成処理が行われた後、第２図ロに示す
ように、作業フアイル４より付属情報AIの集合
を主メモリ３上に読込み、代表キーに従つてソー
ト処理を行い、付属情報AIのストリングを作成
し、これを再び作業フアイル４に書込む。
付属情報作成処理が行われた後、第２図ロに示す
ように、作業フアイル４より付属情報AIの集合
を主メモリ３上に読込み、代表キーに従つてソー
ト処理を行い、付属情報AIのストリングを作成
し、これを再び作業フアイル４に書込む。
第２図ロのソート処理を行つて付属情報ストリ
ングを作成した後、付加情報AIのストリングに
従い、作業フアイル４上のブロツクＢを順次に主
記憶３に読込み、マージ処理を施し、主記憶３上
にデータ・レコードγのストリングを作成する。
主記憶３の内のストリングを、作業フアイル４に
残つている付属情報のストリングのおける先頭の
付属情報の代表キーを用いて２つの部分に分け
る。一方は上記の代表キーより前にあるキーをも
つデータ・レコードのストリングであり、他方は
後方のデータ・レコードのストリングとなる。前
者は直ちに出力レコードとして主記憶３より追出
され、出力フアイル５に格納される。出力フアイ
ル５にデータ・レコードのストリングを格納した
後、主記憶３に後続ブロツクＢを作業フアイル４
から読込み可能であれば、後続のブロツクＢを読
込み、上記のようなマージ処理を行う。主記憶３
に後続のブロツクＢを読込むスペースが存在しな
い場合には、後方のデータ・レコードのストリン
グ中で不必要なレコードを作業フアイル４に書戻
すことにより空きスペースを確保する。この場
合、作業フアイル４へ書戻されるブロツクに対
し、第２図イのようにして付属情報を作成し、こ
の作成した付属情報を第２図ロのように作成され
た付属情報のストリングの中の正しい位置に挿入
する。書戻されたブロツクをも含め、作業フアイ
ル４上に存在する全てのブロツクをマージし、出
力レコード列とした時点で処理は完了する。
ングを作成した後、付加情報AIのストリングに
従い、作業フアイル４上のブロツクＢを順次に主
記憶３に読込み、マージ処理を施し、主記憶３上
にデータ・レコードγのストリングを作成する。
主記憶３の内のストリングを、作業フアイル４に
残つている付属情報のストリングのおける先頭の
付属情報の代表キーを用いて２つの部分に分け
る。一方は上記の代表キーより前にあるキーをも
つデータ・レコードのストリングであり、他方は
後方のデータ・レコードのストリングとなる。前
者は直ちに出力レコードとして主記憶３より追出
され、出力フアイル５に格納される。出力フアイ
ル５にデータ・レコードのストリングを格納した
後、主記憶３に後続ブロツクＢを作業フアイル４
から読込み可能であれば、後続のブロツクＢを読
込み、上記のようなマージ処理を行う。主記憶３
に後続のブロツクＢを読込むスペースが存在しな
い場合には、後方のデータ・レコードのストリン
グ中で不必要なレコードを作業フアイル４に書戻
すことにより空きスペースを確保する。この場
合、作業フアイル４へ書戻されるブロツクに対
し、第２図イのようにして付属情報を作成し、こ
の作成した付属情報を第２図ロのように作成され
た付属情報のストリングの中の正しい位置に挿入
する。書戻されたブロツクをも含め、作業フアイ
ル４上に存在する全てのブロツクをマージし、出
力レコード列とした時点で処理は完了する。
以上の説明から明らかなように、本発明のソー
ト・マージ処理方式によれば、ソート・マージ処
理を効率的に処理することが出来る。従来方式に
おいては、入力データ・レコードの順序が殆んど
揃つているような場合でも、揃つていない場合と
略ぼ同様な処理時間を必要としたが、本発明のソ
ート・マージ処理方式によれば、入力データ・レ
コードの順序が略ぼ揃つているような場合には非
常に短時間で処理を終了することが出来る。
ト・マージ処理方式によれば、ソート・マージ処
理を効率的に処理することが出来る。従来方式に
おいては、入力データ・レコードの順序が殆んど
揃つているような場合でも、揃つていない場合と
略ぼ同様な処理時間を必要としたが、本発明のソ
ート・マージ処理方式によれば、入力データ・レ
コードの順序が略ぼ揃つているような場合には非
常に短時間で処理を終了することが出来る。
第１図は従来のソート・マージ処理方式を示す
図、第２図は本発明のソート・マージ処理方式の
１例を説明する図、第３図は本発明を実施するた
めに必要な機器構成を示す図である。 Ｒ……入力データ・レコード群、γ……入力デ
ータ・レコード、ST……ストリング、Ｂ……ブ
ロツク、AI……付属情報、１……入力フアイル、
２……処理装置、３……主記憶、４……作業フア
イル、５……出力フアイル。
図、第２図は本発明のソート・マージ処理方式の
１例を説明する図、第３図は本発明を実施するた
めに必要な機器構成を示す図である。 Ｒ……入力データ・レコード群、γ……入力デ
ータ・レコード、ST……ストリング、Ｂ……ブ
ロツク、AI……付属情報、１……入力フアイル、
２……処理装置、３……主記憶、４……作業フア
イル、５……出力フアイル。
Claims (1)
- 【特許請求の範囲】 １ 入力フアイルに格納されている入力データ・
レコード群を、処理装置、主記憶、直接アクセス
記憶装置上の作業フアイルを有する計算機でソー
ト・マージ処理し、ソート・マージされたデー
タ・レコードの列を出力フアイルに格納するソー
ト・マージ処理方式において、 (a) 上記入力フアイルに格納されている入力デー
タ・レコード群を順次に上記主記憶に読込み、
上記処理装置で以て処理することにより、上記
入力データ・レコード群を、データ・レコード
の集合である所の複数のブロツクに分割して上
記作業フアイルに格納すると共に、各ブロツク
毎に昇順もしくは降順に従い代表キーを選択
し、作業フアイル上のブロツクのアドレスと当
該ブロツクの代表キーで以てブロツク毎の付属
情報を作成し、作成された付属情報の集合を上
記作業フアイルに格納し、 (b) 作業フアイル上の付属情報の集合を上記主記
憶に読込み、上記処理装置で以て代表キーに従
つてソート処理し、ソート処理された付属情報
の列を上記作業フアイルに格納し、 (c) ソート処理された付属情報の列に従い、上記
作業フアイルよりブロツクを上記主記憶に読込
み、該ブロツクから主記憶上にデータ・レコー
ド列を生成し、次に読込まれた代表キーに基づ
いて上記データ・レコード列を２分し、２個の
部分列の内の所定の部分列を上記出力フアイル
に格納し、残された部分列と次に読込まれたブ
ロツクのデータ・レコードとをマージして、新
たなレコードとして主記憶上に生成する ことを特徴とするソート・マージ処理方式。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP16784580A JPS5790757A (en) | 1980-11-28 | 1980-11-28 | Sort-merge process system |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP16784580A JPS5790757A (en) | 1980-11-28 | 1980-11-28 | Sort-merge process system |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS5790757A JPS5790757A (en) | 1982-06-05 |
| JPH0145648B2 true JPH0145648B2 (ja) | 1989-10-04 |
Family
ID=15857146
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP16784580A Granted JPS5790757A (en) | 1980-11-28 | 1980-11-28 | Sort-merge process system |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS5790757A (ja) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH0782426B2 (ja) * | 1984-08-22 | 1995-09-06 | 株式会社日立製作所 | マージ・ソート方法および装置 |
-
1980
- 1980-11-28 JP JP16784580A patent/JPS5790757A/ja active Granted
Also Published As
| Publication number | Publication date |
|---|---|
| JPS5790757A (en) | 1982-06-05 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5117495A (en) | Method of sorting data records | |
| US5293616A (en) | Method and apparatus for representing and interrogating an index in a digital memory | |
| JPH02178730A (ja) | 分割法を用いた内部ソート方式 | |
| JP3515810B2 (ja) | ソート処理方法および装置 | |
| JPH0145648B2 (ja) | ||
| JPH0782429B2 (ja) | 複数ファイルのマージ方法 | |
| JP2586610B2 (ja) | ファイル作成方式 | |
| JPS62287350A (ja) | インデツクス一括更新方式 | |
| JP2669241B2 (ja) | マイグレーション処理方式 | |
| JP2604787B2 (ja) | 二次元データ格納方式 | |
| JP3047400B2 (ja) | データ処理装置 | |
| JPH02116936A (ja) | 再編成方式 | |
| JPH048816B2 (ja) | ||
| JPH07101382B2 (ja) | マ−ジ処理装置 | |
| JPH03202934A (ja) | データ処理装置 | |
| JP2507399B2 (ja) | デ―タベ―ス装置 | |
| JP2788849B2 (ja) | 連番記述によるグルーピング方法 | |
| JPH0275018A (ja) | マージ処理方法 | |
| JP3456481B2 (ja) | 情報処理装置 | |
| JPS61151754A (ja) | デ−タベ−ス回復処理方式 | |
| JPH04250568A (ja) | レコード検索装置 | |
| JPS626255B2 (ja) | ||
| JPS59214948A (ja) | デ−タソ−テイング方法 | |
| JPH02216554A (ja) | 索引順編成ファイルの再編成方式 | |
| JPH01147720A (ja) | 分類処理方式 |