Dynamic physical database design

• US 20060036989A1
• Filed: 08/10/2004
• Published: 02/16/2006
• Est. Priority Date: 08/10/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chaudhuri, Surajit, Konig, Arnd Christian, Narasayya, Vivek R.
• Granted Patent: US 7,483,918 B2
• Time in Patent Office: Days
• US Class Current: 717/101
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

A monitoring component of a database server collects a subset of a query workload along with related statistics. A remote index tuning component uses the workload subset and related statistics to determine a physical design that minimizes the cost of executing queries in the workload subset while ensuring that queries omitted from the subset do not degrade in performance.

Claims

1. A method comprising:

dynamically capturing a workload subset and related statistics from a query workload executing against a database of a database server;

storing the workload subset and the statistics in a memory on the database server;

limiting the size of the workload subset and the statistics based on a memory constraint; and

transferring the workload subset and the statistics to a database tuning component remote from the database server.

2. A method as recited in claim 1, wherein the dynamically capturing comprises capturing the workload subset and the statistics over a moving time interval, the moving time interval having a specified duration which ranges from a current point in time to a preceding point in time.

3. A method as recited in claim 2, further comprising receiving at the database server, an instruction from a database administrator indicating the specified duration.

4. A method as recited in claim 1, further comprising compressing the workload subset on the database server.

5. A method as recited in claim 4, wherein the compressing comprises:

identifying a query template;

grouping queries belonging to the query template; and

including only a portion of the queries belonging to the query template within the workload subset.

6. A method as recited in claim 4, further comprising maximizing the cost of the portion of the queries belonging to the query template included within the workload subset.

7. A method as recited in claim 6, wherein the maximizing the cost comprises:

determining an average execution cost for each query belonging to a query template based on that query'"'"'s frequency of access to database objects; and

evicting a query having the least average execution cost.

8. A method as recited in claim 1, wherein the storing the workload subset and the statistics comprises:

storing the workload subset in a workload LAT (light-weight aggregation table);

storing in an index_usage LAT, a cumulative cost of all queries using a specific index or materialized view in a select statement; and

storing in a table_usage LAT, a cumulative cost of all write-accesses for each table in the database.

9. A method as recited in claim 1, wherein the limiting comprises:

allocating an amount of memory for storing queries from the query workload; and

evicting queries from the memory when the allocated amount of memory is exceeded.

10. A method as recited in claim 1, wherein the transferring comprises periodically transferring the workload subset and the statistics to the index tuning component at a regular time interval.

11. A method as recited in claim 1, further comprising:

determining a physical design with the database tuning component, wherein the physical design is applicable to the query workload executing against the database and is determined based on the workload subset and the statistics;

determining an estimated cost of executing the workload subset against the database using the physical design; and

reporting the physical design and the estimated cost to a database administrator.

12. A method as recited in claim 11, wherein the determining a physical design comprises minimizing a cost of executing queries in the workload subset subject to a constraint that no query may degrade in performance if that query is within the query workload but not within the workload subset.

13. A method as recited in claim 11, wherein the determining a physical design comprises specifing that a minimum percentage of queries using a database object be contained within the workload subset before the database object can be dropped from the physical design.

14. A method as recited in claim 11, wherein the physical design comprises a set of one or more indexes and/or materialized views.

15. A method as recited in claim 11, further comprising receiving instructions from the database administrator at the database server to implement the physical design.

16. A processor-readable medium comprising processor-executable instructions configured for:

monitoring a query workload, WL, executing on a database server over a sliding time interval;

capturing a workload subset, WL′

, of WL;

capturing statistics associated with WL;

storing WL′ and

the statistics in a main memory of the database server such that WL′ and

the statistics are limited in size according to a memory constraint m.

17. A processor-readable medium as recited in claim 16, comprising further processor-executable instructions configured for:

receiving a time duration, Δ

; and

wherein the monitoring comprises monitoring WL for the time duration of Δ

over the time interval of [now-Δ

, now], wherein now is a current point in time.

18. A processor-readable medium as recited in claim 16, comprising further processor-executable instructions configured for:

determining queries within WL′

having the lowest average execution cost;

receiving a query for WL′

whose text size causes WL′

to exceed the memory constraint m; and

evicting the queries within WL′

having the lowest average execution cost, thereby keeping WL′

within the memory constraint m.

19. A processor-readable medium as recited in claim 16, comprising further processor-executable instructions configured for compressing WL′

.

20. A processor-readable medium as recited in claim 19, wherein the compressing comprises:

identifing a query template;

grouping queries belonging to the query template; and

including only a portion of the queries belonging to the query template within WL′

.

21. A processor-readable medium as recited in claim 16, comprising further processor-executable instructions configured for:

copying WL′ and

the statistics at regular intervals to a remote database tuning component; and

potentially receiving physical design instructions from a database administrator in response to each occurrence of the copying.

22. A computer comprising the processor-readable medium of claim 16.

23. A processor-readable medium comprising processor-executable instructions configured for:

receiving a workload subset, WL′

, and associated statistics from a database server;

receiving a coverage constraint regarding a physical database object, the coverage constraint specifying a percentage of queries in a workload WL using the physical database object that must be present in WL′

before the physical database object can be changed;

determining a physical design based on WL′ and

the associated statistics;

precluding a change to the physical database object in the physical design if the percentage of queries is not present within WL′

; and

permitting a change to the physical database object in the physical design if the percentage of queries is present within WL′

.

24. A processor-readable medium as recited in claim 23, comprising further processor-executable instructions configured for determining an estimated cost of executing WL′

against a database.

25. A processor-readable medium as recited in claim 24, comprising further processor-executable instructions configured for reporting the physical design and the estimated cost to a database administrator.

26. A processor-readable medium as recited in claim 23, wherein receiving a workload subset, WL′

, and associated statistics comprises periodically receiving a workload subset, WL′

, and associated statistics according to a tuning interval specified by a database administrator.

27. A computer comprising the processor-readable medium of claim 23.

28. A dynamic physical database design system comprising:

a database server;

a database store;

a continuous monitoring component configured to monitor a query workload executing on the database server against the database store, and to capture and compress a subset of the query workload and associated statistics over a specified time interval.

29. A dynamic physical database design system as recited in claim 28, further comprising a database tuning component configured to receive the subset and statistics from the continuous monitoring component and to determine a physical design that minimizes a cost of executing queries in the subset subject to a constraint that no query may degrade in performance if that query is within the query workload but not within the subset.

30. A dynamic physical database design system as recited in claim 29, further comprising a database administrator configured to receive the physical design and a cost estimate and to instruct the database server to implement the physical design based on the cost estimate.