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

Boolean simplification benchmark

    • Type: Icon: Task Task
    • Resolution: Fixed
    • Priority: Icon: Major - P3 Major - P3
    • 7.3.0-rc0
    • Affects Version/s: None
    • Component/s: None
    • None
    • Fully Compatible
    • QO 2023-05-29, QO 2023-06-12, QO 2023-06-26, QO 2023-07-10, QO 2023-07-24, QO 2023-08-07, QO 2023-08-21, QO 2023-09-04, QO 2023-09-18, QO 2023-10-02, QO 2023-10-16, QO 2023-10-30, QO 2023-11-13, QO 2023-11-27

      Implement a benchmark of the entire process starting with an unsimplified MatchExpression and ending with a simplified MatchExpression: the entire simplifier encompassing conversion to DNF, finding prime implicants by Quine-McCluskey, Petrick's, and restoring the MatchExpression representation from maxterm/minterm bitsets. In doing so we want to answer two questions:

      • Given an expression that is already in DNF, how does the performance scale as a function of the number of minterms and the number of actual input variables?
      • Given an expression that is not already in DNF, how much does the explosion in expression size due to DNF normalization hurt us?

      Based on what we find, in a future patch we might end up implementing a limit such that we bail out of boolean simplification if either the number of input variables (that is, leaf predicates with a unique hash) is too high, or if we generate too many minterms during conversion to DNF.

            Assignee:
            alexander.ignatyev@mongodb.com Alexander Ignatyev
            Reporter:
            alexander.ignatyev@mongodb.com Alexander Ignatyev
            Votes:
            0 Vote for this issue
            Watchers:
            4 Start watching this issue

              Created:
              Updated:
              Resolved: