Cost based optimization of decision support queries using transient views

• US 6,275,818 B1
• Filed: 11/05/1998
• Issued: 08/14/2001
• Est. Priority Date: 11/06/1997
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Subramanian, Narayana Iyer, Venkataraman, Shivakumar
• Primary Examiner(s): Breene, John
• Assistant Examiner(s): Rayyan, Susan F.
• Application Number:
  US09/186,804
• Time in Patent Office: 1,013 Days
• Field of Search: 707/2-5
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2454 Optimisation of common expressions
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

The present invention discloses a method, apparatus, and article of manufacture for optimizing one or more queries. Initially, redundancies in execution steps for the one or more queries are identified. Then, a new set of equivalent execution steps is created by eliminating redundancies in the execution steps. The new set of equivalent execution steps is used to execute the one or more queries when the use results in efficient query processing.

Claims

1. A method of modifying a query plan for improved performance, comprising:

(a) identifying a plurality of sub-plans within the query plan;

(b) generating one or more equivalence classes for the query plan, wherein each equivalence class contaims similar ones of the sub-plans;

(c) generating a transient view to answer all of the sub-plans in an associated one of the equivalence classes, wherein the transient view contains a union of results from all of the sub-plans in the associated one of the equivalence classes;

(d) utilizing a cost model to identify the transient views that improve the performance of the query plan; and

(e) applying filters to the identified transient views to obtain results for each sub-plan in the associated equivalence class.

2. The method of claim 1, further comprising determining whether to materialize the transient view.

3. The method of claim 1, wherein slimlar ones of the sub-plans contained in an equivalence class are identified by one or more properties.

4. The method of claim 3, wherein the properties are selected from a property list comprised of one or more of the following:

tables in the plan, columns selected, join predicates, selection predicates, aggregation functions, columns in a GROUP BY list, data sources, a cost of executing the plan, and a number of result rows.

5. The method of claim 4, further comprising:

generating a query that represents the transient view from the property list of the transient view;

optimizing the query; and

obtaining an execution plan, cost, and cardinality for the transient view.

6. The method of claim 1, further comprising using the cost model to decide whether to materialize the transient view.

7. The method of claim 1, wherein the sub-plans each have a scan type property, a table scanned property, a simple predicates property, and a columns selected property, further comprising the step of using one or more of these properties to determine which of the sub-plans are similar.

8. The method of claim 1, wherein the sub-plans each have a join method property, a join predicates property, an outer plan property, and an inner plan property, and further comprising the step of using one or more of these properties to determine which of the sub-plans are similar.

9. The method of claim 1, wherein the sub-plans each have an input plan property, and further comprising the step of using this property to determine which of the sub-plans are similar.

10. An apparatus for optimizing one or more queries, comprising:

(a) a computer having a data storage device connected thereto, wherein the data storage device stores a database;

(b) one or more computer programs performed by the computer, for;

(1) identifying a plurality of sub-plans within the query plan;

(2) generating one or more equivalence classes for the query plan, wherein each equivalence class contains similar ones of the sub-plans;

(3) generating a transient view to answer all of the sub-plans in an associated one of the equivalence classes, wherein the transient view contains a union of results from all of the sub-plans in the associated one of the equivalence classes;

(4) utilizing a cost model to identify the transient views that improve the performance of the query plan; and

(5) applying filters to the identified transient views to obtain results for each sub-plan in the associated equivalence class.

11. The apparatus of claim 10, wherein the computer programs further comprise one or more computer programs for determning whether to materialize the transient view.

12. The apparatus of claim 10, wherein similar ones of the sub-plans contained in an equivalence class are identified by one or more properties.

13. The apparatus of claim 12, wherein the properties are selected from a property list comprised of one or more of the following:

tables in the plan, columns selected, join predicates, selection predicates, aggregation functions, columns in a GROUP BY list, data sources, a cost of executing the plan, and a number of result rows.

14. The apparatus of claim 13, wherein the computer programs further comprise one or more computer programs for:

generating a query that represents the transient view from the property list of the transient view;

optimizing the query; and

obtaining an execution plan, cost, and cardinality for the transient view.

15. The apparatus of claim 10, wherein the computer programs further comprise one or more computer programs for using the cost model to decide whether to materialize the transient view.

16. The apparatus of claim 10, wherein the sub-plans each have a scan type property, a table scanned property, a simple predicates property, and a columns selected property, wherein the computer programs further comprise one or more computer programs for using one or more of these properties to determine which of the sub-plans are similar.

18. The apparatus of claim 10, wherein the sub-plans each have an input plan property, and wherein the computer programs further comprise one or more computer programs for using this property to determine which of the sub-plans are similar.

17. The apparatus of claitn 10, wherein the sub-plans each have a join method property, a join predicates property, an outer plan property, and an inner plan property, and wherein the computer programs further comprise one or more computer programs for using one or more of these properties to determine which of the sub-plans are similar.

19. An article of manufacture comprising a computer program carrier readable by a computer and embodying one or more instructions executable by the computer to perform method steps of optimizimg one or more queries, the method comprising the steps of:

(a) identifying a plurality of sub-plans within the query;

plan;

(b) generating one or more equivalence classes for the query plan, wherein each equivalence class contains similar ones of the sub-plans;

(c) generating a transient view to answer all of the sub-plans in an associated one of the equivalence classes, wherein the transient view contains a union of results from all of the sub-plans in the associated one of the equivalence classes;

(d) utilizing a cost model to identify the transient views that improve the performance of the query plan; and

(e) applying filters to the identified transient views to obtain results for each sub-plan in the associated equivalence class.

20. The article of manufacture of claim 19, further comprising determining whether to materialize the transient view.

21. The article of manufacture of claim 19, wherein similar ones of the sub-plans contained in an equivalence class are identified by one or more properties.

22. The article of manufacture of claim 21, wherein the properties are selected from a property list comprised of one or more of the following:

tables in the plan, columns selected, join predicates, selection predicates, aggregation functions, columns in a GROUP BY list, data sources, a cost of executing the plan, and a number of result rows.

23. The article of manufacture of claim 22, further comprising:

generating a queryn that represents the transient view from the property list of the transient view;

optimzing the query; and

obtaining an execution plan, cost, and cardinality for the transient view.

24. The article of manufacture of claim 19, further comprising using the cost model to decide whether to materialize the transient view.

25. The article of manufacture of claim 19, wherein the sub-plans each have a scan type property, a table scanned property, a simple predicates property, and a columns selected property, further comprising the step of using one or more of these properties to determine which of the sub-plans are similar.

26. The article of manufacture of claim 19, wherein the sub-plans each have a join method property, a join predicates property, an outer plan property, and an inner plan property, and further comprising the step of using one or more of these properties to determine which of the sub-plans are similar.

27. The article of manufacture of claim 19, wherein the sub-plans each have an input plan property, and further comprising the step of using this property to determine which of the sub-plans are similar.