Method of building multidimensional workload-aware histograms
First Claim
1. In a database system, a method of maintaining a self-tuning histogram having a plurality of existing buckets arranged in a hierarchical manner and defined by at least two bucket boundaries that represent a range of attribute values, a bucket volume, and a bucket frequency that corresponds to a number of tuples having attribute values that fall in the bucket boundary range comprising:
- creating at least one new bucket in response to a query on the database, each new bucket having bucket boundaries corresponding to a range of tuple attribute values returned by the query and a bucket frequency corresponding to a number of tuples returned by the query;
establishing a logical relationship between the new bucket and an existing bucket such that the existing bucket is a parent bucket of the new bucket;
storing the self-tuning histogram that includes the new bucket in memory; and
wherein bucket boundaries of each new bucket fall within bucket boundaries of the parent bucket of the new bucket.
2 Assignments
0 Petitions
Accused Products
Abstract
In a database system, a method of maintaining a self-tuning histogram having a plurality of existing rectangular shaped buckets arranged in a hierarchical manner and defined by at least two bucket boundaries, a bucket volume, and a bucket frequency. At least one new bucket is created in response to a query on the database. Each new bucket is contained within at least one existing bucket and the new bucket becomes a child bucket and the existing bucket containing it becomes a parent bucket. The boundaries of each new bucket correspond to a region of the database accessed by the query and the frequency of the new bucket is a number of data records returned by the query. Buckets may be merged based on a merge criterion such as similar bucket density when the total number of buckets exceeds the predetermined budget.
35 Citations
25 Claims
-
1. In a database system, a method of maintaining a self-tuning histogram having a plurality of existing buckets arranged in a hierarchical manner and defined by at least two bucket boundaries that represent a range of attribute values, a bucket volume, and a bucket frequency that corresponds to a number of tuples having attribute values that fall in the bucket boundary range comprising:
-
creating at least one new bucket in response to a query on the database, each new bucket having bucket boundaries corresponding to a range of tuple attribute values returned by the query and a bucket frequency corresponding to a number of tuples returned by the query; establishing a logical relationship between the new bucket and an existing bucket such that the existing bucket is a parent bucket of the new bucket; storing the self-tuning histogram that includes the new bucket in memory; and wherein bucket boundaries of each new bucket fall within bucket boundaries of the parent bucket of the new bucket. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. In a database system, a method of maintaining a self-tuning histogram having a plurality of existing parent buckets arranged in a hierarchical manner and defined by at least two bucket boundaries that represent a range of attribute values, a bucket volume, and a bucket frequency that corresponds to a number of tuples having attributes that fall in the bucket boundary range, the method comprising:
-
a) examining the results of a query executed on the database; b) creating at least one candidate hole in the histogram based on the results of the query such that the candidate hole has boundaries corresponding to a range of attribute values returned by the query and a frequency corresponding to a number of tuples returned by the query; c) modifying the boundaries of each candidate hole such that the boundaries of the modified hole are completely contained within the boundaries of at least one existing parent bucket and do not partially intersect the boundaries of any existing bucket; d) creating a new child bucket that has a child frequency in the histogram corresponding to each modified hole; and e) storing the modified self-tuning histogram in one or more computer-readable media. - View Dependent Claims (9, 10, 11, 12, 13)
-
-
14. One or more computer readable media having executable instructions that, when executed, implement a method for maintaining a self-tuning histogram having a plurality of existing parent buckets arranged in a hierarchical manner and defined by at least two bucket boundaries that represent a range of attribute values, a bucket volume, and a bucket frequency that corresponds to a number of tuples having attribute values that fall in the bucket boundary range, the steps comprising:
-
a) examining the results of a query executed on the database; b) creating at least one candidate hole in the histogram based on the results of the query such that the candidate hole has boundaries corresponding to a range of attribute values returned by the query and a frequency corresponding to a number of tuples returned by the query; c) modifying the boundaries of each candidate hole such that the boundaries of the modified hole are completely contained within the boundaries of at least one existing parent bucket and do not partially intersect the boundaries of any existing bucket; and d) creating a new child bucket that has a child frequency in the histogram corresponding to each modified hole; and e) storing the modified self-tuning histogram in one or more computer-readable media. - View Dependent Claims (15, 16)
-
-
17. An apparatus for maintaining a self-tuning histogram having a plurality of existing parent buckets arranged in a hierarchical manner and defined by at least two bucket boundaries that represent a range of attribute values, a bucket volume, and a bucket frequency that corresponds to a number of tuples having attribute values that fall in the bucket boundary range comprising:
-
a) means for examining the results of a query executed on the database; b) means for creating at least one candidate hole in the histogram based on the results of the query such that the candidate hole has boundaries corresponding to a range of attribute values returned by the query and a frequency corresponding to a number of tuples returned by the query; c) means for modifying the boundaries of each candidate hole such that the boundaries of the modified hole are completely contained within the boundaries of at least one existing parent bucket and do not partially intersect the boundaries of any existing bucket; and d) means for creating a new child bucket that has a child frequency in the histogram corresponding to each modified hole.
-
-
18. An apparatus that maintains a self-tuning histogram having a plurality of existing parent buckets arranged in a hierarchical manner and defined by at least two bucket boundaries that represent a range of attribute values, a bucket volume, and bucket frequency that corresponds to a number of tuples having attribute values that fall in the bucket boundary range comprising:
-
a) a memory device that stores a database comprising multiple data records; b) a computer having one or more processing units that execute a stored computer program, said computer including a rapid access memory store; and c) an interface that couples the memory device that stores the database to the computer to allow records to be retrieved from the database;
whereind) the stored program has components including i) a component that examines the results of a query executed on the database;
ii) a component that creates at least one candidate hole in the histogram based on the results of the query such that the candidate hole has boundaries corresponding to a range of attribute values returned by the query and a frequency corresponding to a number of tuples returned by the query;
iii) a component that modifies the boundaries of each candidate hole such that the boundaries of the modified hole are completely contained within the boundaries of at least one existing parent bucket and do not partially intersect the boundaries of any existing bucket; and
iv) a component that creates a new child bucket that has a child frequency in the histogram corresponding to each modified hole.
-
-
19. For use with a database system, a histogram tuning system comprising:
-
a component that receives a histogram having at least a parent bucket; and a tuning component that iteratively populates the parent bucket with a child bucket, as a function of query results, wherein the child bucket is completely contained within the parent bucket. - View Dependent Claims (20, 21, 22, 23, 24)
-
-
25. A database histogram tuning system comprising:
-
means for receiving a bucket from a histogram; and means for iteratively populating the bucket with a child bucket, as a function of query results, such that the child bucket is fully contained within the received bucket.
-
Specification