技術詳細: 成分分解法によるインデックス

1. データベースのインデックス概要

データベースの性能を上げるための、最も一般的で効果的な手法がインデックス(索引)です。一般のデータベースシステムでは、「ハッシュ」と「B-Tree」が良く使われます。

データベースの項目にインデックスを付けると、その項目に関する検索等の速度は大幅に向上します。一方、その項目のデータを変更・更新した場合には、そのインデックスの更新が必要になるため、速度低下の原因になります。そのため、インデックスを付加する項目は少数にしておくのが一般的です。

データベースを構築するときには、このインデックス設計が性能を上げるために非常に重要です。どの項目にインデックスを付けるかを、処理のバランスを考慮して決定する必要があります。後に処理の内容を変更する場合には、インデックス設計をやり直すことになり、長期の再開発期間が必要になります。

また、ある項目をデータベース処理した結果に得られた新しい項目にはインデックスは付いていませんので、必要であればその処理の後でインデックスを付ける必要があります。

2. 成分分解法によるインデックス

Zap-In/Zap-Over で採用している成分分解法では、インデックスがデータ構造に自然な形で組み込まれていますので、すべての項目にインデックスが付いています。このため、すべての項目についての処理を高速に行うことができます。また、インデックス設計が不要になるので、データベース構築が効率的に行えます。

また、データベース処理した結果で新しい項目が生成されても、その新しい項目にもインデックスが自動的に付いています。このため、その後の処理も高速に行われます。インデックス再設計も必要ありません。

3. 各方式の比較

「ハッシュによるインデックス」「B-Treeによるインデックス」「成分分解法」の3つについて、データベース処理の速度の比較を表にしました。

各処理で、成分分解法が非常に優れた特性を持ち、特にデータ量が大きくなった場合には非常に大きな優位性があることがわかります。また、成分分解法ではマルチコアCPUによるマルチスレッドが効果的に作用することも示されています。

処理 ハッシュ B-Tree 成分分解法(pは並列スレッド数)
インデックス付加する項目 主キーのみ 少数 全項目
インデックス生成時間 小さくない 大きい 初回のみ
必要なメモリ量 O(n) O(n*log(n)) なし
SEARCH o(1)
完全一致、1件のみ
o(m*log(n))
mはヒット件数
O(n/p): デフォルト時
O(log(n)/p): 高速化時
SEARCH (部分集合内)
sは部分集合のサイズ
O(s)
完全一致のみ
O(s)+O(m*log(n)) O(s/p)
SORT 効果なし  O(n*log(n)) o(n/p)
SORT (部分集合内)
sは部分集合のサイズ
効果なし O(n*log(n)) o(n/p)
UNION
n1, n2 はテーブルのサイズ
効果なし  効果なし o((n1+n2)/p)
UNION(部分集合)
s1, s2 は部分集合のサイズ
効果なし 効果なし o((s1+s2)/p)
JOIN
n1, n2 はテーブルのサイズ
O(n1)
(SEARCH JOIN)
O(n1*log(n2))
(SEARCH JOIN)
o((n1+n2)/p)
(SORT JOIN)
JOIN(部分集合)
s1, s2 は部分集合のサイズ
効果なし 効果なし o((s1+s2)/p)
(SORT JOIN)
集計 効果なし  効果なし o(n/p)
集計(部分集合) 効果なし 効果なし o(n/p)
インデックス更新 逐次的 面倒 不要