As of the fix for
SERVER-30189, the $in parsing code makes use of a boost::flat_set in order to avoid the many small allocations required for a tree-based sorted set. This, however, results in O(n^2) worst-case time complexity for parsing an $in, since the boost::flat_set constructor is known to be quadratic:
For $in predicates with many elements, this causes a substantial performance regression. It is observable in that a large $in where the elements are pre-sorted outperforms a large $in where the elements are random by orders of magnitude. (When the $in elements are pre-sorted, the boost::flat_set constructor always inserts at the end of its vector, resulting in O(n log n) runtime.)
We should either patch boost to improve the boost::flat_set constructor's performance, or work around the issue by pre-sorting the $in elements prior to invoking the constructor.