Compressing database workloads

• US 6,912,547 B2
• Filed: 06/26/2002
• Issued: 06/28/2005
• Est. Priority Date: 06/26/2002
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chaudhuri, Surajit, Agrawal, Sanjay, Narasayya, Vivek, Gupta, Ashish Kumar
• Primary Examiner(s): Rones, Charles
• Application Number:
  US10/180,667
• Publication Number:
  US 20040002954A1
• Time in Patent Office: 1,098 Days
• Field of Search: 707/104.1, 706/917, 709/224, 703/21
• US Class Current: 707/693
• CPC Class Codes: G06F 16/217 Database tuning G06F16/2282 takes precedence; database performance monitoring G06F11/3409
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries
• CPC Class Codes: Y10S 706/917 Communication
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

Relational database applications such as index selection, histogram tuning, approximate query processing, and statistics selection have recognized the importance of leveraging workloads. Often these applications are presented with large workloads, i.e., a set of SQL DML statements, as input. A key factor affecting the scalability of such applications is the size of the workload. The invention concerns workload compression which helps improve the scalability of such applications. The exemplary embodiment is broadly applicable to a variety of workload-driven applications, while allowing for incorporation of application specific knowledge. The process is described in detail in the context of two workload-driven applications: index selection and approximate query processing.

Claims

1. A computer system for evaluating a workload having a plurality of statements based on a application that uses the workload comprising:

a database management system including a log that contains an initial workload W containing a plurality of statements;

an evaluation component that determines a distance function for pairs of statements within the workload which returns an estimate of the loss in quality for an application if a first statement is discarded from the workload but a second statement of the pair of statements is retained in a compressed workload; and

a search component that finds a compressed workload W′

by evaluating the distance function for pairs of statements to produce a compressed workload having fewer statements than the initial workload W.

2. The system of claim 1 wherein the search component establishes a limit Δ

on a loss in quality between use of the application with the compressed workload W′

when compared with use of the application with the initial workload W.

3. The system of claim 2 wherein statements in the workload have weights and additionally comprising an adjust weight component that adjusts weights of those statements that are retained in the compressed workload W′

based on the weights of statements that are discarded from the initial workload W.

4. The system of claim 2 wherein search component chooses a statement to remove from the workload W based on an all-pairs search using the distance function and wherein removal of additional statements from the workload is ended when such removal results a loss of quality that exceeds the limit Δ

.

5. The system of claim 1 wherein the search component uses the evaluation component to assign a number of statements to different clusters based on the distance function and then compresses statements within a cluster.

9. The method of claim 2 wherein choosing a statement to remove from the workload W is based on an all-pairs search using the distance function and wherein removal of additional statements from the workload is ended when such removal results in a loss of quality that exceeds the limit Δ

.

10. The method of claim 9 wherein a distance calculation for candidate statements is determined and wherein statements are removed from the workload for statements having a maximum contribution to distance until a total of such distance contribution for statements removed from the workload equals or exceeds the limit Δ

.

11. The method of claim 9 wherein a distance calculation for candidate statements is determined and wherein statements are removed from the workload for statements having a minimum contribution to distance until a total of such distance contribution for statements removed from the workload equals or exceeds the limit Δ

.

6. For use in a computer database system, a method for compressing a workload used by an application and including a plurality of statements comprising:

providing a distance function for pairs of statements within a workload which returns an estimate of the loss in quality for an application if a first statement is discarded from the workload but a second statement of the pair of statements is retained in a compressed workload; and

finding a compressed workload W′

by evaluating the distance function for pairs of statements to produce a compressed workload having fewer statements than an initial workload W.

7. The method of claim 6 additionally comprising establishing a limit Δ

on a loss in quality between use of the application with the compressed workload W′

when compared with use of the application with the initial workload W.

8. The method of claim 7 wherein statements are randomly sampled from the workload W and the process evaluates the distance function for statements that are randomly sampled from the workload W and removes sampled statements from the workload until the limit on loss of quality is reached.

12. The method of claim 6 additionally comprising partitioning the workload into groups of statements.

13. The method of claim 12 wherein the distance function assigns a large distance between statements that are categorized into different groups.

14. The method of claim 6 wherein the distance function is used to assign a number of statements to different clusters and then compress the set of statements within a cluster.

15. The method of claim 14 wherein the set of statements within a cluster is compressed into a representative statement.

16. The method of claim 15 additionally comprising establishing a limit Δ

on a loss in quality between use of the application with the compressed workload W′

when compared with use of the application with the initial workload W if the loss of quality when using representative statements from the clustering does not exceed the limit the statements are again clustered with a lesser number of clusters.

17. The method of claim 6 wherein the compressed workload is a subset of the initial workload.

18. The method of claim 17 comprising finding a smallest workload W′

⊂

W, such that Σ

<sub>qi∈

W−

W′</sub>

min<sub>qj∈

W′</sub>

{w_i·

Distance_A (q_i, q_j)}<

Δ

.

19. The method of claim 6 where the statements are queries and updates and the application is index selection for processing the queries and updates and further wherein the distance function is based on index choices for a given pair of queries and updates.

