(57)【要約】  １以上のレコードが格納されたテーブルを各々が保持する複数のノードが含まれるデータ処理システムであって、前記ノードの各々は、所定のＬ演算で被参照側となる構造体を示す右構造体を、自ノードが保持する前記テーブルから作成する右構造体作成手段と、前記Ｌ演算で被操作側となる構造体を示す左構造体を前記右構造体から作成する左構造体作成手段と、前記右構造体作成手段により作成した右構造体を、他のノードに対して送信する送信手段と、前記他のノードで作成された右構造体を受信する受信手段と、前記左構造体と、前記右構造体作成手段により作成した右構造体及び前記受信手段により受信した右構造体の各々とで前記Ｌ演算を行う演算手段と、前記演算手段による演算結果を用いて、自ノードが保持する前記テーブルに格納されている１以上のレコードに対して、前記複数のノードの各々が保持するテーブルに格納されている全てのレコード間での順序を付与する順序付与手段と、を有することを特徴とする。【特許請求の範囲】
【請求項１】
１以上のレコードが格納されたテーブルを各々が保持する複数のノードが含まれるデータ処理システムであって、
前記ノードの各々は、
所定のＬ演算で被参照側となる構造体を示す右構造体を、自ノードが保持する前記テーブルから作成する右構造体作成手段と、
前記Ｌ演算で被操作側となる構造体を示す左構造体を前記右構造体から作成する左構造体作成手段と、
前記右構造体作成手段により作成した右構造体を、他のノードに対して送信する送信手段と、
前記他のノードで作成された右構造体を受信する受信手段と、
前記左構造体と、前記右構造体作成手段により作成した右構造体及び前記受信手段により受信した右構造体の各々とで前記Ｌ演算を行う演算手段と、
前記演算手段による演算結果を用いて、自ノードが保持する前記テーブルに格納されている１以上のレコードに対して、前記複数のノードの各々が保持するテーブルに格納されている全てのレコード間での順序を付与する順序付与手段と、
を有することを特徴とするデータ処理システム。
【請求項２】
前記順序付与手段により自ノードが保持する前記テーブルに格納されている１以上のレコードに対して前記順序が付与されることで、前記複数のノードの各々が保持するテーブルに格納されている全てのレコード間で、検索、集計及びソートが少なくとも含まれるデータ処理が実現される、ことを特徴とする請求項１に記載のデータ処理システム。
【請求項３】
前記左構造体は、各行にキーと結果格納領域とが含まれ、かつ、前記キーの昇順又は降順で前記行が１以上並べられた構造体であり、
前記右構造体は、各行にキーと所定の値とが含まれ、かつ、前記キーの昇順又は降順で前記行が１以上並べられた構造体であり、
前記Ｌ演算は、
前記左構造体のキーと前記右構造体のキーとを昇順又は降順に比較し、比較条件が成立した場合、前記右構造体のキーに対応する値を用いた操作結果を、前記左構造体のキーに対応する結果格納領域に格納する演算である、ことを特徴とする請求項１又は２に記載のデータ処理システム。
【請求項４】
前記比較条件は、前記左構造体のキーが前記右構造体のキーよりも大きいこと又は小さいことを示す条件である、又は、前記左構造体のキーと前記右構造体のキーとが等しいことを示す条件である、ことを特徴とする請求項３に記載のデータ処理システム。
【請求項５】
前記左構造体のキー及び前記右構造体のキーには、複数の値の組が含まれる、ことを特徴とする請求項３又は４に記載のデータ処理システム。
【請求項６】
前記複数のノードにはノード番号が付与されており、
前記複数のノードの各々が保持するテーブルは、所定のテーブルを分割したテーブルのうちの、前記ノード番号に対応するテーブルである、ことを特徴とする請求項１乃至５の何れか一項に記載のデータ処理システム。
【請求項７】
前記右構造体及び前記左構造体の少なくとも一方を分割する分割手段を有し、
前記送信手段は、
前記分割手段により右構造体が分割された場合、分割された右構造体を前記他のノードに対して送信する、ことを特徴とする請求項１乃至６の何れか一項に記載のデータ処理システム。
【請求項８】
１以上のレコードが格納されたテーブルを各々が保持する１以上の他のデータ処理装置と通信可能に接続されるデータ処理装置であって、
所定のＬ演算で被参照側となる構造体を示す右構造体を、前記データ処理装置が保持するテーブルから作成する右構造体作成手段と、
前記Ｌ演算で被操作側となる構造体を示す左構造体を前記右構造体から作成する左構造体作成手段と、
前記右構造体作成手段により作成した右構造体を、前記他のデータ処理装置に対して送信する送信手段と、
前記他のデータ処理装置で作成された右構造体を受信する受信手段と、
前記左構造体と、前記右構造体作成手段により作成した右構造体及び前記受信手段により受信した右構造体の各々とで前記Ｌ演算を行う演算手段と、
前記演算手段による演算結果を用いて、前記データ処理装置が保持する前記テーブルに格納されている１以上のレコードに対して、前記他のデータ処理装置の各々が保持するテーブルに格納されている全てのレコード間での順序を付与する順序付与手段と、
を有することを特徴とするデータ処理装置。
【請求項９】
１以上のレコードが格納されたテーブルを各々が保持する１以上の他のデータ処理装置と通信可能に接続されるデータ処理装置が、
所定のＬ演算で被参照側となる構造体を示す右構造体を、前記データ処理装置が保持するテーブルから作成する右構造体作成手順と、
前記Ｌ演算で被操作側となる構造体を示す左構造体を前記右構造体から作成する左構造体作成手順と、
前記右構造体作成手順で作成した右構造体を、前記他のデータ処理装置に対して送信する送信手順と、
前記他のデータ処理装置で作成された右構造体を受信する受信手順と、
前記左構造体と、前記右構造体作成手順で作成した右構造体及び前記受信手順で受信した右構造体の各々とで前記Ｌ演算を行う演算手順と、
前記演算手順による演算結果を用いて、前記データ処理装置が保持する前記テーブルに格納されている１以上のレコードに対して、前記他のデータ処理装置の各々が保持するテーブルに格納されている全てのレコード間での順序を付与する順序付与手順と、
を実行することを特徴とするデータ処理方法。
【請求項１０】
１以上のレコードが格納されたテーブルを各々が保持する１以上の他のデータ処理装置と通信可能に接続されるデータ処理装置に、
所定のＬ演算で被参照側となる構造体を示す右構造体を、前記データ処理装置が保持するテーブルから作成する右構造体作成手順と、
前記Ｌ演算で被操作側となる構造体を示す左構造体を前記右構造体から作成する左構造体作成手順と、
前記右構造体作成手順で作成した右構造体を、前記他のデータ処理装置に対して送信する送信手順と、
前記他のデータ処理装置で作成された右構造体を受信する受信手順と、
前記左構造体と、前記右構造体作成手順で作成した右構造体及び前記受信手順で受信した右構造体の各々とで前記Ｌ演算を行う演算手順と、
前記演算手順による演算結果を用いて、前記データ処理装置が保持する前記テーブルに格納されている１以上のレコードに対して、前記他のデータ処理装置の各々が保持するテーブルに格納されている全てのレコード間での順序を付与する順序付与手順と、
を実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ処理システム、データ処理装置、データ処理方法及びプログラムに関する。
【背景技術】
【０００２】
各要素間に何等かの順序が定義された順序集合は、レコードと、このレコードを格納するテーブルとで表現される。このとき、順序集合の各要素（レコード）をソートする場合、種々の方法が従来から知られている。これらの方法について、データ項目「Ａｇｅ」、「Ｇｅｎｄｅｒ」、「Ａｄｄｒｅｓｓ」で構成される複数のレコードを「Ａｇｅ」の昇順にソートする場合を例として説明する。【０００３】
第一の方法としては、テーブル内におけるレコードの格納位置を変更する方法が挙げられる。この場合、図１Ａに示すように、ソートの前後でレコードの格納位置が変更され得る。例えば、ソート前に格納位置「０」に格納されていたレコード（Ａｇｅ「８」のレコード）は、ソート後では格納位置「２」に格納される。【０００４】
第二の方法としては、レコード間の順序を示すレコード番号（以降、「ＲｅｃＮｏ」とも表す。）が格納されたレコード番号リストを用いる方法が挙げられる。ここで、レコード番号リストには、同一格納位置のレコードのレコード番号が格納されている。すなわち、レコード番号リストの格納位置「ｎ」には、テーブルの格納位置「ｎ」のレコードのレコード番号が格納される。この場合、図１Ｂに示すように、ソートの前後でレコード番号の格納位置が変更され得る。例えば、レコード番号「０」は、ソート前ではレコード番号リストの格納位置「０」に格納されているが、ソート後ではレコード番号リストの格納位置「２」に格納される。この第二の方法は、レコードのサイズが大きい場合であっても、第一の方法と比較して、メモリのコピー量が少なく高速である。また、真部分集合（例えば、Ｇｅｎｄｅｒが「Ｆ」のレコードのみで構成される順序集合）も、元のテーブルを保持したまま表現可能である。【０００５】
また、第三の方法として、複数のテーブルにレコードが分散して格納されている場合に、これらのテーブル間におけるレコードの統一的な順序を示すＧＯｒｄ（これは、「Ｇｌｏｂａｌ  Ｏｒｄｅｒ」の略である。）を用いて、レコードをソートする方法が知られている（特許文献１参照）。例えば、図２に示すように、テーブル１とテーブル２とが存在し、これらテーブル１とテーブル２とにそれぞれ格納されているレコードを「Ａｇｅ」の昇順にソートする場合、ＧＯｒｄは、１つのテーブル内で昇順になるように決定され、テーブル１とテーブル２との間の統一的な順序を表す。例えば、ＧＯｒｄ「０」のレコードは、テーブル１におけるレコード番号「３」のレコードである。同様に、例えば、ＧＯｒｄ「１」のレコードは、テーブル１におけるレコード番号「１」のレコードである。同様に、例えば、ＧＯｒｄ「２」のレコードは、テーブル２におけるレコード番号「３」のレコードである。以降、ＧＯｒｄ「３」〜「７」についても同様である。この第三の方法は、第二の方法と同様に、高速で、かつ、真部分集合も元のテーブルを保持したまま表現可能である。また、ＧＯｒｄが同一テーブル内で昇順となることからレコードの検索も高速に行うことができる。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特許第４６２０５９３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、上記の第一の方法〜第三の方法は、単一のノード（コンピュータ）内のデータ（レコード）をソートする場合に有効な手法であり、複数のノードに分散して保持されているデータをソートする場合には多くの時間を要する。これは、ノード間でのデータ参照は、一般に、単一のノード内でのデータ参照に比べて数百倍以上の時間を要するためである。このことは、複数のノードに分散して保持されているデータを検索や集計する場合についても同様である。【０００８】
本発明は、上記の点に鑑みてなされたもので、複数のノードに分散して保持されているデータの高速なソート、検索、集計を実現することを目的とする。
【課題を解決するための手段】
【０００９】
上記目的を達成するため、本発明のデータ処理システムは、１以上のレコードが格納されたテーブルを各々が保持する複数のノードが含まれるデータ処理システムであって、前記ノードの各々は、所定のＬ演算で被参照側となる構造体を示す右構造体を、自ノードが保持する前記テーブルから作成する右構造体作成手段と、前記Ｌ演算で被操作側となる構造体を示す左構造体を前記右構造体から作成する左構造体作成手段と、前記右構造体作成手段により作成した右構造体を、他のノードに対して送信する送信手段と、前記他のノードで作成された右構造体を受信する受信手段と、前記左構造体と、前記右構造体作成手段により作成した右構造体及び前記受信手段により受信した右構造体の各々とで前記Ｌ演算を行う演算手段と、前記演算手段による演算結果を用いて、自ノードが保持する前記テーブルに格納されている１以上のレコードに対して、前記複数のノードの各々が保持するテーブルに格納されている全てのレコード間での順序を付与する順序付与手段と、を有することを特徴とする。
【発明の効果】
【００１０】
複数のノードに分散して保持されているデータの高速なソート、検索、集計を実現することができる。
【図面の簡単な説明】
【００１１】
【図１Ａ】従来技術の一例を説明するための図（その１）である。
【図１Ｂ】従来技術の一例を説明するための図（その１）である。
【図２】従来技術の一例を説明するための図（その２）である。
【図３】左構造体及び右構造体の一例を示す図である。
【図４】Ｌ演算（キー比較条件"＞"）の一例を説明するための図である。
【図５】Ｌ演算（キー比較条件"＝"）の一例を説明するための図である。
【図６】全体テーブルと各ノードが保持する部分テーブルとの関係の一例を説明するための図である。
【図７】本発明の実施の形態におけるデータ処理システムの全体構成の一例を示す図である。
【図８】本発明の実施の形態におけるデータ処理装置のハードウェア構成の一例を示す図である。
【図９】本発明の実施の形態におけるデータ処理装置の機能構成の一例を示す図である。
【図１０】全体テーブルと各ノードが保持する部分テーブルとの具体例を示す図である。
【図１１Ａ】検索の一例を説明するための図（その１）である。
【図１１Ｂ】検索の一例を説明するための図（その１）である。
【図１２】検索の一例を説明するための図（その２）である。
【図１３】検索の一例を説明するための図（その３）である。
【図１４】検索の一例を説明するための図（その４）である。
【図１５】集計の一例を説明するための図（その１）である。
【図１６】集計の一例を説明するための図（その２）である。
【図１７Ａ】単項目ソートの一例を説明するための図（その１）である。
【図１７Ｂ】単項目ソートの一例を説明するための図（その１）である。
【図１８Ａ】単項目ソートの一例を説明するための図（その２）である。
【図１８Ｂ】単項目ソートの一例を説明するための図（その２）である。
【図１８Ｃ】単項目ソートの一例を説明するための図（その２）である。
【図１９Ａ】単項目ソートの一例を説明するための図（その３）である。
【図１９Ｂ】単項目ソートの一例を説明するための図（その３）である。
【図１９Ｃ】単項目ソートの一例を説明するための図（その３）である。
【図２０Ａ】単項目ソートの一例を説明するための図（その４）である。
【図２０Ｂ】単項目ソートの一例を説明するための図（その４）である。
【図２０Ｃ】単項目ソートの一例を説明するための図（その４）である。
【図２１Ａ】複数項目ソートの一例を説明するための図である。
【図２１Ｂ】複数項目ソートの一例を説明するための図である。
【図２２】部分集合の一例を説明するための図である。
【図２３Ａ】部分集合でのソートの一例を説明するための図（その１）である。
【図２３Ｂ】部分集合でのソートの一例を説明するための図（その１）である。
【図２４Ａ】部分集合でのソートの一例を説明するための図（その２）である。
【図２４Ｂ】部分集合でのソートの一例を説明するための図（その２）である。
【図２４Ｃ】部分集合でのソートの一例を説明するための図（その２）である。
【図２５Ａ】部分集合でのソートの一例を説明するための図（その３）である。
【図２５Ｂ】部分集合でのソートの一例を説明するための図（その３）である。
【図２５Ｃ】部分集合でのソートの一例を説明するための図（その３）である。
【図２６Ａ】部分集合でのソートの一例を説明するための図（その４）である。
【図２６Ｂ】部分集合でのソートの一例を説明するための図（その４）である。
【図２６Ｃ】部分集合でのソートの一例を説明するための図（その４）である。
【図２７】右構造体の分割の一例を説明するための図である。
【図２８Ａ】左構造体と分割後の右構造体との比較操作の効率化の一例を説明するための図である。
【図２８Ｂ】左構造体と分割後の右構造体との比較操作の効率化の一例を説明するための図である。
【発明を実施するための形態】
【００１２】
以下、本発明の実施の形態について、図面を参照しながら詳細に説明する。以降の本発明の実施の形態では、上述した第三の方法を複数のノード間でのソートに拡張することで、これらの複数のノードの各々が保持しているテーブルに格納されているレコードの高速なソートを実現する場合について説明する。これにより、複数のノードに分散して保持されているデータの高速なソートを実現することができる。なお、ソートを実現することができれば、集計や検索、ＪＯＩＮ等も可能となる。以降では、ソートや集計、検索、ＪＯＩＮ等を「データ処理」とも表す。
【００１３】
＜Ｌ演算＞
まず、ソート等の各種データ処理を実現するためのＬ演算（Ladder Operation）を定義する。Ｌ演算は、相互に比較可能な昇順キー列を持つ二つの構造体間で定義される。これらの二つの構造体のうち、一方は被操作側の構造体（以降、「左構造体」と表す。）であり、他方は被参照側の構造体（以降、「右構造体」と表す。）である。
【００１４】
Ｌ演算とは、左構造体の昇順キー列中のキーと、右構造体の昇順キー列中のキーとをキー比較条件（"＞"又は"＝"のいずれか）により比較し、左構造体中の操作位置を定めた上で、その操作位置に対して各種操作（例えば、フラグのセット又はリセット、加算、その他の各種計算）の結果を格納する演算又は処理のことである。
【００１５】
なお、昇順キー列は、複数の値を連結したキーの列や複数の値を１つの組で表したキーの列等であっても良い。また、キーとして、文字列等の取り扱いに時間の掛かる値を用いる場合は、当該値（例えば文字列等）を整数化することでＬ演算の高速化や処理の単純化を図ることができる。更に、この整数化により、例えば符号を反転することで、Ｌ演算により実現される昇順ソートと同様に、降順ソートもＬ演算により実現することができる。ただし、降順ソートは、この整数化を行わなくても、より一般的には、右構造体及び左構造体のキーを降順にした上で、キー比較条件として"＞"の代わりに"＜"を用いることでも実現することができる。なお、以降では、単に「ソート」と表した場合は、昇順ソートを意味するものとする。
【００１６】
以降では、一例として、図３に示す左構造体及び右構造体を用いて、具体的なＬ演算の例を説明する。図３に示す左構造体は、４行の構造体であり、昇順キー列として「１０」、「２０」、「３０」、「４０」が含まれ、これらのキーには「０」に初期化された結果格納領域（すなわち、各種操作の操作結果が格納される領域）が対応付けられている。また、図３に示す右構造体は、３行の構造体であり、昇順キー列として「１０」、「１５」、「２０」が含まれ、これらのキーには加算値「２」、「１」、「３」が対応付けられている。
【００１７】
（Ｌ演算（キー比較条件"＞"））
まず、キー比較条件が"＞"であるＬ演算について、図４を参照しながら説明する。図４は、Ｌ演算（キー比較条件"＞"）の一例を説明するための図である。
【００１８】
Ｓ１１）まず、左構造体の操作位置は「０」、右構造体の参照位置は「０」であるため、左構造体の昇順キー列中のキー「１０」と、右構造体の昇順キー列中のキー「１０」とを比較する。この場合、キー比較条件"＞"が成り立たないため、左構造体の操作位置を一つ下げる。これにより、左構造体の操作位置が「０」から「１」に更新される。
【００１９】
Ｓ１２）次に、左構造体の昇順キー列中のキー「２０」と、右構造体の昇順キー列中のキー「１０」とを比較する。この場合、キー比較条件"＞"が成り立つため、右構造体のキー「１０」に対応する加算値「２」を、左構造体のキー「２０」に対応する結果格納領域に加算した上で、右構造体の参照位置を一つ下げる。これにより、左構造体の操作位置「１」の結果格納領域に格納されている値が「０」から「２」に更新されると共に、右構造体の参照位置が「０」から「１」に更新される。
【００２０】
Ｓ１３）次に、左構造体の昇順キー列中のキー「２０」と、右構造体の昇順キー列中のキー「１５」とを比較する。この場合、キー比較条件"＞"が成り立つため、右構造体のキー「１５」に対応する加算値「１」を、左構造体のキー「２０」に対応する結果格納領域に加算した上で、右構造体の参照位置を一つ下げる。これにより、左構造体の操作位置「１」の結果格納領域に格納されている値が「２」から「３」に更新されると共に、右構造体の参照位置が「１」から「２」に更新される。
【００２１】
Ｓ１４）次に、左構造体の昇順キー列中のキー「２０」と、右構造体の昇順キー列中のキー「２０」とを比較する。この場合、キー比較条件"＞"が成り立たないため、左構造体の操作位置を一つ下げる。これにより、左構造体の操作位置が「１」から「２」に更新される。
【００２２】
Ｓ１５）次に、左構造体の昇順キー列中のキー「３０」と、右構造体の昇順キー列中のキー「２０」とを比較する。この場合、キー比較条件"＞"が成り立つため、右構造体のキー「２０」に対応する加算値「３」を、左構造体のキー「３０」に対応する結果格納領域に加算する。一方で、右構造体の現在の参照位置は「２」であり、これ以上、参照位置を下げることはできないため、Ｌ演算は終了となる。これにより、左構造体の操作位置「２」の結果格納領域に格納されている値が「０」から「３」に更新された上で、Ｌ演算が終了する。
【００２３】
（Ｌ演算（キー比較条件"＝"））
次に、キー比較条件が"＝"であるＬ演算について、図５を参照しながら説明する。図５は、Ｌ演算（キー比較条件"＝"）の一例を説明するための図である。
【００２４】
Ｓ２１）まず、左構造体の操作位置は「０」、右構造体の参照位置は「０」であるため、左構造体の昇順キー列中のキー「１０」と、右構造体の昇順キー列中のキー「１０」とを比較する。この場合、キー比較条件"＝"が成り立つため、右構造体のキー「１０」に対応する加算値「２」を、左構造体のキー「１０」に対応する結果格納領域に加算した上で、右構造体の参照位置と左構造体の操作位置とを一つ下げる。これにより、左構造体の操作位置「０」の結果格納領域に格納されている値が「０」から「２」に更新されると共に、右構造体の参照位置が「０」から「１」に、左構造体の操作位置が「０」から「１」に更新される。
【００２５】
Ｓ２２）次に、左構造体の昇順キー列中のキー「２０」と、右構造体の昇順キー列中のキー「１５」とを比較する。この場合、キー比較条件"＝"が成り立たないため、左構造体のキー「２０」及び右構造体のキー「１５」のうち、キーの値が小さい方の構造体の位置（操作位置又は参照位置）を一つ下げる。図５に示す例では、右構造体のキー「１５」の方が小さいため、右構造体の参照位置を一つ下げる。これにより、右構造体の参照位置が「１」から「２」に更新される。
【００２６】
Ｓ２３）次に、左構造体の昇順キー列中のキー「２０」と、右構造体の昇順キー列中のキー「２０」とを比較する。この場合、キー比較条件"＝"が成り立つため、右構造体のキー「２０」に対応する加算値「３」を、左構造体のキー「２０」に対応する結果格納領域に加算する。一方で、右構造体の現在の参照位置は「２」であり、これ以上、参照位置を下げることはできないため、Ｌ演算は終了となる。これにより、左構造体の操作位置「２」の結果格納領域に格納されている値が「０」から「３」に更新された上で、Ｌ演算が終了する。
【００２７】
（Ｌ演算の性質）
上述した定義により、Ｌ演算の性質として、以下の（１）及び（２）の性質があることがわかる。
【００２８】
左構造体がｍ行、右構造体がｎ行あるとした場合、（１）キー比較条件による比較回数はｍ＋ｎ回以下、（２）操作位置に対する各種操作結果の格納回数はｎ回以下、である。
【００２９】
なお、以降では、右構造体及び左構造体のキー列は昇順であることを前提として、昇順キー列を単に「キー列」とも表す。
【００３０】
＜Ｇｌｏｂａｌ  Ｌ演算＞
Ｋ個の順序付けられたノードがあり、これらＫ個のノードは何等かの経路（ネットワーク）で相互に通信可能に結合されているものとする。
【００３１】
また、テーブル（これを「全体テーブル」とも表す。）が存在し、この全体テーブルが上から順にＫ個に分割され、各ノードは、当該ノードの番号（以降、「ノード番号」とも表す。）に対応した分割部分のテーブル（これを「部分テーブル」とも表す。）を保持しているものとする。すなわち、図６に示すように、Ｎ個のレコードで構成される全体テーブルが存在し、この全体テーブルを上から順に部分テーブル０、部分テーブル１、・・・、部分テーブルＫ−１と分割した場合、ｋ（０≦ｋ≦Ｋ−１）番目のノードを「ノードｋ」として、部分テーブル０はノード０が、部分テーブル１はノード１が、・・・、部分テーブルＫ−１はノードＫ−１が保持しているものとする（つまり、部分テーブルｋはノードｋが保持しているものとする。）。以降では、全体テーブルが上から順にＫ個に分割された場合に、各ノードが、自身のノード番号ｋに対応する部分テーブルｋを保持していることを「安定性前提」と呼ぶ。
【００３２】
このとき、Ｋ個のノード間で相互に右構造体を交換し、各ノード内でＫ回のＬ演算（自ノードの右構造体とのＬ演算も含む）を行う演算を「Ｇｌｏｂａｌ  Ｌ演算」と表す。
【００３３】
Ｇｌｏｂａｌ  Ｌ演算には、以下の３つの特徴がある。
【００３４】
（特徴１）演算処理の非順序性
各ノード内のＫ回のＬ演算は、どの順番で演算処理を行っても最終的な演算結果が同じになる。
【００３５】
この特徴１により、例えば、スーパーコンピュータ等のように多数のノードで構成されるシステムであってもタスクスイッチを容易に実現することができるようになる。すなわち、Ｇｌｏｂａｌ  Ｌ演算の演算処理の非順序性により、ノード間で異なるタスクが実行されていたとしても、タスク終了後にＬ演算を行うことで各ノードは正しい演算結果を得ることができるため、タスクスイッチが容易になる。
【００３６】
（特徴２）演算処理の並列性
各ノード内のＫ回のＬ演算は並列に実行することが可能である。各Ｌ演算同士は独立しているためである。
【００３７】
（特徴３）多様な分散アーキテクチャに対応可能
各ノードが順序付けられ、かつ、各ノードが自ノードのノード番号に対応する部分テーブルを保持していることだけが条件であり、各ノード相互を結合するネットワークのトポロジ等に依らずに、演算処理を実行することができる。
【００３８】
＜データ処理システム１の全体構成＞
以降では、上述したＧｌｏｂａｌ  Ｌ演算により、ソートも含めたデータ処理（例えば、ソートや集計、検索、ＪＯＩＮ等）を実現可能なデータ処理システム１について説明する。
【００３９】
まず、本発明の実施の形態におけるデータ処理システム１の全体構成について、図７を参照しながら説明する。図７は、本発明の実施の形態におけるデータ処理システム１の全体構成の一例を示す図である。
【００４０】
図７に示すように、本発明の実施の形態におけるデータ処理システム１には、Ｋ個のデータ処理装置１０が含まれる。また、これらＫ個のデータ処理装置１０は、任意のネットワークを介して相互に通信可能に接続される。
【００４１】
各データ処理装置１０は、上述したノードとなるコンピュータである。すなわち、各データ処理装置１０は、順序付けられ、かつ、自ノードのノード番号に対応する部分テーブルを保持している。
【００４２】
以降では、一例として、Ｋ＝３であるものとして、データ処理システム１に含まれるデータ処理装置１０を「データ処理装置１０−０」、「データ処理装置１０−１」及び「データ処理装置１０−２」とも表し、データ処理装置１０−０のノード番号を「０」、データ処理装置１０−１のノード番号を「１」、データ処理装置１０−２のノード番号を「２」とする。また、ノード番号０のノードを「ノード０」、ノード番号１のノードを「ノード１」、ノード番号２のノードを「ノード２」とも表す。
【００４３】
なお、図７に示すデータ処理システム１の構成は一例であって他の構成であっても良い。例えば、Ｋを２以上として、データ処理システム１には、任意のＫ個のデータ処理装置１０が含まれていても良い。例えば、データ処理システム１がスーパーコンピュータ等である場合、一般に、Ｋは、数万個程度となることがある。
【００４４】
＜データ処理装置１０のハードウェア構成＞
次に、本発明の実施の形態におけるデータ処理装置１０のハードウェア構成について、図８を参照しながら説明する。図８は、本発明の実施の形態におけるデータ処理装置１０のハードウェア構成の一例を示す図である。
【００４５】
図８に示すように、本発明の実施の形態におけるデータ処理装置１０は、ハードウェアとして、プロセッサ１１と、メモリ１２と、通信Ｉ／Ｆ１３とを有する。これら各ハードウェアは、それぞれがバス１４を介して通信可能に接続されている。
【００４６】
プロセッサ１１は、例えばＣＰＵ（Central Processing Unit）等であり、各種処理を実行する演算装置である。メモリ１２は、例えばＲＡＭ（Random Access Memory）やＲＯＭ（Read Only Memory）、補助記憶装置等であり、各種プログラムやデータを記憶する。通信Ｉ／Ｆ１３は、データ処理装置１０をネットワークに接続するためのインタフェースである。
【００４７】
本発明の実施の形態におけるデータ処理装置１０は、図８に示すハードウェアを有することにより、ソート等のデータ処理を実現することができる。なお、本発明の実施の形態におけるデータ処理装置１０は、図８に示すハードウェアに加えて、例えば、キーボードやマウス等の入力装置、ディスプレイ等の表示装置等を有していても良い。
【００４８】
＜データ処理装置１０の機能構成＞
次に、本発明の実施の形態におけるデータ処理装置１０の機能構成について、図９を参照しながら説明する。図９は、本発明の実施の形態におけるデータ処理装置１０の機能構成の一例を示す図である。
【００４９】
図９に示すように、本発明の実施の形態におけるデータ処理装置１０は、機能部として、通信部１０１と、演算部１０２とを有する。これら各機能部は、データ処理装置１０にインストールされた１以上のプログラムがプロセッサ１１に実行させる処理により実現される。
【００５０】
また、本発明の実施の形態におけるデータ処理装置１０は、記憶部１０３を有する。当該記憶部１０３は、例えばメモリ１２等を用いて実現可能である。
【００５１】
記憶部１０３は、自ノードのノード番号に対応する部分テーブルを記憶している。通信部１０１は、他のノードとの間でデータの送受信（すなわち、自ノードの右構造体の送信と他のノードの右構造体の受信）を行う。演算部１０２は、左構造体及び右構造体の作成と、Ｌ演算を含む各種演算とを行う。演算部１０２により各種演算が行われることで、ソートや集計、検索、ＪＯＩＮ等のデータ処理が実現される。
【００５２】
＜全体テーブルと各ノードが保持するテーブルとの具体例＞
次に、全体テーブルと、ノード１〜ノード３の各ノードが保持する部分テーブルとの具体例について、図１０を参照しながら説明する。図１０は、全体テーブルと各ノードが保持する部分テーブルとの具体例を示す図である。
【００５３】
図１０に示すように、全体テーブルには、データ項目「Ｇｅｎｄｅｒ」及び「Ａｇｅ」で構成される１２個のレコードが格納されているものとする。
【００５４】
このとき、この全体テーブルに格納されているレコードのうち、格納位置「０」〜「３」に格納されているレコードで構成される部分テーブルを、ノード０が保持する部分テーブルとする。同様に、格納位置「４」〜「７」に格納されているレコードで構成される部分テーブルを、ノード１が保持する部分テーブルとする。また、同様に、格納位置「８」〜「１１」に格納されているレコードで構成される部分テーブルを、ノード２が保持する部分テーブルとする。
【００５５】
また、これら各ノードが保持する部分テーブルには、部分テーブル間における統一的な順序を示すＧＯｒｄが格納されるＧＯｒｄリストと、同一部分テーブル内でのレコードの順序を示すレコード番号（ＲｅｃＮｏ）が格納されるレコード番号リストとが対応付けられている。ここで、全体テーブルから部分テーブルを分割した直後では、ノード番号の昇順に部分テーブルを並べた場合にＧＯｒｄは部分テーブル間で昇順になっており、ＲｅｃＮｏは同一部分テーブル内で昇順になっているものとする。
【００５６】
以降の検索、集計、単項目ソート及び複数項目ソートでは、ノード１〜ノード３は、図１０に示す部分テーブルをそれぞれ保持している（すなわち、安定性前提を満たす部分テーブルを記憶部１０３に記憶されている）ものとして、各データ処理について説明する。
【００５７】
＜検索＞
まず、データ処理の一例として、Ｇｅｎｄｅｒ＝"Ｆ"となるレコードを検索する場合について、図１１乃至図１４を参照しながら説明する。図１１乃至図１４は、検索の一例を説明するための図である。
【００５８】
Ｓ３１）まず、各データ処理装置１０の演算部１０２は、自ノード内でＧｅｎｄｅｒ＝"Ｆ"となるレコードを検索する。すなわち、各データ処理装置１０の演算部１０２は、自身の記憶部１０３に記憶されている部分テーブルにおいて、Ｇｅｎｄｅｒ＝"Ｆ"となるレコードを検索する。
【００５９】
そして、各データ処理装置１０の演算部１０２は、検索されたレコードのレコード番号が格納されるレコード番号リストと、空値（ＮＵＬＬ値）が格納されたＧＯｒｄリストとを作成する。
【００６０】
これにより、データ処理装置１０−０（ノード０）では、レコード番号「０」と「３」とが格納されたレコード番号リストと、これらのレコード番号に対応する空値が格納されたＧＯｒｄリストとが作成される。同様に、データ処理装置１０−１（ノード１）では、レコード番号「２」が格納されたレコード番号リストと、このレコード番号に対応する空値が格納されたＧＯｒｄリストとが作成される。同様に、データ処理装置１０−２（ノード２）では、レコード番号「０」と「１」と「２」とが格納されたレコード番号リストと、これらのレコード番号に対応する空値が格納されたＧＯｒｄリストとが作成される。
【００６１】
Ｓ３２）次に、各データ処理装置１０の演算部１０２は、右構造体を作成する。すなわち、各データ処理装置１０の演算部１０２は、自ノードのノード番号を「キー列」、上記のＳ３１で検索されたレコード件数を「ヒット件数」として右構造体を作成する。これにより、データ処理装置１０−０（ノード０）では、キー「０」とヒット件数「２」とが対応付けられた１行の右構造体が作成される。同様に、データ処理装置１０−１（ノード１）では、キー「１」とヒット件数「１」とが対応付けられた１行の右構造体が作成される。同様に、データ処理装置１０−２（ノード２）では、キー「２」とヒット件数「３」とが対応付けられた１行の右構造体が作成される。
【００６２】
Ｓ３３）次に、各データ処理装置１０の演算部１０２は、左構造体を作成する。すなわち、各データ処理装置１０の演算部１０２は、自ノードのノード番号を「キー列」、初期値「０」を「先方出現件数」として左構造体を作成する。なお、先方出現件数とは、自ノードよりも前のノード番号のノードで検索されたレコード件数を格納するための結果格納領域である。
【００６３】
これにより、データ処理装置１０−０（ノード０）では、キー「０」と先方出現件数「２」とが対応付けられた１行の左構造体が作成される。同様に、データ処理装置１０−１（ノード１）では、キー「１」と先方出現件数「０」とが対応付けられた１行の左構造体が作成される。同様に、データ処理装置１０−２（ノード２）では、キー「２」と先方出現件数「０」とが対応付けられた１行の左構造体が作成される。
【００６４】
Ｓ３４）次に、各データ処理装置１０の通信部１０１は、上記のＳ３２で作成した右構造体を相互に交換する。すなわち、各データ処理装置１０の通信部１０１は、自ノードの右構造体を他の全てのノードに送信すると共に、他の全てのノードから送信された右構造体を受信する。なお、このＳ３４は、上記のＳ３２の直後に実行されても良い。
【００６５】
以降のＳ３５−０〜Ｓ３７−０はノード０で実行され、Ｓ３５−１〜Ｓ３７−１はノード１で実行され、Ｓ３５−２〜Ｓ３７−２はノード２で実行されるが、各ノードは、これらを独立に実行することができる。これは、Ｇｌｏｂａｌ  Ｌ演算が上述した特徴２を有するためである。
【００６６】
Ｓ３５−０）データ処理装置１０−０の演算部１０２は、キー比較条件"＞"によりＬ演算を実行する。具体的には、データ処理装置１０−０の演算部１０２は、以下のＳ３５−０−０〜Ｓ３５−０−２を実行する。ここで、データ処理装置１０−０の演算部１０２は、以下のＳ３５−０−０〜Ｓ３５−０−２の並列処理のため、場合により、それぞれで異なる記憶領域上に展開された左構造体中の先方出現件数を使用する。言い換えれば、並列処理のため、場合により、ノード０の右構造体との比較用の左構造体中の先方出現件数と、ノード１の右構造体との比較用の左構造体中の先方出現件数と、ノード２の右構造体との比較用の左構造体中の先方出現件数とを使用する。なお、Ｇｌｏｂａｌ  Ｌ演算が上述した特徴１を有することにより、以下のＳ３５−０−０〜Ｓ３５−０−２は順不同である。
【００６７】
Ｓ３５−０−０）データ処理装置１０−０の演算部１０２は、自ノードの左構造体のキー列中のキー「０」と、自ノード（ノード０）の右構造体のキー列中のキー「０」とを比較する。この場合、キー比較条件"＞"が成り立たないため、当該演算部１０２は、左構造体の操作位置を一つ下げることになるが、これ以上、操作位置を下げることはできないため、Ｌ演算を終了する。
【００６８】
Ｓ３５−０−１）データ処理装置１０−０の演算部１０２は、自ノードの左構造体のキー列中のキー「０」と、ノード１の右構造体のキー列中のキー「１」とを比較する。この場合、キー比較条件"＞"が成り立たないため、当該演算部１０２は、左構造体の操作位置を一つ下げることになるが、これ以上、操作位置を下げることはできないため、Ｌ演算を終了する。
【００６９】
Ｓ３５−０−２）データ処理装置１０−０の演算部１０２は、自ノードの左構造体のキー列中のキー「０」と、ノード２の右構造体のキー列中のキー「２」とを比較する。この場合、キー比較条件"＞"が成り立たないため、当該演算部１０２は、左構造体の操作位置を一つ下げることになるが、これ以上、操作位置を下げることはできないため、Ｌ演算を終了する。
【００７０】
Ｓ３６−０）次に、データ処理装置１０−０の演算部１０２は、左構造体の先方出現件数の合計を算出する。すなわち、データ処理装置１０−０の演算部１０２は、ノード０の右構造体との比較用の左構造体と、ノード１の右構造体との比較用の左構造体と、ノード２の右構造体との比較用の左構造体とで先方出現件数の合計を算出する。この合計が、ノード０のＧＯｒｄの開始番号となる。この場合、先方出現件数の合計は「０」であるため、ノード０のＧＯｒｄの開始番号は「０」となる。
【００７１】
Ｓ３７−０）次に、データ処理装置１０−０の演算部１０２は、自ノードのＧＯｒｄの開始番号を用いて、上記のＳ３１で作成した自ノードのＧＯｒｄリストを更新する。すなわち、データ処理装置１０−０の演算部１０２は、開始番号から開始して、上から順に１つずつ加算した値をＧＯｒｄリストに格納する。これにより、ノード０のＧＯｒｄリストには、格納位置「０」にＧＯｒｄ「０」、格納位置「１」にＧＯｒｄ「１」が格納される。
【００７２】
Ｓ３５−１）データ処理装置１０−１の演算部１０２は、キー比較条件"＞"によりＬ演算を実行する。具体的には、データ処理装置１０−１の演算部１０２は、以下のＳ３５−１−０〜Ｓ３５−１−２を実行する。ここで、データ処理装置１０−１の演算部１０２は、以下のＳ３５−１−０〜Ｓ３５−１−２の並列処理のため、場合により、それぞれで異なる記憶領域上に展開された左構造体中の先方出現件数を使用する。言い換えれば、並列処理のため、場合により、ノード０の右構造体との比較用の左構造体中の先方出現件数と、ノード１の右構造体との比較用の左構造体中の先方出現件数と、ノード２の右構造体との比較用の左構造体中の先方出現件数とを使用する。なお、Ｇｌｏｂａｌ  Ｌ演算が上述した特徴１を有することにより、以下のＳ３５−１−０〜Ｓ３５−１−２は順不同である。
【００７３】
Ｓ３５−１−０）データ処理装置１０−１の演算部１０２は、自ノードの左構造体のキー列中のキー「１」と、ノード０の右構造体のキー列中のキー「０」とを比較する。この場合、キー比較条件"＞"が成り立つため、当該演算部１０２は、右構造体のキー「０」に対応するヒット件数「２」を、左構造体のキー「１」に対応する先方出現件数に加算する。そして、当該演算部１０２は、右構造体の参照位置を一つ下げることになるが、これ以上、参照位置を下げることはできないため、Ｌ演算を終了する。これにより、左構造体の先方出現件数が「０」から「２」に更新される。
【００７４】
Ｓ３５−１−１）データ処理装置１０−１の演算部１０２は、自ノードの左構造体のキー列中のキー「１」と、自ノード（ノード１）の右構造体のキー列中のキー「１」とを比較する。この場合、キー比較条件"＞"が成り立たないため、当該演算部１０２は、左構造体の操作位置を一つ下げることになるが、これ以上、操作位置を下げることはできないため、Ｌ演算を終了する。
【００７５】
Ｓ３５−１−２）データ処理装置１０−１の演算部１０２は、自ノードの左構造体のキー列中のキー「１」と、ノード２の右構造体のキー列中のキー「２」とを比較する。この場合、キー比較条件"＞"が成り立たないため、当該演算部１０２は、左構造体の操作位置を一つ下げることになるが、これ以上、操作位置を下げることはできないため、Ｌ演算を終了する。
【００７６】
Ｓ３６−１）次に、データ処理装置１０−１の演算部１０２は、左構造体の先方出現件数の合計を算出する。すなわち、データ処理装置１０−１の演算部１０２は、ノード０の右構造体との比較用の左構造体と、ノード１の右構造体との比較用の左構造体と、ノード２の右構造体との比較用の左構造体とで先方出現件数の合計を算出する。この合計が、ノード１のＧＯｒｄの開始番号となる。この場合、先方出現件数の合計は「２」であるため、ノード１のＧＯｒｄの開始番号は「２」となる。
【００７７】
Ｓ３７−１）次に、データ処理装置１０−１の演算部１０２は、自ノードのＧＯｒｄの開始番号を用いて、上記のＳ３１で作成した自ノードのＧＯｒｄリストを更新する。すなわち、データ処理装置１０−１の演算部１０２は、開始番号から開始して、上から順に１つずつ加算した値をＧＯｒｄリストに格納する。これにより、ノード１のＧＯｒｄリストには、格納位置「０」にＧＯｒｄ「２」が格納される。
【００７８】
Ｓ３５−２）データ処理装置１０−２の演算部１０２は、キー比較条件"＞"によりＬ演算を実行する。具体的には、データ処理装置１０−２の演算部１０２は、以下のＳ３５−２−０〜Ｓ３５−２−２を実行する。ここで、データ処理装置１０−２の演算部１０２は、以下のＳ３５−２−０〜Ｓ３５−２−２の並列処理のため、場合により、それぞれで異なる記憶領域上に展開された左構造体中の先方出現件数を使用する。言い換えれば、並列処理のため、場合により、ノード０の右構造体との比較用の左構造体中の先方出現件数と、ノード１の右構造体との比較用の左構造体中の先方出現件数と、ノード２の右構造体との比較用の左構造体中の先方出現件数とを使用する。なお、Ｇｌｏｂａｌ  Ｌ演算が上述した特徴１を有することにより、以下のＳ３５−２−０〜Ｓ３５−２−２は順不同である。
【００７９】
Ｓ３５−２−０）データ処理装置１０−２の演算部１０２は、自ノードの左構造体のキー列中のキー「２」と、ノード０の右構造体のキー列中のキー「０」とを比較する。この場合、キー比較条件"＞"が成り立つため、当該演算部１０２は、右構造体のキー「０」に対応するヒット件数「２」を、左構造体のキー「２」に対応する先方出現件数に加算する。そして、当該演算部１０２は、右構造体の参照位置を一つ下げることになるが、これ以上、参照位置を下げることはできないため、Ｌ演算を終了する。これにより、左構造体の先方出現件数が「０」から「２」に更新される。
【００８０】
Ｓ３５−２−１）データ処理装置１０−２の演算部１０２は、自ノードの左構造体のキー列中のキー「２」と、ノード１の右構造体のキー列中のキー「１」とを比較する。この場合、キー比較条件"＞"が成り立つため、当該演算部１０２は、右構造体のキー「１」に対応するヒット件数「１」を、左構造体のキー「２」に対応する先方出現件数に加算する。そして、当該演算部１０２は、右構造体の参照位置を一つ下げることになるが、これ以上、参照位置を下げることはできないため、Ｌ演算を終了する。これにより、左構造体の先方出現件数が「０」から「１」に更新される。
【００８１】
Ｓ３５−２−２）データ処理装置１０−２の演算部１０２は、自ノードの左構造体のキー列中のキー「２」と、自ノード（ノード２）の右構造体のキー列中のキー「２」とを比較する。この場合、キー比較条件"＞"が成り立たないため、当該演算部１０２は、左構造体の操作位置を一つ下げることになるが、これ以上、操作位置を下げることはできないため、Ｌ演算を終了する。
【００８２】
Ｓ３６−２）次に、データ処理装置１０−２の演算部１０２は、左構造体の先方出現件数の合計を算出する。すなわち、データ処理装置１０−２の演算部１０２は、ノード０の右構造体との比較用の左構造体と、ノード１の右構造体との比較用の左構造体と、ノード２の右構造体との比較用の左構造体とで先方出現件数の合計を算出する。この合計が、ノード２のＧＯｒｄの開始番号となる。この場合、先方出現件数の合計は「３」であるため、ノード２のＧＯｒｄの開始番号は「３」となる。
【００８３】
Ｓ３７−２）次に、データ処理装置１０−２の演算部１０２は、自ノードのＧＯｒｄの開始番号を用いて、上記のＳ３１で作成した自ノードのＧＯｒｄリストを更新する。すなわち、データ処理装置１０−２の演算部１０２は、開始番号から開始して、上から順に１つずつ加算した値をＧＯｒｄリストに格納する。これにより、ノード２のＧＯｒｄリストには、格納位置「０」にＧＯｒｄ「３」、格納位置「１」にＧＯｒｄ「４」、格納位置「２」にＧＯｒｄ「５」が格納される。
【００８４】
以上により、上記のＳ３１で作成された各ＧＯｒｄリストに対してＧＯｒｄが格納される。これにより、各データ処理装置１０で検索されたレコードに対してＧＯｒｄが付与された検索結果が得られる。
【００８５】
＜集計＞
次に、データ処理の一例として、Ｇｅｎｄｅｒ（以降、「性別」とも表す。）毎のＡｇｅ（以降、「年齢」とも表す。）の合計を集計する場合について、図１５乃至図１６を参照しながら説明する。図１５乃至図１６は、集計の一例を説明するための図である。
【００８６】
Ｓ４１）まず、各データ処理装置１０の演算部１０２は、自ノード内で性別毎の年齢の合計を集計して、右構造体を作成する。すなわち、各データ処理装置１０の演算部１０２は、自身の記憶部１０３に記憶されている部分テーブルにおいて、性別（Ｇｅｎｄｅｒ）毎に、年齢（Ａｇｅ）の合計を算出する。そして、各データ処理装置１０の演算部１０２は、性別を「キー列」、当該性別の年齢の合計を「年齢合計」として右構造体を作成する。
【００８７】
これにより、データ処理装置１０−０（ノード０）では、キー「Ｆ」と年齢合計「１６」と対応付けられた行と、キー「Ｍ」と年齢合計「１２」とが対応付けられた行とで構成される２行の右構造体が作成される。同様に、データ処理装置１０−１（ノード１）では、キー「Ｆ」と年齢合計「７」と対応付けられた行と、キー「Ｍ」と年齢合計「２１」とが対応付けられた行とで構成される２行の右構造体が作成される。データ処理装置１０−２（ノード２）では、キー「Ｆ」と年齢合計「２２」と対応付けられた行と、キー「Ｍ」と年齢合計「８」とが対応付けられた行とで構成される２行の右構造体が作成される。
【００８８】
Ｓ４２）次に、各データ処理装置１０の演算部１０２は、左構造体を作成する。すなわち、各データ処理装置１０の演算部１０２は、性別を「キー列」、当該性別の年齢の合計の初期値「０」を「年齢合計」として左構造体を作成する。
【００８９】
これにより、データ処理装置１０−０（ノード０）では、キー「Ｆ」と年齢合計「０」と対応付けられた行と、キー「Ｍ」と年齢合計「０」とが対応付けられた行とで構成される２行の右構造体が作成される。データ処理装置１０−１（ノード１）及びデータ処理装置１０−２（ノード２）についても同様に２行の右構造体が作成される。
【００９０】
Ｓ４３）次に、各データ処理装置１０の通信部１０１は、上記のＳ４１で作成した右構造体を相互に交換する。すなわち、各データ処理装置１０の通信部１０１は、自ノードの右構造体を他の全てのノードに送信すると共に、他の全てのノードから送信された右構造体を受信する。なお、このＳ４３は、上記のＳ４１の直後に実行されても良い。
【００９１】
ｋ＝０，１，２として、以降のＳ４４−ｋ〜Ｓ４５−ｋはノードｋで実行される。各ノードは、これらを独立に実行することができる。これは、Ｇｌｏｂａｌ  Ｌ演算が上述した特徴２を有するためである。
【００９２】
Ｓ４４−ｋ）データ処理装置１０−ｋ（ノードｋ）の演算部１０２は、キー比較条件"＝"によりＬ演算を実行する。具体的には、データ処理装置１０−ｋの演算部１０２は、以下のＳ４４−ｋ−０〜Ｓ４４−ｋ−２を実行する。ここで、データ処理装置１０−ｋの演算部１０２は、以下のＳ４４−ｋ−０〜Ｓ４４−ｋ−２の並列処理のため、場合により、それぞれで異なる記憶領域上に展開された左構造体中の年齢合計を使用する。言い換えれば、並列処理のため、場合により、ノード０の右構造体との比較用の左構造体中の年齢合計と、ノード１の右構造体との比較用の左構造体中の年齢合計と、ノード２の右構造体との比較用の左構造体中の年齢合計とを使用する。なお、Ｇｌｏｂａｌ  Ｌ演算が上述した特徴１を有することにより、以下のＳ４４−ｋ−０〜Ｓ４４−ｋ−２は順不同である。
【００９３】
Ｓ４４−ｋ−０）データ処理装置１０−ｋの演算部１０２は、自ノードの左構造体のキー列中のキー「Ｆ」と、ノード０の右構造体のキー列中のキー「Ｆ」とを比較する。この場合、キー比較条件"＝"が成り立つため、当該演算部１０２は、右構造体のキー「Ｆ」に対応する年齢合計「１６」を、左構造体のキー「Ｆ」に対応する年齢合計に加算した上で、右構造体の参照位置と左構造体の操作位置とを一つ下げる。これにより、左構造体の操作位置「０」の年齢合計（性別「Ｆ」の年齢合計）が「１６」に更新されると共に、右構造体の参照位置が「０」から「１」に、左構造体の操作位置が「０」から「１」に更新される。
【００９４】
次に、データ処理装置１０−ｋの演算部１０２は、自ノードの左構造体のキー列中のキー「Ｍ」と、ノード０の右構造体のキー列中のキー「Ｍ」とを比較する。この場合、キー比較条件"＝"が成り立つため、当該演算部１０２は、右構造体のキー「Ｍ」に対応する年齢合計「１２」を、左構造体のキー「Ｍ」に対応する年齢合計に加算した上で、右構造体の参照位置と左構造体の操作位置とを一つ下げることになるが、これ以上、操作位置及び参照位置を下げることはできないため、Ｌ演算を終了する。これにより、左構造体の操作位置「０」の年齢合計（性別「Ｍ」の年齢合計）が「１２」に更新される。
【００９５】
Ｓ４４−ｋ−１）データ処理装置１０−ｋの演算部１０２は、上記のＳ４４−ｋ−０と同様に、キー比較条件"＝"によりＬ演算を行う。これにより、左構造体の性別「Ｆ」の年齢合計が「７」、性別「Ｍ」の年齢合計が「２１」に更新される。
【００９６】
Ｓ４４−ｋ−２）データ処理装置１０−ｋの演算部１０２は、上記のＳ４４−ｋ−０と同様に、キー比較条件"＝"によりＬ演算を行う。これにより、左構造体の性別「Ｆ」の年齢合計が「２２」、性別「Ｍ」の年齢合計が「８」に更新される。
【００９７】
Ｓ４５−ｋ）次に、データ処理装置１０−ｋの演算部１０２は、性別毎に年齢合計の合計を算出する。すなわち、データ処理装置１０−ｋの演算部１０２は、ノード０の右構造体との比較用の左構造体と、ノード１の右構造体との比較用の左構造体と、ノード２の右構造体との比較用の左構造体とで、性別毎に年齢合計の合計を算出する。これにより、性別「Ｆ」と年齢合計「４５」とが対応付けられた行と、性別「Ｍ」と年齢合計「４１」とが対応付けられた行とで構成される左構造体が得られる。
【００９８】
以上により、各ノードｋ（ｋ＝０，１，２）で同一の集計結果（性別毎の年齢合計）が得られる。
【００９９】
＜単項目ソート＞
次に、データ処理の一例として、性別（Ｇｅｎｄｅｒ）の単項目でソートする場合について、図１７乃至図２０を参照しながら説明する。図１７乃至図２０は、単項目ソートの一例を説明するための図である。なお、以降では、性別「Ｆ」及び「Ｍ」の大小関係はＦ＜Ｍであるものとして、性別の単項目で昇順ソートする場合について説明する。ただし、性別「Ｆ」及び「Ｍ」の大小関係をＦ＞Ｍであるものとして、性別の単項目で降順ソートする場合としても良い。
【０１００】
Ｓ５１）まず、各データ処理装置１０の演算部１０２は、自ノード内で、性別でソートする。すなわち、各データ処理装置１０の演算部１０２は、自身の記憶部１０３に記憶されている部分テーブルのレコード番号リストを性別でソートする。
【０１０１】
そして、各データ処理装置１０の演算部１０２は、ソート後のレコード番号が格納されるレコード番号リストと、空値（ＮＵＬＬ値）が格納されたＧＯｒｄリストとを作成する。
【０１０２】
これにより、データ処理装置１０−０（ノード０）では、レコード番号が「０」、「３」、「１」、「２」の順にソートされたレコード番号リストと、これらのレコード番号に対応する空値が格納されたＧＯｒｄリストとが作成される。同様に、データ処理装置１０−１（ノード１）では、レコード番号が「２」、「０」、「１」、「３」の順にソートされたレコード番号リストと、これらのレコード番号に対応する空値が格納されたＧＯｒｄリストとが作成される。同様に、データ処理装置１０−２（ノード２）では、レコード番号が「０」、「１」、「２」、「３」の順にソートされたレコード番号リストと、これらのレコード番号に対応する空値が格納されたＧＯｒｄリストとが作成される。
【０１０３】
Ｓ５２）次に、各データ処理装置１０の演算部１０２は、右構造体を作成する。すなわち、各データ処理装置１０の演算部１０２は、性別と自ノードのノード番号とを「キー列」、当該性別のレコード件数を「出現数」として右構造体を作成する。これにより、データ処理装置１０−０（ノード０）では、キー「Ｆ」及び「０」と出現数「２」とが対応付けられた行と、キー「Ｍ」及び「０」と出現数「２」とが対応付けられた行とで構成される２行の右構造体が作成される。同様に、データ処理装置１０−１（ノード１）では、キー「Ｆ」及び「１」と出現数「１」とが対応付けられた行と、キー「Ｍ」及び「１」と出現数「３」とが対応付けられた行とで構成される２行の右構造体が作成される。同様に、データ処理装置１０−２（ノード２）では、キー「Ｆ」及び「２」と出現数「３」とが対応付けられた行と、キー「Ｍ」及び「２」と出現数「１」とが対応付けられた行とで構成される２行の右構造体が作成される。
【０１０４】
なお、ノード番号は、１つの左構造体又は右構造体中で全て同一であるため、左構造体及び右構造体のレコード数分繰り返して記憶させる必要は無く、メモリ量及び通信量削減のため、左構造体及び右構造体中の１つの領域に記憶させるだけでも良い。
【０１０５】
Ｓ５３）次に、各データ処理装置１０の演算部１０２は、左構造体を作成する。すなわち、各データ処理装置１０の演算部１０２は、上記のＳ５２で作成した右構造体の全ての出現数を０として、「出現数」を「前方存在数」とした左構造体を作成する。
【０１０６】
Ｓ５４）次に、各データ処理装置１０の通信部１０１は、上記のＳ５２で作成した右構造体を相互に交換する。すなわち、各データ処理装置１０の通信部１０１は、自ノードの右構造体を他の全てのノードに送信すると共に、他の全てのノードから送信された右構造体を受信する。なお、このＳ５４は、上記のＳ５２の直後に実行されても良い。
【０１０７】
以降のＳ５５−０〜Ｓ５８−０はノード０で実行され、Ｓ５５−１〜Ｓ５８−１はノード１で実行され、Ｓ５５−２〜Ｓ５８−２はノード２で実行されるが、各ノードは、これらを独立に実行することができる。これは、Ｇｌｏｂａｌ  Ｌ演算が上述した特徴２を有するためである。
【０１０８】
Ｓ５５−０）データ処理装置１０−０の演算部１０２は、キー比較条件"＞"によりＬ演算を実行する。具体的には、データ処理装置１０−０の演算部１０２は、以下のＳ５５−０−０〜Ｓ５５−０−２を実行する。ここで、データ処理装置１０−０の演算部１０２は、以下のＳ５５−０−０〜Ｓ５５−０−２の並列処理のため、場合により、それぞれで異なる記憶領域上に展開された左構造体中の前方存在数を使用する。言い換えれば、並列処理のため、場合により、ノード０の右構造体との比較用の左構造体中の前方存在数と、ノード１の右構造体との比較用の左構造体中の前方存在数と、ノード２の右構造体との比較用の左構造体中の前方存在数とを使用する。なお、Ｇｌｏｂａｌ  Ｌ演算が上述した特徴１を有することにより、以下のＳ５５−０−０〜Ｓ５５−０−２は順不同である。
【０１０９】
Ｓ５５−０−０）データ処理装置１０−０の演算部１０２は、自ノードの左構造体のキー列中のキー「Ｆ」及び「０」と、自ノード（ノード０）の右構造体のキー列中のキー「Ｆ」及び「０」とを比較する。この場合、キー比較条件"＞"が成り立たないため、当該演算部１０２は、左構造体の操作位置を一つ下げる。これにより、左構造体の操作位置が「０」から「１」に更新される。
【０１１０】
次に、データ処理装置１０−０の演算部１０２は、自ノードの左構造体のキー列中のキー「Ｍ」及び「０」と、自ノード（ノード０）の右構造体のキー列中のキー「Ｆ」及び「０」とを比較する。この場合、キー比較条件"＞"が成り立つため、当該演算部１０２は、右構造体のキー「Ｆ」及び「０」に対応する出現数「２」を、左構造体のキー「Ｍ」及び「０」に対応する前方存在数に加算した上で、右構造体の参照位置を一つ下げる。これにより、左構造体の操作位置「１」の前方存在数が「０」から「２」に更新されると共に、右構造体の参照位置が「０」から「１」に更新される。
【０１１１】
次に、データ処理装置１０−０の演算部１０２は、自ノードの左構造体のキー列中のキー「Ｍ」及び「０」と、自ノード（ノード０）の右構造体のキー列中のキー「Ｍ」及び「０」とを比較する。この場合、キー比較条件"＞"が成り立たないため、当該演算部１０２は、左構造体の操作位置を一つ下げることになるが、これ以上、操作位置を下げることはできないため、Ｌ演算を終了する。
【０１１２】
Ｓ５５−０−１）データ処理装置１０−０の演算部１０２は、自ノードの左構造体のキー列中のキー「Ｆ」及び「０」と、ノード１の右構造体のキー列中のキー「Ｆ」及び「１」とを比較する。この場合、キー比較条件"＞"が成り立たないため、当該演算部１０２は、左構造体の操作位置を一つ下げる。これにより、左構造体の操作位置が「０」から「１」に更新される。
【０１１３】
次に、データ処理装置１０−０の演算部１０２は、自ノードの左構造体のキー列中のキー「Ｍ」及び「０」と、ノード１の右構造体のキー列中のキー「Ｆ」及び「１」とを比較する。この場合、キー比較条件"＞"が成り立つため、当該演算部１０２は、右構造体のキー「Ｆ」及び「１」に対応する出現数「１」を、左構造体のキー「Ｍ」及び「０」に対応する前方存在数に加算した上で、右構造体の参照位置を一つ下げる。これにより、左構造体の操作位置「１」の前方存在数が「０」から「１」に更新されると共に、右構造体の参照位置が「０」から「１」に更新される。
【０１１４】
次に、データ処理装置１０−０の演算部１０２は、自ノードの左構造体のキー列中のキー「Ｍ」及び「０」と、ノード１の右構造体のキー列中のキー「Ｍ」及び「１」とを比較する。この場合、キー比較条件"＞"が成り立たないため、当該演算部１０２は、左構造体の操作位置を一つ下げることになるが、これ以上、操作位置を下げることはできないため、Ｌ演算を終了する。
【０１１５】
Ｓ５５−０−２）データ処理装置１０−０の演算部１０２は、自ノードの左構造体のキー列中のキー「Ｆ」及び「０」と、ノード２の右構造体のキー列中のキー「Ｆ」及び「２」とを比較する。この場合、キー比較条件"＞"が成り立たないため、当該演算部１０２は、左構造体の操作位置を一つ下げる。これにより、左構造体の操作位置が「０」から「１」に更新される。
【０１１６】
次に、データ処理装置１０−０の演算部１０２は、自ノードの左構造体のキー列中のキー「Ｍ」及び「０」と、ノード２の右構造体のキー列中のキー「Ｆ」及び「２」とを比較する。この場合、キー比較条件"＞"が成り立つため、当該演算部１０２は、右構造体のキー「Ｆ」及び「２」に対応する出現数「３」を、左構造体のキー「Ｍ」及び「０」に対応する前方存在数に加算した上で、右構造体の参照位置を一つ下げる。これにより、左構造体の操作位置「１」の前方存在数が「０」から「３」に更新されると共に、右構造体の参照位置が「０」から「１」に更新される。
【０１１７】
次に、データ処理装置１０−０の演算部１０２は、自ノードの左構造体のキー列中のキー「Ｍ」及び「０」と、ノード２の右構造体のキー列中のキー「Ｍ」及び「２」とを比較する。この場合、キー比較条件"＞"が成り立たないため、当該演算部１０２は、左構造体の操作位置を一つ下げることになるが、これ以上、操作位置を下げることはできないため、Ｌ演算を終了する。
【０１１８】
Ｓ５６−０）次に、データ処理装置１０−０の演算部１０２は、左構造体の前方存在数の合計を算出する。すなわち、データ処理装置１０−０の演算部１０２は、ノード０の右構造体との比較用の左構造体と、ノード１の右構造体との比較用の左構造体と、ノード２の右構造体との比較用の左構造体とで前方存在数の合計を算出する。これにより、性別「Ｆ」に対応する前方存在数（の合計）は「０」、性別「Ｍ」に対応する前方存在数（の合計）は「６」となる。
【０１１９】
Ｓ５７−０）次に、データ処理装置１０−０の演算部１０２は、上記のＳ５６−０で算出した前方存在数（の合計）を累計化する。すなわち、データ処理装置１０−０の演算部１０２は、性別「Ｆ」に対応する前方存在数はそのままとする一方で、性別「Ｍ」に対応する前方存在数を、性別「Ｆ」に対応する前方存在数＋性別「Ｍ」に対応する前方存在数とする。
【０１２０】
これにより、性別「Ｆ」に対応する前方存在数は「０」、性別「Ｍ」に対応する前方存在数は「６」となる。この前方存在数が、ノード０における性別毎のＧＯｒｄの開始番号となる。この場合、ノード０の性別「Ｆ」のＧＯｒｄの開始番号は「０」、性別「Ｍ」のＧＯｒｄの開始番号は「６」となる。
【０１２１】
Ｓ５８−０）次に、データ処理装置１０−０の演算部１０２は、上記のＳ５７−０で累計化した前方存在数と、上記のＳ５２で得られた出現数とを用いて、上記のＳ５１で作成した自ノードのＧＯｒｄリストを更新する。すなわち、データ処理装置１０−０の演算部１０２は、性別毎に、前方存在数から開始して、出現数回、上から順に１つずつ加算した値をＧＯｒｄリストに格納する。これにより、ノード０のＧＯｒｄリストには、格納位置「０」にＧＯｒｄ「０」、格納位置「１」にＧＯｒｄ「１」、格納位置「２」にＧＯｒｄ「６」、格納位置「３」にＧＯｒｄ「７」が格納される。
【０１２２】
Ｓ５５−１）データ処理装置１０−１の演算部１０２は、キー比較条件"＞"によりＬ演算を実行する。具体的には、データ処理装置１０−１の演算部１０２は、以下のＳ５５−１−０〜Ｓ５５−１−２を実行する。ここで、データ処理装置１０−１の演算部１０２は、以下のＳ５５−１−０〜Ｓ５５−１−２の並列処理のため、場合により、それぞれで異なる記憶領域上に展開された左構造体中の前方存在数を使用する。言い換えれば、並列処理のため、場合により、ノード０の右構造体との比較用の左構造体中の前方存在数と、ノード１の右構造体との比較用の左構造体中の前方存在数と、ノード２の右構造体との比較用の左構造体中の前方存在数とを使用する。なお、Ｇｌｏｂａｌ  Ｌ演算が上述した特徴１を有することにより、以下のＳ５５−１−０〜Ｓ５５−１−２は順不同である。
【０１２３】
Ｓ５５−１−０）データ処理装置１０−１の演算部１０２は、自ノードの左構造体のキー列中のキー「Ｆ」及び「１」と、ノード０の右構造体のキー列中のキー「Ｆ」及び「０」とを比較する。この場合、キー比較条件"＞"が成り立つため、当該演算部１０２は、右構造体のキー「Ｆ」及び「０」に対応する出現数「２」を、左構造体のキー「Ｆ」及び「１」に対応する前方存在数に加算した上で、右構造体の参照位置を一つ下げる。これにより、左構造体の操作位置「０」の前方存在数が「０」から「２」に更新されると共に、右構造体の参照位置が「０」から「１」に更新される。
【０１２４】
次に、データ処理装置１０−１の演算部１０２は、自ノードの左構造体のキー列中のキー「Ｆ」及び「１」と、ノード０の右構造体のキー列中のキー「Ｍ」及び「０」とを比較する。この場合、キー比較条件"＞"が成り立たないため、当該演算部１０２は、左構造体の操作位置を一つ下げる。これにより、左構造体の操作位置が「０」から「１」に更新される。
【０１２５】
次に、データ処理装置１０−１の演算部１０２は、自ノードの左構造体のキー列中のキー「Ｍ」及び「１」と、ノード０の右構造体のキー列中のキー「Ｍ」及び「０」とを比較する。この場合、キー比較条件"＞"が成り立つため、当該演算部１０２は、右構造体のキー「Ｍ」及び「０」に対応する出現数「２」を、左構造体のキー「Ｍ」及び「１」に対応する前方存在数に加算する。そして、当該演算部１０２は、右構造体の参照位置を一つ下げることになるが、これ以上、参照位置を下げることはできないため、Ｌ演算を終了する。これにより、左構造体の操作位置「１」の前方存在数が「０」から「２」に更新される。
【０１２６】
Ｓ５５−１−１）データ処理装置１０−１の演算部１０２は、自ノードの左構造体のキー列中のキー「Ｆ」及び「１」と、自ノード（ノード１）の右構造体のキー列中のキー「Ｆ」及び「１」とを比較する。この場合、キー比較条件"＞"が成り立たないため、当該演算部１０２は、左構造体の操作位置を一つ下げる。これにより、左構造体の操作位置が「０」から「１」に更新される。
【０１２７】
次に、データ処理装置１０−１の演算部１０２は、自ノードの左構造体のキー列中のキー「Ｍ」及び「１」と、自ノード（ノード１）の右構造体のキー列中のキー「Ｆ」及び「１」とを比較する。この場合、キー比較条件"＞"が成り立つため、当該演算部１０２は、右構造体のキー「Ｆ」及び「１」に対応する出現数「１」を、左構造体のキー「Ｍ」及び「１」に対応する前方存在数に加算した上で、右構造体の参照位置を一つ下げる。これにより、左構造体の操作位置「１」の前方存在数が「０」から「１」に更新されると共に、右構造体の参照位置が「０」から「１」に更新される。
【０１２８】
次に、データ処理装置１０−１の演算部１０２は、自ノードの左構造体のキー列中のキー「Ｍ」及び「１」と、自ノード（ノード１）の右構造体のキー列中のキー「Ｍ」及び「１」とを比較する。この場合、キー比較条件"＞"が成り立たないため、当該演算部１０２は、左構造体の操作位置を一つ下げることになるが、これ以上、操作位置を下げることはできないため、Ｌ演算を終了する。
【０１２９】
Ｓ５５−１−２）データ処理装置１０−１の演算部１０２は、自ノードの左構造体のキー列中のキー「Ｆ」及び「１」と、ノード２の右構造体のキー列中のキー「Ｆ」及び「２」とを比較する。この場合、キー比較条件"＞"が成り立たないため、当該演算部１０２は、左構造体の操作位置を一つ下げる。これにより、左構造体の操作位置が「０」から「１」に更新される。
【０１３０】
次に、データ処理装置１０−１の演算部１０２は、自ノードの左構造体のキー列中のキー「Ｍ」及び「１」と、ノード２の右構造体のキー列中のキー「Ｆ」及び「２」とを比較する。この場合、キー比較条件"＞"が成り立つため、当該演算部１０２は、右構造体のキー「Ｆ」及び「２」に対応する出現数「３」を、左構造体のキー「Ｍ」及び「１」に対応する前方存在数に加算した上で、右構造体の参照位置を一つ下げる。これにより、左構造体の操作位置「１」の前方存在数が「０」から「３」に更新されると共に、右構造体の参照位置が「０」から「１」に更新される。
【０１３１】
次に、データ処理装置１０−１の演算部１０２は、自ノードの左構造体のキー列中のキー「Ｍ」及び「１」と、ノード２の右構造体のキー列中のキー「Ｍ」及び「２」とを比較する。この場合、キー比較条件"＞"が成り立たないため、当該演算部１０２は、左構造体の操作位置を一つ下げることになるが、これ以上、操作位置を下げることはできないため、Ｌ演算を終了する。
【０１３２】
Ｓ５６−１）次に、データ処理装置１０−１の演算部１０２は、左構造体の前方存在数の合計を算出する。すなわち、データ処理装置１０−１の演算部１０２は、ノード０の右構造体との比較用の左構造体と、ノード１の右構造体との比較用の左構造体と、ノード２の右構造体との比較用の左構造体とで前方存在数の合計を算出する。これにより、性別「Ｆ」に対応する前方存在数（の合計）は「２」、性別「Ｍ」に対応する前方存在数（の合計）は「６」となる。
【０１３３】
Ｓ５７−１）次に、データ処理装置１０−１の演算部１０２は、上記のＳ５６−１で算出した前方存在数（の合計）を累計化する。すなわち、データ処理装置１０−１の演算部１０２は、性別「Ｆ」に対応する前方存在数はそのままとする一方で、性別「Ｍ」に対応する前方存在数を、性別「Ｆ」に対応する前方存在数＋性別「Ｍ」に対応する前方存在数とする。
【０１３４】
これにより、性別「Ｆ」に対応する前方存在数は「２」、性別「Ｍ」に対応する前方存在数は「８」となる。この前方存在数が、ノード１における性別毎のＧＯｒｄの開始番号となる。この場合、ノード１の性別「Ｆ」のＧＯｒｄの開始番号は「２」、性別「Ｍ」のＧＯｒｄの開始番号は「８」となる。
【０１３５】
Ｓ５８−１）次に、データ処理装置１０−１の演算部１０２は、上記のＳ５７−１で累計化した前方存在数と、上記のＳ５２で得られた出現数とを用いて、上記のＳ５１で作成した自ノードのＧＯｒｄリストを更新する。すなわち、データ処理装置１０−１の演算部１０２は、性別毎に、前方存在数から開始して、出現数回、上から順に１つずつ加算した値をＧＯｒｄリストに格納する。これにより、ノード１のＧＯｒｄリストには、格納位置「０」にＧＯｒｄ「２」、格納位置「１」にＧＯｒｄ「８」、格納位置「２」にＧＯｒｄ「９」、格納位置「３」にＧＯｒｄ「１０」が格納される。
【０１３６】
Ｓ５５−２）データ処理装置１０−２の演算部１０２は、キー比較条件"＞"によりＬ演算を実行する。具体的には、データ処理装置１０−２の演算部１０２は、以下のＳ５５−２−０〜Ｓ５５−２−２を実行する。ここで、データ処理装置１０−２の演算部１０２は、以下のＳ５５−２−０〜Ｓ５５−２−２の並列処理のため、場合により、それぞれで異なる記憶領域上に展開された左構造体中の前方存在数を使用する。言い換えれば、並列処理のため、場合により、ノード０の右構造体との比較用の左構造体中の前方存在数と、ノード１の右構造体との比較用の左構造体中の前方存在数と、ノード２の右構造体との比較用の左構造体中の前方存在数とを使用する。なお、Ｇｌｏｂａｌ  Ｌ演算が上述した特徴１を有することにより、以下のＳ５５−２−０〜Ｓ５５−２−２は順不同である。
【０１３７】
Ｓ５５−２−０）データ処理装置１０−２の演算部１０２は、自ノードの左構造体のキー列中のキー「Ｆ」及び「２」と、ノード０の右構造体のキー列中のキー「Ｆ」及び「０」とを比較する。この場合、キー比較条件"＞"が成り立つため、当該演算部１０２は、右構造体のキー「Ｆ」及び「０」に対応する出現数「２」を、左構造体のキー「Ｆ」及び「２」に対応する前方存在数に加算した上で、右構造体の参照位置を一つ下げる。これにより、左構造体の操作位置「０」の前方存在数が「０」から「２」に更新されると共に、右構造体の参照位置が「０」から「１」に更新される。
【０１３８】
次に、データ処理装置１０−２の演算部１０２は、自ノードの左構造体のキー列中のキー「Ｆ」及び「２」と、ノード０の右構造体のキー列中のキー「Ｍ」及び「０」とを比較する。この場合、キー比較条件"＞"が成り立たないため、当該演算部１０２は、左構造体の操作位置を一つ下げる。これにより、左構造体の操作位置が「０」から「１」に更新される。
【０１３９】
次に、データ処理装置１０−２の演算部１０２は、自ノードの左構造体のキー列中のキー「Ｍ」及び「２」と、ノード０の右構造体のキー列中のキー「Ｍ」及び「０」とを比較する。この場合、キー比較条件"＞"が成り立つため、当該演算部１０２は、右構造体のキー「Ｍ」及び「２」に対応する出現数「２」を、左構造体のキー「Ｍ」及び「２」に対応する前方存在数に加算する。そして、当該演算部１０２は、右構造体の参照位置を一つ下げることになるが、これ以上、参照位置を下げることはできないため、Ｌ演算を終了する。これにより、左構造体の操作位置「１」の前方存在数が「０」から「２」に更新される。
【０１４０】
Ｓ５５−２−１）データ処理装置１０−２の演算部１０２は、自ノードの左構造体のキー列中のキー「Ｆ」及び「２」と、ノード１の右構造体のキー列中のキー「Ｆ」及び「１」とを比較する。この場合、キー比較条件"＞"が成り立つため、当該演算部１０２は、右構造体のキー「Ｆ」及び「１」に対応する出現数「１」を、左構造体のキー「Ｆ」及び「２」に対応する前方存在数に加算した上で、右構造体の参照位置を一つ下げる。これにより、左構造体の操作位置「０」の前方存在数が「０」から「１」に更新されると共に、右構造体の参照位置が「０」から「１」に更新される。
【０１４１】
次に、データ処理装置１０−２の演算部１０２は、自ノードの左構造体のキー列中のキー「Ｆ」及び「２」と、ノード１の右構造体のキー列中のキー「Ｍ」及び「１」とを比較する。この場合、キー比較条件"＞"が成り立たないため、当該演算部１０２は、左構造体の操作位置を一つ下げる。これにより、左構造体の操作位置が「０」から「１」に更新される。
【０１４２】
次に、データ処理装置１０−２の演算部１０２は、自ノードの左構造体のキー列中のキー「Ｍ」及び「２」と、ノード１の右構造体のキー列中のキー「Ｍ」及び「１」とを比較する。この場合、キー比較条件"＞"が成り立つため、当該演算部１０２は、右構造体のキー「Ｍ」及び「１」に対応する出現数「３」を、左構造体のキー「Ｍ」及び「２」に対応する前方存在数に加算する。そして、当該演算部１０２は、右構造体の参照位置を一つ下げることになるが、これ以上、参照位置を下げることはできないため、Ｌ演算を終了する。これにより、左構造体の操作位置「１」の前方存在数が「０」から「３」に更新される。
【０１４３】
Ｓ５５−２−２）データ処理装置１０−２の演算部１０２は、自ノードの左構造体のキー列中のキー「Ｆ」及び「２」と、自ノード（ノード２）の右構造体のキー列中のキー「Ｆ」及び「２」とを比較する。この場合、キー比較条件"＞"が成り立たないため、当該演算部１０２は、左構造体の操作位置を一つ下げる。これにより、左構造体の操作位置が「０」から「１」に更新される。
【０１４４】
次に、データ処理装置１０−２の演算部１０２は、自ノードの左構造体のキー列中のキー「Ｍ」及び「２」と、自ノード（ノード２）の右構造体のキー列中のキー「Ｆ」及び「２」とを比較する。この場合、キー比較条件"＞"が成り立つため、当該演算部１０２は、右構造体のキー「Ｆ」及び「２」に対応する出現数「３」を、左構造体のキー「Ｍ」及び「２」に対応する前方存在数に加算した上で、右構造体の参照位置を一つ下げる。これにより、左構造体の操作位置「１」の前方存在数が「０」から「３」に更新されると共に、右構造体の参照位置が「０」から「１」に更新される。
【０１４５】
次に、データ処理装置１０−２の演算部１０２は、自ノードの左構造体のキー列中のキー「Ｍ」及び「２」と、自ノード（ノード２）の右構造体のキー列中のキー「Ｍ」及び「２」とを比較する。この場合、キー比較条件"＞"が成り立たないため、当該演算部１０２は、左構造体の操作位置を一つ下げることになるが、これ以上、操作位置を下げることはできないため、Ｌ演算を終了する。
【０１４６】
Ｓ５６−２）次に、データ処理装置１０−２の演算部１０２は、左構造体の前方存在数の合計を算出する。すなわち、データ処理装置１０−２の演算部１０２は、ノード０の右構造体との比較用の左構造体と、ノード１の右構造体との比較用の左構造体と、ノード２の右構造体との比較用の左構造体とで前方存在数の合計を算出する。これにより、性別「Ｆ」に対応する前方存在数（の合計）は「３」、性別「Ｍ」に対応する前方存在数（の合計）は「８」となる。
【０１４７】
Ｓ５７−２）次に、データ処理装置１０−２の演算部１０２は、上記のＳ５６−２で算出した前方存在数（の合計）を累計化する。すなわち、データ処理装置１０−２の演算部１０２は、性別「Ｆ」に対応する前方存在数はそのままとする一方で、性別「Ｍ」に対応する前方存在数を、性別「Ｆ」に対応する前方存在数＋性別「Ｍ」に対応する前方存在数とする。
【０１４８】
これにより、性別「Ｆ」に対応する前方存在数は「３」、性別「Ｍ」に対応する前方存在数は「１１」となる。この前方存在数が、ノード２における性別毎のＧＯｒｄの開始番号となる。この場合、ノード２の性別「Ｆ」のＧＯｒｄの開始番号は「３」、性別「Ｍ」のＧＯｒｄの開始番号は「１１」となる。
【０１４９】
Ｓ５８−２）次に、データ処理装置１０−２の演算部１０２は、上記のＳ５７−２で累計化した前方存在数と、上記のＳ５２で得られた出現数とを用いて、上記のＳ５１で作成した自ノードのＧＯｒｄリストを更新する。すなわち、データ処理装置１０−２の演算部１０２は、性別毎に、前方存在数から開始して、出現数回、上から順に１つずつ加算した値をＧＯｒｄリストに格納する。これにより、ノード２のＧＯｒｄリストには、格納位置「０」にＧＯｒｄ「３」、格納位置「１」にＧＯｒｄ「４」、格納位置「２」にＧＯｒｄ「５」、格納位置「３」にＧＯｒｄ「１１」が格納される。
【０１５０】
以上により、上記のＳ５１で作成された各ＧＯｒｄリストに対してＧＯｒｄが格納される。これにより、各データ処理装置１０でＧＯｒｄ（及びレコード番号）が付与された部分テーブルが得られ、このＧＯｒｄによりデータ処理装置１０全体でのソート結果（単項目でのソート結果）が得られる。
【０１５１】
＜複数項目ソート＞
次に、データ処理の一例として、性別及び年齢の複数項目でソートする場合について、図２１を参照しながら説明する。図２１は、複数項目ソートの一例を説明するための図である。
【０１５２】
Ｓ６１）まず、各データ処理装置１０の演算部１０２は、自ノード内で、性別及び年齢でソートする。すなわち、各データ処理装置１０の演算部１０２は、自身の記憶部１０３に記憶されている部分テーブルのレコード番号リストを性別及び年齢でソートする。
【０１５３】
そして、各データ処理装置１０の演算部１０２は、ソート後のレコード番号が格納されたレコード番号リストと、空値（ＮＵＬＬ値）が格納されたＧＯｒｄリストとを作成する。
【０１５４】
これにより、データ処理装置１０−０（ノード０）では、レコード番号が「０」、「３」、「１」、「２」の順にソートされたレコード番号リストと、これらのレコード番号に対応する空値が格納されたＧＯｒｄリストとが作成される。同様に、データ処理装置１０−１（ノード１）では、レコード番号が「２」、「１」、「０」、「３」の順にソートされたレコード番号リストと、これらのレコード番号に対応する空値が格納されたＧＯｒｄリストとが作成される。同様に、データ処理装置１０−２（ノード２）では、レコード番号が「１」、「２」、「０」、「３」の順にソートされたレコード番号リストと、これらのレコード番号に対応する空値が格納されたＧＯｒｄリストとが作成される。
【０１５５】
Ｓ６２）次に、各データ処理装置１０の演算部１０２は、右構造体を作成する。すなわち、各データ処理装置１０の演算部１０２は、性別と年齢と自ノードのノード番号とを「キー列」、当該性別及び当該年齢のレコード件数を「出現数」として右構造体を作成する。これにより、データ処理装置１０−０（ノード０）では、キー「Ｆ」、「８」及び「０」と出現数「２」とが対応付けられた行と、キー「Ｍ」、「６」及び「０」と出現数「２」とが対応付けられた行とで構成される２行の右構造体が作成される。同様に、データ処理装置１０−１（ノード１）では、キー「Ｆ」、「７」及び「１」と出現数「１」とが対応付けられた行と、キー「Ｍ」、「６」及び「１」と出現数「１」とが対応付けられた行と、キー「Ｍ」、「７」及び「１」と出現数「１」とが対応付けられた行と、キー「Ｍ」、「８」及び「１」と出現数「１」とが対応付けられた行とで構成される４行の右構造体が作成される。同様に、データ処理装置１０−２（ノード２）では、キー「Ｆ」、「７」及び「２」と出現数「２」とが対応付けられた行と、キー「Ｆ」、「８」及び「２」と出現数「１」とが対応付けられた行と、キー「Ｍ」、「８」及び「２」と出現数「１」とが対応付けられた行とで構成される３行の右構造体が作成される。
【０１５６】
Ｓ６３）次に、各データ処理装置１０の演算部１０２は、左構造体を作成する。すなわち、各データ処理装置１０の演算部１０２は、上記のＳ６２で作成した右構造体の全ての出現数を０として、「出現数」を「前方存在数」とした左構造体を作成する。
【０１５７】
Ｓ６４）次に、各データ処理装置１０の通信部１０１は、上記のＳ６２で作成した右構造体を相互に交換する。すなわち、各データ処理装置１０の通信部１０１は、自ノードの右構造体を他の全てのノードに送信すると共に、他の全てのノードから送信された右構造体を受信する。なお、このＳ６４は、上記のＳ６２の直後に実行されても良い。
【０１５８】
Ｓ６５）以降、単項目ソートと同様に、ｋ＝０，１，２として、Ｓ５５−ｋ〜Ｓ５８−ｋを実行する。
【０１５９】
以上により、上記のＳ６１で作成された各ＧＯｒｄリストに対してＧＯｒｄが格納される。これにより、各データ処理装置１０でＧＯｒｄ（及びレコード番号）が付与された部分テーブルが得られ、このＧＯｒｄによりデータ処理装置１０全体でのソート結果（複数項目でのソート結果）が得られる。
【０１６０】
＜部分集合でのソート＞
次に、部分集合でのソートについて説明する。部分集合とは、各部分テーブルに対して何等かのデータ処理を行った結果、これらの部分テーブル全体が表す集合（全体集合）の真部分集合や要素間の順序が更新されている集合等のことである。すなわち、本発明の実施の形態における部分集合とは、全体集合の一部となっている集合（真部分集合）だけでなく、全体集合と要素数は同じであるが要素間の順序が当該集合から変更された場合も含む。
【０１６１】
ここで、全体集合と要素数は同じであるが要素間の順序が変更された場合とは、全体集合に対してソート等が行われた場合である。性別でソートした場合の部分集合を図２２に示す。図２２に示すように、本発明の実施の形態では、全体集合と要素数は同じであるが、性別でソートした結果、要素間の順序が変更された場合も部分集合と扱うものとする。
【０１６２】
このような部分集合を表す部分テーブルは、安定性前提が成り立つとは限らない。そこで、以降では、安定性前提が成り立つとは限らない部分テーブルを各ノードが保持している場合でのソートについて説明する。一例として、各ノードが図２２に示す部分テーブルを保持しているものとして、年齢でソートする場合について、図２３乃至図２６を参照しながら説明する。図２３乃至図２６は、部分集合でのソートの一例を説明するための図である。
【０１６３】
Ｓ７１）まず、各データ処理装置１０の演算部１０２は、自ノード内で、年齢でソートする。すなわち、各データ処理装置１０の演算部１０２は、自身の記憶部１０３に記憶されている部分テーブルのレコード番号リストを年齢でソートする。
【０１６４】
そして、各データ処理装置１０の演算部１０２は、ソート後のレコード番号が格納されるレコード番号リストと、当該レコード番号の現在の（ソート前の）ＧＯｒｄ（以降、「ｏｌｄＧＯｒｄ」とも表す。）が格納されたｏｌｄＧＯｒｄリストと、空値（ＮＵＬＬ値）が格納されたＧＯｒｄリストとを作成する。
【０１６５】
これにより、データ処理装置１０−０（ノード０）では、レコード番号が「１」、「２」、「０」、「３」の順にソートされたレコード番号リストと、これのレコード番号に対応するｏｌｄＧＯｒｄが「６」、「７」、「０」、「１」の順に格納されたｏｌｄＧＯｒｄリストと、これらのレコード番号に対応する空値が格納されたＧＯｒｄリストとが作成される。同様に、データ処理装置１０−１（ノード１）では、レコード番号が「１」、「２」、「０」、「３」の順にソートされたレコード番号リストと、これらのレコード番号に対応するｏｌｄＧＯｒｄが「９」、「２」、「８」、「１０」の順に格納されたｏｌｄＧＯｒｄリストと、これらのレコード番号に対応する空値が格納されたＧＯｒｄリストとが作成される。同様に、データ処理装置１０−２（ノード２）では、レコード番号が「１」、「２」、「０」、「３」の順にソートされたレコード番号リストと、これらのレコード番号に対応するｏｌｄＧＯｒｄが「４」、「５」、「３」、「１１」の順に格納井されたｏｌｄＧＯｒｄリストと、これらのレコード番号に対応する空値が格納されたＧＯｒｄリストとが作成される。
【０１６６】
Ｓ７２）次に、各データ処理装置１０の演算部１０２は、右構造体を作成する。すなわち、各データ処理装置１０の演算部１０２は、まず、上記のＳ７２で作成されたｏｌｄＧＯｒｄリストにおいて、同一の年齢が対応付けられており、かつ、ｏｌｄＧＯｒｄが連番となっている範囲（この範囲を「連番範囲」とも表す。）を１つにまとめた上で、この連番範囲の先頭のｏｌｄＧＯｒｄで当該連番範囲を代表させる。そして、各データ処理装置１０の演算部１０２は、年齢と、ｏｌｄＧＯｒｄ又は連番範囲を代表するｏｌｄＧＯｒｄとを「キー列」、１又は当該連番範囲に含まれるｏｌｄＧＯｒｄの数を「出現数」として右構造体を作成する。なお、出現数が「１」は、連番範囲を代表していないｏｌｄＧＯｒｄに対応付けられる。すなわち、出現数は、該当のｏｌｄＧＯｒｄが連番範囲を代表している場合は当該連番範囲に含まれるｏｌｄＧＯｒｄ数、該当のｏｌｄＧＯｒｄが連番範囲を代表していない場合は１（言い換えれば、該当のｏｌｄＧＯｒｄ数）となる。
【０１６７】
これにより、データ処理装置１０−０（ノード０）では、キー「６」及び「６」と出現数「２」とが対応付けられた行と、キー「８」及び「０」と出現数「２」とが対応付けられた行とで構成される２行の右構造体が作成される。同様に、データ処理装置１０−１（ノード１）では、キー「６」及び「９」と出現数「１」とが対応付けられた行と、キー「７」及び「２」と出現数「１」とが対応付けられた行と、キー「７」及び「８」と出現数「１」とが対応付けられた行と、キー「８」及び「１０」と出現数「１」とが対応付けられた行とで構成される４行の右構造体が作成される。同様に、データ処理装置１０−２（ノード２）では、キー「７」及び「４」と出現数「２」とが対応付けられた行と、キー「８」及び「３」と出現数「１」とが対応付けられた行と、キー「８」及び「１１」と出現数「１」とが対応付けられた行とで構成される３行の右構造体が作成される。
【０１６８】
Ｓ７３）次に、各データ処理装置１０の演算部１０２は、左構造体を作成する。すなわち、各データ処理装置１０の演算部１０２は、上記のＳ７２で作成した右構造体の全ての出現数を０として、「出現数」を「前方存在数」とした左構造体を作成する。
【０１６９】
Ｓ７４）次に、各データ処理装置１０の通信部１０１は、上記のＳ７２で作成した右構造体を相互に交換する。すなわち、各データ処理装置１０の通信部１０１は、自ノードの右構造体を他の全てのノードに送信すると共に、他の全てのノードから送信された右構造体を受信する。なお、このＳ７４は、上記のＳ７２の直後に実行されても良い。
【０１７０】
以降のＳ７５−０〜Ｓ７８−０はノード０で実行され、Ｓ７５−１〜Ｓ７８−１はノード１で実行され、Ｓ７５−２〜Ｓ７８−２はノード２で実行されるが、各ノードは、これらを独立に実行することができる。これは、Ｇｌｏｂａｌ  Ｌ演算が上述した特徴２を有するためである。
【０１７１】
Ｓ７５−０）データ処理装置１０−０の演算部１０２は、キー比較条件"＞"によりＬ演算を実行する。具体的には、データ処理装置１０−０の演算部１０２は、以下のＳ７５−０−０〜Ｓ７５−０−２を実行する。ここで、データ処理装置１０−０の演算部１０２は、以下のＳ７５−０−０〜Ｓ７５−０−２の並列処理のため、場合により、それぞれで異なる記憶領域上に展開された左構造体中の前方存在数を使用する。言い換えれば、並列処理のため、場合により、ノード０の右構造体との比較用の左構造体中の前方存在数と、ノード１の右構造体との比較用の左構造体中の前方存在数と、ノード２の右構造体との比較用の左構造体中の前方存在数とを使用する。なお、Ｇｌｏｂａｌ  Ｌ演算が上述した特徴１を有することにより、以下のＳ７５−０−０〜Ｓ７５−０−２は順不同である。
【０１７２】
Ｓ７５−０−０）データ処理装置１０−０の演算部１０２は、自ノードの左構造体のキー列中のキー「６」及び「６」と、自ノード（ノード０）の右構造体のキー列中のキー「６」及び「６」を比較する。この場合、キー比較条件"＞"が成り立たないため、当該演算部１０２は、左構造体の操作位置を一つ下げる。これにより、左構造体の操作位置が「０」から「１」に更新される。
【０１７３】
次に、データ処理装置１０−０の演算部１０２は、自ノードの左構造体のキー列中のキー「８」及び「０」と、自ノード（ノード０）の右構造体のキー列中のキー「６」及び「６」とを比較する。この場合、キー比較条件"＞"が成り立つため、当該演算部１０２は、右構造体のキー「６」及び「６」に対応する出現数「２」を、左構造体のキー「８」及び「０」に対応する前方存在数に加算した上で、右構造体の参照位置を一つ下げる。これにより、左構造体の操作位置「１」の前方存在数が「０」から「２」に更新されると共に、右構造体の参照位置が「０」から「１」に更新される。
【０１７４】
次に、データ処理装置１０−０の演算部１０２は、自ノードの左構造体のキー列中のキー「８」及び「０」と、自ノード（ノード０）の右構造体のキー列中のキー「８」及び「０」とを比較する。この場合、キー比較条件"＞"が成り立たないため、当該演算部１０２は、左構造体の操作位置を一つ下げることになるが、これ以上、操作位置を下げることはできないため、Ｌ演算を終了する。
【０１７５】
Ｓ７５−０−１）データ処理装置１０−０の演算部１０２は、自ノードの左構造体のキー列中のキー「６」及び「６」と、ノード１の右構造体のキー列中のキー「６」及び「９」とを比較する。この場合、キー比較条件"＞"が成り立たないため、当該演算部１０２は、左構造体の操作位置を一つ下げる。これにより、左構造体の操作位置が「０」から「１」に更新される。
【０１７６】
次に、データ処理装置１０−０の演算部１０２は、自ノードの左構造体のキー列中のキー「８」及び「０」と、ノード１の右構造体のキー列中のキー「６」及び「９」とを比較する。この場合、キー比較条件"＞"が成り立つため、当該演算部１０２は、右構造体のキー「６」及び「９」に対応する出現数「１」を、左構造体のキー「８」及び「０」に対応する前方存在数に加算した上で、右構造体の参照位置を一つ下げる。これにより、左構造体の操作位置「１」の前方存在数が「０」から「１」に更新されると共に、右構造体の参照位置が「０」から「１」に更新される。
【０１７７】
次に、データ処理装置１０−０の演算部１０２は、自ノードの左構造体のキー列中のキー「８」及び「０」と、ノード１の右構造体のキー列中のキー「７」及び「２」とを比較する。この場合、キー比較条件"＞"が成り立つため、当該演算部１０２は、右構造体のキー「７」及び「２」に対応する出現数「１」を、左構造体のキー「８」及び「０」に対応する前方存在数に加算した上で、右構造体の参照位置を一つ下げる。これにより、左構造体の操作位置「１」の前方存在数が「１」から「２」に更新されると共に、右構造体の参照位置が「１」から「２」に更新される。
【０１７８】
次に、データ処理装置１０−０の演算部１０２は、自ノードの左構造体のキー列中のキー「８」及び「０」と、ノード１の右構造体のキー列中のキー「７」及び「８」とを比較する。この場合、キー比較条件"＞"が成り立つため、当該演算部１０２は、右構造体のキー「７」及び「８」に対応する出現数「１」を、左構造体のキー「８」及び「０」に対応する前方存在数に加算した上で、右構造体の参照位置を一つ下げる。これにより、左構造体の操作位置「１」の前方存在数が「２」から「３」に更新されると共に、右構造体の参照位置が「２」から「３」に更新される。
【０１７９】
次に、データ処理装置１０−０の演算部１０２は、自ノードの左構造体のキー列中のキー「８」及び「０」と、ノード１の右構造体のキー列中のキー「８」及び「１０」とを比較する。この場合、キー比較条件"＞"が成り立たないため、当該演算部１０２は、左構造体の操作位置を一つ下げることになるが、これ以上、操作位置を下げることはできないため、Ｌ演算を終了する。
【０１８０】
Ｓ７５−０−２）データ処理装置１０−０の演算部１０２は、自ノードの左構造体のキー列中のキー「６」及び「６」と、ノード２の右構造体のキー列中のキー「７」及び「４」とを比較する。この場合、キー比較条件"＞"が成り立たないため、当該演算部１０２は、左構造体の操作位置を一つ下げる。これにより、左構造体の操作位置が「０」から「１」に更新される。
【０１８１】
次に、データ処理装置１０−０の演算部１０２は、自ノードの左構造体のキー列中のキー「８」及び「０」と、ノード２の右構造体のキー列中のキー「７」及び「４」とを比較する。この場合、キー比較条件"＞"が成り立つため、当該演算部１０２は、右構造体のキー「７」及び「４」に対応する出現数「２」を、左構造体のキー「８」及び「０」に対応する前方存在数に加算した上で、右構造体の参照位置を一つ下げる。これにより、左構造体の操作位置「１」の前方存在数が「０」から「２」に更新されると共に、右構造体の参照位置が「０」から「１」に更新される。
【０１８２】
次に、データ処理装置１０−０の演算部１０２は、自ノードの左構造体のキー列中のキー「８」及び「０」と、ノード２の右構造体のキー列中のキー「８」及び「３」とを比較する。この場合、キー比較条件"＞"が成り立たないため、当該演算部１０２は、左構造体の操作位置を一つ下げることになるが、これ以上、操作位置を下げることはできないため、Ｌ演算を終了する。
【０１８３】
Ｓ７６−０）次に、データ処理装置１０−０の演算部１０２は、左構造体の前方存在数の合計を算出する。すなわち、データ処理装置１０−０の演算部１０２は、ノード０の右構造体との比較用の左構造体と、ノード１の右構造体との比較用の左構造体と、ノード２の右構造体との比較用の左構造体とで前方存在数の合計を算出する。これにより、年齢「６」及びｏｌｄＧＯｒｄ「６」に対応する前方存在数（の合計）は「０」、年齢「８」及びｏｌｄＧＯｒｄ「０」に対応する前方存在数（の合計）は「７」となる。
【０１８４】
Ｓ７７−０）次に、データ処理装置１０−０の演算部１０２は、上記のＳ７６−０で算出した前方存在数（の合計）を累計化する。すなわち、データ処理装置１０−０の演算部１０２は、年齢「６」及びｏｌｄＧＯｒｄ「６」に対応する前方存在数はそのままとする一方で、年齢「８」及びｏｌｄＧＯｒｄ「０」に対応する前方存在数を、年齢「６」及びｏｌｄＧＯｒｄ「６」に対応する前方存在数＋年齢「８」及びｏｌｄＧＯｒｄ「０」に対応する前方存在数とする。
【０１８５】
これにより、年齢「６」及びｏｌｄＧＯｒｄ「６」に対応する前方存在数は「０」、年齢「８」及びｏｌｄＧＯｒｄ「０」に対応する前方存在数は「７」となる。この前方存在数が、ノード０におけるｏｌｄＧＯｒｄ毎のＧＯｒｄの開始番号となる。この場合、ノード０の年齢「６」及びｏｌｄＧＯｒｄ「６」のＧＯｒｄの開始番号は「０」、年齢「８」及びｏｌｄＧＯｒｄ「０」のＧＯｒｄの開始番号は「６」となる。
【０１８６】
Ｓ７８−０）次に、データ処理装置１０−０の演算部１０２は、上記のＳ７７−０で累計化した前方存在数と、上記のＳ７２で得られた出現数とを用いて、上記のＳ７１で作成した自ノードのＧＯｒｄリストを更新する。すなわち、データ処理装置１０−０の演算部１０２は、年齢及びｏｌｄＧＯｒｄ毎に、前方存在数から開始して、出現数回、上から順に１つずつ加算した値をＧＯｒｄリストに格納する。これにより、ノード０のＧＯｒｄリストには、格納位置「０」にＧＯｒｄ「０」、格納位置「１」にＧＯｒｄ「１」、格納位置「２」にＧＯｒｄ「７」、格納位置「３」にＧＯｒｄ「８」が格納される。
【０１８７】
Ｓ７５−１）データ処理装置１０−１の演算部１０２は、キー比較条件"＞"によりＬ演算を実行する。具体的には、データ処理装置１０−１の演算部１０２は、以下のＳ７５−１−０〜Ｓ７５−１−２を実行する。ここで、データ処理装置１０−１の演算部１０２は、以下のＳ７５−１−０〜Ｓ７５−１−２の並列処理のため、場合により、それぞれで異なる記憶領域上に展開された左構造体中の前方存在数を使用する。言い換えれば、並列処理のため、場合により、ノード０の右構造体との比較用の左構造体中の前方存在数と、ノード１の右構造体との比較用の左構造体中の前方存在数と、ノード２の右構造体との比較用の左構造体中の前方存在数とを使用する。なお、Ｇｌｏｂａｌ  Ｌ演算が上述した特徴１を有することにより、以下のＳ７５−１−０〜Ｓ７５−１−２は順不同である。
【０１８８】
Ｓ７５−１−０）データ処理装置１０−１の演算部１０２は、自ノードの左構造体のキー列中のキー「６」及び「９」と、ノード０の右構造体のキー列中のキー「６」及び「６」とを比較する。この場合、キー比較条件"＞"が成り立つため、当該演算部１０２は、右構造体のキー「６」及び「６」に対応する出現数「２」を、左構造体のキー「６」及び「９」に対応する前方存在数に加算した上で、右構造体の参照位置を一つ下げる。これにより、左構造体の操作位置「０」の前方存在数が「０」から「２」に更新されると共に、右構造体の参照位置が「０」から「１」に更新される。
【０１８９】
次に、データ処理装置１０−１の演算部１０２は、自ノードの左構造体のキー列中のキー「６」及び「９」と、ノード０の右構造体のキー列中のキー「８」及び「０」とを比較する。この場合、キー比較条件"＞"が成り立たないため、当該演算部１０２は、左構造体の操作位置を一つ下げる。これにより、左構造体の操作位置が「０」から「１」に更新される。
【０１９０】
次に、データ処理装置１０−１の演算部１０２は、自ノードの左構造体のキー列中のキー「７」及び「２」と、ノード０の右構造体のキー列中のキー「８」及び「０」とを比較する。この場合、キー比較条件"＞"が成り立たないため、当該演算部１０２は、左構造体の操作位置を一つ下げる。これにより、左構造体の操作位置が「１」から「２」に更新される。
【０１９１】
次に、データ処理装置１０−１の演算部１０２は、自ノードの左構造体のキー列中のキー「７」及び「８」と、ノード０の右構造体のキー列中のキー「８」及び「０」とを比較する。この場合、キー比較条件"＞"が成り立たないため、当該演算部１０２は、左構造体の操作位置を一つ下げる。これにより、左構造体の操作位置が「２」から「３」に更新される。
【０１９２】
次に、データ処理装置１０−１の演算部１０２は、自ノードの左構造体のキー列中のキー「８」及び「１０」と、ノード０の右構造体のキー列中のキー「８」及び「０」とを比較する。この場合、キー比較条件"＞"が成り立つため、当該演算部１０２は、右構造体のキー「８」及び「０」に対応する出現数「２」を、左構造体のキー「８」及び「１０」に対応する前方存在数に加算する。そして、当該演算部１０２は、右構造体の参照位置を一つ下げることになるが、これ以上、参照位置を下げることはできないため、Ｌ演算を終了する。これにより、左構造体の操作位置「３」の前方存在数が「０」から「２」に更新される。
【０１９３】
Ｓ７５−１−１）データ処理装置１０−１の演算部１０２は、自ノードの左構造体のキー列中のキー「６」及び「９」と、自ノード（ノード１）の右構造体のキー列中のキー「６」及び「９」とを比較する。この場合、キー比較条件"＞"が成り立たないため、当該演算部１０２は、左構造体の操作位置を一つ下げる。これにより、左構造体の操作位置が「０」から「１」に更新される。
【０１９４】
次に、データ処理装置１０−１の演算部１０２は、自ノードの左構造体のキー列中のキー「７」及び「２」と、自ノード（ノード１）の右構造体のキー列中のキー「６」及び「９」とを比較する。この場合、キー比較条件"＞"が成り立つため、当該演算部１０２は、右構造体のキー「６」及び「９」に対応する出現数「１」を、左構造体のキー「７」及び「２」に対応する前方存在数に加算した上で、右構造体の参照位置を一つ下げる。これにより、左構造体の操作位置「１」の前方存在数が「０」から「１」に更新されると共に、右構造体の参照位置が「０」から「１」に更新される。
【０１９５】
次に、データ処理装置１０−１の演算部１０２は、自ノードの左構造体のキー列中のキー「７」及び「２」と、自ノード（ノード１）の右構造体のキー列中のキー「７」及び「２」とを比較する。この場合、キー比較条件"＞"が成り立たないため、当該演算部１０２は、左構造体の操作位置を一つ下げる。これにより、左構造体の操作位置が「１」から「２」に更新される。
【０１９６】
次に、データ処理装置１０−１の演算部１０２は、自ノードの左構造体のキー列中のキー「７」及び「８」と、自ノード（ノード１）の右構造体のキー列中のキー「７」及び「２」とを比較する。この場合、キー比較条件"＞"が成り立つため、当該演算部１０２は、右構造体のキー「７」及び「２」に対応する出現数「１」を、左構造体のキー「７」及び「８」に対応する前方存在数に加算した上で、右構造体の参照位置を一つ下げる。これにより、左構造体の操作位置「２」の前方存在数が「０」から「１」に更新されると共に、右構造体の参照位置が「１」から「２」に更新される。
【０１９７】
次に、データ処理装置１０−１の演算部１０２は、自ノードの左構造体のキー列中のキー「７」及び「８」と、自ノード（ノード１）の右構造体のキー列中のキー「７」及び「８」とを比較する。この場合、キー比較条件"＞"が成り立たないため、当該演算部１０２は、左構造体の操作位置を一つ下げる。これにより、左構造体の操作位置が「２」から「３」に更新される。
【０１９８】
次に、データ処理装置１０−１の演算部１０２は、自ノードの左構造体のキー列中のキー「８」及び「１０」と、自ノード（ノード１）の右構造体のキー列中のキー「７」及び「８」とを比較する。この場合、キー比較条件"＞"が成り立つため、当該演算部１０２は、右構造体のキー「７」及び「８」に対応する出現数「１」を、左構造体のキー「８」及び「１０」に対応する前方存在数に加算した上で、右構造体の参照位置を一つ下げる。これにより、左構造体の操作位置「３」の前方存在数が「０」から「１」に更新されると共に、右構造体の参照位置が「２」から「３」に更新される。
【０１９９】
次に、データ処理装置１０−１の演算部１０２は、自ノードの左構造体のキー列中のキー「８」及び「１０」と、自ノード（ノード１）の右構造体のキー列中のキー「８」及び「１０」とを比較する。この場合、キー比較条件"＞"が成り立たないため、当該演算部１０２は、左構造体の操作位置を一つ下げることになるが、これ以上、操作位置を下げることはできないため、Ｌ演算を終了する。
【０２００】
Ｓ７５−１−２）データ処理装置１０−１の演算部１０２は、自ノードの左構造体のキー列中のキー「６」及び「９」と、ノード２の右構造体のキー列中のキー「７」及び「４」とを比較する。この場合、キー比較条件"＞"が成り立たないため、当該演算部１０２は、左構造体の操作位置を一つ下げる。これにより、左構造体の操作位置が「０」から「１」に更新される。
【０２０１】
次に、データ処理装置１０−１の演算部１０２は、自ノードの左構造体のキー列中のキー「７」及び「２」と、ノード２の右構造体のキー列中のキー「７」及び「４」とを比較する。この場合、キー比較条件"＞"が成り立たないため、当該演算部１０２は、左構造体の操作位置を一つ下げる。これにより、左構造体の操作位置が「１」から「２」に更新される。
【０２０２】
次に、データ処理装置１０−１の演算部１０２は、自ノードの左構造体のキー列中のキー「７」及び「８」と、ノード２の右構造体のキー列中のキー「７」及び「４」とを比較する。この場合、キー比較条件"＞"が成り立つため、当該演算部１０２は、右構造体のキー「７」及び「４」に対応する出現数「２」を、左構造体のキー「７」及び「８」に対応する前方存在数に加算した上で、右構造体の参照位置を一つ下げる。これにより、左構造体の操作位置「２」の前方存在数が「０」から「２」に更新されると共に、右構造体の参照位置が「０」から「１」に更新される。
【０２０３】
次に、データ処理装置１０−１の演算部１０２は、自ノードの左構造体のキー列中のキー「７」及び「８」と、ノード２の右構造体のキー列中のキー「８」及び「３」とを比較する。この場合、キー比較条件"＞"が成り立たないため、当該演算部１０２は、左構造体の操作位置を一つ下げる。これにより、左構造体の操作位置が「２」から「３」に更新される。
【０２０４】
次に、データ処理装置１０−１の演算部１０２は、自ノードの左構造体のキー列中のキー「８」及び「１０」と、ノード２の右構造体のキー列中のキー「８」及び「３」とを比較する。この場合、キー比較条件"＞"が成り立つため、当該演算部１０２は、右構造体のキー「８」及び「３」に対応する出現数「１」を、左構造体のキー「８」及び「１０」に対応する前方存在数に加算した上で、右構造体の参照位置を一つ下げる。これにより、左構造体の操作位置「３」の前方存在数が「０」から「１」に更新されると共に、右構造体の参照位置が「１」から「２」に更新される。
【０２０５】
次に、データ処理装置１０−１の演算部１０２は、自ノードの左構造体のキー列中のキー「８」及び「１０」と、ノード２の右構造体のキー列中のキー「８」及び「１１」とを比較する。この場合、キー比較条件"＞"が成り立たないため、当該演算部１０２は、左構造体の操作位置を一つ下げることになるが、これ以上、操作位置を下げることはできないため、Ｌ演算を終了する。
【０２０６】
Ｓ７６−１）次に、データ処理装置１０−１の演算部１０２は、左構造体の前方存在数の合計を算出する。すなわち、データ処理装置１０−１の演算部１０２は、ノード０の右構造体との比較用の左構造体と、ノード１の右構造体との比較用の左構造体と、ノード２の右構造体との比較用の左構造体とで前方存在数の合計を算出する。これにより、年齢「６」及びｏｌｄＧＯｒｄ「９」に対応する前方存在数（の合計）は「２」、年齢「７」及びｏｌｄＧＯｒｄ「２」に対応する前方存在数（の合計）は「１」、年齢「７」及びｏｌｄＧＯｒｄ「８」に対応する前方存在数（の合計）は「３」、年齢「８」及びｏｌｄＧＯｒｄ「１０」に対応する前方存在数（の合計）は「４」となる。
【０２０７】
Ｓ７７−１）次に、データ処理装置１０−１の演算部１０２は、上記のＳ７６−１で算出した前方存在数（の合計）を累計化する。すなわち、データ処理装置１０−１の演算部１０２は、各キーの前方存在数を、当該キー以下の全てのキーの前方存在数の合計とする。
【０２０８】
これにより、年齢「６」及びｏｌｄＧＯｒｄ「９」に対応する前方存在数は「２」、年齢「７」及びｏｌｄＧＯｒｄ「２」に対応する前方存在数は「３」、年齢「７」及びｏｌｄＧＯｒｄ「８」に対応する前方存在数は「６」、年齢「８」及びｏｌｄＧＯｒｄ「１０」に対応する前方存在数は「１０」となる。この前方存在数が、ノード１における年齢及びｏｌｄＧＯｒｄ毎のＧＯｒｄの開始番号となる。この場合、ノード１の年齢「６」及びｏｌｄＧＯｒｄ「９」のＧＯｒｄの開始番号は「２」、年齢「７」及びｏｌｄＧＯｒｄ「２」のＧＯｒｄの開始番号は「３」、年齢「７」及びｏｌｄＧＯｒｄ「８」のＧＯｒｄの開始番号は「６」、年齢「８」及びｏｌｄＧＯｒｄ「１０」のＧＯｒｄの開始番号は「１０」となる。
【０２０９】
Ｓ７８−１）次に、データ処理装置１０−１の演算部１０２は、上記のＳ７７−１で累計化した前方存在数と、上記のＳ７２で得られた出現数とを用いて、上記のＳ７１で作成した自ノードのＧＯｒｄリストを更新する。すなわち、データ処理装置１０−１の演算部１０２は、年齢及びｏｌｄＧＯｒｄ毎に、前方存在数から開始して、出現数回、上から順に１つずつ加算した値をＧＯｒｄリストに格納する。これにより、ノード１のＧＯｒｄリストには、格納位置「０」にＧＯｒｄ「２」、格納位置「１」にＧＯｒｄ「３」、格納位置「２」にＧＯｒｄ「６」、格納位置「３」にＧＯｒｄ「１０」が格納される。
【０２１０】
Ｓ７５−２）データ処理装置１０−２の演算部１０２は、キー比較条件"＞"によりＬ演算を実行する。具体的には、データ処理装置１０−２の演算部１０２は、以下のＳ７５−２−０〜Ｓ７５−２−２を実行する。ここで、データ処理装置１０−２の演算部１０２は、以下のＳ７５−２−０〜Ｓ７５−２−２の並列処理のため、場合により、それぞれで異なる記憶領域上に展開された左構造体中の前方存在数を使用する。言い換えれば、並列処理のため、場合により、ノード０の右構造体との比較用の左構造体中の前方存在数と、ノード１の右構造体との比較用の左構造体中の前方存在数と、ノード２の右構造体との比較用の左構造体中の前方存在数とを使用する。なお、Ｇｌｏｂａｌ  Ｌ演算が上述した特徴１を有することにより、以下のＳ７５−２−０〜Ｓ７５−２−２は順不同である。
【０２１１】
Ｓ７５−２−０）データ処理装置１０−２の演算部１０２は、自ノードの左構造体のキー列中のキー「７」及び「４」と、ノード０の右構造体のキー列中のキー「６」及び「６」とを比較する。この場合、キー比較条件"＞"が成り立つため、当該演算部１０２は、右構造体のキー「６」及び「６」に対応する出現数「２」を、左構造体のキー「７」及び「４」に対応する前方存在数に加算した上で、右構造体の参照位置を一つ下げる。これにより、左構造体の操作位置「０」の前方存在数が「０」から「２」に更新されると共に、右構造体の参照位置が「０」から「１」に更新される。
【０２１２】
次に、データ処理装置１０−２の演算部１０２は、自ノードの左構造体のキー列中のキー「７」及び「４」と、ノード０の右構造体のキー列中のキー「８」及び「０」とを比較する。この場合、キー比較条件"＞"が成り立たないため、当該演算部１０２は、左構造体の操作位置を一つ下げる。これにより、左構造体の操作位置が「０」から「１」に更新される。
【０２１３】
次に、データ処理装置１０−２の演算部１０２は、自ノードの左構造体のキー列中のキー「８」及び「３」と、ノード０の右構造体のキー列中のキー「８」及び「０」とを比較する。この場合、キー比較条件"＞"が成り立つため、当該演算部１０２は、右構造体のキー「８」及び「０」に対応する出現数「２」を、左構造体のキー「８」及び「３」に対応する前方存在数に加算する。そして、当該演算部１０２は、右構造体の参照位置を一つ下げることになるが、これ以上、参照位置を下げることはできないため、Ｌ演算を終了する。これにより、左構造体の操作位置「１」の前方存在数が「０」から「２」に更新される。
【０２１４】
Ｓ７５−２−１）データ処理装置１０−２の演算部１０２は、自ノードの左構造体のキー列中のキー「７」及び「４」と、ノード１の右構造体のキー列中のキー「６」及び「９」とを比較する。この場合、キー比較条件"＞"が成り立つため、当該演算部１０２は、右構造体のキー「６」及び「９」に対応する出現数「１」を、左構造体のキー「７」及び「４」に対応する前方存在数に加算した上で、右構造体の参照位置を一つ下げる。これにより、左構造体の操作位置「０」の前方存在数が「０」から「１」に更新されると共に、右構造体の参照位置が「０」から「１」に更新される。
【０２１５】
次に、データ処理装置１０−２の演算部１０２は、自ノードの左構造体のキー列中のキー「７」及び「４」と、ノード１の右構造体のキー列中のキー「７」及び「２」とを比較する。この場合、キー比較条件"＞"が成り立つため、当該演算部１０２は、右構造体のキー「７」及び「２」に対応する出現数「１」を、左構造体のキー「７」及び「４」に対応する前方存在数に加算した上で、右構造体の参照位置を一つ下げる。これにより、左構造体の操作位置「０」の前方存在数が「１」から「２」に更新されると共に、右構造体の参照位置が「１」から「２」に更新される。
【０２１６】
次に、データ処理装置１０−２の演算部１０２は、自ノードの左構造体のキー列中のキー「７」及び「４」と、ノード１の右構造体のキー列中のキー「７」及び「９」とを比較する。この場合、キー比較条件"＞"が成り立たないため、当該演算部１０２は、左構造体の操作位置を一つ下げる。これにより、左構造体の操作位置が「０」から「１」に更新される。
【０２１７】
次に、データ処理装置１０−２の演算部１０２は、自ノードの左構造体のキー列中のキー「８」及び「３」と、ノード１の右構造体のキー列中のキー「７」及び「９」とを比較する。この場合、キー比較条件"＞"が成り立つため、当該演算部１０２は、右構造体のキー「７」及び「９」に対応する出現数「１」を、左構造体のキー「８」及び「３」に対応する前方存在数に加算した上で、右構造体の参照位置を一つ下げる。これにより、左構造体の操作位置「１」の前方存在数が「０」から「１」に更新されると共に、右構造体の参照位置が「２」から「３」に更新される。
【０２１８】
次に、データ処理装置１０−２の演算部１０２は、自ノードの左構造体のキー列中のキー「８」及び「３」と、ノード１の右構造体のキー列中のキー「８」及び「１０」とを比較する。この場合、キー比較条件"＞"が成り立たないため、当該演算部１０２は、左構造体の操作位置を一つ下げる。これにより、左構造体の操作位置が「１」から「２」に更新される。
【０２１９】
次に、データ処理装置１０−２の演算部１０２は、自ノードの左構造体のキー列中のキー「８」及び「１１」と、ノード１の右構造体のキー列中のキー「８」及び「１０」とを比較する。この場合、キー比較条件"＞"が成り立つため、当該演算部１０２は、右構造体のキー「８」及び「１０」に対応する出現数「１」を、左構造体のキー「８」及び「１１」に対応する前方存在数に加算する。そして、当該演算部１０２は、右構造体の参照位置を一つ下げることになるが、これ以上、参照位置を下げることはできないため、Ｌ演算を終了する。これにより、左構造体の操作位置「２」の前方存在数が「０」から「１」に更新される。
【０２２０】
Ｓ７５−２−２）データ処理装置１０−２の演算部１０２は、自ノードの左構造体のキー列中のキー「７」及び「４」と、自ノード（ノード２）の右構造体のキー列中のキー「７」及び「４」とを比較する。この場合、キー比較条件"＞"が成り立たないため、当該演算部１０２は、左構造体の操作位置を一つ下げる。これにより、左構造体の操作位置が「０」から「１」に更新される。
【０２２１】
次に、データ処理装置１０−２の演算部１０２は、自ノードの左構造体のキー列中のキー「８」及び「３」と、自ノード（ノード２）の右構造体のキー列中のキー「７」及び「４」とを比較する。この場合、キー比較条件"＞"が成り立つため、当該演算部１０２は、右構造体のキー「７」及び「４」に対応する出現数「２」を、左構造体のキー「８」及び「３」に対応する前方存在数に加算した上で、右構造体の参照位置を一つ下げる。これにより、左構造体の操作位置「１」の前方存在数が「０」から「２」に更新されると共に、右構造体の参照位置が「０」から「１」に更新される。
【０２２２】
次に、データ処理装置１０−２の演算部１０２は、自ノードの左構造体のキー列中のキー「８」及び「３」と、自ノード（ノード２）の右構造体のキー列中のキー「８」及び「３」とを比較する。この場合、キー比較条件"＞"が成り立たないため、当該演算部１０２は、左構造体の操作位置を一つ下げる。これにより、左構造体の操作位置が「１」から「２」に更新される。
【０２２３】
次に、データ処理装置１０−２の演算部１０２は、自ノードの左構造体のキー列中のキー「８」及び「１１」と、自ノード（ノード２）の右構造体のキー列中のキー「８」及び「３」とを比較する。この場合、キー比較条件"＞"が成り立つため、当該演算部１０２は、右構造体のキー「８」及び「３」に対応する出現数「１」を、左構造体のキー「８」及び「１１」に対応する前方存在数に加算した上で、右構造体の参照位置を一つ下げる。これにより、左構造体の操作位置「２」の前方存在数が「０」から「１」に更新されると共に、右構造体の参照位置が「１」から「２」に更新される。
【０２２４】
次に、データ処理装置１０−２の演算部１０２は、自ノードの左構造体のキー列中のキー「８」及び「１１」と、自ノード（ノード２）の右構造体のキー列中のキー「８」及び「１１」とを比較する。この場合、キー比較条件"＞"が成り立たないため、当該演算部１０２は、左構造体の操作位置を一つ下げることになるが、これ以上、操作位置を下げることはできないため、Ｌ演算を終了する。
【０２２５】
Ｓ７６−２）次に、データ処理装置１０−２の演算部１０２は、左構造体の前方存在数の合計を算出する。すなわち、データ処理装置１０−２の演算部１０２は、ノード０の右構造体との比較用の左構造体と、ノード１の右構造体との比較用の左構造体と、ノード２の右構造体との比較用の左構造体とで前方存在数の合計を算出する。これにより、年齢「７」及びｏｌｄＧＯｒｄ「４」に対応する前方存在数（の合計）は「４」、年齢「８」及びｏｌｄＧＯｒｄ「３」に対応する前方存在数（の合計）は「５」、年齢「８」及びｏｌｄＧＯｒｄ「１１」に対応する前方存在数（の合計）は「２」となる。
【０２２６】
Ｓ７７−２）次に、データ処理装置１０−２の演算部１０２は、上記のＳ７６−２で算出した前方存在数（の合計）を累計化する。すなわち、データ処理装置１０−２の演算部１０２は、各キーの前方存在数を、当該キー以下の全てのキーの前方存在数の合計とする。
【０２２７】
これにより、年齢「７」及びｏｌｄＧＯｒｄ「４」に対応する前方存在数は「４」、年齢「８」及びｏｌｄＧＯｒｄ「３」に対応する前方存在数は「９」、年齢「８」及びｏｌｄＧＯｒｄ「１１」に対応する前方存在数は「１１」となる。この前方存在数が、ノード２における年齢及びｏｌｄＧＯｒｄ毎のＧＯｒｄの開始番号となる。この場合、ノード２の年齢「７」及びｏｌｄＧＯｒｄ「４」のＧＯｒｄの開始番号は「４」、年齢「８」及びｏｌｄＧＯｒｄ「３」のＧＯｒｄの開始番号は「９」、年齢「８」及びｏｌｄＧＯｒｄ「１１」のＧＯｒｄの開始番号は「１１」となる。
【０２２８】
Ｓ７８−２）次に、データ処理装置１０−２の演算部１０２は、上記のＳ７７−２で累計化した前方存在数と、上記のＳ７２で得られた出現数とを用いて、上記のＳ７１で作成した自ノードのＧＯｒｄリストを更新する。すなわち、データ処理装置１０−２の演算部１０２は、年齢及びｏｌｄＧＯｒｄ毎に、前方存在数から開始して、出現数回、上から順に１つずつ加算した値をＧＯｒｄリストに格納する。これにより、ノード２のＧＯｒｄリストには、格納位置「０」にＧＯｒｄ「４」、格納位置「１」にＧＯｒｄ「５」、格納位置「２」にＧＯｒｄ「９」、格納位置「３」にＧＯｒｄ「１１」が格納される。
【０２２９】
以上により、上記のＳ７１で作成された各ＧＯｒｄリストに対してＧＯｒｄが格納される。これにより、各データ処理装置１０でＧＯｒｄ（及びレコード番号）が付与された部分テーブルが得られ、このＧＯｒｄによりデータ処理装置１０全体でのソート結果（部分集合でのソート結果）が得られる。
【０２３０】
＜構造体の分割＞
右構造体及び左構造体はいずれも行数が膨大になる場合があり、データ処理の際に分割を行いたいケースが発生する。特に、右構造体はノード間の通信で相互に交換されるため、通信し易い大きさに分割したいことがある。
【０２３１】
そこで、以降では、右構造体を分割する場合について、図２７を参照しながら説明する。図２７は、右構造体の分割の一例を説明するための図である。なお、左構造体も右構造体と同様に分割することができる。
【０２３２】
図２７に示すように、右構造体の行数をｎ、ｉ行目のキーをｒｉ（０≦ｉ≦ｎ−１）として場合、右構造体は、連続する行を１つの右構造体として、任意の個数（ただし、ｎ個以下）の右構造体に分割することができる。以降では、分割された各右構造体を「分割右構造体」とも表す。右構造体を上から順にＮ個に分割した場合、これら分割された分割右構造体を上から順に「分割右構造体１」、「分割右構造体２」、・・・、「分割右構造体Ｎ」と表す。図２７では、一例としてＮ＝３の場合であり、分割右構造体１、分割右構造体２及び分割右構造体３の３つに分割した場合を示している。
【０２３３】
なお、Ｌ演算の定義により、各分割右構造体と左構造体とのＬ演算は、（分割されていない）右構造体と左構造体とのＬ演算と同一の演算結果が得られる。
【０２３４】
ここで、例えば、各分割右構造体と左構造体とのＬ演算を行う場合、演算部１０２は、分割右構造体を受け取る毎に、当該分割右構造体と左構造体とのＬ演算を操作位置「０」から開始すれば良いが、この場合は効率が良くない。
【０２３５】
そこで、各分割右構造体を「分割右構造体１」、「分割右構造体２」、・・・、「分割右構造体Ｎ」の順に受け取ることが保証されている場合、効率を落とさずに、Ｌ演算が可能となる。左構造体の行数をｍ、ｊ行目のキーをｌｊ（０≦ｊ≦ｍ−１）として、Ｎ＝２である場合について、図２８を参照しながら説明する。図２８は、左構造体と分割後の右構造体との比較操作の効率化の一例を説明するための図である。
【０２３６】
図２８Ａに示すように、左構造体と分割右構造体１とのＬ演算において、ｌ１≦ｒ１かつｌ２＞ｒ１であれば、操作位置を「２」とする。そして、図２８Ｂに示すように、左構造体と分割右構造体２とのＬ演算では、操作位置「２」からＬ演算を実施する。これにより、左構造体と分割右構造体２とのＬ演算では、操作位置「０」〜「１」までのキーの比較操作を行う必要がなくなるため、構造体を分割した場合であっても効率を落とさずに、Ｌ演算が可能となる。
【０２３７】
本発明は、具体的に開示された上記の実施形態に限定されるものではなく、特許請求の範囲から逸脱することなく、種々の変形や変更が可能である。
【０２３８】
本願は、日本国に２０１８年１０月４日に出願された基礎出願２０１８−１８８９６６号に基づくものであり、その全内容はここに参照をもって援用される。
【符号の説明】
【０２３９】
１        データ処理システム
１０      データ処理装置
１０１    通信部
１０２    演算部
１０３    記憶部
【図１Ａ】
2020071368.tif 000002
【図１Ｂ】
2020071368.tif 000003
【図２】
2020071368.tif 000004
【図３】
2020071368.tif 000005
【図４】
2020071368.tif 000006
【図５】
2020071368.tif 000007
【図６】
2020071368.tif 000008
【図７】
2020071368.tif 000009
【図８】
2020071368.tif 000010
【図９】
2020071368.tif 000011
【図１０】
2020071368.tif 000012
【図１１Ａ】
2020071368.tif 000013
【図１１Ｂ】
2020071368.tif 000014
【図１２】
2020071368.tif 000015
【図１３】
2020071368.tif 000016
【図１４】
2020071368.tif 000017
【図１５】
2020071368.tif 000018
【図１６】
2020071368.tif 000019
【図１７Ａ】
2020071368.tif 000020
【図１７Ｂ】
2020071368.tif 000021
【図１８Ａ】
2020071368.tif 000022
【図１８Ｂ】
2020071368.tif 000023
【図１８Ｃ】
2020071368.tif 000024
【図１９Ａ】
2020071368.tif 000025
【図１９Ｂ】
2020071368.tif 000026
【図１９Ｃ】
2020071368.tif 000027
【図２０Ａ】
2020071368.tif 000028
【図２０Ｂ】
2020071368.tif 000029
【図２０Ｃ】
2020071368.tif 000030
【図２１Ａ】
2020071368.tif 000031
【図２１Ｂ】
2020071368.tif 000032
【図２２】
2020071368.tif 000033
【図２３Ａ】
2020071368.tif 000034
【図２３Ｂ】
2020071368.tif 000035
【図２４Ａ】
2020071368.tif 000036
【図２４Ｂ】
2020071368.tif 000037
【図２４Ｃ】
2020071368.tif 000038
【図２５Ａ】
2020071368.tif 000039
【図２５Ｂ】
2020071368.tif 000040
【図２５Ｃ】
2020071368.tif 000041
【図２６Ａ】
2020071368.tif 000042
【図２６Ｂ】
2020071368.tif 000043
【図２６Ｃ】
2020071368.tif 000044
【図２７】
2020071368.tif 000045
【図２８Ａ】
2020071368.tif 000046
【図２８Ｂ】
2020071368.tif 000047
【国際調査報告】
2020071368.tif 000048
2020071368.tif 000049