Fortran 時代からある発想でつくるビッグデータ用の高速かつコンパクトな【自然数インデックス】をざっくり紹介 します。

はじめに

この記事は、Fortran 時代からある発想の組み合わせでつくる高速なインデックスである【自然数インデックス】の紹介です。原理と構成、応用、そして実装についてざっくりと雰囲気がわかる解説です。読んだだけで、検証レベルでも面白い実装ができるように書いてあるつもりです。ぜひ、最後まで、お読みください。
自然数インデックスの対象は、レコード（行）、カラム（項目）からなる表形式（以下テーブルと呼びます）のデータです。おおよそCSVデータだと思っていいです。最近は、10GBを越して、項目数が数千もあるようなCSVはよくあります。そういったビッグデータになっているCSVを高速に扱うのが自然数インデックスです。さらに、全項目にインデックス付きでも圧縮可能で、コンパクトになるが自然数インデックスの特徴です。
自然数インデックスの論文もありますので、詳しく知りたい方は、お読みください。論文作成には私もかかわりました。この論文は、自然数インデックスの提唱者である古庄さんが、First Author です。

インデックスとは、データを全件走査せずに、データの格納位置を高速で特定するための仕組みです。実装はいろいろありますが、最終的には、データの記憶番地を使ってデータを取得するために使います。だとするとデータの記憶番地（行番号、配列で言えば添字）を直接使うとインデックスは高速になるはずです。これが自然数インデックスの基本的な発想です。テーブルデータの記憶番地つまり行番号（添字）は自然数の連番です。この自然数（添字）を値の代わりに操作するとアルゴリズムが、簡素化されます。値のデータ・タイプがなんであっても、自然数に変換されるからです。
大雑把にいえば、配列の添字をデータの値として操作する仕組みだと思ってもいいでしょう。
以下、説明は、単純からはじまり、用途別に複雑にすすみます。

自然数インデックスとは、まず単純な SVL + NNC

実際の例を見るほうがわかりやすいでしょう。自然数インデックスは、カラムごとにインデックスをつくるのでいわゆるカラム指向です。カラムを分離して扱えるので、必要なカラムのみ選択して利用することができます。例示してあるデータは、日時（途中とびがあります）、センサー（a,b,c の３種類）、観測値（実数）の３カラムです。

まずは、単純な事例で説明します。
図にある左の表形式デーブルをSVL(Sorted Value List),NNC(Natural Number Column) という一次元配列に分解し、すべての値が自然数からなる表形式テーブルに変換します。SVLは、値をソートして、重複なしにしたものです。このSVLの値番号（行番号のことですが、元の行番号ではないので、区別のために値番号と呼びます。）を実際の値と置き換えたのが、NNC です。
SVL + NNC の表現は、もとのテーブルと論理的に等価で相互変換可能です。
行番号、値番号の列がありますが、オレンジ色になっている部分は、データの位置なので、実装上は存在しません。

カウンティングソートが使えると思いませんか？　ソート激速ですよね。自然数化テーブルになるとすごい便利です。

右にある自然数インデックスの表を見て、ソートのときにカウンティングソートが使えるとピンときませんか？　カウンティングソートは計算量は、O(N) です。クイックソートは、O(N*LogN)です、ビッグデータになると計算量は劇的に変わります。ビッグデータになればなるほど、LogN が効いてきます。100万行のカウンティングソートとクイックソートだと log100万なので20倍ぐらいの差（いい加減な数字ですみません。）になります。

(問い)自然数インデックス（添字操作）は、なぜ速いか？

（回答）その１　事前にソートしてあるから、ソートが早い

なかなか理解してもらえなかった点なので最初につたえておきます。自然数インデックスは、あとで説明しますが、INVという形で事前にソートしておきます。計算量は、O(1)です。すでにソートしています状態です。イベントの受付で手渡す資料（首からかけてもらうネームタグなど）に連番をつけることはよくあります。それらの資料は連番順に並べ替えたり、名前順に並べ替えると便利ですね。こんな状況を念頭においてもらって、自然数インデックスは、全部のカラムで、ソートするので便利だと思ってもらえるでしょうか？　自然数インデックスは、データべース的には、すべてのカラムにインデックスをつける状態です。

（回答）その２　カウンティングソートだから、ソートが早い

これはすでに説明しました。ですが、カウンティングソートは早いというのがピンとこない人がかなりいます。もし、ここで、カウンティングソートだから、早いというのがピンとこないと自然数インデックスの面白さはわかりませんので、ぜひ、カウンティングソートを調べてみてください。「クイックソートですら足元に及ばないほど高速です。 おそらく、広く知られたソートアルゴリズムの中ではこれが最高速のソートでしょう。」というのは常識なはずです。

（回答）その３　固定長だから、データアクセスが早い

