Improving MongoDB Queries by Simplifying Boolean Expressions

This post details the implementation of a Boolean expression simplification engine for MongoDB queries. It describes the challenges of simplifying Abstract Syntax Trees (ASTs) and introduces a modified Quine–McCluskey algorithm combined with Petrick's method, utilizing an efficient bitset representation. The post also elaborates on the specific logical semantics of MongoDB Query Language (MQL), particularly how negation and missing values are handled, and proves that Boolean algebra laws hold for MQL negations, ensuring the correctness of the simplification process.