JP3061486B2 - データソート処理システム - Google Patents

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、ソート対象のデータ列
をデータの持つ属性値の大きさに従ってソートするよう
処理するデータソート処理システムに関し、特に、高速
にソート処理を実行できるようにするデータソート処理
システムに関する。

【０００２】データ処理の様々な分野で、データ列をデ
ータ値やキー値等の属性値に従ってソートしていく処理
が実行されている。このソート処理は、ソート対象のデ
ータの数が多くなるに従って長い処理時間を要すること
になる。これから、ソート対象のデータの数が多くなる
ときにあっても、高速にソート処理を実行できるような
構成の構築が叫ばれている。

【０００３】

【従来の技術】従来、ソート処理を高速で実行する必要
があるときには、最初に、ソート対象のデータ列を単純
に複数のブロックに分割して、この各ブロック毎にソー
ト処理を実行し、続いて、ブロック間で順次データを比
較しながらソート処理を行っていくことで、全体のソー
ト処理を完成させるという２段階のソート処理手順に従
って、高速性を実現するという方法を採っていた。

【０００４】

【発明が解決しようとする課題】しかしながら、このよ
うな従来技術のソート処理手順では、未だ処理時間が長
いという問題点があった。

【０００５】本発明はかかる事情に鑑みてなされたもの
であって、データ列をデータの持つ属性値の大きさに従
ってソートするよう処理するデータソート処理システム
にあって、従来技術よりも高速なソート処理を実現する
新たなデータソート処理システムの提供を目的とする。

【０００６】

【課題を解決するための手段】図１に本発明の原理構成
を図示する。図中、１は本発明を具備するデータ処理装
置である。このデータ処理装置１は、第１の展開手段１
０と、テーブル手段１１と、分割手段１２と、第２の展
開手段１３と、ソート手段１４と、連結手段１５と、第
３の展開手段１６と、登録手段１７とを備える。

【０００７】この第１の展開手段１０は、ソート対象の
データ列を展開する。この展開されるソート対象のデー
タは、データ値やキー値といった属性値を持つ。テーブ
ル手段１１は、ソート対象のデータ列の持つ属性値域に
含まれる複数の属性値を管理する。分割手段１２は、テ
ーブル手段１１の管理する属性値を使って、第１の展開
手段１０に展開されるソート対象のデータ列を複数のブ
ロックに分割する。

【０００８】第２の展開手段１３は、分割手段１２の分
割したブロックを単位にしてソート対象のデータ列を展
開する。ソート手段１４は、第２の展開手段１３の展開
する各ブロックの持つデータをブロック毎に属性値の大
きさに従ってソートする。連結手段１５は、第２の展開
手段１３の展開するソート対象のデータ列を連結する。
第３の展開手段１６は、連結手段１５によりソートされ
たデータ列を展開する。登録手段１７は、第３の展開手
段１６に展開される前回ソートされたデータ列を概略同
一のデータ数を持つ複数のブロックに分割し、これらの
ブロックを区切るデータの属性値を特定する機能と、こ
の特定した属性値をテーブル手段１１に登録する機能と
を有する。

【０００９】

【作用】本発明では、登録手段１７は、第３の展開手段
１６に展開される前回ソートされたデータ列を概略同一
のデータ数を持つ複数のブロックに分割し、これらのブ
ロックを区切るデータの属性値を特定して、その属性値
をテーブル手段１１に登録する。

【００１０】このようにして、テーブル手段１１に属性
値が登録されると、分割手段１２は、第１の展開手段１
０に展開される今回ソート対象となるデータの持つ属性
値と、テーブル手段１１の管理する属性値とを比較する
ことで、今回ソート対象となるデータ列を複数のブロッ
クに分割して、その分割結果を第２の展開手段１３に展
開する。

【００１１】第２の展開手段１３に分割手段１２の分割
結果が展開されると、ソート手段１４は、第２の展開手
段１３の展開する各ブロックの持つデータをブロック毎
に属性値の大きさに従ってソートし、このソート手段１
４によるソート処理が終了すると、連結手段１５は、ソ
ート手段１４によりソートされたブロックのデータを、
ブロックの生成元となったテーブル手段１１の管理属性
値の値順に連結することで、第１の展開手段１０に展開
されるデータ列のソート処理を完成させる。

【００１２】このようにして、本発明では、前回ソート
したデータ列を概略同一のデータ数を持つ複数のブロッ
クに分割することで、今回ソートするデータ列の分割ソ
ート用のキー配列を求める構成を採って、そのキー配列
を使って、今回ソートするデータ列を分割しソートして
それらを連結することでソート処理を実行するという構
成を採ることから、直接的かつ簡単に、概略同一のデー
タ数を持つ複数のブロックに分割できるようになること
で、高速のソート処理を実行できるようになる。

【００１３】

