iterate_upper_bound semantics/performance opportunities

[markpapadakis]

I should have probably looked at the actual implementation, but if rocksdb::ReadOptions::iterate_upper_bound is defined, then maybe, when iterating, instead of comparing each key against the prefix key provided in Seek(), the upper bound can be used to determine, well, the upper bound using e.g binary search, so that you can safely assume that within a range [start, end) all keys will be >= prefix and thus commit the comparison altogether.
Apologies if this is already the case -- it doesn't seem to be though.

[siying]

@yiwu-arbug did a set of improvements so that the upper bound check is avoided if the whole data block or the whole SST file is inside the upper bound. Do you still see key comparison for upper bound for every key?

[markpapadakis]

@siying I am merely suggesting that if there's an upper bound key specified, then binary search can be used to determine the upper bound in a block's/SSTable's keys range, so that when iterating a [start, end) range, there won't be no need to invoke the comparator for the keys in that range to determine if the iteration is within that range, because the end of the range has been determined earlier using binary search and the upper bound key.

I am not familiar with the internals/semantics of rocksdb, but this seems like a trivial optimisation ? I experimented with KVs iterations with, and without, an UB key and it didn't seem to do that, based on then number of the time the comparator was invoked.