豪鬼メモ

一瞬千撃

データベースにおける浮動小数点数の表現

実数のデータをデータベースの検索キーにするなら、実数をどのように表して保存するかが問題になる。精度を最大化するためには、浮動小数点数のバイナリをそのまま格納したいところだ。そこで、浮動少数点数のデータをバイナリ形式のままバイト列に変換するシリアライザと、そのバイト列同士の前後関係を判定するための比較関数を実装した。また、TkrzwのB+木データベースにそれらを組み込んで、使い勝手を確認した。


まずはおさらいだ。浮動小数点数とは、実数の近似であり、符号（sign）と仮数（significand/fraction）と指数（exponent）のタプルとして値を表現する方式である。典型的には基数は2であり、sign * significand * 2^exponent という式で元の値が手に入る。C99およびPOSIXのfrexp関数を使うとこの分解が簡単にできる。例えば、1.0を表すなら、符号が1、仮数は0.5、指数は1だ（1 * 0.5 * 2^1 = 1.0）。-0.125を表すなら、符号が-1、仮数は0.5、指数は-2となる。仮数の変域は、ゼロ以外の場合、0.5以上1.0未満と決められていて、それを超えるなら2で割って指数を増やし、それ未満になるなら2を掛けて指数を減らすことになる。

現在市場にあるほとんどのシステムはIEEE754の二進単精度浮動小数点数（binary32 = float）と二進倍精度浮動小数点数（binary64 = double）を実装していて、前者は合計4バイト、後者は合計8バイトのオブジェクトとしてタプルを格納する。単精度と倍精度に加えて拡張精度浮動小数点数（long double）をサポートしている処理系も多い。しかし、long doubleのバイト数はi386の処理系だと12バイトで、x86_64の処理系だと16バイトだし、コンパイラのオプションでも処理内容が変わるので、ちょっと気を使う。いずれにせよ、符号と仮数と指数はそれぞれの方式でビット列にエンコードされた上で、連結される。

IEEE754において浮動小数点数のビットの並びは決まっていて、例えばdoubleでは先頭1ビットは符号で、次の11ビットは指数で、残り52ビットが仮数である。しかし、それらを繋げた64ビット=8バイトをメモリ上に格納する方法は処理系のバイトオーダーに委ねられる。つまりビッグエンディアンの処理系では最初の1バイトは符号の1ビットと指数の最初の7ビットを格納する一方、リトルエンディアンの処理系では最初の1バイトは仮数の最後の8ビットを格納する。

さて、データベースファイルには相互運用性を持たせたい。すなわち、ある処理系で作ったデータベースファイルを別の処理系に転送しても使えるようにしたい。実数の相互運用性を考える場合、大きく分けて二つの方法がある。テキスト形式とバイナリ形式である。テキスト形式では、"-123.456" のように人間可読な文字列をDBに格納する。バイナリ形式では、IEEE754にバイトオーダー正規化を施したバイナリをDBに格納する。

テキスト形式の利点は、読みやすいことと、精度を自由に決められることと、処理系依存性が皆無であることだ。例えば1/3を保存するなら、最大精度を確保すべく "0.3333333333333333" という文字列を保持してもいいし、有効桁数を適当に決めて丸め処理を行った上で "0.333" とかにしてもいい。doubleを10進数で表した場合の有効桁数は16桁くらいだが、その範囲であれば精度と空間効率のトレードオフを自分で調整できる。

バイナリ形式の利点は、最大精度でデータを保存しても空間効率が落ちないことだ。floatの演算結果はfloatをシリアライズした4バイトのバイナリとして保存すればいい、doubleの演算結果はdoubleをシリアライズした8バイトのバイナリとして保存すればいい。doubleで演算してfloatに丸めて保存したり、long doubleで演算してdoubleに丸めて保存したりもできなくはない。処理系がIEEE754（のbinary32/64）に準拠していることを前提として、バイトオーダーだけビッグエンディアンに統一してシリアライズすれば、相互運用性にも問題はない。メインフレームのシステムを組んでいるのでもなければIEEE754準拠でない処理系について考える必要はそうそうないだろう。なお、シリアライズとデシリアライズの処理の時間効率がテキスト形式の処理よりはほんのちょっとだけ高いことも利点と言えるかもしれないが、DBの文脈ではほとんど意味がない。

