Reducing the domain of a subquery by retrieving constraints from the outer query
First Claim
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 subquery;
parsing the database query to build an operator tree, which includes a subtree corresponding to the subquery;
estimating a cardinality of rows in database tables specified in the subtree;
estimating a fraction of the estimated cardinality of rows that do not satisfy a filter condition specified in one or more subsequent operations in the operator tree;
in accordance with a determination that the estimated fraction exceeds a first threshold, inserting, into the subtree, a domain constraint that includes an early-probe operator that specifies comparing rows generated from execution of the subtree to a hash table of a second subtree in the operator tree, the domain constraint corresponding to the filter condition, thereby forming a modified operator tree in which execution of the subtree restricts rows retrieved according to the filter condition;
executing the modified operator tree to form a final result set corresponding to the database query; and
returning the final result set.
1 Assignment
0 Petitions
Accused Products
Abstract
A database engine receives a human-readable database query that includes a subquery, and parses the database query to build an operator tree. The operator tree includes a subtree corresponding to the subquery. The database engine estimates the number of rows that will accessed when the subtree is executed and estimates the fraction of the cardinality of rows that will be filtered out by subsequent operations in the operator tree. In accordance with a determination that the estimated fraction exceeds a first threshold, the database engine inserts a domain constraint into the subtree that restricts rows retrieved by execution of the subtree, thereby forming a modified operator tree. The database engine executes the modified operator tree to form a final result set corresponding to the database query and returns the final result set.
-
Citations
18 Claims
-
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 subquery; parsing the database query to build an operator tree, which includes a subtree corresponding to the subquery; estimating a cardinality of rows in database tables specified in the subtree; estimating a fraction of the estimated cardinality of rows that do not satisfy a filter condition specified in one or more subsequent operations in the operator tree; in accordance with a determination that the estimated fraction exceeds a first threshold, inserting, into the subtree, a domain constraint that includes an early-probe operator that specifies comparing rows generated from execution of the subtree to a hash table of a second subtree in the operator tree, the domain constraint corresponding to the filter condition, thereby forming a modified operator tree in which execution of the subtree restricts rows retrieved according to the filter condition; executing the modified operator tree to form a final result set corresponding to the database query; and returning the final result set. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. 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 subquery; parsing the database query to build an operator tree, which includes a subtree corresponding to the subquery; estimating a cardinality of rows in database tables specified in the subtree; estimating a fraction of the estimated cardinality of rows that do not satisfy a filter condition specified in one or more subsequent operations in the operator tree; in accordance with a determination that the estimated fraction exceeds a first threshold, inserting, into the subtree, a domain constraint that includes an early-probe operator that specifies comparing rows generated from execution of the subtree to a hash table of a second subtree in the operator tree, the domain constraint corresponding to the filter condition, thereby forming a modified operator tree in which execution of the subtree restricts rows retrieved according to the filter condition; executing the modified operator tree to form a final result set corresponding to the database query; and returning the final result set. - View Dependent Claims (12, 13, 14, 15, 16, 17)
-
-
18. 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 subquery; parsing the database query to build an operator tree, which includes a subtree corresponding to the subquery; estimating a cardinality of rows in database tables specified in the subtree; estimating a fraction of the estimated cardinality of rows that do not satisfy a filter condition specified in one or more subsequent operations in the operator tree; in accordance with a determination that the estimated fraction exceeds a first threshold, inserting, into the subtree, a domain constraint that includes an early-probe operator that specifies comparing rows generated from execution of the subtree to a hash table of a second subtree in the operator tree, the domain constraint corresponding to the filter condition, thereby forming a modified operator tree in which execution of the subtree restricts rows retrieved according to the filter condition; executing the modified operator tree to form a final result set corresponding to the database query; and returning the final result set.
-
Specification