【実施例】以下、実施例に従って本発明を詳細に説明す
る。図２に、本発明を具備するデータ処理装置１の実行
するソート処理の全体処理フローを図示する。

【００１４】この処理フローに示すように、本発明を具
備するデータ処理装置１は、先ず最初に、ステップ１
で、登録手段１７による登録処理を実行し、次に、ステ
ップ２で、分割手段１２による分割処理を実行し、続い
て、ステップ３で、ソート手段１４によるソート処理を
実行し、続いて、ステップ４で、連結手段１５による連
結処理を実行することで、ソート対象のデータ列のソー
ト処理を実現する構成を採るものである。

【００１５】図３に、登録手段１７の実行する登録処理
の詳細な処理フローの一実施例、図４に、分割手段１２
の実行する分割処理の詳細な処理フローの一実施例、図
５に、ソート手段１４の実行するソート処理の詳細な処
理フローの一実施例、図６に、連結手段１５の実行する
連結処理の詳細な処理フローの一実施例を図示する。次
に、これらの処理フローに従って、本発明のソート処理
について詳細に説明する。

【００１６】登録手段１７は、ソート対象のデータ列の
ソート要求が発行されると、図３の処理フローに示すよ
うに、先ず最初に、ステップ１で、ユーザと対話するこ
とでブロック数ｎを設定する。ここで、このブロック数
ｎを予め固定的に設定しておくことも可能である。次
に、ステップ２で、第３の展開手段１６に展開されてい
る前回ソートされたデータ列をｎ個に分割して、そのｎ
個を区切る分割点のデータの持つ属性値を特定してテー
ブル手段１１に登録する。

【００１７】このようにして、登録手段１７の処理に従
って、テーブル手段１１には、前回ソートされたデータ
列の持つ属性値域に含まれる複数の属性値が登録される
ことになる。

【００１８】テーブル手段１１に属性値が登録される
と、分割手段１２は、図４の処理フローに示すように、
先ず最初に、ステップ１で、第２の展開手段１３に登録
手段１７の設定したｎ個のブロックエントリーを生成す
る。このブロックエントリーは、テーブル手段１１の管
理する属性値に対応付けられることになるものであっ
て、１番からｎ番までのブロック番号が割り当てられる
ことになる。次に、ステップ２で、第１の展開手段１０
に展開されているソート対象のデータ列から、先頭のデ
ータ（ステップ５を経由してくるときには、前回読み出
したデータの次のデータ）を１つ読み出す。

【００１９】続いて、ステップ３で、この読み出したデ
ータの持つ属性値が、テーブル手段１１の属性値の区切
るどのゾーンに属するのかを特定する。続いて、ステッ
プ４で、この読み出したデータを特定したゾーンの指す
ブロック番号のブロックエントリーに格納する。そし
て、続くステップ５で、第１の展開手段１０に展開され
ているソート対象のデータの全てを読み出したのか否か
を判断して、読み出したときには、処理を終了し、読み
出していないときには、ステップ２に戻ることで全デー
タに対しての処理を実行する。

【００２０】このようにして、分割手段１２の処理に従
って、ソート対象のデータが、並びの確定されている複
数のブロックエントリーに振り分けられて格納されるこ
とになる。

【００２１】ソート対象のデータ列が複数のブロックに
分割されて第２の展開手段１３に展開されると、ソート
手段１４は、図５の処理フローに示すように、先ず最初
に、ステップ１で、変数ｉに“１”を設定する。次に、
ステップ２で、変数ｉの指すｉ番目のブロックデータを
属性値の大きさに従ってソートする。続いて、ステップ
３で、変数ｉの値が“ｎ”に達したのか否かを判断し
て、達したと判断するときには、処理を終了し、達しな
いと判断するときには、ステップ４に進み、変数ｉの値
を１つ歩進させてからステップ２に戻っていくことで、
全ブロックデータに対してのソート処理を実行する。

【００２２】このようにして、ソート手段１４の処理に
従って、第２の展開手段１３に展開される各ブロックの
持つデータがブロック毎に属性値の大きさに従ってソー
トされることになる。

【００２３】第２の展開手段１３に展開されるブロック
データがブロックを単位としてソートされると、連結手
段１５は、図６の処理フローに示すように、先ず最初
に、ステップ１で、変数ｊに“１”を設定する。次に、
ステップ２で、変数ｊの指すｊ番目のブロックデータ
を、前回格納した（ｊ−１）番目のブロックデータに続
けて第３の展開手段１６に展開する。ここで、１番目の
ブロックデータについては、先頭であることから規定の
展開位置に展開する。続いて、ステップ３で、変数ｊの
値が“ｎ”に達したのか否かを判断して、達したと判断
するときには、処理を終了し、達しないと判断するとき
には、ステップ４に進み、変数ｊの値を１つ歩進させて
からステップ２に戻っていくことで、ｎ個あるブロック
データの連結処理を実行する。

