富士通でかつて年間２８００億円節約に貢献した、自然数インデックスをもう一度
JOINが1000倍早いなら、いまでも使えます。
この文章は、データベースの高速化に関心がある人向けの とあるインデックス についての記事です。とあるインデックスは、自然数インデックスと呼ばれるものです。実装は小学5年生でもわかるほど単純なのですが、応用は幅広くかなり難解のようです。自然数インデックスは古くから実装され実際にシステムとして稼働してます。自然数インデックスを使っているシステムは、2002年5月5日の日経新聞朝刊に、「富士通、2800億円削減 今年度新購買システム稼働」 という記事で紹介されています。日経テレコン使える人は、調べてみてください。２０年前の当時、私はこの話を自然数インデックスの開発者から聞いたとき非常に面白いと思いました。それから20年たった今ですが、私は、Jaxa のアポロの月地震計のデータ（postgres で、800Gぐらいあります）を扱う共同研究に一員として参加しています。このぐらい大きなデータになると自然数インデックスは非常に有効です。この自然数インデックスは、アーカイブデータ（変更のない）に特化して高性能をだします。それで、思ったことがあります。このぐらい大きなデータになると問い合わせに高速に対応できる高速なインデックスがやはり必要だということでした。20年前からある自然数インデックスはこのぐらい大きなデータになると非常に高速に対応できます。現在でもまだまだ使えるなという実感をもちました。自然数インデックスが高速である理由は多岐にわたりますが、インデックスを多用する JOIN のような操作において、特に効果を発揮します。それは、JOIN のための操作の大部分を、CPUキャッシュ（主にL2キャッシュ内）で行えるからです。自然数インデックスは、原理簡単（コードを書くのは）、実用的な応用は超難解（理解すればできる人ならすぐコードはかけます）なので、理解する人が増えればこれからのビッグデータの高速処理の一翼をになう存在になると思っています。残念ながら、私はコードをさくさく書ける人ではないので、この文章をできる人が読んで、さくっと実装してくれるのを望んでいます。実装簡単、応用無限大（但し、難解） の技術です。思考実験では、ビッグデータのjoin はおおよそ1000倍くらい速い です。
インデックスは、問い合わせを高速化するもの
まずは、ざっくりした話をします。インデックスとは、全件検索しなくても、検索をはじめとする高速な処理を行うためのものです。どうしたら高速にできるかというと、高速なメモリアクセスをすることです。
高速であることは計算量で議論されることが多いのですが、ここでは記憶媒体へのアクセス時間ということで考えます。まずは、
記憶媒体へのアクセス時間について、zacky1972さんの記事から引用します。
大雑把な目安として
レジスタ時間を1として、CPUキャッシュ時間を10 、メモリ時間を200, SSD時間を100,000 ディスク時間を10,000,000 ぐらいに考えます。
CPUキャッシュ時間とメモリ時間を比較すると 20倍くらいになります。自然数インデックスは、CPUキャッシュに適したインデックス構造なので、CPUキャッシュの高速性の恩恵をうけます。
いい加減な見積もりですが、JOIN の主要な作業がCPUキャッシュ時間でおわるなら、ディスク時間が多い場合に比べて、1000倍くらい早い可能性があります。上記の時間目安なら、１００万倍ですが、メモリキャッシュもあるので、ディスクの場合でも、1000倍ぐらいではないでしょうか？ 超いい加減な見積もりですが、１００億行のデータのJOINなら、１０００倍早い としてもいいでしょう。実際には、検索結果のJOINもあるので、通常の計算量の比較でも、１０００倍ぐらいでもよい気がします。検索結果にインデックスがついた状態でCPUキャッシュ活用のJOIN が可能なのが、自然数インデックスの強みです。
| メモリ/ストレージの種類 | アクセス時間 | アクセス開始までの所要クロックサイクル | 最大転送速度 | 容量 |
|---|---|---|---|---|
| レジスタ | 0.33〜1ナノ秒 | 1 | 96〜576Gbps換算 | 60〜256バイト換算 |
| L1キャッシュ | 1.33〜4ナノ秒 | 4程度 | 96〜576Gbps換算 | 32〜64KB |
| L2キャッシュ | 4〜15ナノ秒 | 12-15程度 | 96〜576Gbps程度？ | 512KB〜1MB |
| L3キャッシュ | 16〜50ナノ秒 | 〜50程度 | 96〜576Gbps程度？ | 16〜256MB |
| メインメモリ(DDR4) | 100ナノ秒 | 100〜300程度 | 96〜272Gbps程度 | 4GB〜2TB |
| NVMe SSD | 50マイクロ秒程度 | 50,000〜150,000程度 | 0.48〜33.6Gbps程度 (60〜4200MB/s程度) | 〜2TB |
| SATA3.0 SSD | 100〜200マイクロ秒程度 | 100,000〜600,000程度 | 0.14〜4Gbps程度 (17〜500MB/s程度) | 〜4TB |
| SATA3.0 HDD (3.5inch) | 10〜20数ミリ秒程度 | 10,000,000〜60,000,000程度 | 0.04〜0.8Gbps程度 (0.5〜100MB/s程度) | 〜16TB |
この記事のもとには学術的な論文は、宇宙科学分野のビッグデータ処理を高速化する自然数インデックス (NNI: Natural Number Index があります。論文だと高速性がわかりにくいで、できるだけわかりやすく説明したつもりなのがこの記事です。
単純な説明からはじめます。シングルカラムでシングル検索（ヒットはマルチもあり）
自然数インデクスの構造は非常に簡単です。ただ、さらにわかりやすくするために、単純な例からはじめます。データは、シングルカラムで、[a,z,b,c,d,a,x] 配列としましょう。非常に簡単な例です。通常データは、テーブル形式ですが、あえて、シングルカラムからはいります。そしてさらに単純化するために、一つの値を検索することにします。シングルカラム、シングル検索です。
検索結果とは、最終的には、配列上の位置(自然数インデックスの本質)を返すこと
a の値を検索するとはどういったことでしょうか？ 今はシングルカラムの検索です。マルチカラムすなわちテーブルの検索ではないです。通常のテーブル検索では、実際の値を返すものですが、シングルカラムだと、同じ値の羅列になります。シングルカラムで a（一つの値） を検索するとは、a がある配列の位置を返すことではないでしょうか？ データを固定長にすると配列の位置は、事実上、記憶媒体の位置情報になります。
[a,z,b,c,b,a,x] で、a を検索すると [a,a] が結果というのは変です。そういうわけで、検索結果は、配列の添字の配列とします。自然数インデックスは、問い合わせ結果は、添字の配列が基本なのです。ただ、マルチカラムになると、自然数が並びまくっていて、わけがわからないので、値をいれて説明するのが通常です。
値が、a だったら、検索結果は[0,5] の配列です。添字は、0から始まるとします。
| データ | 検索 | 結果 |
|---|---|---|
| [a,z,b,c,b,a,x] | 値 aを検索 | [0,5] |
これは、全件調べればわかります。
ではインデックスの定義です。
インデックスは、全件検索せずに、問い合わせ（ここでは、検索）に答えるもの - まず、自然数インデックスの説明
全件検索しないで、問い合わせに答えるのがインデックスの役割です。
自然数インデックスでは、もとの配列から次に説明のある配列（SVL,ACM,NNC,INV）をつくります。その配列の集まりをインデックスとしてつかいます。なお、配列の名称は論文とは少し違います。では少し長くなりますが、これから自然数インデックスの説明につきあってください。
まず、SVL,ACM,NNC,INV は記憶媒体上では、固定長です。固定長だと、添字からいきなり、記憶媒体にアクセス可能です。 オフセット＋(固定長の長さ✕添字の値) で位置情報を取得できます。レジスタ時間 で、位置情報を取得できるのです。
元データ
[a,z,b,c,b,a,x]
配列は、長さは、7 です。
SVL (sorted value list)
値をソートしてユニークにしたものです。論文とは少し違って最初にNULLをいれるようにしておきます。実際の値は、NULL がよくあるので、NULLがあったりなかったりより、最初からあるとしてしまいます。その方が便利ですので、すみません。NULL先頭にします。
-
通常の配列としての表現
[NULL,a,b,c,x,z] -
縦表現
| 添字 | SVLの値 |
|---|---|
| 0 | NULL |
| 1 | a |
| 2 | b |
| 3 | c |
| 4 | x |
| 5 | z |
ACM(累積数)
SVL の値が累積して何個あるかです。先頭はNULLなのですが、今回はNULLがないので、0 になります。
-
通常の配列としての表現
[0,2,4,5,6,7] -
縦表現
| 添字 | ACMの累積の値 |
|---|---|
| 0 | 0 |
| 1 | 2 |
| 2 | 4 |
| 3 | 5 |
| 4 | 6 |
| 5 | 7 |
NNC(自然数カラム)
もとの配列の値を、SVL の添字で置き換えたものです。
-
通常の配列としての表現
[1,5,2,3,2,1,4] -
縦表現
| 添字 | SVLの添字 |
|---|---|
| 0 | 1 |
| 1 | 5 |
| 2 | 2 |
| 3 | 3 |
| 4 | 2 |
| 5 | 1 |
| 6 | 4 |
INV(転置ソート配列)
もとの配列の添字を値でソート順（昇順）に並べた配列です。
-
通常の配列としての表現
[0,5,2,4,3,6,1] -
縦表現
| 添字 | NNCの添字 |
|---|---|
| 0 | 0 |
| 1 | 5 |
| 2 | 2 |
| 3 | 4 |
| 4 | 3 |
| 5 | 6 |
| 6 | 1 |
自然数ばかりでわかりづらいですね。次の版でわかりやすく変更する予定です。
では自然数インデックスをつかって検索してみましょう。
1.SVLで a の添字を見つける
下記から 1 です。実際は、二分木をつかいますが、ここでは省略。なお、固定長なので二分木検索できます。
| 添字 | SVLの値 |
|---|---|
| 0 | NULL |
| 1 | a |
| 2 | b |
| 3 | c |
| 4 | x |
| 5 | z |
2.ACM と INV をつかいます。
ACM は、SVL と同じ長さです。下記説明は説明不足ですね。すみません。少し思考実験して補ってください。
a は、SVLの添字の値が１です。ACMで同じ値の添字1 は2になります。
| 添字 | ACMの累積の値 | |
|---|---|---|
| 0 | NULL | 0 |
| 1 | a | 2 |
| 2 | b | 4 |
| 3 | c | 5 |
| 4 | x | 6 |
| 5 | z | 7 |
ここから、INV の範囲をわりだします。INVの最初は、一つ前のACMの値で、0 です。
INVの最後の添字は、2-1 で、1 です。[0,1]が、該当します。
| 添字 | ACMの累積の値 |
|---|---|
| 0 | 0 |
| 1 | 2 |
| 2 | 4 |
| 3 | 5 |
| 4 | 6 |
| 5 | 7 |
INV の範囲 0,1 から a のNNCでの添字がわかります。
| 添字 | NNCの添字 |
|---|---|
| 0 | 0 |
| 1 | 5 |
| 2 | 2 |
| 3 | 4 |
| 4 | 3 |
| 5 | 6 |
| 6 | 1 |
めでたく、[0,5] が得られました。
NNCで表現すると
| 添字 | SVLの添字 |
|---|---|
| 0 | 1 |
| 1 | 5 |
| 2 | 2 |
| 3 | 3 |
| 4 | 2 |
| 5 | 1 |
| 6 | 4 |
他の値 b で 検索
b でやってみましょう。
SVL の添字は、2
ACM から、INVの範囲は、2,4-1 で 2,3
INV の範囲2,3 からNNCは、2,4 となります。
SVL -> ACM -> INV -> NNC という流れです。
★つっこみどころ マルチカラムのテーブル表現ではどうなるのかな。
なんで 自然数インデックスだと高速なのか？
直接記憶番地にアクセスしてる
まず、SVL で値検索するところは、２分木なので、まあ速いですが、B-tree には負けるでしょう。
次のACM のところが速いのです。a の例で 1 なので、
ACMの配列[1] で値 2を呼び出しています。どこが速いのかというと、
1 から直接、ACMの値2が格納されている記憶番地にアクセスが可能です。先に説明したように、ACMが固定長だからです。
ACMの配列[1] -> メモリ or ディスク上にアクセスして、2 の値が格納されている記憶番地 -> aの値 と一度他の記憶番地を参照する必要がないです。レジスタ内での計算時間だけですみます。
インデックスにはいろいろのパターンがありますが、一度は、記憶番地が格納している記憶番地を参照するものが多いような気がします。ハッシュインデックスも、記憶媒体へのアクセスがひと手間あるようにみえます。
★実際のベンチマークがめちゃくちゃ難しいけど、できるだろうか？ この議論のレベルだとじゃないかに終わっているのでは、<- はいそうです。ベンチマークまで手が回りません。
このひと手間がどのくらいかかるかですが、ACMがメモリ上にあるとしても、１０倍はあるでしょう。レジスタ時間で済むというのが、自然インデックスが高速である大きな理由です。
参考 各種メモリ／ストレージのアクセス時間，所要クロックサイクル，転送速度，容量の目安
更に更に、高速である理由はあるのですが、今回はここまでです。
Discussion