Generating Materialized Query Table Candidates

• US 20110196857A1
• Filed: 02/09/2010
• Published: 08/11/2011
• Est. Priority Date: 02/09/2010
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Chen, Dong Sheng, Zhang, Zhong Liang, Wang, Xiao Bo, Min, Hong, Shuf, Yefim, Purcell, Terence P.
• Granted Patent: US 8,620,899 B2
• Time in Patent Office: Days
• US Class Current: 707/714
• CPC Class Codes: G06F 16/24539 using cached or materialised query results

Abstract

Techniques for generating a set of one or more materialized query table (MQT) candidates for a workload are provided. The techniques include receiving a workload, wherein the workload comprises a set of one or more queries, generating one or more best matching MQTs (BMQTs) based on one or more query blocks of the one or more queries by removing syntax that is not qualified for a MQT re-write, determining one or more frequently used multi-joins in the workload, using the one or more BMQTs and the one or more frequently used multi-joins to generate a set of one or more workload MQTs (WMQTs), and grouping one or more WMQTs and one or more BMQTs into one or more groups to merge into a set of a smaller number of MQTs and to cover the workload.

Claims

1. A method for generating a set of one or more materialized query table (MQT) candidates for a workload, wherein the method comprises:

receiving a workload, wherein the workload comprises a set of one or more queries;

generating one or more best matching MQTs (BMQTs) based on one or more query blocks of the one or more queries by removing syntax that is not qualified for a MQT re-write;

determining one or more frequently used multi-joins in the workload;

using the one or more BMQTs and the one or more frequently used multi-joins to generate a set of one or more workload MQTs (WMQTs); and

grouping one or more WMQTs and one or more BMQTs into one or more groups to merge into a set of a smaller number of MQTs and to cover the workload.

2. The method of claim 1, further comprising receiving one or more initial sets of MQTs to be considered for further processing.

3. The method of claim 1, wherein generating a best matching MQT (BMQT) for a query block of the one or more queries further comprises gathering any MQT that a user would like to input as a source of one or more candidates.

4. The method of claim 1, wherein grouping one or more WMQTs and one or more BMQTs into one or more groups further comprises grouping one or more WMQTs, one or more BMQTs and one or more other candidates into one or more groups to merge into a set of a smaller number of MQTs and to cover the workload.

5. The method of claim 4, wherein grouping one or more WMQTs, one or more BMQTs and one or more other candidates into one or more groups to merge into a set of a smaller number of MQTs comprises performing merging of select and aggregation columns.

6. The method of claim 4, wherein grouping one or more WMQTs, one or more BMQTs and one or more other candidates into one or more groups to merge into a set of a smaller number of MQTs comprises examining predicate distributions in one or more sampled workloads to determine an appropriate level of consolidation.

7. The method of claim 6, wherein examining predicate distributions in one or more sampled workloads to determine an appropriate level of consolidation comprises dividing predicates observed on a column in a sample workload by using a same histogram grouping that a host database management system (DBMS) uses on the column.

8. The method of claim 1, further comprising performing pre-consolidation of one or more BMQTs.

9. The method of claim 1, further comprising analyzing the workload to obtain information, wherein the information comprises at least one of table and index statistics, join relationships between joined tables and columns, a number of occurrences of each join in the workload, an association of the queries with joins, and referential integrity constraints among tables.

10. The method of claim 1, wherein determining one or more frequently used multi-joins in the workload comprises:

building a data structure to record join relationship and one or more usage patterns;

using the data structure to find a list of one or more commonly used multi-joins; and

sorting all multi-joins by defined order criteria.

11. The method of claim 10, wherein the data structure comprises a matrix.

12. The method of claim 11, determining one or more frequently used multi-joins in the workload comprises traversing the matrix to record one or more important common connected multi-joins in the workload based on certain formulated criteria.

13. The method of claim 12, wherein connection is dictated by elements in the matrix, and importance is measured by criteria, wherein the criteria comprises at least one of frequencies and sizes of tables included.

14. The method of claim 1, wherein using the one or more BMQTs and the one or more frequently used multi-joins to generate a set of one or more WMQTs comprises:

iterating through each BMQT and its associated query identifier and determining a top n number of multi-joins that cover each BMQT; and

