(57)【要約】【課題】効率的なレコードの入力を実現することができるマージ処理装置、制御プログラム及びレコードマージ方法を提供すること【解決手段】本発明にかかるマージ処理装置１０は、ソートされた複数のレコードからなるレコード列が複数入力され、それぞれのレコード列を、少なくとも１のレコードを含むレコードブロックに分離しレコードブロックのそれぞれに含まれる予測用レコードを前方に位置するように順序を入れ替える配置変換部２０と、レコードブロックを記憶部２４へ入力する入力部２２と、予測用レコードに基づいて取得するレコード列を選択するレコード列選択部２６とを備える。入力部２２はレコードを順序が入れ替えられた順に取得し、全てのレコードを取得する前に取得済の予測用レコードを出力し、レコード列選択部２６は、予測用レコードに基づいて、次に取得するレコード列を選択する。【選択図】図１
2011233012.tif 000002
【特許請求の範囲】
【請求項１】
ソートされた複数のレコードから構成されるレコード列が複数入力され、前記入力されたそれぞれのレコード列を、少なくとも１のレコードを含むレコードブロックに分離し、当該レコードブロックのそれぞれに含まれる複数のレコードの最後方に配置されている予測用レコードを、現在配置されている位置よりも前方に位置するようにレコードの順序を入れ替える配置変換部と、
前記配置変換部から複数のレコードブロックを取得し、記憶部へ入力する入力部と、
前記複数のレコードブロックのそれぞれに含まれた前記予測用レコードの大小関係に基づいて、前記入力部が前記配置変換部から取得するレコード列を選択するレコード列選択部と、を備え、
前記入力部は、
前記レコードブロックに含まれるレコードのそれぞれを前記順序が入れ替えられたレコードの順に取得し、前記レコードブロックに含まれる全てのレコードを取得する前に、取得済の予測用レコードを前記レコード列選択部へ出力し、
前記レコード列選択部は、
前記入力部から出力された予測用レコードの入力に応じて、次に前記入力部が前記配置変換部から取得するレコード列を選択する処理を開始するマージ処理装置。
【請求項２】
前記配置変換部は、
前記予測用レコードを前記レコードブロックの先頭に位置するように、前記レコードの順序を入れ替える、請求項１記載のマージ処理装置。
【請求項３】
前記入力部は、
前記レコードの順序が入れ替えられたレコードブロックの順序を元に戻して、前記順序が元に戻されたレコードブロックを前記記憶部へ入力する、請求項１又は２に記載のマージ処理装置。
【請求項４】
ソートされた複数のレコードから構成されるレコード列が複数入力され、当該前記入力されたそれぞれのレコード列を少なくとも１のレコードを含む複数のレコードブロックに分離する分離部と、
前記分離部に後から入力された前記レコードブロックから順に前記レコードブロックを取得し、記憶部へ入力するとともに、前記レコードブロック内で最も前方に位置するブロックを予測用レコードとして取り出す入力部と、
前記複数のレコードブロックのそれぞれに含まれた前記予測用レコードの大小関係に基づいて、前記入力部が前記配置変換部から取得するレコードブロックを選択するレコード列選択部と、
前記レコード列のソート順序と逆のソート順序に従い記憶部からレコードを順に取り出して出力する整列出力部とを備え、
前記入力部は、
前記レコードブロックのレコードを全て取得する前に、前記予測用レコードを前記レコード列選択部へ出力し、
前記レコード列選択部は、
前記入力部から出力された予測用レコードに基づいて、次に前記入力部が前記配置変換部から取得するレコード列を選択する処理を開始するマージ処理装置。
【請求項５】
ソートされた複数のレコードから構成されるレコード列が複数入力され、前記入力されたそれぞれのレコード列を、少なくとも１のレコードを含むレコードブロックに分離し、当該レコードブロックのそれぞれに含まれる複数のレコードの最後方に配置されている第１の予測用レコードを、現在配置されている位置よりも前方に位置するようにレコードの順序を入れ替える配置変換部と、
前記配置変換部から複数のレコードブロックを取得し、第１の記憶部へ入力する第１の入力部と、
前記レコード列のソート順序と同じソート順序に従い前記第１の記憶部からレコードを順に取り出して出力する第１の整列出力部と、
前記配置変換部へ後から入力された前記レコードブロックから順に前記レコードブロックを取得し、第２の記憶部へ入力するとともに、前記レコードブロック内で最も前方に配置されているブロックを第２の予測用レコードとして取り出す第２の入力部と、
前記レコード列のソート順序と逆のソート順序に従い前記第２の記憶部からレコードを順に取り出して出力する第２の整列出力部と、
前記複数のレコードブロックのそれぞれに含まれた前記第１の予測用レコードの大小関係に基づいて、前記第１の入力部が前記配置変換部から取得するレコード列を選択する第１のレコード列選択部と、
前記複数のレコードブロックのそれぞれに含まれた前記第２の予測用レコードの大小関係に基づいて、前記第２の入力部が前記配置変換部から取得するレコード列を選択する第２のレコード列選択部と、を備え、
前記第１及び第２の入力部は、
前記レコードブロックのレコードを全て取得する前に、前記第１及び第２の予測用レコードを前記第１及び第２のレコード列選択部へ出力し、
前記第１及び第２のレコード列選択部は、
前記第１及び第２の入力部から出力された第１及び第２の予測用レコードに基づいて、次に前記第１及び第２の入力部が前記配置変換部から取得するレコード列を選択する処理を開始するマージ処理装置。
【請求項６】
前記配置変換部は、
前記レコードブロックに含まれるレコードの前半の列と、残りのレコードを逆順に並び替えたレコードの列とを交互に配置する請求項５に記載のマージ処理装置。
【請求項７】
複数のレコードから構成されるレコード列を複数格納する記憶部と、前記記憶部に格納されたレコードを取り出してソート規則に従う順序に並び変えてレコードを出力する整列出力部と、複数のレコード列が少なくとも１のレコードを含むレコードブロックに分離され、当該レコードブロックのそれぞれにおいて外部からの入力時に最後方に配置されている予測用レコードに基づいて、次に入力するレコード列を選択するレコード列選択部とを含むマージ処理ユニットに、前記レコード列を入力する処理をコンピュータに実行させる制御プログラムであって、
外部から前記レコードブロックを複数取得するするステップと、
前記取得された複数のレコードブロックの最後方に配置されている予測用レコードを、現在配置されている位置よりも前方に位置するようにレコードの順序を入れ替えるステップと、
前記順序が入れ替えられたレコードの順に前記レコードを前記マージ処理ユニットに入力するステップと、をコンピュータに実行させる制御プログラム。
【請求項８】
複数のレコードから構成されるレコード列を複数格納する記憶部と、前記記憶部に格納されたレコードを取り出してソート規則に従う順序に並び変えてレコードを出力する整列出力部と、複数のレコード列が少なくとも１のレコードを含むレコードブロックに分離され、当該レコードブロックのそれぞれにおいて外部からの入力時に最後方に配置されている予測用レコードに基づいて、次に入力するレコード列を選択するレコード列選択部とを含むマージ処理ユニットに、前記レコード列を入力する処理をコンピュータに実行させる制御プログラムであって、
外部から前記レコードブロックを複数取得するするステップと、
前記取得した複数のレコードブロックに含まれるレコードをソートするステップと、
前記ソートされた複数のレコードブロックの最後方に配置されている予測用レコードを、現在配置されている位置よりも前方に位置するようにレコードの順序を入れ替えるステップと、
前記順序が入れ替えられたレコードの順に前記レコードを前記マージ処理ユニットに入力するステップと、をコンピュータに実行させる制御プログラム。
【請求項９】
ソートされた複数のレコードから構成されるレコード列が複数入力され、前記入力されたそれぞれのレコード列を、少なくとも１のレコードを含むレコードブロックに分離するステップと、
前記複数のレコードブロックのそれぞれに含まれる複数のレコードの最後方に配置されている予測用レコードを、現在配置されている位置よりも前方に位置するようにレコードの順序を入れ替えるステップと、
前記レコードブロックに含まれるレコードのそれぞれを前記順序が入れ替えられたレコードの順に取得するとともに、取得済みの予測用レコードを出力するステップと、
前記出力された予測用レコードの入力に応じて、次に入力されるレコード列を選択する処理を開始するステップと、を備えるレコードマージ方法。
【請求項１０】
複数のレコードから構成されるレコード列が複数入力され、前記入力されたそれぞれのレコード列を、少なくとも１のレコードを含むレコードブロックに分離するステップと、
前記レコードブロックに含まれるレコードをソートするステップと、
前記複数のレコードブロックのそれぞれに含まれる複数のレコードの最後方に配置されている予測用レコードを、現在配置されている位置よりも前方に位置するようにレコードの順序を入れ替えるステップと、
前記レコードブロックに含まれるレコードのそれぞれを前記順序が入れ替えられたレコードの順に取得するとともに、取得済みの予測用レコードを出力するステップと、
前記出力された予測用レコードの入力に応じて、次に入力されるレコード列を選択する処理を開始するステップと、を備えるレコードマージ方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はマージ処理装置、制御プログラム及びレコードマージ方法に関し、特に予測による手法を用いたマージ処理装置、マージ処理装置を動作させる制御プログラム、及び、マージ処理装置を用いたレコードマージ方法に関する。
【背景技術】
【０００２】
データベース等の情報処理システムにおいて、ソートは、重要な基本処理であり、ソートを高速に処理する技術が求められている。ソートの一手法であるマージソート法は、既に得られている短いソート済みレコード列を結合して、より長いソート済みレコード列を得るマージ処理を段階的に繰り返す。これにより、多数のレコードを集めたデータのソートが可能となる。
【０００３】
図１８を用いて、一般的に用いられるマージ処理装置の構成例について説明する。説明に用いる用語は、非特許文献１を参照し、次のように定義する。ソートされるデータの並び替え単位を「レコード（record）」とし、複数個のレコードをソート順序に従い並び変えられたものを「連（run）」とする。マージする連の個数を２以上の整数Ｐを用いて表す。各々の連には、１からＰまでの番号（連番号）がつけられている。
【０００４】
マージ処理装置１００は、外部の入力供給部１５０からマージするＰ個の連のレコードデータを入力し、内部でマージ処理を行った後、得られたマージ済み連のレコードを外部の出力記憶部１６０へ出力する。マージ処理装置１００は、入力供給部１５０からレコードが入力される入力部１１０と、入力部１１０に入力されたレコードを格納する一時記憶部１２０と、一時記憶部１２０内のレコードを１個ずつ読み出し、ソート順序に従い並び替えて外部の出力記憶部１６０に出力する整列出力部１４０と、を備えている。さらに、入力部が入力する連の選択を行う入力連選択部１３０を備えている。
【０００５】
ここで、一時記憶部１２０は、マージされる連のレコードを全て格納するだけの容量を備えていない。そのため、一時記憶部１２０は、少しずつレコードデータを取得しながらマージ処理を進行させる。一時記憶部１２０へのレコード入力処理は、１個または複数のレコードの集まりであるレコードブロックを一単位として行われる。さらに入力部１１０は、Ｐ個の連で共有されている。そのため、一時記憶部１２０は、Ｐ個の連からレコードを同時に入力することはできず、入力する連を切り替えながら入力を進める。具体例としては、マージ処理装置１００にメモリバスを介して接続されたＳＤＲＡＭメモリからバースト転送モードを利用してレコードのデータを読み出す場合がある。このような事例を記載した文献として特許文献１がある。あるいは別の例として、マージ処理装置１００に接続されたディスク装置からレコードのデータを所定長のブロック単位でまとめて入力する場合、イーサネット（登録商標）で接続されたストレージサーバからレコードを一定長のレコードブロック単位で読み出す場合などがある。
【０００６】
マージ処理中に入力部１１０から一時記憶部１２０へ出力されるレコードブロックの選択は、入力連選択部によって行われる。整列出力部１４０の動作を停止させることなくマージ処理を高速に進行させるためには、Ｐ個の連の全てに対して一時記憶部１２０におけるレコード格納個数が空にならないよう十分な速度でレコードが一時記憶部１２０に入力される必要がある。しかし、各々の連に用いられるバッファからレコードが出力される速度は入力に依存して変化する。そのため、入力連選択部１３０は、一時記憶部のレコード格納状態を観測しながら入力連の決定を行う。この入力連の選択制御において有効な技法として、非特許文献１、Ｐ３０７及び非特許文献２、ＡＰＰＥＮＤＩＸ２において、予測(forecast)に基づく選択手法が考案されている
【０００７】
ここで、非特許文献１及び非特許文献２連番号に開示されている予測（forecast）について具体的に説明する。一時記憶部１２０の第iのバッファに対して、第iの連からその時点で一時記憶部１２０に入力し終えた最後のレコードを第iの連の最後方レコードとする。予測に基づく手法では、入力選択部１３０は、Ｐ個ある最後方レコードの中からソート順序が最も前方になるレコードを選び出し、そのレコードを供給した連を、次にレコードを入力する連として選択する。このように選択された連は、その時点で後続のレコード供給を最も早く必要とする連を示している。そのため、予測に基づく入力連の選択手法は、一時記憶部１２０に必要なレコード記憶領域の容量や、マージ処理遅延を減らす上で好ましい手法である。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開平５−２９８０６９号公報
【非特許文献】
【０００９】
【非特許文献１】The Art of Computer Programming Volume 3 Sorting and Searching Second Edition 日本語版、Donald E.Knuth (著) 、有澤誠 (監訳)、和田英一 (監訳) 、アスキー、2006年
【非特許文献２】E.H. Friend, "Sorting on Electronic Computer Systems," J. ACM, vol. 3, no. 3, 1956, pp. 134-168.
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかし、マージ処理装置において予測に基づく入力連選択を用いる場合、予測自体に要する処理時間や、入力先の連番号を決定してから実際にレコードデータが入力されるまでの遅延時間が大きいときに、レコード入力処理の実行が効率良く行われない。さらに、マージ処理速度の低下が引き起こされる問題がある。この問題について、図１９を用いて説明する。図１９は、入力供給部１５０に対する入力要求処理と、入力供給部１５０からレコードが入力される処理と、入力連を決定する処理と、の３つの実行順序関係を示している。本図において、入力供給部１５０にレコード供給を要求してからレコードデータが入力されるまで３レコード分の遅延があるとする。また、入力単位であるレコードブロックは、８個のレコードから構成され、それらがソート規則に従う順序で並んでいる。予測に基づいて入力連を選択する場合、これらのレコードの中で最後に入力されたものを用いる。そのため、図１９に示すように、入力連の選択処理中と入力遅延の間、レコード入力が全く行われず、レコード入力処理の効率が悪いという問題がある。
【００１１】
この問題を解決するためには、冗長なバッファを用意していくつかのレコードブロックを先読みする手法や、全てのレコード入力を待たずに投機的に次の入力連を予測選択する手法などが考えられる。しかし、必要なバッファ容量と処理遅延時間を増加させる問題や、予測が外れた場合に時間ペナルティが生じるため、妥当ではない。
【００１２】
本発明は、このような問題を解決するためになされたものであり、効率的なレコードの入力を実現することができるマージ処理装置、制御プログラム及びレコードマージ方法を提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明の第１の態様にかかるマージ処理装置は、ソートされた複数のレコードから構成されるレコード列が複数入力され、前記入力されたそれぞれのレコード列を、少なくとも１のレコードを含むレコードブロックに分離し、当該レコードブロックのそれぞれに含まれる複数のレコードの最後方に配置されている予測用レコードを、現在配置されている位置よりも前方に位置するようにレコードの順序を入れ替える配置変換部と、前記配置変換部から複数のレコードブロックを取得し、記憶部へ入力する入力部と、前記複数のレコードブロックのそれぞれに含まれた前記予測用レコードの大小関係に基づいて、前記入力部が前記配置変換部から取得するレコード列を選択するレコード列選択部と、を備え、前記入力部は、前記レコードブロックに含まれるレコードのそれぞれを前記順序が入れ替えられたレコードの順に取得し、前記レコードブロックに含まれる全てのレコードを取得する前に、取得済の予測用レコードを前記レコード列選択部へ出力し、前記レコード列選択部は、前記入力部から出力された予測用レコードの入力に応じて、次に前記入力部が前記配置変換部から取得するレコード列を選択する処理を開始するものである。
【００１４】
本発明の第２の態様にかかるマージ処理装置は、ソートされた複数のレコードから構成されるレコード列が複数入力され、当該前記入力されたそれぞれのレコード列を少なくとも１のレコードを含む複数のレコードブロックに分離する分離部と、前記分離部に後から入力された前記レコードブロックから順に前記レコードブロックを取得し、記憶部へ入力するとともに、前記レコードブロック内で最も前方に位置するブロックを予測用レコードとして取り出す入力部と、前記複数のレコードブロックのそれぞれに含まれた前記予測用レコードの大小関係に基づいて、前記入力部が前記配置変換部から取得するレコードブロックを選択するレコード列選択部と、前記レコード列のソート順序と逆のソート順序に従い記憶部からレコードを順に取り出して出力する整列出力部とを備え、前記入力部は、前記レコードブロックのレコードを全て取得する前に、前記予測用レコードを前記レコード列選択部へ出力し、前記レコード列選択部は、前記入力部から出力された予測用レコードに基づいて、次に前記入力部が前記配置変換部から取得するレコード列を選択する処理を開始するものである。
【００１５】
本発明の第３の態様にかかるマージ処理装置は、ソートされた複数のレコードから構成されるレコード列が複数入力され、前記入力されたそれぞれのレコード列を、少なくとも１のレコードを含むレコードブロックに分離し、当該レコードブロックのそれぞれに含まれる複数のレコードの最後方に配置されている第１の予測用レコードを、現在配置されている位置よりも前方に位置するようにレコードの順序を入れ替える配置変換部と、前記配置変換部から複数のレコードブロックを取得し、第１の記憶部へ入力する第１の入力部と、前記レコード列のソート順序と同じソート順序に従い前記第１の記憶部からレコードを順に取り出して出力する第１の整列出力部と、前記配置変換部へ後から入力された前記レコードブロックから順に前記レコードブロックを取得し、第２の記憶部へ入力するとともに、前記レコードブロック内で最も前方に配置されているブロックを第２の予測用レコードとして取り出す第２の入力部と、前記レコード列のソート順序と逆のソート順序に従い前記第２の記憶部からレコードを順に取り出して出力する第２の整列出力部と、前記複数のレコードブロックのそれぞれに含まれた前記第１の予測用レコードの大小関係に基づいて、前記第１の入力部が前記配置変換部から取得するレコード列を選択する第１のレコード列選択部と、前記複数のレコードブロックのそれぞれに含まれた前記第２の予測用レコードの大小関係に基づいて、前記第２の入力部が前記配置変換部から取得するレコード列を選択する第２のレコード列選択部と、を備え、前記第１及び第２の入力部は、前記レコードブロックのレコードを全て取得する前に、前記第１及び第２の予測用レコードを前記第１及び第２のレコード列選択部へ出力し、前記第１及び第２のレコード列選択部は、前記第１及び第２の入力部から出力された第１及び第２の予測用レコードに基づいて、次に前記第１及び第２の入力部が前記配置変換部から取得するレコード列を選択する処理を開始するものである。
【００１６】
本発明の第４の態様にかかる制御プログラムは、複数のレコードから構成されるレコード列を複数格納する記憶部と、前記記憶部に格納されたレコードを取り出してソート規則に従う順序に並び変えてレコードを出力する整列出力部と、複数のレコード列が少なくとも１のレコードを含むレコードブロックに分離され、当該レコードブロックのそれぞれにおいて外部からの入力時に最後方に配置されている予測用レコードに基づいて、次に入力するレコード列を選択するレコード列選択部とを含むマージ処理ユニットに、前記レコード列を入力する処理をコンピュータに実行させる制御プログラムであって、外部から前記レコードブロックを複数取得するするステップと、前記取得された複数のレコードブロックの最後方に配置されている予測用レコードを、現在配置されている位置よりも前方に位置するようにレコードの順序を入れ替えるステップと、前記順序が入れ替えられたレコードの順に前記レコードを前記マージ処理ユニットに入力するステップと、をコンピュータに実行させるものである。
【００１７】
本発明の第５の態様にかかるレコードマージ方法は、ソートされた複数のレコードから構成されるレコード列が複数入力され、前記入力されたそれぞれのレコード列を、少なくとも１のレコードを含むレコードブロックに分離するステップと、前記複数のレコードブロックのそれぞれに含まれる複数のレコードの最後方に配置されている予測用レコードを、現在配置されている位置よりも前方に位置するようにレコードの順序を入れ替えるステップと、前記レコードブロックに含まれるレコードのそれぞれを前記順序が入れ替えられたレコードの順に取得するとともに、取得済みの予測用レコードを出力するステップと、前記出力された予測用レコードの入力に応じて、次に入力されるレコード列を選択する処理を開始するステップと、を備えるものである。
【発明の効果】
【００１８】
本発明により、効率的なレコードの入力を実現することができるマージ処理装置、制御プログラム及びレコードマージ方法を提供することができる。
【図面の簡単な説明】
【００１９】
【図１】実施の形態１にかかるマージ処理装置の構成図である。
【図２】実施の形態１にかかるマージ処理装置の構成図である。
【図３】実施の形態１にかかるレコードの並び替えを示す図である。
【図４】実施の形態１にかかる予測処理のフローチャートである。
【図５】実施の形態１にかかるレコード入力要求の動作を示す図である。
【図６】実施の形態２にかかるマージ処理装置の構成図である。
【図７】実施の形態２にかかるレコードの並び替えを示す図である。
【図８】実施の形態３にかかるマージ処理装置の構成図である。
【図９】実施の形態３にかかるレコードの並び替えを示す図である。
【図１０】実施の形態３にかかるレコードの並び替えを示す図である。
【図１１】実施の形態４にかかるレコードの並び替えを示す図である。
【図１２】実施の形態４にかかるレコードの並び替えを示す図である。
【図１３】実施の形態５にかかるマージ処理装置の構成図である。
【図１４】実施の形態６にかかるマージ処理装置の構成図である。
【図１５】実施の形態６にかかるマージ処理装置の構成図である。
【図１６】実施の形態７にかかるソート処理装置の構成図である。
【図１７】実施の形態８にかかるソート処理装置の構成図である。
【図１８】一般的なマージ処理装置の構成図である。
【図１９】一般的なマージ処理装置におけるレコード入力要求の動作を示す図である。
【発明を実施するための形態】
【００２０】
（実施の形態１）
以下、図面を参照して本発明の実施の形態について説明する。図１を用いて本発明の実施の形態１にかかるマージ処理装置の構成例について説明する。マージ処理装置１０は、配置変換部２０と、入力部２２と、記憶部２４と、レコード列選択部２６と、を備えている。
【００２１】
配置変換部２０は、ソートされた複数のレコードから構成されるレコード列が複数入力される。さらに、配置変換部２０は、入力された複数のレコード列を、少なくとも１のレコードを含むレコードブロックに分離し、それぞれのレコードブロックに含まれる複数のレコードの最後方に配置されている予測用レコードを、現在配置されている位置よりも前方に位置するようにレコードの順序を入れ替える。
【００２２】
入力部２２は、配置変換部２０から複数のレコードブロックを取得し、記憶部２４へ入力する。入力部２２は、配置変換部２０から、レコードブロックに含まれるレコードのそれぞれを順序が入れ替えられたレコードの順に取得する。これにより、入力部２２は、レコードブロックに含まれる全てのレコードを取得する前に、予測用レコードを取得することができる。入力部２２は、レコードブロックに含まれる全てのレコードを取得する前に、取得済みの予測用レコードを、レコード列選択部２６へ出力する。
【００２３】
レコード列選択部２６は、複数のレコードブロックのそれぞれに含まれた予測用レコードに基づいて、入力部２２が配置変換部２０から取得するレコード列を選択する。レコード列選択部２６によって選択されたレコード列は、入力部２２における現在のレコード列の取得が完了後に、入力部２２によって配置変換部２０から取得される。
【００２４】
記憶部２４は、入力部２２から入力されたレコード列を格納する。
【００２５】
以上説明したように、図１において説明したマージ処理装置１０を用いることにより、入力部２２は、レコードブロックに含まれるレコードを全て取得する前に、予測用レコードを取得することができる。これにより、入力部２２は、レコードブロックに含まれるレコードを全て取得する前に、予測用レコードをレコード列選択部２６へ出力することができる。よって、レコード列選択部２６は、出力された予測用レコードに基づいて、入力部２２が配置変換部２０からレコードブロックに含まれるレコードを全て取得する前に、次に入力部２２が配置変換部２０から取得するレコード列を選択する処理を開始することができる。そのため、配置変換部から入力部にレコード列が入力されてから、次のレコード列が入力されるまでの時間を短縮することができるため、レコード列の効率的な入力処理を実現することができる。
【００２６】
続いて、図２を用いて本発明の実施の形態１にかかるマージ処理装置の詳細な構成例について説明する。マージ処理装置１０は、配置変換部２０と、入力部２２と、記憶部２４と、レコード列選択部２６と、入力記憶部３０と、整列出力部３２と、を備えている。記憶部２４は、第１のバッファ４１と、第２のバッファ４２と、第Ｐのバッファ４３と、を有している。また、マージ処理装置１０は、入力供給部５０と、出力記憶部６０とに接続されている。図１と同様の機能を有するマージ処理装置１０の構成要素は、図１と同様の符号を付して説明する。また、以下の説明において用いる連（run）という用語は、上述したレコード列と同様の意味を有する。
【００２７】
マージ処理装置１０は、外部の入力供給部５０から、マージするＰ個の連のレコードデータが入力される。各々の連は、１からＰまでの番号（連番号）を用いて識別される。マージ処理装置１０は、装置内部においてＰ個の連のマージ処理を行った後、得られたマージ済み連のレコードを外部の出力記憶部６０へ出力する。
【００２８】
配置変換部２０は、入力供給部５０から供給されるレコードを取得し、レコードの配置を並び替える。例えば、配置変換部２０は、連に含まれる複数のレコードを、予め定められたレコード数を有するレコードブロックに区切り、レコードブロックの最後方に配置されているレコード、つまり予測用レコードを、先頭に位置するように配置する。
【００２９】
入力記憶部３０は、配置変換部２０からレコードが入力され、並び替えられたレコードをレコードブロック単位に記憶する。
【００３０】
入力部２２は、入力記憶部３０から、配置変換部２０によって順序が入れ替えられたレコードの順にレコードを取得する。入力部２２は、レコード列選択部２６によって選択された連から、レコードブロック単位にレコードを取得する。入力部２２は、予測用レコードを取得すると、レコードブロックに含まれる全てのレコードを取得する前に、取得した予測用レコードをレコード列選択部２６へ出力する。さらに、入力部２２は、取得したレコードを、並び替え前のソート順序に復元して、記憶部２４へ出力する。
【００３１】
記憶部２４は、連ごとにレコードを格納するために複数のバッファを有している。例えば、マージ処理装置１０にＰ個の連が入力される場合、連１を格納するバッファを第１のバッファ４１とし、連２を格納するバッファを第２のバッファ４２とし、連Ｐを格納するバッファを第Ｐのバッファ４３とする。記憶部２４は、連ごとに、復元されたレコードの順にそれぞれのバッファへレコードを格納する。
【００３２】
整列出力部３２は、記憶部２４内のレコードをソート順序に従いながら読み出し、外部の出力記憶部６０へ出力する。例えば、整列出力部３２は、それぞれのバッファの先頭に位置するレコードの値が一番小さいレコードを読み出す。これにより、整列出力部３２は、値の小さいレコードから順にレコードをソートして、複数の連をマージすることができる。
【００３３】
レコード列選択部２６は、入力部２２が入力記憶部３０から取得するレコードブロックを、予測に基づく手法により選択する。以下に、予測に基づく手法について説明する。
【００３４】
レコード列選択部２６に対しては、入力部２２が記憶部２４へレコードブロックを入力する際に、入力部２２から、それぞれのレコードブロックに含まれる予測用レコードが出力され、レコード列選択部２６は、最後に出力された予測用レコードをそれぞれの連ごとに１つずつ、合計でＰ個保持している。レコード列選択部２６は、Ｐ個ある予測用レコードの中から、ソート順序が最も前方になるレコード、つまり、値が最も小さいレコードを抽出する。レコード列選択部２６は、抽出したレコードを供給した連を、次にレコードを入力する連として選択する。このように選択された連は、その時点で後続のレコード供給を最も早く必要とする連を示している。レコード列選択部２６は、入力部２２及び入力記憶部３０の少なくとも一方に対して、選択した連を通知する。
【００３５】
入力記憶部３０は、レコード列選択部２６によって選択された連が通知されると、選択された連に含まれるレコードブロックを入力部２２へ出力する。もしくは、入力部２２は、レコード列選択部２６によって選択された連が通知されると、入力記憶部３０に対して選択された連に含まれるレコードブロックの出力を要求してもよい。
【００３６】
入力部２２は、入力記憶部３０からレコードブロックを取得すると、予測用レコードをレコード列選択部２６へ出力し、レコード列選択部２６は、取得した予測用レコードと、保持している他の連の予測用レコードとを用いて、値が最も小さいレコードを抽出する。
【００３７】
以上説明したように、入力部２２が入力記憶部３０から取得するレコードブロックは、予測に基づく手法により選択される。
【００３８】
次に、マージ処理装置１０内の処理動作のタイミングについて説明する。ここで、マージ処理装置１０内の、入力部２２と、記憶部２４と、整列出力部３２と、入力連選択部２６とをまとめてマージ処理ユニットとする。マージ処理が開始されると各部において必要な初期化が行われる。その後、配置変換部２０は、外部の入力供給部５０からのレコードデータ入力を待機する。配置変換部２０は、レコードデータの入力開始とともにレコードデータの並び替えと、入力記憶部に対するレコードデータの格納を開始する。配置変換部２０は、全てのレコードデータの入力を終えるまで処理を続ける。その途中、入力記憶部３０に十分な量のレコードデータが蓄積されると、マージ処理ユニットは、マージ処理を開始する。マージ処理ユニットは、全てのレコードを外部の出力記憶部６０に出力し終えるまで処理を続ける。配置変換部２０とマージ処理ユニットの動作タイミングとは一定の時間差を保ちながら同期して動作しても構わないし、独立したタイミングにより動作しても構わない。ただし、処理すべきレコードデータが未入力である場合、マージ処理ユニットは、処理を行わず待機する。あるいは、入力記憶部３０が、全てのレコードデータを記憶可能な容量を持っている場合、マージ処理ユニットは、配置変換部２０から入力されるレコードデータの蓄積が全て完了してから、処理を開始しても良い。
【００３９】
続いて、図３を用いて本発明の実施の形態１にかかる、レコードの並び替え処理について説明する。図３におけるａ１、ａ２、ａ３・・・は、外部から供給された任意の連のレコードを表し、添字の番号はソート規則に従う順序を表す。各々の連のレコードは、図３(ａ)で表されるように、ソート順序に従い配置変換部２０に供給される。配置変更部２０は、これらのレコードを、ａ１〜ａ８、ａ９〜ａ１６、ａ１７〜ａ２４、のように８個のレコードを有するレコードブロックに区切る。さらに、配置変換部２０は、レコードブロック内のレコードの配置順序を、図３（ｂ）で示されるように、それぞれのレコードブロックの最後方レコード（予測用レコード）を、レコードブロックの先頭に位置するように、並び替える。配置変換部２０は、このようにレコードの配置が変更された連を、レコードブロック単位に入力記憶部３０へ格納する。
【００４０】
図３（ｂ）には、各レコードブロック内において最後方のレコード（ａ８、ａ１６、ａ２４・・・）が先頭に配置され、その他のレコードは一つ位置を後ろにずらして格納される様子が示されている。入力記憶部３０から入力部２２へのレコードデータの供給はレコードブロック単位で行われるが、レコードブロック内のレコードはこの並び替えられた順序により供給される。
【００４１】
また、入力部２２は、配置変換部２０により並び替えられたレコードブロック内のレコード配置を、元の配置順に戻しながらレコードを記憶部２４へ入力する。これにより、ソートされた順序と異なる配置によりレコードが入力されても、記憶部２４内ではソートされた順序によりレコードが格納される。そのため、整列出力部３２は、それぞれのバッファの先頭レコードを比較して抽出することにより、マージ処理を実行することができる。
【００４２】
続いて、図４を用いて本発明の実施の形態１にかかるマージ処理の流れについて説明する。はじめに、マージ処理ユニットにおいてマージ処理が開始されると、レコード列選択部２６は、保持する変数を初期化する（Ｓ１）。例えば、レコード列選択部２６は、最小の値を有する予測用レコードの連番号及び予測用レコードの最小値を初期化する。
【００４３】
次に、記憶部２４は、連ｉのバッファに空きがあるか否かを判定する（Ｓ２）。連ｉのバッファに空きがあると判定された場合、レコード列選択部２６は、連ｉの予測用レコードが入力済みの予測用レコードの中で最小か否かを判定する（Ｓ３）。レコード列選択部２６は、連ｉの予測用レコードが最小であると判定した場合、連番号ｉ及び予測用レコードの最小値を示す変数を更新する（Ｓ４）。次に、連ｉ＋１についても、同様にステップＳ２乃至４の処理を繰り返し実行する（Ｓ５）。
【００４４】
ステップＳ２において、記憶部２４が、連ｉのバッファに空きがないと判定した場合、又はステップＳ３において、レコード列選択部２６が、連ｉの予測用レコードが最小ではないと判定した場合、ステップＳ５の処理へ移行する。次に、レコード列選択部２６は、全ての連について、ステップＳ２以降の処理を実行したか否かを判定する（Ｓ６）。レコード列選択部２６によって、全ての連がステップＳ２以降の処理を実行していないと判定された場合、ステップＳ２の処理へ移行する。レコード列選択部２６によって、全ての連がステップＳ２以降の処理を実行したと判定された場合、記憶部２４が有するバッファに空きのあるバッファがあったか否かを判定する（Ｓ８）。レコード列選択部２６は、空きのあるバッファがあったと判定した場合、入力部２２及び入力記憶部３０の少なくともどちらか一方に、更新された連番号を通知し、レコードの入力要求を行う（Ｓ９）。レコード列選択部２６は、空きのあるバッファがないと判定した場合、処理を終了する。
【００４５】
以上説明したように、本発明の実施の形態１にかかるマージ処理装置を用いることにより、入力記憶部３０から入力部２２に対するレコードブロックの入力処理を連続的に実行することができる。図５を用いて、本発明の実施の形態１における効果を説明する。入力部２２は、配置変換部２０によって順序が並び替えられたレコードを取得する。例えば、配置変換部２０によって予測用レコードがレコードブロックの先頭に位置するように配置された場合、入力部２２は、レコードブロックの全てのレコードを取得する前に、予測用レコードをレコード列選択部２６へ出力することができる。これにより、レコード列選択部２６は、入力部２２が全てのレコードを取得する前に、次に入力する連を選択し、入力部２２及び入力記憶部３０の少なくとも一方にレコード入力要求を行う。これにより、レコード入力要求が行われてから、入力部２２が実際に入力記憶部３０からレコードを取得するまでの遅延時間を隠蔽する時間的余裕がある。そのため、入力記憶部３０は、入力部２２に対して、連続的にレコードの入力処理を実行することができる。
【００４６】
（実施の形態２）
続いて、図６を用いて本発明の実施の形態２にかかるマージ処理装置の構成例について説明する。図６のマージ処理装置１０は、図２のマージ処理装置と比較して、配置変換部２０が無い点において異なる。図６のその他の構成は、図２と同様であるため、図２と同様の符号を用いて説明する。
【００４７】
入力記憶部３０は、入力供給部５０から、マージされる全ての連のレコードを記憶できるだけの容量を有する。そのため、入力記憶部３０が、入力供給部５０から全てのレコードデータを入力されると、マージ処理ユニットによるマージ処理が開始される。入力記憶部３０は、入力供給部５０から入力されるレコードのソート順序を保ちながらレコードを格納する。ここで、ａ１、ａ２、・・・と、値が小さいレコードから入力される順序を昇順とする。これと逆の順序を降順とする。入力記憶部３０は、入力供給部５０から入力されたレコードデータを、少なくとも１のレコードを含むレコードブロックに分離する。また、ａ１〜ａ８のレコードを有するレコードブロックをレコードブロック１とし、ａ９〜ａ１６のレコードを有するレコードブロックをレコードブロック２とし、ａ４１〜ａ４８のレコードを有するレコードブロックをレコードブロック６とする。ａ１７〜ａ４１は、レコードブロック３〜５が設定される。図７（ａ）に、レコードブロック内のレコード数を８個として、４８個のレコードを持つ連を入力記憶部３０に格納した場合の配置例を示す。
【００４８】
入力部２２は、本発明の実施の形態１と異なり、入力記憶部３０から、レコードブロック６、レコードブロック５、・・・レコードブロック１の順（降順）にレコードブロックを取得する。ただし、入力部２２は、レコードブロック内のレコードを昇順に取得する。さらに、入力部２２は、レコードブロック内のレコードを全て降順に並べ替えながら、取得したレコードを記憶部２４へ格納する。図７（ｂ）は、入力部２２が入力記憶部３０から取得するレコードの順序と、記憶部２４へ格納するレコードの順序を示している。
【００４９】
ここで、レコード列選択部２６が予測のために用いる予測用レコードは、ソート順序を降順とした時のレコードブロックの最後方レコード、すなわちソート順序を昇順とした時のレコードブロックの最前方レコードとする。入力部２２は、レコードブロック内のレコードを昇順に取得する。そのため、予測用レコードは、レコードブロック内のレコードの中で最初に入力部２２に取得される。入力部２２は、予測用レコードを取得すると、レコードブロック内のすべてのレコードが入力される前に、取得した予測用レコードをレコード列選択部２６へ出力する。これにより、レコード列選択部２６は、入力部２２がレコードブロック内の全てのレコードを取得する前に、次に取得するレコードブロックの連を決定する処理を開始する。なお、本発明の実施の形態２においては、レコード列選択部２６は、予測用レコードの中で最大の値が設定されている予測用レコードの連を選択する。
【００５０】
以上説明したように、本発明の実施の形態２にかかるマージ処理装置においては、本発明の第１の実施の形態にかかるマージ処理装置と同様のタイミングにより、入力部２２が入力記憶部３０からレコードを取得することができる。よって、マージ処理ユニットの可動効率を高めるとともに、マージ処理の処理速度を高めることができる。
【００５１】
（実施の形態３）
続いて、図８を用いて本発明の実施の形態３にかかるマージ処理装置の構成例について説明する。本発明の実施の形態３にかかるマージ処理装置は、本発明の実施の形態１及び２を組み合わせた構成を有している。入力部２２と、記憶部２４と、レコード列選択部２６と、整列出力部３２と、を昇順マージ処理ユニットとし、昇順マージ処理ユニットは、本発明の実施の形態１にかかるマージ処理ユニットと同様の動作をする。また、入力部２２＿１と、記憶部２４＿１と、レコード列選択部２６＿１と、整列出力部３２＿１と、を降順マージ処理ユニットとし、降順マージ処理ユニットは、本発明の実施の形態２にかかるマージ処理ユニットと同様の動作をする。
【００５２】
入力記憶部３０は、本発明の実施の形態２にかかるマージ処理装置と同様に、マージされる全ての連のレコードデータを記憶できるだけの容量を有する。そのため、入力記憶部３０に、配置変換部２０から全てのレコードデータが入力されてから昇順マージ処理ユニット及び降順マージ処理ユニットによるマージ処理が開始される。入力供給部５０から入力されるレコードは、本発明の実施の形態１にかかるマージ処理装置１０と同様に、配置変換部２０に入力される。配置変換部２０は、入力供給部５０から図９（ａ）のようにソートされた順番に入力されたレコードを、図９（ｂ）のように、それぞれのレコードブロックの最後方レコードを、先頭に位置するようにレコードの順番を入れ替える。配置変換部２０は、並び替えた複数の連のレコードを、入力記憶部３０に入力する。
【００５３】
入力記憶部３０は、入力されたレコードの総数もしくはレコードデータが占める記憶容量をマージ処理装置内の制御部に通知し、制御部はこれを元に出力記憶部６０にマージされたレコード列を書き込む領域を確保する。確保が終わると、昇順マージ処理ユニットと降順マージ処理ユニットにマージ処理を開始するよう指令を出す。
【００５４】
入力部２２は、それぞれの連について、レコードブロック１、レコードブロック２、・・・レコードブロック６の順番にレコードを取得する。以降の処理は、図１０（ａ）に示されるように、本発明の実施の形態１にかかるマージ処理装置と同様であり、入力部２２は、レコードを、並び替えられる前の順番に復元して、記憶部２４へ入力する。これらのレコードは昇順に並び替えられた上で出力記憶部６０に順次出力される。出力されたレコードは、出力記憶部６０に確保された領域の先頭から書き込まれる。
【００５５】
入力部２２＿１は、それぞれの連について、レコードブロック６、レコードブロック５、・・・レコードブロック１の順番にレコードを取得する。また、降順マージ処理ユニットにおいては、本発明の実施の形態２と同様に、予測用レコードは、ａ１、ａ９、・・・ａ４１である。本発明の実施の形態３においては、配置変換部２０において、レコードの順番が入れ替えられているため、予測用レコードは、それぞれのレコードブロックの２番目に配置されている。入力部２２＿１は、予測用レコードを取得した場合、レコードブロックの全てのレコードを取得する前に、レコード列選択部２６＿１へ予測用レコードを出力する。以降の処理は、本発明の実施の形態２にかかるマージ処理装置と同様に、入力部２２は、レコードを降順に並べ替えて、記憶部２４＿１へ入力する。これらのレコードは降順に並び替えられた上で出力記憶部６０に順次出力される。出力されたレコードは、出力記憶部に確保された領域の後ろから逆順に書き込まれる。
【００５６】
ここで、昇順マージ処理ユニットは、入力された連の前方に位置するレコードブロックから順にマージ処理を行う。これに対して、降順マージ処理ユニットは、入力された連の後方に位置するレコードブロックから順にマージ処理を行う。これより、入力された連のレコードは、昇順マージ処理ユニットもしくは降順マージ処理ユニットのどちらか一方によりマージ処理が実行されるように制御されてもよい。これは例えば、昇順マージ処理ユニットが出力したレコードの個数と、降順マージユニットが出力したレコードの個数をマージ処理装置内の制御部が監視し、両者の個数の和が入力されたレコードの総数に到達した時点で、両ユニットの動作を停止させることで行われてもよい。これにより、出力記憶部６０に対して、重複するレコードの書き込みを防止することができる。
【００５７】
以上説明したように、本発明の実施の形態３にかかるマージ処理装置を用いることにより、入力されたＰ個の連に対して、昇順マージ処理ユニットによるマージ処理と、降順マージ処理ユニットによるマージ処理とを並列に実行することができる。そのため、本発明の実施の形態１及び２と比較して、高速なマージ処理を実現することができる。
【００５８】
（実施の形態４）
続いて、本発明の実施の形態４にかかる配置変換部２０のレコード入れ替えパタンについて説明する。本発明の実施の形態４にかかるマージ処理装置の構成は、図８の構成と同様である。図１１を用いて、本発明の実施の形態４にかかる配置変換部２０のレコード入れ替えパタンについて説明する。
【００５９】
図１１（ａ）は、配置変換部２０に入力される連１のレコードの順序を示している。これに対して、図１１（ｂ）は、配置変換部２０によってレコードが入れ替えられた後の、連１のレコードの順序を示している。レコードブロック１を例に説明する。配置変換部２０によって並び替えられる前のレコードブロック内のレコードの順序は、ａ１〜ａ８の順番に並べられている。配置変換部２０によって並び替えられた後のレコードブロック１内のレコードの順序は、ａ８、ａ１、ａ７、ａ２、ａ６、ａ３、ａ５、ａ４の順番に並び替えられている。レコードの並び替えは次のようにして行われる。はじめに、並び替えられる前のレコードブロック１内のａ１〜ａ４を前半部とし、ａ５〜ａ８を後半部とする。ここで、後半部のレコードを降順に並び替えを行う。次に、昇順に並べられている前半部のレコードと、降順に並べられている後半部のレコードとを交互に配置する。これにより、上述したレコードの順序となる。
【００６０】
図１２（ａ）は、入力部２２から記憶部２４へレコードが入力される際に行われるレコードの並び替えであり、図１０（ａ）と同様に、それぞれのレコードは、昇順に並び替えられて、記憶部２４へ入力される。また、図１２（ｂ）は、入力部２２＿１から記憶部２４＿１へレコードが入力される際に行われるレコードの並び替えであり、図１０（ｂ）と同様に、それぞれのレコードは、降順に並び替えられて記憶部２４へ入力される。
【００６１】
上述したように、図１２（ａ）及び（ｂ）に示したように、レコードブロックの前半部と後半部を交互に配置した場合、図１０（ｂ）において説明した場合よりも、入力部２２＿１から記憶部２４＿１へレコードを入力するまでの遅延時間を短縮することができる。図１０（ｂ）においては、入力部２２＿１は、８番目に到着するレコードａ４７を取得するまで、記憶部２４＿１へレコードを出力することができない。これに対して、図１２（ｂ）においては、入力部２２＿１は、５番目に到着するレコードａ４６を取得すると、記憶部２４＿１へレコードを出力することができる。これより、降順マージ処理ユニットにおける記憶部２４＿１への出力遅延時間を短縮することができる。昇順マージ処理ユニットにおける記憶部２４＿１への出力遅延時間は、増加することになるが、一方のマージ処理ユニットにおける遅延時間が大幅に増加することを防止することができる。
【００６２】
（実施の形態５）
続いて、図１３を用いて本発明の実施の形態５にかかるマージ処理装置の構成例について説明する。図１３に示すマージ処理装置は、Ｎ個のマージ処理部を直列に接続したパイプラインマージソート装置である。このマージ処理装置は、Ｐ個のレコード列をマージする装置であり、第１のマージ処理部７１、第２のマージ処理部７２、・・・、第Ｎのマージ処理部７３は、それぞれＰ１、Ｐ２、・・・、ＰＮ個のレコード列をマージする機能を備える。ここで、Ｐ＝Ｐ１×Ｐ２×・・・×ＰＮであるとし、それぞれのマージ処理部は、レコード列を記憶する十分な入力記憶部を備えるとする。第１のマージ処理部７１は、外部からソート済みレコード列がＰ１個入力されるとマージ処理を開始し、第２のマージ処理部７２の入力記憶部にマージ後のレコード列を出力し、これをＰ÷Ｐ１＝Ｐ２×・・・×ＰＮ回繰り返す。第２のマージ処理部７２は、第１のマージ処理部７１からレコード列がＰ２個入力されるとマージ処理を開始し、第３のマージ処理部の入力記憶部にマージ後のレコード列を出力し、これをＰ３×・・・×ＰＮ回繰り返す。このようにして、このマージ処理装置は、Ｐ個のレコード列のマージを行う。
【００６３】
このマージ処理装置において、それぞれのマージ処理部は、本発明の実施の形態２にかかるマージ処理装置と同じ構成をしている。Ｎ＝１のときは、本発明の実施の形態２と同じである。第１のマージ処理部に入力されたレコード列のソート順を昇順とすると、第１のマージ処理部７１から第２のマージ処理部７２に出力されるレコード列のソート順は降順である。同様に、第２のマージ処理部７２から第３のマージ処理部に出力されるレコード列のソート順は昇順となり、第Ｎのマージ処理部７３は、Ｎが奇数のとき昇順のレコード列を入力して降順のレコード列を出力し、Ｎが偶数のとき降順のレコード列を入力して昇順のレコード列を出力する。
【００６４】
マージ処理部の内部の動作は、実施の形態２で説明した通りである。それぞれの処理部が備える入力記憶部はレコードブロック単位で読み出す必要があり、さらに読み出し遅延時間が生じる。しかし、入力のソート順序と出力のソート順序とを入れ替えて、出力ソート順序に従ったときの予測用レコードをレコードブロックの最初に読み出せるようにすることで、読み出し遅延を隠蔽しレコード入力の効率を高め、高速な動作を可能としている。
【００６５】
（実施の形態６）
続いて、図１４を用いて本発明の実施の形態６にかかるマージ処理装置の構成例について説明する。図１４に示すマージ処理装置も実施の形態５と同様の構成をしたパイプラインマージソート装置であるが、各マージ処理部の間に配置変換部７４及び７５を備えていることと、Ｎ個のマージ処理部の内部構成と動作が異なっている。ここで、第１のマージ処理部７１は一般的なマージ処理装置であり、第２〜第Ｎのマージ処理部は、その手前の配置変換部と合わせて本発明の実施の形態１または３または４と同様の構成と動作をする。例えば図１５は、Ｎ＝２であり、第２のマージ処理部７２が本発明の実施の形態１と同様の構成である場合の構成を示す。このマージ処理装置において、配置変換部、全てのマージ処理部において、入力レコード列のソート順と出力レコード列のソート順は同じである。
【００６６】
ここで、第１のマージ処理部７１と第２のマージ処理部７２の間の配置変換部７４は、第１のマージ処理部７１から順に出力されるレコードを、レコードブロックに区切りながら配置変換を同時に行い、変換された配置のレコードブロックデータを第２のマージ処理部７２に書き込む。この配置変換処理は、マージ処理部の出力と同時に行われるため、配置変換処理を行うことによるマージ処理時間の増加は少ない。同様に、第Ｎのマージ処理部７３と第(n+1)のマージ処理部の間の配置変換部は、第Ｎのマージ処理部７３のレコード出力と同時に動作するため、配置変換処理を行うことによるマージ処理時間の増加は少ない。よって、本発明の実施の形態のマージ処理装置は、レコード入力の効率を高め、高速な動作を可能としている。
【００６７】
（実施の形態７）
続いて、図１６を用いて本発明の実施の形態７にかかるソート処理装置の構成例について説明する。このソート処理装置は、本発明の実施の形態５のマージ処理装置の入力にソート処理部８１を加えたソート装置である。ソート処理部８１は、複数のレコードを内部の記憶部に入力し、それらをＰ個のレコードのグループに分割してグループ内のソートを行う。ソートされたレコード列を、第１のマージ処理部７１に出力する。ソート処理部８１におけるソート順序は第１のマージ処理部のソート順序の逆である。このように構成されたソート処理装置は、実施の形態５のマージ処理装置と同様に高速に動作する。
【００６８】
（実施の形態８）
続いて、図１７を用いて本発明の実施の形態８にかかるソート処理装置の構成例について説明する。このソート処理装置は、本発明の実施の形態６のマージ処理装置における第１のマージ処理部７１をソート処理部に置き換えたソート装置である。ソート処理部８１は、複数のレコードを内部の記憶部に入力し、それらをＰ個のレコードのグループに分割してグループ内のソートを行う。ソートされたレコード列を、第１のマージ処理部７１に出力する。このように構成されたソート処理装置は、実施の形態６のマージ処理装置と同様に高速に動作する。
【００６９】
なお、上述した実施の形態１乃至８において、入力される連（レコード列）に含まれるレコードの数は、説明を容易にするため、それぞれ等しいとして説明しているが、レコードの数は制限されない。つまり、入力される連に含まれるそれぞれのレコードの数は、連ごとに任意に定められる。
【００７０】
また、上述した本発明の実施の形態１乃至８にかかるマージ処理装置の適用例について、以下に説明する。
【００７１】
はじめに、第１乃至第８の実施形態に係るマージ処理装置を集積回路により構成した例について説明する。入力記憶部３０と整列出力部３２とはＳＤＲＡＭとその制御用回路から構成され、記憶部２４にはＳＲＡＭとその制御用回路から構成される。ＳＤＲＡＭはバースト転送モードを用いることにより高速なデータ読み出しが可能であり、レコードブロックのレコード数は、ＳＤＲＡＭからの読み出し効率が高くなるように大きめに設定される。また、レコードブロックが配置されるアドレスは、適切な倍数のアドレスにアラインされている。ＳＤＲＡＭにデータを読み出すコマンド発行してからデータが転送されるまでアクセス遅延があり、これがマージ処理装置におけるレコード入力処理の効率を低下させる要因となる。しかし、本発明のマージ処理装置１０は、ＳＤＲＡＭにレコードブロックを格納する際の配置を並び替えているため、レコードブロック内の全てのレコードを入力部２０に転送し終える前に次のリード要求処理をＳＤＲＡＭに対して行うことができる。そのため、ＳＤＲＡＭからデータが転送されるまでの、アクセス遅延を隠蔽できる。これにより、マージ処理装置を集積回路により構成した場合、本発明を用いないマージ装置よりも高速にマージ処理を実行できる。
【００７２】
続いて、第１乃至第８の実施形態に係るマージ処理装置をＣＰＵと主記憶メモリからなるコンピュータとハードディスク装置、コンピュータにマージ処理を行わせるプログラムにより構成した例について説明する。入力記憶部３０と整列出力部３２とへのレコードの記憶にはハードディスクを用い、記憶部２４には、コンピュータ内部の主記憶メモリを用いる。このコンピュータは複数のスレッドを並列に動作させることが可能であり、このプログラムは、配置変更部２０、入力部２２、レコード列選択部２６、整列出力部３２に複数のスレッドを起動して、ＣＰＵに本発明に係るマージ処理を行わせるための指令が記述されている。ハードディスク装置に記憶されたレコードデータを読み出す際、読み出しコマンドを発行してから、データが読み出されるまで遅延時間があるため、これがマージ処理装置におけるレコード入力処理の効率を低下させる要因となる。しかし、本発明のマージ処理装置は、ハードディスクにレコードブロックを格納する際の配置を並び替えている。そのため、レコードブロック内の全てのレコードを入力部２２に転送し終える前に次のリード要求処理をハードディスクに対して行うことができる。そのため、ハードディスク装置からデータが読み出されるまでのアクセス遅延を隠蔽できる。これにより、マージ処理装置をコンピュータ装置により構成した場合、本発明を用いないマージ処理装置よりも高速にマージ処理を実行できる。
【００７３】
上述の実施の形態では、本発明をハードウェアの構成として説明したが、本発明は、これに限定されるものではない。本発明は、任意の処理を、ＣＰＵ（Central Processing Unit）にコンピュータプログラムを実行させることにより実現することも可能である。
【００７４】
プログラムは、様々なタイプの非一時的なコンピュータ可読媒体（non-transitory computer readable medium）を用いて格納され、コンピュータに供給することができる。非一時的なコンピュータ可読媒体は、様々なタイプの実体のある記録媒体（tangible storage medium）を含む。非一時的なコンピュータ可読媒体の例は、磁気記録媒体（例えばフレキシブルディスク、磁気テープ、ハードディスクドライブ）、光磁気記録媒体（例えば光磁気ディスク）、ＣＤ−ＲＯＭ（Read Only Memory）、ＣＤ−Ｒ、ＣＤ−Ｒ／Ｗ、半導体メモリ（例えば、マスクＲＯＭ、ＰＲＯＭ（Programmable ROM）、ＥＰＲＯＭ（Erasable PROM）、フラッシュＲＯＭ、ＲＡＭ（random access memory））を含む。また、プログラムは、様々なタイプの一時的なコンピュータ可読媒体（transitory computer readable medium）によってコンピュータに供給されてもよい。一時的なコンピュータ可読媒体の例は、電気信号、光信号、及び電磁波を含む。一時的なコンピュータ可読媒体は、電線及び光ファイバ等の有線通信路、又は無線通信路を介して、プログラムをコンピュータに供給できる。
【００７５】
なお、本発明は上記実施の形態に限られたものではなく、趣旨を逸脱しない範囲で適宜変更することが可能である。
【００７６】
（付記１）ソートされた複数のレコードから構成されるレコード列が複数入力され、前記入力されたそれぞれのレコード列を、少なくとも１のレコードを含むレコードブロックに分離し、当該レコードブロックのそれぞれに含まれる複数のレコードの最後方に配置されている予測用レコードを、現在配置されている位置よりも前方に位置するようにレコードの順序を入れ替える配置変換部と、前記配置変換部から複数のレコードブロックを取得し、記憶部へ入力する入力部と、前記複数のレコードブロックのそれぞれに含まれた前記予測用レコードの大小関係に基づいて、前記入力部が前記配置変換部から取得するレコード列を選択するレコード列選択部と、を備え、前記入力部は、前記レコードブロックに含まれるレコードのそれぞれを前記順序が入れ替えられたレコードの順に取得し、前記レコードブロックに含まれる全てのレコードを取得する前に、取得済の予測用レコードを前記レコード列選択部へ出力し、前記レコード列選択部は、前記入力部から出力された予測用レコードの入力に応じて、次に前記入力部が前記配置変換部から取得するレコード列を選択する処理を開始するマージ処理装置。
【００７７】
（付記２）前記配置変換部は、前記予測用レコードを前記レコードブロックの先頭に位置するように、前記レコードの順序を入れ替える、付記１記載のマージ処理装置。
【００７８】
（付記３）前記入力部は、前記レコードの順序が入れ替えられたレコードブロックの順序を元に戻して、前記順序が元に戻されたレコードブロックを前記記憶部へ入力する、付記１又は２に記載のマージ処理装置。
【００７９】
（付記４）ソートされた複数のレコードから構成されるレコード列が複数入力され、当該前記入力されたそれぞれのレコード列を少なくとも１のレコードを含む複数のレコードブロックに分離する分離部と、前記分離部に後から入力された前記レコードブロックから順に前記レコードブロックを取得し、記憶部へ入力するとともに、前記レコードブロック内で最も前方に位置するブロックを予測用レコードとして取り出す入力部と、前記複数のレコードブロックのそれぞれに含まれた前記予測用レコードの大小関係に基づいて、前記入力部が前記配置変換部から取得するレコードブロックを選択するレコード列選択部と、前記レコード列のソート順序と逆のソート順序に従い記憶部からレコードを順に取り出して出力する整列出力部とを備え、前記入力部は、前記レコードブロックのレコードを全て取得する前に、前記予測用レコードを前記レコード列選択部へ出力し、前記レコード列選択部は、前記入力部から出力された予測用レコードに基づいて、次に前記入力部が前記配置変換部から取得するレコード列を選択する処理を開始するマージ処理装置。
【００８０】
（付記５）ソートされた複数のレコードから構成されるレコード列が複数入力され、前記入力されたそれぞれのレコード列を、少なくとも１のレコードを含むレコードブロックに分離し、当該レコードブロックのそれぞれに含まれる複数のレコードの最後方に配置されている第１の予測用レコードを、現在配置されている位置よりも前方に位置するようにレコードの順序を入れ替える配置変換部と、前記配置変換部から複数のレコードブロックを取得し、第１の記憶部へ入力する第１の入力部と、前記レコード列のソート順序と同じソート順序に従い前記第１の記憶部からレコードを順に取り出して出力する第１の整列出力部と、前記配置変換部へ後から入力された前記レコードブロックから順に前記レコードブロックを取得し、第２の記憶部へ入力するとともに、前記レコードブロック内で最も前方に配置されているブロックを第２の予測用レコードとして取り出す第２の入力部と、前記レコード列のソート順序と逆のソート順序に従い前記第２の記憶部からレコードを順に取り出して出力する第２の整列出力部と、前記複数のレコードブロックのそれぞれに含まれた前記第１の予測用レコードの大小関係に基づいて、前記第１の入力部が前記配置変換部から取得するレコード列を選択する第１のレコード列選択部と、前記複数のレコードブロックのそれぞれに含まれた前記第２の予測用レコードの大小関係に基づいて、前記第２の入力部が前記配置変換部から取得するレコード列を選択する第２のレコード列選択部と、を備え、前記第１及び第２の入力部は、前記レコードブロックのレコードを全て取得する前に、前記第１及び第２の予測用レコードを前記第１及び第２のレコード列選択部へ出力し、前記第１及び第２のレコード列選択部は、前記第１及び第２の入力部から出力された第１及び第２の予測用レコードに基づいて、次に前記第１及び第２の入力部が前記配置変換部から取得するレコード列を選択する処理を開始するマージ処理装置。
【００８１】
（付記６）前記配置変換部は、前記レコードブロックに含まれるレコードの前半の列と、残りのレコードを逆順に並び替えたレコードの列とを交互に配置する付記５に記載のマージ処理装置。
【００８２】
（付記７）複数のレコードから構成されるレコード列を複数格納する記憶部と、前記記憶部に格納されたレコードを取り出してソート規則に従う順序に並び変えてレコードを出力する整列出力部と、複数のレコード列が少なくとも１のレコードを含むレコードブロックに分離され、当該レコードブロックのそれぞれにおいて外部からの入力時に最後方に配置されている予測用レコードに基づいて、次に入力するレコード列を選択するレコード列選択部とを含むマージ処理ユニットに、前記レコード列を入力する処理をコンピュータに実行させる制御プログラムであって、外部から前記レコードブロックを複数取得するするステップと、前記取得された複数のレコードブロックの最後方に配置されている予測用レコードを、現在配置されている位置よりも前方に位置するようにレコードの順序を入れ替えるステップと、前記順序が入れ替えられたレコードの順に前記レコードを前記マージ処理ユニットに入力するステップと、をコンピュータに実行させる制御プログラム。
【００８３】
（付記８）複数のレコードから構成されるレコード列を複数格納する記憶部と、前記記憶部に格納されたレコードを取り出してソート規則に従う順序に並び変えてレコードを出力する整列出力部と、複数のレコード列が少なくとも１のレコードを含むレコードブロックに分離され、当該レコードブロックのそれぞれにおいて外部からの入力時に最後方に配置されている予測用レコードに基づいて、次に入力するレコード列を選択するレコード列選択部とを含むマージ処理ユニットに、前記レコード列を入力する処理をコンピュータに実行させる制御プログラムであって、外部から前記レコードブロックを複数取得するするステップと、前記取得した複数のレコードブロックに含まれるレコードをソートするステップと、前記ソートされた複数のレコードブロックの最後方に配置されている予測用レコードを、現在配置されている位置よりも前方に位置するようにレコードの順序を入れ替えるステップと、前記順序が入れ替えられたレコードの順に前記レコードを前記マージ処理ユニットに入力するステップと、をコンピュータに実行させる制御プログラム。
【００８４】
（付記９）ソートされた複数のレコードから構成されるレコード列が複数入力され、前記入力されたそれぞれのレコード列を、少なくとも１のレコードを含むレコードブロックに分離するステップと、前記複数のレコードブロックのそれぞれに含まれる複数のレコードの最後方に配置されている予測用レコードを、現在配置されている位置よりも前方に位置するようにレコードの順序を入れ替えるステップと、前記レコードブロックに含まれるレコードのそれぞれを前記順序が入れ替えられたレコードの順に取得するとともに、取得済みの予測用レコードを出力するステップと、前記出力された予測用レコードの入力に応じて、次に入力されるレコード列を選択する処理を開始するステップと、を備えるレコードマージ方法。
【００８５】
（付記１０）複数のレコードから構成されるレコード列が複数入力され、前記入力されたそれぞれのレコード列を、少なくとも１のレコードを含むレコードブロックに分離するステップと、前記レコードブロックに含まれるレコードをソートするステップと、前記複数のレコードブロックのそれぞれに含まれる複数のレコードの最後方に配置されている予測用レコードを、現在配置されている位置よりも前方に位置するようにレコードの順序を入れ替えるステップと、前記レコードブロックに含まれるレコードのそれぞれを前記順序が入れ替えられたレコードの順に取得するとともに、取得済みの予測用レコードを出力するステップと、前記出力された予測用レコードの入力に応じて、次に入力されるレコード列を選択する処理を開始するステップと、を備えるレコードマージ方法。
【００８６】
（付記１１）複数のレコードから構成されるレコード列が複数入力され、当該前記入力されたそれぞれのレコード列を少なくとも１のレコードを含む複数のレコードブロックに分離し、当該レコードブロックに含まれるレコードをソートするソート処理部と、前記ソート処理部に後から入力された前記レコードブロックから順に前記レコードブロックを取得し、記憶部へ入力するとともに、前記レコードブロック内で最も前方に位置するブロックを予測用レコードとして取り出す入力部と、前記複数のレコードブロックのそれぞれに含まれた前記予測用レコードの大小関係に基づいて、前記入力部が前記配置変換部から取得するレコードブロックを選択するレコード列選択部と、前記レコード列のソート順序と逆のソート順序に従い記憶部からレコードを順に取り出して出力する整列出力部とを備え、前記入力部は、前記レコードブロックのレコードを全て取得する前に、前記予測用レコードを前記レコード列選択部へ出力し、前記レコード列選択部は、前記入力部から出力された予測用レコードに基づいて、次に前記入力部が前記配置変換部から取得するレコード列を選択する処理を開始するソート処理装置。
【００８７】
（付記１２）複数のレコードから構成されるレコード列が複数入力され、前記入力されたそれぞれのレコード列を、少なくとも１のレコードを含むレコードブロックに分離し、当該レコードブロックに含まれるレコードをソートするソート処理部と、前記レコードブロックのそれぞれに含まれる複数のレコードの最後方に配置されている予測用レコードを、現在配置されている位置よりも前方に位置するようにレコードの順序を入れ替える配置変換部と、前記配置変換部から複数のレコードブロックを取得し、記憶部へ入力する入力部と、前記複数のレコードブロックのそれぞれに含まれた前記予測用レコードの大小関係に基づいて、前記入力部が前記配置変換部から取得するレコード列を選択するレコード列選択部と、を備え、前記入力部は、前記レコードブロックに含まれるレコードのそれぞれを前記順序が入れ替えられたレコードの順に取得し、前記レコードブロックに含まれる全てのレコードを取得する前に、取得済の予測用レコードを前記レコード列選択部へ出力し、前記レコード列選択部は、前記入力部から出力された予測用レコードの入力に応じて、次に前記入力部が前記配置変換部から取得するレコード列を選択する処理を開始するソート処理装置。
【符号の説明】
【００８８】
１０  マージ処理装置
２０  配置変換部
２２、２２＿１  入力部
２４、２４＿１  記憶部
２６、２６＿１  レコード列選択部
３０  入力記憶部
３２、３２＿１  整列出力部
４１  第１のバッファ
４２  第２のバッファ
４３  第Ｐのバッファ
５０  入力供給部
６０  出力記憶部
【図１】
2011233012.tif 000003
【図２】
2011233012.tif 000004
【図３】
2011233012.tif 000005
【図４】
2011233012.tif 000006
【図５】
2011233012.tif 000007
【図６】
2011233012.tif 000008
【図７】
2011233012.tif 000009
【図８】
2011233012.tif 000010
【図９】
2011233012.tif 000011
【図１０】
2011233012.tif 000012
【図１１】
2011233012.tif 000013
【図１２】
2011233012.tif 000014
【図１３】
2011233012.tif 000015
【図１４】
2011233012.tif 000016
【図１５】
2011233012.tif 000017
【図１６】
2011233012.tif 000018
【図１７】
2011233012.tif 000019
【図１８】
2011233012.tif 000020
【図１９】
2011233012.tif 000021