Compressing database workloads

• US 20050102305A1
• Filed: 12/08/2004
• Published: 05/12/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
• Granted Patent: US 7,293,036 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 method for compressing a workload used by an application comprising:

providing a distance function for a pair of statements within an initial workload W containing an initial plurality of statements; and

finding a compressed workload W′

containing a compressed plurality of statements.

2. The method of claim 1 for compressing a workload used by an application additionally comprising establishing an initial running time which is a running time of the application on the initial workload W.

3. The method of claim 1 for compressing a workload used by an application additionally comprising establishing a total running time which is a sum of a running time of the application on the compressed workload W′

plus a time taken to find the compressed workload W′

.

4. The method of claim 1 for compressing a workload used by an application additionally comprising establishing a limit on the total running time.

5. The method of claim 1 for compressing a workload used by an application wherein a count of the compressed plurality of statements is less than a count of the initial plurality of statements.

6. A method for compressing a workload used by an application and including a plurality of statements comprising:

providing a distance function for a pair of statements within an initial workload W;

finding a compressed workload W′

;

establishing an initial running time which is a running time of the application on the initial workload W;

establishing a total running time which is a sum of a running time of the application on the compressed workload W′

plus a time taken to find the compressed workload W′

; and

establishing a limit on the total running time.

7. The method of claim 6 for compressing a workload used by an application and including a plurality of statements wherein the limit is less than the initial running time.

8. The method of claim 6 for compressing a workload used by an application and including a plurality of statements wherein the limit is determined by an estimation of the total running time.

9. The method of claim 8 for compressing a workload used by an application and including a plurality of statements wherein the estimation of the total running time is a sum of an estimated execution time for each of the plurality of statements in the compressed workload W′

plus a time taken to find the compressed workload W′

.

10. The method of claim 9 for compressing a workload used by an application and including a plurality of statements wherein the estimated execution time is determined by a query optimizer.

11. The method of claim 9 for compressing a workload used by an application and including a plurality of statements wherein the estimated execution time is determined using a previous execution time of one or more of the plurality of statements.

12. The method of claim 6 for compressing a workload used by an application and including a plurality of statements wherein the initial running time is taken to be an estimation of a running time of the application on the initial workload W.

13. The method of claim 12 for compressing a workload used by an application and including a plurality of statements wherein the estimation of the running time is a sum of an estimated execution time for each of the plurality of statements in the initial workload W.

14. The method of claim 13 for compressing a workload used by an application and including a plurality of statements wherein the estimated execution time is determined by a query optimizer.

15. The method of claim 13 for compressing a workload used by an application and including a plurality of statements wherein the estimated execution time is determined using a previous execution time of one or more of the plurality of statements.

16. The method of claim 6 for compressing a workload used by an application and including a plurality of statements wherein the compressed workload W′

contains fewer statements than the initial Workload W.

17. A computer system for evaluating a workload comprising:

a database management system including an initial workload W including an initial plurality of statements;

an evaluation component that determines a distance function for a pair of statements within a workload; and

a search component which evaluates the distance function and finds a compressed workload W′

including a compressed plurality of statements.

18. The system of claim 17 for evaluating a workload additionally comprising an initial running time which is a running time of an application on the initial workload W.

19. The system of claim 17 for evaluating a workload additionally comprising a total running time which is a sum of a running time of the application on the compressed workload W′

plus a time taken to find the compressed workload W′

.

20. The system of claim 17 for evaluating a workload additionally comprising a limit on the total running time.

21. The system of claim 17 for evaluating a workload wherein the compressed workload W′

contains fewer statements than the initial workload W.

22. A computer system for evaluating a workload comprising:

a database management system including an initial workload W including an initial plurality of statements;

an evaluation component that determines a distance function for a pair of statements within a workload;

a search component which evaluates the distance function and finds a compressed workload W′

including a compressed plurality of statements.

an initial running time which is a running time of an application on the initial workload W;

a total running time which is a sum of a running time of the application on the compressed workload W′

plus a time taken to find the compressed workload W′

; and

a limit on the total running time.

23. The system of claim 22 for evaluating a workload wherein the limit is less than the initial running time.

