構造写像アプローチ

スキーマごとにRDBテーブルを対応させます。blogアプリで説明すればカラム数4のテーブルとカテゴリカラムを加えたカラム数5のテーブルのふたつを別にします。

|id|title|body|update_at|
|0 |t0   |b0  |2009/10/5|
|1 |t1   |b1  |2009/10/5|

|id|title|body|update_at|category|
|2 |t2   |b2  |2009/10/5|misc    |
|3 |t3   |b3  |2009/10/5|tech    |

Nとmを使うと、各テーブルのレコード総数はそれぞれN以下です。スキーマ種別の数によりますが上限はNに抑えられます。各テーブルのカラム数のオーダーはmになります。

このアプローチの利点は、文書数に対してスケールしやすい、細かなチューニングがしやすい(カラムごとに厳密な型、各テーブルごとに個別のindexが可能など)というのがあります。

欠点は、テーブル数の増加、コードが複雑になる(DDLの発行が必要)、テーブル間にまたがった情報の取得が遅くなる、というのがあります。

テーブル同士の独立性が強い場合、最も素直かつ現実的なアプローチです。テーブル間にまたがった情報取得が必要な場合、構造写像アプローチ単体では厳しいので、他のアプローチを組み合わせる必要があります。

モデル写像アプローチ

モデル写像アプローチは厳密には色々パターンがありますが、ここでは次のようなキー、バリューのカラムを持つテーブルでスキーマ不定データを保持するアプローチを考えます。keyカラムに項目名(カラム型は文字列)、valueカラムに項目値(カラム型はvarcharまたはblob)を持たせます。

|id|key       |value    |type  |
|0 |title     |t0       |string|
|0 |body      |b0       |string|
|0 |updated_at|2009/10/5|date  |
|2 |title     |t2       |string|
|2 |body      |b2       |string|
|2 |updated_at|2009/10/5|date  |
|2 |category  |misc     |string|
type列のようなメタデータは別テーブルでもよい

Nとmを使うと、レコード数のオーダーは(N * m)になります。

このアプローチの利点は、テーブルにまたがった情報の抽出が速い(joinが不要)、実行時のDDLの発行が不要というものです。

欠点は、レコード数の増加、項目値の型変換が必要、適切なindexを張ることが難しい(ものによっては不可能)、というものです。

friendfeedアプローチ

friendfeedでは全データを持ったテーブルとインデックス用のテーブルを分けて持ちます。データテーブルのデータ列はアプリケーションに都合のよいシリアライズ化を施したデータです。

特定の条件で文書を検索する場合、インデックス用テーブルでレコードを抽出して、データテーブルとjoinします。

|id|data                  |
|0 |{title:t0,body:b0,...}|
|1 |{title:t1,body:b1,...}|
|2 |{title:t2,body:b2,...}|
|3 |{title:t3,body:b3,...}|

|id|title<indexed>|
|0 |t0            |
|1 |t1            |
|2 |t2            |
|3 |t3            |

|id|category<indexed>|
|2 |misc             |
|3 |tech             |

項目型などのメタデータを別テーブルに持つかもしれない(シリアライズが型を持たない場合)

Nとmを使うと、データテーブルのレコード数のオーダーはNになります。インデックス用テーブル数の上限はmです。インデックス用テーブルの各レコード数の上限はNです。

このアプローチの利点は、レコード数のオーダーがNで抑えられる点、index更新のコストが最小限というものです。

欠点は、データテーブルのデータ列のシリアライズおよびデシリアライズのコスト、テーブル数の増加、というものです。

salesforceアプローチ

salesforceアプローチは、friendfeedアプローチと同じく、全データを持つテーブルとインデックス用テーブルを別に持ちます。違うのはデータテーブルがあらかじめ多くのカラムを持つ点です。カラムの型はvarchar(もしくはblob)です。

|id|schema-id|val0|val1|val2     |val3|...|val500|
|0 |sc0      |t0  |b0  |2009/10/5|    |...|      |
|1 |sc0      |t1  |b1  |2009/10/5|    |...|      |
|2 |sc1      |t2  |b2  |2009/10/5|misc|...|      |
|3 |sc1      |t3  |b3  |2009/10/5|tech|...|      |

|id|title<indexed>|
|0 |t0            |
|1 |t1            |
|2 |t2            |
|3 |t3            |

|id|category<indexed>|
|2 |misc             |
|3 |tech             |

|schema-id|field     |column|
|sc0      |title     |val0  |
|sc0      |body      |val1  |
|sc0      |updated_at|val2  |
|sc1      |title     |val0  |
|sc1      |body      |val1  |
|sc1      |updated_at|val2  |
|sc1      |category  |val3  |
項目型などのメタデータの持ち方はこれに限らない

Nとmを使うと、データテーブルのレコード数のオーダーはNになります。インデックス用テーブル数の上限はmです。インデックス用テーブルの各レコード数の上限はNです。

アプローチの利点と欠点はfriendfeedとほぼ同じです。

friendfeedとsalesforceのアプローチは実に似ています。どちらかがマネしたのか(順序的にはsalesforceが先なのでマネしたのはfriendfeed)、試行錯誤の結果、同じ結論に達したのかは謎です。

両者とも、全データを持つデータテーブルのスケーラビリティへの解決にパーティショニング(or shard)で対処しています。Nが億のオーダーになっても、パーティショニングでレコード読み込みは対応できるということのようです。しかしindex更新が必要な更新処理には耐えられないので、そこはテーブルを分離、という結論です。