Generating optimal plans for Boolean expressions

We present an algorithm that produces optimal plans to evaluate arbitrary Boolean expressions possibly containing conjunctions and disjunctions. The complexity of our algorithm is O(n3n), where n is the number of simple predicates in the Boolean expression. This complexity is far lower than that of Reinwald and Soland's algorithm (O(22(n))). This lower complexity allows us to optimize Boolean expressions with up to 16 predicates in a reasonable time. Further, opposed to many existing approaches, our algorithm fulfills all requirements necessary in the context of main memory database systems. We then use this algorithm to (1) determine the optimization potential inherent in Boolean expressions and (2) evaluate the plan quality of two heuristics proposed in the literature