Cost-based optimizer for an XML data repository within a database

• US 20050240624A1
• Filed: 04/21/2004
• Published: 10/27/2005
• Est. Priority Date: 04/21/2004
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Sedlar, Eric, Chandrasekar, Sivasankaran, Murthy, Ravi, Agarwal, Nipun, Ge, Fei
• Granted Patent: US 7,930,277 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/8365 Query optimisation

Abstract

Cost-based optimizer functionality for an XML database repository provides means for optimizing the execution of database queries that access XML resources in the database repository. Statistics about XML resources that are stored in the database repository are gathered, stored and utilized by a query optimizer to compute computational costs associated with each of multiple methods of accessing particular XML resources requested in a database query. Hence, the optimizer is able to select the most efficient query execution plan based on the costs of possible access paths. In one embodiment, specific statistics about the hierarchical structure of XML resources stored in the XML database repository are gathered, stored in a relational table in the database management system, and used to compute the selectivity of query predicates and the index cost associated with traversing one or more indexes to access requested XML resources.

Claims

1. A method comprising the computer-implemented steps of:

gathering statistics about XML resources that are stored in a database repository;

storing said statistics; and

in response to a request for access to one or more XML resources from said database repository, computing a computational cost associated with each of one or more methods of accessing said one or more XML resources from said database repository, based on said statistics.

2. The method of claim 1, wherein said XML resources are logically organized in a hierarchy of nodes in which each node is either a container or a resource, and

wherein the step of gathering statistics comprises gathering one or more data from a group consisting of

a total number of nodes in said hierarchy that are accessible via a path through a specified node,

a total number of containers in said hierarchy that are accessible via a path through said specified node,

a total number of nodes in said hierarchy that are accessible via a path through said specified node and that are in a level of said hierarchy that is immediately under a level of said specified node,

a total number of containers in said hierarchy that are accessible via a path through said specified node and that are in a level of said hierarchy that is immediately under said level of said specified node, and

a number of levels from a root node of said hierarchy, at which said specified node is organized in said hierarchy.

3. The method of claim 1, wherein said XML resources are logically organized in a hierarchy of nodes in which each node is either a container or a resource, and

wherein the step of gathering statistics comprises gathering each of

a total number of nodes in said hierarchy that are accessible via a path through a specified node,

a total number of containers in said hierarchy that are accessible via a path through said specified node,

a total number of nodes in said hierarchy that are accessible via a path through said specified node and that are in a level of said hierarchy that is immediately under a level of said specified node,

a total number of containers in said hierarchy that are accessible via a path through said specified node and that are in a level of said hierarchy that is immediately under said level of said specified node, and

a number of levels from a root node of said hierarchy, at which said specified node is organized in said hierarchy.

4. The method of claim 1, wherein the step of storing statistics comprises storing said statistics in a relational table of a database of which said database repository is part.

5. The method of claim 4, wherein said relational table is a first relational table that is a different table than a second relational table in which said XML resources are stored in said database repository.

6. The method of claim 4, wherein said relational table is a relational table in which said XML resources are stored in said database repository.

7. The method of claim 1, wherein the step of storing statistics comprises storing said statistics in a hierarchical index table in which said XML resources are indexed to said database repository.

8. The method of claim 1, wherein the step of computing a computational cost comprises computing a selectivity value for each of one or more predicates, from said request, that contain operators on said database repository.

9. The method of claim 8, wherein each of said XML resources is logically organized in a hierarchy of nodes and stored, in association with a location of said XML resource in said hierarchy, in a column of a table in said database repository, and wherein said operator is an operator that determines whether a particular XML resource can be located in said database repository through a particular specified path through a portion of said hierarchy.

10. The method of claim 8, wherein each of said XML resources is logically organized in a hierarchy of nodes and stored, in association with a location of said XML resource in said hierarchy, in a column of a table in said database repository, and wherein said operator is an operator that determines whether a particular XML resource can be located in said database repository at a terminal location of a particular specified path through a portion of said hierarchy.

11. The method of claim 1, wherein the step of computing a computational cost comprises computing a computational cost of traversing, to locate a particular XML resource specified in said request, an index in which said XML resources are indexed to said database repository.

12. The method of claim 11, wherein computing said computational cost of traversing an index comprises computing a computational cost associated with one or more CPUs used for said traversing.