【００２４】このようにして、連結手段１５の処理に従
って、第１の展開手段１０に展開されるデータ列のソー
ト処理が完成されることになる。次に、図７に従って、
本発明のソート処理について具体的に説明する。

【００２５】図中に示すように、第１の展開手段１０に
は、データ値をソートキーとする１２個のソート対象の
データが展開されており、テーブル手段１１には、属性
値となるデータ値として、"1","7","14","20" が登録さ
れているとする。

【００２６】このソート対象のデータ列に対して、登録
手段１７は、ブロック数として“３”を設定し、このブ
ロック数の設定を受けて、分割手段１２は、Ａ，Ｂ，Ｃ
で識別される３個のブロックエントリーを生成する。

【００２７】次に、分割手段１２は、図中ので示すよ
うに、第１の展開手段１０からソート対象のデータを１
つずつ読み出していって、この読み出したデータのデー
タ値が"1" から"7" の範囲にあるときにはＡのブロック
エントリーに格納し、"8" から"14"の範囲にあるときに
はＢのブロックエントリーに格納し、"15"から"20"の範
囲にあるときにはＣのブロックエントリーに格納してい
く処理を実行する。

【００２８】続いて、ソート手段１４は、図中ので示
すように、Ａ，Ｂ，Ｃの３つのブロックデータをブロッ
ク毎にデータ値の大きさに従ってソートする。続いて、
連結手段１５は、図中ので示すように、ソートされた
ブロックデータをブロックＡ、ブロックＢ、ブロックＣ
という順に従って第３の展開手段１６に展開すること
で、この３つのブロックデータを連結して、第１の展開
手段１０に展開されるソート対象のデータのソートを完
結する。

【００２９】続いて、登録手段１７は、図中のに示す
ように、第３の展開手段１６に展開されるソートされた
データ列からテーブル手段１１に登録する新たなデータ
値として"1","6","14","20" を決定して、これらのデー
タ値をテーブル手段１１に登録する。

【００３０】図示実施例について説明したが、本発明は
これに限定されるものではない。例えば、実施例では、
登録手段１７が前回ソートされたデータ列をデータ数の
等しいブロックに分割することで、テーブル手段１１に
登録する属性値を決定していく構成を開示したが、正確
に等分割する必要はなく、概略同一のデータ数を持つよ
うに分割することでもよい。

【００３１】

【発明の効果】以上説明したように、本発明では、前回
ソートしたデータ列を概略同一のデータ数を持つ複数の
ブロックに分割することで、今回ソートするデータ列の
分割ソート用のキー配列を求める構成を採って、そのキ
ー配列を使って、今回ソートするデータ列を分割しソー
トしてそれらを連結することでソート処理を実行すると
いう構成を採ることから、サンプリング手法を用いるこ
となく、直接的に、概略同一のデータ数を持つ複数のブ
ロックに分割できるようになることで、高速のソート処
理を実行できるようになるとともに、ヒストグラムを作
成するといった複雑な手法を用いることなく、簡単に、
概略同一のデータ数を持つ複数のブロックに分割できる
ようになることで、高速のソート処理を実行できるよう
になる。

【図面の簡単な説明】

【図１】本発明の原理構成図である。

【図２】本発明のソート処理の全体処理フローである。

【図３】登録手段の実行する処理フローの一実施例であ
る。

【図４】分割手段の実行する処理フローの一実施例であ
る。

【図５】ソート手段の実行する処理フローの一実施例で
ある。

【図６】連結手段の実行する処理フローの一実施例であ
る。

【図７】本発明の処理の説明図である。

【符号の説明】

１ データ処理装置 １０ 第１の展開手段 １１ テーブル手段 １２ 分割手段 １３ 第２の展開手段 １４ ソート手段 １５ 連結手段 １６ 第３の展開手段 １７ 登録手段

───────────────────────────────────────────────────── フロントページの続き (56)参考文献 特開 昭61−34626（ＪＰ，Ａ)

Claims (1)

(57)【特許請求の範囲】
1. 【請求項１】 データ列を、データの持つ属性値の大き
   さに従ってソートするデータソート処理システムであっ
   て、前回ソートされたデ ータ列を概略同一のデータ数を持つ
   複数のブロックに分割して、該ブロックを区切る属性値
   を特定する特定手段と、 データの持つ属性値と、上記特定手段の特定した属性値
   とを比較することで、今回ソートするデータ列を複数の
   ブロックに分割する分割手段と、 上記分割手段により分割された各ブロックの持つデータ
   を、ブロック毎に属性値の大きさに従ってソートするソ
   ート手段と、 上記ソート手段によりソートされたブロックのデータ
   を、該ブロックの生成元となった上記特定手段の特定し
   た属性値の値順に連結する連結手段とを備えることを、 特徴とするデータソート処理システム。