24. The system of claim 22 for evaluating a workload wherein the limit is determined by an estimation of the total running time.

25. The system of claim 24 for evaluating a workload wherein the estimation of the total running time is a sum of an estimated execution time for each of the plurality of statements in the compressed workload W′

plus the time taken to find the compressed workload W′

.

26. The system of claim 25 for evaluating a workload wherein the estimated execution time is determined by a query optimizer

27. The system of claim 25 for evaluating a workload wherein the estimated execution time is determined using a previous execution time of one or more of the plurality of statements.

28. The system of claim 22 for evaluating a workload wherein the initial running time is taken to be an estimation of a running time of the application on the initial workload W.

29. The system of claim 28 for evaluating a workload wherein the estimation of the running time is a sum of an estimated execution time for each of the plurality of statements in the initial workload W.

30. The system of claim 29 for evaluating a workload wherein the estimated execution time is determined by a query optimizer.

31. The system of claim 29 for evaluating a workload wherein the estimated execution time is determined using a previous execution time of one or more of the plurality of statements.

32. The system of claim 22 for evaluating a workload wherein the compressed workload W′

contains fewer statements than the initial workload W.

33. A computer readable medium having instructions stored on the medium for:

providing a distance function for a pair of statements within an initial workload W containing an initial plurality of statements; and

finding a compressed workload W′

containing a compressed plurality of statements.

34. The computer readable medium of claim 33 having instructions stored on the medium additionally comprising establishing an initial running time which is a running time of the application on the initial workload W.

35. The computer readable medium of claim 34 having instructions stored on the medium wherein the initial workload W includes an initial plurality of statements.

36. The computer readable medium of claim 33 having instructions stored on the medium additionally comprising establishing a total running time which is a sum of a running time of the application on the compressed workload W′

plus a time taken to find the compressed workload W′

.

37. The computer readable medium of claim 36 having instructions stored on the medium wherein the compressed workload W′

includes a compressed plurality of statements.

38. The computer readable medium of claim 33 having instructions stored on the medium additionally comprising establishing a limit on the total running time.

39. The computer readable medium of claim 33 having instructions stored on the medium wherein a count of the compressed plurality of statements is less than a count of the initial plurality of statements.

40. A computer readable medium having instructions stored on the medium for:

providing a distance function for a pair of statements within an initial workload W;

finding a compressed workload;

establishing an initial running time which is a running time of the application on the initial workload W;

establishing a total running time which is a sum of a running time of the application on the compressed workload W′

plus a time taken to find the compressed workload W′

; and

establishing a limit on the total running time.

41. The computer readable medium of claim 40 having instructions stored on the medium wherein the limit is less than the initial running time.

42. The computer readable medium of claim 40 having instructions stored on the medium wherein the limit is determined by an estimation of the total running time

43. The computer readable medium of claim 42 having instructions stored on the medium wherein the estimation of the total running time is a sum of an estimated execution time for each of the plurality of statements in the compressed workload W′

plus the time taken to find the compressed workload W′

.

44. The computer readable medium of claim 43 having instructions stored on the medium wherein the estimated execution time is determined by a query optimizer.

45. The computer readable medium of claim 43 having instructions stored on the medium wherein the estimated execution time is determined using a previous execution time of one or more of the plurality of statements.

46. The computer readable medium of claim 40 having instructions stored on the medium wherein the initial running time is taken to be an estimation of a running time of the application on the initial workload W.

47. The computer readable medium of claim 46 having instructions stored on the medium wherein the estimation of the running time is a sum of an estimated execution time for each of the plurality of statements in the initial workload W.

48. The computer readable medium of claim 47 having instructions stored on the medium wherein the estimated execution is determined by a query optimizer.

49. The computer readable medium of claim 47 having instructions stored on the medium wherein the estimated execution time is determined using a previous execution time of one or more of the plurality of statements.

50. The computer readable medium of claim 40 having instructions stored on the medium wherein the compressed workload W′

contains fewer statements than the initial workload W.

51. A computer system for evaluating a workload comprising:

a database management means for managing a database;

a distance function means for determining a distance function; and

an evaluation means for evaluating the distance function.