Query optimization by transparently altering properties of relational tables using materialized views

• US 6,339,769 B1
• Filed: 09/14/1998
• Issued: 01/15/2002
• Est. Priority Date: 09/14/1998
• Status: Expired due to Term

• Current Assignee: Devine Licensing LLC (IP Edge LLC)
• Original Assignee: International Business Machines Corporation
• Inventors: Simmen, David E., Zuzarte, Calisto Paul, Pirahesh, Mir Hamid, Leung, Ting Yu, Lapis, George, Cochrane, Roberta Jo, Sidle, Richard Sefton, Urata, Monica Sachiye
• Primary Examiner(s): Corrielus, Jean M.
• Application Number:
  US09/152,551
• Time in Patent Office: 1,219 Days
• Field of Search: 707/201, 707/10, 707/203, 707/2, 707/3, 707/1, 707/4, 707/104, 707/5, 707/6, 707/7, 707/100
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24539 using cached or materialised query results
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A method, apparatus, and article of manufacture for optimizing database queries using a materialized view for a table referenced in the query, wherein the materialized view has different properties than the referenced table. The materialized view may be replicated across multiple processors of the computer system, so that some or all of the query can be executed in a local fashion wherein there is no data movement required to perform the operations. The materialized view also may be partitioned across multiple processors of the computer system using a different partitioning key than the referenced table. The materialized view may be a vertical and/or horizontal subset of the table, so that only selected columns and/or tuples from the table are present therein. Columns may be added to the materialized view to contain pre-computed results of complex expressions, and indices may be created on the columns of the materialized view.

Claims

1. A method of optimizing a query in a computer system, the query being performed by the computer system to retrieve data from a database stored on the computer system, the method comprising the steps of:

(a) accepting the query into the computer system;

(b) determining whether there exists one or more materialized views for one or more tables referenced in the query, wherein the materialized view has different partitioning or replication properties than the tables referenced in the query;

(c) analyzing whether at least a portion of the query can be evaluated using one or more of the materialized views in a local fashion, so that no data movement is required for the evaluation;

(d) rewriting the query to use one or more materialized views rather than an original table or tables referenced in the query; and

(e) executing the rewritten query using one or more materialized views.

2. The method of claim 1, wherein the computer system is comprised of a plurality of processors.

3. The method of claim 2, wherein the materialized view is replicated across the processors of the computer system.

4. The method of claim 2, wherein the materialized view is partitioned across the processors of the computer system.

5. The method of claim 1, wherein the materialized view comprises only selected columns of the table.

6. The method of claim 1, wherein the materialized view comprises only selected tuples of the table.

7. The method of claim 1, wherein the materialized view includes one or more columns containing pre-computed results from one or more expressions.

8. The method of claim 1, wherein the materialized view includes one or more indices on one or more columns of the materialized view.

9. The method of claim 1, wherein the analyzing step comprises the step of identifying a join of a first table and a second table in the query, wherein a materialized view is substitutable for the second table, the materialized view is local with the first table, and the join is performed locally.

10. The method of claim 1, wherein the analyzing step comprises the step of identifying a left join of a first table and a second table in the query, wherein a materialized view is substitutable for the second table, the materialized view is local with the first table, and the left join is performed locally.

11. The method of claim 1, wherein the analyzing step comprises the step of identifying a right join of a first table and a second table in the query, wherein a materialized view is substitutable for the first table, the materialized view is local with the second table, and the right join is performed locally.

12. The method of claim 1, wherein the analyzing step comprises the step of identifying a full join of a first table and a second table in the query, wherein a first materialized view is substitutable for the first table and a second materialized view is substitutable for the second table, the first and second materialized views are co-located in at least one processor, and the full join is performed locally.

13. A method of optimizing a query in a computer system having a plurality of processors, the query being performed by the computer system to retrieve data from a database stored across the processors of the computer system, the method comprising the steps of:

(a) materializing a view for a table of the database, wherein the materialized view has different properties than the table;

(b) replicating the materialized view across the processors of the computer system;

(c) analyzing a query into the computer system to determine whether the materialized view can be substituted for a table referenced in the query, so that at least a portion of the query can be evaluated in a local fashion;

(d) rewriting the query to use the replicated materialized view rather than the table referenced in the query; and

(e) executing the query using the replicated materialized view.

14. The method of claim 13, wherein another table referenced in the query is comprised of a plurality of partitions and the replicating step comprises the step of replicating the materialized view so that it is local with each of the partitions.

15. The method of claim 13, wherein the replicating step comprises the step of broadcast replicating the materialized views across the processors of the computer system.

16. The method of claim 13, wherein the materialized view comprises only selected columns of the table and the replicating step comprises the step of replicating only the selected columns across the processors of the computer system.

17. The method of claim 13, wherein the materialized view comprises only selected rows of the table and the replicating step comprising the step of replicating only the selected rows across the processors of the computer system.

18. The method of claim 13, wherein the materialized view comprises one or more columns containing pre-computed results of one or more complex expressions in the query.

19. The method of claim 18, further comprising the step of creating an index for the column of the materialized view containing the pre-computed results.

