そもそもカラムストアとは？
私を含め多くのデータベース・エンジニアにとってカラムストアは馴染みの薄いものだと思います。 そこで、カラムストアとはどのようなものなのかを考えてみます。 図はOracle技術者にはおなじみであるSCOTTスキーマEMP表の検索結果を表示させたものです。
リレーショナルデータベースとしての論理的な「タプル」と物理的な「レコード」はほぼ同一のイメージで、各レコードはrowidにより識別されます。 Oracleデータブロックには以下のイメージでデータが格納され、行ディレクトリには各行へのポインタ情報があります。（図2）
OLTPにより新たなレコードがインサートされた場合は、データブロックの空いた領域にレコードが格納されます。 また、格納済みレコードが更新され空き領域以上にレコード長が長くなる場合は、ポインタを残して別ブロックにレコードが移動される「行移行」が発生します。これはローストアならではの特徴と言えます。
次に、EMP表を基にカラムストアのイメージを考えてみます。
図3は各列を「EMPNO」「ENAME」…のように８つのカラムストアに分割したところを示しています。 カラムストア内のデータは同じデータ型なので、メモリ上では「配列（Array）」として実装され、配列内の各要素は添字（アドレス）で識別されます。 このイメージでは単純に分割しているだけなので、重複したデータが存在していて冗長に見えますが、配列の添字が同じデータを横串に連結すればタプルを表現できます。（赤枠）
1件のみのインサート処理でも8つのカラムストアそれぞれに書込みが発生するため、カラム数が多いほどローストアに比べてカラムストアは処理が複雑になります。
次に、カラムストアを重複排除およびソートしたイメージも考えてみます。（図4）
これは「SELECT DISTINCT （カラム名） FROM EMP ORDER BY （カラム名）」とした場合の結果をまとめたものとなります。
配列の大きさも各カラムのカーディナリティの違いからこの例では3～12の様々なバリエーションが存在します。つまり、この形式のカラムストアではカーディナリティが低いほど配列の大きさが小さくなり縦方向に圧縮（サイズ縮小）されることになります。
このような重複排除かつソートされた配列は「順序配列（Ordered array）」と呼ばれます。 順序配列ではインデックスなしでもバイナリサーチ（二分探索）による高速検索が可能となります。
※バイナリサーチは検索範囲を半分、さらに半分と絞り込むことで、先頭から順に検索するリニアサーチ（線形探索）と比べはるかに効率的に検索することができるアルゴリズムです。
また、配列の先頭と最後尾を参照することで、最小値と最大値を自動的に取得することができます。（「SAL」カラム等）
ただし、この形式では各配列の添字が異なるため図のようにタプルのイメージを形成することは難しくなります。
このように一口にカラムストアと言っても、その実装は複雑になりそうだとういう実感を持っていただけたでしょうか？ （上で挙げたカラムストアのイメージはあくまでも概念的なものであって、SAP HANAで実装されている形とは異なります。これは次々回にて説明する予定です。）
ここで、順序配列に挿入（削除）する場合について考えてみます。（図5）
「JOB」カラムに「ENGINEER」というデータを挿入しようとしています。 このデータは添字3の位置に挿入すべきですが、そこには既に「MANAGER」という値が入っているので、最後尾の「SALESMAN」から後ろに一つずつずらして添字3の位置を空けます。 そして、空けた位置に「ENGINEER」というデータを書き込みます。
すなわち①挿入する位置を特定する。②挿入位置以降のデータを後ろにずらす。③挿入する。という動作になります。
配列が大きいほど、挿入位置が先頭に近いほど挿入に対するコスト（時間）がかかるので、短いトランザクションでデータを処理する必要があるOLTPでも実用的な時間で処理ができるカラムストアを実現することは非常にハードルが高い課題になることが想像できます。
SAP HANAではこの課題をどのようにして解決しているのでしょうか？実際の仕組みを見てみましょう。
