We love things to be sorted. And we have been trying to keep things sorted.
Yet another random idea that you probably have considered:
What if the key is just (pred, sub, obj) instead of (pred, sub)? To get the “posting list” from RockDB, we just seek to the prefix (pred, sub) and keep reading? The iterating might be painful, as opposed to a simple key-value fetch. But since RocksDB operates in blocks of about 4K, we can expect that once we hit a (pred, sub, obj), the other objs should be in the same block.