Uploaded image for project: 'Core Server'
  1. Core Server
  2. SERVER-35693

Parsing of $in takes quadratic time due to O(n^2) boost::flat_set constructor

    • Type: Icon: Bug Bug
    • Resolution: Fixed
    • Priority: Icon: Critical - P2 Critical - P2
    • 3.2.21, 3.4.16, 3.6.6, 4.0.1, 4.1.1
    • Affects Version/s: 3.2.19, 3.4.9, 3.6.5, 4.0.0-rc6
    • Component/s: Querying
    • Labels:
    • Fully Compatible
    • ALL
    • v4.0, v3.6, v3.4, v3.2
    • Query 2018-07-02
    • 0

      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.

            david.storch@mongodb.com David Storch
            david.storch@mongodb.com David Storch
            0 Vote for this issue
            10 Start watching this issue