Mongodb $in implementation and complexity

Question

Here is our document schema

{
  name: String
}

Here is our query

{
  name: {$in: ["Jack", "Tom"]}
}

I believe even if there isn't an index on name, the query engine will turn the array in the $in into a hashset and then check for presence as it scans through each record with a COLSCAN which is O(n). It will never do a naive O(m*n) search, right?

I'm trying to find supporting documentation online but I've come up short. I've tried searching in the source code but I can't seem to find the exact section responsible for this either.

If the index exists I believe that it will use it directly instead and be faster. If I'm not wrong I think it will be O(m*log(n)) as it gets the result set in log(n) time from the b-tree for every element in the $in array and returns the union of them all. Though big Oh wise for large m it seems slower than the O(n) hashset approach, its faster in practice as the disk reads are much more expensive.

Is this line of thinking correct when there is an index?

And if there isn't an index does it do the COLSCAN with a naive search or will it use a hashset to fasten the process?

Joe · Accepted Answer · 2021-04-10 00:28:54Z

1

When setting up the query, the $in expression sorts the non-regex elements in the setEqualities function:

    if (!std::is_sorted(_originalEqualityVector.begin(),
                        _originalEqualityVector.end(),
                        _eltCmp.makeLessThan())) {
        std::sort(
            _originalEqualityVector.begin(), _originalEqualityVector.end(), _eltCmp.makeLessThan());
    }

It then tests the element from each document using the contains function, which uses a binary search:

bool InMatchExpression::contains(const BSONElement& e) const {
    return std::binary_search(_equalitySet.begin(), _equalitySet.end(), e, _eltCmp.makeLessThan());
}

answered Apr 10, 2021 at 0:28

Joe

29k4 gold badges25 silver badges50 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Mongodb $in implementation and complexity

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related