Elimination of common subexpressions in complex database queries

Abstract

A database engine receives a human-readable database query that includes a plurality of conditional expressions. The database engine parses the database query to build an operator tree that includes a subtree corresponding to each of the conditional expressions. The database engine identifies a subexpression that appears in two or more of the conditional expressions. The subexpression is executed conditionally. The database engine hoists the subexpression outside of the conditional expression so that it is executed unconditionally. The database engine modifies the operator tree to specify computation of a value for the subexpression a first time and to reuse the computed value when the subexpression is subsequently encountered. The database engine executes the modified operator tree to form a result set corresponding to the database query, thereby evaluating the subexpression only a single time for each row of input data and returns the result set.

What is claimed is: 
     
       1. A database engine, comprising:
 one or more computing devices, each having one or more processors and memory, wherein the memory stores one or more programs configured for execution by the one or more processors, the one or more programs comprising instructions for: 
 receiving a human-readable database query that includes a plurality of conditional expressions; 
 parsing the database query to build an operator tree that includes a subtree corresponding to each of the conditional expressions; 
 identifying a subexpression that appears in two or more of the conditional expressions, wherein the subexpression is executed conditionally; 
 hoisting the subexpression outside of the two or more conditional expressions so that it is executed unconditionally; 
 modifying the operator tree to specify computation of a value for the subexpression a first time and to reuse the computed value when the subexpression is subsequently encountered; 
 executing the modified operator tree to form a result set corresponding to the database query, thereby evaluating the subexpression only a single time for each row of input data; and 
 returning the result set. 
 
     
     
       2. The database engine of  claim 1 , further comprising:
 mapping the subexpression to a register; and 
 for each row of input data:
 computing a respective value for the subexpression a first time; 
 storing the respective value in the register; and 
 retrieving the respective value from the register when data for the subexpression is needed a second time. 
 
 
     
     
       3. The database engine of  claim 1 , further comprising:
 determining that a second subexpression is equivalent to the subexpression; and 
 further modifying the operator tree to reuse the computed value when the second subexpression is subsequently encountered; 
 wherein executing the modified operator tree comprises reusing the computed value for the subexpression as a value for the second subexpression. 
 
     
     
       4. The database engine of  claim 3 , wherein determining that the second subexpression and the subexpression are equivalent comprises using an equivalence function to recursively check that the subexpression and the second expression apply a same expression type to a same set of input arguments. 
     
     
       5. The database engine of  claim 4 , wherein the equivalence function accounts for equivalence of operations that are associative and/or commutative. 
     
     
       6. The database engine of  claim 1 , wherein the subexpression is nested inside of a conditional expression. 
     
     
       7. The database engine of  claim 1 , wherein hoisting the subexpression outside of the conditional expression comprises caching the subexpression to an outer consumer context, thereby making the subexpression available for reuse. 
     
     
       8. The database engine of  claim 1 , wherein:
 the operator tree has a plurality of alternative branches; and 
 the hoisting is performed in accordance with a determination that the subexpression will be computed no matter which alternative branch of the plurality of alternative branches is executed during execution of the operator tree. 
 
     
     
       9. The database engine of  claim 1 , wherein:
 the operator tree has a plurality of alternative branches; and 
 the hoisting is performed in accordance with a determination that the subexpression is accessed for at least a plurality of the alternative branches. 
 
     
     
       10. The database engine of  claim 1 , wherein executing the operator tree comprises compiling the operator tree to form machine code and executing the machine code. 
     
     
       11. The database engine of  claim 1 , wherein machine code generated for the modified operator tree has fewer instructions than machine code generated for the operator tree built from parsing the database query. 
     
     
       12. A method of retrieving data from a database, comprising:
 at a computer system having one or more computing devices, each computing device having one or more processors and memory storing one or more programs configured for execution by the one or more processors: 
 receiving a human-readable database query that includes a plurality of conditional expressions; 
 parsing the database query to build an operator tree that includes a subtree corresponding to each of the conditional expressions; 
 identifying a subexpression that appears in two or more of the conditional expressions, wherein the subexpression is executed conditionally; 
 hoisting the subexpression outside of the two or more conditional expressions so that it is executed unconditionally; 
 modifying the operator tree to specify computation of a value for the subexpression a first time and to reuse the computed value when the subexpression is subsequently encountered; 
 executing the modified operator tree to form a result set corresponding to the database query, thereby evaluating the subexpression only a single time for each row of input data; and 
 returning the result set. 
 
     
     
       13. The method of  claim 12 , further comprising:
 mapping the subexpression to a register; and 
 for each row of input data:
 computing a respective value for the subexpression a first time; 
 storing the respective value in the register; and 
 retrieving the respective value from the register when data for the subexpression is needed a second time. 
 
 
     
     
       14. The method of  claim 12 , further comprising:
 determining that a second subexpression is equivalent to the subexpression; and 
 further modifying the operator tree to reuse the computed value when the second subexpression is subsequently encountered; 
 wherein executing the modified operator tree comprises reusing the computed value for the subexpression as a value for the second subexpression. 
 
     
     
       15. The method of  claim 14 , wherein determining that the second subexpression and the subexpression are equivalent comprises using an equivalence function to recursively check that the subexpression and the second expression apply a same expression type to a same set of input arguments. 
     
     
       16. The method of  claim 15 , wherein the equivalence function accounts for equivalence of operations that are associative and/or commutative. 
     
     
       17. The method of  claim 12 , wherein:
 the operator tree has a plurality of alternative branches; and 
 the hoisting is performed in accordance with a determination that the subexpression will be computed no matter which alternative branch of the plurality of branches is executed during execution of the operator tree. 
 
     
     
       18. The method of  claim 12 , wherein:
 the operator tree has a plurality of alternative branches; and 
 the hoisting is performed in accordance with a determination that the subexpression is accessed for at least a plurality of the alternative branches. 
 
     
     
       19. The method of  claim 12 , wherein executing the operator tree comprises compiling the operator tree to form machine code and executing the machine code. 
     
     
       20. A non-transitory computer readable storage medium storing one or more programs configured for execution by a computer system having one or more processors and memory, the one or more programs comprising instructions for:
 receiving a human-readable database query that includes a plurality of conditional expressions; 
 parsing the database query to build an operator tree that includes a subtree corresponding to each of the conditional expressions; 
 identifying a subexpression that appears in two or more of the conditional expressions, wherein the subexpression is executed conditionally; 
 hoisting the subexpression outside of the two or more conditional expressions so that it is executed unconditionally; 
 modifying the operator tree to specify computation of a value for the subexpression a first time and to reuse the computed value when the subexpression is subsequently encountered; 
 executing the modified operator tree to form a result set corresponding to the database query, thereby evaluating the subexpression only a single time for each row of input data; and 
 returning the result set.