(57)【特許請求の範囲】
【請求項１】
カラム単位でタプルデータが格納されるストレージと、前記ストレージについて、有効データ範囲を示す第１の情報とすでに有効でないデータの識別情報からなる第２の情報が格納される管理構造部と、を備えるカラムストアデータベースと、
前記カラムストアデータベースに対してデータを追加する処理を行う場合、前記ストレージの末尾に前記データを追記して前記管理構造部の前記第１の情報を更新し、前記カラムストアデータベースに対してデータを削除する処理を行う場合、前記管理構造部の前記第２の情報に削除対象データの識別情報を追記するデータベース処理手段と、
を備えることを特徴とするデータベース処理装置。
【請求項２】
前記データベース処理手段は、前記カラムストアデータベースを更新しているときの前記カラムストアデータベースに対する排他制御範囲を前記管理構造部に格納された情報に基づいて定める
ことを特徴とする請求項１に記載のデータベース処理装置。
【請求項３】
要求された演算処理を並列演算器を用いて実行するか否かを判定し、並列演算器を用いて実行すると判定した場合、前記要求された演算処理を前記並列演算器に実行させる実行演算器判定部をさらに備える
ことを特徴とする請求項１又は請求項２に記載のデータベース処理装置。
【請求項４】
前記データベース処理手段は、前記カラムストアデータベースに対してデータを検索する処理を行う場合、前記管理構造部の前記第１の情報に基づいて検索範囲を決定し、前記第２の情報に基づいて検索から除外するデータを特定して検索を行う
ことを特徴とする請求項１から請求項３のいずれかに記載のデータベース処理装置。
【請求項５】
前記データベース処理手段は、前記カラムストアデータベースに対してデータを更新する処理を行う場合、更新対象データを検索し、検索した更新対象データについて前記削除処理を行い、更新用に作成したデータについて前記追加処理を行う
ことを特徴とする請求項１から請求項４のいずれかに記載のデータベース処理装置。
【請求項６】
前記管理構造部は、前記第２の情報に追記される情報の有効範囲を示す第３の情報がさらに格納され、
前記データベース処理手段は、前記カラムストアデータベースに対してデータを削除する処理を行う場合、前記管理構造部の前記第２の情報に削除対象データの識別情報を追記し、当該追記された情報が有効範囲に含まれるよう前記第３の情報を更新する
ことを特徴とする請求項１から請求項３のいずれかに記載のデータベース処理装置。
【請求項７】
前記データベース処理手段は、前記カラムストアデータベースに対してデータを検索する処理を行う場合、前記管理構造部の前記第１の情報に基づいて検索範囲を決定し、前記第２の情報と前記第３の情報に基づいて検索から除外するデータを特定して検索を行う
ことを特徴とする請求項６に記載のデータベース処理装置。
【請求項８】
前記データベース処理手段は、前記カラムストアデータベースに対してデータを更新する処理を行う場合、更新対象データを検索し、検索した更新対象データについて前記削除処理を行い、更新用に作成したデータについて前記追加処理を行う
ことを特徴とする請求項７に記載のデータベース処理装置。
【請求項９】
カラム単位でタプルデータが格納されるストレージと、前記ストレージについて、有効データ範囲を示す第１の情報とすでに有効でないデータの識別情報からなる第２の情報が格納される管理構造部と、を備えるカラムストアデータベースに対して、データを追加する処理を行う場合、前記ストレージの末尾に前記データを追記して前記管理構造部の前記第１の情報を更新し、
前記カラムストアデータベースに対して、データを削除する処理を行う場合、前記管理構造部の前記第２の情報に削除対象データの識別情報を追記する
ことを特徴とするデータベース処理方法。
【請求項１０】
前記管理構造部は、前記第２の情報に追記される情報の有効範囲を示す第３の情報がさらに格納され、
前記カラムストアデータベースに対してデータを削除する処理を行う場合、前記管理構造部の前記第２の情報に削除対象データの識別情報を追記し、当該追記された情報が有効範囲に含まれるよう前記第３の情報を更新する
ことを特徴とする請求項９に記載のデータベース処理方法。
【請求項１１】
コンピュータに、
カラム単位でタプルデータが格納されるストレージと、前記ストレージについて、有効データ範囲を示す第１の情報とすでに有効でないデータの識別情報からなる第２の情報が格納される管理構造部と、を備えるカラムストアデータベースに対して、データを追加する処理を行う場合、前記ストレージの末尾に前記データを追記して前記管理構造部の前記第１の情報を更新する処理、
前記カラムストアデータベースに対して、データを削除する処理を行う場合、前記管理構造部の前記第２の情報に削除対象データの識別情報を追記する削除処理、
を実行させることを特徴とするプログラム。
【請求項１２】
前記管理構造部は、前記第２の情報に追記される情報の有効範囲を示す第３の情報がさらに格納され、
前記削除処理は、前記管理構造部の前記第２の情報に削除対象データの識別情報を追記し、当該追記された情報が有効範囲に含まれるよう前記第３の情報を更新する
ことを特徴とする請求項１１に記載のプログラム。
【請求項１３】
カラム単位でタプルデータが格納されるストレージと、  前記ストレージについて、有効データ範囲を示す第１の情報とすでに有効でないデータの識別情報からなる第２の情報が格納される管理構造部と、を備えるカラムストアデータベースのデータ構造。
【請求項１４】
前記管理構造部は、前記第２の情報に追記される情報の有効範囲を示す第３の情報がさらに格納される
ことを特徴とする請求項１３に記載のカラムストアデータベースのデータ構造。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、カラムストアデータベースを処理するデータベース処理装置、方法、プログラム及びデータ構造に関する。
【背景技術】
【０００２】
カラム単位でデータ管理を行うカラムストアデータベースがある。カラムストアデータベースは、バッチ系、ＤＷＨ（Data Ware House）などの読み取り系ストレージとして発展したが、メモリの低コスト化、ＣＰＵのマルチコア化、リアルタイムデータの高速分析への要求によってこれをＯＬＴＰ（On-Line Transaction Processing）ワークロードにも適用し、高速大量の書き込み、高速並列読み取りを可能とする技術が求められている。例えば特許文献１には、カラムストアデータベースにおいてデータの追加処理によるパフォーマンスの低下を防ぐ技術が記載されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２０１１−２０９８０７号
【発明の概要】
【発明が解決しようとする課題】
【０００４】
カラムストアデータベースで書き換えを行う際はカラム間の不整合を伴わないよう、すべてのカラムもしくは行をロックし、読み取りクエリを同時実行しないよう制御したうえで書き換え、ロック解除を行う必要がある。これにより、書き込みクエリを実行している間は読み取りクエリを実行できなかった。また、書き込みクエリはメモリまたはＤｉｓｋ内のさまざまな個所を変更するため、キャッシュミスを多発し処理が遅くなる傾向にあった。
【０００５】
本発明は、上記問題点に鑑みてなされたもので、カラムストアデータベースの書き込みの高速化と読み込みの並列性を向上させることができるデータベース処理装置、方法及びプログラム等を提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明は、カラム単位でタプルデータが格納されるストレージと、前記ストレージについて、有効データ範囲を示す第１の情報とすでに有効でないデータの識別情報からなる第２の情報が格納される管理構造部と、を備えるカラムストアデータベースと、前記カラムストアデータベースに対してデータを追加する処理を行う場合、前記ストレージの末尾に前記データを追記して前記管理構造部の前記第１の情報を更新し、前記カラムストアデータベースに対してデータを削除する処理を行う場合、前記管理構造部の前記第２の情報に削除対象データの識別情報を追記するデータベース処理手段と、を備えることを特徴とするデータベース処理装置である。
【０００７】
本発明は、カラム単位でタプルデータが格納されるストレージと、前記ストレージについて、有効データ範囲を示す第１の情報とすでに有効でないデータの識別情報からなる第２の情報が格納される管理構造部と、を備えるカラムストアデータベースに対して、データを追加する処理を行う場合、前記ストレージの末尾に前記データを追記して前記管理構造部の前記第１の情報を更新し、前記カラムストアデータベースに対して、データを削除する処理を行う場合、前記管理構造部の前記第２の情報に削除対象データの識別情報を追記することを特徴とするデータベース処理方法である。
【０００８】
本発明は、コンピュータに、カラム単位でタプルデータが格納されるストレージと、前記ストレージについて、有効データ範囲を示す第１の情報とすでに有効でないデータの識別情報からなる第２の情報が格納される管理構造部と、を備えるカラムストアデータベースに対して、データを追加する処理を行う場合、前記ストレージの末尾に前記データを追記して前記管理構造部の前記第１の情報を更新する処理、前記カラムストアデータベースに対して、データを削除する処理を行う場合、前記管理構造部の前記第２の情報に削除対象データの識別情報を追記する削除処理、を実行させることを特徴とするプログラムである。
【０００９】
本発明は、カラム単位でタプルデータが格納されるストレージと、前記ストレージについて、有効データ範囲を示す第１の情報とすでに有効でないデータの識別情報からなる第２の情報が格納される管理構造部と、を備えるカラムストアデータベースのデータ構造である。
【発明の効果】
【００１０】
本発明によれば、カラムストアデータベースの書き込みの高速化と読み込みの並列性を向上させることができる。
【図面の簡単な説明】
【００１１】
【図１】図１は本発明の第１の実施形態に係るデータベース処理装置の構成を示す図である。
【図２】図２は本発明の第１の実施形態に係るデータベースの構造を示す図である。
【図３】図３は第１の実施形態の追加処理を具体的に説明するための図である。
【図４】図４は第１の実施形態の削除処理を具体的に説明するための図である。
【図５】図５は第１の実施形態の更新処理を具体的に説明するための図である。
【図６】図６は第１の実施形態の検索処理を具体的に説明するための図である。
【図７】図７は第１の実施形態の検索処理を説明するためのフローチャートである。
【図８】図８は本発明の第２の実施形態に係るデータベース処理装置の構成を示す図である。
【図９】図９は本発明の第２の実施形態に係るデータベースの構造を示す図である。
【図１０】図１０は第２の実施形態の追加処理を具体的に説明するための図である。
【図１１】図１１は第２の実施形態の削除処理を具体的に説明するための図である。
【図１２】図１２は第２の実施形態の更新処理を具体的に説明するための図である。
【図１３】図１３は第２の実施形態の検索処理を具体的に説明するための図である。
【図１４】図１４は第２の実施形態の検索処理を説明するためのフローチャートである。
【発明を実施するための形態】
【００１２】
以下、本発明の実施形態について図面を参照して説明する。
【００１３】
（第１の実施形態）
図１は、本発明の第１の実施形態に係るデータベース処理装置の構成を示す図である。データベース処理装置は、ＣＰＵと、ＧＰＵ等の並列演算器と、記憶部等を備えるコンピュータから構成され、図１に示すように、データベース１０と、並列演算器環境検知部２０と、データベース演算処理部３０と、データ処理結果・格納・再処理部４０とを備える。
【００１４】
データベース１０は、カラムストアデータベースである。データベースの管理単位は、タプル、カラム、テーブル、スキーマから構成され、それぞれ上位構造に対して複数を格納することができる。タプルは、データベース内部のある行のデータを含んでいる。あるカラムストア内部には特定のカラムのデータがタプル単位で集められる。データベース１０に格納されるデータは、固定長でもよく可変長でもよい。
【００１５】
データベース１０の構造を図２に例示する。図示されるように、データベース１０は、追記のみを許容するカラムデータベース（ストレージ）１１と、テーブル単位の管理構造部１２とを備える。管理構造部１２は、ある時点で有効とみなされる位置を示す最新タプル位置（max_TID）のデータと、すでに有効でないタプルの識別情報として、それまでに削除されたタプルＩＤの配列を示す削除タプル配列（delete_TID_Vector）のデータと、を記憶する。前記データベース演算処理部３０は、カラムストアデータベースを更新しているときのカラムストアデータベースに対する排他制御範囲を管理構造部１２に格納された情報に基づいて定める。
【００１６】
並列演算器環境検知部２０は、例えば、本装置における並列演算器の処理能力に関する情報（データ処理単位等）を取得する。
【００１７】
データベース演算処理部３０は、実行演算器判定部３１と、並列演算処理部３２とを含む。実行演算器判定部３１は、要求された計算処理について、並列演算器に適したものであるかを判断し、設定された判断結果に基づいて、いずれの演算器（ＣＰＵ、ＧＰＵ）を使用して演算処理を実行するかを判断する。例えば、並列演算器を使用して高速化可能な演算処理（カラムストレージへのfilter演算など）をあらかじめ設定しておき、要求された演算処理が設定された演算処理のいずれかに該当する場合には、並列演算器を用いると判断するようにしてもよい。また、実行演算器判定部３１は、並列演算器の使用率の情報を取得し、閾値よりも高い場合には、要求された演算処理をＣＰＵで実行すると判断し、その旨指示するようにしてもよい。並列演算処理部３２は、実行演算器判定部３１が並列演算器を使用すると判断した場合、並列演算器に各種演算処理を実行させる。
【００１８】
データ処理結果・格納・再処理部４０は、データベース演算処理部３０による演算結果を格納・処理する。
【００１９】
次に、本実施形態に係るデータベース処理装置の動作について説明する。データベース１０に対して行う処理は、データの追加（INSERT）、削除（DELETE）、更新（UPDATE）、検索（FIND）、検索結果に対する計算（Func）及び再処理（INSERT,DELETE,UPDATE）である。
【００２０】
追加処理（INSERT）について説明する。データベース演算処理部３０は、ストレージ１１に対し、新たに追加するデータの数だけ、ＴＩＤ（タプルＩＤ）を発行し、ストレージ末尾にデータの追記を行う。そして、追記を行うべき全てのカラムに対するタプル追記が完了した場合、管理構造部１２の最新タプル位置max_TIDを、追記したデータ数分だけ加算した値で更新する。このとき、旧max_TIDよりも小さいＴＩＤを持つデータの変更を行わないため、これにかかわる検索、データ削除等の他のデータベース処理を同時並行に実行することができる。
【００２１】
上記の追加処理を図３を参照して具体的に説明する。ストレージ１１にはＴＩＤ１９９までのタプルが存在し、このうちＴＩＤ１０、１１０、５０については、これまでの操作により既に無効になったデータとして記録されていることとする。このとき、max_TIDには１９９と設定されている。データベース演算処理部２２は、ストレージ１１に新しいデータをＴＩＤ２００として投入し、ストレージ１１に対する挿入処理が完了すると管理構造部１２のmax_TIDを２００に変更する。
【００２２】
削除処理（DELETE）について説明する。データベース演算処理部３０は、ストレージ１１に対し特定の値を無効にする場合、管理構造部１２の削除タプル配列delete_TID_Vectorに対して、指定の値を追記する。このとき、カラムストレージに対する変更を行わないため、これにかかわる検索等の他処理を同時並行に実行することができる。また、データの追加についても同時に実行することができる。
【００２３】
上記の削除処理を図４を参照して具体的に説明する。ストレージ１１にはＴＩＤ２００までのタプルが存在し、このうちＴＩＤ１０、１１０、５０については、これまでの操作により既に無効になったデータとして記録されていることする。このとき、max_TIDには２００と設定されている。ここでＴＩＤ１９９のデータを削除する場合、データベース演算処理部３０は、管理構造部１２のdelete_TID_Vectorの最後尾に、無効とするデータのＴＩＤ１９９（削除対象データの識別情報）を追記する。
【００２４】
更新処理（UPDATE）について説明する。データベース演算処理部３０は、更新対象となるタプルを検索して特定し、更新後のタプルデータを作成したうえで更新対象タプルを削除し、新しいタプルデータを追加する。更新処理は、検索、削除、追加の組み合わせで実現される。このとき、旧max_TIDよりも小さいＴＩＤを持つデータの変更を行わないため、これにかかわる検索、データ削除等の他のデータベース処理を同時並行に実行することができる。
【００２５】
上記の更新処理を図５を参照して具体的に説明する。ストレージ１１にはＴＩＤ２００までのタプルが存在し、このうちＴＩＤ１０、１１０、５０、１９９については、これまでの操作により既に無効になったデータとして記録されていることとする。このとき、max_TIDには２００と設定されている。データベース演算処理部３０は、ＴＩＤ１００に格納されているデータを更新する場合には、ＴＩＤ１００を削除し、新しいデータをＴＩＤ２０１として投入する。つまり更新処理は、これまでに説明した削除（DELETE）と追加（INSERT）の２段階の処理として実施される。
【００２６】
検索処理（FIND）について説明する。データベース演算処理部３０は、管理構造部１２からmax_TIDを取得し、そのＴＩＤ以下のカラムストレージ１１内の領域を検索領域（検索範囲）として設定する。また、データベース演算処理部３０は、管理構造部１２からdelete_TID_Vectorを取得し、検索から除外するデータとしてマークする。指定された条件による検索処理を実行し、ＴＩＤのリストとして結果を得る。
【００２７】
上記の検索処理を図６を参照して具体的に説明する。ストレージ１１にはＴＩＤ２０１までのタプルが存在し、このうちＴＩＤ１０、１１０、５０、１９９、１００については、これまでの操作により既に無効になったデータとして記録されていることとする。このとき、max_TIDは２０１と設定されている。この時点での検索は、ＴＩＤ２０１までのタプルを有効とし、delete_TID_Vectorに記録されているＴＩＤ１０、１１０、５０、１９９、１００のタプルについては無効として実行する。いま、検索操作は、指定されたカラムのデータが指定された条件を満たすかどうかについて検査を行う。データベース演算処理部３０により実現される検索器は、ストレージ１１から指定されたカラムを取り出し、さらにここからタプルが有効であるかどうかを判定する処理を行う。この処理を図７のフローチャートを参照して説明する。
【００２８】
データベース演算処理部３０は、あるタプルについて、そのＴＩＤがmax_TID以下どうかを判定する（ステップＳ１１）。この判定において、そのタプルのＴＩＤがmax_TIDよりも大きい場合（ステップＳ１１：ＮＯ）、検索処理を終了し、要求元に検索結果を送信する（ステップＳ１７）。また、タプルのＴＩＤが、max_TIDに一致するか小さい場合（ステップＳ１１：ＹＥＳ）、delete_TLD_Vector内部に処理対象タプルのタプルＩＤと一致するタプルＩＤが格納されているかを検査する（ステップＳ１２）。格納されている場合（ステップＳ１２：ＹＥＳ）、処理対象を次のタプルに移行する（ステップＳ１６）。格納されていな場合（ステップＳ１２：ＮＯ）、処理対象タプルが有効であるとし、そのタプルに格納されているデータを取り出す（ステップＳ１３）。そして、取り出したデータが検索条件にマッチするかを検査し（ステップＳ１４）、マッチする場合（ステップＳ１４：ＹＥＳ）には、その検索結果を所定記録領域に記録し（ステップＳ１５）、処理対象を次のタプルに移行し（ステップＳ１６）、フローはステップＳ１１に戻る。
【００２９】
この検索処理が実行されるとき、データベース内部の構造に一切変更を伴わないため、複数の検索クエリを同時実行できる。また、検索クエリの実行中に追加、削除、更新の各クエリを同時実行することができる。
【００３０】
データベース１０は大量のタプルを保持しており、特に検索処理においてはデータ処理量が多くなるために高速化を実現する要求がある。本カラムストアデータベースではカラムストレージに対して並列演算器での並列計算により検索処理等を高速化することができる。
【００３１】
データベース問い合わせ計算には途中結果をタプルに対する２値の配列として使用する場合が多くある。本追記型カラムストアデータベースの場合では、削除されたタプルを指定し、これを問い合わせ結果から除外する必要もある。このときにもタプルに対する２値の配列を使用する。並列演算器は２値配列の生成や合成を高速に実行することができる。近年のＧＰＧＰＵをこの演算高速化に適用する場合には、ストレージおよびdelete_TID_VectorをＧＰＵ側のメモリに格納し、クエリの結果合成をＧＰＵ側で行うことで高速性を発揮できる。
【００３２】
本発明は、大量の更新処理が必要かつ、高速な即時分析を行う分野での利用に適している。
【００３３】
以上説明したように本発明によれば、カラム単位にデータ格納が行われるデータベースに対して、ある時点での有効データ範囲をさし示すmax_TIDと、すでに有効でないデータ位置を示すdelete_TID_Vectorをもち、追記型の構成を持つことによってデータベースに対する排他制御範囲を小さくし処理の並列性を向上することができる。
【００３４】
（第２の実施形態）
図８は、本発明の第２の実施形態に係るデータベース処理装置の構成を示す図である。第２の実施形態のデータベース処理装置は、ＣＰＵと、ＧＰＵ等の並列演算器と、記憶部等を備えるコンピュータから構成され、データベース１０と、並列演算器環境検知部２０と、データベース演算処理部３０と、データ処理結果・格納・再処理部４０とを備える。第２の実施形態の各構成要素は第１の実施形態において対応する各構成要素とほぼ同様である。以下、第１の実施形態との相違点を中心に説明する。
【００３５】
データベース１０の構造を図９に例示する。図示されるように、データベース１０は、追記のみを許容するカラムデータベース（ストレージ）１１と、テーブル単位の管理構造部１３とを備える。管理構造部１３は、ある時点で有効とみなされる位置を示す最新タプル位置（max_TID）のデータと、すでに有効でないタプルの識別情報として、それまでに削除されたタプルＩＤの配列を示す削除タプル配列（delete_TID_Vector）のデータと、前記第２の情報に追記される情報の有効範囲を示す情報、すなわち、削除されたタプルＩＤ配列（delete_TID_Vector）の有効位置（deleteIndex）を記憶する。
【００３６】
次に、本実施形態に係るデータベース処理装置の動作について説明する。データベース１０に対して行う処理は、データの追加（INSERT）、削除（DELETE）、更新（UPDATE）、検索（FIND）、検索結果に対する計算（Func）及び再処理（INSERT,DELETE,UPDATE）である。
【００３７】
追加処理（INSERT）について説明する。データベース演算処理部３０は、ストレージ１１に対し、新たに追加するデータの数だけ、ＴＩＤ（タプルＩＤ）を発行し、ストレージ末尾にデータの追記を行う。そして、追記を行うべき全てのカラムに対するタプル追記が完了した場合、管理構造部１３の最新タプル位置max_TIDを、追記したデータ数分だけ加算した値で更新する。このとき、旧max_TIDよりも小さいＴＩＤを持つデータの変更を行わないため、これにかかわる検索、データ削除等の他のデータベース処理を同時並行に実行することができる。
【００３８】
上記の追加処理を図１０を参照して具体的に説明する。ストレージ１１にはＴＩＤ１９９までのタプルが存在し、このうちＴＩＤ１０、１１０、５０については、これまでの操作により既に無効になったデータとして記録されていることとする。このとき、max_TIDには１９９と設定されている。また、deleteIndexは２を示している（初期値０）。データベース演算処理部２２は、ストレージ１１に新しいデータをＴＩＤ２００として投入し、ストレージ１１に対する挿入処理が完了すると管理構造部１３のmax_TIDを２００に変更する。
【００３９】
削除処理（DELETE）について説明する。データベース演算処理部３０は、ストレージ１１に対し特定の値を無効にする場合、管理構造部１３の削除タプル配列delete_TID_Vectorに対して、指定の値を追記する。また、deleteIndexに１を加算する。このとき、カラムストレージに対する変更を行わないため、これにかかわる検索等の読み取り系他処理を同時並行に実行することができる。また、データの追加についても同時に実行することができる。
【００４０】
上記の削除処理を図１１を参照して具体的に説明する。ストレージ１１にはＴＩＤ２００までのタプルが存在し、このうちＴＩＤ１０、１１０、５０については、これまでの操作（削除）により既に無効になったデータとして記録されていることする。このとき、max_TIDには２００と設定されている。ここでＴＩＤ１９９のデータを削除する場合、データベース演算処理部３０は、管理構造部１２のdelete_TID_Vectorの最後尾に、無効とするデータのＴＩＤ１９９（削除対象データの識別情報）を追記する。また、追記された情報が有効範囲に含まれるよう、deleteIndexの２に１を加算して３とする。
【００４１】
更新処理（UPDATE）について説明する。データベース演算処理部３０は、更新対象となるタプルを特定し、更新後のタプルデータを作成したうえで更新対象タプルを削除し、新しいタプルデータを追加する。更新処理は、検索、削除、追加の組み合わせで実現される。このとき、旧max_TIDよりも小さいＴＩＤを持つデータの変更を行わないため、これにかかわる検索、データ削除等の他のデータベース処理を同時並行に実行することができる。
【００４２】
上記の更新処理を図１２を参照して具体的に説明する。ストレージ１１にはＴＩＤ２００までのタプルが存在し、このうちＴＩＤ１０、１１０、５０、１９９については、これまでの操作により既に無効になったデータとして記録されていることとする。このとき、max_TIDには２００と設定されている。データベース演算処理部３０は、ＴＩＤ１００に格納されているデータを更新する場合には、ＴＩＤ１００を削除し、新しいデータをＴＩＤ２０１として投入する。この場合、管理構造部１３のdelete_TID_Vectorの最後尾に、無効とするデータのＴＩＤ１００を追記し、deleteIndexの３に１を加算して４とする。また、max_TIDを２０１に変更する。つまり更新処理は、これまでに説明した削除（DELETE）と追加（INSERT）の２段階の処理として実施される。
【００４３】
検索処理（FIND）について説明する。データベース演算処理部３０は、管理構造部１２からmax_TIDを取得し、そのＴＩＤ以下のカラムストレージ１１内の領域を検索領域として設定する。また、データベース演算処理部３０は、管理構造部１３からdelete_TID_Vectorを取得し、deleteIndexから有効な削除位置を検出したうえで、検索から除外するデータとしてマークする。指定された条件による検索処理を実行し、ＴＩＤのリストとして結果を得る。
【００４４】
上記の検索処理を図１３を参照して具体的に説明する。ストレージ１１にはＴＩＤ２０１までのタプルが存在し、このうちＴＩＤ１０、１１０、５０、１９９、１００については、これまでの操作により既に無効になったデータとして記録されていることとする。このとき、max_TIDは２０１と設定されている。この時点での検索は、ＴＩＤ２０１までのタプルを有効とし、delete_TID_Vectorに記録されていてかつ、deleteIndex以下であるＴＩＤ１０、１１０、５０、１９９、１００のタプルについては無効として実行する。いま、検索操作は、指定されたカラムのデータが指定された条件を満たすかどうかについて検査を行う。データベース演算処理部３０により実現される検索器は、ストレージ１１から指定されたカラムを取り出し、さらにここからタプルが有効であるかどうかを判定する処理を行う。この処理のフローチャートを図１４に示す。図７に示す第１の実施形態の処理との相違点はステップ１２’である。ステップＳ１２’では、データベース演算処理部３０は、deleteIndexが示す有効位置までのdelete_TLD_Vector内部に、処理対象タプルのタプルＩＤと一致するタプルＩＤが格納されているかを検査する
【００４５】
この検索処理が実行されるとき、データベース内部の構造に一切変更を伴わないため、複数の検索クエリを同時実行できる。また、検索クエリの実行中に追加、削除、更新の各クエリを同時実行することができる。
【００４６】
データベース１０は大量のタプルを保持しており、特に検索処理においてはデータ処理量が多くなるために高速化を実現する要求がある。本カラムストアデータベースではカラムストレージに対して並列演算器での並列計算により検索処理等を高速化することができる。
【００４７】
データベース問い合わせ計算には途中結果をタプルに対する２値の配列として使用する場合が多くある。本追記型カラムストアデータベースの場合では、削除されたタプルを指定し、これを問い合わせ結果から除外する必要もある。このときにもタプルに対する２値の配列を使用する。並列演算器は２値配列の生成や合成を高速に実行することができる。近年のＧＰＧＰＵをこの演算高速化に適用する場合には、ストレージおよびdelete_TID_VectorをＧＰＵ側のメモリに格納し、クエリの結果合成をＧＰＵ側で行うことで高速性を発揮できる。
【００４８】
本発明は、大量の更新処理が必要かつ、高速な即時分析を行う分野での利用に適している。
【００４９】
以上説明したように本発明によれば、カラム単位にデータ格納が行われるデータベースに対して、ある時点での有効データ範囲をさし示すmax_TIDと、すでに有効でないデータを識別するためのデータ位置を示すdelete_TID_Vectorと、delete_TID_Vectorの有効位置を示すdeleteIndexをもち、追記型の構成を持つことによってデータベースに対する排他制御範囲をさらに小さくし処理の並列性をより向上することができる。
【００５０】
削除リストが追記構造を有しロックレスであれば、トランザクション実行初期化時にロックして取得し、読み込みクエリはこれ以降ロックなしで進行し、削除を伴う書込みクエリは書込み時にロックして削除リストの有効位置を取得し、追記を行って有効位置を更新し、ロック解除すればよい。これにより、削除リストのロック時間を短縮することができる。
【００５１】
なお、上記説明では、データベース処理装置がデータベース１０を備える構成としているがこれに限定されず、例えば、データベース１０を他の記憶装置に設け、この記憶装置と上記データベース処理装置をネットワーク等により接続するような構成としてもよい。
【００５２】
上述した本発明の実施形態に係るデータベース処理装置は、本装置のＣＰＵ（Central Processing Unit）が記憶部に格納された動作プログラム等を読み出して実行することにより実現されてもよく、また、ハードウェアで構成されてもよい。上述した実施の形態の一部の機能のみをコンピュータプログラムにより実現することもできる。
【００５３】
以上、好ましい実施の形態をあげて本発明を説明したが、本発明は必ずしも上記実施の形態に限定されるものではなく、その技術的思想の範囲内において様々に変形し実施することが出来る。
この出願は、２０１２年３月２６日に出願された日本出願特願２０１２−０６９０２６を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【００５４】
上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
【００５５】
（付記１）
カラム単位でタプルデータが格納されるストレージと、前記ストレージについて、有効データ範囲を示す第１の情報とすでに有効でないデータの識別情報からなる第２の情報が格納される管理構造部と、を備えるカラムストアデータベースと、
前記カラムストアデータベースに対してデータを追加する処理を行う場合、前記ストレージの末尾に前記データを追記して前記管理構造部の前記第１の情報を更新し、前記カラムストアデータベースに対してデータを削除する処理を行う場合、前記管理構造部の前記第２の情報に削除対象データの識別情報を追記するデータベース処理手段と、
を備えることを特徴とするデータベース処理装置。
【００５６】
（付記２）
前記データベース処理手段は、前記カラムストアデータベースを更新しているときの前記カラムストアデータベースに対する排他制御範囲を前記管理構造部に格納された情報に基づいて定める
ことを特徴とする付記１に記載のデータベース処理装置。
【００５７】
（付記３）
要求された演算処理を並列演算器を用いて実行するか否かを判定し、並列演算器を用いて実行すると判定した場合、前記要求された演算処理を前記並列演算器に実行させる実行演算器判定部をさらに備える
ことを特徴とする付記１又は付記２に記載のデータベース処理装置。
【００５８】
（付記４）
前記データベース処理手段は、前記カラムストアデータベースに対してデータを検索する処理を行う場合、前記管理構造部の前記第１の情報に基づいて検索範囲を決定し、前記第２の情報に基づいて検索から除外するデータを特定して検索を行う
ことを特徴とする付記１から付記３のいずれかに記載のデータベース処理装置。
【００５９】
（付記５）
前記データベース処理手段は、前記カラムストアデータベースに対してデータを更新する処理を行う場合、更新対象データを検索し、検索した更新対象データについて前記削除処理を行い、更新用に作成したデータについて前記追加処理を行う
ことを特徴とする付記１から付記４のいずれかに記載のデータベース処理装置。
【００６０】
（付記６）
前記管理構造部は、前記第２の情報に追記される情報の有効範囲を示す第３の情報がさらに格納され、
前記データベース処理手段は、前記カラムストアデータベースに対してデータを削除する処理を行う場合、前記管理構造部の前記第２の情報に削除対象データの識別情報を追記し、当該追記された情報が有効範囲に含まれるよう前記第３の情報を更新する
ことを特徴とする付記１から付記３のいずれかに記載のデータベース処理装置。
【００６１】
（付記７）
前記データベース処理手段は、前記カラムストアデータベースに対してデータを検索する処理を行う場合、前記管理構造部の前記第１の情報に基づいて検索範囲を決定し、前記第２の情報と前記第３の情報に基づいて検索から除外するデータを特定して検索を行う
ことを特徴とする付記６に記載のデータベース処理装置。
【００６２】
（付記８）
前記データベース処理手段は、前記カラムストアデータベースに対してデータを更新する処理を行う場合、更新対象データを検索し、検索した更新対象データについて前記削除処理を行い、更新用に作成したデータについて前記追加処理を行う
ことを特徴とする付記７に記載のデータベース処理装置。
【００６３】
（付記９）
カラム単位でタプルデータが格納されるストレージと、前記ストレージについて、有効データ範囲を示す第１の情報とすでに有効でないデータの識別情報からなる第２の情報が格納される管理構造部と、を備えるカラムストアデータベースに対して、データを追加する処理を行う場合、前記ストレージの末尾に前記データを追記して前記管理構造部の前記第１の情報を更新し、
前記カラムストアデータベースに対して、データを削除する処理を行う場合、前記管理構造部の前記第２の情報に削除対象データの識別情報を追記する
ことを特徴とするデータベース処理方法。
【００６４】
（付記１０）
前記カラムストアデータベースを更新しているときの前記カラムストアデータベースに対する排他制御範囲を、前記管理構造部に格納された情報に基づいて定める
ことを特徴とする付記９に記載のデータベース処理方法。
【００６５】
（付記１１）
要求された演算処理を並列演算器を用いて実行するか否かを判定し、並列演算器を用いて実行すると判定した場合、前記要求された演算処理を前記並列演算器に実行させる
ことを特徴とする付記９又は付記１０に記載のデータベース処理方法。
【００６６】
（付記１２）
前記カラムストアデータベースに対してデータを検索する処理を行う場合、前記管理構造部の前記第１の情報に基づいて検索範囲を決定し、前記第２の情報に基づいて検索から除外するデータを特定して検索を行う
ことを特徴とする付記９から付記１１のいずれかに記載のデータベース処理方法。
【００６７】
（付記１３）
前記カラムストアデータベースに対してデータを更新する処理を行う場合、更新対象データを検索し、検索した更新対象データについて前記削除処理を行い、更新用に作成したデータについて前記追加処理を行う、
ことを特徴とする付記９から付記１２のいずれかに記載のデータベース処理方法。
【００６８】
（付記１４）
前記管理構造部は、前記第２の情報に追記される情報の有効範囲を示す第３の情報がさらに格納され、
前記カラムストアデータベースに対してデータを削除する処理を行う場合、前記管理構造部の前記第２の情報に削除対象データの識別情報を追記し、当該追記された情報が有効範囲に含まれるよう前記第３の情報を更新する
ことを特徴とする付記９から付記１１のいずれかに記載のデータベース処理方法。
【００６９】
（付記１５）
前記カラムストアデータベースに対してデータを検索する処理を行う場合、前記管理構造部の前記第１の情報に基づいて検索範囲を決定し、前記第２の情報と前記第３の情報に基づいて検索から除外するデータを特定して検索を行う
ことを特徴とする付記１４に記載のデータベース処理方法。
【００７０】
（付記１６）
前記カラムストアデータベースに対してデータを更新する処理を行う場合、更新対象データを検索し、検索した更新対象データについて前記削除処理を行い、更新用に作成したデータについて前記追加処理を行う
ことを特徴とする付記１６に記載のデータベース処理装置。
【００７１】
（付記１７）
コンピュータに、
カラム単位でタプルデータが格納されるストレージと、前記ストレージについて、有効データ範囲を示す第１の情報とすでに有効でないデータの識別情報からなる第２の情報が格納される管理構造部と、を備えるカラムストアデータベースに対して、データを追加する処理を行う場合、前記ストレージの末尾に前記データを追記して前記管理構造部の前記第１の情報を更新する処理、
前記カラムストアデータベースに対して、データを削除する処理を行う場合、前記管理構造部の前記第２の情報に削除対象データの識別情報を追記する削除処理、
を実行させることを特徴とするプログラム。
【００７２】
（付記１８）
前記コンピュータに、
前記カラムストアデータベースを更新しているときの前記カラムストアデータベースに対する排他制御範囲を前記管理構造部に格納された情報に基づいて定める処理、
を実行させることを特徴とする付記１７に記載のプログラム。
【００７３】
（付記１９）
前記コンピュータに、
要求された演算処理を並列演算器を用いて実行するか否かを判定し、並列演算器を用いて実行すると判定した場合、前記要求された演算処理を前記並列演算器に実行させる処理
を実行させることを特徴とする付記１７又は付記１８に記載のプログラム。
【００７４】
（付記２０）
前記コンピュータに、
前記カラムストアデータベースに対してデータを検索する処理を行う場合、前記管理構造部の前記第１の情報に基づいて検索範囲を決定し、前記第２の情報に基づいて検索から除外するデータを特定して検索を行う処理、
を実行させることを特徴とする付記１７から付記１９のいずれかに記載のプログラム。
【００７５】
（付記２１）
前記コンピュータに、
前記カラムストアデータベースに対してデータを更新する処理を行う場合、更新対象データを検索し、検索した更新対象データについて前記削除処理を行い、更新用に作成したデータについて前記追加処理を行う処理、
を実行させることを特徴とする付記１７から付記２０のいずれかに記載のプログラム。
【００７６】
（付記２２）
前記管理構造部は、前記第２の情報に追記される情報の有効範囲を示す第３の情報がさらに格納され、
前記削除処理は、前記管理構造部の前記第２の情報に削除対象データの識別情報を追記し、当該追記された情報が有効範囲に含まれるよう前記第３の情報を更新する
ことを特徴とする付記１７から付記１９のいずれかに記載のプログラム。
【００７７】
（付記２３）
前記コンピュータに、
前記カラムストアデータベースに対してデータを検索する処理を行う場合、前記管理構造部の前記第１の情報に基づいて検索範囲を決定し、前記第２の情報と前記第３の情報に基づいて検索から除外するデータを特定して検索を行う処理、
を実行させることを特徴とする付記２２に記載のプログラム。
【００７８】
（付記２４）
前記コンピュータに、前記カラムストアデータベースに対してデータを更新する処理を行う場合、更新対象データを検索し、検索した更新対象データについて前記削除処理を行い、更新用に作成したデータについて前記追加処理を行う処理、
を実行させることを特徴とする付記２３に記載のプログラム。
【００７９】
（付記２５）
カラム単位でタプルデータが格納されるストレージと、  前記ストレージについて、有効データ範囲を示す第１の情報とすでに有効でないデータの示す第２の情報が格納される管理構造部と、を備えるカラムストアデータベースのデータ構造。
【００８０】
（付記２６）
前記管理構造部は、前記第２の情報に追記される情報の有効範囲を示す第３の情報がさらに格納される
ことを特徴とする付記２５に記載のカラムストアデータベースのデータ構造。
【符号の説明】
【００８１】
１０    データベース
１１    カラムデータベース格納部
１２、１３    管理構造部
２０    並列演算器環境検知部
３０    データベース演算処理部
３１    実行演算器判定部
３２    並列演算処理部
４０    データ処理結果・格納・再処理部
【図１】
0005999351.tif 000002
【図２】
0005999351.tif 000003
【図３】
0005999351.tif 000004
【図４】
0005999351.tif 000005
【図５】
0005999351.tif 000006
【図６】
0005999351.tif 000007
【図７】
0005999351.tif 000008
【図８】
0005999351.tif 000009
【図９】
0005999351.tif 000010
【図１０】
0005999351.tif 000011
【図１１】
0005999351.tif 000012
【図１２】
0005999351.tif 000013
【図１３】
0005999351.tif 000014
【図１４】
0005999351.tif 000015