History files data re-order [experiment]

tldr:
in history
- it stores keys/values in order (key, txnum)
- explore benefits of storing in order (txnum, key)
- probably merge is less i/o intensive
- maybe better data locality for `debug_traceTransaction`
- maybe file size will be impacted
- any difference on collation perf?

----

Sudeep — Yesterday at 14:34
why is history snapshot keys stored sorted by (key, txnum)? The only reason i can think of is better compression.

for some reason i think debug_traceTransaction/eth_call at previous block is the most important usecase for history (not sure if that is correct). But if so, it'll have better page cache locality of .v file if stored sorted by (txnum, key). Also, HistoryRange becomes fast. Merge probably becomes faster too.
Alex Sharov GMT+7 — Yesterday at 17:46
history snapshot keys stored sorted by (key, txnum) - they are not.
.v - values_list
.ef - key tx_nums_list
.efi - key -> offset in .ef
.vi - (key, txNum) -> offset in .ef

Because GetAsOf(k, n) does search in .ef first. Find there txNum >= n. And then somehow by (k, txNum) need to find exact offset in .v

PageLevel compression adding keys to .v files - because .vi can't address anything withing compressed page - so have to binary_search there by key. It's another story - it worked good for commitment.history and rcache.history because there are large values.
About: (txnum, key) format of .v. It can be better data-locality (for debug_traceTransaction) - and this is great.

But in (txnum, key) it's probably not the same txNum as you expect. Because we storing value BEFORE update in .v. Means when you do GetAsOf(k, n) we have to find value stored somewhere in txNum >= n (or fallback to .kv file).

So, in (txnum, key) - values will be grouped by update time (which likely will crazy speedup -blks-range check) - but re-execution of given block - probably will still have bad data-locality (but maybe much better than we have now).
Sudeep — 12:04
ah i see. makes sense. yes, keys are only stored when page compression is enabled.

we might get less i/o in merge as well (commitment/account/rcache) because now merge is a scan. But for chains like bloatnet -- commitment hist is disabled, and next big domaintype is storage, not acct.
Alex Sharov GMT+7 — 12:17
Can be. But i would still prioritize perf of debug_traceTransaction (re-exec on historical state) above merge perf. If can get both - great.
merge of .v - in my head it's sequential scan now.

Sudeep — 13:22
it's sequential within a single .v, but if merging N files, needs to keep N hot page cache entry
with (txnum, key) grouping, just do sequential scan of single file, followed by next file so on (so 1 hot page cache entry).
bt i guess it doesn't make huge difference because N is typically small.
i guess it's an okay idea, maybe only impact to be seen is file size change.
Alex Sharov GMT+7 — 13:27
can debug_traceTransaction benefit?
Sudeep — 14:00
in theory it sounds like better data locality. Have to check with experiments. Maybe for frequently changing accounts..