DBMライブラリであるTkrzwは、任意のバイナリを保存する仕組みなので、実際に格納されるデータがテキストなのかバイナリなのかは感知しない。ユーザが適当に決めればいい。ハッシュデータベースのキーに求められる要件は、区別すべきレコードのキーはバイナリパターンが異なるべきということだけだ。ツリーデータベースのキーに求められる要件は、そのバイナリパターンを比較関数に渡した時に区別できるということだが、比較関数はユーザが自由に定義できるので、やはり要件はユーザに委ねられる。よって、実数のキーをテキスト形式で表しても浮動小数点数のバイナリ形式で表しても問題ない。そのへんの機微が分かっている人だけが使うライブラリなので、このスパルタンな仕様は妥当だと思っている。その上で、できるだけ便利に使えるユーティリティをも提供していきたい。

データベースの主キーに実数を使うというのは普通は推奨されない。同一性が精度に左右されるのは望ましくないからだ。実数をキーにする典型的なユースケースは、主キー以外の属性を使ったセカンダリインデックスを構築することだろう。例えば学力偏差値によるランキングとかだ。ランキングということはキーの昇順または降順でレコードにアクセスするので、必然的にツリー系のアルゴリズムが選択される。Tkrzwで言えばTreeDBMとSkipDBMだ。TreeDBMでは比較関数を自由に定義して指定できるが、デフォルトではバイト列の辞書順の比較関数であるLexicalKeyComparatorというのが使われる。バイト列の辞書順の比較というのは便利なもので、UTF-8のテキストならUnicodeのコードポイントの辞書順になるし、ビッグエンディアンの正整数なら数値の順になるし、IEEE754の浮動小数点数をビッグエンディアンで表した場合でも、正数の実数の範囲であれば、数値の順が保たれる。

テキスト形式で数値を格納した場合、辞書順の比較はうまくいかない。例えば、"10" よりも "2" の方が後になってしまう。桁数を固定にして "00000010"、"00000002" などと表現すれば数値順と辞書順が一致することになるが、空間効率が悪化するし、桁数を予め決めねばならないというのが保守性を悪化させる。固定長にするくらいならバイナリを使えよと言いたくなる。なので、テキスト形式の数値を簡単かつ直感的に扱うためには、10進数文字列用の比較関数を使う方が良い。Tkrzwでは10進整数用のDecimalKeyComparatorと、10進実数用にRealNumberKeyComaratorというのが用意されている。後者は前者の上位互換とも言えるが、前者は "10" と "10.1" を同一視し、後者は区別するので、使い分けた方が精神衛生上良いだろう。実数を使ってインデックスを作るPythonコードの例を以下に示す。

import tkrzw

# 10進実数用比較関数を指定してデータベースを開く
open_params = {
    "truncate": True,
    "key_comparator": "RealNumber",
}
status = dbm.Open("casket.tkt", True, **open_params).OrDie()

# キーを10進実数テキストとして表してレコードを格納する
# e.g: "1.5" -> "hop"
dbm.Set("1.5", "hop").OrDie()
dbm.Set("256.5", "step").OrDie()
dbm.Set("32.5", "jump").OrDie()

# 格納したレコードを検索する
print(dbm.GetStr("1.5"))
print(dbm.GetStr("256.5"))
print(dbm.GetStr("32.5"))

# キーの昇順で全レコードを操作する
iter = dbm.MakeIterator()
iter.First()
while True:
    record = iter.GetStr()
    if not record: break
    print("{:.3f}: {}".format(float(record[0]), record[1]))
    iter.Next()

# データベースを閉じる
dbm.Close().OrDie()

やはり、テキスト形式は読みやすいのがいい。コードが読みやすいし、データも読みやすい。コマンドユーティリティでもデータベースの中身を簡単に確認できる。

$ tkrzw_dbm_util list casket.tkt
1.5      hop
32.5     jump
256.5    step

有効桁数に基づいたキーの変換も、どの言語にもあるだろうformatとかsprintfとかいった関数で簡単にできる。しかし、良いことばかりではない。有効桁数を最大化して16桁とかにすると空間効率が悪くなるし、長すぎると人間可読性も落ちるのがいただけない。とはいえ、実際のところ、学力偏差値のランキングを作るような場合、有効桁数は最大化したいだろう。偏差値 58.3451 の人が偏差値 58.3452 の人より上位になっていたら納得行かない。58.34 くらいまでしか表示しなければユーザから文句は来ないだろうけど、そういう問題じゃない。例えば指定校推薦をそれで決めるような場合には、順位の決定は非常に重要になるので、無限精度にはできないにしても、せめて最大精度にしておきたいところだ。

