Techniques of XML query optimization over static and dynamic heterogeneous XML containers

• US 7,577,642 B2
• Filed: 07/13/2006
• Issued: 08/18/2009
• Est. Priority Date: 07/13/2006
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Krishnaprasad, Muralidhar, Liu, Zhen Hua
• Primary Examiner(s): Vo; Tim T
• Assistant Examiner(s): TRAN, ANHTAI V
• Application Number:
  US11/486,794
• Publication Number:
  US 20080016122A1
• Time in Patent Office: 1,132 Days
• Field of Search: 707/3, 707/103.R, 707/200
• US Class Current: 1/1
• CPC Class Codes: G06F 16/8365 Query optimisation
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure

Abstract

A method and apparatus for optimizing XML queries over heterogeneous XML tables is provided. A query that targets a container (e.g. table or collection) that contains a plurality of XML documents is received, wherein at least two XML documents in the plurality do not conform to the same schema. Based on the received query, a plurality of execution plans is generated. Each execution plan is associated with a different XML schema. An execution plan is used to execute the query relative to those XML documents that conform to the XML schema associated with the execution plan.

Claims

1. A method comprising the steps of:

receiving a database statement that targets a table that contains a plurality of XML documents, wherein at least two of the XML documents in the table do not conform to the same XML schema;

wherein the table comprises (a) a plurality of rows that each stores data for a different XML document and (b) a column that indicates, for each row, the schema to which the corresponding XML document conforms;

in response to receiving the database statement, generating a plurality of execution plans for said database statement;

wherein each execution plan of said plurality of execution plans corresponds to a different XML schema;

wherein each execution plan of the plurality of execution plans is optimized based on the XML schema to which said execution plan corresponds;

producing a plurality of intermediate results by using each execution plan, of the plurality of execution plans, to execute the database statement relative to only those XML documents, within the table, that conform to the XML schema associated with the execution plan;

wherein using said each execution plan to execute the database statement includes, for each row of two or more rows of the table, using one or more values from the column of the table to determine the XML schema to which the corresponding XML document conforms; and

generating a final result for the database statement based on the plurality of intermediate results;

wherein the steps are performed on one or more computing devices.

2. The method of claim 1, wherein:

the table is explicitly limited to a particular set of XML schemas; and

a database statement compiler generates the plurality of execution plans at compile time.

3. The method of claim 1, further comprising, after the database statement has been executed and before a subsequent database statement has been received, the steps of:

adding a new execution plan to the plurality of execution plans based on an addition of one or more XML documents to the plurality of XML documents; and

deleting an execution plan from the plurality of execution plans based on a deletion of one or more second XML documents from the plurality of XML documents.

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

determining that a particular XML schema has changed;

deleting, from the plurality of execution plans, an execution plan that corresponds to XML documents that conform to the particular XML schema; and

based on the particular XML schema, adding a new execution plan to the plurality of execution plans.

5. The method of claim 1, wherein generating a plurality of execution plans includes generating a second database statement that comprises the plurality of execution plans, wherein each execution plan of the plurality of execution plans is included in a separate CASE branch of the second database statement.

6. The method of claim 1, wherein:

generating the plurality of execution plans includes generating two or more database statements; and

the results of the two or more database statements are grouped by one or more union operators.

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

determining that an execution plan from the plurality of execution plans is capable of being optimized based on an index, wherein the key of the index is based, at least partially, on an XPath specified in the database statement; and

accessing the index during execution of the execution plan.

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

determining that a execution plan from the plurality of execution plans is capable of being optimized based on an index, wherein the key of the index is based, at least partially, on a specific schema; and

accessing the index during execution of the execution plan.

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

determining that a schema to which a particular subset of XML documents conform does not include an XPath specified in said database statement; and

determining to not generate a execution plan corresponding to said schema.

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

determining that a schema to which a particular subset of XML documents conform does not include an XPath specified in said database statement; and

determining to not execute the execution plan that corresponds to said schema.

11. The method of claim 1, further comprising the step of generating a cursor that includes an execution plan for each execution plan of the plurality of execution plans.

12. The method of claim 1, further comprising the step of generating a cursor for each execution plan of the one of the plurality of execution plans, wherein each cursor includes an execution plan for the corresponding execution plan.

13. The method of claim 1, wherein the database statement specifies a data manipulation language (DML) operation.

14. The method of claim 1, wherein generating the plurality of execution plans includes accessing one or more XML schemas to perform type checking, of one or more variables specified in the database statement, at compile time.

15. The method of claim 1, wherein the table is not explicitly limited to a particular set of XML schemas.

16. The method of claim 15, wherein:

the plurality of XML documents in the table conform to a plurality of XML schemas; and

the method further comprising the steps of, during execution time of the database statement;

identifying a particular schema of a particular XML document in the table;

generating an execution plan for the database statement relative to the particular schema; and

using the execution plan to process the database statement relative to the particular XML document.

17. The method of claim 16, wherein:

said particular XML document is a first XML document;

said particular schema is a first schema;

the method further comprising the steps of, during execution time of the database statement;

