In SERVER-98115, we implemented an initial approach to sampling estimation of number of index keys of an IndexScan. It works by invoking the BTreeKeyGenerator on each document to generate the set of index keys expressed as key strings, converting each key string to BSON, and then evaluating how many keys fall in the given IndexBounds.

We can improve the performance by avoiding unnecessary allocations of key string and BSON index keys. We can use BSONElementIterator  to iterate over all values of indexed fields in a document and perform the comparisons to the bounds to determine how many keys match.