JPH01201722A - ソート処理装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明はソート処理装置の構成に関し、より詳細には、
ソート対象とするレコードを複数のデータに分割して１
分割した各データに対して、ソート対象であるか否かの
指定と、昇順あるいは降順のソート順を指定できるよう
に構成したことを特徴とするソート処理装置に関する。

〔従来の技術〕

一般に、データベース処理で扱う個々のデータをレコー
ドという、レコードの件数が極めて大きい場合や、複数
のデータベースを処理対象とする場合には、汎用の電子
計算機で処理すると膨大な時間を必要とする。このため
、データベース処理の一部あるいは全体を直接ハードウ
ェアで実行して高速化するソート処理装置が３例えば特
開昭６０−８１６４０号公報に開示されている。

第３図は、上述の特開昭６０−８１６４０号公報に開示
されているソート処理装置の構成を示すものである０図
において、１は比較ユニット、２はユニット間データ転
送路、３は第１のメモリ、４は第２のメモリ、５は比較
器、６は第１のフラグレジスタ、７は第２のフラグレジ
スタを示している。

ソート対象とするレコードは、ユニット間データ転送路
２および比較器５で一度に転送あるいは比較できる単位
のデータに分割して、比較ユニットｌの１次元アレイか
ら成るソート処理装置に入力する。各比較ユニッ）１で
は、入力されるデータと自ユニット内の第１あるいは第
２のメモリに格納されたレコードの対応するデータとを
比較して、その結果を第１のフラグレジスタに累積する
。

自ユニット内の第１あるいは第２のメモリの何れに格納
されたレコードと入力レコードとを比較するかは、第２
のフラグレジスタの値によって決まり、第１及び第２の
メモリに格納された２つのレコードのうち、一方が入力
レコードとの比較対象となり、他方が隣接する比較ユニ
ットへの転送対象となる。転送対象となるレコードは分
割したデータとして隣接する比較ユニットに出力され、
隣接する比較ユニットにおける入力データとして該比較
ユニットで比較される。

以上示したように１本従来法に示すソート処理装置は、
複数の１次元アレイ状に接続された比較ユニット１の各
々で、ソート対象とするレコードを複数の分割したデー
タとしてパイプライン的に入力し並列比較によって、高
速にソートできる様に構成されたものである。また、ソ
ート可能なレコード長の上限は、比較ユニット内の第１
および第２のメモリ容量にのみ依存し、ソート対象とす
るレコードの長さに関係なく比較器およびユニット間デ
ータ転送路を構成できる。

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

上記従来技術においては、ソート処理装置に入力するレ
コードを複数のデータに分割して比較と転送処理を行う
ことから、ソート対象とするレコード長に関係なく比較
器やデータ転送路を構成することができる。しかし１本
従来法では、レコード全体を比較して、昇順あるいは降
順にソートすることを目的としていたことから、レコー
ド長が長いソートはできるが、複数のカラムからなるレ
コードの特定カラムだけを比較の対象に指定したり、特
定カラムを昇順にソートし、他のカラムを降順にソート
するような複雑な条件によるソートが行えない問題があ
った。

このため、レコードから比較の対象とする部分だけを取
り出す前処理を必要としたり、レコードを構成する一部
カラムについて昇順にソートした後に、他のカラムにつ
いて降順にソートする等の処理を必要とし、ソート処理
時間の増大や装置の複雑化を招く要因となっていた。

本発明は、上記従来技術の問題点を解決することを目的
として、複雑なソート条件に基づいてソートすることが
できるソート処理装置を提供することにある。

〔問題点を解決するための手段〕

本発明の上記目的は、２個のレコードを入力して格納す
る記憶手段と、格納された該２個のレコードを複数個の
データに分割して該レコード記憶手段から読みだして比
較する比較手段と、該分割されたデータの内で比較の対
象であると指定されたデータに限定して、昇順あるいは
降順に指定されたソート条件に基づいて、前記比較手段
の出力に反転あるいは非反転操作を加えてルコード分の
比較結果を累積して７前記レコードの大小関係を判定す
る比較結果累積手段とを少なくとも具備した比較ユニッ
トの１次元アレイからなり。

該比較結果累積手段の出力によって、前記２個の格納し
たレコードの何れかを隣接する比較ユニットに出力し、
同時に、他方の隣接する比較ユニットからレコードを入
力することによって、入力レコードを指定されたソート
条件に基づいてソートすることを特徴としたソート処理
装置によって達成される。

〔作用〕