identifying a second schema of a second XML document in the table, wherein the second schema is different from the first schema;

generating the a second execution plan for the database statement relative to the second schema; and

using the second execution plan to process the database statement relative to the second XML document.

18. The method of claim 16, wherein:

said particular XML document is a first XML document;

said particular schema is a first schema;

the method further comprising the steps of, during execution time of the database statement;

after generating the execution plan associated with the first schema, storing the execution plan;

determining that a second XML document in the table conforms to the first schema;

retrieving the stored execution plan; and

using the execution plan to process the database statement relative to the second XML document.

19. A machine-readable storage medium storing instructions which, when executed by one or more processors, cause the one or more processors to perform the steps recited in claim 1.

20. A machine-readable storage medium storing instructions which, when executed by one or more processors, cause the one or more processors to perform the steps recited in claim 2.

21. A machine-readable storage medium storing instructions which, when executed by one or more processors, cause the one or more processors to perform the steps recited in claim 3.

22. A machine-readable storage medium storing instructions which, when executed by one or more processors, cause the one or more processors to perform the steps recited in claim 4.

23. A machine-readable storage medium storing instructions which, when executed by one or more processors, cause the one or more processors to perform the steps recited in claim 5.

24. A machine-readable storage medium storing instructions which, when executed by one or more processors, cause the one or more processors to perform the steps recited in claim 6.

25. A machine-readable storage medium storing instructions which, when executed by one or more processors, cause the one or more processors to perform the steps recited in claim 7.

26. A machine-readable storage medium storing instructions which, when executed by one or more processors, cause the one or more processors to perform the steps recited in claim 8.

27. A machine-readable storage medium storing instructions which, when executed by one or more processors, cause the one or more processors to perform the steps recited in claim 9.

28. A machine-readable storage medium storing instructions which, when executed by one or more processors, cause the one or more processors to perform the steps recited in claim 10.

29. A machine-readable storage medium storing instructions which, when executed by one or more processors, cause the one or more processors to perform the steps recited in claim 11.

30. A machine-readable storage medium storing instructions which, when executed by one or more processors, cause the one or more processors to perform the steps recited in claim 12.

31. A machine-readable storage medium storing instructions which, when executed by one or more processors, cause the one or more processors to perform the steps recited in claim 13.

32. A machine-readable storage medium storing instructions which, when executed by one or more processors, cause the one or more processors to perform the steps recited in claim 14.

33. A machine-readable storage medium storing instructions which, when executed by one or more processors, cause the one or more processors to perform the steps recited in claim 15.

34. A machine-readable storage medium storing instructions which, when executed by one or more processors, cause the one or more processors to perform the steps recited in claim 16.

35. A machine-readable storage medium storing instructions which, when executed by one or more processors, cause the one or more processors to perform the steps recited in claim 17.

36. A machine-readable storage medium storing instructions which, when executed by one or more processors, cause the one or more processors to perform the steps recited in claim 18.

37. A method comprising the steps of:

receiving a database statement that targets a container that contains a plurality of XML documents, wherein at least two of the XML documents in the container do not conform to the same XML schema;

in response to receiving the database statement, generating a plurality of execution plans for said database statement;

wherein each execution plan of said plurality of execution plans corresponds to a different XML schema;

wherein each execution plan of the plurality of execution plans is optimized based on the XML schema to which said execution plan corresponds;

producing a plurality of intermediate results by using each execution plan, of the plurality of execution plans, to execute the database statement relative to those XML documents, within the container, that conform to the XML schema associated with the execution plan;

generating a final result for the database statement based on the plurality of intermediate results; and

maintaining a set of statistics that indicate, for each schema in a plurality of schemas, a number of XML documents in the plurality of XML documents that conform to said each schema;

wherein the set of statistics are generated by performing one or more of the following;

(a) executing a query against the container to determine the number of XML documents in the plurality of XML documents that conform to said each schema, or

(b) for each schema of the plurality of schemas, incrementing a count that corresponds to said each schema when a new XML document that conforms to said each schema is added to the container and decrementing said count when an XML document, of the plurality of documents, that conforms to said each schema is deleted from the container;

wherein the steps are performed on one or more computing devices.

38. The method of claim 37, further comprising performing at least one of the following steps based on the set of statistics:

deleting a execution plan from the plurality of execution plans;

or

adding a new execution plan to the plurality of execution plans.

39. The method of claim 37, wherein the plurality of XML documents are stored in at least one of the following:

a table, a collection, a folder, a virtual folder, a directory, a view, a function, and a stream of documents.

40. The method of claim 37, wherein the container is not explicitly limited to a particular set of XML schemas.

41. A machine-readable storage medium storing instructions which, when executed by one or more processors, cause the one or more processors to perform the steps recited in claim 40.

42. A machine-readable storage medium storing instructions which, when executed by one or more processors, cause the one or more processors to perform the steps recited in claim 37.

43. A machine-readable storage medium storing instructions which, when executed by one or more processors, cause the one or more processors to perform the steps recited in claim 38.

44. A machine-readable storage medium storing instructions which, when executed by one or more processors, cause the one or more processors to perform the steps recited in claim 39.