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

    XMLWordPrintable

    Details

    • Type: Bug
    • Status: Closed
    • Priority: Critical - P2
    • Resolution: Fixed
    • Affects Version/s: 3.2.19, 3.4.9, 3.6.5, 4.0.0-rc6
    • Fix Version/s: 3.2.21, 3.4.16, 3.6.6, 4.0.1, 4.1.1
    • Component/s: Querying
    • Labels:
      None
    • Backwards Compatibility:
      Fully Compatible
    • Operating System:
      ALL
    • Backport Requested:
      v4.0, v3.6, v3.4, v3.2
    • Sprint:
      Query 2018-07-02
    • Case:
    • Linked BF Score:
      0

      Description

      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:

      https://svn.boost.org/trac10/ticket/13140

      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.

        Attachments

          Issue Links

            Activity

              People

              • Votes:
                0 Vote for this issue
                Watchers:
                11 Start watching this issue

                Dates

                • Created:
                  Updated:
                  Resolved: