QlikViewの高速性を支えるアーキテクチャ（シンボルテーブルとビットスタッフト・ポインター）

今回はQlikViewがなぜ高速に動作するのか、内部的なアーキテクチャについて説明します。
上級者向けの内容ですが、QlikViewがなぜ高速に動作するのか、他のBIツールと一線を画すと言われているのはなぜなのか、QlikViewというソフトウェアの特長を理解する上でも、役に立つと思います。

まず、QlikViewの開発元であるQlikTech社が運営している「QlikView Design Blog 」というブログがあり、ここにはメーカーの方しか知り得ないような、アーキテクチャに関する情報なども掲載されています。
2012年から続いているブログで、現時点で175の記事が公開されています。

わたしもQlikViewの技術担当として、このブログをよく見るのですが、いままでにわたしが見た記事の中でも、特に以下の三つの記事には重要な内容が書かれています。

このなかでも、もっとも重要だと思っているのが一つ目に挙げた「Symbol Tables and Bit-Stuffed Pointers 」です。
今回はこの記事のポイントをまとめてみます。
※以降の内容は、もとの記事を翻訳／再構成したものです。完全な翻訳ではありません。

まず、QlikViewは取り込んだテーブルを、一つのデータテーブルと複数のシンボルテーブルに分けて格納します。
シンボルテーブルは項目ごとに一つずつ作られます。
たとえば、三つの項目からなるテーブルを取り込んだ場合、データテーブル x 1とシンボルテーブル x 3で、内部的には計四つのテーブルが作成されます。

簡単に図示すると以下のようになります。

それではつづいて、データテーブルとシンボルテーブルの中身について見てみましょう。

データテーブルは、もとのテーブルとおなじ構造を持ちます。行数と列数もおなじです。
ただし、データテーブルにはデータ値そのものではなく、シンボルテーブルへのポインターだけが格納されています。

言い換えると、データテーブルはもとのテーブルのデータ値を、すべてポインターに置き換えたものとなります。

データテーブルにデータ値がないという点に、はじめは混乱するかもしれません。QlikViewのアーキテクチャを語る際、データ値そのものは「シンボル」と呼ばれます。
たとえば「東京」「大阪」といった文字列や、「￥1,000」といった金額をあらわす数値などがシンボルです。

シンボルテーブルはデータ値そのものと、データテーブルへのポインターを持ちます。そのためシンボルテーブルは、つねに二列のテーブルとして構成されます。
ただし、データ値はすべて一意になっており、重複する行は含まれません。
これはデータ値が数値タイプでも文字タイプでも変わりません。

ここまでの内容を図示すると以下のようになります。

データテーブルとシンボルテーブルはポインターによって関連付けられているため、情報量としてはもとのテーブルと変わりません。
ただし、シンボルテーブルのデータ値が一意になっているため、その分データのサイズが圧縮されます。
さらに、ここで言うポインターは「ビットスタッフト・ポインター」と呼ばれるもので、サイズが非常に小さいという特長があります。

それではこんどは、ビットスタッフト・ポインターについて見てみましょう。

ビットスタッフト・ポインターというのは、つまり値の種類の分だけ、必要最低限のビット数で作成されるということを意味しています。
たとえば、A,B,C,Dの四種類のデータ値があった場合、ビットスタッフト・ポインターは以下の表のように2ビットで構成されます。

前述のとおり、データテーブルはもとのテーブルの構造を保管しているため、データに重複があります。
ただし、その重複しているデータはビットスタッフト・ポインターであるため、これを保存するためには必要最低限のサイズしか消費しません。

このように、シンボルテーブル（値を一意にする）と、ビットスタッフト・ポインター（必要最低限のサイズしか消費しない）の働きによって、QlikViewはもとのテーブルのサイズを大幅に圧縮します。
また、これによりQlikViewは大量データであっても高速に動作します。

では最後に、いままで説明してきた内容を、実際にどうように活用できるのか、もとの記事に例が二つ載っていましたので、紹介いたします。
まず、もとの記事にもあるように「シンボルのサイズ」と「データ値の一意の件数」を認識することが重要です。
そのことを念頭においてご覧ください。

AutoNumber関数（AutoNumberHash128関数とAutoNumberHash256関数を含む）を使用すると一意の連番が作成できます。
そのため、単純な連番でよい項目（おもにキー項目）は、AutoNumber関数に置き換えることで、シンボルのサイズを小さくできます。

さらにAutoNumber関数が優れているのは、”シンボルのサイズが小さくなる”だけでなく、”シンボルのサイズがゼロになる”という点です。
連番の値はポインターから計算できるため、ポインターのみあればよく、シンボルは必要なくなるということです。

AutoNumber関数を使用しなかった場合は、結果として連番だったとしても、シンボルのサイズがゼロにならない場合もあるので注意してください。
たとえば以下のようなLOAD文があったとします。

LOAD ID1,
AutoNumber(ID1) as ID2,
AutoNumberHash128(ID1) as ID3,
AutoNumberHash256(ID1) as ID4,
:

このとき、ID1が結果的に連番だったとしても、ID1のサイズがゼロにならない場合もあります。
しかし、ID2、ID3、ID4のサイズはゼロになります。

一つの項目を複数の項目に分割するだけでも、一意の件数を減らせる場合があります。
特に日付時刻の項目を秒単位まで保持しているような場合、一意の件数が非常に多くなる可能性があります。
（1日 = 24時間 x 60分 x 60秒 = 86,400秒なので、一日分で最大86,400種類の値が必要。）

日付時刻の項目は日付と時刻に分ける、時刻は秒単位を切り捨てるなどすることで、シンボルテーブルのサイズを大幅に小さくできる可能性があります。
以下は例文です。

Date(Floor(日付時刻)) as 日付
Time(Frac(日付時刻)) as 時刻
MakeTime(Hour(日付時刻), Minute(日付時刻), 0) as 時刻_分単位
MakeTime(Hour(日付時刻), Minute(日付時刻), Floor(Second(日付時刻), 15)) as 時刻_15秒単位

もとの記事の最後の部分を見ると、一意の件数が10万種類を超えるようなら、項目の分割を検討するとよいとあります。

たとえば、一年分の日付を表現するには365日分で、365種類の値が必要です。（閏年であれば366種類）
これに対して、もし年、月、日を別の項目に分割した場合は、年1種類 + 月12種類 + 日31種類 = 計44種類の値で、一年分の日付を表現できます。

ただ、日付の値は仮に10年分保持したとしても3,650件程度にしかならないため、そもそも問題にならないことが多いです。
注意しなければならないのは、時刻の値です。

もし時刻の値を秒単位まで保持しようとした場合、一日で最大86,400種類の値が必要になります。
24時間 x 60分 x 60秒 = 86,400秒

さらに、日付と組み合わせた場合、一年で最大約3千万種類の値が必要になります。
365日 * 86,400秒 = 31,536,000秒
もちろん、3千万種類というのは”最大で”ですが、一意の件数が非常に大きくなり得ることに変わりはありません。

今回はQlikViewのアーキテクチャについて説明いたしました。
QlikViewは高速性を実現するために、内部的にさまざまな工夫がなされています。今回紹介したシンボルテーブルとビットスタッフト・ポインターは、その代表例です。

ちなみに、QlikView Design Blogの最初の投稿は以下の記事で、QlikViewのバージョン1の画面が確認できます。
Welcome to the QlikView Design Blog

QlikView Design Blogには、他にもよい記事がたくさんありますので、機会があればまたこのブログで紹介していきます。

お疲れ様でした。