Self-tuning histogram and database modeling

• US 6,460,045 B1
• Filed: 03/15/1999
• Issued: 10/01/2002
• Est. Priority Date: 03/15/1999
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Aboulnaga, Ashraf, Chaudhuri, Surajit
• Primary Examiner(s): Vu, Kim
• Assistant Examiner(s): Ly, Anh
• Application Number:
  US09/268,589
• Time in Patent Office: 1,296 Days
• Field of Search: 707/1-10, 707/101, 707/102, 707/103
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24545 Selectivity estimation or determination
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

Building histograms by using feedback information about the execution of query workload rather than by examining the data helps reduce the cost of building and maintaining histograms. A method of maintaining self-tuning histograms updates histograms based on feedback about the execution of a user query. A histogram may be initialized using an assumption of uniform distribution of data or by combining existing histograms. A histogram tuner accesses and estimated result in response to a user query generated by using the histogram. The histogram tuner calculates an estimation error based on the result of the user query and the estimated result. The frequencies of histogram buckets are refined based on the estimation error. The bucket bounds of the histogram are restructured based on the refined frequencies. The method may be performed on-line after a user query or off-line by accessing a workload log. By updating a histogram without accessing the database, the cost of building and maintaining histograms is significantly reduced.

Claims

1. In a database system, a method of maintaining a self-tuning histogram having a plurality of buckets defined by at least two bucket boundaries and a bucket frequency comprising:

(a) identifying the histogram;

(b) using the histogram to generate an estimated result size in response to a user query;

(c) calculating an estimation error based on the estimated result size and the size of the result of the user query;

(d) dividing the estimation error into one or more portions;

(e) applying the portions to the bucket frequencies of one or buckets to modify the bucket frequencies.

2. The method of claim 1 wherein the step of applying the estimation error portions comprises applying the portions to the bucket frequencies of the one or more buckets in proportion to their relative bucket frequency.

3. The method of claim 1 wherein the step of applying the estimation error portions comprises applying the portions to the bucket frequencies of buckets used to generate the estimated result size.

4. The method of claim 1 wherein the step of identifying the histogram comprises initializing the histogram.

5. The method of claim 4 wherein the step of initializing the histogram comprises assigning substantially uniform bucket frequencies and bucket boundaries to the buckets.

6. The method of claim 4 wherein the step of initializing the histogram comprises combining a plurality of existing histograms.

7. The method of claim 1 wherein the self-tuning histogram is multi-dimensional.

8. A method of building and maintaining a self-tuning histogram having a plurality of buckets each defined by at least two bucket boundaries and a bucket frequency comprising the steps of:

a) initializing the histogram;

b) using the histogram to generate an estimated result size in response to a user query;

c) calculating an estimation error based on the size of the result of the user query and the estimated result size;

d) modifying the frequency of the buckets by applying a damping factor to the estimation error, dividing the estimation error into one or more portions and applying the portions to the bucket frequencies of the buckets used to generate the estimation error in proportion to their relative bucket frequency; and

e) redefining the bucket boundaries of one or more of the buckets by merging adjacent buckets having relatively similar frequencies into single buckets to free buckets, selecting buckets belonging to a set of buckets having the highest frequency to be split, and splitting the selected buckets into a plurality of buckets such that the total number of buckets remains constant.

9. The method of claim 8 wherein the step of merging buckets is performed by repeatedly scanning the histogram buckets and finding adjacent buckets having the minimum difference in frequencies and merging the buckets if the difference in frequencies is below a predetermined threshold.

10. The method of claim 8 wherein the self-tuning histogram is multi-dimensional.

11. The method of claim 8 wherein the step of initializing the histogram comprises assigning uniform frequencies and boundaries to the buckets.

12. The method of claim 8 wherein the step of initializing the histogram comprises combining a plurality of existing histograms.

13. The method of claim 8 wherein the step of modifying the frequency of the buckets is performed immediately following an execution of user query.

14. The method of claim 8 wherein the steps of generating an estimated result size and calculating an estimation error are performed by accessing a log of stored user queries and corresponding result sizes.

15. The method of claim 8 wherein the step of redefining the bucket boundaries comprises merging adjacent buckets when the total number of buckets reaches a predetermined limit on the number of buckets.

16. The method of claim 8 wherein the step of modifying the bucket frequencies is performed when a predetermined minimum estimation error has been observed.

17. A method of building and maintaining an n dimensional self-tuning histogram having a plurality of buckets arranged in a grid, each bucket defined by at least four grid partitions and a bucket frequency, the histogram being defined by n scales, one scale for each dimension, and an n dimensional frequency matrix, each of the scales defining the partitions of the frequency matrix which divide the frequency matrix into a plurality of (n−

1) dimensional slices of the frequency matrix comprising the steps of;

a) initializing the histogram;

b) using the histogram to generate an estimated result size in response to a user query;

c) calculating an estimation error based on the size of the result of the user query and the estimated result size;

d) modifying the frequency of the buckets in the frequency matrix by dividing the estimation error into one or more portions and applying the portions to the bucket frequencies of the buckets used to generate the estimation error in proportion to their relative bucket frequency; and

e) changing the scales of the histogram in at least one dimension to redefine the grid partitions by merging adjacent slices of the frequency matrix having relatively similar frequencies to free buckets, selecting slices of the frequency matrix belonging to a set of slices having the highest marginal frequency to be split, and splitting the selected slices into a plurality of slices such that the total number of buckets remains constant.