20. The method of claim 19 wherein the distance function categorizes queries and updates by the selection, projection, order by, and group by properties of a query and compares these four properties between pairs of queries.

21. The method of claim 20 wherein the distance function determines a distance based on a maximum distance measure for the four properties.

22. The method of claim 6 wherein the statements in the workload are aggregation queries and the application is to find a sample of the database for providing an approximate answer to aggregation queries in the workload such that the average relative error in answers to the workload is minimized.

23. The method of claim 22 further wherein the distance function provides an indication of an increase in error of an approximate answer to the a specified aggregation query if said specified aggregation query is removed from the workload and a second aggregation query of said pair of queries is kept in the compressed workload.

24. The method of claim 6 wherein statements in the workload are given different weights of importance and wherein weights of statements that are removed from the workload W are combined with weights of statements that remain in the compressed workload W′

.

25. The method of claim 6 wherein statements in the workload are partitioned into groups and a distance between statements is determined only if the two statements are classified in the same group.

26. For use in a computer database system, a computer readable medium having instructions stored on said medium for:

providing a distance function for pairs of statements within a workload which returns an estimate of the loss in quality for an application if a first statement is discarded from the workload but a second statement of the pair of statements is retained in a compressed workload; and

finding a compressed workload W′

by evaluating the distance function for pairs of statements to produce a compressed workload having fewer statements than an initial workload W.

27. The computer readable medium of claim 26 additionally comprising instructions for establishing a limit Δ

on a loss in quality between use of the application with the compressed workload W′

when compared with use of the application with the initial workload W.

28. The computer readable medium of claim 27 wherein the instruction randomly sample pairs of statements and the instructions remove evaluates statements that are randomly sampled from the workload W and removes sampled statements from the workload until the limit on loss of quality is reached.

29. The computer readable medium of claim 27 wherein the instructions choose the statement to remove from the workload W based on an all-pairs search using the distance function and wherein removal of additional statements from the workload is ended when such removal results in a loss of quality that exceeds the limit Δ

.

30. The computer readable medium of claim 29 wherein the instructions determine a distance calculation for candidate statements and remove candidate statements from the workload for statements having maximum contribution to distance until a total of such distance contribution for statements removed from the workload equals or exceeds the limit Δ

.

31. The computer readable medium of claim 29 wherein the instructions determine a distance calculation for candidate statements and remove candidate statements from the workload for statements having minimum contribution to distance until a total of such distance contributions for statements removed from the workload equals or exceeds the limit Δ

.

32. The computer readable medium of claim 26 additionally comprising instructions that partition the workload into groups of statements.

33. The computer readable medium of claim 32 wherein the instructions that implement the distance function assign a large distance between statements that are categorized into different groups.

34. The computer readable medium of claim 26 wherein the instructions use the distance function to assign a number of statements to different clusters and then compress the set of statements within a cluster.

35. The computer readable medium of claim 34 wherein the instructions cause the set of statements within a cluster to be compressed into a representative statement for that cluster.

36. The computer readable medium of claim 35 wherein the instructions additionally establish a limit Δ

on a loss in quality between use of the application with the compressed workload W′

when compared with use of the application with the initial workload W and if the loss of quality when using representative statements from the clustering does not exceed the limit the instructions again cluster the statements with a lesser number of clusters.

37. The computer readable medium of claim 26 wherein the instructions choose statements to include in the compressed workload as a subset of the initial workload.

38. The computer readable medium of claim 37 wherein the instructions find a smallest workload W′

⊂

W, such that Σ

<sub>qi∈

W−

W′</sub>

min<sub>qj∈

W′</sub>

{w_i·

Distance_A (q_i, q_j)}<

Δ

.

39. The computer readable medium of claim 26 where the statements are queries and updates, the application is index selection for database attributes for processing the queries and updates, and wherein the distance function is based on index choices for a given pair of queries and updates.

40. The computer readable medium of claim 39 wherein instructions that implement the distance function categorize queries and updates by the selection, projection, order by, and group by properties of a query and compares these four properties between pairs of queries.

41. The computer readable medium of claim 40 wherein the instructions that implement the distance function determine a distance based on a maximum distance measure for the four properties.

42. The computer readable medium of claim 26 wherein the statements in the workload are aggregation queries and the application finds a sample of the database for providing an approximate answer to aggregation queries in the workload such that the average relative error in answers to the workload is minimized.

43. The computer readable medium of claim 42 further wherein the instructions that implement the distance function provides an indication of an increase in error of the approximate answer to a specified aggregation query if the specified aggregation query is removed from the workload and a second aggregation query of said pair of queries is kept in the compressed workload.

44. The computer readable medium of claim 27 wherein the instructions randomly sample pairs of statements and the instructions remove evaluates statements that are randomly sampled from the workload W and removes sample statements from the workload until the limit on loss of quality is reached.

45. The computer readable medium of claim 26 wherein the instructions partition statements in the workload into groups and determine a distance between statements only if the two statements are classified in the same group.