Automatic detection of frequently used query patterns in a query workload

• US 20050283458A1
• Filed: 06/22/2004
• Published: 12/22/2005
• Est. Priority Date: 06/22/2004
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Galindo-Legaria, Cesar A., Waas, Florian M.
• Application Number:
  US10/873,529
• Publication Number:
  US 20050283458A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/24539 using cached or materialised query results

Abstract

In the course of an optimization, a query can be broken down into its sub-expressions. Materialized views may be substituted for the sub-expressions during query optimization. Encoded sub-expressions are generated and used in the comparison with stored materialized views. Instead of discarding the encoding of a query'"'"'s sub-expression if no matching materialization is found, the encoding is stored. If subsequently submitted queries contain the same sub-expression, a view matching mechanism will find the previously stored encoding. Because no materialization is associated with this expression, the view is not substituted. However, usage statistics counters are updated; e.g., a counter is incremented indicating that the sub-expression was found in another query. Because view matching is applied to the sub-expression that are candidates for being materialized, the statistics accurately reflect which are the most frequently occurring candidate sub-expressions in a workload. Users can view and analyze the types and frequencies of sub-expressions found in a workload by querying a system table or virtual table. The table provides an accurate, up-to-date workload synopsis without requiring additional tools or incurring the overhead of client-side tools.

Claims

1. A method for recording data comprising:

receiving a plurality of queries;

obtaining at least one sub-expression for each query;

identifying duplicate occurrences of each sub-expression in the queries;

determining occurrence statistics on each sub-expression; and

maintaining a stored representation of the occurrence statistics for each sub-expression.

2. The method of claim 1, wherein the plurality of queries is provided in its entirety for analysis.

3. The method of claim 1, wherein the plurality of queries is provided in a streaming fashion and analyzed one by one.

4. The method of claim 1, wherein the plurality of queries is an observed sequence submitted by an application for their compilation and execution in a database management system.

5. The method of claim 1, wherein the at least one sub-expressions of each query is obtained by using syntactic rules on the original form of the queries.

6. The method of claim 1, wherein the at least one sub-expressions of each query is obtained by using semantic rules yielding expressions that can be used to answer the query.

7. The method of claim 1, wherein the at least one sub-expressions of each query is obtained by taking sub-plans generated by a query optimizer in its process of plan enumeration.

8. The method of claim 1, wherein the at least one sub-expressions of each query is obtained in a process of attempting materialized view matching in a query compiler.

9. The method of claim 1, wherein identifying duplicate occurrences of each sub-expression in the queries is performed based on syntactical equality of the expressions.

10. The method of claim 1, wherein identifying duplicate occurrences of each sub-expression in the queries is performed based on semantic equality of the expressions.

11. The method of claim 1, wherein identifying duplicate occurrences of each sub-expression in the queries is performed using algorithms for materialized view matching.

12. The method of claim 1, wherein the occurrence statistics comprise a list of queries in which a given sub-expression is obtained.

13. The method of claim 1, wherein the occurrence statistics comprise a count of the number of queries in which a given sub-expression is obtained.

14. The method of claim 1, wherein the occurrence statistics comprise the first or last time in which a given sub-expression is obtained.

15. The method of claim 1, wherein a single store is used to maintain information about materialized views as well as sub-expression statistics.

16. The method of claim 1, wherein a sub-expression storage entry comprises the identification of a materialized view that is semantically equivalent to said sub-expression.

17. The method of claim 1, further comprising, for each sub-expression, an attempt is made to match with an existing materialized view;

only if that fails is a new storage entry created in a data store for the sub-expression.

18. A method for maintaining data related to a query, comprising:

receiving a query;

determining a sub-expression of the query;

determining if the sub-expression matches any previously stored materialized view of a plurality of previously stored materialized views;

substituting the matching previously stored materialized view for the sub-expression in the query, if the sub-expression matches the previously stored materialized view;

storing the sub-expression in a storage device, if the sub-expression fails to match any of the previously stored materialized views.

19. The method of claim 18, further comprising associating a counter with the sub-expression that is stored in the storage device.

20. The method of claim 19, further comprising storing the counter in a system table.

21. The method of claim 20, further comprising:

receiving a second sub-expression after associating the counter with the sub-expression that is stored in the storage device;

determining if the second sub-expression matches the stored sub-expression; and

incrementing the counter if the second sub-expression matches the stored sub-expression.

22. The method of claim 21, further comprising retrieving the count of the counter and outputting the count.

23. The method of claim 21, further comprising:

determining if the second sub-expression matches any previously stored materialized view of the plurality of previously stored materialized views;

substituting the matching previously stored materialized view for the second sub-expression, if the second sub-expression matches the previously stored materialized view;

storing the second sub-expression in the storage device, if the second sub-expression fails to match any of the previously stored materialized views.

24. The method of claim 23, further comprising associating a counter with the second sub-expression that is stored in the storage device.

25. The method of claim 18, wherein determining if the sub-expression matches any previously stored materialized view comprises:

extracting a graph view representation from the sub-expression;

extracting a graph view representation from each of the plurality of previously stored materialized views; and

comparing the extracted graph view representation from the sub-expression with the extracted graph view representations from each of the previously stored materialized views.

26. The method of claim 18, wherein storing the sub-expression in a storage device comprises storing the sub-expression in a lookup table.

27. A computer system comprising:

a data store comprising a plurality of materialized views; and

a processor for receiving a sub-expression of a query, determining if the sub-expression matches any of the materialized views, substituting the matching materialized view for the sub-expression in the query if the sub-expression matches the materialized view, and storing the sub-expression in a storage device if the sub-expression fails to match any of the materialized views.

28. The computer system of claim 27, wherein the storage device comprises a lookup table.

29. The computer system of claim 27, wherein the processor determines if the sub-expression matches any materialized view by extracting a graph view representation from the sub-expression, extracting a graph view representation from each of the plurality of materialized views, and comparing the extracted graph view representation from the sub-expression with the extracted graph view representations from each of the materialized views.

30. The computer system of claim 27, further comprising a counter associated with the sub-expression that is stored in the storage device.

31. The computer system of claim 30, further comprising a system table that stores the counter.

32. The computer system of claim 31, wherein the processor receives a second sub-expression after associating the counter with the sub-expression that is stored in the storage device, determines if the second sub-expression matches the stored sub-expression, and increments the counter if the second sub-expression matches the stored sub-expression.

33. The computer system of claim 31, wherein the processor retrieves the count of the counter and outputs the count.

34. The computer system of claim 31, wherein the processor determines if the second sub-expression matches any of the plurality of materialized views, substitutes the matching materialized view for the second sub-expression if the second sub-expression matches the materialized view, and stores the second sub-expression in the storage device if the second sub-expression fails to match any of the materialized views.

35. The computer system of claim 34, further comprising another counter associated with the second sub-expression that is stored in the storage device.