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

• US 20070118561A1
• Filed: 11/21/2005
• Published: 05/24/2007
• Est. Priority Date: 11/21/2005
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Sedlar, Eric, Idicula, Sam, Murthy, Ravi, Agarwal, Nipun
• Granted Patent: US 8,949,455 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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:

upon determining that a path cache does not contain a first cache entry for a first node that descends from a second node in a hierarchy of nodes, determining whether the path cache contains a second cache entry that corresponds to the second node;

if the path cache contains the second cache entry, then automatically generating, based at least in part on a first pathname that is indicated in the second cache entry, a second pathname for the first node; and

if the path cache does not contain the second cache entry, then automatically determining a pathname for the second node and inserting, into the path cache, a cache entry that (a) corresponds to the second node and (b) indicates the pathname for the second node.

2. The method of claim 1, wherein the step of automatically determining the pathname for the second node comprises:

determining whether the path cache contains a third cache entry that corresponds to a third node from which the second node descends in the hierarchy;

if the path cache contains the third cache entry, then automatically generating the pathname for the second node based at least in part on a third pathname that is indicated in the third cache entry; and

if the path cache does not contain the third cache entry, then automatically determining a pathname for the third node and inserting, into the path cache, a cache entry that (a) corresponds to the third node and (b) indicates the pathname for the third node.

3. The method of claim 1, further comprising:

inserting, into the path cache, a cache entry that (a) corresponds to the first node and (b) indicates the second pathname.

4. The method of claim 1, wherein the step of automatically determining the pathname for the second node comprises:

in a first recursive iteration of a procedure, determining a third node from which the second node depends in the hierarchy of nodes;

in the first recursive iteration of the procedure, passing an identity of the third node as a parameter in an invocation of a second recursive iteration of the procedure;

in the second recursive iteration of the procedure, determining whether the path cache contains a third cache entry that corresponds to the third node;

in the second recursive iteration of the procedure, in response to determining that the path cache contains the third cache entry, returning, to the first recursive iteration of the procedure, a third pathname that is indicated in the third cache entry; and

in the first recursive iteration of the procedure, generating the pathname for the second node by appending a node name of the second node to the third pathname.

5. The method of claim 4, wherein the step of inserting, into the path cache, the cache entry that (a) corresponds to the second node and (b) indicates the pathname for the second node comprises:

in the first recursive iteration of the procedure, inserting, into the path cache, the cache entry that (a) corresponds to the second node and (b) indicates the pathname for the second node.

6. The method of claim 4, further comprising:

in the first recursive iteration of the procedure, returning, to an entity that invoked the first recursive iteration of the procedure, the pathname for the second node.

7. The method of claim 1, further comprising:

determining whether a fullness of the path cache exceeds a specified threshold;

in response to a determination that the fullness of the path cache exceeds the specified threshold, selecting a particular cache entry from among cache entries in the path cache; and

removing the particular cache entry from the path cache;

wherein the step of selecting the particular cache entry comprises selecting the particular cache entry based at least in part on a number of times that the particular cache entry was accessed.

8. The method of claim 1, further comprising:

determining whether a fullness of the path cache exceeds a specified threshold;

in response to a determination that the fullness of the path cache exceeds the specified threshold, selecting a particular cache entry from among cache entries in the path cache; and

removing the particular cache entry from the path cache;

wherein the step of selecting the particular cache entry comprises selecting the particular cache entry based at least in part on an amount of time that has passed since the particular cache entry was accessed.

9. The method of claim 1, further comprising:

determining whether a fullness of the path cache exceeds a specified threshold;

in response to a determination that the fullness of the path cache exceeds the specified threshold, selecting a particular cache entry from among cache entries in the path cache; and

removing the particular cache entry from the path cache;

wherein the step of selecting the particular cache entry comprises selecting the particular cache entry based at least in part on a quotient that is produced by dividing (a) a number of other nodes that descend from a particular node that corresponds to the particular cache entry by (b) a number of total nodes in the hierarchy of nodes.

10. 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 of a database query whose results depend at least in part on the second pathname.

11. 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 of a database 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.

12. The method of claim 1, further comprising:

locating, in a 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.

13. 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.

14. 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.

15. 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.

16. 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.

17. 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.

18. 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.

19. 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.

20. 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.

21. 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.

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 10.

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 11.

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 12.