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

Simplify boolean expressions before feeding them to the optimizer

    XMLWordPrintableJSON

Details

    • Query Optimization

    Description

      As a part of a Skunkworks project we implemented a Boolean expression simplifier which demonstrated good results on some non-trivial Boolean expressions.

      For example,
      given the following indexes: {d: 1, b: 1}, {a: 1}

      and the following query

      {
      		 
          '$and': [
      		 
              {b: 0},
      		 
              {
      		 
                  '$or': [
      		 
                      {a: 0},
      		 
                      {
      		 
                          '$and': [
      		 
                              {c: {'$in': [34, 45]}},
      		 
                              {c: {'$nin': [34, 45]}},
      		 
                          ]
      		 
                      }
      		 
                  ]
      		 
              },
      		 
          ]
      		 
      };

      the optimizer chose a full collection scan plan.

      The boolean expression simplifier can simplify this filter just to the following one:

      {a: 0, b: 0}

      given this filter the optimizer chose much more effective index scan on {a: 1} plan.

      The proposed in the Skunkworks project implementation does not depend on any optimizer and can be used for the classic one as well for the Bonsai. This ticket proposes to add the simplification for the classic optimizer. Then we can reuse the implementation of this ticket for the Bonsai: https://jira.mongodb.org/browse/SERVER-74879

      Attachments

        Issue Links

          is related to

          Task - A task that needs to be done. SERVER-76509 Enable booleanExpressionSimplifier flag for Bonsai integration tests

          • Major - P3 - Major loss of function.
          • Open

          Improvement - An improvement or enhancement to an existing feature or task. SERVER-74879 [CQF] Boolean minimization for BoolExpr based on Quine-McCluskey simplification

          • Major - P3 - Major loss of function.
          • Open
          related to

          Bug - A problem which impairs or prevents the functions of the product. SERVER-60373 Duplicate predicates in query plan for time-series collection

          • Minor - P4 - Minor loss of function, or other problem where easy workaround is present.
          • Closed

          Task - A task that needs to be done. SERVER-78962 Check on feasibility to perform boolean simplification before parameterization

          • Minor - P4 - Minor loss of function, or other problem where easy workaround is present.
          • Backlog

          Improvement - An improvement or enhancement to an existing feature or task. SERVER-22857 eliminate redundant conditions/clauses from query

          • Major - P3 - Major loss of function.
          • Backlog

          Improvement - An improvement or enhancement to an existing feature or task. SERVER-35018 remove unnecessary FETCH from plan when fetch tests condition that's implied by indexed condition

          • Major - P3 - Major loss of function.
          • Backlog

          Improvement - An improvement or enhancement to an existing feature or task. SERVER-31360 MatchExpression::getOptimizer() for $or/$and should collapse equivalent clauses

          • Minor - P4 - Minor loss of function, or other problem where easy workaround is present.
          • Backlog
          split to

          Task - A task that needs to be done. SERVER-77343 Boolean simplification benchmark

          • Major - P3 - Major loss of function.
          • Open

          Task - A task that needs to be done. SERVER-81139 Stop Boolean expression simplification if it explodes the expression in size

          • Major - P3 - Major loss of function.
          • Open

          Task - A task that needs to be done. SERVER-76939 Implement Quine-McCluskey algorithm

          • Major - P3 - Major loss of function.
          • Closed

          Task - A task that needs to be done. SERVER-76940 Implement Petrick's method

          • Major - P3 - Major loss of function.
          • Closed

          Task - A task that needs to be done. SERVER-77470 Optimize the Petrick's method implementation.

          • Major - P3 - Major loss of function.
          • Closed

          Task - A task that needs to be done. SERVER-77670 Implement DNF converter for boolean expressions

          • Major - P3 - Major loss of function.
          • Closed

          Task - A task that needs to be done. SERVER-79018 Implement MatchExpression hasher

          • Major - P3 - Major loss of function.
          • Closed

          Task - A task that needs to be done. SERVER-79314 Implement additional pipeline Expression unit tests

          • Major - P3 - Major loss of function.
          • Closed

          Activity

            People

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

              Dates

                Created:
                Updated: