Time-optimal short-circuit evaluation of boolean expressions

Boolean expressions are an important constituent of programming languages and query languages for data base systems. Evaluation of boolean expressions by short-circuiting is a familiar method which skips over the evaluation of boolean primitives no longer relevant to the value of the expression as a whole. It often results in an attractive optimization of the execution time, both in programming languages [1,4,5] and in data base query languages [2,3]. However, commutativity and associativity of “and” and “or” operations, which can allow further optimization, is not taken into account in previous works. In this paper we focus on short-circuit evaluation of boolean expressions and present a method of realizing time-optimal short-circuit evaluation by reordering the evaluation sequence. In general, the time of short-circuit evaluation varies between the cases when it yields “true” and “false”. We first derive formulae to estimate the expected time and true/false probability of short-circuit evaluation in each case, given a boolean expression and an evaluation time and true/false probability for each boolean primitive of the expression. Using these formulae, we present a theorem to minimize the expected time of short-circuit evaluation by reordering the evaluation sequence of boolean subexpressions, based on laws of commutativity and associativity of “and” and “or” operations. The theorem utilizes the concept of dynamic programming. An early idea of this paper appeared in [7]; detailed discussions can be found in [6].