前提条件を述べておらずみません。物理的な記憶媒体への実装はデータを固定長にします。固定長になっていると添字（行番号、値番号）から、簡単な計算で記憶媒体上のアドレスを指定できます。
記憶媒体上のアドレス = データ長 * 番地（添字）　＋　オフセット
実際の値は、SVL にはいっているので、添字から記録媒体上のアドレスを取得し、値を取得します。固定長なのでいきなり値を取得が可能です。この計算は、データ長とオフセットは、CPUのレジスタに格納し、番地のデータのみ記憶媒体（メモリ、or ディスク）からの取得になり、高速化できます。
なお、並列（非同期）で、SVL経由のデータ取得が可能です。 つまり高速化が容易だということです。このあたりは、のちほど説明します。

実際はもっと高速化するために工夫（チート）します。（ACM,INV)

分解は、SVL,NNC が基本ですが、実際には、SVL+ACM,NNC+INV という分解を行います。先に、INVについては書きましたが、集計もします。
これは、検索とソートについての工夫（チート）です。高速化のための冗長な配列をつくります。

まず、ソート用の工夫（チート）のINVです。どうせソートするなら、はじめからソートしておきます。カラム毎のソートはこれで更に早くなります。ソート済みなのでソートが早いというのもおかしいですけど

図で、NNCのとなりに書いてあるINV(Inverted record Number )は、元の行番号を、値（センサー）順にソートしたものです。カラムの値にしたがって事前にソートしてある状態ですね。INVがあることで、ソートは激速になります。NNC->SVL 経由でデータ取得して、ただ、表示するだけです。

次は、ACM(Acumuration)です。
ACMは、ソートされた状態のINVでどこからどこまでが、同じ値番号になっているかをしめすものです。はいっているのはINVの最後の行番号＋１になっています。これは、計算の都合上です。検索結果が何個あるかは、検索結果の最後の値 -最初の値 = 個数　で計算します。一番最初の行には更に前の行（－１番目の行）が必要なります。行を０から始めているので、ACMの最初に０が来てもいいのですが、見た目で個数ゼロのようにも見えるで、＋１にしてあります。

★よくある指摘　（挿入、削除、変更に伴う再構築が必要）
挿入、削除でデータの位置が変わったら面倒じゃないですか？　はよくある指摘です。自然数インデックスは挿入、削除に弱いと誰もがすぐに思うでしょう。特にSVLは値の順番を使うので、変更があるとSVLの作り直しになります。変更があった場合は非常に面倒だというのは容易にわかります。だから、自然数インデックス的な発想は実用的ではないと思われてきたのでしょう。でも、本当にそうなんでしょうか？

★　指摘への回答　その１　変更なしのアーカイブデータだったら適用できます。
変更することないデータだったら、データの位置はかわらないので行番号をそのままつかってもよいはずです。
（例）チケット番号( git の issue )
git お使いの方は、「 issue #45　を早く処理してください」のようなやりとりはよく行うでしょう。チケットは一度番号をふったら、その番号はかわりません。というわけで、アーカイブデータだったらデータの位置は変わらないので、適用可能です。一度発生したデータの位置情報をそのまま使えるアーカイブ運用なら自然数インデックスの利点を適用できます。

実は、アーカイブ運用でなくても結構つかえます。あと記事でそのことは書きます。

★　指摘への回答　その２　高速で位置の変更やデータ書き換えができれば、変更があっても実用的です。挿入、削除、変更でデータで位置が変わると、インデックスとして保持しているSVLも変わるので、大変です。でも、メモリだったら書き換えやデータの移動が早いので、実用的なこともあります。メモリが、64k しかなかった時代では、想像もできない使い方ですが、今は、16G ぐらいあるのは普通です。最近、インメモリデータベースが使われるようになっています。これは、高速なデバイスの登場で、データの記憶番地の移動の処理時間が短くなり、実用的な時間の範囲になったからです。メモリ運用なら自然数インデックスをそのまま使っても十分に実用的です。

添字の集合は実は、特殊な性質をもっています。つかうといろんなことができます。それで、わざわざ完全連番という名称を付与しておきます。

添字は、0..n-1 の配列（集合として扱うことあります）です。間がつまっています。プログラムする人なら誰でも毎日のように使っている数の配列です。名称がついていないようなので完全連番と呼ぶこととします。この完全連番は非常に便利な性質があります。

一番重要なのは、連番圧縮ができることです。通常配列は、列記します。つまり、[a,b,c,d,e,f...]のように要素をすべて書き記す必要があります。完全連番は、N個あるとかけばよいだけです。これだけで、[0.....N-1]の数列と論理的に同じものです。このため、インデックスの値が見えなくなります。たとえば、NNCとINV 両方にインデックスがついている状態ですが、データ領域上は不要です。記憶番地をインデックスにつかう、隠れインデックスともいえます。さらに範囲が連番になっているなら、連番圧縮ができます。最初の番号から最後の番号の２つの番号を保持すればいいだけです。この性質があるため、完全連番は空気のような存在になっています。普段、毎日のようにつかっているのに、存在を意識していません。
自然数インデックスは、この完全連番の世界だけでできるだけ、処理をします。実際のデータが必要なときだけ、SVL 経由で、実の値を参照するのです。
他にも、完全連番の部分の配列であることは、高速化に非常に役立ちます。完全連番の部分配列にも、カウンティングソートは適用可能だからです。さらに並列化ができます。それらはおいおい説明していきます。