本発明のソート処理装置では、レコードを分割して比較
し、得られた比較結果をルコード分累積する際に、指定
されたソート条件によって比較結果を無効としたり、比
較結果を反転して累積することによって、複雑なソート
条件でソートするように構成したことを特徴とし、この
結果、比較結果累積回路にわずかな回路を付加すること
によって、複数カラムからなるレコードの特定カラムを
比較の対象に指定し、更に、比較の対象に指定されたカ
ラムに対して昇順あるいは降順にソートするように指定
できるソート処理装置を容易に実現できる。

〔実施例〕

以下１本発明の実施例を図面に基づいて詳細に説明する
。

第１図は２本発明のソート処理装置の一実施例を示す構
成図であり、第３図に示した従来のソート処理装置に於
ける比較器５以降に設ける比較結果累積回路について、
その構成を詳細に示している。ここでは１本発明の複雑
なソート条件の指定を可能とした比較結果累積回路の構
成及びその動作を詳細に説明し、従来技術の項で説明し
たソート処理装置の動作原理については簡略な説明にと
どめる。

図において、１０はフリップフロップ回路、ｌｌはアン
ド回路、１２はオア回路、１３はインバータ回路、１４
はイクスクルーシプオア回路を示す論理シンボルであり
、いずれもＴＴＬ等の既知な回路で容易に実現できる。

また５図中の５は第３図に示した比較器と同一な回路構
成であり、実現は容易である。

第２図は、第１図に示した比較結果累積回路の動作を説
明するタイミング図であり、第２図の例では、２つの４
桁の整数１２３４．１１２５を１桁ずつ比較し、比較の
結果を４桁分累積する動作を示している。したがって、
第２図の例では、４桁の整数からなるレコードは、各桁
毎にカラムを形成し、４つのカラムから構成されている
こととする。

図中の信号名は第１図に対応したものであり。

以下に、各信号の役割を示す、信号■および■はソート
処理装置を同期して動作させるためのタイミング信号で
ある。信号ＡおよびＢは、レコードを分割して比較・転
送する際のデータ入力を示している。ＥＮＤ信号は、連
続して比較するレコードの区切りを示す信号であり、Ｅ
ＮＤ信号が論理値１になるまで比較結果を累積する。Ｃ
ＭＰおよびＡ／Ｄ信号は、ソート条件を指定する信号で
ある。ＣＭＰ信号が論理値ｌの時、比較器に入力されて
いるカラム（信号ＡおよびＢの入力データ）は、ソート
する際の比較対象であることを示し。

Ａ／Ｄが論理値ｌの時は昇順ソートを、論理値０の時は
降順ソートを示している。第２図の例では。

４桁の整数を比較するのに。

ｉ）千の位は降順ソート。

■）百の位は比較の対象外 （即ちＣＭＰ信号が論理値Ｏ）。

ｉｉ）十の位は昇順ソ゛−ト。

１ｖ）−の位は降順ソート となるように指定した場合を示しており、比較結果の累
積は上位の桁はど優先度が高くなるように行っている。

比較器の出力であるＥＱおよびＧＴは、タイミングＩに
同期して入力されるＡとＢの比較結果であり、ＥＱは両
者が一致していることを、ＧＴはＡの方がＢより大きい
ことを現している。実際には、タイミング■で入力され
るデータから比較に必要な時間だけ遅延して出力される
が１図では簡略にタイミングＩで出力されるように表示
している０以上が比較結果累積回路の外部から与えられ
る信号であり、これらの信号によって、比較結果累積回
路の′動作が規定される。

ＦＥおよびＦＧは、第３図に示した従来のソート処理装
置における第１のフラグレジスタ６に相当するフリップ
フロップであり、ルーコード分の比較結果を累積するた
めのフラグである。初期状態では、フリップフロツプＦ
Ｅを論理値１に、フリップフロップＦＣを論理値０に設
定する。フリップフロップＦＥが論理値１の時は、レコ
ードの先頭（上位桁）から行った比較の結果、２つのレ
コードが一致していることを示している。フリップフロ
ップＦＧが論理値０の時は、レコードの先頭から現時点
までで比較器のＡ側から入力したデータ群の方がＢ側か
ら入力したデータ群より大きいことを示し、ＦＧが論理
値１の時は逆を示している。但し、ＦＧの値は、ＦＥが
論理値０の場合に有効であり、初期状態では、ＦＢ−１
かつＦＣ−〇であるから、レコードの先頭位置（当該レ
コードの比較を行う前）では１両者は等しいことを示し
ている。

第２図に於けるＦＥおよびＦＣの値を時間を追って説明
する。この例では、２つのレコードの千の位は共に１で
等しく、比較を行った後でもＦＢ−１，ＦＣ−０である
。２つのレコードの百の位は２と１で異なっているが、
百の位は比較の対象外（ＣＭＰ−０）となっていること
から、ＦＥ。

