Database query optimization and cost estimation
View Patent ↗Described are systems and methods relating to database query optimization and query cost estimation. The approach is described in the context of searching balanced and semi-balanced tree indexes such as B-trees, B+ trees, and R-B trees. The described approach may be used for both simple and composite queries, and the described approach may be used for relational queries, i.e., where a variable is less than or greater than a certain value and the database is being used to find the set of records that satisfy the relation. Further, the described approach may be used for generalized N-ary tree queries and cost estimations.
1. A system for optimizing database queries and estimating query costs, the system comprising:
a computer-readable medium having a tree indexed data structure comprising nodes, the computer-readable medium operable to store a computer-readable query optimizer; and
a processor operable to execute the query optimizer for computing a cost estimate ratio associated with performing a query based at least in part on a key value, the cost estimate ratio comprising a first number of nodes in the tree indexed data structure having values less than the key value versus a second number of nodes in the tree indexed data structure having values more than the key value, and further operable to compute a cost estimation by normalizing the cost estimate ratio relative to a total size of the tree indexed data structure,
wherein the tree indexed data structure comprises a hierarchical structure with a root node and a plurality of child nodes, and further wherein the tree indexed data structure is traversed with the key value to compute the cost estimate ratio associated with performing the query based at least in part on the key value.
2. A system of claim 1 , wherein the nodes comprise stored values that are compared to the key value when the tree indexed data structure is traversed.
3. A system of claim 2 , wherein the processor traverses the tree indexed data structure by comparing the key value to the stored values, starting at the root node and traversing the hierarchical structure until a compared node's stored value matches the key value.
4. A system of claim 3 , wherein the processor traverses to a left node at a lower level in the hierarchical structure if the stored value of a compared node is less than the key value and traverses to a right node at the lower level if the stored value of the compared node is greater than the key value.
5. A system of claim 4 , wherein the processor is further operable to compute a first running total of nodes with values less than the key value and a second running total of nodes with values greater than the key value, and estimates a number of matches present in a left sub-tree and in a right sub-tree for a particular query based on the first and second running totals.
6. A system of claim 5 , wherein the cost estimate ratio is based on the first and second running totals.
7. A system of claim 6 , wherein the processor computes the cost estimation using the following formulas:
estimate
of
number
of
nodes
with
values
less
than
the
key
=
the
first
number
of
nodes
×
the
total
size
of
the
tree
index
first
running
total
+
second
running
total
;
and
estimate
of
number
of
nodes
with
values
greater
than
the
key
=
the
second
number
of
nodes
×
total
size
of
the
tree
index
first
running
total
+
second
running
total
.
8. A system of claim 1 , wherein the values of each node are unique.
9. A system of claim 8 , wherein the processor is further operable to append a unique value to an end of a value in a node to allow for the values of each node to be unique.
10. The system of claim 9 , wherein appending the unique value results in a substantially flattened tree.
11. A system of claim 1 , where the tree indexed data structure is a balanced tree indexed data structure.
12. A system of claim 1 , where in the tree indexed data structure is a semi-balanced tree indexed data structure.
13. A system of claim 1 , wherein the tree indexed data structure is an in-memory database structure.
14. A method for optimizing database queries and estimating query costs, the method comprising:
executing, using a computer processor, a computer-executable query optimizer stored in a computer-readable medium, the query optimizer operable for:
computing a cost estimate ratio associated with performing a query based at least in part on a key value, the cost estimate ratio comprising a first number of nodes in a tree indexed data structure having values less than the key value versus a second number of nodes in the tree indexed data structure having values more than the key value, and
computing a cost estimation by normalizing the cost estimate ratio relative to a total size of the tree indexed data structure,
wherein the tree indexed data structure comprises a hierarchical structure with a root node and a plurality of child nodes, and further wherein the tree indexed data structure is traversed with the key value to compute the cost estimate ratio associated with performing the query based at least in part on the key value.
15. The method of claim 14 , wherein the nodes comprise stored values, and further comprising traversing the tree indexed data structure by comparing the stored values to the key value.
16. A method of claim 15 , further comprising:
traversing, using the processor, the tree indexed data structure by comparing the key value to the stored values, starting at the root node and traversing the hierarchical structure until a compared node's stored value matches the key value.
17. A method of claim 16 , further comprising:
traversing to a left node at a lower level in the hierarchical structure if the stored value of a compared node is less than the key value; and
traversing to a right node at the lower level if the stored value of the compared node is greater than the key value.
18. A method of claim 17 , further comprising:
computing a first running total of nodes with values less than the key value and a second running total of nodes with values greater than the key value; and
estimating a number of matches present in a left sub-tree and in a right sub-tree for a particular query based on the first and second running totals.
19. A method of claim 18 , wherein the cost estimate ratio is based on the first and second running totals.
20. A method of claim 19 , wherein computing the cost estimate uses the following formulas:
estimate
of
number
of
nodes
with
values
less
than
the
key
=
the
first
number
of
nodes
×
the
total
size
of
the
tree
index
first
running
total
+
second
running
total
;
and
estimate
of
number
of
nodes
with
values
greater
than
the
key
=
the
second
number
of
nodes
×
total
size
of
the
tree
index
first
running
total
+
second
running
total
.