Reusing optimized query blocks in query processing

• US 7,246,108 B2
• Filed: 07/27/2004
• Issued: 07/17/2007
• Est. Priority Date: 07/27/2004
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Ahmed, Rafi
• Primary Examiner(s): Cottingham; John
• Assistant Examiner(s): Lu; Kuen S.
• Application Number:
  US10/901,272
• Publication Number:
  US 20060026115A1
• Time in Patent Office: 1,085 Days
• Field of Search: 707/2, 707/3, 709/101
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24535 of sub-queries or views
• 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/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

Techniques for reusing optimized query blocks in query processing are provided. The techniques include checking a data structure to determine whether a previously-generated query block information record corresponding to an already-processed first inner query block exists in the data structure, where the already-processed first inner query block corresponds to the first inner query block in a first state in an already-processed form. If the previously-generated query block information record exists in the data structure, then query block information is established for the first inner query block in the first state based on the previously-generated query block information record. Then a cost is determined for a semantically equivalent query that includes the first inner query block in the first state based on the query block information for the first inner query block in the first state.

Claims

1. A method of processing a query that comprises an outer query and a first inner query block, comprising the machine-implemented steps of:

checking a data structure to determine whether a previously-generated query block information record corresponding to an already-processed first inner query block exists in the data structure, wherein the already-processed first inner query block corresponds to the first inner query block in a first state in an already-processed form;

if the previously-generated query block information record exists in the data structure, then establishing query block information for the first inner query block in the first state based on the previously-generated query block information record;

if the previously-generated query block information record does not exist in the data structure, then generating and storing the query block information, for the first inner query block in the first state, in a newly-generated query block information record in the data structure; and

based on the query block information for the first inner query block in the first state, determining a cost for a semantically equivalent query that includes the first inner query block in the first state;

wherein the semantic equivalent query is one of a plurality of semantically equivalent queries for which costs are determined; and

based on the costs, selecting and executing one of the plurality of semantically equivalent queries.

2. The method of claim 1, wherein the previously-generated query block information record comprises a memory pointer to a previously-generated, in-memory representation of the already-processed first inner query block;

and wherein the step of determining the cost for the semantically equivalent query comprises;

incorporating the previously-generated, in-memory representation of the already-processed first inner query block into an in-memory representation of the semantically equivalent query by using the memory pointer to the previously-generated in-memory representation of the already-processed first inner query block;

determining the cost for the semantically equivalent query based on the in-memory representation of the semantically equivalent query, wherein the in-memory representation of the semantically equivalent query comprises the previously-generated in-memory representation of the already-processed first inner query block.

3. The method of claim 2, wherein the in-memory representation of the semantically equivalent query already includes an in-memory representation of the first inner query block in non-processed form;

and

wherein the step of incorporating comprises;

replacing the in-memory representation of the first inner query block in non-processed form with the previously-generated, in-memory representation of the already-processed first inner query block.

4. The method of claim 1, further comprising the steps of:

if the previously-generated query block information record does not exist in the data structure;

processing the first inner query block in the first state to produce the already-processed first inner query block;

determining a newly-generated query block information, wherein said newly-generated query block information is associated with the already-processed first inner query block; and

establishing the query block information for the first inner query block in the first state based on said newly-generated query block information.

5. The method of claim 1, wherein the first inner query block is a subquery.

6. The method of claim 5, wherein the subquery in the first state comprises the subquery nested in the query.

7. The method of claim 5, wherein the subquery in the first state comprises the subquery unnested into an inline view in the query.

8. The method of claim 5, further comprising the step of generating the semantically equivalent query with the subquery in the first state, including:

unnesting the subquery in the outer query, resulting in an inline view; and

merging the inline view into the query.

9. The method of claim 1, wherein the first inner query block is a view.

10. The method of claim 9, wherein the view in the first state comprises the view unmerged in the query.

11. The method of claim 9, wherein the view in the first state comprises the view merged into the query.

12. The method of claim 9, wherein the view in the first state comprises a predicate from the outer query pushed into the view.

13. The method of claim 1, wherein the method further comprises the steps of:

checking the data structure to determine whether a second previously-generated query block information record corresponding to a second already-processed first inner query block exists in the data structure, wherein the second already-processed first inner query block corresponds to the first inner query block in a second state in an already-processed form;

if the second previously-generated query block information record exists in the data structure, then;

establishing query block information for the first inner query block in the second state based on the second previously-generated query block information record.

14. The method of claim 13, further comprising the steps of:

if the second previously-generated query block information record does not exist in the data structure;

processing the first inner query block in the second state to produce the second already-processed first inner query block;

determining second newly-generated query block information associated with the second already-processed first inner query block; and

establishing the query block information for the first inner query block in the second state based on said second newly-generated query block information.

15. The method of claim 14, further comprising the steps of:

if the second previously-generated query block information record does not exist in the data structure, then;

storing said second newly-generated query block information in a second newly-generated query block information record in the data structure.

16. The method of claim 1, wherein the steps of claim 1 are performed for each semantically equivalent query of two or more queries that are semantically equivalent to the query;

and wherein the step of selecting one of the plurality of semantically equivalent queries further comprises;

choosing, as a particular query, a semantically equivalent query with the lowest cost from among the two or more queries that are semantically equivalent to the query.

17. The method of claim 16, further comprising, after executing the particular query, providing the results of the executing step to a sender of the query.

18. The method of claim 16, wherein the two or more queries comprise all semantically equivalent queries that can be generated by a query-processing unit.

19. The method of claim 16, wherein the two or more queries comprise all candidate queries determined by a linear selection technique or an iterative selection technique.

20. The method of claim 1, wherein the first state is one of multiple, available states.

21. The method of claim 13, wherein each of the first state and the second state is one of multiple, available states;

and wherein the first state is different from the second state.

22. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 1.

23. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 2.

24. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 3.

25. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 4.

26. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 5.

27. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 6.

28. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 7.

29. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 8.

30. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 9.

31. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 10.

32. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 11.

33. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 12.

34. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 13.

35. A computer-readable storage medium carrying one or more sequences of instructions which when executed by one or more processors, causes the one or more processors to perform the method recited in claim 14.

36. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 15.

37. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 16.

38. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 17.

39. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 18.

40. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 19.

41. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 20.

42. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 21.