てことで、多少面倒でも、バイナリ形式の浮動小数点数をDBに格納したくなることがある。ここまで長々と講釈を垂れたが、これが言いたかったのだ。で、Tkrzwの最新版（1.0.30）と各種言語バインディングでは、それを簡単に行う機能が追加されれいる。SerializeFloat/DeserializeFloatというユーティリティ関数で、浮動小数点数をビッグエンディアンでシリアライズしたりそれをデシリアライズしたりするのが一撃でできる。また、そうしてシリアライズしたキーを昇順で比較するFloatBigEndianKeyComparatorという比較関数が組み込まれている。それらを使うと、テキストの場合とほぼ同じコードでバイナリの処理が可能になる。

import tkrzw

# バイナリ浮動少数点数用比較関数を指定してデータベースを開く
open_params = {
    "truncate": True,
    "key_comparator": "FloatBigEndian",
}
status = dbm.Open("casket.tkt", True, **open_params).OrDie()

# キーをバイナリ浮動少数点数として表してレコードを格納する
# e.g: "\x3F\xF8\x00\x00\x00\x00\x00\x00" -> "hop"
dbm.Set(tkrzw.Utility.SerializeFloat(1.5), "hop").OrDie()
dbm.Set(tkrzw.Utility.SerializeFloat(256.5), "step").OrDie()
dbm.Set(tkrzw.Utility.SerializeFloat(32.5), "jump").OrDie()

# 格納したレコードを検索する
print(dbm.GetStr(tkrzw.Utility.SerializeFloat(1.5)))
print(dbm.GetStr(tkrzw.Utility.SerializeFloat(256.5)))
print(dbm.GetStr(tkrzw.Utility.SerializeFloat(32.5)))

# キーの昇順で全レコードを操作する
iter = dbm.MakeIterator()
iter.First()
while True:
    record = iter.Get()
    if not record: break
    print("{:.3f}: {}".format(tkrzw.Utility.DeserializeFloat(record[0]), record[1].decode()))
    iter.Next()

# Closes the database.
dbm.Close().OrDie()

繰り返しになるが、ビッグエンディアンのバイナリとしてキーをシリアライズしていれば、デフォルトのLexicalKeyComparatorでも、浮動少数点数の昇順でレコードにアクセスすることができる。よって、今回追加した関数群を使わなくても、各言語のpack/unpack関数でビッグエンディアンでシリアライズしてデフォルトの比較関数をそのまま使えば、バイナリの浮動小数点数を扱うことは従来から可能だ。しかし、正数の範囲ならバイナリの辞書順と数値の昇順が一致するというのは、IEEE754の策定者にとっては意図的であったとしても、利用者には偶然の産物に見えるわけで、それに依存したコードを書くのはちょっと気持ち悪い。また、負数や非数を入れるとうまく動かないというのも気持ち悪い。さらに、各言語のpack/unpack関数の挙動を把握するのも面倒くさい。それよりは、ライブラリが提供する統一された関数群を使う方が直感的だし、相互運用性をライブラリ側の責任にできるというのは気が楽だ。

実数のキーを使ったデータベースの構築方法については、各言語でサンプルコードを用意しておいたので、そちらもご覧いただきたい（C++、Java、Python、Ruby、Go）。

余談だが、空間効率を気にするのであれば、圧縮オプションを有効にすると良い。Tkrzwのビルド時にZLIB/ZSTD/LZ4/LZMAを有効にしていれば、DBを開く際のパラメータにどれかを指定するだけで、簡単に圧縮できる。ツリーデータベースの圧縮はページ毎に行われるので、アプリ側で個々のレコードを圧縮してから保存するよりも遥かに効率が良い。圧縮率と速度の話についてはこちらの記事をご覧いただきたい。

params.key_comparator = FloatBigEndianKeyComparator;
params.record_comp_mode = tkrzw::HashDBM::RECORD_COMP_ZSTD;
dbm.OpenAdvanced("casket.tkt", true, File::OPEN_TRUNCATE, params).OrDie();

さらに余談だが、圧縮と同じ機構で、RC4やAESによる暗号化もできる。DBを開く際に同じ暗号キーを指定すれば正常に動くが、そうでなければDBが開けない状態になる。もちろん、データベースファイルのバイナリパターンを解析してもレコードの中身を見ることは不可能だ。

params.record_comp_mode = tkrzw::HashDBM::RECORD_COMP_AES;
params.cipher_key = "hogehoge";
dbm.OpenAdvanced("casket.tkt", true, File::OPEN_TRUNCATE, params).OrDie();

まとめ。実数をキーにしてデータベースを構築するなら、ちょっと面倒だけど、バイナリ表現を使うのがおすすめだ。精度と空間効率が最大化するし、それでいて相互運用性も確保できる。ツリー系データベースを使う場合、シリアライザとでシリアライザに加えて、比較関数も実装することが望ましい。Tkrzwの最新版ではそれらが提供されているので、簡単に実数のデータベースを構築することができる。