When debugging WT-5665, I noticed we may walk the entire history store tree for searching. The test reads data without a timestamp. Suppose the value we want to search doesn't exist, we place the history store cursor on the key larger than the one we want to search and call prev in __wt_hs_cursor_position. The prev call may potentially walk the whole tree and return not found because all the keys' tombstones are visible to the current search transaction.

This problem is exacerbated if we read without a timestamp. However, even if we read with a timestamp, this still can be pretty costly as a large chunk of the tree may be with tombstones that have timestamps visible to the search.