20. The method of claim 13, further comprising the step of partitioning the materialized view across the processors of the computer system.

21. The method of claim 13, wherein the analyzing step comprises the step of identifying a join of a first table and a second table in the query, wherein the materialized view is substitutable for the second table, the materialized view is local with the first table, and the join is performed locally.

22. The method of claim 13, wherein the analyzing step comprises the step of identifying a left join of a first table and a second table in the query, wherein the materialized view is substitutable for the second table, the materialized view is local with the first table, and the left join is performed locally.

23. The method of claim 13, wherein the analyzing step comprises the step of identifying a right join of a first table and a second table in the query, wherein the materialized view is substitutable for the first table, the materialized view is local with the second table, and the right join is performed locally.

24. The method of claim 13, wherein the analyzing step comprises the step of identifying a full join of a first table and a second table in the query, wherein a first materialized view is substitutable for the first table and a second materialized view is substitutable for the second table, the first and second materialized views are co-located in at least one processor, and the full join is performed locally.

25. An apparatus for optimizing a query, comprising:

(a) a computer system having a data storage device coupled thereto for storing a database, the query being performed by the computer to retrieve data from the database; and

(b) means, performed by the computer system, for accepting the query into the computer system;

for determining whether there exists one or more materialized views for one or more tables referenced in the query, wherein the materialized view has different partitioning or replication properties than the tables referenced in the query;

for analyzing whether at least a portion of the query can be evaluated using one or more of the materialized views in a local fashion, so that no data movement is required for the evaluation, for rewriting the query to use one or more materialized views rather than an original table or tables referenced in the query; and

for executing the rewritten query using one or more materialized views.

26. The apparatus of claim 25, wherein the computer system is comprised of a plurality of processors.

27. The apparatus of claim 26, wherein the materialized view is replicated across the processors of the computer system.

28. The apparatus of claim 26, wherein the materialized view is partitioned across the processors of the computer system.

29. The apparatus of claim 25, wherein the materialized view comprises only selected columns of the table.

30. The apparatus of claim 25, wherein the materialized view comprises only selected tuples of the table.

31. The apparatus of claim 25, wherein the materialized view includes one or more columns containing pre-computed results from one or more expressions.

32. The apparatus of claim 25, wherein the materialized view includes one or more indices on one or more columns of the materialized view.

33. The apparatus of claim 25, wherein the means for analyzing comprises means for identifying a join of a first table and a second table in the query, wherein a materialized view is substitutable for the second table, the materialized view is local with the first table, and the join is performed locally.

34. The apparatus of claim 25, wherein the means for analyzing comprises means for identifying a left join of a first table and a second table in the query, wherein a materialized view is substitutable for the second table, the materialized view is local with the first table, and the left join is performed locally.

35. The apparatus of claim 25, wherein the means for analyzing comprises means for identifying a right join of a first table and a second table in the query, wherein a materialized view is substitutable for the first table, the materialized view is local with the second table, and the right join is performed locally.

36. The apparatus of claim 25, wherein the means for analyzing comprises means for identifying a full join of a first table and a second table in the query, wherein a first materialized view is substitutable for the first table and a second materialized view is substitutable for the second table, the first and second materialized views are co-located in at least one processor, and the full join is performed locally.

37. An apparatus for optimizing a query, comprising:

(a) a computer having a plurality of processors, the query being performed by the computer to retrieve data from a database stored across the processors of the computer system; and

(b) means, performed by the computer, for materializing a view for a table of the database, wherein the materialized view has different properties than the table;

for replicating the materialized view across the processors of the computer system;

for analyzing a query into the computer system to determine whether the materialized view can be substituted for a table referenced in the query, so that at least a portion of the query can be evaluated in a local fashion;

for rewriting the query to use the replicated materialized view rather than the table referenced in the query; and

for executing the query using the replicated materialized view.

38. The apparatus of claim 37, wherein another table referenced in the query is comprised of a plurality of partitions and the means for replicating comprises means for replicating the materialized view so that it is local with each of the partitions.

39. The apparatus of claim 37, wherein the means for replicating comprises means for broadcast replicating the materialized views across the processors of the computer system.

40. The apparatus of claim 37, wherein the materialized view comprises only selected columns of the table and the means for replicating comprises means for replicating only the selected columns across the processors of the computer system.

41. The apparatus of claim 37, wherein the materialized view comprises only selected rows of the table and the means for replicating comprises means for replicating only the selected rows across the processors of the computer system.

42. The apparatus of claim 37, wherein the materialized view comprises one or more columns containing pre-computed results of one or more complex expressions in the query.

43. The apparatus of claim 42, further comprising means for creating an index for the column of the materialized view containing the pre-computed results.

44. The apparatus of claim 37, further comprising means for partitioning the materialized view across the processors of the computer system.

45. The apparatus of claim 37, wherein the means for analyzing comprises means for identifying a join of a first table and a second table in the query, wherein the materialized view is substitutable for the second table, the materialized view is local with the first table, and the join is performed locally.

46. The apparatus of claim 37, wherein the means for analyzing comprises means for identifying a left join of a first table and a second table in the query, wherein the materialized view is substitutable for the second table, the materialized view is local with the first table, and the left join is performed locally.

