order preserving encoding

Order Preserving Encoding in Databases

Erigondb is a custom database designed for blockchain data, specially ethereum. It divided into multiple tiers, where the top, hot tier is MDBX - a mmap'ed database. While the lower tiers have immutable snapshot files.

I recently came across a problem when switching over from a hash index to a btree index for some snapshot files. The snapshot file is a sequence of key-values; and the btree index is built on top of it with some configurable degree of sparseness. The leaf of this btree index is essentially the snapshot file.

Btree employs some kind of memcmp – in memory comparison of keys to navigate through the tree and arrive at some offset on the snapshot file. This works only when the on-disk order matches the logical order of the keys. Most of the times, this is the case. For example, to map ethereum accounts to their values, the snapshot kv files are sorted by keys, which turn out to be the same as the logical order used by bt.

Sometimes they don't match. For example, when storing history, the key is key++txnum (where txnum is autoincrement transaction number; multiple keys can belong to a txnum). The snapshot kv we prepare is not sorted by the appended key, but rather by the tuple (key,txnum). Although they still store key++txnum as the key (there's no multikey).

Suppose if you have 3 entries: a) key=00; txnum=01 b) key=00; txnum=03 c) key=0001; txnum=00

ondisk stores a, b, c; but their logical order is a, c, b.

Problem: how do we then prepare a btree index for such a snapshot file?

Somehow we must produce a logical ordering which matches the physical (ondisk) ordering. This is where order preserving encoding comes in. So essentially, the keys you store in the btree file or query, need to be modified:

func order_preserving_encoding(key, txnum):
    return escape_and_terminate(key) ++ txnum

func escape_and_terminate(key):
    mk=nil
    for b in key:
        if b == 0:
            mk=mk ++ 0x00 ++ 0xFF
        else:
            mk=mk ++ b
    return mk ++ 0x00 ++ 0x00

this modifies the keys: a') 00 00 FF 00 00 01 b') 00 00 FF 00 00 03 c') 00 00 FF 01 00 00 00

which has order a', b', c'