Database query optimization apparatus and method

Abstract

A database query optimizer processes an expression in a database query, and generates therefrom an operand list and a corresponding truth table that may be represented by a list of binary characters, where the operand list and corresponding truth table represent a disjunct normal form for the expression. Each expression is stored once it is processed into its operand list and corresponding list of binary characters. New queries are processed into component expressions, and each expression is checked to see if the expression was previously processed and stored as a processed expression. If so, the operand list and list of binary characters for the previously-stored expression may be used in processing the current expression. If there is no previously-stored expression that corresponds to the current expression, the previously-stored expressions are checked to see if any correspond to a complement of the current expression. If so, a new expression is easily constructed for the current expression by retrieving the list of binary characters that correspond to the complement expression, and inverting the bits in the list of binary characters. If there is no previously-stored expression that corresponds to the current expression or its complement, an operand list and corresponding list of binary characters are generated for the current expression. Logical operations between predicates in a query may be performed by performing mathematical operations on the lists of binary characters corresponding to each predicate expression. The end result is an operand list and corresponding list of binary characters that represents the entire expression in a query.