Compressing database workloads

• US 7,293,036 B2
• Filed: 12/08/2004
• Issued: 11/06/2007
• Est. Priority Date: 06/26/2002
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chaudhuri, Surajit, Narasayya, Vivek, Gupta, Ashish Kumar
• Primary Examiner(s): Gaffin; Jeffrey
• Assistant Examiner(s): ABEL JALIL, NEVEEN
• Application Number:
  US11/008,335
• Publication Number:
  US 20050102305A1
• Time in Patent Office: 1,063 Days
• Field of Search: 707/104.1, 707/3, 706/917, 709/224, 703/21
• 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 to compress a workload including a plurality of statements comprising:

providing a distance function in a database management system for a pair of statements within an initial workload W containing a plurality of statements;

compressing the initial workload W to generate a compressed workload W′

based on the distance function, the compressed workload W′

including a subset of statements of the plurality of statements of the initial workload W;

determining a generation time indicating a length of time to generate the compressed workload W′

;

establishing a compressed running time indicating a length of time for an application to run the compressed workload W′

;

establishing a total running time of the application indicating a length of time for the application to run the initial workload W; and

estimating a total running time which includes a sum of the generation time and the compressed running time; and

determining a limit on the total running time, the limit on the total running time being less then the initial running time; and

outputting the generated compressed workload W′

.

2. The method of claim 1 wherein the compressed workload W′

is used by the application and wherein a count of the compressed plurality of statements is less than a count of the initial plurality of statements.

3. The method of claim 1 wherein the compressed workload W′

is used by the application, the method further comprising establishing the initial running time which is a running time of the application on the initial workload W.

4. The method of claim 1 wherein the compressed workload W′

is used by the application the method further comprising establishing the total running time which is a sum of a running time of the application on the compressed workload W′

plus a time taken to generate the compressed workload W′

.

5. The method of claim 4 wherein the compressed workload W′

is used by the application, the method further comprising establishing the limit on the total running time.

6. The method of claim 1 wherein the limit on the total running time is determined by an estimation of the total running time.

7. The method of claim 1 wherein the estimation of the total running time includes a sum of an estimated execution time for each of the plurality of statements in the compressed workload W′

plus a time taken to generate the compressed workload W′

.

8. The method of claim 7 wherein the estimated execution time is determined by a query optimizer.

9. The method of claim 7 wherein the estimated execution time is determined using a previous execution time of one or more of the plurality of statements.

10. The method of claim 1 wherein the estimation of the initial running time includes a sum of an estimated execution time for each of the plurality of statements in the initial workload W.

11. The method of claim 10 wherein the estimated execution time is determined by a query optimizer.

12. The method of claim 10 wherein the estimated execution time is determined using a previous execution time of one or more of the plurality of statements in the initial workload W.

13. The method of claim 1 wherein the compressed workload W′

contains fewer statements than the initial workload W.

14. A computer system to compress a workload comprising:

a processor;

a database management system that receives an initial workload W, the initial workload W including an initial plurality of statements;

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

a search component which evaluates the distance function and compresses the initial workload W to generate a compressed workload W′

including a compressed plurality of statements based on the distance function,

wherein the database management estimating a total running time including a sum of a running time of an application on the compressed workload W′

plus a time taken to generate the compressed workload W′

further outputs the compressed workload W′

.

15. The system of claim 14 wherein the database management system further estimates an initial running time of the application, the initial running time indicating a length of time for the application to run the initial workload W.

16. The system of claim 14 wherein the computer system further determines a limit on the total running time.

17. The system of claim 14 wherein the compressed workload W′

contains fewer statements than the initial workload W.

18. A computer system to compress a workload comprising:

a processor;

a database management system that receives an initial workload W, the initial workload W including an initial plurality of statements;

an evaluation component that determines a distance function for a pair of statements within the initial plurality of statements of the workload W;

a search component which compresses the initial workload W to generate a compressed workload W′

including a compressed plurality of statements based on the distance function, the search component estimating;

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 to generate the compressed workload W′

; and

a limit on the total running time, the limit on the total running time being less than the initial running time,

wherein the database management system receives the comoressed workload W′ and

outputs the compressed workload W′

.

19. The system of claim 18 wherein the limit on the total running time is determined by estimating the total running time.

20. The system of claim 19 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 to generate the compressed workload W′

.

21. The system of claim 20 wherein the estimated execution time is determined by a query optimizer.

22. The system of claim 20 wherein the estimated execution time is determined using a previous execution time of one or more of the plurality of statements.

23. The system of claim 18 wherein the initial running time is an estimation of a running time of the application on the initial workload W.

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

25. The system of claim 24 wherein the estimated execution time is determined by a query optimizer.

26. The system of claim 24 wherein the estimated execution time is determined using a previous execution time of one or more of the plurality of statements.

27. The system of claim 18 wherein the compressed workload W′

contains fewer statements than the initial workload W.

28. A computer readable storage medium having executable instructions stored on the medium, the execution of the instruction on a computer, perform the following steps

providing a distance function in a database management system for a pair of statements within an initial workload W;

finding a compressed workload W′

based on the distance function;

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

establishing a total running time, the total running time being a sum of a running time of the application on the compressed workload W′

plus a time to generate the compressed workload W′

; and

establishing a limit on the total running time, the limit on the total running time being determined by an estimation of the total time running time; and

outputting the generated compressed workload W′

.

29. The computer readable storage medium of claim 28 having further instructions to establish an initial running time of the application on the initial workload W.

30. The computer readable storage medium of claim 29 wherein the initial workload W includes an initial plurality of statements.

31. The computer readable storage medium of claim 28 having further instructions to establish 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 generate the compressed workload W′

.

32. The computer readable storage medium of claim 31 wherein the compressed workload W′

includes a compressed plurality of statements.

33. The computer readable storage medium of claim 28 having further instructions to establish a limit on the total running time.

34. The computer readable storage medium of claim 28 wherein a count of the compressed plurality of statements is less than a count of the initial plurality of statements.

35. The computer readable storage medium of claim 28 wherein the limit on the total running time is less than the initial running time.

36. The computer readable storage medium of claim 28 wherein the estimation of the total running time is a sum of the 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′

.

37. The computer readable storage medium of claim 36 wherein the estimated execution time is determined using a previous execution time of one or more of the plurality of statements.

38. The computer readable storage medium of claim 36 wherein the estimated execution time is determined by a query optimizer.

39. The computer readable storage medium of claim 28 wherein the initial running time is taken to be an estimation of a running time of the application on the initial workload W.

40. The computer readable storage medium of claim 39 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.

41. The computer readable storage medium of claim 40 wherein the estimated execution time is determined by a query optimizer.

42. The computer readable storage medium of claim 40 wherein the estimated execution time is determined using a previous execution time of one or more of the plurality of statement in the initial workload W.

43. The computer readable storage medium of claim 28 wherein the compressed workload W′

contains fewer statements than the initial Workload W.