ＦＧの値は保存されている。十の位は、Ａ偏入力が３．
Ｂ個入力が２で比較の対象（ＣＭＰ＝１）であるから９
本来ではＡ側から入力されるレコードが大きい（ＦＧ＝
０）と判定されるべきであるが、この例では、十の位は
昇順になるように指定されているため、ＦＣ＝１となっ
ている。−の位は、４と５でＡ偏入力が小さいが、既に
十の位の比較でレコード間の大小関係が決定しているた
め。

−の位の比較結果は累積されない。以上をまとめると２
次表になる。

以上示したように、比較結果の累積はフリップフロップ
ＦＧによってなされ、フリップフロップＦＢはそれ以前
が一致しているかを示す補助をしている。ルーコード分
の累積が完了したＦＧの値は、レコードの区切りすなわ
ちＥＮＤ−１の時に。

第２のフリップフロップＦＳに移される。ＦＳの出力Ｆ
ＬＧが比較ユニットに格納された２つのレコードのいず
れを隣接する比較ユニットに転送するかを規定する。こ
の機構は、第３図に示した従来技術と同一であり、説明
は省略する。

本実施例では、第１図に示した構成の比較結果累積回路
を例として説明したが、比較器の出力に本実施例と同様
な比較結果を有効とするか否かの指定、及び、比較した
データを昇順になるようにソートするか降順になるよう
にソートするかの指定の少なくとも１つを指定可能とす
る機能を実現すれば充分であり、これらの機能を別の回
路構成で実現することも容易である。

〔発明の効果〕

以上述べた如（１本発明によれば、２個のレコードを入
力して格納する記憶手段と、格納された該２個のレコー
ドを複数個のデータに分割して該レコード記憶手段から
読みだして比較する比較手段と、該分割されたデータの
内で比較の対象であると指定されたデータに限定して、
昇順あるいは降順に指定されたソート条件に基づいて、
前記比較手段の出力に反転あるいは非反転操作を加えて
ルーコード分の比較結果を累積して、前記レコードの大
小関係を判定する比較結果累積手段とを少なくとも具備
した比較ユニットの１次元アレイからなり。

該比較結果累積手段の出力によって、前記２個の格納し
たレコードの何れかを隣接する比較ユニットに出力し、
同時に、他方の隣接する比較ユニットからレコードを入
力することによって、入力レコードを指定されたソート
条件に基づいてソートすることを特徴とするソート処理
装置を実現できるという顕著な効果を奏するものである
。

この結果２本発明のソート処理装置では、複数カラムか
らなるレコードをソート対象として、カラム毎に異なる
ソート条件を指定した複雑なソート処理を一度に処理す
ることができ、ソート処理時間を短縮できる。また、レ
コードからキーを抽出する前処理回路を簡略に構成でき
ることから。

装置の小型化にも効果がある。

【図面の簡単な説明】

第１図は１本発明のソート処理装置の一実施例を示す構
成図。 第２図は、第１図に示した比較結果累積回路の動作を説
明するタイミング図。 第３図は、従来のソート処理装置の一例を示す構成図で
ある。 ｌ・・・比較ユニット。 ２・・・ユニット間データ転送路。 ３・・・第１のメモリ。 ４・・・第２のメモリ。 ５・・・比較器。 ６・・・第１のフラグレジスタ。 ７・・・第２のフラグレジスタ。 １０・・・フリップフロップ回路。 １１・・・アンド回路。 １２・・・オア回路。 １３・・・インバータ回路。 １４・・・イクスクルーシブオア回路を示す論理シンボ
ルである。 特許出願人　日本電信電話株式会社

Claims (1)

1. 【特許請求の範囲】 ２個のレコードを入力して格納する記憶手段と、格納さ
   れた該２個のレコードを複数個のデータに分割して該レ
   コード記憶手段から読みだして比較する比較手段と、該
   分割されたデータの内で比較の対象であると指定された
   データに限定して、昇順あるいは降順に指定されたソー
   ト条件に基づいて、前記比較手段の出力に反転あるいは
   非反転操作を加えて１レコード分の比較結果を累積して
   、前記レコードの大小関係を判定する比較結果累積手段
   とを少なくとも具備した比較ユニットの１次元アレイか
   らなり、 該比較結果累積手段の出力によって、前記２個の格納し
   たレコードの何れかを隣接する比較ユニットに出力し、
   同時に、他方の隣接する比較ユニットからレコードを入
   力することによって、入力レコードを指定されたソート
   条件に基づいてソートすることを特徴としたソート処理
   装置。