See sampling_estimator_impl.cpp. When estimating the total number of keys that would be scanned by an index scan, the sampling estimator naively iterates over the fields of the documents in the sample once per field in the index being scanned. This results in time complexity O(#fields in the index * #fields in the sample total).