13. The method of claim 11, wherein computing said computational cost of traversing an index comprises computing a computational cost associated with reading data blocks in which portions of said index are stored.

14. The method of claim 11, wherein computing said computational cost of traversing an index comprises computing (a) a computational cost associated with one or more CPUs used for said traversing and (b) a computational cost associated with reading data blocks in which portions of said index are stored.

15. The method of claim 1, wherein the step of computing a computational cost comprises (a) computing a selectivity value for each of one or more predicates, from said request, that contain operators on said database repository and (b) computing a computational cost of traversing, to locate a particular XML resource specified in said request, an index in which said XML resources are indexed to said database repository.

16. The method of claim 1, wherein said request for access to one or more XML resources from said database repository is a SQL query.

17. The method of claim 16, wherein each of said XML resources is logically organized in a hierarchy of nodes and stored, in association with a location of said XML resource in said hierarchy, in a column of a table in said database repository, and wherein said SQL query comprises a mechanism for providing one possible path through said hierarchy to each of said XML resources.

18. The method of claim 17, wherein the step of computing a computational cost comprises computing a computational cost component for one or more predicates, from said request, that contain an operator in conjunction with said mechanism acting on said database repository.

19. The method of claim 16, wherein each of said XML resources is logically organized in a hierarchy of nodes and stored, in association with a location of said XML resource in said hierarchy, in a column of a table in said database repository, and wherein said SQL query comprises a mechanism for providing all possible paths through said hierarchy to each of said XML resources.

20. The method of claim 19, wherein the step of computing a computational cost comprises computing a computational cost component for one or more predicates, from said request, that contain an operator in conjunction with said mechanism acting on said database repository.

21. The method of claim 1, wherein said database repository is part of a relational database management system.

22. A computer-readable 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 method comprising the computer-implemented steps of:

gathering, by a database management system, statistics about XML resource that are stored in a repository of said database management system; and

storing said statistics in said database management system.

39. The method of claim 38, wherein the step of storing comprises storing said statistics as XML data type in a schema-based table in said database management system.

40. The method of claim 38, wherein said XML resources are logically organized in a hierarchy of nodes in which each node is either a container or a resource, and

wherein the step of gathering statistics comprises gathering each of

a total number of nodes in said hierarchy that are accessible via a path through a specified node,

a total number of containers in said hierarchy that are accessible via a path through said specified node,

a total number of nodes in said hierarchy that are accessible via a path through said specified node and that are in a level of said hierarchy that is immediately under a level of said specified node, and

a total number of containers in said hierarchy that are accessible via a path through said specified node and that are in a level of said hierarchy that is immediately under said level of said specified node.

41. A computer-readable 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 38.

42. A method comprising the computer-implemented steps of:

in response to a request for access to one or more XML resources from a database repository within a database management system,

accessing, from said database management system, statistics about the structure of a hierarchy in which said one or more XML resources are logically organized; and

computing a computational cost associated with each of one or more methods of accessing said one or more XML resources from said database repository, based on said statistics.

43. The method of claim 42, wherein the step of computing a computational cost comprises computing a selectivity value for each of one or more predicates, from said request, that contain operators on said database repository.

44. The method of claim 42, wherein the step of computing a computational cost comprises computing a computational cost of traversing, to locate particular XML resources specified in said request, an index in which said XML resources are indexed to said database repository.

45. The method of claim 42, wherein the step of computing a computational cost comprises (a) computing a selectivity value for each of one or more predicates, from said request, that contain operators on said database repository and (b) computing a computational cost of traversing, to locate a particular XML resource specified in said request, an index in which said XML resources are indexed to said database repository.

46. A computer-readable 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 42.

47. A database system comprising:

an XML data repository within a relational database management system; and

a query optimizer that receives a database query and, in response to said query, formulates a query execution plan based on computational costs of access paths associated with XML data stored in said repository, wherein said computational costs are based on statistics about an organizational structure of said XML data.

48. A system comprising:

means for gathering statistics about XML resources that are stored in a database repository;

means for storing said statistics; and

means for computing, in response to a request for access to one or more XML resources from said database repository and based on said statistics, a computational cost associated with each of one or more methods of accessing said one or more XML resources from said database repository.