Simplify boolean expressions before feeding them to the optimizer

XMLWordPrintableJSON

    • Query Optimization
    • Fully Compatible
    • None
    • 3
    • None
    • None
    • None
    • None
    • None
    • None

      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

        1.
        		 Implement Quine-McCluskey algorithm SERVER-76938 Sub-task Closed Alexander Ignatyev  

            Assignee:
            Alexander Ignatyev
            Reporter:
            Alexander Ignatyev
            Votes:
            0 Vote for this issue
            Watchers:
            10 Start watching this issue

              Created:
              Updated:
              Resolved: