(57)【特許請求の範囲】
【請求項１】
並列演算器を有するデータベース処理装置であって、
前記並列演算器のデータ処理単位に応じたフラグメント長を決定し、カラムストアデータベースにおいて、可変長データを含むタプルデータをフラグメントに格納するとともに、フラグメントヘッダとして前記フラグメントのメタデータを格納するデータ格納手段と、
前記カラムストアデータベースに格納されたデータの処理に際して、前記メタデータを参照して各スレッドに割り当てるフラグメントを決定し、決定内容に基づいて各スレッドにフラグメントを割り当てて並列演算を実行させる並列演算手段と、
を備え、
前記並列演算手段は、各スレッドにおいて、割り振られたフラグメントについて文字列を検索し、検索結果としてフラグメントのバイト位置をビット反転したものを記録する手段と、前記並列演算器のデータ処理単位に応じた数の前記検索結果を各スレッドに割り当てて、各スレッドにおいて、割り当てられた前記検索結果についてビット反転を検出し、検出結果フラグをタプルレベルの検索結果として記録する手段と、を備える
ことを特徴とするデータベース処理装置。
【請求項２】
並列演算器を有するデータベース処理装置におけるデータ処理方法であって、
前記並列演算器のデータ処理単位に応じたフラグメント長を決定し、カラムストアデータベースにおいて、可変長データを含むタプルデータをフラグメントに格納するとともに、フラグメントヘッダとして前記フラグメントのメタデータを格納するデータ格納ステップと、
前記カラムストアデータベースに格納されたデータの処理に際して、前記メタデータを参照して各スレッドに割り当てるフラグメントを決定し、決定内容に基づいて各スレッドにフラグメントを割り当てて並列演算を実行させる並列演算ステップと、
を備え、
前記並列演算ステップは、各スレッドにおいて、割り振られたフラグメントについて文字列を検索し、検索結果としてフラグメントのバイト位置をビット反転したものを記録するステップと、前記並列演算器のデータ処理単位に応じた数の前記検索結果を各スレッドに割り当てて、各スレッドにおいて、割り当てられた前記検索結果についてビット反転を検出し、検出結果フラグをタプルレベルの検索結果として記録するステップと、を備える
ことを特徴とするデータベース処理方法。
【請求項３】
並列演算器を有するコンピュータに、
前記並列演算器のデータ処理単位に応じたフラグメント長を決定し、カラムストアデータベースにおいて、可変長データを含むタプルデータをフラグメントに格納するとともに、フラグメントヘッダとして前記フラグメントのメタデータを格納するデータ格納ステップ、
前記カラムストアデータベースに格納されたデータの処理に際して、前記メタデータを参照して各スレッドに割り当てるフラグメントを決定し、決定内容に基づいて各スレッドにフラグメントを割り当てて並列演算を実行させる並列演算ステップ、
を実行させ、
前記並列演算ステップは、各スレッドにおいて、割り振られたフラグメントについて文字列を検索し、検索結果としてフラグメントのバイト位置をビット反転したものを記録するステップと、前記並列演算器のデータ処理単位に応じた数の前記検索結果を各スレッドに割り当てて、各スレッドにおいて、割り当てられた前記検索結果についてビット反転を検出し、検出結果フラグをタプルレベルの検索結果として記録するステップと、を備える
ことを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＧＰＧＰＵ（General Purpose computing on Graphics Processing Units）を用いるデータベース技術に関する。
【背景技術】
【０００２】
近年、ＧＰＵ（Graphics Processing Unit）等の並列演算器に汎用的な演算処理を行わせるＧＰＧＰＵ技術が注目されている。ＧＰＵは、ＣＰＵ（Central Processing
Unit）よりも演算器の並列度が高く、演算のスループットが高い。また、複数の演算器に対して命令供給を行うＳＩＭＤ演算器に似た構成を有する。ＧＰＧＰＵを用いて高い処理性能を発揮するには、命令分岐が少なくなるようにし、且つ、ある演算器のセットへのデータ供給に関して、データの供給量が一致することと供給するデータが連続性を持つ状態にすることが必要である。
【０００３】
カラムストアによるデータ構造はＧＰＧＰＵのような並列演算器による処理に適した構造と考えられる。固定長データのデータ処理は、カラムストアによってカラムごとに固定長の配列として表現されるため、これをＧＰＧＰＵでデータ処理に供すればよい。
【０００４】
例えば非特許文献１には、大規模な一つのテキストについて、その内容の全文検索をＧＰＧＰＵを援用して行う技術が開示されている。
【先行技術文献】
【特許文献】
【０００５】
【非特許文献１】東竜一、藤本典幸、萩原兼一、“ＧＰＵの汎用計算環境ＣＵＤＡによる主記憶上の大規模なテキストに対する高速な全文検索の検討”、情報処理学会研究報告、No.19,2008年,pp.139-144
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかし、可変長データを含むデータ群を効率的に格納するデータベースやそのようなデータベースを効率的に処理できるデータベース処理方法は未だ実現されていない。
【０００７】
本発明は、上記問題点に鑑みてなされたもので、並列演算器を用いて、可変長データについても効率的なデータベース処理を実現することができるデータベースシステム、データベース処理方法等を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明は、並列演算器を有するデータベース処理装置であって、前記並列演算器のデータ処理単位に応じたフラグメント長を決定し、カラムストアデータベースにおいて、可変長データを含むタプルデータをフラグメントに格納するとともに、フラグメントヘッダとして前記フラグメントのメタデータを格納するデータ格納手段と、前記カラムストアデータベースに格納されたデータの処理に際して、前記メタデータを参照して各スレッドに割り当てるフラグメントを決定し、決定内容に基づいて各スレッドにフラグメントを割り当てて並列演算を実行させる並列演算手段と、を備え、前記並列演算手段は、各スレッドにおいて、割り振られたフラグメントについて文字列を検索し、検索結果としてフラグメントのバイト位置をビット反転したものを記録する手段と、前記並列演算器のデータ処理単位に応じた数の前記検索結果を各スレッドに割り当てて、各スレッドにおいて、割り当てられた前記検索結果についてビット反転を検出し、検出結果フラグをタプルレベルの検索結果として記録する手段と、を備えることを特徴とするデータベース処理装置である。
【０００９】
本発明は、並列演算器を有するデータベース処理装置におけるデータ処理方法であって、前記並列演算器のデータ処理単位に応じたフラグメント長を決定し、カラムストアデータベースにおいて、可変長データを含むタプルデータをフラグメントに格納するとともに、フラグメントヘッダとして前記フラグメントのメタデータを格納するデータ格納ステップと、前記カラムストアデータベースに格納されたデータの処理に際して、前記メタデータを参照して各スレッドに割り当てるフラグメントを決定し、決定内容に基づいて各スレッドにフラグメントを割り当てて並列演算を実行させる並列演算ステップと、を備え、前記並列演算ステップは、各スレッドにおいて、割り振られたフラグメントについて文字列を検索し、検索結果としてフラグメントのバイト位置をビット反転したものを記録するステップと、前記並列演算器のデータ処理単位に応じた数の前記検索結果を各スレッドに割り当てて、各スレッドにおいて、割り当てられた前記検索結果についてビット反転を検出し、検出結果フラグをタプルレベルの検索結果として記録するステップと、を備えることを特徴とするデータベース処理方法である。
【００１０】
本発明は、並列演算器を有するコンピュータに、前記並列演算器のデータ処理単位に応じたフラグメント長を決定し、カラムストアデータベースにおいて、可変長データを含むタプルデータをフラグメントに格納するとともに、フラグメントヘッダとして前記フラグメントのメタデータを格納するデータ格納ステップ、前記カラムストアデータベースに格納されたデータの処理に際して、前記メタデータを参照して各スレッドに割り当てるフラグメントを決定し、決定内容に基づいて各スレッドにフラグメントを割り当てて並列演算を実行させる並列演算ステップ、を実行させ、前記並列演算ステップは、各スレッドにおいて、割り振られたフラグメントについて文字列を検索し、検索結果としてフラグメントのバイト位置をビット反転したものを記録するステップと、前記並列演算器のデータ処理単位に応じた数の前記検索結果を各スレッドに割り当てて、各スレッドにおいて、割り当てられた前記検索結果についてビット反転を検出し、検出結果フラグをタプルレベルの検索結果として記録するステップと、を備えることを特徴とするプログラムである。
【００１１】
本発明は、カラムストアデータベースのデータ構造であって、並列演算器のデータ処理単位に応じてコンピュータにより決定された固定長のフラグメント長を有し、前記コンピュータにより可変長データを含むタプルデータが格納されたフラグメントと、前記コンピュータにより、各前記フラグメントに対して付与された、前記フラグメントの順番を示した番号と、前記フラグメント最後部データ位置のタプル先頭位置からのオフセットと、を示すフラグメントヘッダと、を備えるデータベースのデータ構造である。
【発明の効果】
【００１２】
本発明によれば、並列演算器を用いて、可変長データについても効率的なデータベース処理を実現することができる。
【図面の簡単な説明】
【００１３】
【図１】図１は本発明の実施形態に係るデータベースシステムのシステム構成の概略図である。
【図２】図２はデータベースにおけるデータ構造の一例を示す図である。
【図３】図３はデータベースシステムの動作を説明するためのフローチャートである。
【図４】図４は記憶領域に記録された検索処理結果を例示する図である。
【図５】図５は所定記憶領域に記録された再処理結果を例示する図である。
【図６】図６は本データベースシステムの動作の概要を例示する図である。
【図７】図７は並列演算処理部が各スレッドに割り当てるフラグメントを決定する処理を説明するためのフローチャートである。
【図８】図８は可変長データ格納・処理部がデータベースにデータを格納する処理を説明するためのフローチャートである。
【発明を実施するための形態】
【００１４】
以下、本発明の実施形態について図面を参照して説明する。
【００１５】
図１は、本発明の実施形態に係るデータベースシステムのシステム構成の概略図である。図示されるように、本システムは、データベース１０とデータベース処理装置２０とを備え、これらはＬＡＮ（Local Area Network）等のネットワークにより接続されている。
【００１６】
データベース１０は、カラムストアデータベースである。データベース１０の管理単位は、タプル、カラム、テーブル、スキーマであり、それぞれ上位構造に対して複数を格納することができる。タプルは、データベース内部のある行のデータを含む。あるカラムストア内部には特定のカラムのデータがタプル単位で集められている。
【００１７】
データベース処理装置２０は、ホストコンピュータとコプロセッサ（並列演算器）等から構成される。データベース処理装置２０は、並列演算器環境検知部２１、可変長データ格納長決定部２２、可変長データ格納・処理部２３、並列演算処理部２４、データ処理結果・格納・再処理部２５、を備える。
【００１８】
並列演算器環境検知部２１は、本装置における並列演算器（ＧＰＵ）の処理能力に関する情報（データ処理単位等）を取得する。可変長データ格納長決定部２２は、並列演算器環境検知部２１が取得した情報に基づいて、データベース１０におけるデータ格納長（フラグメント長）を決定する。
【００１９】
可変長データ格納・処理部２３は、可変長データ格納長決定部２２により決定されたデータ格納長に基づいて、データをデータベース１０に格納する。カラム単位の、固定長データを含む可変長のタプルデータ（カラムタプル）は、固定長のフラグメントへ格納される。あるカラムのタプルデータは、必要に応じて複数のフラグメントからなるフラグメントセットへ格納される。
【００２０】
データベース１０のデータ構造の一例を図２に示す。図示されるように、データベース１０に格納されるデータは、フラグメントと、当該フラグメントに付されたフラグメントヘッダを備える。フラグメントは、１つのカラムタプルの部分データもしくは全体を格納する。フラグメントヘッダは、カラムタプルに関するメタデータを格納する。同じタプルに属するフラグメントは必ず連続的に格納される。フラグメントヘッダは、カラムタプルの部分データを格納したフラグメントの順番を示した番号(ct id)と、当該フラグメント最後部データ位置のタプル先頭位置からのオフセット(Length)を示す。
【００２１】
フラグメント長は、フラグメントセット内のカラムごとには固定長となりうるが、カラムごとにまたはフラグメントセット毎に、独立に設定することができる。可変長データ格納長決定部２２は、カラムもしくはフラグメントセット内に現れるデータ長を計測し、適当なアルゴリズムを用いて、並列演算器の処理能力に適合した、処理効率もしくは空間効率を向上できるフラグメント長を導くことができる。例えば、並列演算器のデータ処理単位に適したデータ長（４，８、１６、３２、６４バイト等）を設定してもよい。また、可変長データのデータ長の平均値等を設定してもよく、また、その平均値近傍の並列演算器のデータ処理単位に適したデータ長を設定してもよい。
【００２２】
並列演算処理部２４は、データベース１０に格納されたデータについて並列演算処理を行う。データ処理結果・格納・再処理部２５は、並列演算処理部２４による演算結果を処理する。
【００２３】
次に、本実施形態に係るデータベースシステムの動作について、データベース２１からある文字列を検索する場合を例に説明する。
【００２４】
検索の実行処理としては、１．フラグメントをまたがる処理が必要である場合と、２．フラグメントをまたがる処理が必要でない場合がある。
【００２５】
上記１．の場合は、検索対象の文字列（可変長バイト列）がフラグメントの処理格納単位バイト長よりも長く、かつ検索対象のタプルが複数のフラグメントから構成される場合を含む。この場合、各スレッドに対して担当フラグメントをオーバーラップさせ、多段処理する。Ｎ番目のスレッドは、Ｎ番目のフラグメントとＮ＋１番目のフラグメント、Ｎ＋１番目のスレッドは、Ｎ＋１番目のフラグメントとＮ＋２番目のフラグメントを担当する。一番最後になるスレッドはＥＮＤ番目のフラグメントのみ担当する。
【００２６】
上記２．の場合は、フラグメントへのデータ投入最短長管理単位（Byte）一発の検索と、すべてのフラグメントは１つのみでそれぞれのタプルを構成できている場合の検索と、を含む。これらは上記１．の特殊例として処理することができ、処理段が複数化しないので高速処理が可能となる。よって、以降、上記１．の場合を中心に図３を参照して説明する。
【００２７】
まず、並列演算処理部２４は、検索処理の結果セットの格納領域を確保する（ステップＳ１）。検索の結果は、複数のヒット結果などに対応するため、フラグメント内部のバイトごとにビットで与えられる。具体的には、検索対象バイト列の最初のバイトにあたるビット位置を反転するものとする。
【００２８】
並列演算処理部２４は、並列演算器で実行される各スレッドに割り当てるフラグメントを、フラグメントに付与されたメタデータを参照して決定する（ステップＳ２）。このとき、１つのスレッドに処理させるフラグメント数はフラグメント長によって変化させる。例えばバイトのビット長である８とフラグメントのバイト長の最小公倍数を設定することで結果セットを空隙なく、かつ全てのスレッドに同じ長さのデータを与えることができる。例えば、フラグメント長が４バイトのフラグメントについては２フラグメントをスレッドに与えてもよい。フラグメント長が８バイトのフラグメントについては１フラグメントをスレッドに与えてもよい。フラグメント長が１６バイトのフラグメントについては１フラグメントをスレッドに与えてもよい。また、並列演算器のデータ処理単位に基づいて、各スレッドに割り当てるフラグメントを決定してもよい。演算器が３２ビットの場合には、各スレッドに与えるデータ長を３２ビットの倍数となるようにしてもよい。
【００２９】
ステップＳ２の決定内容に基づいて並列演算処理が実行される（ステップＳ３）。具体的には、各スレッドにより以下の処理が実行される。スレッドは、検索対象となる可変長バイト列が与えられると、検索対象バイト列の長さを算出する。また、当該スレッドの担当すべきフラグメントセットの位置が与えられる。スレッドは、指定されたフラグメントを順次読み込み、検索対象バイト列が、読み込んだフラグメントセットに現れているかを判別する検索処理を行う。
【００３０】
なお、検索処理を行う条件として、現在までに与えられた逐次フラグメント内部に格納されているデータの合計長を算出し、所定の条件[（検索対象バイト列長−１）＋逐次フラグメントデータ長以上]を満たす場合に、検索処理を実行してもよい。すなわち、検索処理を行う条件として、現在処理を実行しているフラグメント内部の、未処理であるデータ長が、検索対象バイト列よりも長い場合には検索処理を実行してもよい。条件を満たさない場合は、次のフラグメントを続けて読み込み、データ合計長を算出して上記条件を満たすか判定してもよい。
【００３１】
検索処理では、検索対象バイト列の先頭のオフセットがそのスレッドの担当する先頭フラグメントの内部にあり、かつ検索対象バイト列のマッチ領域に１つのタプルＩＤのみ検出された場合、検索対象バイト列を検出したとしてその開始位置のビットを反転し、検索処理結果とする。この検索処理結果はスレッド単位でバイトアライメントされた領域に記録される。所定記憶領域に記録される検索処理結果の例を図４に示す。
【００３２】
次に、データ処理結果・格納・再処理部２５は、上記検索処理結果の再計算処理を行うため、再計算処理の結果セットの格納領域を確保する（ステップＳ４）。再計算の結果は、タプルに対して１ビットの容量確保で済む。すなわち、タプル数＊ビット数＋アライメントの数となる。
【００３３】
データ処理結果・格納・再処理部２５は、各スレッドに割り当てるフラグメントを決定する（ステップＳ５）。このとき、１つのスレッドに割り当てるタプル数を、バイトのビット長である８倍数に設定することでタプルレベルの結果セットを空隙なく、かつ全てのスレッドに同じ長さを与えることができる。また、並列演算器のデータ処理単位に基づいて割り当てるフラグメントを決定してもよい。演算器のデータ処理単位が３２ビットの場合には、各スレッドに与えるデータ長を３２ビットの倍数となるようにしてもよい。
【００３４】
ステップＳ５の決定内容に基づいて並列演算処理が実行される（ステップＳ６）。具体的には、各スレッドにより以下の処理が実行される。スレッドは、担当するタプルＩＤと、検索処理の結果セットの読み取り担当位置、フラグメントセットの担当位置を通知される。
【００３５】
各スレッドは、自分が担当するタプルＩＤについて次の処理を行う。通知された位置からフラグメントを読み込み、そのタプルＩＤを算出する。自分が担当するタプルＩＤか判断し、担当するタプルＩＤの場合は、対応する検索結果を読み込み、フラグが上がっている場合には、そのタプルに検索対象バイト列が存在するとして、タプルレベルのフラグを上げる。この処理結果はスレッド単位でバイトアライメントされた領域に記録される。所定記憶領域に記録された再処理結果の例を図５に示す。これにより、各タプルに検索対象バイト列が存在するか否かが示される。
【００３６】
なお、上述した本データベースシステムの動作の概要を図６に例示する。図６の例では、データベースにおいて、"HELLO!"、"parallel"、"GPU"、"GPGPU"等のタプルデータが各フラグメントに格納されている。並列演算処理部２４は、バイト列"GPU"を検索する処理について、検索処理の結果を格納する領域を確保し、並列演算器で実行される各スレッドに割り当てるフラグメントを、メタデータや並列演算器のデータ処理単位に基づいて決定する。この決定内容に基づいて各スレッドにフラグメントが割り当てられる。各スレッドは、割り当てられたフラグメントについて、バイト列”GPU”を検索する演算処理を行い、処理結果を記録する。図６では、演算結果の記録領域において、”GPU”が検出されたバイト列に対応する領域の先頭位置のビットが反転されている。次に、データ処理結果・格納部２５は、演算結果を再計算した処理結果を格納する領域を確保し、各スレッドに割り当てるタプルを決定する。このとき、各スレッドに割り当てるタプルの数は８の倍数に設定する。各スレッドは、割り当てられたタプルに対応する演算結果を読み込み、読み込んだ演算結果にフラグが立っている場合、そのタプルの処理結果としてフラグを立てる。図６では、フラグが立っている演算結果である"100"と"00100"、の処理結果として、フラグ"1"がそれぞれ立てられている。
【００３７】
次に、並列演算処理部２４が各スレッドに割り当てるフラグメントを決定する処理（上記ステップＳ２）の詳細を、図７を参照して説明する。並列演算処理部２４は、割り当て対象のフラグメントを処理対象データから特定し、そのフラグメント長を取得する（ステップＳ１１）。並列演算処理部２４は、割り当て対象のフラグメントのフラグメント長が、８の倍数である所定数（８とフラグメントの最小公倍数等）であるかを判定する（ステップＳ１２）。フラグメント長が所定数でなければ（ステップＳ１２：ＮＯ）、並列演算処理部２４は、処理対象データにおける他のフラグメントを割り当て対象のフラグメントに追加し、再度、割り当て対象フラグメントのフラグメント長を算出して（ステップＳ１３）、ステップＳ１２に戻る。フラグメント長が所定数である場合（ステップＳ１２:ＹＥＳ）、並列演算処理部２４は、割り当て対象のフラグメントをスレッドの一つに割り当てる（ステップＳ１４）。並列演算処理部２４は、処理対象データにおける全てのフラグメントについて割り当てが完了したかを判定し（ステップＳ１５）、完了した場合には（ステップＳ１５：ＹＥＳ）、処理を終了する。割り当てが完了していない場合には（ステップＳ１５：ＮＯ）、ステップＳ１１に戻り、残りのフラグメントについての処理を続行する。なお、本処理は一例であり、他の割り当て処理を用いてもよい。
【００３８】
次に、可変長データ格納・処理部２３がデータベース１０にデータを格納する処理について図８を参照して説明する。可変長データ格納・処理部２３は、格納対象のデータを読み込む（ステップＳ２１）。読み込まれるデータは、カラム単位の固定長データを含む可変長のタプルデータである。可変長データ格納・処理部２３は、読み込んだタプルデータをデータベース１０におけるフラグメントに格納する（ステップＳ２２）。フラグメントは固定長であり、その長さは可変長データ格納長決定部２２により、本システムで用いる並列演算器のデータ処理単位等に基づいて決定されている。可変長データ格納・処理部２３は、フラグメントに格納したタプルデータに対応するメタデータを、データベース１０におけるフラグメントヘッダに格納する（ステップＳ２３）。メタデータは、タプルデータを識別するＩＤと、当該フラグメント最後部のタプル先頭位置からのオフセットを含む。可変長データ格納・処理部２３は、格納対象の全データについてデータベース１０への格納が完了したかを判定し（ステップＳ２４）、完了した場合には（ステップＳ２４：ＹＥＳ）、処理を終了する。格納が完了していない場合には（ステップＳ２４：ＮＯ）ステップＳ２１に戻り、残りのデータについての処理を続行する。なお、本処理は一例であり、他の格納処理を用いてもよい。また、フラグメントのフラグメント長は、一般的な並列演算器のデータ処理単位に基づく、予め設定された値（例えば、４バイトや８バイトや１６バイト等）を用いるようにしてもよい。
【００３９】
以上説明したように本実施形態によれば、可変長データのＧＰＵ上での効率的な処理を行えるようにするため、空間効率と処理効率のバランスをとることで効率的な処理を実現する。
【００４０】
上述した本発明の実施形態に係る並列演算器環境検知部２１、可変長データ格納長決定部２２、可変長データ格納・処理部２３、並列演算処理部２４、データ処理結果・格納・再処理部２５は、データベース処理装置２０のＣＰＵやコプロセッサが記憶部に格納された動作プログラム等を読み出して実行することにより実現されてもよく、また、ハードウェアで構成されてもよい。上述した実施の形態の一部の機能のみをコンピュータプログラムにより実現することもできる。
【００４１】
以上、好ましい実施の形態をあげて本発明を説明したが、本発明は必ずしも上記実施の形態に限定されるものではなく、その技術的思想の範囲内において様々に変形し実施することが出来る。本出願は、２０１１年３月２４日に出願された日本出願特願２０１１−０６５１７１号を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【符号の説明】
【００４２】
１０    データベース
２０    データベース処理装置
２１    並列演算器環境検知部
２２    可変長データ格納長決定部
２３    可変長データ格納・処理部
２４    並列演算処理部
２５    データ処理結果・格納・再処理部
【図１】
0005382383.tif 000002
【図２】
0005382383.tif 000003
【図３】
0005382383.tif 000004
【図４】
0005382383.tif 000005
【図５】
0005382383.tif 000006
【図６】
0005382383.tif 000007
【図７】
0005382383.tif 000008
【図８】
0005382383.tif 000009