(57)【要約】  メモリ共有型マルチプロセッサシステムにおいて、所定の項目の組に関する一意の項目値の組を抽出するために、所定の項目の組に関する項目値の組に対応する項目値番号の組の出現回数を並列的に数え上げ、出現回数の累積度数分布を表現する累積度数分布配列を共有メモリに生成し、レコード番号配列の要素の値を添字として使って項目値番号の組を並列的に読み出し、項目値番号の組を添字として使って累積度数分布配列の要素を並列的に読み出し、累積度数分布配列の要素をインデックスポインタとして利用してレコード番号配列の要素の値をソートされたレコード番号配列に並列的に格納し、インデックスポインタとして利用された累積度数分布配列の要素の値に従ってソートされたレコード番号配列を一意の項目値の組を有するレコードのレコード番号のグループに区分し、区分されたレコード番号の各グループから１個のレコード番号を抽出する。
2008155852.tif 000002
【特許請求の範囲】
【請求項１】
表形式データのレコードのレコード番号が所定のレコード順に従って格納されたレコード番号配列、上記表形式データの上記レコードの所定の項目の項目値に対応する項目値番号がレコード番号に従って格納された項目値番号配列、及び、上記表形式データの項目値が当該項目値に対応する項目値番号の順序に従って格納された項目値配列を記憶する共有メモリと、
上記共有メモリにアクセス可能である複数台のプロセッサと、
を備えたメモリ共有型マルチプロセッサシステムにおいて、
所定の項目の組に関する一意の項目値の組を抽出する方法であって、
上記複数台のプロセッサを用いて、上記所定の項目の組に関する項目値の組に対応する項目値番号の組の出現回数を並列的に数え上げ、上記出現回数の累積度数分布を表現する累積度数分布配列を上記共有メモリに生成するステップと、
上記複数台のプロセッサを用いて、上記レコード番号配列の要素の値を添字として使って上記項目値番号の組を並列的に読み出し、上記項目値番号の組より計算された値を添字として使って上記累積度数分布配列の要素を並列的に読み出し、上記累積度数分布配列の要素をインデックスポインタとして利用して上記レコード番号配列の要素の値をソートされたレコード番号配列に並列的に格納するステップと、
上記インデックスポインタとして利用された上記累積度数分布配列の要素の値に従って上記ソートされたレコード番号配列を上記一意の項目値の組を有するレコードのレコード番号のグループに区分するステップと、
上記区分されたレコード番号の各グループから１個のレコード番号を抽出することにより、上記一意の項目値の組を特定するステップと、
を備える方法。
【請求項２】
上記累積度数分布配列を上記共有メモリに並列的に生成するステップが、上記複数台のプロセッサを用いて、上記レコード番号配列に格納された上記レコード番号毎に、上記所定の項目の組に関する項目値の組に対応する項目値番号の組に含まれる上記項目値番号の範囲に応じて基数を設定することにより、上記項目値番号の組を、上記項目値番号の組に含まれる各項目値番号が各桁を表現する基数形式の仮想項目値番号に変換するステップを備える、
請求項１記載の方法。
【請求項３】
上記所定の項目の組に含まれる項目毎に上記累積度数分布配列を上記共有メモリに並列的に生成するステップ（ｉ）と、上記所定の項目の組に含まれる項目毎に上記レコード番号配列の要素の値を上記ソートされたレコード番号配列に並列的に格納するステップ（ｉｉ）と、上記所定の項目の組に含まれる項目毎に上記ソートされたレコード番号配列を上記一意の項目値の組を有するレコードのレコード番号のグループに区分するステップ（ｉｉｉ）とを実行するステップを備え、
上記累積度数分布配列を上記共有メモリに並列的に生成するステップ（ｉ）が、上記複数台のプロセッサを用いて、上記項目に関する項目値に対応する項目値番号の出現回数を並列的に数え上げ、上記出現回数の累積度数分布を表現する累積度数分布配列を上記共有メモリに並列的に生成するステップを備え、
上記レコード番号配列の要素を上記ソートされたレコード番号配列に並列的に格納するステップ（ｉｉ）が、上記複数台のプロセッサを用いて、上記項目値番号配列の要素の値を添字として使って上記項目値番号を並列的に読み出し、上記項目値番号を添字として使って上記累積度数分布配列の要素を並列的に読み出し、上記累積度数分布配列の要素をインデックスポインタとして利用して上記レコード番号配列の要素の値を上記ソートされたレコード番号配列に並列的に格納するステップを備える、
請求項１記載の方法。
【請求項４】
上記複数台のプロセッサを用いて、上記所定の項目値の組毎に別の項目に関する項目値を並列的に集計するステップをさらに備える、請求項１記載の方法。
【請求項５】
上記複数台のプロセッサを用いて、上記ソートされたレコード番号配列中のレコード番号及び前記レコード番号に対応するグループのグループ番号を、前記レコード番号を添字として使って、補助的なレコード番号配列及び補助的なグループ番号配列に並列的に格納するステップと、
上記複数台のプロセッサを用いて、上記補助的なレコード番号配列の要素を添字として使って上記別の項目に関する項目値番号配列から並列的に要素を読み出し、前記項目値番号配列の要素を添字として使って上記別の項目に関する項目値配列から並列的に項目値を読み出し、上記補助的なレコード番号配列の要素を添字として使って上記補助的なグループ番号配列の要素を読み出し、上記補助的なグループ番号配列の要素を集計配列の添字として使って上記読み出された項目値の集計結果を上記集計配列に格納するステップと、
をさらに備える、請求項１記載の方法。
【請求項６】
上記複数台のプロセッサを用いて、上記ソートされたレコード番号配列の要素を添字として使って上記別の項目に関する項目値番号配列から並列的に要素を読み出し、前記項目値番号配列の要素を添字として使って上記別の項目に関する項目値配列から並列的に項目値を読み出し、上記ソートされたレコード番号配列の要素に対応するグループのグループ番号を集計配列の添字として使って上記読み出された項目値の集計結果を上記集計配列に格納するステップをさらに備える、請求項１記載の方法。
【請求項７】
表形式データのレコードのレコード番号が所定のレコード順に従って格納されたレコード番号配列、上記表形式データの上記レコードの所定の項目の項目値に対応する項目値番号がレコード番号に従って格納された項目値番号配列、及び、上記表形式データの項目値が当該項目値に対応する項目値番号の順序に従って格納された項目値配列を記憶する共有メモリと、
上記共有メモリにアクセス可能である複数台のプロセッサと、
を備えたメモリ共有型マルチプロセッサシステムにおいて、
所定の項目の組に関する一意の項目値の組を抽出する装置であって、
上記複数台のプロセッサを用いて、上記所定の項目の組に関する項目値の組に対応する項目値番号の組の出現回数を並列的に数え上げ、上記出現回数の累積度数分布を表現する累積度数分布配列を上記共有メモリに生成する手段と、
上記複数台のプロセッサを用いて、上記レコード番号配列の要素の値を添字として使って上記項目値番号の組を並列的に読み出し、上記項目値番号の組より計算された値を添字として使って上記累積度数分布配列の要素を並列的に読み出し、上記累積度数分布配列の要素をインデックスポインタとして利用して上記レコード番号配列の要素の値をソートされたレコード番号配列に並列的に格納する手段と、
上記インデックスポインタとして利用された上記累積度数分布配列の要素の値に従って上記ソートされたレコード番号配列を上記一意の項目値の組を有するレコードのレコード番号のグループに区分する手段と、
上記区分されたレコード番号の各グループから１個のレコード番号を抽出することにより、上記一意の項目値の組を特定する手段と、
を備える装置。
【請求項８】
上記累積度数分布配列を上記共有メモリに並列的に生成する手段が、上記複数台のプロセッサを用いて、上記レコード番号配列に格納された上記レコード番号毎に、上記所定の項目の組に関する項目値の組に対応する項目値番号の組に含まれる上記項目値番号の範囲に応じて基数を設定することにより、上記項目値番号の組を、上記項目値番号の組に含まれる各項目値番号が各桁を表現する基数形式の仮想項目値番号に変換する手段を備える、
請求項７記載の装置。
【請求項９】
上記累積度数分布配列を上記共有メモリに並列的に生成する手段が、上記所定の項目の組に含まれる項目毎に、上記複数台のプロセッサを用いて、上記項目に関する項目値に対応する項目値番号の出現回数を並列的に数え上げ、上記出現回数の累積度数分布を表現する累積度数分布配列を上記共有メモリに並列的に生成する手段を備え、
上記レコード番号配列の要素を上記ソートされたレコード番号配列に並列的に格納する手段が、上記所定の項目の組に含まれる項目毎に、上記複数台のプロセッサを用いて、上記項目値番号配列の要素の値を添字として使って上記項目値番号を並列的に読み出し、上記項目値番号を添字として使って上記累積度数分布配列の要素を並列的に読み出し、上記累積度数分布配列の要素をインデックスポインタとして利用して上記レコード番号配列の要素の値を上記ソートされたレコード番号配列に並列的に格納する手段を備える、
請求項７記載の装置。
【請求項１０】
上記複数台のプロセッサを用いて、上記所定の項目値の組毎に別の項目に関する項目値を並列的に集計する手段をさらに備える、請求項７記載の装置。
【請求項１１】
上記複数台のプロセッサを用いて、上記ソートされたレコード番号配列中のレコード番号及び前記レコード番号に対応するグループのグループ番号を、前記レコード番号を添字として使って、補助的なレコード番号配列及び補助的なグループ番号配列に並列的に格納する手段と、
上記複数台のプロセッサを用いて、上記補助的なレコード番号配列の要素を添字として使って上記別の項目に関する項目値番号配列から並列的に要素を読み出し、前記項目値番号配列の要素を添字として使って上記別の項目に関する項目値配列から並列的に項目値を読み出し、上記補助的なレコード番号配列の要素を添字として使って上記補助的なグループ番号配列の要素を読み出し、上記補助的なグループ番号配列の要素を集計配列の添字として使って上記読み出された項目値の集計結果を上記集計配列に格納する手段と、
をさらに備える、請求項７記載の装置。
【請求項１２】
上記複数台のプロセッサを用いて、上記ソートされたレコード番号配列の要素を添字として使って上記別の項目に関する項目値番号配列から並列的に要素を読み出し、前記項目値番号配列の要素を添字として使って上記別の項目に関する項目値配列から並列的に項目値を読み出し、上記ソートされたレコード番号配列の要素に対応するグループのグループ番号を集計配列の添字として使って上記読み出された項目値の集計結果を上記集計配列に格納する手段をさらに備える、請求項７記載の装置。
【請求項１３】
表形式データのレコードのレコード番号が所定のレコード順に従って格納されたレコード番号配列、上記表形式データの上記レコードの所定の項目の項目値に対応する項目値番号がレコード番号に従って格納された項目値番号配列、及び、上記表形式データの項目値が当該項目値に対応する項目値番号の順序に従って格納された項目値配列を記憶する共有メモリと、
上記共有メモリにアクセス可能である複数台のプロセッサと、
を備えたコンピュータにロードされ、所定の項目の組に関する一意の項目値の組を抽出するコードを上記コンピュータに実行させるコンピュータ読み取り可能なプログラムであって、
上記複数台のプロセッサを用いて、上記所定の項目の組に関する項目値の組に対応する項目値番号の組の出現回数を並列的に数え上げ、上記出現回数の累積度数分布を表現する累積度数分布配列を上記共有メモリに生成するコードと、
上記複数台のプロセッサを用いて、上記レコード番号配列の要素の値を添字として使って上記項目値番号の組を並列的に読み出し、上記項目値番号の組より計算された値を添字として使って上記累積度数分布配列の要素を並列的に読み出し、上記累積度数分布配列の要素をインデックスポインタとして利用して上記レコード番号配列の要素の値をソートされたレコード番号配列に並列的に格納するコードと、
上記インデックスポインタとして利用された上記累積度数分布配列の要素の値に従って上記ソートされたレコード番号配列を上記一意の項目値の組を有するレコードのレコード番号のグループに区分するコードと、
上記区分されたレコード番号の各グループから１個のレコード番号を抽出することにより、上記一意の項目値の組を特定するコードと、
を含むプログラム。
【請求項１４】
上記累積度数分布配列を上記共有メモリに並列的に生成するコードが、上記複数台のプロセッサを用いて、上記レコード番号配列に格納された上記レコード番号毎に、上記所定の項目の組に関する項目値の組に対応する項目値番号の組に含まれる上記項目値番号の範囲に応じて基数を設定することにより、上記項目値番号の組を、上記項目値番号の組に含まれる各項目値番号が各桁を表現する基数形式の仮想項目値番号に変換するコードを備える、
請求項１３記載のプログラム。
【請求項１５】
上記所定の項目の組に含まれる項目毎に上記累積度数分布配列を上記共有メモリに並列的に生成するコード（ｉ）と、上記所定の項目の組に含まれる項目毎に上記レコード番号配列の要素の値を上記ソートされたレコード番号配列に並列的に格納するコード（ｉｉ）と、上記所定の項目の組に含まれる項目毎に上記ソートされたレコード番号配列を上記一意の項目値の組を有するレコードのレコード番号のグループに区分するコードとを実行するコード（ｉｉｉ）を備え、
上記累積度数分布配列を上記共有メモリに並列的に生成するコード（ｉ）が、上記複数台のプロセッサを用いて、上記項目に関する項目値に対応する項目値番号の出現回数を並列的に数え上げ、上記出現回数の累積度数分布を表現する累積度数分布配列を上記共有メモリに並列的に生成するコードを備え、
上記レコード番号配列の要素を上記ソートされたレコード番号配列に並列的に格納するコード（ｉｉ）が、上記複数台のプロセッサを用いて、上記項目値番号配列の要素の値を添字として使って上記項目値番号を並列的に読み出し、上記項目値番号を添字として使って上記累積度数分布配列の要素を並列的に読み出し、上記累積度数分布配列の要素をインデックスポインタとして利用して上記レコード番号配列の要素の値を上記ソートされたレコード番号配列に並列的に格納するコードを備える、
請求項１３記載のプログラム。
【請求項１６】
上記複数台のプロセッサを用いて、上記所定の項目値の組毎に別の項目に関する項目値を並列的に集計するコードをさらに備える、請求項１３記載のプログラム。
【請求項１７】
上記複数台のプロセッサを用いて、上記ソートされたレコード番号配列中のレコード番号及び前記レコード番号に対応するグループのグループ番号を、前記レコード番号を添字として使って、補助的なレコード番号配列及び補助的なグループ番号配列に並列的に格納するコードと、
上記複数台のプロセッサを用いて、上記補助的なレコード番号配列の要素を添字として使って上記別の項目に関する項目値番号配列から並列的に要素を読み出し、前記項目値番号配列の要素を添字として使って上記別の項目に関する項目値配列から並列的に項目値を読み出し、上記補助的なレコード番号配列の要素を添字として使って上記補助的なグループ番号配列の要素を読み出し、上記補助的なグループ番号配列の要素を集計配列の添字として使って上記読み出された項目値の集計結果を上記集計配列に格納するコードと、
をさらに備える、請求項１３記載のプログラム。
【請求項１８】
上記複数台のプロセッサを用いて、上記ソートされたレコード番号配列の要素を添字として使って上記別の項目に関する項目値番号配列から並列的に要素を読み出し、前記項目値番号配列の要素を添字として使って上記別の項目に関する項目値配列から並列的に項目値を読み出し、上記ソートされたレコード番号配列の要素に対応するグループのグループ番号を集計配列の添字として使って上記読み出された項目値の集計結果を上記集計配列に格納するコードをさらに備える、請求項１３記載のプログラム。
【請求項１９】
表形式データのレコードのレコード番号が所定のレコード順に従って格納されたレコード番号配列、上記表形式データの上記レコードの所定の項目の項目値に対応する項目値番号がレコード番号に従って格納された項目値番号配列、及び、上記表形式データの項目値が当該項目値に対応する項目値番号の順序に従って格納された項目値配列を記憶する共有メモリと、上記共有メモリにアクセス可能である複数台のプロセッサと、を備えたコンピュータにロードされ、所定の項目の組に関する一意の項目値の組を抽出する請求項１記載の方法を上記コンピュータに実行させるためのコンピュータプログラムプロダクト。
【請求項２０】
表形式データのレコードのレコード番号が所定のレコード順に従って格納されたレコード番号配列、上記表形式データの上記レコードの所定の項目の項目値に対応する項目値番号がレコード番号に従って格納された項目値番号配列、及び、上記表形式データの項目値が当該項目値に対応する項目値番号の順序に従って格納された項目値配列を記憶する共有メモリと、上記共有メモリにアクセス可能である複数台のプロセッサと、を備えたコンピュータにロードされ、所定の項目の組に関する一意の項目値の組を抽出する請求項１記載の方法を上記コンピュータに実行させるためのコンピュータプログラムが記録された記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、メモリ共有型並列処理システム、特に、対称型マルチプロセッサ（Ｓｙｍｍｅｔｒｉｃ  Ｍｕｌｔｉｐｌｅ  Ｐｒｏｃｅｓｓｏｒ）システムにおいて、表形式データから一意の項目値の組を抽出する方法及び装置に関係する。また、本発明は、共有メモリにアクセスする複数台のプロセッサを備えるコンピュータに、表形式データから一意の項目値の組を抽出するコードを実行させるプログラムに関係する。また、本発明は、上記方法を共有メモリにアクセスする複数台のプロセッサを備えるコンピュータに実行させるためのコンピュータプログラムプロダクト、及び、コンピュータプログラムが記録された記録媒体に関係する。【０００２】
本発明は、さらに、メモリ共有型並列処理システム、特に、対称型マルチプロセッサシステムにおいて、表形式データを多次元で集計する方法及び装置に関係する。また、本発明は、共有メモリにアクセスする複数台のプロセッサを備えるコンピュータに、表形式データを多次元で集計するコードを実行させるプログラムに関係する。また、本発明は、上記方法を共有メモリにアクセスする複数台のプロセッサを備えるコンピュータに実行させるためのコンピュータプログラムプロダクト、及び、コンピュータプログラムが記録された記録媒体に関係する。
【背景技術】
【０００３】
従来、産業上の様々な分野において、大規模データを高速に処理することが求められている。大規模データの処理は、キャッシュやプリフェッチなどによるメモリアクセスの高速化、メモリ自体の高速化、及び、プロセッサの並列化のような演算処理の高速化、といったハードウェア技術の開発、ならびに、データ処理アルゴリズムの開発によって、高速化され続けている。たとえば、本発明者は、大規模データを高速に処理するため、特許文献１に記載されているような、「オンメモリデータ処理アルゴリズム」を提案している。【０００４】
また、大規模データを処理するために、効率の良いアルゴリズムが開発されている。大規模データ、特に、大規模な表形式データを処理する際に頻出する処理はソートである。効率的なソートアルゴリズムとして、基数（ＲＡＤＩＸ）ソートとカウンティング（ＣＯＵＮＴＩＮＧ）ソート（計数ソート、分布数え上げソートとも称される）が知られている。カウンティングソートは基数ソートの各桁のソートに利用されることがあり、効率の良いアルゴリズムである。【０００５】
近年、複数個のプロセッサが並列に動作するマルチプロセッサや、１チップ上に複数個のＣＰＵコアが搭載されたマルチコアプロセッサ、特に、複数個のＣＰＵが同等に処理を分担する対称型マルチプロセッサのようなメモリ共有型並列処理システムが設計されている。大規模データの検索・集計・ソート等の処理は、多くの場合に大規模データに同じ演算を適用するので、特に、対称型マルチプロセッサは大規模データの高速処理に適していると考えられる。これに関して、本発明者は、特許文献２に記載されているように、大規模な表形式データを処理するために、効率的なソートアルゴリズムと組み合わされたメモリ共有型マルチプロセッサシステムを提案している。【０００６】
特許文献２に記載されたメモリ共有型マルチプロセッサシステムでは、最初に、処理対象のレコードが分割されて複数台のプロセッサへ割り当てられる。次に、各プロセッサが処理対象のレコードに関連付けられた項目値番号のローカルな出現回数をカウントする。次に、各プロセッサでカウントされた項目値番号のローカルな出現回数を、項目値番号のグローバルな累計数、すなわち、複数台のプロセッサ間で共通に用いられる累計数に変換する。最後に、各プロセッサは、このグローバルな累計数をポインタとして利用することにより、割り当てられたレコードの順序を入れ替える。処理対象のレコードの複数台のプロセッサへの割り当て、ローカルな出現回数のカウント、及び、割り当てられたレコードの順序の入れ替えは、複数台のプロセッサが並列に処理可能である。また、グローバルな累計数の算出は、複数台のプロセッサの並列処理を利用してもよいが、メモリにシーケンシャルにアクセスできるためキャッシュへのヒット率が高いので、１台又は一部のプロセッサだけが担当して高速性を維持できる。【０００７】
このように、特許文献２には、メモリ共有型並列ソート技術が開示されているが、メモリ共有型並列集計技術は記載されていない。また、本発明者は、特許文献３に記載されているように、メモリ分散型並列集計技術を既に提案している。メモリ共有型とメモリ分散型とを問わず、集計とは、例えば、情報の項目に対応した項目値を含むレコードの配列として表される表形式データから、ある項目（次元）のある項目値（次元値）毎に、別の項目の項目値に基づく数量（測度）を算出することである。測度の算出とは、測度の個数をカウントしたり、測度の総和を算出したり、測度の平均値を算出したりすることである。また、次元数は、２次元以上でも構わない。例えば、年齢という項目と、身長という項目と、体重という項目を含む表形式データである場合に、年齢・身長別に体重の平均値を求める処理は、年齢と身長を次元とし、体重の平均値を測度とする集計処理である。【０００８】
このような集計処理では、最初に、次元を設定し、次元値毎にレコードを分類することが必要である。次元値毎にレコードを分類するために、次元値に関してレコードをソートする処理を利用することが可能である。特に、多次元集計においては、レコードを次元値の組毎にグループ化し、同一のグループに属するレコードに含まれる項目値に基づく測度を算出することによって、表形式データ全体の集計が達成される。よって、メモリ共有型マルチプロセッサシステムにおいて、大規模な表形式データを高速集計するためには、集計のための、特に、多次元集計のための次元を高速に作成する技術が必要である。
【特許文献１】国際公開ＷＯ００／１０１０３号公報
【特許文献２】国際公開ＷＯ２００６／１２６４６７号公報
【特許文献３】国際公開ＷＯ２００５／０４１０６７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００９】
本発明の目的は、上記の従来技術の問題点に鑑みて、メモリ共有型並列処理システムにおいて、表形式データから、多次元集計のための次元を表現する一意の項目値の組を効率的に抽出する方法を提供することである。【００１０】
本発明のさらなる目的は、上記の従来技術の問題点に鑑みて、メモリ共有型並列処理システムにおいて、表形式データから、多次元集計のための次元を表現する一意の項目値の組を効率的に抽出する装置を提供することである。【００１１】
本発明は、さらに、メモリ共有型並列処理システムにおいて、表形式データの多次元集計を効率的に実行する方法及び装置の提供を目的とする。
【課題を解決するための手段】
【００１２】
上記本発明の目的を達成するため、本発明の一態様によれば、表形式データのレコードのレコード番号が所定のレコード順に従って格納されたレコード番号配列、上記表形式データの上記レコードの所定の項目の項目値に対応する項目値番号がレコード番号に従って格納された項目値番号配列、及び、上記表形式データの項目値が当該項目値に対応する項目値番号の順序に従って格納された項目値配列を記憶する共有メモリと、
上記共有メモリにアクセス可能である複数台のプロセッサと、
を備えたメモリ共有型マルチプロセッサシステムにおいて、
所定の項目の組に関する一意の項目値の組を抽出する方法であって、
（ａ）上記複数台のプロセッサを用いて、上記所定の項目の組に関する項目値の組に対応する項目値番号の組の出現回数を並列的に数え上げ、上記出現回数の累積度数分布を表現する累積度数分布配列を上記共有メモリに生成するステップと、
（ｂ）上記複数台のプロセッサを用いて、上記レコード番号配列の要素の値を添字として使って上記項目値番号の組を並列的に読み出し、上記項目値番号の組より計算された値を添字として使って上記累積度数分布配列の要素を並列的に読み出し、上記累積度数分布配列の要素をインデックスポインタとして利用して上記レコード番号配列の要素の値をソートバージョンのレコード番号配列（すなわち、ソートされたレコード番号配列）に並列的に格納するステップと、
（ｃ）上記インデックスポインタとして利用された上記累積度数分布配列の要素の値に従って上記ソートされたレコード番号配列を上記一意の項目値の組を有するレコードのレコード番号のグループに区分するステップと、
（ｄ）上記区分されたレコード番号の各グループから１個のレコード番号を抽出することにより、上記一意の項目値の組を特定するステップと、
を備える方法が提供される。【００１３】
さらに、本発明の方法は、上記累積度数分布配列を上記共有メモリに並列的に生成するステップ（ａ）が、上記複数台のプロセッサを用いて、上記レコード番号配列に格納された上記レコード番号毎に、上記所定の項目の組に関する項目値の組に対応する項目値番号の組に含まれる上記項目値番号の範囲に応じて基数を設定することにより、上記項目値番号の組を、上記項目値番号の組に含まれる各項目値番号が各桁を表現する基数形式の仮想項目値番号に変換するステップを備えることを特徴とする。【００１４】
さらに、本発明の方法は、上記所定の項目の組に含まれる項目毎に上記累積度数分布配列を上記共有メモリに並列的に生成するステップ（ｉ）と、上記所定の項目の組に含まれる項目毎に上記レコード番号配列の要素の値を上記ソートされたレコード番号配列に並列的に格納するステップ（ｉｉ）と、上記所定の項目の組に含まれる項目毎に上記ソートされたレコード番号配列を上記一意の項目値の組を有するレコードのレコード番号のグループに区分するステップ（ｉｉｉ）とを備え、
上記累積度数分布配列を上記共有メモリに並列的に生成するステップ（ｉ）が、上記複数台のプロセッサを用いて、上記項目に関する項目値に対応する項目値番号の出現回数を並列的に数え上げ、上記出現回数の累積度数分布を表現する累積度数分布配列を上記共有メモリに並列的に生成するステップを備え、
上記レコード番号配列の要素を上記ソートされたレコード番号配列に並列的に格納するステップ（ｉｉ）が、上記複数台のプロセッサを用いて、上記項目値番号配列の要素の値を添字として使って上記項目値番号を並列的に読み出し、上記項目値番号を添字として使って上記累積度数分布配列の要素を並列的に読み出し、上記累積度数分布配列の要素をインデックスポインタとして利用して上記レコード番号配列の要素の値を上記ソートされたレコード番号配列に並列的に格納するステップを備えることを特徴とする。【００１５】
さらに、本発明の方法は、（ｅ）上記複数台のプロセッサを用いて、上記所定の項目値の組毎に別の項目に関する項目値を並列的に集計するステップをさらに備えることを特徴とする。【００１６】
さらに、本発明の方法は、（ｆ）上記複数台のプロセッサを用いて、上記ソートされたレコード番号配列中のレコード番号及び前記レコード番号に対応するグループのグループ番号を、前記レコード番号を添字として使って、補助的なレコード番号配列及び補助的なグループ番号配列に並列的に格納するステップと、
（ｇ）上記複数台のプロセッサを用いて、上記補助的なレコード番号配列の要素を添字として使って上記別の項目に関する項目値番号配列から並列的に要素を読み出し、前記項目値番号配列の要素を添字として使って上記別の項目に関する項目値配列から並列的に項目値を読み出し、上記補助的なレコード番号配列の要素を添字として使って上記補助的なグループ番号配列の要素を読み出し、上記補助的なグループ番号配列の要素を集計配列の添字として使って上記読み出された項目値の集計結果を上記集計配列に格納するステップと、
をさらに備えることを特徴とする。【００１７】
さらに、本発明の方法は、（ｈ）上記複数台のプロセッサを用いて、上記ソートされたレコード番号配列の要素を添字として使って上記別の項目に関する項目値番号配列から並列的に要素を読み出し、前記項目値番号配列の要素を添字として使って上記別の項目に関する項目値配列から並列的に項目値を読み出し、上記ソートされたレコード番号配列の要素に対応するグループのグループ番号を集計配列の添字として使って上記読み出された項目値の集計結果を上記集計配列に格納するステップをさらに備えることを特徴とする。【００１８】
上記本発明のさらなる目的を達成するため、本発明の一態様によれば、表形式データのレコードのレコード番号が所定のレコード順に従って格納されたレコード番号配列、上記表形式データの上記レコードの所定の項目の項目値に対応する項目値番号がレコード番号に従って格納された項目値番号配列、及び、上記表形式データの項目値が当該項目値に対応する項目値番号の順序に従って格納された項目値配列を記憶する共有メモリと、
上記共有メモリにアクセス可能である複数台のプロセッサと、
を備えたメモリ共有型マルチプロセッサシステムにおいて、
所定の項目の組に関する一意の項目値の組を抽出する装置であって、
（ａ）上記複数台のプロセッサを用いて、上記所定の項目の組に関する項目値の組に対応する項目値番号の組の出現回数を並列的に数え上げ、上記出現回数の累積度数分布を表現する累積度数分布配列を上記共有メモリに生成する手段と、
（ｂ）上記複数台のプロセッサを用いて、上記レコード番号配列の要素の値を添字として使って上記項目値番号の組を並列的に読み出し、上記項目値番号の組より計算された値を添字として使って上記累積度数分布配列の要素を並列的に読み出し、上記累積度数分布配列の要素をインデックスポインタとして利用して上記レコード番号配列の要素の値をソートバージョンのレコード番号配列（すなわち、ソートされたレコード番号配列）に並列的に格納する手段と、
（ｃ）上記インデックスポインタとして利用された上記累積度数分布配列の要素の値に従って上記ソートされたレコード番号配列を上記一意の項目値の組を有するレコードのレコード番号のグループに区分する手段と、
（ｄ）上記区分されたレコード番号の各グループから１個のレコード番号を抽出することにより、上記一意の項目値の組を特定する手段と、
を備える装置が提供される。【００１９】
さらに本発明の一態様によれば、表形式データのレコードのレコード番号が所定のレコード順に従って格納されたレコード番号配列、上記表形式データの上記レコードの所定の項目の項目値に対応する項目値番号がレコード番号に従って格納された項目値番号配列、及び、上記表形式データの項目値が当該項目値に対応する項目値番号の順序に従って格納された項目値配列を記憶する共有メモリと、
上記共有メモリにアクセス可能である複数台のプロセッサと、
を備えたコンピュータにロードされ、所定の項目の組に関する一意の項目値の組を抽出するコードを上記コンピュータに実行させるコンピュータ読み取り可能なプログラムであって、
（ａ）上記複数台のプロセッサを用いて、上記所定の項目の組に関する項目値の組に対応する項目値番号の組の出現回数を並列的に数え上げ、上記出現回数の累積度数分布を表現する累積度数分布配列を上記共有メモリに生成するコードと、
（ｂ）上記複数台のプロセッサを用いて、上記レコード番号配列の要素の値を添字として使って上記項目値番号の組を並列的に読み出し、上記項目値番号の組より計算された値を添字として使って上記累積度数分布配列の要素を並列的に読み出し、上記累積度数分布配列の要素をインデックスポインタとして利用して上記レコード番号配列の要素の値をソートバージョンのレコード番号配列（すなわち、ソートされたレコード番号配列）に並列的に格納するコードと、
（ｃ）上記インデックスポインタとして利用された上記累積度数分布配列の要素の値に従って上記ソートされたレコード番号配列を上記一意の項目値の組を有するレコードのレコード番号のグループに区分するコードと、
（ｄ）上記区分されたレコード番号の各グループから１個のレコード番号を抽出することにより、上記一意の項目値の組を特定するコードと、
を含むプログラムが提供される。【００２０】
さらに本発明の一態様によれば、表形式データのレコードのレコード番号が所定のレコード順に従って格納されたレコード番号配列、上記表形式データの上記レコードの所定の項目の項目値に対応する項目値番号がレコード番号に従って格納された項目値番号配列、及び、上記表形式データの項目値が当該項目値に対応する項目値番号の順序に従って格納された項目値配列を記憶する共有メモリと、上記共有メモリにアクセス可能である複数台のプロセッサと、を備えたコンピュータにロードされ、所定の項目の組に関する一意の項目値の組を抽出する本発明の方法を上記コンピュータに実行させるためのコンピュータプログラムプロダクトが提供される。【００２１】
さらに本発明の一態様によれば、表形式データのレコードのレコード番号が所定のレコード順に従って格納されたレコード番号配列、上記表形式データの上記レコードの所定の項目の項目値に対応する項目値番号がレコード番号に従って格納された項目値番号配列、及び、上記表形式データの項目値が当該項目値に対応する項目値番号の順序に従って格納された項目値配列を記憶する共有メモリと、上記共有メモリにアクセス可能である複数台のプロセッサと、を備えたコンピュータにロードされ、所定の項目の組に関する一意の項目値の組を抽出する本発明の方法を上記コンピュータに実行させるためのコンピュータプログラムが記録された記憶媒体が提供される。
【発明の効果】
【００２２】
本発明によれば、大規模な表形式データの多次元集計処理を高速に実現することが可能になる。
【図面の簡単な説明】
【００２３】
【図１】図１は、本発明の一実施形態によるコンピュータシステムの概要図である。
【図２】図２は、データ管理機構を説明するための表形式データの一例を表す図である。
【図３】図３は、本発明の一実施形態によるデータ管理機構の説明図である。
【図４】図４は、本発明の一実施形態による多次元集計処理のフローチャートである。
【図５】図５は、本発明の一実施形態による多項目一括ソート処理の説明図である。
【図６】図６は、本発明の一実施形態による仮想項目値番号を計算する処理の説明図である。
【図７】図７は、本発明の一実施形態による仮想項目値番号を数え上げる処理の説明図である。
【図８】図８は、本発明の一実施形態による累積度数分布配列を生成する処理の説明図である。
【図９】図９は、本発明の一実施例によるレコード番号配列の要素を並べ替える処理の説明図である。
【図１０】図１０は、本発明の一実施例によるレコード番号配列の要素を並べ替える処理の結果の説明図である。
【図１１】図１１は、本発明の一実施例によるユニーク行抽出処理の説明図である。
【図１２】図１２は、本発明の一実施形態によるユニーク行抽出処理によって抽出された一意の項目値の組を元のレコード番号配列に出現した順序に並べ替える処理の説明図である。
【図１３】図１３は、本発明の一実施形態によるユニーク行抽出処理によって抽出された一意の項目値の組を元のレコード番号配列に出現した順序に並べ替える処理の説明図である。
【図１４】図１４は、本発明の一実施形態による多項目逐次ソート処理の概要説明図である。
【図１５】図１５は、本発明の一実施形態による多項目逐次ソート処理の下位次元ソート処理における並列カウントアップ処理の説明図である。
【図１６】図１６は、本発明の一実施形態による多項目逐次ソート処理の下位次元ソート処理における累積度数分布配列生成処理の説明図である。
【図１７】図１７は、本発明の一実施形態による多項目逐次ソート処理の下位次元ソート処理におけるレコード番号配列の要素を並べ替える処理の説明図である。
【図１８】図１８は、本発明の一実施形態による多項目逐次ソート処理の上位次元ソート処理における並列カウントアップ処理の説明図である。
【図１９】図１９は、本発明の一実施形態による多項目逐次ソート処理の上位次元ソート処理における累積度数分布配列生成処理の説明図である。
【図２０】図２０は、本発明の一実施形態による多項目逐次ソート処理の上位次元ソート処理におけるレコード番号配列の要素を並べ替える処理の説明図である。
【図２１】図２１は、本発明の一実施形態によるレコード番号昇順タイプの測度並列算出処理における並べ替え処理の説明図である。
【図２２】図２２は、本発明の一実施形態によるレコード番号昇順タイプの測度並列算出処理における集計処理の説明図である。
【図２３】図２３は、本発明の一実施形態によるグループ番号昇順タイプの測度並列算出処理における集計処理の説明図である。
【図２４】図２４Ａ、Ｂは、実施例１による多段階並列ソートのソート対象のデータ構造の説明図である。
【図２５】図２５は、実施例１による多段階並列ソート方法のフローチャートである。
【図２６】図２６Ａ、Ｂは、実施例１による多段階並列ソート方法の第１段階のカウントアップステップの説明図（その１）である。
【図２７】図２７Ａ、Ｂは、実施例１による多段階並列ソート方法の第１段階のカウントアップステップの説明図（その２）である。
【図２８】図２８Ａ、Ｂは、実施例１による多段階並列ソート方法の第１段階のカウントアップステップの説明図（その３）である。
【図２９】図２９Ａ、Ｂは、実施例１による昇順の多段階並列ソート方法の第１段階の累計数化ステップの説明図である。
【図３０】図３０Ａ、Ｂは、実施例１による昇順の多段階並列ソート方法の第１段階の転送ステップの説明図（その１）である。
【図３１】図３１Ａ、Ｂは、実施例１による昇順の多段階並列ソート方法の第１段階の転送ステップの説明図（その２）である。
【図３２】図３２Ａ、Ｂは、実施例１による昇順の多段階並列ソート方法の第１段階の転送ステップの説明図（その３）である。
【図３３】図３３は、実施例１による多段階並列ソート方法の第２段階の初期化ステップの説明図である。
【図３４】図３４Ａ、Ｂは、実施例１による多段階並列ソート方法の第２段階のカウントアップステップの説明図（その１）である。
【図３５】図３５Ａ、Ｂは、実施例１による多段階並列ソート方法の第２段階のカウントアップステップの説明図（その２）である。
【図３６】図３６Ａ、Ｂは、実施例１による多段階並列ソート方法の第２段階のカウントアップステップの説明図（その３）である。
【図３７】図３７は、実施例１による昇順の多段階並列ソート方法の第２段階の累計数化ステップの説明図である。
【図３８】図３８Ａ、Ｂは、実施例１による昇順の多段階並列ソート方法の第２段階の転送ステップの説明図（その１）である。
【図３９】図３９Ａ、Ｂは、実施例１による昇順の多段階並列ソート方法の第２段階の転送ステップの説明図（その２）である。
【図４０】図４０Ａ、Ｂは、実施例１による昇順の多段階並列ソート方法の第２段階の転送ステップの説明図（その３）である。
【図４１】図４１Ａ−Ｃは、実施例１による昇順の多段階並列ソート方法を適用した結果を示す図（その１）である。
【図４２】図４２Ａ、Ｂは、実施例１による昇順の多段階並列ソート方法を適用した結果を示す図（その２）である。
【図４３】図４３、実施例２による多段階ソートを説明するためのデータ構造図である。
【図４４】図４４Ａ−Ｄは、実施例２による多段階ソートの第１段階のカウントアップ及び累計数化の説明図である。
【図４５】図４５Ａ、Ｂは、実施例２による多段階ソートの第１段階のレコード番号転送の説明図である。
【図４６】図４６は、実施例２による多段階ソートの第１段階のレコード番号転送の結果の説明図である。
【図４７】図４７は、実施例２による多段階ソートの第２段階の初期状態を表す図である。
【図４８】図４８Ａ−Ｃは、実施例２による多段階ソートの第２段階のカウントアップ及び累計数化の説明図である。
【図４９】図４９Ａ、Ｂは、実施例２による多段階ソートの第２段階のレコード番号転送の説明図である。
【図５０】図５０Ａ−Ｃは、実施例３における集計処理の内容を説明する図であり、図５０Ａは出力される集計結果テーブルを表し、図５０Bは１００万行からなる集計元テーブルを表し、図５０Ｃは６３２３３４個のレコードからなる集計結果テーブルを表している。
【図５１】図５１Ａ−Ｃは、実施例３の測定結果を示す図であり、図５１Ａは実施例３の５方式による処理の所要時間（ミリ秒）を表し、図５１Ｂは本発明による方式が旧方式に対して高速化された倍率を表し、図５１Ｃは図５１Ｂと同じ高速化倍率をグラフ化したものである。
【図５２】図５２Ａ−Ｃは、実施例４における集計処理の内容を説明する図であり、図５２Ａは出力される集計結果テーブルを表し、図５２Bは１００万行からなる集計元テーブルを表し、図５２Ｃは６３２３３４個のレコードからなる集計結果テーブルを表している。
【図５３】図５３Ａ−Ｃは、実施例４の測定結果を示す図であり、図５３Ａは実施例４の５方式による処理の所要時間（ミリ秒）を表し、図５３Ｂは本発明による方式が旧方式に対して高速化された倍率を表し、図５３Ｃは図５３Ｂと同じ高速化倍率をグラフ化したものである。
【符号の説明】
【００２４】
１０        コンピュータシステム
１２−１，１２−２，・・・，１２−ｐ        ＣＰＵ
１４        共有メモリ
１６        ＲＯＭ
１８        固定記憶装置
２０        ＣＤ−ＲＯＭドライバ
２２        Ｉ／Ｆ
２４        入力装置
２６        表示装置
【発明を実施するための最良の形態】
【００２５】
以下、本発明を実施するための種々の形態を図面と共に詳細に説明する。【００２６】
［コンピュータシステム構成］
図１は、本発明の一実施形態による表形式データの集計処理を実施するコンピュータシステム１０の概略図である。図１に示すように、このコンピュータシステム１０は、プログラムを実行することによりシステム全体および個々の構成部分を制御するｐ台のプロセッサ（ＣＰＵ）１２−１、１２−２、．．．１２−ｐと、ワークデータ等を記憶する、たとえば、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）のような共有メモリ１４と、プログラム等を記憶するＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）１６と、ハードディスク等の固定記憶媒体１８と、ＣＤ−ＲＯＭ１９をアクセスするためのＣＤ−ＲＯＭドライバ２０と、ＣＤ−ＲＯＭドライバ２０及び外部ネットワーク等（図示せず）へ繋がれた外部端子に接続されているインタフェース（Ｉ／Ｆ）２２と、キーボード及びマウス等のような入力装置２４と、コンピュータモニターのような表示装置２６とを備えている。ＣＰＵ１２、ＲＡＭ１４、ＲＯＭ１６、外部記憶媒体１８、Ｉ／Ｆ２２、入力装置２４及び表示装置２６は、バス２８を介して相互に接続されている。図示されていないが、各ＣＰＵは固有のローカルメモリを備え、ローカルメモリにはキャッシュメモリが搭載されている。【００２７】
本実施形態による方法をコンピュータシステム１０に実行させるプログラムは、ＣＤ−ＲＯＭ１９に収容され、ＣＤ−ＲＯＭドライバ２０に読取られても良いし、ＲＯＭ１６に予め記憶されていても良い。また、いったんＣＤ−ＲＯＭ１９から読み出したものを、外部記憶媒体１８の所定の領域に記憶しておいても良い。或いは、上記プログラムは、ネットワーク（図示せず）、外部端子、及び、Ｉ／Ｆ２２を介して、外部から供給されるものであっても良い。【００２８】
また、本発明の一実施形態によるメモリ共有型マルチプロセッサシステムは、コンピュータシステム１０に表形式データを集計するプログラムを実行させることにより実現される。【００２９】
［情報ブロックに基づくデータ管理機構］
図２はデータ管理機構を説明するための表形式データの一例を表す図である。この表形式データは、上述の国際公開第ＷＯ００／１０１０３号に提案したデータ管理機構を用いることにより、コンピュータ内では図３に示されるようなデータ構造として記憶される。このデータ構造は、市販されているコンピュータ、たとえば、パーソナルコンピュータのハードウェア資源、特に、プロセッサ及びメモリを使用して大規模な表形式データの検索、ソート、集計等を実現するために提案された、コンピュータのメモリ上に置かれる表形式データのデータ構造であることに注意すべきである。【００３０】
図３に示すように、表形式データの各レコードの並び順の番号と、内部データの並び順の番号を対応付けるレコード番号配列３０１（以下、この配列を「ＯｒｄＳｅｔ」のように略記する。）には、表形式のレコード毎に内部データの並び順番号が値として配置される。この例では、すべての表形式データが内部データとして表されるため、表形式データのレコード番号と内部データの並び順番号とは一致する。【００３１】
ここで、本明細書中での配列の記法について説明する。一般に、配列Ａは、添字をｉとすると、配列の要素がＡ［ｉ］のように表記できるが、図面中では、配列は、配列の要素Ａ［ｉ］は、実線で囲まれた領域内に示され、要素Ａ［ｉ］と要素Ａ［ｉ＋１］の境界は点線で示されている。また、要素Ａ［ｉ］の添字ｉが要素Ａ［ｉ］の左側に示されている。また、配列の添字ｉは０から始まる整数で表されている。【００３２】
もう一度図３に戻ると、性別に関しては、表形式データのレコード０に対応する内部データの並び順番号は、配列ＯｒｄＳｅｔ３０１から「０」であることがわかる。並び順番号が「０」であるレコードに関する実際の性別の値、即ち、「男」又は「女」は、実際の値が所定の順序に従ってソートされた値リストである項目値配列３０３（以下、項目値配列、すなわち、値リストを「ＶＬ」のように略記する。）へのポインタ配列である項目値番号配列３０２（以下、項目値番号配列、すなわち、ポインタ配列を「ＶＮｏ」のように略記する。）を参照することによって取得できる。ポインタ配列３０２は、配列ＯｒｄＳｅｔ３０１に格納されている並び順番号の順に従って、実際の値リスト３０３中の要素を指し示すポインタを格納している。これにより、表形式データのレコード「０」に対応する性別の項目値は、（１）配列ＯｒｄＳｅｔ３０１からレコード「０」に対応する並び順番号「０」を取り出し、（２）値リストへのポインタ配列３０２から並び順番号「０」に対応する要素「１」を取り出し、（３）値リスト３０３から、値リストへのポインタ配列３０２から取り出された要素「１」によって指し示される要素「女」を取り出すことにより取得できる。【００３３】
他のレコードに対しても、また、年齢及び身長に関しても同様に項目値を取得することができる。【００３４】
このように表形式データは、値リストＶＬと、値リストへのポインタ配列ＶＮｏの組合せにより表現され、この組合せを、特に、「情報ブロック」と称する。図３には、性別、年齢及び身長に関する情報ブロックがそれぞれ情報ブロック３０８、３０９及び３１０として示されている。【００３５】
単一のコンピュータが、単一のメモリ（物理的には複数であっても良いが、単一のアドレス空間に配置されアクセスされるという意味で単一のメモリ）であれば、当該メモリに、順序集合の配列ＯｒｄＳｅｔ、各情報ブロックを構成する値リストＶＬおよびポインタ配列ＶＮｏとを記憶しておけばよい。しかしながら、大量のレコードを保持するためには、その大きさに伴ってメモリ容量も大きくなるため、これらの大量のレコードを並列処理できるのが望ましい。【００３６】
そこで、本実施形態においては、複数台のプロセッサが共有メモリに記憶されたレコードのデータにアクセスし、複数台のプロセッサの並列処理により、高速な集計を実現している。【００３７】
［多次元集計処理］
次に、本実施形態によるメモリ共有型マルチプロセッサシステムにおける多次元集計処理を説明する。本実施形態による集計処理は、本質的に複数台のプロセッサが同じ処理を実行することによって達成される。すなわち、この集計処理は、単一の集計処理命令を複数台のプロセッサへ与えることにより、複数台のプロセッサが並列に動作して集計処理を実行できるように構成されている。複数台のプロセッサは、同じ動作を実行するので、一つのプログラムを作成するだけで、並列処理を実現できる。【００３８】
図４は本発明の一実施形態による表形式データの多次元集計処理のフローチャートである。この多次元集計処理は、図１に示されるようなコンピュータシステム１０によって実行される。コンピュータシステム１０の共有メモリ１４は、表形式データのレコードのレコード番号が所定のレコード順に従って格納されたレコード番号配列、上記表形式データの上記レコードの所定の項目の項目値に対応する項目値番号がレコード番号に従って格納された項目値番号配列、及び、上記表形式データの項目値が当該項目値に対応する項目値番号の順序に従って格納された項目値配列を記憶する。複数台のプロセッサ１２−１，・・・，１２−ｐは共有メモリ１４にアクセス可能である。【００３９】
各プロセッサは、上記所定の項目の組に関する項目値の組に対応する項目値番号の組の出現回数を並列的に数え上げ（ステップ４０１）、上記出現回数の累積度数分布を表現する累積度数分布配列を上記共有メモリに生成する（ステップ４０２）。所定の項目の組とは、多次元集計の際に用いられる次元の組に相当し、項目値の組は次元値の組に相当する。【００４０】
次に、各プロセッサは、上記レコード番号配列の要素の値を添字として使って上記項目値番号の組を並列的に読み出し、上記項目値番号の組によって計算された値を添字として使って上記累積度数分布配列の要素を並列的に読み出し、上記累積度数分布配列の要素をインデックスポインタとして利用して上記レコード番号配列の要素の値をソートバージョンのレコード番号配列（すなわち、ソートされたレコード番号配列）に並列的に格納する（ステップ４０３）。たとえば、項目値番号の組は、各項目値番号が各桁に対応するように基数表現された値に変換することが可能である。この基数表現への変換は、乗算の代わりにビットシフト演算を用いることによって高速化される。しかし、項目値番号の組から値への変換は、基数表現に限定されることはなく、変換後の値から元の項目値番号の組へ逆変換できる演算であれば、どのような変換でも構わない。これにより、元のレコード番号配列の要素は、項目値の組に対応する項目値番号の組に関してソートされ、ソートされた要素が格納されたソートバージョンのレコード番号配列が生成される。【００４１】
さらに、少なくとも１台のプロセッサが、上記インデックスポインタとして利用された上記累積度数分布配列の要素の値に従って上記ソートバージョンのレコード番号配列を上記一意の項目値の組を有するレコードのレコード番号のグループに区分する（ステップ４０４）。これにより、レコードは、同じ項目値の組、すなわち、同じ次元値の組を有するレコードのグループに分類される。【００４２】
少なくとも１台のプロセッサが、上記区分されたレコード番号の各グループから１個のレコード番号を抽出することにより、上記一意の項目値の組を特定する（ステップ４０５）。これにより、多次元集計の際に利用される一意の次元値の組が特定される。【００４３】
最後に、各プロセッサは、上記所定の項目値の組毎に別の項目に関する項目値を並列的に集計する（ステップ４０６）。【００４４】
以下では、多次元並列集計処理において用いられる多次元並列ソート処理（多項目一括ソート処理又は多項目逐次ソート処理）、ユニーク行抽出処理、及び、測度並列算出処理（レコード番号昇順集計処理又はグループ番号昇順集計処理）について詳述する。【００４５】
さらに、本発明の種々の実施形態では、対称型マルチプロセッサシステムの特長を十分に発揮させるため、種々の配列に適用される処理は、各配列を複数台のプロセッサにほぼ均等に割り当てることにより、複数台のプロセッサによって並列処理される。以下では、発明の理解を助けるために、プロセッサの台数ｎが４であるとして説明するが、プロセッサの台数が４台に限定されないことは当業者に明白であろう。【００４６】
［多項目一括ソート処理］
多項目一括ソート処理とは、表形式データの複数の項目に関するソートを一括に行う処理であり、（ｉ）ソート処理が高速化される、（ｉｉ）プログラムの記述が容易化される、（ｉｉｉ）同一の項目値の組を有するレコードの抽出が簡単化される、という利点がある。【００４７】
図５は、本発明の一実施形態による多項目一括ソート処理の説明図である。同図に示された表形式データ５０１は、レコード番号が０から１５で表される１６個のレコードを含み、各レコードには、「年齢」という項目Ａｇｅと「クラス」という項目Ｃｌａｓｓが含まれている。項目「年齢」は多次元集計の第１の次元Ｄｉｍ−１に対応し、項目「クラス」は多次元集計の第２の次元Ｄｉｍ−２に対応している。この表形式データは、本実施形態では、レコード番号配列５０３と、第１の次元に関する項目値番号配列５１１及び項目値配列５１２と、第２の次元に関する項目値番号配列５２１及び項目値配列５２２というデータ構造５０２の形で共有メモリ１４上に構築されている。【００４８】
このような表形式データは、「クラス」を下位次元とし、「年齢」を上位次元として、「クラス」及び「年齢」の２次元に関してソートすると、同図の矢印の右側に示されるような表形式データに変換される。ソート順は、各項目の項目値配列に格納されている項目値の順番と一致する。よって、同図の例では、「年齢」は昇順にソートされ、「クラス」はアルファベット順にソートされている。しかし、実際のソートは、項目値自体ではなく、項目値に対応する項目値番号に関して行われるので、本実施形態は実データのデータ形式とは無関係に適用できるという利点がある。【００４９】
表形式データ５５１は、多項目一括ソートの結果に従って表形式データの行の順序を入れ替えたものである。このソート結果は、本実施形態では、レコード番号配列５０３からレコード番号配列５５３への要素の順序の入れ替えによって表現されている。尚、本実施形態の説明において、多項目一括ソート処理の次元数は２として説明しているが、次数が２に限定されないことは当業者に明白であろう。【００５０】
次に、図５に示された表形式データの例を用いて、多項目一括ソート処理を詳細に説明する。【００５１】
多項目一括ソート処理は、複数の項目のそれぞれに関する各項目値を組み合わせて新たな仮想的な項目値番号（以下では、仮想項目値番号と称する）を生成し、この仮想項目値番号に基づいてレコード番号を一度にソートする処理である。項目値番号の組み合わせは、上位次元の項目値番号が上位の桁、下位次元の項目値番号が下位の桁となるように、項目値番号の組を基数形式で表現することによって仮想項目値番号に変換される。基数は、各項目値番号が取り得る値の範囲に応じて決められる。たとえば、図５の例のように、第１の次元の項目値番号が０から２までの値を取り、第２の次元の項目値番号が０から３の値を取るならば、基数として４以上の整数を設定することにより、項目値番号の組み合わせが、４を基数とする基数形式で表現された仮想項目値番号に変換できる。【００５２】
図６は本発明の一実施形態による仮想項目値番号の計算を説明する図である。本実施形態では、４台のプロセッサＣＰＵ−０、ＣＰＵ−１、ＣＰＵ−２、ＣＰＵ−３のそれぞれは、レコード番号の個数と一致するサイズを有する項目値番号配列のそれぞれの部分を受け持ち、第１の次元の項目値番号と第２の次元の項目値番号を組み合わせて仮想項目値番号を生成する。【００５３】
具体的には、ｉがレコード番号を表し（本例では、ｉ＝０，１，２，・・・，１５）、第１の次元の項目値番号配列をＶＮｏ＿１（図５及び６において５１１で示されている）、第２の次元の項目値番号配列ＶＮｏ＿２（図５及び６において５２１で示されている）、仮想項目値番号配列をＶ＿ＶＮｏ（図６において６０１で示されている）とすると、
ＣＰＵ−０が、受け持ち範囲６０２、すなわち、ｉ＝０，１，２，３に対して、
Ｖ＿ＶＮｏ［ｉ］＝ＶＮｏ＿１［ｉ］＊４＋ＶＮｏ＿２［ｉ］
を計算し、同様に、ＣＰＵ−１が、受け持ち範囲６０３、すなわち、ｉ＝４，５，６，７に対して、
Ｖ＿ＶＮｏ［ｉ］＝ＶＮｏ＿１［ｉ］＊４＋ＶＮｏ＿２［ｉ］
を計算し、ＣＰＵ−２が、受け持ち範囲６０４、すなわち、ｉ＝８，９，１０，１１に対して、
Ｖ＿ＶＮｏ［ｉ］＝ＶＮｏ＿１［ｉ］＊４＋ＶＮｏ＿２［ｉ］
を計算し、ＣＰＵ−３が、受け持ち範囲６０５、すなわち、ｉ＝１２，１３，１４，１５に対して、
Ｖ＿ＶＮｏ［ｉ］＝ＶＮｏ＿１［ｉ］＊４＋ＶＮｏ＿２［ｉ］
を計算する。【００５４】
上記の説明では、仮想項目値番号配列の計算は、乗算と加算によって実現されているが、計算を高速化するため、好ましくは、乗算の代わりにビットシフト演算が採用される。【００５５】
次に、各プロセッサは、それぞれの受け持つレコード番号配列の範囲内の要素に関して、仮想項目値番号の出現回数を数え上げる。図７は本発明の一実施形態による仮想項目値番号を数え上げる処理の説明図である。この数え上げ処理もまた、プロセッサが受け持ち範囲を分担する。本例では、レコード番号配列５０３は、４台のプロセッサのそれぞれの受け持ち範囲７０１、７０２、７０３及び７０４に分割される。【００５６】
レコード番号をｉ、レコード番号配列をＯｒｄＳｅｔ、仮想項目値番号配列をＶ＿ＶＮｏ、プロセッサ番号をｊ（ｊ＝０，１，２，３）としてプロセッサｊが数え上げた仮想項目値番号の個数を格納するカウント配列をＣｏｕｎｔ［ｊ］とすると、本実施形態による数え上げ処理は、たとえば、Ｃ言語スタイルでは、
ｆｏｒ  （ｉ＝０；ｉ＜４；ｉ＋＋）  ｛
ｆｏｒ  （ｊ＝０；ｊ＜４；ｊ＋＋）  ｛
Ｃｏｕｎｔ［ｊ］［Ｖ＿ＶＮｏ［ＯｒｄＳｅｔ［ｊ＊４＋ｉ］］］＋＋；
｝
｝
と記述される。図７の例では、初期化されたカウント配列７１０、７１１、７１２及び７１３は、仮想項目値番号の数え上げ処理によって、カウント配列７２０、７２１、７２２及び７２３となる。尚、本例において、第１の項目値配列をＶＬ＿１、第２の項目値配列をＶＬ＿２とすると、カウント配列Ｃｏｕｎｔのサイズは、（ＶＬ＿１のサイズ）×（ＶＬ＿２）のサイズに一致する。【００５７】
この数え上げ処理の結果は、たとえば、ＣＰＵ−０の受け持ち範囲内では、仮想順位番号＝０、２、５及び９がそれぞれ１個ずつ存在し、ＣＰＵ−１の受け持ち範囲内では、仮想順位番号＝６、７、１０及び１１がそれぞれ１個ずつ存在し、ＣＰＵ−２の受け持ち範囲内では、仮想順位番号０、３、４及び５がそれぞれ１個ずつ存在し、ＣＰＵ−３の受け持ち範囲内では、仮想順位番号＝２、５、１０及び１１がそれぞれ１個ずつ存在することを表している。【００５８】
続いて、本発明の一実施形態では、コンピュータシステム１０は、仮想項目値番号配列の各要素を累計数化して、仮想項目値番号の出現回数の累積度数分布配列を生成する。図８は、本発明の一実施形態による累積度数分布配列を生成する処理の説明図である。プロセッサｊの受け持ち範囲内のカウント配列をＣｏｕｎｔ［ｊ］、累積度数分布配列をＡｇｇｒ［ｊ］とすると、累積度数分布は、
Ａｇｇｒ［０］［０］＝０
Ａｇｇｒ［１］［０］＝Ａｇｇｒ［０］［０］＋Ｃｏｕｎｔ［０］［０］
Ａｇｇｒ［２］［０］＝Ａｇｇｒ［１］［０］＋Ｃｏｕｎｔ［１］［０］
Ａｇｇｒ［３］［０］＝Ａｇｇｒ［２］［０］＋Ｃｏｕｎｔ［２］［０］
Ａｇｇｒ［０］［１］＝Ａｇｇｒ［３］［０］＋Ｃｏｕｎｔ［３］［０］
Ａｇｇｒ［１］［１］＝Ａｇｇｒ［０］［１］＋Ｃｏｕｎｔ［０］［１］
Ａｇｇｒ［２］［１］＝Ａｇｇｒ［１］［１］＋Ｃｏｕｎｔ［１］［１］
Ａｇｇｒ［３］［１］＝Ａｇｇｒ［２］［１］＋Ｃｏｕｎｔ［２］［１］
Ａｇｇｒ［０］［２］＝Ａｇｇｒ［３］［１］＋Ｃｏｕｎｔ［３］［１］
・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・
途中省略
・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・
Ａｇｇｒ［３］［１０］＝Ａｇｇｒ［２］［１０］＋Ｃｏｕｎｔ［２］［１０］
Ａｇｇｒ［０］［１１］＝Ａｇｇｒ［３］［１０］＋Ｃｏｕｎｔ［３］［１０］
Ａｇｇｒ［１］［１１］＝Ａｇｇｒ［０］［１１］＋Ｃｏｕｎｔ［０］［１１］
Ａｇｇｒ［２］［１１］＝Ａｇｇｒ［１］［１１］＋Ｃｏｕｎｔ［１］［１１］
Ａｇｇｒ［３］［１１］＝Ａｇｇｒ［２］［１１］＋Ｃｏｕｎｔ［２］［１１］
として計算される。この計算は、４台のプロセッサのうちのいずれか１台のプロセッサが単独で行ってもよいが、４台のプロセッサに仮想項目値番号の範囲を割り当てて、４台のプロセッサによって並列に行ってもよい。【００５９】
４台のプロセッサによって並列的に累積度数分布を計算する場合には、最初に、各仮想項目値番号ｉの出現回数の合計値Ｓｕｍ［ｉ］を、たとえば、
ｆｏｒ（ｉ＝０；ｉ＜１２；ｉ＋＋）  ｛
ｆｏｒ（ｊ＝０；ｊ＜４；ｊ＋＋）  ｛
Ｓｕｍ［ｉ］＝Ｃｏｕｎｔ［ｊ］［ｉ］；
｝
｝
によって、並列的に計算する。本実施形態では、たとえば、ＣＰＵ−０がｉ＝０，１，２のループを担当し、ＣＰＵ−１がｉ＝３，４，５のループを担当し、ＣＰＵ−２がｉ＝６，７，８のループを担当し、ＣＰＵ−３がｉ＝９，１０，１１のループを担当する。【００６０】
続いて、たとえば、４台のプロセッサが並列的に、
Ａｇｇｒ［０］［０］＝０
Ａｇｇｒ［１］［０］＝Ａｇｇｒ［０］［０］＋Ｃｏｕｎｔ［０］［０］
Ａｇｇｒ［２］［０］＝Ａｇｇｒ［１］［０］＋Ｃｏｕｎｔ［１］［０］
Ａｇｇｒ［３］［０］＝Ａｇｇｒ［２］［０］＋Ｃｏｕｎｔ［２］［０］
Ａｇｇｒ［０］［１］＝Ｓｕｍ［０］
Ａｇｇｒ［１］［１］＝Ａｇｇｒ［０］［１］＋Ｃｏｕｎｔ［０］［１］
Ａｇｇｒ［２］［１］＝Ａｇｇｒ［１］［１］＋Ｃｏｕｎｔ［１］［１］
Ａｇｇｒ［３］［１］＝Ａｇｇｒ［２］［１］＋Ｃｏｕｎｔ［２］［１］
Ａｇｇｒ［０］［２］＝Ｓｕｍ［１］
・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・
途中省略
・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・
Ａｇｇｒ［３］［１０］＝Ａｇｇｒ［２］［１０］＋Ｃｏｕｎｔ［２］［１０］
Ａｇｇｒ［０］［１１］＝Ｓｕｍ［１０］
Ａｇｇｒ［１］［１１］＝Ａｇｇｒ［０］［１１］＋Ｃｏｕｎｔ［０］［１１］
Ａｇｇｒ［２］［１１］＝Ａｇｇｒ［１］［１１］＋Ｃｏｕｎｔ［１］［１１］
Ａｇｇｒ［３］［１１］＝Ａｇｇｒ［２］［１１］＋Ｃｏｕｎｔ［２］［１１］
を実行することによって、累積度数分布配列が得られる。【００６１】
図８には、最終的な累積度数分布配列８０１、８０２、８０３及び８０４が示されている。【００６２】
本発明の一実施形態による多項目一括ソート処理では、最後に、元のレコード番号配列の要素をソート後のレコード番号配列に転送する。図９は、本発明の一実施形態によるレコード番号配列の要素を並べ替える処理の説明図である。この処理では、レコード番号配列５０３は、図７と同様に、４台のプロセッサの受け持ち範囲７０１、７０２、７０３及び７０４に分割され、４台のプロセッサが並列処理を実行する。元のレコード番号配列をＯｒｄＳｅｔ、ソート後のレコード番号配列をＯｒｄＳｅｔ’、仮想項目値番号配列をＶ＿ＶＮｏ、累積度数分布配列をＡｇｇｒ［ｊ］（ｊはプロセッサ番号）とすると、プロセッサ０番、すなわち、ＣＰＵ−０による並べ替え処理は、
ｆｏｒ  （ｉ＝０；ｉ＜４；ｉ＋＋）  ｛
ＯｒｄＳｅｔ’［Ａｇｇｒ［０］［Ｖ＿ＶＮｏ［ＯｒｄＳｅｔ［ｉ］］］］＝ＯｒｄＳｅｔ［ｉ］；
Ａｇｇｒ［０］［Ｖ＿ＶＮｏ［ＯｒｄＳｅｔ［ｉ］］］＋＋；
｝
と記述できる。ここで、Ａｇｇｒ［０］［Ｖ＿ＶＮｏ［ＯｒｄＳｅｔ［ｉ］］］＋＋から、累積度数分布配列の要素がインデックスポインタとして利用されていることがわかる。たとえば、図８では、レコード番号０に対して、
ＯｒｄＳｅｔ［０］＝０
Ｖ＿ＶＮｏ［ＯｒｄＳｅｔ［０］］＝Ｖ＿ＶＮｏ［０］＝５
Ａｇｇｒ［０］［Ｖ＿ＶＮｏ［ＯｒｄＳｅｔ［０］］］＝Ａｇｇｒ［０］［５］＝６
ＯｒｄＳｅｔ’［Ａｇｇｒ［０］［Ｖ＿ＶＮｏ［ＯｒｄＳｅｔ［０］］］］＝ＯｒｄＳｅｔ’［６］
となり、したがって、
ＯｒｄＳｅｔ’［６］＝０
Ａｇｇｒ［０］［５］＝７
となることが示されている。【００６３】
さらに、プロセッサ番号ｊをループ変数とすると、本実施形態によるレコード番号配列の要素を並べ替える処理は、
ｆｏｒ  （ｊ＝０；ｊ＜４；ｊ＋＋）  ｛
ｆｏｒ  （ｉ＝０；ｉ＜４；ｉ＋＋）  ｛
ＯｒｄＳｅｔ’［Ａｇｇｒ［ｊ］［Ｖ＿ＶＮｏ［ＯｒｄＳｅｔ［ｊ＊４＋ｉ］］］］＝ＯｒｄＳｅｔ［ｊ＊４＋ｉ］；
Ａｇｇｒ［ｊ］［Ｖ＿ＶＮｏ［ＯｒｄＳｅｔ［ｊ＊４＋ｉ］］］＋＋；
｝
｝
と記述できる。【００６４】
図１０は、本発明の一実施形態によるレコード番号配列の要素を並べ替える処理の結果を説明する図である。累積度数分布配列１００１、１００２、１００３及び１００４は、ソート後の累積度数分布配列を表し、ソートバージョンのレコード番号配列１００５はソート後のレコード番号配列を表している。このように、本発明の一実施形態によるレコード番号配列の要素を並べ替える処理により、元のレコード番号配列５０３の要素は、第１の次元と第２の次元の二つの次元に関して一括的にソートされ、ソートバージョンのレコード番号配列１００５に格納されている。【００６５】
［ユニーク行抽出処理］
多項目一括ソート処理によって、多次元集計の対象となるレコードは複数の次元に関して所定の順序でソートされている。多次元集計を行うためには、次元値を特定する必要がある。そのため、本発明の一実施形態では、同一の次元値を有するレコードの中から代表となるレコードを抽出する。本明細書では、このようなレコードを抽出する処理をユニーク行抽出処理とも称する。【００６６】
ユニーク行抽出処理では、複数台のプロセッサのうちの何れかのプロセッサが、インデックスポインタとして利用された累積度数分布配列の要素の値に従ってソートバージョンのレコード番号配列を一意の項目値の組を有するレコードのレコード番号のグループに区分し、区分されたレコード番号の各グループから１個のレコード番号を抽出することにより、一意の項目値の組を特定する。【００６７】
レコード番号をレコード番号配列に格納する際に、累積度数分布配列の要素をインデックスポインタとして使用すると、レコード番号を格納する毎に累積度数分布配列の要素がインクリメントされる。その結果、累積度数分布配列の要素は、レコード番号がレコード番号配列中に格納されている位置を表現している。よって、ソートバージョンのレコード番号配列の完成後に、累積度数分布配列の要素の値はソートバージョンのレコード番号配列中のレコード番号のグループの境界を指している。【００６８】
図１１は、本発明の一実施形態によるユニーク行抽出処理の説明図である。ソート後の累積度数分布配列の要素、本例では、出現回数の数え上げを行う際に、レコード番号配列の最後の範囲を担当したＣＰＵ−４が生成したカウント配列に基づく累積度数分布配列１００４の要素は、レコード番号をグループに区分するため利用できる。より具体的に説明すると、累積度数分布配列がインデックスポインタとして利用されたという事実から、最終的な累積度数分布配列１００４の各要素が指し示しているソートバージョンのレコード番号配列１００５の要素、すなわち、
ＯｒｄＳｅｔ’［Ａｇｇｒ［３］［０］］＝ＯｒｄＳｅｔ’［２］
ＯｒｄＳｅｔ’［Ａｇｇｒ［３］［１］］＝ＯｒｄＳｅｔ’［２］
ＯｒｄＳｅｔ’［Ａｇｇｒ［３］［２］］＝ＯｒｄＳｅｔ’［４］
ＯｒｄＳｅｔ’［Ａｇｇｒ［３］［３］］＝ＯｒｄＳｅｔ’［５］
ＯｒｄＳｅｔ’［Ａｇｇｒ［３］［４］］＝ＯｒｄＳｅｔ’［６］
ＯｒｄＳｅｔ’［Ａｇｇｒ［３］［５］］＝ＯｒｄＳｅｔ’［９］
ＯｒｄＳｅｔ’［Ａｇｇｒ［３］［６］］＝ＯｒｄＳｅｔ’［１０］
ＯｒｄＳｅｔ’［Ａｇｇｒ［３］［７］］＝ＯｒｄＳｅｔ’［１１］
ＯｒｄＳｅｔ’［Ａｇｇｒ［３］［８］］＝ＯｒｄＳｅｔ’［１１］
ＯｒｄＳｅｔ’［Ａｇｇｒ［３］［９］］＝ＯｒｄＳｅｔ’［１２］
ＯｒｄＳｅｔ’［Ａｇｇｒ［３］［１０］］＝ＯｒｄＳｅｔ’［１４］
ＯｒｄＳｅｔ’［Ａｇｇｒ［３］［１１］］＝ＯｒｄＳｅｔ’［１６］
は、一意の項目値の組を有するレコードのグループの境界を表していることがわかる。【００６９】
これにより、図１１の例では、レコード番号は、
グループ０＝｛１，９｝  （同図では、１１０１を参照）
グループ１＝｛３，１５｝  （同図では、１１０２を参照）
グループ２＝｛１１｝  （同図では、１１０３を参照）
グループ３＝｛８｝  （同図では、１１０４を参照）
グループ４＝｛０，１０，１４｝  （同図では、１１０５を参照）
グループ５＝｛５｝  （同図では、１１０６を参照）
グループ６＝｛４｝  （同図では、１１０７を参照）
グループ７＝｛２｝  （同図では、１１０８を参照）
グループ８＝｛６，１２｝  （同図では、１１０９を参照）
グループ９＝｛７，１３｝  （同図では、１１１０を参照）
の１０個のグループに分類されることがわかる。【００７０】
このようにグループは１０個しかないので、グループ毎に１個ずつのレコード番号、すなわち、全部で１０個のレコード番号を代表レコード番号として抽出することにより、一意の項目値の組を抽出することができる。【００７１】
図１１では、抽出された代表レコード番号を含む代表レコード番号配列ＯｒｄＳｅｔ’’が１１２０として示されている。【００７２】
次に、ｉをループ変数、ＶＬ＿１及びＶＮｏ＿１を第１の次元の項目値配列及び項目値番号配列、ＶＬ＿２及びＶＮｏ＿２を第２の次元の項目値配列及び項目値番号配列とし、集計の第１の次元の次元値配列をＤｉｍ−１、第２の次元の次元値配列をＤｉｍ−２とすると、たとえば、
ｆｏｒ  （ｉ＝０；ｉ＜１０；ｉ＋＋）  ｛
Ｄｉｍ−１［ｉ］＝ＶＬ＿１［ＶＮｏ＿１［ＯｒｄＳｅｔ’’［ｉ］］］；
Ｄｉｍ−２［ｉ］＝ＶＬ＿２［ＶＮｏ＿２［ＯｒｄＳｅｔ’’［ｉ］］］；
｝
を複数台のプロセッサで並列に実行することによって、集計の次元１１３０が作成される。【００７３】
上記のユニーク行抽出処理において、一意の項目値の組は、項目値に関してソートされた順番に抽出されている。たとえば、一意の項目値の組を、元のレコード番号配列ＯｒｄＳｅｔに出現した順序で抽出するには、代表レコード番号配列の要素を元のレコード番号配列に出現した順序で並べ替えればよい。図１２及び１３は、本発明の一実施形態によるユニーク行抽出処理によって抽出された一意の項目値の組を元のレコード番号配列に出現した順序に並べ替える処理の説明図である。【００７４】
この処理は、代表レコード番号配列に格納されたレコード番号に対応するビットマップフラグを作成するステップと、元のレコード番号の順にビットマップフラグをチェックし、フラグがセットされているレコード番号を元のレコード番号配列に格納されたレコード番号の順序で抽出するステップとを含む。これらのステップは、代表レコード番号配列及び元のレコード番号配列を複数台（本例では、４台）のＣＰＵに割り当てることによって並列処理可能である。【００７５】
図１２を参照すると、代表レコード番号配列ＯｒｄＳｅｔ’’１１２０は、ＣＰＵ−０の受け持ち範囲１２００と、ＣＰＵ−１の受け持ち範囲１２０１と、ＣＰＵ−２の受け持ち範囲１２０２と、ＣＰＵ−３の受け持ち範囲１２０３とに分割されている。各プロセッサは、代表レコード番号配列１１２０からそのプロセッサ自体の受け持ち範囲内の要素、すなわち、レコード番号を読み出し、それぞれのビットマップフラグ配列１２１０、１２１１、１２１２及び１２１３の中で、読み出されたレコード番号に対応するビットをセットする。たとえば、ＣＰＵ−０は、ＯｒｄＳｅｔ’’［０］＝１、ＯｒｄＳｅｔ’’［１］＝３及びＯｒｄＳｅｔ’’［２］＝１１の３個のレコード番号を読み出し、ビットマップフラグ配列中の３個のフラグをセットする。すなわち、Ｆｌａｇ＿０［１］＝１、Ｆｌａｇ＿０［３］＝１、及び、Ｆｌａｇ＿０［１１］＝１である。ビットマップフラグ配列Ｆｌａｇ＿０のその他の要素は０のままである。ＣＰＵ−１、ＣＰＵ−２及びＣＰＵ−３も同様に、それぞれ、ビットマップフラグ配列Ｆｌａｇ＿１、Ｆｌａｇ＿２及びＦｌａｇ＿３を設定する。これらの処理は、複数台のプロセッサによって並列に実行される。【００７６】
次に、ビットマップフラグ配列１２１０、１２１１、１２１２及び１２１３のそれぞれが、先頭から順番に、ＣＰＵ−０、ＣＰＵ−１、ＣＰＵ−２及びＣＰＵ−３の４台のプロセッサに割り当てられ、全体的なビットマップフラグ配列Ｆｌａｇが作成される。具体的には、各プロセッサがそれぞれの受け持ち範囲１２２０、１２２１、１２２２、１２２３に関して、論理和演算を並列に実行することにより、全体として、
ｆｏｒ  （ｉ＝０；ｉ＜１６；ｉ＋＋）  ｛
Ｆｌａｇ［ｉ］＝Ｆｌａｇ＿１［ｉ］  ＯＲ  Ｆｌａｇ＿２［ｉ］  ＯＲ  Ｆｌａｇ＿３［ｉ］  ＯＲ  Ｆｌａｇ＿４［ｉ］；
｝
が実行される。これにより、図１２の全体的なビットマップフラグ配列１２３０が得られる。【００７７】
図１３を参照すると、各プロセッサは、全体的な元のレコード番号配列５０３の受け持ち範囲７０１、７０２、７０３、７０４の中の要素の順に、全体的なビットマップフラグ配列１２３０の要素のフラグがセットされているか否かをチェックし、フラグがセットされているレコード番号をチェック順に作業配列１３００に格納し、最後に作業配列をさらなる代表レコード番号配列１３１０に格納する。さらなる代表レコード番号配列１３１０は、代表レコード番号が元のレコード番号配列に格納されたレコード番号の順序で格納されている配列である。【００７８】
次に、ｉをループ変数、ＶＬ＿１及びＶＮｏ＿１を第１の次元の項目値配列及び項目値番号配列、ＶＬ＿２及びＶＮｏ＿２を第２の次元の項目値配列及び項目値番号配列とし、集計の第１の次元の次元値配列をＤｉｍ−１、第２の次元の次元値配列をＤｉｍ−２とすると、たとえば、
ｆｏｒ  （ｉ＝０；ｉ＜１０；ｉ＋＋）  ｛
Ｄｉｍ−１［ｉ］＝ＶＬ＿１［ＶＮｏ＿１［ＯｒｄＳｅｔ’’’［ｉ］］］；
Ｄｉｍ−２［ｉ］＝ＶＬ＿２［ＶＮｏ＿２［ＯｒｄＳｅｔ’’’［ｉ］］］；
｝
を複数台のプロセッサで並列に実行することによって、集計の次元１３２０が作成される。【００７９】
［多項目逐次ソート処理］
多項目並列ソート処理には、上述の多項目一括ソート処理の他に、これから説明する多項目逐次ソート処理がある。たとえば、仮想項目値番号のビット数がコンピュータ上で処理できる整数の範囲を超える場合、上記の多項目一括ソート処理を適用できなくなるので、この多項目逐次ソート処理が適用される。以下では、図５の表形式データを用いて、本発明の一実施形態による多項目逐次ソート処理を説明する。以下の例では、次元数を２として説明しているが、次元数２の多項目逐次ソート処理を多段階化することにより任意の次数の多項目逐次ソート処理を実現可能であることは当業者に明白であろう。【００８０】
多項目逐次ソート処理は、上位次元の項目に関するソートより下位次元の項目に関するソートを先に実行する。上位次元と下位次元の考え方は、多項目一括ソート処理に関して説明した通りである。そして、ユニーク行抽出処理に関して説明したグループ番号の考え方を下位次元のソートと上位次元のソートのそれぞれにおいて導入することにより、比較演算を行うことなくグループ分けを行っている。下位次元のソートによって得られたグループ番号を上位次元のソートの際にレコード番号と共にソートすることにより、上位次元のグループ化が簡単化される。尚、項目値番号が０から連続的に使用されることが保証されるならば、項目値番号をグループ番号として使用することも可能であるが、一般には、データの追加・削除により実際に使用されている項目値番号が飛び飛びの値となることもあるので、好ましくは、項目値番号とは別個にグループ番号が使用される。【００８１】
図１４は、本発明の一実施形態による多項目逐次ソート処理の概要説明図である。ソート処理前の表形式データ５０１は、図５に示されているデータと同じである。下位次元である項目「クラス」に関して「クラス」の項目値の昇順（たとえば、アルファベット順）に表形式データをソートすると、下位次元でソートされた表形式データ１４００が得られる。このとき、「クラス」の項目値に基づく第１のグループ番号配列１４０１を表形式データ１４００に付与する。【００８２】
次に、表形式データ１４００と第１のグループ番号配列１４０１を、上位次元である項目「年齢」の項目値の昇順にソートすると、ソートされた表形式データ１４１０と、ソーとされた第１のグループ番号配列１４１１とが得られる。このとき、ソート結果に基づいて新たな第２のグループ番号配列１４１２を表形式データ１４１０に付与する。【００８３】
最後に、第２のグループ番号配列１４１２を参照して、表形式データ１４１０からユニーク行を抽出すると、多項目一括ソート処理で作成された集計の次元と同じ集計の次元１１３０が得られる。【００８４】
以下では、図面を参照して、本発明の一実施形態による多項目逐次ソート処理をより詳細に説明する。図１５は、本発明の一実施形態による多項目逐次ソート処理の下位次元ソート処理における並列カウントアップ処理の説明図である。下位次元ソート処理は、下位次元の項目に関する項目値番号の昇順にレコード番号配列に格納されたレコード番号を並べ替える処理である。この処理は、多項目一括ソート処理における仮想項目値番号の昇順にレコード番号を並べ替える処理と類似している。図１５の例では、下位次元の項目の項目値に対応する項目値番号の出現回数を数え上げる。この数え上げ処理もまた、プロセッサが受け持ち範囲を分担する。本例では、レコード番号配列５０３は、４台のプロセッサのそれぞれの受け持ち範囲１５０１、１５０２、１５０３及び１５０４に分割される。【００８５】
レコード番号をｉ、レコード番号配列をＯｒｄＳｅｔ、項目値番号配列をＶＮｏ＿２、プロセッサ番号をｊ（ｊ＝０，１，２，３）としてプロセッサｊが数え上げた項目値番号の個数を格納するカウント配列をＣｏｕｎｔ［ｊ］とすると、本実施形態による数え上げ処理は、たとえば、Ｃ言語スタイルでは、
ｆｏｒ  （ｉ＝０；ｉ＜４；ｉ＋＋）  ｛
ｆｏｒ  （ｊ＝０；ｊ＜４；ｊ＋＋）  ｛
Ｃｏｕｎｔ［ｊ］［Ｖ＿ＶＮｏ［ＯｒｄＳｅｔ［ｊ＊４＋ｉ］］］＋＋；
｝
｝
と記述される。図１５の例では、初期化されたカウント配列１５１０、１５１１、１５１２及び１５１３は、項目値番号の数え上げ処理によって、カウント配列１５２０、１５２１、１５２２及び１５２３となる。尚、本例において、カウント配列Ｃｏｕｎｔのサイズは、対象としている項目の項目値番号配列をＶＬとし、プロセッサの台数をＮとすると、（ＶＬのサイズ）×Ｎに一致する。【００８６】
続いて、本発明の一実施形態では、コンピュータシステム１０は、項目値番号配列の各要素を累計数化して、項目値番号の出現回数の累積度数分布配列を生成する。図１６は、本発明の一実施形態による多項目逐次ソート処理の下位次元ソート処理における累積度数分布配列を生成する処理の説明図である。プロセッサｊの受け持ち範囲内のカウント配列をＣｏｕｎｔ［ｊ］、累積度数分布配列をＡｇｇｒ［ｊ］とすると、累積度数分布は、
Ａｇｇｒ［０］［０］＝０
Ａｇｇｒ［１］［０］＝Ａｇｇｒ［０］［０］＋Ｃｏｕｎｔ［０］［０］
Ａｇｇｒ［２］［０］＝Ａｇｇｒ［１］［０］＋Ｃｏｕｎｔ［１］［０］
Ａｇｇｒ［３］［０］＝Ａｇｇｒ［２］［０］＋Ｃｏｕｎｔ［２］［０］
Ａｇｇｒ［０］［１］＝Ａｇｇｒ［３］［０］＋Ｃｏｕｎｔ［３］［０］
Ａｇｇｒ［１］［１］＝Ａｇｇｒ［０］［１］＋Ｃｏｕｎｔ［０］［１］
Ａｇｇｒ［２］［１］＝Ａｇｇｒ［１］［１］＋Ｃｏｕｎｔ［１］［１］
Ａｇｇｒ［３］［１］＝Ａｇｇｒ［２］［１］＋Ｃｏｕｎｔ［２］［１］
Ａｇｇｒ［０］［２］＝Ａｇｇｒ［３］［１］＋Ｃｏｕｎｔ［３］［１］
Ａｇｇｒ［１］［２］＝Ａｇｇｒ［０］［２］＋Ｃｏｕｎｔ［０］［２］
Ａｇｇｒ［２］［２］＝Ａｇｇｒ［１］［２］＋Ｃｏｕｎｔ［１］［２］
Ａｇｇｒ［３］［２］＝Ａｇｇｒ［２］［２］＋Ｃｏｕｎｔ［２］［２］
Ａｇｇｒ［０］［３］＝Ａｇｇｒ［３］［２］＋Ｃｏｕｎｔ［３］［２］
Ａｇｇｒ［１］［３］＝Ａｇｇｒ［０］［３］＋Ｃｏｕｎｔ［０］［３］
Ａｇｇｒ［２］［３］＝Ａｇｇｒ［１］［３］＋Ｃｏｕｎｔ［１］［３］
Ａｇｇｒ［３］［３］＝Ａｇｇｒ［２］［３］＋Ｃｏｕｎｔ［２］［３］
として計算される。この計算は、４台のプロセッサのうちのいずれか１台のプロセッサが単独で行ってもよいが、４台のプロセッサに仮想項目値番号の範囲を割り当てて、４台のプロセッサによって並列に行ってもよい。【００８７】
４台のプロセッサによって並列的に累積度数分布を計算する場合には、最初に、各仮想項目値番号ｉの出現回数の合計値Ｓｕｍ［ｉ］を、たとえば、
ｆｏｒ（ｉ＝０；ｉ＜４；ｉ＋＋）  ｛
ｆｏｒ（ｊ＝０；ｊ＜４；ｊ＋＋）  ｛
Ｓｕｍ［ｉ］＝Ｃｏｕｎｔ［ｊ］［ｉ］；
｝
｝
によって、並列的に計算する。本実施形態では、たとえば、ＣＰＵ−０がｉ＝０のループを担当し、ＣＰＵ−１がｉ＝１のループを担当し、ＣＰＵ−２がｉ＝２のループを担当し、ＣＰＵ−３がｉ＝３のループを担当する。【００８８】
続いて、たとえば、４台のプロセッサが並列的に、
Ａｇｇｒ［０］［０］＝０
Ａｇｇｒ［１］［０］＝Ａｇｇｒ［０］［０］＋Ｃｏｕｎｔ［０］［０］
Ａｇｇｒ［２］［０］＝Ａｇｇｒ［１］［０］＋Ｃｏｕｎｔ［１］［０］
Ａｇｇｒ［３］［０］＝Ａｇｇｒ［２］［０］＋Ｃｏｕｎｔ［２］［０］
Ａｇｇｒ［０］［１］＝Ｓｕｍ［０］
Ａｇｇｒ［１］［１］＝Ａｇｇｒ［０］［１］＋Ｃｏｕｎｔ［０］［１］
Ａｇｇｒ［２］［１］＝Ａｇｇｒ［１］［１］＋Ｃｏｕｎｔ［１］［１］
Ａｇｇｒ［３］［１］＝Ａｇｇｒ［２］［１］＋Ｃｏｕｎｔ［２］［１］
Ａｇｇｒ［０］［２］＝Ｓｕｍ［１］
Ａｇｇｒ［１］［２］＝Ａｇｇｒ［０］［２］＋Ｃｏｕｎｔ［０］［２］
Ａｇｇｒ［２］［２］＝Ａｇｇｒ［１］［２］＋Ｃｏｕｎｔ［１］［２］
Ａｇｇｒ［３］［２］＝Ａｇｇｒ［２］［２］＋Ｃｏｕｎｔ［２］［２］
Ａｇｇｒ［０］［３］＝Ｓｕｍ［２］
Ａｇｇｒ［１］［３］＝Ａｇｇｒ［０］［３］＋Ｃｏｕｎｔ［０］［３］
Ａｇｇｒ［２］［３］＝Ａｇｇｒ［１］［３］＋Ｃｏｕｎｔ［１］［３］
Ａｇｇｒ［３］［３］＝Ａｇｇｒ［２］［３］＋Ｃｏｕｎｔ［２］［３］
を実行することによって、累積度数分布配列が得られる。【００８９】
図１６には、最終的な累積度数分布配列１６００、１６０１、１６０２及び１６０３が示されている。【００９０】
次に、本発明の一実施形態による多項目逐次ソート処理の下位次元ソートでは、元のレコード番号配列の要素をソート後のレコード番号配列に転送する。図１７は、本発明の一実施形態によるレコード番号配列の要素を並べ替える処理の説明図である。この処理では、レコード番号配列５０３は、図１５と同様に、４台のプロセッサの受け持ち範囲１５０１、１５０２、１５０３及び１５０４に分割され、４台のプロセッサが並列処理を実行する。元のレコード番号配列をＯｒｄＳｅｔ、ソート後のレコード番号配列をＯｒｄＳｅｔ’、項目値番号配列をＶＮｏ＿２、累積度数分布配列をＡｇｇｒ［ｊ］（ｊはプロセッサ番号）とすると、プロセッサ０番、すなわち、ＣＰＵ−０による並べ替え処理は、
ｆｏｒ  （ｉ＝０；ｉ＜４；ｉ＋＋）  ｛
ＯｒｄＳｅｔ’［Ａｇｇｒ［０］［ＶＮｏ＿２［ＯｒｄＳｅｔ［ｉ］］］］＝ＯｒｄＳｅｔ［ｉ］；
Ａｇｇｒ［０］［ＶＮｏ＿２［ＯｒｄＳｅｔ［ｉ］］］＋＋；
｝
と記述できる。ここで、Ａｇｇｒ［０］［ＶＮｏ＿２［ＯｒｄＳｅｔ［ｉ］］］＋＋から、累積度数分布配列の要素がインデックスポインタとして利用されていることがわかる。【００９１】
さらに、プロセッサ番号ｊをループ変数とすると、本実施形態によるレコード番号配列の要素を並べ替える処理は、
ｆｏｒ  （ｊ＝０；ｊ＜４；ｊ＋＋）  ｛
ｆｏｒ  （ｉ＝０；ｉ＜４；ｉ＋＋）  ｛
ＯｒｄＳｅｔ’［Ａｇｇｒ［ｊ］［ＶＮｏ＿２［ＯｒｄＳｅｔ［ｊ＊４＋ｉ］］］］＝ＯｒｄＳｅｔ［ｊ＊４＋ｉ］；
Ａｇｇｒ［ｊ］［ＶＮｏ＿２［ＯｒｄＳｅｔ［ｊ＊４＋ｉ］］］＋＋；
｝
｝
と記述できる。【００９２】
レコード番号配列の要素を並べ替える処理が完了すると、累積度数分布配列１７００、１７０１、１７０２及び１７０３は、ソート後の累積度数分布配列を表し、ソートバージョンのレコード番号配列１７１０はソート後のレコード番号配列を表している。このように、本発明の一実施形態によるレコード番号配列の要素を並べ替える処理により、元のレコード番号配列５０３の要素は、下位次元に関してソートされ、ソートバージョンのレコード番号配列１７１０に格納されている。表形式データ１４００は下位次元に関してソートされた表形式データを示している。【００９３】
さらに、ソート完了時の累積度数分布配列１７０３の値を用いることにより、グループ番号配列１７２０に示されるように、レコード番号をグループ分けすることができる。このグループ番号は、後で上位次元に関してレコード番号をソートするときに、レコード番号と共にソートされる。【００９４】
本発明の一実施形態による多次元逐次ソート処理では、下位次元に関するソートに続いて、上位次元に関するソートが行われる。上位次元に関するソートは下位次元に関するソートに類似しているので簡単に説明する。図１８は、本発明の一実施形態による多項目逐次ソート処理の上位次元ソート処理における並列カウントアップ処理の説明図である。ここでも、上位次元の項目値番号配列ＶＮｏ＿１中の要素の出現回数を４台のプロセッサで並列的にカウントアップする。カウントアップ結果がカウント配列１８２０、１８２１、１８２２、１８２３に示されている。【００９５】
図１９は、本発明の一実施形態による多項目逐次ソート処理の上位次元ソート処理における累積度数分布配列生成処理の説明図である。上位次元ソート処理の場合も、下位次元ソート処理と同様に、複数台のプロセッサを用いて並列的に累積度数分布配列１９００、１９０１、１９０２、１９０３が生成される。【００９６】
図２０は、本発明の一実施形態による多項目逐次ソート処理の上位次元ソート処理におけるレコード番号配列の要素を並べ替える処理の説明図である。上位次元ソート処理の場合も、下位次元ソート処理と同様に、複数台のプロセッサを用いて、レコード番号配列１７１０がレコード番号配列２０１０へ並列的に並べ替えられる。このとき、同時に、グループ番号配列１７２０もグループ番号配列２０２０へ並列的に並べ替えられる。表形式データ１４１０は下位次元に続いて上位次元に関してソートされた表形式データを示している。【００９７】
レコード番号配列２０１０は、図１０を参照して説明した多項目一括ソート処理によって得られたレコード番号配列１００５と同一であり、多項目一括ソート処理と多項目逐次ソート処理のどちらでも同じ結果が得られることが確かめられた。【００９８】
グループ番号配列２０２０は、最終的な累積度数分布配列２００３の要素によって示されているように、Ｇｒｏｕｐ２［０］からＧｒｏｕｐ２［４］の第１区間と、Ｇｒｏｕｐ２［５］からＧｒｏｕｐ２［１０］までの第２区間と、Ｇｒｏｕｐ２［１１］からＧｒｏｕｐ２［１５］までの第３区間の３区間にグループ化される。さらに、第１区間は、要素の値によって、０、２、３の３個に分割され、第２区間は０、１、２、３の４個に分割され、第３区間は１、２、３の３個に分割されている。よって、グループ番号配列２０２０を先頭から順次比較することにより、たとえば、ｆｏｒループを使ってカウントアップすることにより、完全なグループ番号配列２０３０を得ることが可能である。尚、このようなシーケンシャルなアクセスは、キャッシュのプリフェッチが有効であることに注意すべきである。【００９９】
以上の通り、多項目逐次ソート処理によって得られたレコード番号配列２０１０に上記のユニーク行抽出処理を適用することによって、一意の固有値の組、すなわち、集計の次元を作成することができる。【０１００】
［測度並列算出処理］
最後に、ユニーク行抽出処理によって得られた集計の次元に基づいて測度を算出することにより多次元集計処理が実現される。以下、この測度の算出について説明する。集計処理の結果は、グループ番号を行とし、次元及び測度を列とする集計結果テーブルによって表現される。ここでは、集計結果テーブルのサイズ、すなわち、行数と、キャッシュメモリのサイズの関係に応じて、２通りの測度算出方法が提案される。ユニーク行抽出処理によって得られた最終的なレコード番号配列とグループ番号配列について検討すると、グループ番号配列は要素が昇順に並んでいる。一方、レコード番号配列は要素がランダムに配置されている。そのため、測度の算出を実施する際に、集計結果テーブルの行数が小さい場合には、できるだけキャッシュヒット率を高めるために、レコード番号配列中の要素をシーケンシャルに並べ替える（レコード番号昇順タイプ）これによって、レコード番号配列へのアクセスがシーケンシャルアクセスになるため、キャッシュのプリフェッチ機構によりキャッシュヒット率が高くなる。一方、グループ番号配列は、配列中の要素の値の変動が比較的小さいのでキャッシュヒット率が高い。逆に、集計結果テーブルの行数が比較的大きい場合には、処理手順の簡略化と作業用メモリの使用量の削減化のため、レコード番号配列の並べ替えは行わない（グループ番号昇順タイプ）。【０１０１】
［レコード番号昇順タイプの測度並列算出処理］
以下、レコード番号昇順タイプの測度並列算出処理について説明する。この処理は、キャッシュヒット率が高くなるという利点がある。レコード番号配列の要素は、一意であるが、レコード番号昇順の形に変換することにより、シーケンシャルアクセスになるため、プリフェッチ機構によりキャッシュヒット率が高くなる。また、グループ番号配列は変動が小さいので、高いキャッシュヒット率が維持できる。この処理では、各プロセッサがグループ番号配列の全体にアクセスする可能性があるので、プロセッサ毎に集計作業領域を用意し、各プロセッサの集計結果をまとめて最終的な集計結果を作成する。尚、多数の測度が存在する場合には、測度１つ当たりのレコード番号配列の並べ替えのコストが低下すること、項目値番号配列から項目値配列へのアクセスはランダムアクセスであることに注意すべきである。【０１０２】
レコード番号昇順タイプの測度並列算出処理は、複数台のプロセッサを用いて、レコード番号配列の要素及びグループ番号配列の要素を、レコード番号配列の要素が昇順となるように並べ替えるステップと、複数台のプロセッサを用いて、測度を並列的に集計し、各プロセッサで算出された測度を合成するステップとを備える。【０１０３】
図２１は、本発明の一実施形態によるレコード番号昇順タイプの測度並列算出処理における並べ替え処理の説明図である。【０１０４】
並べ替え前のレコード番号配列をＯｒｄＳｅｔ’’、グループ番号配列をＧｒｏｕｐ３とし、並べ替え後のレコード番号配列をＯｒｄＳｅｔ’’、グループ番号配列をＧｒｏｕｐ４とし、ループ変数をｉとすると、この並べ替え処理は、
ｆｏｒ  （ｉ＝０；ｉ＜１６；ｉ＋＋）  ｛
ＯｒｄＳｅｔ’’’［ＯｒｄＳｅｔ’’［ｉ］］＝ＯｒｄＳｅｔ’’［ｉ］；
Ｇｒｏｕｐ４［ＯｒｄＳｅｔ’’［ｉ］］＝Ｇｒｏｕｐ４［ｉ］；
｝
と記述することができる。この処理は、レコード番号配列２０１０を図２１に示されるようにプロセッサ毎の受け持ち範囲２１００、２１０１、２１０２、２１０３のように分割することによって、複数台のプロセッサによって並列に実行される。【０１０５】
図２２は、本発明の一実施形態によるレコード番号昇順タイプの測度並列算出処理における集計処理の説明図である。レコード番号配列２１１０をプロセッサ毎の受け持ち範囲２２００、２２０１、２２０２、２２０３のように４分割することによって、測度並列算出処理は４台のプロセッサによって並列に実行される。図２２には、測度算出の対象となる項目「ポイント」の項目値番号配列ＶＮｏ＿３と項目値配列ＶＬ＿３がそれぞれ示されている。本例では、測度は「ポイント」の合計値である。よって、既に求められた集計の次元１１３０に関して、「ポイント」の合計値を算出する。【０１０６】
４台のプロセッサが用いられるので、共有メモリ上には４個の中間結果格納配列Ｓｕｍ＿０、Ｓｕｍ＿１、Ｓｕｍ＿２、Ｓｕｍ＿３と、最終的な結果格納配列Ｓｕｍが確保され、要素の値が０に初期化される。たとえば、ＣＰＵ−０の処理は、ｉをループ変数として、
ｆｏｒ  （ｉ＝０；ｉ＜４；ｉ＋＋）  ｛
Ｓｕｍ＿０［Ｇｒｏｕｐ４［ＯｒｄＳｅｔ’’’［ｉ］］＝＋ＶＬ＿３［ＶＮｏ＿３［ＯｒｄＳｅｔ’’’［ｉ］］］；
｝
として記述される。ＣＰＵ−１、ＣＰＵ−２、ＣＰＵ−３についても同様である。【０１０７】
次に、最終的な結果格納配列Ｓｕｍを４分割して、各プロセッサが受け持ち範囲について、
Ｓｕｍ［ｉ］＝Ｓｕｍ＿０［ｉ］＋Ｓｕｍ＿１［ｉ］＋Ｓｕｍ＿２［ｉ］＋Ｓｕｍ＿３［ｉ］
として記述される演算を実行することにより、同図に示されるような最終的な結果格納配列２２４０が得られる。この最終的な結果格納配列の要素が算出された測度であり、対応する次元が次元１１３０として図２２に示されている。【０１０８】
［グループ番号昇順タイプの測度並列算出処理］
次に、グループ番号昇順タイプの測度並列算出処理について説明する。この処理は、上記のＳｕｍ＿０、Ｓｕｍ＿１、Ｓｕｍ＿２、Ｓｕｍ＿３のような中間的な結果格納配列を確保しなくてもよいので、集計結果テーブルの行数が大きくても使用されるメモリ量が増加しないという利点がある。また、この処理は、レコード番号配列の並べ替えを必要としないので、処理時間が短縮されるという利点がある。一方、レコード番号配列の要素を添字として用いる項目値番号配列へのアクセスはランダムアクセスになることに注意する必要がある。また、項目値番号配列から項目値配列へのアクセスもランダムアクセスである。【０１０９】
図２３は、本発明の一実施形態によるグループ番号昇順タイプの測度並列算出処理における集計処理の説明図である。レコード番号配列２０１０を４台のプロセッサ毎の受け持ち範囲２３００、２３０１、２３０２、２３０３に分割する。ここで、注意すべきことは、同じグループに属するレコード番号が別々のプロセッサに割り当てられることがないように、かつ、各プロセッサの受け持ち範囲ができるだけ均等になるように受け持ち範囲２３００、２３０１、２３０２、２３０３を決定しなければならない。たとえば、受け持ち範囲は、たとえば、何れか１台のプロセッサが、１台当たりの受け持ち範囲の限界を設定し、グループ番号配列２０３０を先頭から順に走査し、同一のグループに属するレコード番号が同一のプロセッサに割り当てられるように、受け持ち範囲の限界内で境界を選択することによって決定される。各プロセッサの受け持ち範囲が決定されると、測度並列算出処理は４台のプロセッサによって並列に実行される。図２３には、測度算出の対象となる項目「ポイント」の項目値番号配列ＶＮｏ＿３と項目値配列ＶＬ＿３がそれぞれ示されている。本例では、測度は「ポイント」の合計値である。よって、既に求められた集計の次元１１３０に関して、「ポイント」の合計値を算出する。【０１１０】
レコード番号配列をＯｒｄＳｅｔ’’、グループ番号配列をＧｒｏｕｐ３、結果格納配列をＳｕｍ（初期値は０）とし、ループ変数をｉとすると、測度算出処理の全体は、
ｆｏｒ  （ｉ＝０；ｉ＜１６；ｉ＋＋）  ｛
Ｓｕｍ［Ｇｒｏｕｐ３［ＯｒｄＳｅｔ’’［ｉ］］］＝＋ＶＬ＿３［ＶＮｏ＿３［ＯｒｄＳｅｔ’’［ｉ］］］；
｝
として記述される。実際には、このループ中の命令は、各プロセッサの処理に展開されて並列に実行される。【０１１１】
本発明は、以上の実施の形態に限定されることなく、特許請求の範囲に記載された発明の範囲内で、種々の変更が可能であり、それらも本発明の範囲内に包含されるものであることは言うまでもない。
【実施例１】
【０１１２】
［多段階並列ソート］
ここでは、特許文献３に記載されているような、カウンティングソートに基づく並列ソートと基数ソートの考え方とを組み合わせることにより実現される多段階並列ソートの実施例を説明する。この多段階並列ソートは、上述の多項目一括ソート処理及び多項目逐次ソート処理の基礎となる記述である。【０１１３】
項目値配列ＶＬのサイズが大きいとき、すなわち、項目値番号の個数が多数であるときには、項目値番号を基数で表現し、桁ごとに並列ソートを実施することにより、効率的なソートを実現することが可能である。本例の多段階並列ソートは、最下位の桁から始めて順番に現在の桁に関するソート処理を行い、最後に最上位の桁に関するソート処理を行うことによって最終的なソートを完了する。【０１１４】
多段階並列ソート方法の一例では、図２４のデータ構造を利用する。本実施の形態では、ＣＰＵの台数は４台とし、すべてのＣＰＵが並列に動作する例を考える。システム内のＣＰＵの総数、及び、並列に動作するＣＰＵの台数はこの例に限定されないことに注意すべきである。また、以下では、説明の便宜上、年齢の項目に関して、年齢の昇順にソートする場合を考える。また、年齢の項目値配列の要素は年齢の昇順に並べられている。図４のデータ構造では、年齢に関する項目値番号ＶＮｏは０から４までの値を取り得るので、基数＝４として項目値番号を分解すると、項目値番号は下の桁と上の桁の２桁に分解される。具体的には、項目値番号のモジュロ（４）の値が下の桁の値であり、項目値番号を４で割った商が上の桁の値である。【０１１５】
図２５は、本実施例にかかる多段階並列ソート方法のフローチャートである。多段階並列ソート方法は、ステップ２５０１からステップ２５０５の５ステップにより構成される。【０１１６】
ステップ２５０１：項目値番号の範囲に応じて項目値番号の基数（本例では基数＝４）を選択し、初期のレコード番号配列ＯｒｄＳｅｔを現在のレコード番号配列に設定し、項目値番号の最下位の桁（本例では項目値番号のモジュロ（４）の値）を現在の桁に設定する。【０１１７】
ステップ２５０２：現在のレコード番号配列を分割して４台のプロセッサに割り当てる。【０１１８】
ステップ２５０３：４台のプロセッサのうちの各プロセッサにおいて、割り当てられたレコード番号配列の部分に含まれるレコードに対応した項目値番号の現在の桁の値の出現回数をカウントする。【０１１９】
ステップ２５０４：項目値番号の現在の桁の値の範囲を分割して４台のプロセッサに割り当てる。【０１２０】
ステップ２５０５：４台のプロセッサのうちの各プロセッサにおいて、項目値番号の現在の桁の値の順番に、項目値番号の現在の桁の値が一致する範囲内ではレコード番号配列の部分の順番に従って、割り当てられた項目値番号の現在の桁の値のそれぞれの出現回数を累計数に変換する。【０１２１】
ステップ２５０６：４台のプロセッサのうちの各プロセッサにおいて、割り当てられたレコード番号配列の部分に含まれるレコードに対応した項目値番号の現在の桁の値の出現回数の累計数をポインタとして利用して、割り当てられたレコード番号配列の部分に含まれるレコード番号をさらなるレコード番号配列に格納する。【０１２２】
ステップ２５０７：基数で表現された項目値番号の最上位桁までソート処理が行われたかどうかを判定し、最上位桁までソートされているならば、多段階並列ソート処理を終了する。【０１２３】
ステップ２５０８：未処理の桁が残っているならば、その桁を現在の桁に設定し、さらなるレコード番号配列を現在のレコード番号配列として、ステップ２５０２へ戻る。【０１２４】
上記の本実施例による多段階並列ソート方法において、ステップ２５０２からステップ２５０６までのソート処理は、上記の本発明の並列ソート方法と同様の処理であり、項目値番号の代わりに項目値番号の現在の桁の値が使用される点だけが異なっている。【０１２５】
次に、本実施例による多段階並列ソート方法を具体的に説明する。本例では、図２４に示されたデータを、４台のＣＰＵを使用し、年齢の昇順でソートする。初期化ステップ２５０１は、１段階目のソート処理として、年齢の項目値番号のモジュロー４（ＭＯＤ  ４）の値（下位の桁の値）に関するソート処理を設定し、２段階目のソート処理として、年齢の項目値番号の４で割った商（ＤＩＶ  ４）の値に関するソート処理を設定する。【０１２６】
初期化ステップ２５０１では、項目値番号の現在の桁の値の出現回数をカウントする配列が準備される。【０１２７】
図２６Ａ乃至２８Ｂは、多段階並列ソート方法の第１段階のカウントステップ２５０３の説明図である。図２６Ａのサブステップ１では、たとえば、ＣＰＵ−０は、ＯｒｄＳｅｔ［０］の値０を読み出し、読み出された値０を添字として、ＶＮｏ［０］の値１を読み出し、この値１のモジュロー４（ＭＯＤ４）の値１を添字として、Ｃｏｕｎｔ−０［１］の値０を１にインクリメントする。同様に、ＣＰＵ−１は、ＯｒｄＳｅｔ［５］の値５を読み出し、この値５を添字として、ＶＮｏ［５］の値２を読み出し、この値２のＭＯＤ４の値２を添字として、Ｃｏｕｎｔ−１［２］の値０を１にインクリメントする。以下、図２６Ｂのサブステップ２、図２７Ａのサブステップ３、図２７Ｂのサブステップ４及び図２８Ａのサブステップ５を実行することにより、図２８Ｂに示されるようなカウントアップ結果が得られる。図２８Ｂの配列Ｃｏｕｎｔ−０の要素Ｃｏｕｎｔ−０［ｉ］は、ＣＰＵ−０が担当した配列ＯｒｄＳｅｔのＯｒｄＳｅｔ［０］からＯｒｄＳｅｔ［４］の範囲内の各レコードに対応する年齢の項目値番号の下位の桁の値ｉの出現回数を表わしている。たとえば、Ｃｏｕｎｔ−０［０］は、ＣＰＵ−０の担当範囲内の項目値番号の下位の桁の値０の出現回数が２回であることを表し、Ｃｏｕｎｔ−３［１］はＣＰＵ−３の担当範囲内の項目値番号の下位の桁の値１の出現回数が２回であることを表す。【０１２８】
図２９Ａ、Ｂは多段階並列ソート方法の第１段階の累計数化ステップの説明図である。本例では、昇順ソートに対応して、項目値番号の下位の桁の値の昇順に累計数化を行う。ＣＰＵ−０は、配列Ｃｏｕｎｔの１行目（すなわち、項目値番号の下位の桁の値０）の累計数化を担当し、ＣＰＵ−１乃至ＣＰＵ−３は、それぞれ、配列Ｃｏｕｎｔの２乃至４行目（すなわち、項目値番号の下位の桁の値１乃至３）の累計数化を担当する。図２９Ａに示されるように、累計数化は配列Ｃｏｕｎｔの横方向（すなわち、添字が一致する行）を優先して行われ、次に、先行する行の累計数を後続する行の累計数に加算することにより、全体の累計数が決まる。尚、横方向の累計数化は、既に説明したように各ＣＰＵが並列に実行可能であるが、単一のＣＰＵが担当してもよい。【０１２９】
図３０Ａ乃至３２Ｂは多段階並列ソート方法の第１段階においてレコード番号をさらなるレコード番号配列に格納する転送ステップの説明図である。転送ステップでは、各ＣＰＵは、レコード番号配列ＯｒｄＳｅｔから自分が担当する範囲内のレコード番号を読み出し、次に、そのレコード番号を添字として、ポインタ配列ＶＮｏから項目値番号の下位の桁の値を読み出し、さらに、この項目値番号の下位の桁の値を添字として、自プロセッサに関連付けられた累計数化されたＣｏｕｎｔ配列から累計数値を読み出し、この読み出された累計数値をポイントしてさらなるレコード番号配列ＯｒｄＳｅｔ’にレコード番号を格納すると共に、Ｃｏｕｎｔ配列の累計数値を１ずつインクリメントする。図３２Ｂはこのような転送ステップの結果として第１段階で得られたレコード番号配列ＯｒｄＳｅｔ’を表す。【０１３０】
第２段階では、第１段階で得られたレコード番号配列ＯｒｄＳｅｔ’を初期条件として、年齢の項目値番号の上位の桁の値（ＤＩＶ  ４の値）に関する昇順ソートを実行する。【０１３１】
図３３は、本実施例による多段階並列ソート方法の第２段階のステップ２５０２において、現在のレコード番号配列ＯｒｄＳｅｔ’を４台のＣＰＵに割り当て、それぞれのＣｏｕｎｔ配列を準備した状態を示す図である。【０１３２】
図３４Ａ乃至３６Ｂは、多段階並列ソート方法の第２段階のカウントステップの説明図である。図３４Ａのサブステップ１では、たとえば、ＣＰＵ−０は、ＯｒｄＳｅｔ’［０］の値２を読み出し、読み出された値２を添字として、ＶＮｏ［２］の値４を読み出し、この値１の４で割った商（ＤＩＶ４）の値１を添字として、Ｃｏｕｎｔ−０［１］の値０を１にインクリメントする。同様に、ＣＰＵ−１は、ＯｒｄＳｅｔ’［５］の値１２を読み出し、この値１２を添字として、ＶＮｏ［１２］の値４を読み出し、この値４のＤＩＶ４の値１を添字として、Ｃｏｕｎｔ−１［１］の値０を１にインクリメントする。以下、図３４Ｂのサブステップ２、図３５Ａのサブステップ３、図３５Ｂのサブステップ４及び図３６Ａのサブステップ５を実行することにより、図３６Ｂに示されるような第２段階のカウントアップ結果が得られる。図３６Ｂの配列Ｃｏｕｎｔ−０の要素Ｃｏｕｎｔ−０［ｉ］は、ＣＰＵ−０が担当した配列ＯｒｄＳｅｔ’のＯｒｄＳｅｔ’［０］からＯｒｄＳｅｔ［４］の範囲内の各レコードに対応する年齢の項目値番号の上位の桁の値ｉの出現回数を表わしている。たとえば、Ｃｏｕｎｔ−０［０］は、ＣＰＵ−０の担当範囲内の項目値番号の上位の桁の値０の出現回数が４回であることを表し、Ｃｏｕｎｔ−３［１］はＣＰＵ−３の担当範囲内の項目値番号の上位の桁の値１の出現回数が０回であることを表す。【０１３３】
図３７は多段階並列ソート方法の第２段階の累計数化ステップの説明図である。本例では、昇順ソートに対応して、項目値番号の上位の桁の値の昇順に累計数化を行う。多段階化によって項目値番号の上位の桁の値の個数は２個に削減されているので、本例では、たとえば、ＣＰＵ−０がすべての値の累計数化を担当する。図３７に示されるように、ＣＰＵ−０は、Ｃｏｕｎｔ−０［０］、Ｃｏｕｎｔ−１［０］、Ｃｏｕｎｔ−２［０］、Ｃｏｕｎｔ−３［０］、Ｃｏｕｎｔ−０［１］、Ｃｏｕｎｔ−１［１］、Ｃｏｕｎｔ−２［１］、及び、Ｃｏｕｎｔ−３［１］の順に累計数化を行う。勿論、本例の場合に、ＣＰＵ−０とＣＰＵ−１の２台のＣＰＵに項目値番号の上位の桁の値０と１を割り当て、２台のＣＰＵが累計数化演算を行ってもよい。【０１３４】
図３８Ａ乃至４０Ｂは多段階並列ソート方法の第２段階においてレコード番号をさらなるレコード番号配列に格納する転送ステップの説明図である。転送ステップでは、各ＣＰＵは、レコード番号配列ＯｒｄＳｅｔから自分が担当する範囲内のレコード番号を読み出し、次に、そのレコード番号を添字として、ポインタ配列ＶＮｏから項目値番号の上位の桁の値を読み出し、さらに、この項目値番号の上位の桁の値を添字として、自プロセッサに関連付けられた累計数化されたＣｏｕｎｔ配列から累計数値を読み出し、この読み出された累計数値をポイントしてさらなるレコード番号配列ＯｒｄＳｅｔ”にレコード番号を格納すると共に、Ｃｏｕｎｔ配列の累計数値を１ずつインクリメントする。図４０Ｂはこのような転送ステップの結果として第２段階で得られたレコード番号配列ＯｒｄＳｅｔ”を表す。【０１３５】
本実施例の多段階並列ソート方法は項目値番号の下位の桁と上位の桁の２段階により構成されているので、これ以上のソート処理は行われない。したがって、第２段階で得られたレコード番号配列ＯｒｄＳｅｔ”が最初のレコード番号配列ＯｒｄＳｅｔを年齢に関して昇順にソートを行った結果である。【０１３６】
図４１Ａ及び４２Ｂは、図４に示されたデータ構造に対して本発明の実施の形態にかかる昇順の多段階並列ソート方法を適用した結果を示す図である。本例では、年齢に関する昇順ソートを行ったので、結果のレコード番号配列ＯｒｄＳｅｔ”には、年齢の項目値として１６歳、１８歳、２０歳、２１歳及び２３歳を有するレコードが年齢順に並んでいることがわかる。また、年齢が一致するレコードの順番は、元のレコード番号配列ＯｒｄＳｅｔ中の順番が保存されている。【０１３７】
また、上記の多段階並列ソート方法は昇順ソートであるが、本実施例による多段階並列ソートは降順ソートでも同様に動作する。さらに、多段階並列ソートの各段階における累計数化演算は、複数台のプロセッサで並列処理してもよく、或いは、少なくとも１台、好ましくは、１台のプロセッサが単独で処理してもよい。
【実施例２】
【０１３８】
［多段階ソート］
上記の多段階並列ソートは、最下位の桁から始めて順番に現在の桁に関するソート処理を行い、最後に最上位の桁に関するソート処理を行うことによって最終的なソートを完了している。これに対して、最上位の桁から始めて順番に現在の桁に関するソート処理を行い、最後に最下位の桁に関するソート処理を行うことによって最終的なソートを完了することも可能である。以下では、このような最上位から最下位の順にソート処理を多段化する方法を簡単に説明する。この多段化手法は、上述の多項目逐次ソート処理に同様に適用される。【０１３９】
本例では、図４３に示されるようなデータ構造を利用する。また、本例では、ＣＰＵの台数は１台とする。また、以下では、年齢の項目に関して、年齢の昇順にソートする場合を考える。レコードの総数はレコード番号０からレコード番号１９までの２０個であり、項目値番号は０から８までの９個である。すなわち、実際の年齢の値は、１５、１６、１８、１９、２０、２１、２３、２５及び２８の９通りである。図４３のデータ構造では、年齢に関する項目値番号ＶＮｏは０から８までの値を取り得るので、基数＝４として項目値番号を分解すると、項目値番号を４で割った商が上の桁の値であり、項目値番号のモジュロ（４）の値が下の桁の値である。項目値番号の上の桁は０、１及び２の３通りの値を取り、下の桁は０、１、２及び３の４通りの値を取り得る。【０１４０】
最初に、第１段階において、上の桁の値０、１及び２の出現回数をカウントするための配列Ｃｏｕｎｔ−１を準備し、要素を０で初期化する。たとえば、Ｃｏｕｎｔ−１［０］は、項目値番号の上位の桁の値が０であるレコードの個数をカウントするための領域である。【０１４１】
次に、レコード番号配列ＯｒｄＳｅｔの先頭の要素（すなわち、レコード）から順番に、その要素に対応する項目値番号を配列ＶＮｏから読み出し、その項目値番号を４で割った商の値をポインタとして用いて、配列Ｃｏｕｎｔ−１の要素の値をインクリメントする。図４４Ａ乃至Ｄは、ＯｒｄＳｅｔ［０］＝０、ＯｒｄＳｅｔ［７］＝７、及び、ＯｒｄＳｅｔ［１９］＝１９の３個のレコード番号について、項目値番号の上位の桁の値を算出し、該当するカウンタをカウントアップし、次に累計数化する例の説明図である。図４４Ｃからわかるように、この第１段階のカウントアップ処理により、項目値番号の上位の桁の値が０であるレコードの個数は１２個、上位の桁の値が１であるレコードの個数は７個、上位の桁の値が２であるレコードの個数は１個である。さらに、図４４Ｄに示されるように、このカウント値を累計数化する。【０１４２】
次に、項目値番号の上位の桁の値の出現回数が累計数化された配列Ａｇｇｒ−１を用いて、レコード番号配列ＯｒｄＳｅｔをさらなるレコード番号配列ＯｒｄＳｅｔ’に変換する。具体的には、ＯｒｄＳｅｔ［ｉ］＝ｊであるならば、ＶＮｏ［ｊ］を読み出し、このＶＮｏ［ｊ］を４で割った商（ＶＮｏ［ｊ］  ＤＩＶ  ４）をｋとすると、Ａｇｇｒ−１［ｋ］の値を読み出し、ＯｒｄＳｅｔ［Ａｇｇｒ−１［ｋ］］にレコード番号ｊを設定し、Ａｇｇｒ−１［ｋ］をインクリメントする。図４５Ａ、Ｂは、このような多段階ソートにおけるレコード番号転送処理の説明図であり、図４５ＡはＯｒｄＳｅｔ［０］の転送を、図４５ＢはＯｒｄＳｅｔ［１９］の転送を表している。図４６は、第１段階のレコード番号転送の結果のレコード番号配列ＯｒｄＳｅｔ’と、上位の桁の値が分布する範囲とを表している。たとえば、上位の桁の値が０であるレコードはレコード番号配列ＯｒｄＳｅｔ’のＯｒｄＳｅｔ’［０］からＯｒｄＳｅｔ’［１１］の範囲（区間０）に分布し、上位の桁の値が１であるレコードはレコード番号配列ＯｒｄＳｅｔ’のＯｒｄＳｅｔ’［１２］からＯｒｄＳｅｔ’［１８］の範囲（区間１）に分布し、上位の桁の値が２であるレコードはレコード番号配列ＯｒｄＳｅｔ’のＯｒｄＳｅｔ’［１９］（区間２）に存在する。【０１４３】
次に、多段階ソートの第２段階では、各区間内で、項目値番号の下位の桁の値によってレコード番号をソートする。たとえば、ＯｒｄＳｅｔ’の区間１は、ＯｒｄＳｅｔ”の対応した区間１へ転送される。第２段階のソートでは、既に上位の桁で区間が定められているので、レコード番号が区間外に転送されることはない。【０１４４】
図４７は、多段階ソートの第２段階の初期状態を表す図である。以下の説明では、ＯｒｄＳｅｔ’の区間１について説明する。たとえば、複数台のプロセッサが存在する場合には、区間ごとにプロセッサを割り当てることにより、以下の処理を並列化することも可能である。Ｃｏｕｎｔ−２は区間１内で項目値番号の下位の桁の値（０，１，２，３）の出現回数をカウントするための配列である。【０１４５】
図４８Ａ乃至Ｃは、多段階ソートの第２段階のカウントアップ及び累計数化の説明図である。図４８Ａから始めて順番にカウントアップすることにより、図４８Ｂに示されるようなカウントアップ配列が得られる。このカウントアップ配列は、図４８Ｃに示されるように累計数化される。【０１４６】
最後に、第２の累計数配列Ａｇｇｒ−２をポインタとして利用して、レコード番号配列ＯｒｄＳｅｔ’の区間１をレコード番号配列ＯｒｄＳｅｔ”の区間１へ転送することにより、多段階ソートが完了する。図４９Ａ、Ｂは、多段階ソートの第２段階のレコード番号転送の説明図である。具体的には、ＯｒｄＳｅｔ’［ｉ］＝ｊであるならば、ＶＮｏ［ｊ］を読み出し、このＶＮｏ［ｊ］を４で割った余り（ＶＮｏ［ｊ］  ＭＯＤ  ４）をｋとすると、Ａｇｇｒ−２［ｋ］の値を読み出し、ＯｒｄＳｅｔ”［Ａｇｇｒ−２［ｋ］］にレコード番号ｊを設定し、Ａｇｇｒ−２［ｋ］をインクリメントする。図４９ＡはＯｒｄＳｅｔ’［１４］の転送を、図４９ＢはＯｒｄＳｅｔ’［１８］の転送を表している。図４９ＢのＯｒｄＳｅｔ”の区間１は、区間１の最終的なソート結果を表している。【０１４７】
区間１と同様に、その他の区間０、区間２についても第２段階のカウントアップ、累計数化、及び、レコード番号転送を適用することにより、レコード番号配列ＯｒｄＳｅｔの全体がレコード番号配列ＯｒｄＳｅｔ”へ転送され、ソートが完了する。
【実施例３】
【０１４８】
実施例３では、１００万行（１Ｍ）、５００万行（５Ｍ）、１０００万行（１０Ｍ）、５０００万行（５０Ｍ）及び１億行（１００Ｍ）の３次元表形式テーブルをソートし、一意の項目値の組を抽出し、各項目値の組の出現回数をカウントする集計処理を以下の５通りの方式、すなわち、
（１）多段階並列ソート方式（旧方式）
（２）本発明による多項目逐次ソートとレコード番号昇順形式を組み合わせた方式（ＯｒｄＳｅｔ昇順方式）
（３）本発明による多項目一括ソートとレコード番号昇順形式を組み合わせた方式（ＯｒｄＳｅｔ昇順方式（３次元一括ソート））
（４）本発明による多項目逐次ソートとグループ番号昇順形式を組み合わせた方式（次元昇順方式）
（５）本発明による多項目一括ソートとグループ番号昇順形式を組み合わせた方式（次元昇順方式（３次元一括ソート））
を用いて実施した。そして、各方式の処理時間を計測し、本発明による方式が旧方式に対してどの程度高速化されたかを表す高速化倍率を算出した。本実施例の測定環境は次の通りである。
コンピュータ機種：Ｄｅｌｌ  ＰｏｗｅｒＥｄｇｅＴＭ  ６８００
ＣＰＵ：          Ｉｎｔｅｌ（登録商標）デュアルコアプロセッサ×２
クロック数：      ３．１６ＧＨｚ
メモリサイズ：    ３２ＧＢ
Ｌ２キャッシュ：  １ＭＢ×４
ＯＳ：            ＳｕＳＥ  ２．６．５−７−１９１−ｓｍｐ
図５０Ａ乃至Ｃは実施例３における集計処理の内容を説明する図である。図５０Ａは出力される集計結果テーブルを表し、図５０Bは１００万行からなる集計元テーブルを表し、図５０Ｃは６３２３３４個のレコードからなる集計結果テーブルを表している。【０１４９】
図５１Ａ乃至Ｃは実施例３の測定結果を示す図である。図５１Ａは、上記の５方式による処理の所要時間（ミリ秒）を表し、図５１Ｂは本発明による上記の（２）から（５）の方式が旧方式（１）に対して高速化された倍率を表し、図５１Ｃは図５１Ｂと同じ高速化倍率をグラフ化したものである。【０１５０】
（５）次元昇順方式（３次元一括ソート）、（３）ＯｒｄＳｅｔ昇順方式（３次元一括ソート）、（４）次元昇順方式、（２）ＯｒｄＳｅｔ昇順方式の順に高速化され、高速化倍率は、状況によっては、旧方式の１０倍に達している。
【実施例４】
【０１５１】
実施例４では、実施例３と同じ測定環境において、１００万行（１Ｍ）、５００万行（５Ｍ）、１０００万行（１０Ｍ）、５０００万行（５０Ｍ）及び１億行（１００Ｍ）の３次元表形式テーブルをソートし、一意の項目値の組を抽出し、測度の合計を算出する集計処理を実施例２と同様に上記の５通りの方式を用いて実施した。そして、各方式の処理時間を計測し、本発明による方式が旧方式に対してどの程度高速化されたかを表す高速化倍率を算出した。【０１５２】
図５２Ａ乃至Ｃは実施例４における集計処理の内容を説明する図である。図５２Ａは出力される集計結果テーブルを表し、図５２Bは１００万行からなる集計元テーブルを表し、図５２Ｃは６３２３３４個のレコードからなる集計結果テーブルを表している。【０１５３】
図５３Ａ乃至Ｃは実施例４の測定結果を示す図である。図５３Ａは、上記の５方式による処理の所要時間（ミリ秒）を表し、図５３Ｂは本発明による上記の（２）から（５）の方式が旧方式（１）に対して高速化された倍率を表し、図５３Ｃは図５３Ｂと同じ高速化倍率をグラフ化したものである。【０１５４】
集計結果テーブルのサイズにかかわらず、３次元一括ソート方式が逐次ソート方式より高速に集計処理を実現している。さらに、集計結果テーブルのサイズが比較的小さい場合（５００万行未満の場合）、次元昇順方式がＯｒｄＳｅｔ昇順方式より高速化されているが、集計結果テーブルのサイズが大きくなると、ＯｒｄＳｅｔ昇順方式が次元昇順方式より高速化されることがわかった。【０１５５】
実施例３及び実施例４から、本発明の方式は、（２）から（５）の何れの方式であっても、大規模な表形式データの多次元集計処理を従来技術より高速に実現することが実証された。
【図１】
2008155852.tif 000003
【図２】
2008155852.tif 000004
【図３】
2008155852.tif 000005
【図４】
2008155852.tif 000006
【図５】
2008155852.tif 000007
【図６】
2008155852.tif 000008
【図７】
2008155852.tif 000009
【図８】
2008155852.tif 000010
【図９】
2008155852.tif 000011
【図１０】
2008155852.tif 000012
【図１１】
2008155852.tif 000013
【図１２】
2008155852.tif 000014
【図１３】
2008155852.tif 000015
【図１４】
2008155852.tif 000016
【図１５】
2008155852.tif 000017
【図１６】
2008155852.tif 000018
【図１７】
2008155852.tif 000019
【図１８】
2008155852.tif 000020
【図１９】
2008155852.tif 000021
【図２０】
2008155852.tif 000022
【図２１】
2008155852.tif 000023
【図２２】
2008155852.tif 000024
【図２３】
2008155852.tif 000025
【図２４】
2008155852.tif 000026
【図２５】
2008155852.tif 000027
【図２６】
2008155852.tif 000028
【図２７】
2008155852.tif 000029
【図２８】
2008155852.tif 000030
【図２９】
2008155852.tif 000031
【図３０】
2008155852.tif 000032
【図３１】
2008155852.tif 000033
【図３２】
2008155852.tif 000034
【図３３】
2008155852.tif 000035
【図３４】
2008155852.tif 000036
【図３５】
2008155852.tif 000037
【図３６】
2008155852.tif 000038
【図３７】
2008155852.tif 000039
【図３８】
2008155852.tif 000040
【図３９】
2008155852.tif 000041
【図４０】
2008155852.tif 000042
【図４１】
2008155852.tif 000043
【図４２】
2008155852.tif 000044
【図４３】
2008155852.tif 000045
【図４４】
2008155852.tif 000046
【図４５】
2008155852.tif 000047
【図４６】
2008155852.tif 000048
【図４７】
2008155852.tif 000049
【図４８】
2008155852.tif 000050
【図４９】
2008155852.tif 000051
【図５０】
2008155852.tif 000052
【図５１】
2008155852.tif 000053
【図５２】
2008155852.tif 000054
【図５３】
2008155852.tif 000055
【手続補正書】
【提出日】平成20年6月17日(2008.6.17)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
多次元集計の対象となる表形式データのレコードのレコード番号が所定のレコード順に従って格納されたレコード番号配列、上記表形式データの上記レコードの所定の項目の項目値に対応する項目値番号がレコード番号に従って格納された項目値番号配列、及び、上記表形式データの項目値が当該項目値に対応する項目値番号の順序に従って格納された項目値配列を記憶する共有メモリと、
上記共有メモリにアクセス可能である複数台のプロセッサと、
を備えたメモリ共有型マルチプロセッサシステムにおいて、
多次元集計に用いられる次元の組を表す所定の項目の組に関する一意の項目値の組を抽出する方法であって、
上記レコード番号配列の各部分を受け持つ上記複数台のプロセッサを用いて、上記所定の項目の組に関する項目値の組に対応する項目値番号の組の出現回数を並列的に数え上げ、上記項目値番号の組より計算された値を添字として使って上記出現回数を累積度数分布配列に並列的に格納するステップと、
上記レコード番号配列の各部分を受け持つ上記複数台のプロセッサを用いて、上記レコード番号配列の要素の値を添字として使って上記項目値番号の組を並列的に読み出し、上記項目値番号の組より計算された値を添字として使って上記累積度数分布配列の要素を並列的に読み出し、上記累積度数分布配列の要素をインデックスポインタとして利用して上記レコード番号配列の要素の値を上記項目値の組に関してソートされたレコード番号配列に並列的に格納するステップと、
上記複数台のプロセッサのうちの少なくとも１台のプロセッサを用いて、上記インデックスポインタとして利用された上記累積度数分布配列の要素によって指定される上記レコード番号配列中のレコード番号のグループの境界に従って上記ソートされたレコード番号配列を上記一意の項目値の組を有するレコードのレコード番号のグループに区分するステップと、
上記複数台のプロセッサのうちの少なくとも１台のプロセッサを用いて、上記区分されたレコード番号の各グループから１個のレコード番号を抽出することにより、多次元集計に用いられる次元値の組に対応する上記一意の項目値の組を特定するステップと、
を備える方法。
【請求項２】
（削除）
【請求項３】
多次元集計の対象となる表形式データのレコードのレコード番号が所定のレコード順に従って格納されたレコード番号配列、上記表形式データの上記レコードの所定の項目の項目値に対応する項目値番号がレコード番号に従って格納された項目値番号配列、及び、上記表形式データの項目値が当該項目値に対応する項目値番号の順序に従って格納された項目値配列を記憶する共有メモリと、
上記共有メモリにアクセス可能である複数台のプロセッサと、
を備えたメモリ共有型マルチプロセッサシステムにおいて、
多次元集計に用いられる次元の組を表す所定の項目の組に関する一意の項目値の組を抽出する方法であって、
上記レコード番号配列の各部分を受け持つ上記複数台のプロセッサを用いて、多次元集計における上位次元の項目値番号が上位の桁となり下位次元の項目値番号が下位の桁となるように、上記項目値番号が取り得る値の範囲に応じて決められた基数を設定することにより、上記項目値番号の組を基数形式で表現された仮想項目値番号に変換するステップと、
上記レコード番号配列の各部分を受け持つ上記複数台のプロセッサを用いて、上記仮想項目値番号の出現回数を並列的に数え上げ、上記仮想項目値番号を添字として使って上記出現回数を累積度数分布配列に並列的に格納するステップと、
上記レコード番号配列の各部分を受け持つ上記複数台のプロセッサを用いて、上記レコード番号配列の要素の値を添字として使って上記仮想項目値番号を並列的に読み出し、上記仮想項目値番号を添字として使って上記累積度数分布配列の要素を並列的に読み出し、上記累積度数分布配列の要素をインデックスポインタとして利用して上記レコード番号配列の要素の値をソートされたレコード番号配列に並列的に格納するステップと、
上記複数台のプロセッサのうちの少なくとも１台のプロセッサを用いて、上記インデックスポインタとして利用された上記累積度数分布配列の要素によって指定される上記レコード番号配列中のレコード番号のグループの境界に従って上記ソートされたレコード番号配列を上記一意の項目値の組を有するレコードのレコード番号のグループに区分するステップと、
上記複数台のプロセッサのうちの少なくとも１台のプロセッサを用いて、上記区分されたレコード番号の各グループから１個のレコード番号を抽出することにより、多次元集計の次元値に対応する上記一意の項目値の組を特定するステップと、
を備える方法。
【請求項４】
多次元集計の対象となる表形式データのレコードのレコード番号が所定のレコード順に従って格納されたレコード番号配列、上記表形式データの上記レコードの所定の項目の項目値に対応する項目値番号がレコード番号に従って格納された項目値番号配列、及び、上記表形式データの項目値が当該項目値に対応する項目値番号の順序に従って格納された項目値配列を記憶する共有メモリと、
上記共有メモリにアクセス可能である複数台のプロセッサと、
を備えたメモリ共有型マルチプロセッサシステムにおいて、
多次元集計に用いられる次元の組を表す所定の項目の組に関する一意の項目値の組を抽出する方法であって、
上記表形式データの各部分を受け持つ上記複数台のプロセッサを用いて、多次元集計における下位次元の項目に関して上記表形式データをカウンティングソートし、下位次元に関するカウンティングソートによって生成されたソートバージョンのレコード番号配列を、下位次元に関するカウンティングソート中に生成された最終的な累積度数分布配列の各要素が指示するソートバージョンのレコード番号配列の要素を境界として用いてグループ分けし、下位次元に関してカウンティングソートされた表形式データに下位次元の項目値のグループ分けに対応したグループ番号配列を付与するステップと、
下位次元に関してカウンティングソートされた表形式データの各部分を受け持つ上記複数台のプロセッサを用いて、多次元集計における上位次元の項目に関して段階的に、下位次元に関してカウンティングソートされた表形式データ及びグループ番号配列をカウンティングソートし、上位次元に関するカウンティングソートによって生成されたソートバージョンのレコード番号配列を、上位次元に関するカウンティングソート中に生成された最終的な累積度数分布配列の各要素が指示するソートバージョンのレコード番号配列の要素を境界として用いてグループ分けし、上位次元に関してカウンティングソートされた表形式データに上位次元の項目値のグループ分けに対応したグループ番号配列を付与するステップと、
上記複数台のプロセッサのうちの少なくとも１台のプロセッサを用いて、上記上位次元に関するグループ番号配列を参照して、上記上位次元に関してカウンティングソートされた表形式データから各グループを代表する上記一意の項目値の組を特定するステップと、
を備える方法。
【請求項５】
上記複数台のプロセッサを用いて、上記レコード番号配列の要素及び上記レコード番号配列中の各レコードが属するグループを表すグループ番号の配列の要素を、上記レコード番号配列の要素が昇順となるように並べ替えるステップと、
上記複数台のプロセッサを用いて、上記所定の項目値の組毎に別の項目に関する項目値を並列的に集計するステップと、
をさらに備える、請求項１、３又は４のうち何れか１項に記載の方法。
【請求項６】
上記複数台のプロセッサのうちの少なくとも１台のプロセッサを用いて、同じグループに属するレコードが別々のプロセッサに割り当てられることがないように、各プロセッサのための上記レコード番号配列の受け持ち範囲を決定するステップと、
上記複数台のプロセッサを用いて、各プロセッサの受け持ち範囲内で上記所定の項目値の組毎に別の項目に関する項目値を並列的に集計するステップと、
をさらに備える、請求項１、３又は４のうち何れか１項に記載の方法。
【請求項７】
多次元集計の対象となる表形式データのレコードのレコード番号が所定のレコード順に従って格納されたレコード番号配列、上記表形式データの上記レコードの所定の項目の項目値に対応する項目値番号がレコード番号に従って格納された項目値番号配列、及び、上記表形式データの項目値が当該項目値に対応する項目値番号の順序に従って格納された項目値配列を記憶する共有メモリと、
上記共有メモリにアクセス可能である複数台のプロセッサと、
を備えたメモリ共有型マルチプロセッサシステムにおいて、
多次元集計に用いられる次元の組を表す所定の項目の組に関する一意の項目値の組を抽出する装置であって、
上記レコード番号配列の各部分を受け持つ上記複数台のプロセッサを用いて、上記所定の項目の組に関する項目値の組に対応する項目値番号の組の出現回数を並列的に数え上げ、上記項目値番号の組より計算された値を添字として使って上記出現回数を累積度数分布配列に並列的に格納する手段と、
上記レコード番号配列の各部分を受け持つ上記複数台のプロセッサを用いて、上記レコード番号配列の要素の値を添字として使って上記項目値番号の組を並列的に読み出し、上記項目値番号の組より計算された値を添字として使って上記累積度数分布配列の要素を並列的に読み出し、上記累積度数分布配列の要素をインデックスポインタとして利用して上記レコード番号配列の要素の値を上記項目値の組に関してソートされたレコード番号配列に並列的に格納する手段と、
上記複数台のプロセッサのうちの少なくとも１台のプロセッサを用いて、上記インデックスポインタとして利用された上記累積度数分布配列の要素によって指定される上記レコード番号中のレコード番号のグループの境界に従って上記ソートされたレコード番号配列を上記一意の項目値の組を有するレコードのレコード番号のグループに区分する手段と、
上記複数台のプロセッサのうちの少なくとも１台のプロセッサを用いて、上記区分されたレコード番号の各グループから１個のレコード番号を抽出することにより、多次元集計に用いられる次元値の組に対応する上記一意の項目値の組を特定する手段と、
を備える装置。
【請求項８】
（削除）
【請求項９】
多次元集計の対象となる表形式データのレコードのレコード番号が所定のレコード順に従って格納されたレコード番号配列、上記表形式データの上記レコードの所定の項目の項目値に対応する項目値番号がレコード番号に従って格納された項目値番号配列、及び、上記表形式データの項目値が当該項目値に対応する項目値番号の順序に従って格納された項目値配列を記憶する共有メモリと、
上記共有メモリにアクセス可能である複数台のプロセッサと、
を備えたメモリ共有型マルチプロセッサシステムにおいて、
多次元集計に用いられる次元の組を表す所定の項目の組に関する一意の項目値の組を抽出する装置であって、
上記レコード番号配列の各部分を受け持つ上記複数台のプロセッサを用いて、多次元集計における上位次元の項目値番号が上位の桁となり下位次元の項目値番号が下位の桁となるように、上記項目値番号が取り得る値の範囲に応じて決められた基数を設定することにより、上記項目値番号の組を基数形式で表現された仮想項目値番号に変換する手段と、
上記レコード番号配列の各部分を受け持つ上記複数台のプロセッサを用いて、上記仮想項目値番号の出現回数を並列的に数え上げ、上記仮想項目値番号を添字として使って上記出現回数を累積度数分布配列に並列的に格納する手段と、
上記レコード番号配列の各部分を受け持つ上記複数台のプロセッサを用いて、上記レコード番号配列の要素の値を添字として使って上記仮想項目値番号を並列的に読み出し、上記仮想項目値番号を添字として使って上記累積度数分布配列の要素を並列的に読み出し、上記累積度数分布配列の要素をインデックスポインタとして利用して上記レコード番号配列の要素の値をソートされたレコード番号配列に並列的に格納する手段と、
上記複数台のプロセッサのうちの少なくとも１台のプロセッサを用いて、上記インデックスポインタとして利用された上記累積度数分布配列の要素によって指定される上記レコード番号配列中のレコード番号のグループの境界に従って上記ソートされたレコード番号配列を上記一意の項目値の組を有するレコードのレコード番号のグループに区分する手段と、
上記複数台のプロセッサのうちの少なくとも１台のプロセッサを用いて、上記区分されたレコード番号の各グループから１個のレコード番号を抽出することにより、多次元集計の次元値に対応する上記一意の項目値の組を特定する手段と、
を備える装置。
【請求項１０】
多次元集計の対象となる表形式データのレコードのレコード番号が所定のレコード順に従って格納されたレコード番号配列、上記表形式データの上記レコードの所定の項目の項目値に対応する項目値番号がレコード番号に従って格納された項目値番号配列、及び、上記表形式データの項目値が当該項目値に対応する項目値番号の順序に従って格納された項目値配列を記憶する共有メモリと、
上記共有メモリにアクセス可能である複数台のプロセッサと、
を備えたメモリ共有型マルチプロセッサシステムにおいて、
多次元集計に用いられる次元の組を表す所定の項目の組に関する一意の項目値の組を抽出する装置であって、
上記表形式データの各部分を受け持つ上記複数台のプロセッサを用いて、多次元集計における下位次元の項目に関して上記表形式データをカウンティングソートし、下位次元に関するカウンティングソートによって生成されたソートバージョンのレコード番号配列を、下位次元に関するカウンティングソート中に生成された最終的な累積度数分布配列の各要素が指示するソートバージョンのレコード番号配列の要素を境界として用いてグループ分けし、下位次元に関してカウンティングソートされた表形式データに下位次元の項目値のグループ分けに対応したグループ番号配列を付与する手段と、
下位次元に関してカウンティングソートされた表形式データの各部分を受け持つ上記複数台のプロセッサを用いて、多次元集計における上位次元の項目に関して段階的に、下位次元に関してカウンティングソートされた表形式データ及びグループ番号配列をカウンティングソートし、上位次元に関するカウンティングソートによって生成されたソートバージョンのレコード番号配列を、上位次元に関するカウンティングソート中に生成された最終的な累積度数分布配列の各要素が指示するソートバージョンのレコード番号配列の要素を境界として用いてグループ分けし、上位次元に関してカウンティングソートされた表形式データに上位次元の項目値のグループ分けに対応したグループ番号配列を付与する手段と、
上記複数台のプロセッサのうちの少なくとも１台のプロセッサを用いて、上記上位次元に関するグループ番号配列を参照して、上記上位次元に関してカウンティングソートされた表形式データから各グループを代表する上記一意の項目値の組を特定する手段と、
を備える装置。
【請求項１１】
上記複数台のプロセッサを用いて、上記レコード番号配列の要素及び上記レコード番号配列中の各レコードが属するグループを表すグループ番号の配列の要素を、上記レコード番号配列の要素が昇順となるように並べ替える手段と、
上記複数台のプロセッサを用いて、上記所定の項目値の組毎に別の項目に関する項目値を並列的に集計する手段と、
をさらに備える、請求項７、９又は１０のうち何れか１項に記載の装置。
【請求項１２】
上記複数台のプロセッサのうちの少なくとも１台のプロセッサを用いて、同じグループに属するレコードが別々のプロセッサに割り当てられることがないように、各プロセッサのための上記レコード番号配列の受け持ち範囲を決定する手段と、
上記複数台のプロセッサを用いて、各プロセッサの受け持ち範囲内で上記所定の項目値の組毎に別の項目に関する項目値を並列的に集計する手段と、
をさらに備える、請求項７、９又は１０のうち何れか１項に記載の装置。
【請求項１３】
多次元集計の対象となる表形式データのレコードのレコード番号が所定のレコード順に従って格納されたレコード番号配列、上記表形式データの上記レコードの所定の項目の項目値に対応する項目値番号がレコード番号に従って格納された項目値番号配列、及び、上記表形式データの項目値が当該項目値に対応する項目値番号の順序に従って格納された項目値配列を記憶する共有メモリと、
上記共有メモリにアクセス可能である複数台のプロセッサと、
を備えたコンピュータにロードされ、多次元集計に用いられる次元の組を表す所定の項目の組に関する一意の項目値の組を抽出するコードを上記コンピュータに実行させるコンピュータ読み取り可能なプログラムであって、
上記レコード番号配列の各部分を受け持つ上記複数台のプロセッサを用いて、上記所定の項目の組に関する項目値の組に対応する項目値番号の組の出現回数を並列的に数え上げ、上記項目値番号の組より計算された値を添字として使って上記出現回数を累積度数分布配列に並列的に格納するコードと、
上記レコード番号配列の各部分を受け持つ上記複数台のプロセッサを用いて、上記レコード番号配列の要素の値を添字として使って上記項目値番号の組を並列的に読み出し、上記項目値番号の組より計算された値を添字として使って上記累積度数分布配列の要素を並列的に読み出し、上記累積度数分布配列の要素をインデックスポインタとして利用して上記レコード番号配列の要素の値を上記項目値の組に関してソートされたレコード番号配列に並列的に格納するコードと、
上記複数台のプロセッサのうちの少なくとも１台のプロセッサを用いて、上記インデックスポインタとして利用された上記累積度数分布配列の要素によって指定される上記レコード番号配列中のレコード番号のグループの境界に従って上記ソートされたレコード番号配列を上記一意の項目値の組を有するレコードのレコード番号のグループに区分するコードと、
上記複数台のプロセッサのうちの少なくとも１台のプロセッサを用いて、上記区分されたレコード番号の各グループから１個のレコード番号を抽出することにより、多次元集計に用いられる次元値の組に対応する上記一意の項目値の組を特定するコードと、
を含むプログラム。
【請求項１４】
（削除）
【請求項１５】
多次元集計の対象となる表形式データのレコードのレコード番号が所定のレコード順に従って格納されたレコード番号配列、上記表形式データの上記レコードの所定の項目の項目値に対応する項目値番号がレコード番号に従って格納された項目値番号配列、及び、上記表形式データの項目値が当該項目値に対応する項目値番号の順序に従って格納された項目値配列を記憶する共有メモリと、
上記共有メモリにアクセス可能である複数台のプロセッサと、
を備えたコンピュータにロードされ、多次元集計に用いられる次元の組を表す所定の項目の組に関する一意の項目値の組を抽出するコードを上記コンピュータに実行させるコンピュータ読み取り可能なプログラムであって、
上記レコード番号配列の各部分を受け持つ上記複数台のプロセッサを用いて、多次元集計における上位次元の項目値番号が上位の桁となり下位次元の項目値番号が下位の桁となるように、上記項目値番号が取り得る値の範囲に応じて決められた基数を設定することにより、上記項目値番号の組を基数形式で表現された仮想項目値番号に変換するコードと、
上記レコード番号配列の各部分を受け持つ上記複数台のプロセッサを用いて、上記仮想項目値番号の出現回数を並列的に数え上げ、上記仮想項目値番号を添字として使って上記出現回数を累積度数分布配列に並列的に格納するコードと、
上記レコード番号配列の各部分を受け持つ上記複数台のプロセッサを用いて、上記レコード番号配列の要素の値を添字として使って上記仮想項目値番号を並列的に読み出し、上記仮想項目値番号を添字として使って上記累積度数分布配列の要素を並列的に読み出し、上記累積度数分布配列の要素をインデックスポインタとして利用して上記レコード番号配列の要素の値をソートされたレコード番号配列に並列的に格納するコードと、
上記複数台のプロセッサのうちの少なくとも１台のプロセッサを用いて、上記インデックスポインタとして利用された上記累積度数分布配列の要素によって指定される上記レコード番号配列中のレコード番号のグループの境界に従って上記ソートされたレコード番号配列を上記一意の項目値の組を有するレコードのレコード番号のグループに区分するコードと、
上記複数台のプロセッサのうちの少なくとも１台のプロセッサを用いて、上記区分されたレコード番号の各グループから１個のレコード番号を抽出することにより、多次元集計の次元値に対応する上記一意の項目値の組を特定するコードと、
を含むプログラム。
【請求項１６】
多次元集計の対象となる表形式データのレコードのレコード番号が所定のレコード順に従って格納されたレコード番号配列、上記表形式データの上記レコードの所定の項目の項目値に対応する項目値番号がレコード番号に従って格納された項目値番号配列、及び、上記表形式データの項目値が当該項目値に対応する項目値番号の順序に従って格納された項目値配列を記憶する共有メモリと、
上記共有メモリにアクセス可能である複数台のプロセッサと、
を備えたコンピュータにロードされ、多次元集計に用いられる次元の組を表す所定の項目の組に関する一意の項目値の組を抽出するコードを上記コンピュータに実行させるコンピュータ読み取り可能なプログラムであって、
上記表形式データの各部分を受け持つ上記複数台のプロセッサを用いて、多次元集計における下位次元の項目に関して上記表形式データをカウンティングソートし、下位次元に関するカウンティングソートによって生成されたソートバージョンのレコード番号配列を、下位次元に関するカウンティングソート中に生成された最終的な累積度数分布配列の各要素が指示するソートバージョンのレコード番号配列の要素を境界として用いてグループ分けし、下位次元に関してカウンティングソートされた表形式データに下位次元の項目値のグループ分けに対応したグループ番号配列を付与するコードと、
下位次元に関してカウンティングソートされた表形式データの各部分を受け持つ上記複数台のプロセッサを用いて、多次元集計における上位次元の項目に関して段階的に、下位次元に関してカウンティングソートされた表形式データ及びグループ番号配列をカウンティングソートし、上位次元に関するカウンティングソートによって生成されたソートバージョンのレコード番号配列を、上位次元に関するカウンティングソート中に生成された最終的な累積度数分布配列の各要素が指示するソートバージョンのレコード番号配列の要素を境界として用いてグループ分けし、上位次元に関してカウンティングソートされた表形式データに上位次元の項目値のグループ分けに対応したグループ番号配列を付与するコードと、
上記複数台のプロセッサのうちの少なくとも１台のプロセッサを用いて、上記上位次元に関するグループ番号配列を参照して、上記上位次元に関してカウンティングソートされた表形式データから各グループを代表する上記一意の項目値の組を特定するコードと、
を含むプログラム。
【請求項１７】
上記複数台のプロセッサを用いて、上記レコード番号配列の要素及び上記レコード番号配列中の各レコードが属するグループを表すグループ番号の配列の要素を、上記レコード番号配列の要素が昇順となるように並べ替えるコードと、
上記複数台のプロセッサを用いて、上記所定の項目値の組毎に別の項目に関する項目値を並列的に集計するコードと、
をさらに含む、請求項１３、１５又は１６のうち何れか１項に記載のプログラム。
【請求項１８】
上記複数台のプロセッサのうちの少なくとも１台のプロセッサを用いて、同じグループに属するレコードが別々のプロセッサに割り当てられることがないように、各プロセッサのための上記レコード番号配列の受け持ち範囲を決定するステップと、
上記複数台のプロセッサを用いて、各プロセッサの受け持ち範囲内で上記所定の項目値の組毎に別の項目に関する項目値を並列的に集計するステップと、
をさらに含む、請求項１３、１５又は１６のうち何れか１項に記載のプログラム。
【請求項１９】
多次元集計の対象となる表形式データのレコードのレコード番号が所定のレコード順に従って格納されたレコード番号配列、上記表形式データの上記レコードの所定の項目の項目値に対応する項目値番号がレコード番号に従って格納された項目値番号配列、及び、上記表形式データの項目値が当該項目値に対応する項目値番号の順序に従って格納された項目値配列を記憶する共有メモリと、上記共有メモリにアクセス可能である複数台のプロセッサと、を備えたコンピュータにロードされ、多次元集計に用いられる次元の組を表す所定の項目の組に関する一意の項目値の組を抽出する請求項１記載の方法を上記コンピュータに実行させるためのコンピュータプログラムプロダクト。
【請求項２０】
多次元集計の対象となる表形式データのレコードのレコード番号が所定のレコード順に従って格納されたレコード番号配列、上記表形式データの上記レコードの所定の項目の項目値に対応する項目値番号がレコード番号に従って格納された項目値番号配列、及び、上記表形式データの項目値が当該項目値に対応する項目値番号の順序に従って格納された項目値配列を記憶する共有メモリと、上記共有メモリにアクセス可能である複数台のプロセッサと、を備えたコンピュータにロードされ、多次元集計に用いられる次元の組を表す所定の項目の組に関する一意の項目値の組を抽出する請求項１記載の方法を上記コンピュータに実行させるためのコンピュータプログラムが記録された記憶媒体。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００２０
【補正方法】変更
【補正の内容】
【００２０】
理は、たとえば、Ｃ言語スタイルでは、
ｆｏｒ    （ｉ＝０；ｉ＜４；ｉ＋＋）    ｛
ｆｏｒ    （ｊ＝０；ｊ＜４；ｊ＋＋）    ｛
Ｃｏｕｎｔ［ｊ］［Ｖ＿ＶＮｏ［ＯｒｄＳｅｔ［ｊ＊４＋ｉ］］］＋＋；
｝
｝
と記述される。図７の例では、初期化されたカウント配列７１０、７１１、７１２及び７１３は、仮想項目値番号の数え上げ処理によって、カウント配列７２０、７２１、７２２及び７２３となる。尚、本例において、第１の項目値配列をＶＬ＿１、第２の項目値配列をＶＬ＿２とすると、カウント配列Ｃｏｕｎｔのサイズは、（ＶＬ＿１のサイズ）×（ＶＬ＿２）のサイズに一致する。
［００５７］
この数え上げ処理の結果は、たとえば、ＣＰＵ−０の受け持ち範囲内では、仮想項目値番号＝０、２、５及び９がそれぞれ１個ずつ存在し、ＣＰＵ−１の受け持ち範囲内では、仮想項目値番号＝６、７、１０及び１１がそれぞれ１個ずつ存在し、ＣＰＵ−２の受け持ち範囲内では、仮想項目値番号０、３、４及び５がそれぞれ１個ずつ存在し、ＣＰＵ−３の受け持ち範囲内では、仮想項目値番号＝２、５、１０及び１１がそれぞれ１個ずつ存在することを表している。
［００５８］
続いて、本発明の一実施形態では、コンピュータシステム１０は、仮想項目値番号配列の各要素を累計数化して、仮想項目値番号の出現回数の累積度数分布配列を生成する。図８は、本発明の一実施形態による累積度数分布配列を生成する処理の説明図である。プロセッサｊの受け持ち範囲内のカウント配列をＣｏｕｎｔ［ｊ］、累積度数分布配列をＡｇｇｒ［ｊ］とすると、累積度数分布は、
Ａｇｇｒ［０］［０］＝０
Ａｇｇｒ［１］［０］＝Ａｇｇｒ［０］［０］＋Ｃｏｕｎｔ［０］［０］
Ａｇｇｒ［２］［０］＝Ａｇｇｒ［１］［０］＋Ｃｏｕｎｔ［１］［０］
Ａｇｇｒ［３］［０］＝Ａｇｇｒ［２］［０］＋Ｃｏｕｎｔ［２］［０］
Ａｇｇｒ［０］［１］＝Ａｇｇｒ［３］［０］＋Ｃｏｕｎｔ［３］［０］
Ａｇｇｒ［１］［１］＝Ａｇｇｒ［０］［１］＋Ｃｏｕｎｔ［０］［１］
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００３０
【補正方法】変更
【補正の内容】
【００３０】
び１５２３となる。尚、本例において、カウント配列Ｃｏｕｎｔのサイズは、対象としている項目の項目値番号配列をＶＬとし、プロセッサの台数をＮとすると、（ＶＬのサイズ）×Ｎに一致する。
［００８６］
続いて、本発明の一実施形態では、コンピュータシステム１０は、項目値番号配列の各要素を累計数化して、項目値番号の出現回数の累積度数分布配列を生成する。図１６は、本発明の一実施形態による多項目逐次ソート処理の下位次元ソート処理における累積度数分布配列を生成する処理の説明図である。プロセッサｊの受け持ち範囲内のカウント配列をＣｏｕｎｔ［ｊ］、累積度数分布配列をＡｇｇｒ［ｊ］とすると、累積度数分布は、
Ａｇｇｒ［０］［０］＝０
Ａｇｇｒ［１］［０］＝Ａｇｇｒ［０］［０］＋Ｃｏｕｎｔ［０］［０］
Ａｇｇｒ［２］［０］＝Ａｇｇｒ［１］［０］＋Ｃｏｕｎｔ［１］［０］
Ａｇｇｒ［３］［０］＝Ａｇｇｒ［２］［０］＋Ｃｏｕｎｔ［２］［０］
Ａｇｇｒ［０］［１］＝Ａｇｇｒ［３］［０］＋Ｃｏｕｎｔ［３］［０］
Ａｇｇｒ［１］［１］＝Ａｇｇｒ［０］［１］＋Ｃｏｕｎｔ［０］［１］
Ａｇｇｒ［２］［１］＝Ａｇｇｒ［１］［１］＋Ｃｏｕｎｔ［１］［１］
Ａｇｇｒ［３］［１］＝Ａｇｇｒ［２］［１］＋Ｃｏｕｎｔ［２］［１］
Ａｇｇｒ［０］［２］＝Ａｇｇｒ［３］［１］＋Ｃｏｕｎｔ［３］［１］
Ａｇｇｒ［１］［２］＝Ａｇｇｒ［０］［２］＋Ｃｏｕｎｔ［０］［２］
Ａｇｇｒ［２］［２］＝Ａｇｇｒ［１］［２］＋Ｃｏｕｎｔ［１］［２］
Ａｇｇｒ［３］［２］＝Ａｇｇｒ［２］［２］＋Ｃｏｕｎｔ［２］［２］
Ａｇｇｒ［０］［３］＝Ａｇｇｒ［３］［２］＋Ｃｏｕｎｔ［３］［２］
Ａｇｇｒ［１］［３］＝Ａｇｇｒ［０］［３］＋Ｃｏｕｎｔ［０］［３］
Ａｇｇｒ［２］［３］＝Ａｇｇｒ［１］［３］＋Ｃｏｕｎｔ［１］［３］
Ａｇｇｒ［３］［３］＝Ａｇｇｒ［２］［３］＋Ｃｏｕｎｔ［２］［３］
として計算される。この計算は、４台のプロセッサのうちのいずれか１台のプロセッサが単独で行ってもよいが、４台のプロセッサに項目値番号の範囲を割り当てて、４台のプロセッサによって並列に行ってもよい。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００３１
【補正方法】変更
【補正の内容】
【００３１】
［００８７］
４台のプロセッサによって並列的に累積度数分布を計算する場合には、最初に、各項目値番号ｉの出現回数の合計値Ｓｕｍ［ｉ］を、たとえば、
ｆｏｒ（ｉ＝０；ｉ＜４：ｉ＋＋）    ｛
ｆｏｒ（ｊ＝０；ｊ＜４；ｊ＋＋）    ｛
Ｓｕｍ［ｉ］＝Ｃｏｕｎｔ［ｊ］［ｉ］；
｝
｝
によって、並列的に計算する。本実施形態では、たとえば、ＣＰＵ−０がｉ＝０のループを担当し、ＣＰＵ−１がｉ＝１のループを担当し、ＣＰＵ−２がｉ＝２のループを担当し、ＣＰＵ−３がｉ＝３のループを担当する。
［００８８］
続いて、たとえば、４台のプロセッサが並列的に、
Ａｇｇｒ［０］［０］＝０
Ａｇｇｒ［１］［０］＝Ａｇｇｒ［０］［０］＋Ｃｏｕｎｔ［０］［０］
Ａｇｇｒ［２］［０］＝Ａｇｇｒ［１］［０］＋Ｃｏｕｎｔ［１］［０］
Ａｇｇｒ［３］［０］＝Ａｇｇｒ［２］［０］＋Ｃｏｕｎｔ［２］［０］
Ａｇｇｒ［０］［１］＝Ｓｕｍ［０］
Ａｇｇｒ［１］「１］＝Ａｇｇｒ［０］［１］＋Ｃｏｕｎｔ［０］［１］
Ａｇｇｒ［２］［１］＝Ａｇｇｒ［１］［１］＋Ｃｏｕｎｔ［１］［１］
Ａｇｇｒ［３］［１］＝Ａｇｇｒ［２］［１］＋Ｃｏｕｎｔ［２］［１］
Ａｇｇｒ［０］［２］＝Ｓｕｍ［１］
Ａｇｇｒ［１］［２］＝Ａｇｇｒ［０］［２］＋Ｃｏｕｎｔ［０］［２］
Ａｇｇｒ［２］［２］＝Ａｇｇｒ［１］［２］＋Ｃｏｕｎｔ［１］［２］
Ａｇｇｒ［３］［２］＝Ａｇｇｒ［２］［２］＋Ｃｏｕｎｔ［２］［２］
Ａｇｇｒ［０］［３］＝Ｓｕｍ［２］
Ａｇｇｒ［１］［３］＝Ａｇｇｒ［０］［３］＋Ｃｏｕｎｔ［０］［３］
Ａｇｇｒ［２］［３］＝Ａｇｇｒ［１］［３］＋Ｃｏｕｎｔ［１］［３］
Ａｇｇｒ［３］［３］＝Ａｇｇｒ［２］［３］＋Ｃｏｕｎｔ［２］［３］
を実行することによって、累積度数分布配列が得られる。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００３８
【補正方法】変更
【補正の内容】
【００３８】
ここでは、特許文献３に記載されているような、カウンティングソートに基づく並列ソートと基数ソートの考え方とを組み合わせることにより実現される多段階並列ソートの実施例を説明する。この多段階並列ソートは、上述の多項目一括ソート処理及び多項目逐次ソート処理の基礎となる技術である。
［０１１３］
項目値配列ＶＬのサイズが大きいとき、すなわち、項目値番号の個数が多数であるときには、項目値番号を基数で表現し、桁ごとに並列ソートを実施することにより、効率的なソートを実現することが可能である。本例の多段階並列ソートは、最下位の桁から始めて順番に現在の桁に関するソート処理を行い、最後に最上位の桁に関するソート処理を行うことによって最終的なソートを完了する。
［０１１４］
多段階並列ソート方法の一例では、図２４のデータ構造を利用する。本実施の形態では、ＣＰＵの台数は４台とし、すべてのＣＰＵが並列に動作する例を考える。システム内のＣＰＵの総数、及び、並列に動作するＣＰＵの台数はこの例に限定されないことに注意すべきである。また、以下では、説明の便宜上、年齢の項目に関して、年齢の昇順にソートする場合を考える。また、年齢の項目値配列の要素は年齢の昇順に並べられている。図４のデータ構造では、年齢に関する項目値番号ＶＮｏは０から４までの値を取り得るので、基数＝４として項目値番号を分解すると、項目値番号は下の桁と上の桁の２桁に分解される。具体的には、項目値番号のモジュロ（４）の値が下の桁の値であり、項目値番号を４で割った商が上の桁の値である。
［０１１５］
図２５は、本実施例にかかる多段階並列ソート方法のフローチャートである。多段階並列ソート方法は、ステップ２５０１からステップ２５０５の５ステップにより構成される。
［０１１６］
ステップ２５０１：項目値番号の範囲に応じて項目値番号の基数（本例では基数＝４）を選択し、初期のレコード番号配列ＯｒｄＳｅｔを現在のレコード番号配列に設定し、項目値番号の最下位の桁（本例では項目値番号のモジュロ（４）の値）を現在の桁に設定する。
［０１１７］
ステップ２５０２：現在のレコード番号配列を分割して４台のプロセッサに割り当てる。
［０１１８］
ステップ２５０３：４台のプロセッサのうちの各プロセッサにおいて、割り当てられたレコード番号配列の部分に含まれるレコードに対応した項目値番号の現在の桁の値の出現回数をカウントする。
【国際調査報告】
2008155852.tif 000056
2008155852.tif 000057
2008155852.tif 000058