[SERVER-77343] Boolean simplification benchmark Created: 22/May/23  Updated: 16/Nov/23  Resolved: 16/Nov/23

Status: Closed
Project: Core Server
Component/s: None
Affects Version/s: None
Fix Version/s: 7.3.0-rc0

Type: Task Priority: Major - P3
Reporter: Alexander Ignatyev Assignee: Alexander Ignatyev
Resolution: Fixed Votes: 0
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Issue split
split from SERVER-75079 Simplify boolean expressions before f... Closed
Backwards Compatibility: Fully Compatible
Sprint: 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
Participants:

 Description   

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.



 Comments   
Comment by Githook User [ 16/Nov/23 ]

Author:

{'name': 'Alexander Ignatyev', 'email': 'alexander.ignatyev@mongodb.com', 'username': 'aligusnet'}

Message: SERVER-77343 Add Boolean simplification benchmarks (#1059)

SERVER-77343 Add Boolean simplification benchmarks

To measure performance of Boolean expressions which can be simplified by
the Boolean Simplifier.
Branch: master
https://github.com/mongodb/genny/commit/a829edcf4e6717d5bbedaf755245c207c431b8d0

Generated at Thu Feb 08 06:35:14 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.