自然数インデックスでできること　いろいろ書きました。

• 圧縮: すべてのカラムがインデックスをつけても元テーブルより小さくできることがあります。多重度が多ければ、多いほど圧縮効率は良いです。
• 計算時間がO(n): 主要な操作（ソート、検索、抽出、JOIN）が、ときどきデータの比較が必要ですが、ほぼほぼ逐次処理で処理が可能です。ACMがあるので検索 → 件数を数える場合は、O(1)の場合もあり、非常に高速です。
• 遅延実行: 逐次処理を部分的にも、途中から実行も可能です。表示部分が少ない場合は、非常に高速です。
• サーバレス　ファイルサーバ機能をつかいクライントアプリのみ処理可能　遠隔地のテーブルもローカルなテーブルも組沢せて検索可能です。これは、一部のデータへのアクセスだけで処理が可能なためです。
• エンジンプログラムのフットプリントが少ない（10M程度）。主要なアルゴリズムが完全連番を前提にした自然数のみを扱うからです。
• 省メモリ実装が可能。スマホだけで遠隔のビッグデータ（ファイル）を検索可能
• 用途別実装　用途の合わせたIot 向けの限定実装や、高機能のデータベース用のエンジン実装も可能
• 同型（検索）: 検索結果を自然数インデックスと同型にすることが可能（インメモリ処理の場合は実用的）
• 結合（横）: テーブル長が同じなら複数テーブルをカラム結合しても、一体となった自然数インデックス付きテーブルとして扱える
• 結合（縦）: 複数テーブルをレコード結合しても、自然数インデックスとほぼ同様に扱える

このように完全連番をつかった自然数インデックスで実現できることは多岐に渡ります。この記事では、まずは、できることのごくごく一部のみ紹介します。工夫次第で面白いことができますので、ぜひ想像力をつかって用途別の自然数インデックスを実装してみてください。

なお、SVL+ACM,NNC+INVを作成するプログラムはこの説明で書くことができるのではないでしょうか？

上記の性質のうちいくつかをかなり簡素化していますが、解説します。

遅延実行: 逐次処理を部分的も、途中から実行も可能で、処理時間を最小化できる

単独カラムの検索は、検索結果の何番目から何番目とデータを指定して表示可能です。何番目のデータを特定するには、頭出しのみ２分岐検索なので、一度の計算量O(log(SVLの長さ))ですみます。十分にはやいです。検索件数が１００億でも、対話的な環境での検索結果の一部ブラウジングが、数十件を画面上に見せるだけなら、全くストレスなく可能です。さらに、複数のカラムのand検索でも、状態を維持して途中から再開が可能です。遅延実行を利用するアプリケーションには、様々な実装がありえます。従来のインデックス実装では対話的な運用が処理時間的に不可能な場合でも、自然数インデックスでは十分に可能な場合もあります。実装的には面白い領域です。これは、カラムがすべてソートされているために、逐次処理が可能で計算量がO(n) が基本になるためです。

結合（横）行数が同じなら、複数テーブルを透過的に結合可能

物理的な実体としてのテーブルが異なっていても、自然数インデックス化され、行数が同じであれば、どんなテーブルでも仮想的に一つの自然数インデックス化されたテーブルに統合することが可能です。イメージとしては、横結合です。逆にいえば、カラムを簡単に外だしできるようなものです。遠隔地にあるビッグデータに対して抽出処理用のフラグをローカルのテーブルとしてつくって運用することが可能になります。

結合（縦）　複数テーブルを行方向に結合もできます。結合しても自然数インデックスとほぼ同様に扱えます。

時系列データのテーブルを縦に結合して一つの仮想的なテーブルとして扱いたいということはしばしばあるでしょう。縦の結合です。自然数インデックスは、カラムをソートしてSVLを作成するのが基本なので、そのまま適用することはできません。複数テーブルでは、SVLは、レコード番号（添字）と値の紐付けがテーブルごとに異なるからです。しかし、先ののべたように自然数インデックスなら、遅延実行でO(処理件数×テーブル数)の計算量で検索取得が可能になります。そして、検索結果総件数は、もっと早くO(テーブル数）で取得可能で、十分に高速です。検索結果の何番目のデータというのも、おおよそO(log(もっとも件数の多いデータ)）で特定可能です。特定したあと、次のデータをたどっていく逐次処理は、最悪でもO（取得するレコード数×テーブル数）です。十分に早いでしょう。

★とりあえずここまです。図などは、不足しているので随時追加していきます。

次は、並列処理できることを書いてみます。JOINなどはその次です。