memcomparable format について

Memcomparable format

TL;DR

複合キーでもソートしたいときに便利なフォーマット。

説明

バイト列を辞書順比較したい。一つのバイト列なら問題ないが、複数のバイト列を連結させてもソート順を保ちたい。シンプルにくっつけただけだと順序関係が壊れてしまうし、それぞれをデシリアライズして適切な型にしてから比較する必要があり、性能的に不利である。

ユースケースとして、 key-value store を 使って複合キーを表現したいときに使う。 複数のカラムを連結させて key として利用したい場合などである。

そこで使えるのが Memcomparable formatである。このフォーマットは、C言語の memcmp で比較可能なバイト列にすることを目指す。

簡単のため、ここではデータはバイナリで表現されるものとする。

データを 8 バイトで区切ったグループに分ける。そして、グループごとの末尾に extra byte としてそのグループの significant byte の総数を付与する。 extra byte は1から9までの値を取り、1から8までの数の場合はそれが最後のグループでありかつその数値はsignificantの数を表す。9の場合は、すべてのbyteがsignificantであり更にデータが有ることを示す。

ここで significant とは、元データが存在するバイトの数を示す。

また、バイナリ同士での比較となるため、Memcomparable formatでindex可能なカラムはbinary , latin1_bin, utf8_bin の collation のみがサポートされる。

参考文献

• https://github.com/pingcap/tidb/blob/master/util/codec/bytes.go
• https://github.com/KOBA789/relly/blob/wdb/src/memcmpable.rs
• https://github.com/facebook/mysql-5.6/wiki/MyRocks-record-format#:~:text=The memcomparable format allows comparison of two values,fields from the key and doing type-specific comparisons.