generating the set of one or more WMQTs by adding same select, aggregation and predicate clauses from a BMQT to the corresponding multi-join.

15. The method of claim 1, wherein using the one or more BMQTs and the one or more frequently used multi-joins to generate a set of one or more WMQTs comprises:

iterating through one or more BMQTs in the workload;

identifying a top number of common multi-joins that exist in each BMQT;

removing one or more tables that are not in multi-joins from each BMQT if a join from one or more tables to one or more tables in multi-join are lossless; and

modifying other operators of the one or more BMQTs to only contain the remaining tables.

16. The method of claim 1, further comprising modeling one or more join patterns.

17. The method of claim 16, wherein modeling one or more join patterns comprises:

ranking each join by one or more characteristics;

recording frequencies of one or more joins in the workload in a data structure; and

recording a frequency of co-existence in a query of a lower ranked join with respect to a higher ranked join.

18. The method of claim 1, further comprising providing a system, wherein the system comprises one or more distinct software modules, each of the one or more distinct software modules being embodied on a tangible computer-readable recordable storage medium, and wherein the one or more distinct software modules comprise a user options module, a workload structure query language (SQL) module, a workload capture module, a workload analysis module, a query syntactic structure analysis module, a BMQT generation and consolidation module, a WMQT generation module, and a MQT consolidation module executing on a hardware processor.

19. A computer program product comprising a tangible computer readable recordable storage medium including computer useable program code for generating a set of one or more materialized query table (MQT) candidates for a workload, the computer program product including:

computer useable program code for receiving a workload, wherein the workload comprises a set of one or more queries;

computer useable program code for generating one or more best matching MQTs (BMQTs) based on one or more query blocks of the one or more queries by removing syntax that is not qualified for a MQT re-write;

computer useable program code for determining one or more frequently used multi-joins in the workload;

computer useable program code for using the one or more BMQTs and the one or more frequently used multi-joins to generate a set of one or more workload MQTs (WMQTs); and

computer useable program code for grouping one or more, WMQTs and one or more BMQTs into one or more groups to merge into a set of a smaller number of MQTs and to cover the workload.

20. The computer program product of claim 19, wherein the computer useable program code for grouping one or more WMQTs, one or more BMQTs and one or more other candidates into one or more groups to merge into a set of a smaller number of MQTs comprises computer useable program code for examining predicate distributions in one or more sampled workloads to determine an appropriate level of consolidation.

21. The computer program product of claim 19, further comprising computer useable program code for receiving one or more initial sets of MQTs to be considered for further processing.

22. A system for generating a set of one or more materialized query table (MQT) candidates for a workload, comprising:

a memory; and

at least one processor coupled to the memory and operative to;

receive a workload, wherein the workload comprises a set of one or more queries;

generate one or more best matching MQTs (BMQTs) based on one or more query blocks of the one or more queries by removing syntax that is not qualified for a MQT re-write;

determine one or more frequently used multi-joins in the workload;

use the one or more BMQTs and the one or more frequently used multi-joins to generate a set of one or more workload MQTs (WMQTs); and

group one or more WMQTs and one or more BMQTs into one or more groups to merge into a set of a smaller number of MQTs and to cover the workload.

23. The system of claim 22, wherein the at least one processor coupled to the memory operative to group one or more WMQTs, one or more BMQTs and one or more other candidates into one or more groups to merge into a set of a smaller number of MQTs is further operative to examine predicate distributions in one or more sampled workloads to determine an appropriate level of consolidation.

24. The system of claim 22, wherein the at least one processor coupled to the memory is further operative to receive one or more initial sets of MQTs to be considered for further processing.

25. An apparatus for generating a set of one or more materialized query table (MQT) candidates for a workload, the apparatus comprising:

means for receiving a workload, wherein the workload comprises a set of one or more queries;

means for generating one or more best matching MQTs (BMQTs) based on one or more query blocks of the one or more queries by removing syntax that is not qualified for a MQT re-write;

means for determining one or more frequently used multi-joins in the workload;

means for using the one or more BMQTs and the one or more frequently used multi joins to generate a set of one or more workload MQTs (WMQTs); and

means for grouping one or more WMQTs and one or more BMQTs into one or more groups to merge into a set of a smaller number of MQTs and to cover the workload.