Path-caching mechanism to improve performance of path-related operations in a repository

• US 8,949,455 B2
• Filed: 11/21/2005
• Issued: 02/03/2015
• Est. Priority Date: 11/21/2005
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Idicula, Sam, Agarwal, Nipun, Murthy, Ravi, Sedlar, Eric
• Primary Examiner(s): Zele, Krista
• Assistant Examiner(s): FORMAN, JAMES Q
• Application Number:
  US11/284,521
• Publication Number:
  US 20070118561A1
• Time in Patent Office: 3,361 Days
• Field of Search: 707/10, 707/1, 707/3, 707/100, 702/2, 395/425, 709/238
• US Class Current: 709/238
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0817 using directory methods
• CPC Class Codes: G06F 12/0833 in combination with broadcast means (e.g. for invalidation or updating)
• CPC Class Codes: G06F 16/13 File access structures, e.g. distributed indices arrangements of input from, or output to, record carriers G06F3/06
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: G06F 16/972 Access to data in other repository systems, e.g. legacy data or dynamic Web page generation
• CPC Class Codes: G06F 2212/62 Details of cache specific to multiprocessor cache arrangements
• CPC Class Codes: G06F 2212/622 State-only directory, i.e. not recording identity of sharing or owning nodes
• CPC Class Codes: G06F 2212/7204 Capacity control, e.g. partitioning, end-of-life degradation

Abstract

A method and apparatus for processing path-based database operations is provided. According to one aspect, a path cache is maintained. For each hierarchical node that is traversed during a path-determining operation, it is determined whether a cache entry corresponding to that node is already contained in the path cache. If such a cache entry is already contained in the path cache, then the path indicated in that cache entry is used to complete the pathname for the node for which the operation is being performed. As a result, hierarchically higher nodes do not need to be traversed to complete the operation. Alternatively, if such a cache entry is not already contained in the path cache, then a cache entry for the node currently being traversed is generated and inserted into the path cache for use in subsequent path-determining operations.

Claims

1. A computer-implemented method of processing path-based operations, the method comprising:

in response to a request to determine a complete path to a requestor-specified first node, and upon determining that a path cache does not contain a first cache entry that specifies a complete path from a root node to the first node, which is an immediate child of a second node in a hierarchy of nodes, determining whether the path cache contains a second cache entry that specifies a complete path from the root node to the second node;

upon determining that the path cache does not contain the second cache entry, automatically determining a pathname that specifies the complete path from the root node to the second node and inserting, into the path cache, a particular cache entry that (a) corresponds to the second node and (b) indicates the pathname for the second node;

storing, in the particular cache entry, a first value that indicates a quantity of nodes that descend from the second node in the hierarchy; and

in response to a determination that at least one cache entry is to be evicted from the path cache, selecting the particular cache entry for eviction from the path cache based at least in part on the first value;

wherein the method is performed by one or more computing devices.

2. The method of claim 1, wherein the step of determining whether the path cache contains the second cache entry is performed in response to an execution, relative to a relational database, of a Structured Query Language (SQL) query whose results depend at least in part on the pathname.

3. The method of claim 1, wherein the step of determining whether the path cache contains the second cache entry is performed in response to an execution, relative to a relational database, of a Structured Query Language (SQL) query whose results depend at least in part on a determination of whether the first node is within a specified path in the hierarchy of nodes.

4. The method of claim 1, further comprising:

locating, in a relational database table, a first row that corresponds to the first node; and

locating, in the first row, an attribute that identifies a location, in the database table, of a second row that corresponds to the second node.

5. The method of claim 1, further comprising:

storing, in the particular cache entry, a second value that indicates a quantity of nodes that separate the second node from the root node in the hierarchy; and

in response to the determination that at least one cache entry is to be evicted from the path cache, selecting the particular cache entry for eviction from the path cache based at least in part on the second value.

6. The method of claim 5, wherein cache entries with higher second values are more likely to be selected for eviction than cache entries with lower second values.

7. The method of claim 1, further comprising:

in response to a descendant of the second node being added to or removed from the hierarchy, updating the first value in the particular cache entry.

8. The method of claim 1, further comprising:

in response to the determination that at least one cache entry is to be evicted from the path cache, selecting the particular cache entry for eviction from the path cache based at least in part on a value produced by dividing the first value by a total number of nodes in the hierarchy.

9. The method of claim 1, wherein the step of automatically determining the pathname that specifies the complete path from the root node to the second node further comprises:

determining the complete path from the root node to the second node based at least in part on information contained in a directory links table that contains, for at least one node in the hierarchy, an array storing multiple row identifiers of multiple parents of said at least one node in the hierarchy.

10. The method of claim 1, wherein cache entries with lower first values are more likely to be selected for eviction than cache entries with higher first values.

11. A volatile or non-volatile non-transitory computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform steps comprising:

in response to a request to determine a complete path to a requestor-specified first node, and upon determining that a path cache does not contain a first cache entry that specifies a complete path from a root node to the first node, which is an immediate child of a second node in a hierarchy of nodes, determining whether the path cache contains a second cache entry that specifies a complete path from the root node to the second node;

upon determining that the path cache does not contain the second cache entry, automatically determining a pathname that specifies the complete path from the root node to the second node and inserting, into the path cache, a particular cache entry that (a) corresponds to the second node and (b) indicates the pathname for the second node;

storing, in the particular cache entry, a first value that indicates a quantity of nodes that descend from the second node in the hierarchy; and

in response to a determination that at least one cache entry is to be evicted from the path cache, selecting the particular cache entry for eviction from the path cache based at least in part on the first value.

12. The computer-readable medium of claim 11, wherein the step of determining whether the path cache contains the second cache entry is performed in response to an execution, relative to a relational database, of a Structured Query Language (SQL) query whose results depend at least in part on the pathname.

13. The computer-readable medium of claim 11, wherein the step of determining whether the path cache contains the second cache entry is performed in response to an execution, relative to a relational database, of a Structured Query Language (SQL) query whose results depend at least in part on a determination of whether the first node is within a specified path in the hierarchy of nodes.

14. The computer-readable medium of claim 11, wherein the steps further comprise:

locating, in a relational database table, a first row that corresponds to the first node; and

locating, in the first row, an attribute that identifies a location, in the database table, of a second row that corresponds to the second node.

15. The computer-readable medium of claim 11, wherein the steps further comprise:

storing, in the particular cache entry, a second value that indicates a quantity of nodes that separate the second node from the root node in the hierarchy; and

in response to the determination that at least one cache entry is to be evicted from the path cache, selecting the particular cache entry for eviction from the path cache based at least in part on the second value.

16. The computer-readable medium of claim 15, wherein cache entries with higher second values are more likely to be selected for eviction than cache entries with lower second values.

17. The computer-readable medium of claim 11, wherein the steps further comprise:

in response to a descendant of the second node being added to or removed from the hierarchy, updating the first value in the particular cache entry.

18. The computer-readable medium of claim 11, wherein the steps further comprise:

in response to the determination that at least one cache entry is to be evicted from the path cache, selecting the particular cache entry for eviction from the path cache based at least in part on a value produced by dividing the first value by a total number of nodes in the hierarchy.

19. The computer-readable medium of claim 11, wherein the step of automatically determining the pathname that specifies the complete path from the root node to the second node further comprises:

determining the complete path from the root node to the second node based at least in part on information contained in a directory links table that contains, for at least one node in the hierarchy, an array storing multiple row identifiers of multiple parents of said at least one node in the hierarchy.

20. The computer-readable medium of claim 11, wherein cache entries with lower first values are more likely to be selected for eviction than cache entries with higher first values.