47. The apparatus of claim 37 wherein the means for analyzing comprises means for identifying a right join of a first table and a second table in the query, wherein the materialized view is substitutable for the first table, the materialized view is local with the second table, and the right join is performed locally.

48. The apparatus of claim 37, wherein the means for analyzing comprises means for identifying a full join of a first table and a second table in the query, wherein a first materialized view is substitutable for the first table and a second materialized view is substitutable for the second table, the first and second materialized views are co-located in at least one processor, and the full join is performed locally.

49. An article of manufacture embodying logic for performing method steps for optimizing a query, the query being performed by a computer system to retrieve data from a database stored in a data storage device coupled to the computer system, the method comprising the steps of:

(a) accepting the query into the computer system;

(b) determining whether there exists one or more materialized views for one or more tables referenced in the query, wherein the materialized view has different partitioning or replication properties than the tables referenced in the query;

(c) analyzing whether at least a portion of the query can be evaluated using one or more of the materialized views in a local fashion, so that no data movement is required for the evaluation;

(d) rewriting the query to use one or more materialized views rather than an original table or tables referenced in the query; and

(e) executing the rewritten query using one or more materialized views.

50. The method of claim 49, wherein the computer system is comprised of a plurality of processors.

51. The method of claim 50, wherein the materialized view is replicated across the processors of the computer system.

52. The method of claim 50, wherein the materialized view is partitioned across the processors of the computer system.

53. The method of claim 49, wherein the materialized view comprises only selected columns of the table.

54. The method of claim 49, wherein the materialized view comprises only selected tuples of the table.

55. The method of claim 49, wherein the materialized view includes one or more columns containing pre-computed results from one or more expressions.

56. The method of claim 49, wherein the materialized view includes one or more indices on one or more columns of the materialized view.

57. The method of claim 49, wherein the analyzing step comprises the step of identifying a join of a first table and a second table in the query, wherein a materialized view is substitutable for the second table, the materialized view is local with the first table, and the join -is performed locally.

58. The method of claim 49, wherein the analyzing step comprises the step of identifying a left join of a first table and a second table in the query, wherein a materialized view is substitutable for the second table, the materialized view is local with the first table, and the left join is performed locally.

59. The method of claim 49, wherein the analyzing step comprises the step of identifying a right join of a first table and a second table in the query, wherein a materialized view is substitutable for the first table, the materialized view is local with the second table, and the right join is performed locally.

60. The method of claim 49, wherein the analyzing step comprises the step of identifying a full join of a first table and a second table in the query, wherein a first materialized view is substitutable for the first table and a second materialized view is substitutable for the second table, the first and second materialized views are co-located in at least one processor, and the full join is performed locally.

61. An article of manufacture embodying logic for performing method steps for optimizing a query, the query being performed by a computer system having a plurality of processors to retrieve data from a database stored across the processors of the computer system, the method comprising the steps of:

(a) materializing a view for a table of the database, wherein the materialized view has different properties than the table;

(b) replicating the materialized view across the processors of the computer system;

(c) analyzing a query into the computer system to determine whether the materialized view can be substituted for a table referenced in the query, so that at least a portion of the query can be evaluated in a local fashion;

(d) rewriting the query to use the replicated materialized view rather than the table referenced in the query; and

(e) executing the query using the replicated materialized view.

62. The method of claim 61, wherein another table referenced in the query is comprised of a plurality of partitions and the replicating step comprises the step of replicating the materialized view so that it is local with each of the partitions.

63. The method of claim 61, wherein the replicating step comprises the step of broadcast replicating the materialized views across the processors of the computer system.

64. The method of claim 61, wherein the materialized view comprises only selected columns of the table and the replicating step comprises the step of replicating only the selected columns across the processors of the computer system.

65. The method of claim 61, wherein the materialized view comprises only selected rows of the table and the replicating step comprising the step of replicating only the selected rows across the processors of the computer system.

66. The method of claim 61, wherein the materialized view comprises one or more columns containing pre-computed results of one or more complex expressions in the query.

67. The method of claim 66, further comprising the step of creating an index for the column of the materialized view containing the pre-computed results.

68. The method of claim 61, further comprising the step of partitioning the materialized view across the processors of the computer system.

69. The method of claim 61, wherein the analyzing step comprises the step of identifying a join of a first table and a second table in the query, wherein the materialized view is substitutable for the second table, the materialized view is local with the first table, and the join is performed locally.

70. The method of claim 61, wherein the analyzing step comprises the step of identifying a left join of a first table and a second table in the query, wherein the materialized view is substitutable for the second table, the materialized view is local with the first table, and the left join is performed locally.

71. The method of claim 61, wherein the analyzing step comprises the step of identifying a right join of a first table and a second table in the query, wherein the materialized view is substitutable for the first table, the materialized view is local with the second table, and the right join is performed locally.

72. The method of claim 61, wherein the analyzing step comprises the step of identifying a full join of a first table and a second table in the query, wherein a first materialized view is substitutable for the first table and a second materialized view is substitutable for the second table, the first and second materialized views are co-located in at least one processor, and the full join is performed locally.