There is a check in verification that verifies the entries in the history store always have corresponding entries in the data store. That check was failing (WT-5839) because we only ignore the tombstones in the history store but not ignoring the tombstones in the data store. As a result, when we see an entry in the history store, the corresponding entry in the data store may have been removed by a tombstone.

WT-5839 addresses that by ignoring non-globally visible tombstones for both the history store and the data store. It works for most of the cases but in the cases of out of order timestamp. It may break.

For example, if we have an entry with a tombstone of txnid 1 and timestamp 100 in the history store, then we commit a tombstone with txnid 100 and timestamp 0 in the data store. After that, we move the oldest id to 101 and move the oldest timestamp to 10.

If we call verify after that, the check will see the history store entry as its tombstone is not globally visible and is ignored. While we can't see the data in the data store because the tombstone in the data store is globally visible and thus is not ignored.

We have a hack to mitigate this problem by only ignoring non-globally visible tombstones in the history store but ignoring all the tombstones in the data store. However, the change is ugly and we prefer not to do it.

This also doesn't solve the problem completely. After we read the entry in the history store, the data store page may be evicted, in that case, when we read the data store page, the whole key is removed from the page and we can't find it no matter what we do.

Therefore, it is unsafe to run verify on tables that can have out of order timestamps. If possible, we should avoid doing that.