18. The method of claim 17 wherein the step of initializing the histogram comprises assigning uniform frequencies and partitions to the frequency matrix.

19. The method of claim 17 wherein the step of initializing the histogram comprises combined a plurality existing histograms.

20. The method of claim 19 wherein the step of merging adjacent slices is performed by repeatedly scanning the histogram buckets and finding adjacent slices having the minimum difference in frequencies between corresponding buckets and merging the slices if the difference in frequencies is below a predetermined threshold.

21. The method of claim 19 wherein the steps are performed immediately following an execution of user query.

22. The method of claim 19 wherein the steps are performed by accessing a log of stored user queries and corresponding result sizes.

23. A computer-readable medium having computer executable instructions for performing steps for maintaining a self-tuning histogram in database wherein user queries are executed on the database to return query results, the method comprising:

(a) identifying a self-tuning histogram having a plurality of buckets defined by at least two bucket boundaries and a bucket frequency; and

(b) updating the histogram based on the results of an executed query against the database by using the histogram to generate an estimated result size in response to a user query, calculating an estimation error based on the size of the result of the user query and the estimated result size, and updating the histogram based on the estimation error.

24. The computer readable medium of claim 23 wherein the step of updating the histogram comprises modifying the bucket frequency of one or more of the buckets based on the estimation error.

25. The computer readable medium of claim 24 wherein the step of modifying the bucket frequency of the one or more buckets comprises:

I) dividing the estimation error into one or more portions; and

II) applying the portions to the bucket frequencies of the buckets used to generate the estimated result.

26. The computer readable medium of claim 24 wherein the step of modifying the bucket frequency of the one or more buckets comprises:

I) dividing the estimation error into one or more portions; and

II) applying the portions to bucket frequencies of the buckets in proportion to their relative bucket frequency.

27. The computer readable medium of claim 23 wherein the step of identifying the histogram comprises initializing the histogram.

28. The computer readable medium of claim 27 wherein the step of initializing the histogram comprises assigning substantially uniform bucket frequencies and bucket boundaries to the buckets.

29. The computer readable medium of claim 23 wherein the self-tuning histogram is multi-dimensional.

30. The computer readable medium of claim 23 additionally including computer readable instructions for redefining one or more bucket boundaries based on bucket frequencies.

31. The computer readable medium of claim 30 wherein the step of redefining the one or more bucket boundaries comprises splitting one or more buckets that meet a split criteria into a plurality of buckets.

32. The computer readable medium of claim 31 wherein the step of redefining the one or more bucket boundaries comprises merging one or more sets of adjacent buckets that meet a merge criteria.

33. The computer readable medium of claim 32 wherein the merge criteria comprises having a bucket frequency relatively similar to the bucket frequency of adjacent buckets.

34. The computer readable medium of claim 32 wherein the step of merging buckets generates free buckets for splitting buckets.

35. The computer readable medium of claim 34 wherein the step of splitting buckets comprises allocating freed buckets to one or more buckets in proportion to their relative bucket frequency.

36. The computer readable medium of claim 31 wherein the split criteria comprises belonging to a set of buckets having the highest bucket frequencies.

37. The computer readable medium of claim 31 wherein the step of redefining one or more bucket boundaries is performed such that the total number of buckets remains constant.

38. An apparatus for maintaining a self-tuning histogram in database wherein user queries are executed on the database to return query results, and wherein the histogram has a plurality of buckets defined by at least two bucket boundaries and a bucket frequency comprising:

a) means for refining the bucket frequencies based on the results of an executed query against the database;

b) means for redefining one or more of the bucket boundaries based on the bucket frequencies comprising means for calculating an estimation error based on the size of a result of a user query and an estimated result size estimated using the histogram; and

wherein the means for refining refines the frequencies by distributing the estimation error amongst bucket frequencies.

39. The apparatus of claim 38 wherein the means for redefining the bucket boundaries comprises means for merging one or more sets of adjacent buckets having relatively similar bucket frequencies and means for splitting buckets belong to a set of buckets having a relatively high bucket frequency into a plurality of buckets.

40. An apparatus for maintaining a self-tuning histogram in database wherein user queries are executed on the database to return query results, and wherein the histogram has a plurality of buckets defined by at least two bucket boundaries and a bucket frequency comprising:

a) a memory device for storing a database comprising multiple data records;

b) a computer having one or more processing units for executing a stored computer program, said computer including a rapid access memory store; and

c) an interface for coupling the memory device for storing the database to the computer to allow records to be retrieved from the database;

wherein

d) the computer executing a stored program having software components including i) a component for providing a statistical model of the data distribution in the form of a self-tuning histogram having a plurality of buckets defined by at least two bucket boundaries and a bucket frequency;

ii) a component for refining the bucket frequencies based on the results of an executed query against the database comprising a component for determining an estimation error based on the result size of a user query and an estimated result size as determined by the statistical model; and

iii) a component for redefining at least one bucket boundary based on the bucket frequencies by applying the estimation error to the bucket frequencies.

41. The apparatus of claim 40 wherein the component for redefining the bucket boundaries further comprises a component for merging one or more sets of adjacent buckets that have similar bucket frequencies and a component for splitting one or more buckets belonging to a set of having relatively high bucket frequency into a plurality of buckets.