技術詳細: 成分分解法について

1. 成分分解法の概要

成分分解法 (Linear Filtering Method, LFM) は、ターボデータラボラトリが開発した革新的なデータベース技術です。多数の特許を日本国内・海外で取得済みです。

元来、データベースシステムに対しては以下の性能・機能向上の要求がありました。

・データを安全に更新する
・桁違いに大量のデータを扱える
・桁違いに高速に処理する
・アナリティクスにも適用できる
・複雑な計算処理を行うバッチ処理に適用できる
・分散環境にも対応できる

成分分解法は上記の多くに対して、最も優れた解であると言えます。

2. 成分分解法の長所

成分分解法は以下の長所を持っています。

1. 計算量がO(n)

ほとんどすべてのアルゴリズムの計算量をO(n)に引き下げることができます。(nはレコード数) 従来のデータベースシステムではO(n*log(n))ですから、オーダーの違う高速性を実現します。これはビッグデータを扱う際にきわめて有利な特性です。

2.高機能・高速なインデックス

データベースの高速化・効率化の鍵となるインデックスに関するさまざま課題を解決しました。何段階も処理を重ねても有効なインデックスを実現しました。BOM展開などの多段階処理では圧倒的な高速性を発揮します。

3.並列処理

ほとんどすべてのデータベース処理を並列化できます。近年では普通になったマルチコアCPUの並列処理機能を最大限に活かして、処理を何倍にも高速化できます。

3. 表形式データの成分分解の例

下図では、左側がデータベースの内容の表示(論理表現)、右側がそれに対応するメモリ内の内容(物理表現)になっています。論理表現を物理表現へ変換するのが「成分分解処理」です。図1

上段がデータベースの最初の状態です。すべての項目はValueNumberで管理され、項目の実際のValueはValueListに置かれています。すべての ValueListはソートされています。

中段は、上段にサーチ処理をした結果です。これは以下の手順で処理されます。

1.Age の ValueList 内で 8以上 のものを探す。結果は2と3。(この処理は軽い)
2.Age の ValueNumber 内で 2と3の物を探す。結果は0と2と5と6と7。
3.Name の ValueNumber から 0と2と5と6と7 を引く。結果は2と1と0と2と1。
4.Name の ValueList から 2と1と0と2と1 を引く。結果はCathyとBethとAnnとCathyとBeth。
5.Age の ValueNumber から 0と2と5と6と7 を引く。結果は2と3と3と3と2。
6.Age の ValueList から 2と3と3と3と2 を引く。結果は8と9と8と9と8。
7.上記4.6.を合わせたものが処理結果。

この処理は非常に軽いものであることがわかります。

下段は、中段をNameでソートしたものです。これは以下の手順で処理されます。

1.OrderedSetの内容0と2と5と6と7 を、Name のValueNumberから引く。結果は2と1と0と2と1。
2.2と1と0と2と1をソートする。結果は0と1と1と2と2。
3.Name の ValueList から 0と1と1と2と2 を引く。結果は AnnとBethとBethとCathyとCathy。
4.以下略

上記の処理で、OrderedSet以外の物理表現は変化していません。つまり成分分解で付加されたインデックスに変化はなく(不揮発)、非常に効率的に処理が進められることがわかります。

4. 成分分解法のモデル名について

成分分解法には、いくつかの種類(モデル)があります。主なものは、1/3 モデル、3/4 モデル、3/5 モデルです。

成分分解法で分解されたデータ形式は、下記のように分類できます。(1次元配列の場合)

1.昇順かつユニークなもの(整数や浮動小数点、文字列など)
2.ランダムだが上限・下限が決まった整数
3.(部分)昇順の整数(Tree技術)

成分分解法の各モデルで、が使うすべての成分の種類数を m とし、うち昇順もしくは部分昇順の成分の種類数を n として、各モデルを n/m モデルと呼ぶことにしました。

1/3 モデル: Zap-In (単純で最も成功している)
3/4 モデル: ツリー
3/5 モデル: 超並列専用ハードウェア向け

5. 参考文献

古庄 晋二著: 汎用超高速データベース処理技術 – 多様なデータ構造と超並列処理への普遍的アプローチ RealTimeVIDP  <amazon>