REGISTER  |  SIGN IN
United States Patent6073129
Levine , ; et al.June 6, 2000
Title
Method and apparatus for improving the performance of a database management system through a central cache mechanism
Abstract
A host system includes a multicache system configured within the host system's memory which has a plurality of local and central cache systems used for storing information being utilized by a plurality of processes running on the system. Persistent shared memory is used to store control structure information entries required for operating central cache systems for substantially long periods of time in conjunction with the local caches established for the processes. Such entries includes a descriptor value for identifying a directory control structure and individual sets of descriptors for identifying a group of control structures defining those components required for operating the configured central cache systems. The cache directory structure is used for defining the name of each configured central cache system and for providing an index value identifying the particular set of descriptors associated therewith. The multicache system also includes a plurality of interfaces for configuring the basic characteristics of both local and central cache systems as a function of the type and performance requirements of application processes being run.
Inventors:Levine; Donald P. (Glendale, AZ), Egolf; David A.  (Glendale, AZ)
Assignee:Bull HN Information Systems Inc. (Billerica, MA)
Appl. No.:999248
Filed:December 29, 1997
Current U.S. Class:707/4 707/10 707/2 
Field of Search:711/122,144,121,140,164,119 707/101,10,3,4,2,103,5 379/207
U.S. Patent Documents
5023776June 1991Gregor
5222224June 1993Flynn et al.
5249282September 1993Segers
5276848January 1994Gallagher et al.
5617568April 1997Ault et al.
5692152November 1997Cohen et al.
5737575April 1998Blaner
5752264May 1998Blake et al.
5812996September 1998Rubin et al.
5822749October 1998Agarwal
5835908November 1998Bennett et al.
5875462February 1999Bauman et al.
5915249June 1999Spencer
5974129October 1999Bodnar
Primary Examiner: Amsbury; Wayne
Assistant Examiner: Pardo; Thuy
Attorney, Agent or Firm:Driscoll; Faith F. Solakian; John S.
Claims

What is claimed is:
1. A multicache system configurable within a primary memory of a host system for improving the performance of a number of processes running on the host system in processing complex database query statements, the multicache system comprising:
(a) a plurality of local caches in main memory corresponding to the number of processes being run on the host system, each local cache being associated with a different one of the processes being run; and
(b) at least one configured central cache system located in a predefined area of primary memory shared by the processes, the central cache system being operatively coupled to each of the plurality of local cache systems associated therewith, said central cache system including:
a number of shared control structures used for controlling access to the central cache system;
a number of sets of central cache control structures corresponding to the number of central caches configured for storing code segments; and,
a control mechanism operatively coupled to the number of shared control structures and to the number of sets of central cache structures, the control mechanism being operative to control the configuration and operation of each of the central caches so that generated code segments produced by any one of the processes for executing a complex database query statement are stored automatically in the local cache associated with the process and in the central cache configured to be associated therewith for use by other processes associated with the same central cache in processing logically equivalent complex database query statements.

2. The system of claim 1 wherein the host system further includes a number of interfaces which operatively couple to the central cache system for configuring and operating the number of central caches.

3. The system of claim 2 wherein the multicache system further includes a cache utility program component operatively coupled to receive utility directives entered into the system by a user and operatively coupled to the central cache system, the cache utility program component operatively coupled to a first one of the number of interfaces, the cache utility program component in response to the user initiated directives being operative to issue utility functions for invoking the control mechanism to perform a sequence of operations for carrying out the specified functions.

4. The system of claim 3 wherein the utility directives include commands for specifying clearing, creating and deleting central caches within the central cache system.

5. The system of claim 2 wherein the host system includes a configuration file for storing user entered configuration parameters defining the characteristics of the central caches to be configured, the number of interfaces including a second interface operatively coupled to the configuration file and to the central cache system, the second interface being operative when a process is put in execution to invoke the control mechanism for storing parameter information in specific ones of the shared control structures and into a specified one of the number of sets of central cache control structures derived from the configuration file.

6. The system of claim 5 wherein the configuration parameters include a central cache name parameter for specifying the central cache to be used and a use central cache parameter specifying if processes are to access code segments in central cache.

7. The system of claim 5 wherein the second interface operatively couples to the plurality of local caches and wherein the configuration parameters include a max local cache entries parameter for defining a maximum number of entries to be cached simultaneously in a local cache and a max local cache words parameter defining a maximum number of words to be used by a local cache.

8. The system of claim 2 wherein the number of interfaces includes a third interface operatively coupled to receive internal commands generated by a process during the processing of database query statements, the third interface being operatively coupled to the central cache system of invoking the control mechanism to carry out those operations required for executing the internal commands.

9. The system of claim 8 wherein the internal commands include an insert command, a delete command, a find command, a clear command and a print info command.

10. The system of claim 2 wherein the number of interfaces includes a fourth interface operatively coupled to receive command calls from processes running on the host system, the fourth interface being operatively coupled to the central cache system and operative in response to the command calls invoke the control mechanism for carrying out operations specified by the command calls.

11. The system of claim 10 wherein the command calls include a generate central report command call used for generating statistics for the central cache system and a reset central statistics command call used for resetting statistics for the central cache system.

12. The system of claim 1 wherein the central cache system includes a persistent memory segment for storing the shared control structures, the memory including a number of memory sections, each section being associated with a different configured central cache and each section including first descriptor values for identifying one of the shared control structures corresponding to a directory control store structure and a set of descriptors for identifying one of the number of sets of central cache structures defining those components required for operating the configured central cache associated therewith.

13. The system of claim 12 wherein the directory control structure includes a number of indexed entry locations, each location for storing a value defining a name identifier for a set of central cache control structures for operating a configured central cache and for defining an index value identifying the set of descriptors associated with the configured central cache.

14. The system of claim 13 wherein the set of control structures includes:
a cache data structure for defining the characteristics of the central cache, a bucket structure, a cnode structure and a code descriptor structure for accessing code segments in the central cache associated therewith.

15. The system of claim 1 wherein the complex database query statements are SQL statements used for accessing relational database facilities of the host system and wherein the generated code correspond to the statements for executing the query statements.

16. The system of claim 1 wherein the shared control structures are stored in a predefined area of memory which is inaccessible by the processes running on the host system and which endures for a substantially long period of time.

17. The system of claim 12 wherein the memory segment further includes a separate section for storing a number of pairs of descriptors sequentially allocated to each configured central cache during the configuration thereof, each allocated pair of descriptors providing information to straggling processes pertaining to the central caches associated therewith for enabling the processes to detect that a central cache has been deleted from the central cache system.

18. A method of organizing a multicache system within a primary memory of a host system for improving the performance of a number of processes running on the host system in processing complex database query statements, the multicache system including a plurality of local caches in main memory corresponding to the number of processes being run on the host system, each local cache being associated with a different one of the processes being run, the method comprising the steps of:
(a) configuring at least one configured central cache system in a predefined area of primary memory shared by the processes, the central cache system being operatively coupled to each of the plurality of local cache systems associated therewith;
(b) including in the central cache system, a number of shared control structures used for controlling access thereto;
(c) including in the central cache system, a number of sets of central cache control structures corresponding to the number of central caches configured for storing code segments; and,
(d) including in the central cache system, a control mechanism operatively coupled to the number of shared control structures and to the number of sets of central cache structures, the control mechanism being operative to control the configuration and operation of each of the configured central caches so that generated code segments produced by any one of the processes for executing a complex database query statement are stored automatically in the local cache associated with the process and in the central cache associated therewith for use by other processes configured to be associated with the same central cache in processing logically equivalent complex database query statements.

19. The method of claim 18 further including the step of:
(e) including in the host system, a number of interfaces that operatively couple to the central cache system for configuring and operating the number of central caches.

20. The method of claim 19 wherein the method further includes the steps of:
including a cache utility program component operatively coupled to receive utility directives entered into the system by a user and operatively coupled to the control central cache system; operatively coupling the cache utility program component to a first one of the number of interfaces; and,
issuing utility functions by the cache utility program component in response to the user initiated directives for invoking the control mechanism to perform a sequence of operations for carrying out the specified functions.

21. The method of claim 20 wherein the utility directives include commands for specifying clearing, creating and deleting central caches within the central cache system.

22. The method of claim 19 wherein the host system includes a configuration file for storing user entered configuration parameters defining the characteristics of the central caches to be configured and the method further includes the steps of:
operatively coupling a second one of the interfaces to the configuration file and to the central cache system; invoking the control mechanism by the second interface when a process is put in execution for storing parameter information in specific ones of the shared control structures and into a specified one of the number of sets of central cache control structures derived from the configuration file.

23. The method of claim 22 wherein the configuration parameters include a central cache name parameter for specifying the central cache to be used and a use central cache parameter specifying if processes are to access code segments in central cache.

24. The method of claim 22 wherein the method further includes the step of operatively coupling the second interface to the plurality of local caches and wherein the configuration parameters include a max local cache entries parameter for defining a maximum number of entries to be cached simultaneously in a local cache and a max local cache words parameter defining a maximum number of words to be used by a local cache.

25. The method of claim 19 wherein the method further includes the steps of:
including a third one of the interfaces which operatively couples to receive internal commands generated by a process during the processing of database query statements; and
operatively coupling the third interface to the central cache system for invoking the control mechanism to carry out those operations required for executing the internal commands.

26. The method of claim 25 wherein the internal commands include an insert command, a delete command, a find command, a clear command and a print info command.

27. The method of claim 19 wherein the method further includes the steps of:
including a fourth one of the interfaces that operatively couples to receive command calls from processes running on the host system; and
operatively coupling the fourth interface to the central cache system for invoking the control mechanism in response to the command calls for carrying out operations specified by the command calls.

28. The method of claim 27 wherein the command calls include a generate central report command call used for generating statistics for the central cache system and a reset central statistics command call used for resetting statistics for the central cache system.

29. The method of claim 18 wherein the method further includes:
utilizing a persistent memory segment in the central cache system for storing the shared control structures, the memory segment including a number of memory sections, each section being associated with a different configured central cache and each including first descriptor values for identifying one of the shared structures corresponding to a directory control store structure and a set of descriptors for identifying one of the number of sets of central cache structures defining those components required for operating the configured central cache associated therewith.

30. The method of claim 29 wherein the directory control structure includes a number of indexed entry locations, each location for storing a value defining a name identifier for a set of central cache control structures for operating a configured central cache and for defining an index value
identifying the set of descriptors associated with the configured central cache.

31. The method of claim 30 wherein the set of control structures includes:
a cache data structure for defining the characteristics of the central cache, a bucket structure, a cnode structure and a code descriptor structure for accessing code segments in the central cache associated therewith.

32. The method of claim 29 wherein the method further includes the steps of:
utilizing a separate section for storing a number of pairs of descriptors sequentially allocated to each configured central cache during the configuration thereof, each allocated pair of descriptors providing information to straggling processes pertaining to the central caches associated therewith for enabling the processes to detect that a central cache has been deleted from the central cache system.

33. A computer main memory containing a number of segments for storing data and control structures for improving the performance of a number of processes on a host system in processing complex database query statements, the data and control structures comprising:
(a) a plurality of local caches in a corresponding number of main memory segments corresponding to the number of processes being run on the host system, each local cache being associated with a different one of the processes being run; and
(b) at least one configured central cache system located in a predefined area of another one of the segments of main memory shared by the processes, the central cache system being operatively coupled to each of the plurality of local cache systems associated therewith, said central cache system including:
a number of shared control structures used for controlling access to the central cache system; and,
a number of sets of central cache control structures corresponding to the number of central caches configured for storing code segments; the sets of central cache structures enabling configuration and operation of each of the central caches so that generated code segments produced by any one of the processes for executing a complex database query statement are stored automatically in the local cache associated with the process and in the central cache configured to be associated therewith for use by other processes associated with the same central cache in processing logically equivalent complex database query statements.

34. A multicache system configurable within a primary memory of a host system for improving the performance of a number of processes running on the host system in processing complex database query statements, the multicache system comprising:
(a) a plurality of local caches in main memory corresponding to the number of processes being run on the host system, each local cache being associated with a different one of the processes being run; and
(b) at least one configured central cache system located in a shared predefined area of primary memory, the central cache system being operatively coupled to each of the plurality of local cache systems associated therewith, said central cache system including:
a number of shared control structures used for controlling access to the central cache system;
a number of sets of central cache control structures corresponding to the number of central caches configured for storing code segments; and,
a control mechanism operatively coupled to the number of shared control structures and to the number of sets of central cache structures, the control mechanism being operative to control the configuration and operation of each of the central caches so that generated code segments produced by any one of the processes for executing a complex database query statement are automatically stored in the local cache associated with the process and in the configured central cache associated therewith for use by other processes associated with the same central cache in processing logically equivalent complex database query statements;
(c) a number of interfaces which operatively couple to the central cache system for configuring and operating the number of central caches; and,
(d) a cache utility program component operatively coupled to receive utility directives entered into the system by a user and operatively coupled to the central cache system, the cache utility program component being operatively coupled to a first one of the number of interfaces, the cache utility program component in response to the user initiated directives being operative to issue utility functions for invoking the control mechanism to perform a sequence of operations for carrying out the specified functions.

35. A multicache system configurable within a primary memory of a host system for improving the performance of a number of processes running on the host system in processing complex database query statements, the multicache system comprising:
(a) a plurality of local caches in main memory corresponding to the number of processes being run on the host system, each local cache being associated with a different one of the processes being run; and
(b) at least one configured central cache system located in a shared predefined area of primary memory, the central cache system being operatively coupled to each of the plurality of local cache systems associated therewith, said central cache system including:
a number of shared control structures used for controlling access to the central cache system;
a number of sets of central cache control structures corresponding to the number of central caches configured for storing code segments; and,
a control mechanism operatively coupled to the number of shared control structures and to the number of sets of central cache structures, the control mechanism being operative to control the configuration and operation of each of the central caches so that generated code segments produced by any one of the processes for executing a complex database query statement are automatically stored in the local cache associated with the process and in the configured central cache associated therewith for use by other processes associated with the same central cache in processing logically equivalent complex database query statements;
(c) a number of interfaces which operatively couple to the cell cache system for configuring and operating the number of central caches; and,
(d) a configuration file for storing user entered configuration parameters defining the characteristics of the central caches to be configured, the number of interfaces includes a second interface operatively coupled to the configuration file and to the central cache system, the second interface being operative when a process is put in execution to invoke the control mechanism for storing parameter information in specific ones of the shared control structures and into a specified one of the number of sets of central cache control structures derived from the configuration file.

36. A multicache system configurable within a primary memory of a host system for improving the performance of a number of processes running on the host system in processing complex database query statements, the multicache system comprising:
(a) a plurality of local caches in main memory corresponding to the number of processes being run on the host system, each local cache being associated with a different one of the processes being run; and
(b) at least one configured central cache system located in a shared predefined area of primary memory, the central cache system being operatively coupled to each of the plurality of local cache systems associated therewith, sad central cache system including:
a number of shared control structures used for controlling access to the central cache system;
a number of sets of central cache control structures corresponding to the number of central caches configured for storing code segments; and,
a control mechanism operatively coupled to the number of shared control structures and to the number of sets of central cache structures, the control mechanism being operative to control the configuration and operation of each of the central caches so that generated code segments produced by any one of the processes for executing a complex database query statement are automatically stored in the local cache associated with the process and in the configured central cache associated therewith for use by other processes associated with the same central cache in processing logically equivalent complex database query statements; and,
(c) a number of interfaces which operatively couple to the central cache system for configuring and operating the number of central caches; the number of interfaces including a fourth interface operatively coupled to receive command calls from processes running on the host system, the fourth interface being operatively coupled to the central cache system and operative in response to the command calls to invoke the control mechanism for carrying out operations specified by the command calls, the command calls including a generate central report command call used for generating statistics for the central cache system and a reset central statistics command call used for resetting statistics for the central cache system.

37. A multicache system configurable within a primary memory of a host system for improving the performance of a number of processes running on the host system in processing complex database query statements, the multicache system comprising:
(a) a plurality of local caches in main memory corresponding to the number of processes being run on the host system, each local cache being associated with a different one of the processes being run; and
(b) at least one configured central cache system located in a shared predefined area of primary memory, the central cache system being operatively coupled to each of the plurality of local cache systems associated therewith, said central cache system including:
a number of shared control structures used for controlling access to the central cache system;
a number of sets of central cache control structures corresponding to the number of central caches configured for storing code segments; and,
a control mechanism operatively coupled to the number of stared control structures and to the number of sets of central cache structures, the control mechanism being operative to control the configuration and operation of each of the central caches so that generated code segments produced by any one of the processes for executing a complex database query statement are automatically stored in the local cache associated with the process and in the configured central cache associated therewith for use by other processes associated with the same central cache in processing logically equivalent complex database query statements; and,
a persistent memory segment for storing the shared control structures, the memory including a number of memory sections, each section being associated with a different configured central cache and each section including first descriptor values for identifying one of the shared control structures corresponding to a directory control store structure and a set of descriptors for identifying one of the number of sets of central cache structures defining those components required for operating the configured central cache associated therewith, the persistent memory segment further including a separate section for storing a number of pairs of descriptors sequentially allocated to each configured central cache during the configuration thereof, each allocated pair of descriptors providing information to straggling processes pertaining to the central caches associated therewith for enabling the processes to detect that a central cache has been deleted from the central cache system.

38. A method of organizing a multicache system within a primary memory of a host system for improving the performance of a number of processes running on the host system in processing complex database query statements, the multicache system including a plurality of local caches in main memory corresponding to the number of processes being run on the host system, each local cache being associated with a different one of the processes being run, the method comprising the steps of:
(a) configuring at least one central cache system in a shared predefined area of primary memory, the central cache system being operatively coupled to each of the plurality of local cache systems associated therewith;
(b) including in the central cache system, a number of shared control structures used for controlling access thereto;
(c) including in the central cache system, a number of sets of central cache control structures corresponding to the number of central caches configured for storing code segments;
(d) including in the central cache system, a control mechanism operatively coupled to the number of shared control structures and to the number of sets of central cache structures, the control mechanism being operative to control the configuration and operation of each of the central caches so that generated code segments produced by any one of the processes for executing a complex database query statement are automatically stored in the local cache associated with the process and in the configured central cache associated therewith for use by other processes associated with the same central cache in processing logically equivalent complex database query statements;
(e) including in the host system, a number of interfaces that operatively couple to the central cache system for configuring and operating the number of central caches;
(f) including a cache utility program component operatively coupled to receive utility directives entered into the system by a user and operatively coupled to the control central cache system; operatively coupling the cache utility program component to a first one of the number of interfaces; and,
(g) issuing utility functions by the cache utility program component in response to the user initiated directives for invoking the control mechanism to perform a sequence of operations for carrying out the specified functions.

39. A method of organizing a multicache system within a primary memory of a host system for improving the performance of a number of processes running on the host system in processing complex database query statements, the multicache system including a plurality of local caches in main memory corresponding to the number of processes being run on the host system, each local cache being associated with a different one of the processes being run, the method comprising the steps of:
(a) configuring at least one configured central cache system in a shared predefined area of primary memory, the central cache system being operatively coupled to each of the plurality of local cache systems associated therewith;
(b) including in the central cache system, a number of shared control structures used for controlling access thereto;
(c) including in the central cache system, a number of sets of central cache control structures corresponding to the number of central caches configured for storing code segments;
(d) including in the central cache system, a control mechanism operatively coupled to the number of shared control structures and to the number of sets of central cache structures, the control mechanism being operative to control the configuration and operation of each of the central caches so that generated code segments produced by any one of the processes for executing a complex database query statement are automatically stored in the local cache associated with the process and in the configured central cache associated therewith for use by other processes associated with the same central cache in processing logically equivalent complex database
query statements
(e) including in the host system a number of interfaces that operatively couple to the central cache system for configuring and operating the number of central caches, the host system including a configuration file for storing user entered configuration parameters defining the characteristics of the central caches to be configured and a second one of the interfaces being operatively coupled to the configuration file; and,
(f) invoking the control mechanism by the second interface when a process is put in execution for storing parameter information in specific ones of the shared control structures and into a specified one of the number of sets of central cache control structures derived from the configuration file.

40. A method of organizing a multicache system within a primary memory of a host system for improving the performance of a number of processes running on the host system in processing complex database query statements, the multicache system including a plurality of local caches in main memory corresponding to the number of processes being run on the host system, each local cache being associated with a different one of the processes being run, the method comprising the steps of:
(a) configuring at least one configured central cache system in a shared predefined area of primary memory, the central cache system being operatively coupled to each of the plurality of local cache systems associated therewith;
(b) including in the central cache system, a number of shared control structures used for controlling access thereto;
(c) including in the central cache system, a number of sets of central cache control structures corresponding to the number of central caches configured for storing code segments;
(d) including in the central cache system, a control mechanism operatively coupled to the number of shared control structures and to the number of sets of central cache structures, the control mechanism being operative to control the configuration and operation of each of the central caches so that generated code segments produced by any one of the processes for executing a complex database query statement are automatically stored in the local cache associated with the process and in the configured central cache associated therewith for use by other processes associated with the same central cache in processing logically equivalent complex database query statements;
(e) utilizing a persistent memory segment in the central cache system for storing the shared control structures, the memory segment including a number of memory sections, each section being associated with a different configured central cache and each including first descriptor values for identifying one of the shared structures corresponding to a directory control store structure and a set of descriptors for identifying one of the number of sets of central cache structures defining those components required for operating the configured central cache associated therewith; and,
(f) utilizing a separate section for storing a number of pairs of descriptors sequentially allocated to each configured central cache during the configuration thereof, each allocated pair of descriptors providing information to straggling processes pertaining to the central caches associated therewith for enabling the processes to detect that a central cache has been deleted from the central cache system.
Description
BACKGROUND OF THE INVENTION

1. Field of Use

The present invention relates to data processing systems and more particularly to database management systems.

2. Prior Art

Typically, today's enterprise or legacy systems store large quantities of data in database systems accessed by database management system (DBMS) software. In such database systems, data is logically organized into relations or tables wherein each relation can be viewed as a table where each row is a tuple and each column is a component of the relation designating an attribute. It has become quite common to use relational database management systems (RDMS) for enabling users to enter queries into the database in order to obtain or extract requested data. To extract desired data, the user enters a query derived from a database query language into the RDMS. One well known query language is SQL. The query language provides a set of commands for storing, retrieving and deleting data. Such language for relational database management systems does not require users to specify the manner in which data needs to be accessed. For additional information, reference may be made to the glossary included herein. Generally, a query optimizer component is included in the database management system to select the manner in which queries will be processed. That is, the query optimizer component analyzes how best to conduct the user's query of the database in terms of optimum speed in accessing the requested data.

As known in the art, to conserve space in the database, it becomes desirable that the stored data values not be unnecessarily duplicated. Therefore, in a relational database, instead of having one very large table to hold duplicate data values, the user generally creates several smaller tables that contain unique data values that are related to each other through common attributes. A user can retrieve data for a given set of criteria by "joining" the smaller tables to represent the large table. Data is extracted from the system using a query command which locates all rows in a table or tables that meet specified criteria. In such systems, one of the most expensive operations to conduct in terms of time and resources is the "join operation" which joins together two or more entire relations which can be fairly large. When multiple joins are present in a user generated query, as is the typical case, the cost of processing the query increases dramatically. Thus, the time expended in developing, optimizing and processing complex queries can be exceedingly costly in

terms of time and resources. This is particularly true as more and more complex data types.

To improve system performance in executing programs that use SQL statements to access such databases, one approach has been the introduction of an SQL cache which makes it possible to reuse the results of having processed certain types of complex query statements. The approach has been to reuse the results of previously processed SQL statements. Generally, a SQL statement is processed by optimizer software which develops an access plan for executing the SQL statement in a manner that produces optimum performance. Executable code is then generated for executing the statement. Since this process is quite time consuming particularly in the case of complex query statements, the approach was to reuse previously generated executable code by storing the code in a local cache associated with the process (i.e., each program in execution) initiating the SQL queries.

The above approach has allowed the system in certain cases to bypass the step of code generation when the system encounters an identical SQL statement during the execution of a particular process. Since programs that access such database files repeatedly execute identical SQL statements, the use of an SQL cache with each process has been found to significantly improve performance. An example of a system that makes use of an SQL cache is the INTEREL product developed and marketed by Bull HN Information Systems Inc. For information concerning this product, reference may be made to the publication entitled, "Database Products INTEREL Reference Manual INTEREL Performance Guidelines, Copyright, 1996 by Bull HN Information Systems Inc., Order No. LZ93 Rev01B.

While the above approach has increased performance, it still takes considerable time to process complex statements in those instances where the particular process being run has not processed the same identical statement. Further, even if the process has previously processed the statement, the results of such processing are not saved when the process terminates. Hence, the same statement must again be processed when that same process is later run. Thus, the "local cache based" approach still is unable to address delays on a global basis.

Accordingly, it is a primary object of the present invention to provide a more efficient cache organization for improving system performance.

It is a further object of the present invention to provide a more extensive and flexible approach in processing complex statements.

It is still a further object to provide a more efficient way of managing memory resources during the processing of information queries.

SUMMARY OF THE INVENTION

The above objects are achieved in a preferred embodiment of the present invention in which a host system includes a multilevel cache system within the host system's memory that includes one local cache memory per process accessing host system databases and a central cache system shareable among the processes. In the preferred embodiment, the central cache system includes a control mechanism, a number of shared central cache control structures and a number of sets of control structures, one set for each central cache configured within the central cache system for accessing code segments associated therewith. Each set of control structures is user accessible via a set of utility directives through the shared central cache control structures. The shared central cache control structures include a first control table structure in the form of a directory containing entries which define the central cache memories configured for use by the system and references to associated set of control structures used in operating each configured central cache.

In the preferred embodiment, a utility is run to create individual caches within the central cache system. During operation, the process's local cache and central cache system operate cooperatively in processing complex database query statements. For example, in the case of a first process being executed, code is generated for each complex statement processed and stored in both the process's local cache and in the central cache associated with the process. Code generation and caching continues until all of the unique statements have been processed at which time the system is deemed to be in a steady state condition. The time required to reach steady state is referred to as "ramp-up" time. After code has been generated, the first process can now execute statements stored in its local cache without further code generation. Other subsequently executed processes configured to use the same central cache as the first process that are required to process complex statements identical to those processed by the first such process can use the previously generated code stored in the central cache. That is, when one of the processes first encounters a complex database statement, a search is made in local cache. If the appropriate code is found, the process executes that code. If the appropriate code is not found, then the system searches the central cache configured to be used by the process. If the code is found to be in the central cache, the central cache system moves a copy of the previously generated code to that process's local cache and converts the generated code into an executable form which the process can then execute out of its local cache.

When the first process terminates, the process's local cache is discarded while the central cache operates indefinitely until deleted bet the system using the set of utility directives. By enabling processes to share code generated by other processes even after such processes have been terminated, the multicache system of the present invention improves overall system performance. Further, the present invention enables new central caches to be created or deleted as required for optimizing performance as a function of the type of applications being executed and their requirements.

The above objects and advantages of the present invention will be better understood from the following description when taken in conjunction with the accompanying drawings.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is an overall block diagram of a data processing system that utilizes the teachings of the present invention.

FIG. 2 is a block diagram illustrating the multilevel cache system organization according to the teachings of the present invention.

FIG. 3 is a block diagram illustrating major components of a database system which incorporates the multilevel cache system.

FIG. 4a is a block diagram illustrating the components of FIG. 3 in greater detail.

FIG. 4b illustrates the operational flow of the search mechanism of the central cache system of FIG. 3.

FIG. 4c illustrates the overall organization of the central cache system of FIG. 3.

FIG. 5 illustrates in greater detail, the control data structures utilized by the central cache system organization of the present invention.

FIG. 6 is illustrates the different interfaces used by the multilevel cache system organization of the present invention.

FIG. 7a illustrates the administrative flow utilized by the multilevel cache system organization of the present invention.

FIG. 7b is a flow diagram illustrating the interaction between central and local cache in processing SQL statements according to the teachings of the present invention.

FIGS. 8a through 8d are flow charts illustrating in greater detail, the main operation of FIG. 7b in terms of processing commands/directives according to the present invention.

DESCRIPTION OF THE PREFERRED EMBODIMENT

FIG. 1

FIG. 1 is a block diagram of a conventional data processing system 10 that utilizes the multicache organization of the present invention. As shown, the system 10 includes a plurality of processing units 12-1 through 12-n which connect to a system bus 14 through their individual physical caches in common with a number of input/output units (IOUs) 16-1 through 16-n and a system control unit (SCU) 22. As shown, each IOU couples to a particular I/O subsystem (i.e., 19-1 through 19-n) which in turn connect to any one of a number of different types of devices both local and remote such as workstations 21-1 via a network 20 or disk mass storage units 21-n as indicated.

The SCU 22 connects to a number of memory units (MUs) 24-1 through 24-n. For the purpose of the present invention, system 10 may be considered convention in design and may for example utilize a mainframe computer system such as the DPS9000
manufactured by Bull HN Information Systems Inc. which operates under the control of the GCOS8 operating system. In this system configuration, users may wish to access the files of a large relational database stored on disk storage 21-n via the network
20 by entering SQL database queries via their workstation keyboard and/or via other input devices (e.g. mouse). The system 10 upon receiving the SQL query operates to initiate a search of the database files to obtain the data requested by the user. In system 10, all user SQL queries are presented to a relational application manager which forms part of a relational database management system such as INTEREL software which runs under the GCOS8 operating system. The INTEREL software further includes a host based relational file manager (RFM) software for accessing the database files and an Operational Directory Interface (ODI) used for the storage of directory information. These components are described in greater detail in the publication entitled, Bull Users Society Fall Conference Proceedings, Copyright, 1991 by Bull HN Information Systems Inc. These components are discussed herein only to the extent required for an understanding of the operational environment in which the multicache system of the present invention operates.

FIG. 2--Multicache Organization

FIG. 2 depicts the organization of the multicache system of the present invention. For ease of illustration, a single memory unit 24-1 is shown. It is assumed that there are three processes (A, B, and C) being executed and that specific areas of memory unit 24-1 have been allocated to each process. These memory areas correspond to the local cache blocks 24-2a through 24-2c in FIG. 2. Additionally, another area of memory unit 24-1 has been allocated to be shared among the processes. This memory area corresponds to central cache block 24-4 in FIG. 2. As explained herein, the multi-level cache system of the present invention is made up of one or more Process-Local Caches and a central cache system containing at least one Central Cache. As diagrammatically indicated by the dotted lines in FIG. 2, the process-local cache is dedicated to the specific process for which it is created. In a conventional manner, the RDMS (INTEREL software) automatically creates a process-local cache for each process that accesses relational database files stored on disk 21-n and allocates memory for code segments generated during process execution. In the example shown, the central cache system is to be shared by the multiple processes A, B, and C. Through the use of utility directives, an administrator specifies the configuration parameters for each central cache within the central cache system and creates each cache explicitly as described herein. When the central cache is so configured, configuration parameters can be used to specify whether processes A, B and C will use a central cache and which central cache will be used by such processes. As indicated by the solid lines between each local cache and central cache system 24-4, it is assumed that all three local caches are specified to use the same central cache within the cache system 24-4.

FIG. 3 Database System Components

FIG. 3 illustrates in block diagram form, the major components of the preferred embodiment involved in processing database query statements. As shown, these components include the components of RDMS 302 (INTEREL software) and a SQL cache manager component that manages both local and central cache systems as described herein. In greater detail, RDMS 302 comprise a Runtime Library 302-1 which serves as the application's interface to the RDMS 302, a SQL Director Component 302-4, a Common Component
302-6, a Relational Access Manager (RAM) component 302-8, a Code Generation component 302-10 which contains support routines for acquiring information stored in a number of "Code Generation" structures relating to code which has been generated and an Operational Directory Interface (ODI) component 302-12 arranged as shown.

The Runtime library 302-1 contains runtime routines bound into the application used by the application 300 for issuing calls. Each such call results in library 302-1 sending a query statement to Director component 302-4. The Director component
302-4 contains routines which analyze each query statement for determining if the statement is of a type that accesses relational database files and thus is suitable for code generation and storage in the process's local cache. The Director component also contains routines that generate calls to Cache Manager component 304 to see if the code for that statement can be found in the process's local cache or in any central cache associated therewith. When code for that statement is not found in either cache, the Director component 302-4 calls the Relational Access Manager 302-8 via the Common component 302-6 to process and "potentially" execute the query statement as described herein.

Also, as indicated, there is a path provided which enables the Common component 302-6 to call the ODI component 302-12 to delete obsolete code through the SQL Cache Manager component 304. Lastly, the Common component 302-6 also directly communicates calls to the SQL Cache Manager component 304 when deleting obsolete code. The path taken to delete obsolete code depends upon the particular operation that is triggering the deletion.

FIG. 4a-SQL Cache Manager Components

FIG. 4a shows in greater detail, the components that comprise the SQL Cache Manager component 304 of FIG. 3. The Cache Manager component 304 includes a number of routines for performing services involving cache entries associated with the central and local caches. Hence, the Director component does not differentiate between central and local cache; the component views them simply as "the cache".

As shown, the Cache Manager component 304 includes an internal programmable interface component 304-1, a local cache component 304-3, a central cache component 304-5, a SQL Cache Utility Program (SCUP) 304-7 and an Obsolete Code Management (OCM) component 304-10, all of which are operatively coupled as shown.

The programmatic interface component 304-1 serves as the interface to both central and local cache components and is called by the Director component 302-4 to perform a number of internal operations as indicated in FIG. 4a. As shown, these operations correspond to find, delete, clear, insert and print-info requests used to access the contents of the cache. The internal programmatic interface commands/requests will be discussed in greater detail with reference to FIG. 6.

The local cache component 304-3 and central cache component 304-5 each includes a search logic mechanism and associated control structures described in greater detail herein required for carrying out the processing of requests received from SQL Director component 302-4 via SQL Cache Manager Interface component 304-1. The local cache component 304-3 manages the storage of generated code within process-local memory while central cache component 304-5 manages the storage of generated code within the portion(s) of memory shared by multiple processes.

As shown in FIG. 4a, both caches 304-3 and 304-5 operatively couple to Code Generation component 302-10 for receiving generated code header information of code segments 540 for use within their respective search logic mechanisms. The Code Generation routines that support movement and conversion include: a Centralize Code routine which is called by the Cache Manager component to prepare a specific piece of generated code for movement from the local cache system to the central cache system, and a Localize Code routine used to prepare a specific piece of generated code from the central cache system for movement to the local cache system. The Centralize Code routine performs the operations of marking the code as not directly executable, storing information in the code header and preparing

a checksum or similar verification. The Localize Code routine performs the operations of resolving process-relative address references, marking the code as executable, and calling for the insertion of the code into the local cache system.

Additionally, central cache component 304-5 couples to SQL cache utility program (SCUP) component 304-7. The SCUP component 304-7 is a batch program used for carrying out a number of functions pertaining to the central cache component 304-5 in response to a set of utility directives applied via its interface with the central cache system 304-5. This interface will be described in greater detail with reference to FIG. 6. Also, the central cache component 304-5 operatively couples to the OCM component 304-10.

As in the prior art discussed above, the local cache component 304-3 processes cache entries represented by L-nodes. Each L-node contains information related to one block of generated code. Some of the information is stored in the L-node while other information is merely pointed to by the L-node. For example, the generated code is not located in the L-node but a pointer to the code is stored in the L-node. Active L-nodes are linked into lists. A first set of lists is based on a hash value with each list containing L-nodes associated with a particular hash value. All L-nodes are also linked into a second list called a most recently used (MRU) list. This results in each L-node that is in used to be linked to two lists, a particular hash bucket list and the MRU list. The L-nodes not in use are linked at the end of the MRU list.

When a new L-node is to be inserted into cache, it is placed at the head of the appropriate hash bucket list and linked at the head of the MRU list. Both types of lists are doubly linked lists to allow for simple removal of entries or in the case of the MRU list, to allow for reordering. When an existing L-node in cache is accessed for use of the generated code, it is relinked to the head of the MRU list. Once local cache is full, each new entry causes the deletion of the least recently used entry, along with the associated generated code and the allocated memory is reused for the storage of the new entry.

Each L-node contains the following type of information fields: fields containing "next" and "previous" links to nodes in the same bucket; fields containing "next" and "previous" links to nodes in the MRU list, a code token field used to reference and call a piece of generated code; a model token field used to differentiate models in use by the process; the number of host variables; a SQL command type field and a size field for specifying the number of words of generated code. For further information regarding the use of L node structures, reference may be made to Appendix VI.

In the preferred embodiment, each central cache entry is represented by a C-node structure. As in the case of the local cache, the central cache system uses a bucket mechanism and a MRU list. The number of an available entries, as well as the number of buckets are not necessarily the same for the local and central cache systems. C-nodes differ somewhat in content from L-nodes, but share certain components such as those that link nodes to each other both within the same bucket and within their respective MRU chains. In contrast to L-nodes, a C-node does not contain a code token or a model token field. Instead of a code token field (which is a domain relative data type in the L-node), the central cache system has a list of descriptors that are indexed in parallel with the array of C-nodes. Each descriptor frames a segment of memory in the shared workspace that contains the associated code. The model token field in an L-node is used for storing a process relative value that cannot be used in the central cache system. Identification of the tables referenced by the generated code in the central cache system, qualified by owner and model are included with the generated code and are accessed by the central cache system through code generation data access macros. Additionally, there are a number of other structures that are used by the central cache system. These will be discussed in connection with FIG. 5.

The Cache Manager component calls routines in the Code Generation component 302-10 and provides a code "token" as an input which is interpreted as a pointer to a generated code segment or to a data structure that contains the pointer to the code segment. For further information regarding these routines, reference may be made to Appendix II.

Search Mechanism-FIG. 4b

FIG. 4b illustrates the operational flow of the central cache search mechanism 304-50. This mechanism is similar in operation to the search that occurs in the local cache. As indicated in FIG. 4b, the search mechanism 304-50 utilizes a hash method of function in order to handle searches involving thousands of potential entries to be searched. The hash method also allows use of the results of the calculation already done by the local cache to be used for the central cache search.

The hash function takes, as input, the properties of the SQL statement such as the normalized SQL statement length and text, the number, type and length of host variables, the use of indicator variables and the name of the cursor, if any. The hash function involves calculating the checksum of these items or values representing these items to provide a "hash intermediate value". This value is divided by the number of buckets (i.e., a prime number) and the remainder of the result is used to determine the bucket. It will be appreciated that other algorithms could be used to calculate the hash function.

The hash intermediate value is calculated during the search of the local cache. If the central cache system must also be searched as for example, during the execution of a find function in which the search of the local cache results in a miss, the hash intermediate value is passed on to the central cache system so that the checksum portion of the calculation need not be repeated. The division operation to obtain the remainder is performed separately in the local and central cache systems since the number of buckets in each most likely will differ.

The search mechanism compares the entries in the calculated bucket list until it detects a match which it signals a hit or until all of the entries in the list have been examined in which case, it signals a miss. When traversing a bucket list comparing entries for a hit, the central cache system uses as the criteria for a hit, identical matches of the following items: cursor name if any; statement type; host variable number, type and length if any; statement text; secondary text (i.e., the SELECT text associated with a FETCH statement); owner name; model name; and executing user id name.

The bucket lists are double-linked lists to allow simple removal of entries that are not at either end of the list. The number of buckets used is equal to the prime number less than or equal to the configured maximum number of cache entries. With a reasonable distribution across the buckets, the number of entry match comparisons can be kept to a minimum. It will be appreciated that the number of buckets could also be a user configurable number.

FIG. 4c--Central Cache System Organization

FIG. 4c illustrates in greater detail, the overall organization of the central cache system 304-5 of FIG. 4a. As indicated, the system 304-5 includes a number of shared control structures 500, 520 and 530, a control mechanism 560 and a set of control structures 510 for each central cache configured in the system. The cache directory structure 500 is a structure used for indicating which central caches have been configured within the system.

The linkage segment 520 is a system memory segment that contains all of the descriptors (segment and entry) that define a domain (see glossary). These descriptors are created by a linker program prior to execution or by the operating system during execution. For further information regarding the use of such segments, reference may be made to U.S. Pat. No. 4,300,192 that issued on Nov. 10, 1981.

The directory gate block structure 530 is a structure used for controlling access to cache directory 500 through a queue monitor mechanism which is used to manage the cache directory 500 resource. For the purposes of the present invention, the queue monitor mechanism may be considered conventional in design. For example, the queue monitor mechanism may take the form of the monitor mechanism described in the text entitled, "Operating Systems Advanced Concepts" by Mamoru Maekawa, Arthur Oldehoeft and Rodney Oldehoeil, Copyright 1987 by The Benjamin/Cummings Publishing Company, Inc., at pages 57-59.

The control mechanism 560 includes the various routines that are used to create, modify and access the central cache control structures through linkage segment 520. These routines will be described in conjunction with FIGS. 8a through 8d.

FIG. 5--Control Structures

FIG. 5 illustrates in greater detail, the different sets of control structures included in the central cache system of FIG. 4c. As shown, the linkage segment 520 includes a number segments 0 through n for storing a corresponding number of sets of descriptors labeled as 520-0 through 520-n. Additionally, as shown, linkage segment 520 provides storage for a cache directory descriptor, cache.sub.-- dir, a directory gate block descriptor, dir.sub.-- gate.sub.-- b1 and a directory condition ID descriptor, dir.sub.-- cond.sub.-- id. These descriptors provide values for accessing information and the structures 500 and 530 as indicated.

As shown, the central cache directory 500 includes entries identifying each central cache which has been previously configured in the system using the cache utility commands described in Appendix III. As indicated, the CACHE.sub.-- DIR structure
500 takes the form of a table structure having n number of entry storage locations for storing a corresponding number of data entries. Each table data entry defines a particular central cache being used by the system. By way of example, the CACHE.sub.-- DIR control structure 500 is shown as containing two data entries in locations 0 and 1. The first data entry is coded to specify that a first central cache named ".sub.-- SYS" has been configured by the system. As explained herein in greater detail, configuration is carried out through the use of a create.sub.-- central.sub.-- cache command described in Appendix III and discussed herein. The second data entry specifies that a second central cache named "CACHE2" has also been configured by the system.

As shown in FIG. 5, both data entries contain the two additional fields cid$ and data$. These fields serve as pointers to a pair of memory addresses contained within linkage segment 520. By storing central cache structures in linkage segment
520, this ensures that such structures remain or persist in memory for a sufficiently long period of time (e.g. days, weeks etc. or until the system shuts down).

Also, the directory control structure 500 establishes an index value for accessing the further group of control structures 510 which define the different components/structures required for operating the corresponding central cache. As shown in FIG. 5, these components include a cache data component structure 510a, a bucket component structure 510b, a CNODE component structure 510c and a code descriptor component structure 510d. An additional group of structures 510e may also be included for utilization by the obsolete code manager component 304-10 of FIG. 4a when that capability has been included within the multicache system of the present invention.

As indicated in FIG. 5, the each of the sets of central cache structures are accessed through the particular set of descriptors indexed using a cache index value which is mapped to the address of the central cache name stored in CACHE.sub.-- DIR structure 500. Stated differently, the CACHE.sub.-- DIR entry location associated with the name of the particular central cache serves as the index value used by the system (i.e., control mechanism 560) to locate the set of descriptors associated therewith. Thus, the central cache named .sub.-- SYS is mapped to the index value of zero which identifies the set of descriptors 520-0 of descriptor segment "0" as being associated therewith. The central cache named CACHE2 is mapped to the index value of one while a central cache name stored in CACHE.sub.-- DIR entry location n would be mapped to the index value of n which identifies the set of descriptors 520-n of segment descriptor "n" of FIG. 5. As indicated in FIG. 5, each segment descriptor specifies the location of the structures for a particular central cache, including the bucket structures, the CNODE structures, and the code segment descriptor list.

As indicated in FIG. 5, there is another set of descriptors that is maintained for each central cache and stored in a different area of the linkage segment 520. These descriptors are used in conjunction with the queue monitor mechanisms that are used to implement exclusive access to the structures of each central cache. This set of descriptors is referred to as a rotation set 520f in FIG. 5. Two descriptors of this set are allocated for each central cache. They are kept separate from the descriptors described above since they need to exist for a while after the associated central cache is deleted. This extra time allows for straggling processes that have completed exclusive access to the CACHE.sub.-- DIR, (so they believe that the desired central cache still exists), but are waiting for exclusive access to the structures for the specific central cache (i.e., those structures which may have been deleted in the meantime). With the exclusive access mechanism descriptors stored separate from the descriptors that specify the other structures of each central cache, the straggling processes can detect that the cache has been deleted and return status accordingly.

The pairs of descriptors in the rotation set are allocated sequentially as caches are created. References to each pair in use are stored in the CACHE.sub.-- DIR 500 and are represented as cid$ and data$. When the end of the rotation set is reached, reallocation resumes at the start of the rotation set. The rotation set can support four times as many central caches as can be active at one time. This allows sufficient time for the straggler processes mentioned above to recognize the deletion of the cache they are attempting to access if such deletion has occurred.

For each central cache that is created, one of the two descriptors allocated in the rotation set is used to describe a shared area of memory. One part of that shared area of memory is used for exclusive access counts and signaling. This area also contains configuration and statistical information relating to the associated central cache. The other descriptor is used directly by the exclusive access mechanism.

Considering the structures 510 in greater detail, it is seen that the CACHE.sub.-- DATA structure 510a describes the basic characteristics of its central cache system. As indicated in FIG. 5, the structure 510a includes a number of different sections labeled gate, config, stats, flag and info. The gate section which provides protection is used for storing identification information values used to enforce exclusive access to the particular central cache system. The config section is used for storing configuration related information values such as maximum number of buckets, maximum number of entries, maximum memory etc. As indicated earlier, these values are configured using the create central cache command of Appendix III.

The stats section is used for storing statistical information values obtained during the operation of the central cache system associated therewith. The flag section is used for storing informational flag values set during central cache operation while the info section is used for storing other informational values.

The bucket structure 510b is used for storing bucket information values such as head pointer, tail pointer and count. The CNODE structure 510c is used for storing node information values such as node link pointers for traversing the CNODE structure, number of words in code, command type, host variables, bucket identifier, etc. The code descriptor structure 510d is used for storing code descriptor information relative to identifying the location of a code segment. Examples of these different control structures are shown in Appendix VI.

Central Cache Interfaces--FIG. 6

FIG. 6 illustrates the different interfaces utilized with the central cache system 304-5. As shown, there are four separate paths or interfaces associated with the central cache system 304-5. These correspond to the

internal programmable interface of FIG. 4, the utility directive interface used by the cache utility program component 304-7 of FIG. 4, a configuration interface and an application visible interface. As previously, discussed, the internal programmable interface is an interface utilized by the Director component 302-4 to have various services performed by the central cache system 304-5 initiated by requests received from the application 300.

In greater detail, cache manager component 304 in response to a Find Entry request initiated by a routine call received from the Director component 302-4, searches local cache component 304-3 for a statement matching the current one and if found, causes the execution of the generated code. In response to a Delete Entry request, the Cache Manager component 304 operates to remove an entry from the local cache component 304-3 and in response to a Clear Cache request clears the local cache component
304-3 (during disconnect processing). Also, when the Code Generator component 302-10 calls the Cache Manager component 304 to perform an Insert Entry logical operation, the Cache Manager component 304 operates to register a code fragment in the local cache component 304-3. If the cache is full, the inserting of an entry operation causes another entry to be deleted from the local cache component 304-3. Lastly, in response to a Print Info request, the Cache Manager component 304 causes a printout of summary cache information.

The utility directive interface is used by the SCUP component 304-7 to create a central cache system and define its basic characteristics, to delete a central cache system, to manipulate selected entries in a central cache system and to acquire information regarding the contents of central cache system to develop statistical information. The central cache utility directives have a particular syntax and a set of representative directive commands is shown in Appendix III.

The configuration interface is used by a database or system administrator to manage the usage of the central cache system 304-5. More specifically, the interface can be used as follows:

(a) to specify the configuration parameters to be associated with central cache system 304-5;

(b) to specify whether specific user IDs and/or processes will use and update central cache system 304-5; and,

(c) to tune cache performance by adjusting variables such as configuration parameters based experience gained during system operation.

The manner of specifying cache configuration parameters and the structure of these parameters is described in Appendix IV.

The application visible interface is used by the application 300 to call various routines contained with the support library 302-1 of RDMS 302 which relate to the generation of statistics, the clearing of certain statistical counters, and the clearing of the local cache. This interface can only be used to access a single central cache system specified by the application 300 or process associated therewith. The particular central cache to be accessed with the interface is specified using the configuration parameters provided via the configuration interface. The calls provided by the interface are described in Appendix V.

DESCRIPTION OF OPERATION

With reference to FIGS. 1 through 6, the operation of the control mechanism constructed according to the present invention will now be described in conjunction with the flow charts of FIGS. 7a, 7b, and 8a through 8d. FIG. 7a illustrates the overall administrative operation of the multicache system of the present invention in the system of FIG. 1. FIG. 7b illustrates the interaction between the local and central caches in processing SQL statements.

As indicated in block 700 of FIG. 7a, initially the configuration files are setup by an administrator. When the application is run, the RDBMS software loads the contents of the configuration files into the appropriate memory areas. If there are no configuration parameters specified, then the system uses established default values.

Since the particular method of configuration is not pertinent to an understanding of the present invention, it is assumed that the setup procedure of block 700 has been performed. That is, the sizes of the local caches 24-2a through 24-2c have been configured utilizing the parameters of Appendix IV. Also, it will be assumed that the appropriate directives have been issued to configure each central cache system to be utilized within the system and its basic characteristics. This results in the appropriate information being stored within each of the control structures of FIG. 5 such that a central cache of central cache system 24-4 of FIG. 2 will have been created and configured to be shared among the processes in the manner described relative to FIG. 2. As indicated in block 710, after the execution of block 700, the RDBMS software is able to run processes A, B and C which are started in a conventional manner as indicated in FIG. 7b.

As indicated in block 720 of FIG. 7a, during execution, the application or process using the central cache system is able to report statistical information. This is accomplished through the application visible interface of Appendix V. Through the use of a X.sub.-- SQL.sub.-- CACHE.sub.-- GEN.sub.-- CENTRAL.sub.-- REPORT call, the process can access the accumulated statistical information stored in the CACHE.sub.-- DATA structure and display/generate statistics reflecting the use of the central cache system. Also, the user can issue a LIST.sub.-- STATISTICS command via the utility directive interface as described in Appendix III to display the statistics pertaining to any existing central cache.

In the present example, process A, B or C can issue such calls via the application visible interface. In the present example, it is assumed that only one central cache system has been configured within the system of FIG. 1. The results of analyzing such statistical data can cause various configuration scenarios to can take place for the purpose of improving system performance. As indicated by blocks 730 and 740, the scenarios may also involve invoking SCUP component 304-7 of FIG. 4a using the delete and create cache utility commands of Appendix III. This use of such commands/directives will be discussed in greater detail with reference to FIGS. 8a through 8d.

Before considering the possible configuration scenarios, the manner in which the local and central caches interact in processing SQI, statements will be discussed with reference to FIG. 7b.

FIG. 7b

As indicated in block 1 of FIG. 7b, a program corresponding to process A of FIG. 2 (e.g. written in COBOL or some other language) is running in system 10 of FIG. 1 and somewhere in its execution flow of operation encounters a SQL statement labeled SQL1 wherein it enters the flow of FIG. 7b. It processes that SQL statement, analyzes it to some degree and searches local cache 24-2a to see if the code for that statement has already been generated as indicated in block 710-2. If there is no appropriate code in the local cache 24-2a (i.e., the No path), then process A searches to see if there is appropriate code stored in central cache system 24-4 as indicated in block 710-3.

There are several things that could happen which would cause the miss to occur in local cache 24-2a. One is that the amount of available space in local cache 24-2a was such that the SQL1 statement had to be replaced. In terms of the ramp-up type of situation, it could be that process A is a new process that has just begun execution and that this is the first time that process A encountered this SQL statement. At this point, the system now searches in central cache system 244 to see if any other process (i.e., process B or C) has encountered the SQL1 statement.

In the beginning of operation, there is no generated code stored in any of the caches in memory unit 24-1. Thus, when the system searches local cache 24-2a, it does not find the statement. Next, as indicated in block 710-3, the system searches central cache system 24-4 and again finds that the generated code is not stored in central cache system 24-4. As indicated in block 710-4, next, the system determines if it can generate code for the particular statement. If the answer is no, then the system interpretatively executes the same SQL1 statement as described below.

As indicated in block 710-5, the system determines by means of testing an execute mode switch indicator if the generated code is to be executed. This function enables the local and central caches to be populated or preloaded without having to execute the generated code. Later, when the application is started, it can access the contents of the central cache system 42-4 without the need to generate code for the preloaded statements.

With reference to FIG. 7b, when the execute mode indicator is turned off, indicating no execution is to take place (i.e., as determined by block 710-5), then the system moves down through the program sequence and exits via block 710-6.

When the execute mode switch indicator is set to "on", the system follows the "yes" path to block 710-7 of FIG. 7b wherein the statement is executed interpretively by the system calling RAM component of FIG. 3 which then calls the lower level access manager software to perform the actual database file access. The program then exits via block 710-6 and continues normal program execution at the point following that SQL statement.

Relative to block 710-4, when the system determines that code can be generated for that statement, it sequences to block 710-8. As indicated in block 710-8, the system generates the code for the SQL1 statement and stores it in local cache 24-2a. At this point, the system is operating as it did in the past. But, in contrast to the prior operation, the system continues its processing of the statement by searching central cache 24-4 for appropriately generated code for that statement. If the generated code is not there (i.e., process B or C assumed to be executing has not generated code for the statement during the time the system was sequencing to block 710-8), then the system makes a representative copy of the generated code and sends it over to central cache 24-4 as indicated in block 710-9.

The copy moved to the central cache system is termed to be a representative copy rather than an exact copy because some of the addresses and offsets must be converted before it could be deemed an exact copy. More specifically, the following items are converted: references to the "SEGID" of the code segment; references to other segments in the specific domain in which it will execute; references to other domains and references to offsets within the code segment.

After performing the copy functions of block 710-9, the system sequences to block 710-10. At this point, the generated code has been copied into the central cache 24-4. As indicated in FIG. 7b, the system performs a test of the "execute mode" switch which is the same as performed in block 5. But, in this case, the results of such test cause the system to sequence to a different point in the flow.

More specifically, when the execute mode switch indicator is not "on", then the system sequences to block 710-6 wherein it exits the flow and returns to program execution as previously described. At this point, the system has accomplished populating the local and central caches with generated code for that SQL1 statement.

When the execute mode switch indicator is "on" as determined in block 710-10, the system sequences to block 710-11 wherein the generated code associated with the statement is executed directly out of local cache 24-2a by the system. By contrast, central cache system does not execute the generated code right where it stored. That is, central cache system 24-4 serves more as a repository. The generated code is executed, again by calling the lower level access manager software to perform the actual database file access as indicated in block 710-11. As indicated in FIG. 7b, the system then sequences to block 710-6 where it exits in the manner described above.

With reference to block number 710-2 of FIG. 7b, if the system did not find the statement in local cache 24-2a, the system sequences from block 710-2 to block 710-3 wherein it tests for the presence of the SQL1 statement in central cache system
24-4. This is the case in which process A is just standing up and the central cache system 24-4 has been storing generated code for statements that were executed by processes B and C. In this case, when the system performs the test of block 710-3, the answer is yes causing the system to sequence to block 710-12. As indicated, the system then copies the generated code stored in central cache system 24-4 into local cache 24-2a. That is, the generated code is extracted out of central cache system 24-4, converted to executable form using the Localize Code routine, and moved into local cache 24-2a.

The operation of block 710-12 is performed as quickly as possible because central cache system 24-4 is capable of being shared among a number of processes and the time required for exclusive access must be minimized. Next, the system sequences to block 710-10 and then to block 710-11 after which it exits through block 710-6 as described above.

It will be noted that if the statement is in local cache 24-2a to begin with, then the system does not have to do perform any operations in central cache. The system just executes the generated code for the statement directly out of local cache
24-2a that is fastest mode of operation (just sequences through blocks 710-2, 710-10 and 710-11). Thus, in steady state, when the local cache 24-2a is large enough, the system can run the fastest.

It is seen from the above description that the execute mode switch indicator provides a way of populating both local and central caches. Prior to the existence of this indicator, the code had to be executed when it was stored in the cache. But if the purpose of the execution was solely to pre-populate the cache, the changes to the database that resulted from the execution of the code had to be undone. Alternatively, the statement could be written to modify a record in the database that would never be subsequently used. The addition of the execute mode switch allows the use of a simpler mechanism for avoiding this undesired execution while still populating the cache.

It should be noted that the execute mode switch indicator is used differently for local cache and for central cache. With just a local cache involved, the execute mode switch is turned off during the population of the local cache, but must be later turned on by that same process in order to utilize the preloaded cache. This is because the local cache is deleted when the process terminates. With the addition of the central cache, the executed mode switch can be turned off for a process (or set of processes) that exist for the explicit purpose of populating the central cache. Following the termination of these processes, subsequent processes (that have the execute mode switch set to "on" as is the default), can access the code that was previously loaded into the central cache. The use of the execute mode switch may involve more than turning it "off" at the start of an existing application, particularly in those applications in which the result of one SQL statement is used in subsequent SQL statements or in subsequent logic in the application. This is because when the execute mode switch is set to "off", the SQL statement cannot return data from the database nor result in modifications to the database.

Configuration Scenarios

It may be desirable to alter the sizes of the local and central caches through the use of configuration system and utility directive arguments, respectively. If a local cache is configured to be sufficiently large to hold all or a majority of the SQL statements to be executed by the process, then the central cache system can be then used primarily during the ramp-up process. Once the required SQL code is moved into the local cache of the processes, cache searches will result in local cache hits and the central cache system will not need to be accessed. Given enough main memory space to minimize paging of the local caches, this will result in maximum performance but will require the most memory resources. Thus, the administrator may alter certain configuration parameters by changing environmental variables as described in Appendix IV for use by those processes not already in execution.

As indicated above, it is also possible to logically change the size of a central cache by cache utility commands that invoke the SCUP component 304-7 of FIG. 4a. For example, the user could first issue a DELETE.sub.--

CENTRAL.sub.-- CACHE command and then issue a CREATE.sub.-- CENTRAL.sub.-- CACHE command as indicated by blocks 730 and 740 of FIG. 7a. This can be done while the application/process is running. The delete command would be used to delete the central cache associated with the process and the create cache command would be used to create a cache having the same name but with a larger size as required for better performance. During the period in which the central cache does not exist, the process will continue executing using only the local cache. Once the central cache is created with the name of the deleted central cache, then the process will execute using the newly created central cache.

Additionally, the present example presumed that there is a single central cache system configured which is being shared by processes A, B and C. It may be determined that a number of central caches are needed to optimize performance because of the characteristics of the system workload. The key in determining whether to use more than one central cache system is to identify processes that frequently execute the same SQL statements and then associate those processes with the same central cache. It may be that there are multiple applications with sets of processes that execute those different applications. For example, the system may be running a loan qualification application program that is separate from an ATM application. In this situation, it may be important to ensure that the SQL statements utilized by the loan application are not displacing the SQL statements utilized by the ATM application. Therefore, it is desirable to create a second central cache for handling the ATM application. Also, in the case of the ATM application, since there is a small limited number of SQL statements, a large central cache is not required and the local caches may be configured to hold all of the SQL statements for that application. By contrast, the loan application may use a large variety of unique SQL statements such that the local cache size would be selected to hold only a small subset of those statements while the central cache size would be selected to hold the local cache statements as well as the rest of the statements which are not accessed as often.

When more than one central cache is created, the user can specify which one is to be used by: (a) each Userid (i.e., all processes that execute under that Userid); or (b) a specific process. This capability enables the user to group the processes that include the same SQL statements and that will therefore realize the most improvement in performance by sharing access to the same central cache.

It is desirable to consider in greater detail, the main operations of the control mechanism 560 of the central cache system 304-5 of FIG. 4c. The main operations are depicted in FIG. 8a. This figure illustrates the operations performed by the control mechanism 560 in response to internal functions called during SQL statement processing, specific utility directives and user initiated commands described in Appendix III. The table below relates the central cache system functions (main operations depicted in FIG. 8a) to the different cache system components and the operations that utilize such functions. For example, SQL statement processing can result in SQL cache manager Interface 304-1 initiating the find.sub.-- entry function.

__________________________________________________________________________ Central Cache System Function "User" Component Operation That Utilizes The __________________________________________________________________________ Function Find.sub.-- entry SQL Cache Manager Interface (304-1) SQL statement processing Delete.sub.-- entry SQL Cache Manager Interface (304-1) SQL statement processing Insert.sub.-- entry SQL Cache Manager Interface (304-1) SQL statement processing Clear.sub.-- cache SQL Cache Utility Program (304-7) CLEAR.sub.-- CENTRAL.sub.-- CACHE Directive Delete.sub.-- code SQL Cache Manager Interface (304-1) SQL statement processing SQL Cache Utility Program (304-7) DELETE.sub.-- CODE.sub.-- IN Directive Reset.sub.-- stats SQL Cache Utility Program (304-7) RESET.sub.-- STATISTICS Directive Application Interface X.sub.-- SQL.sub.-- CACHE.sub.-- RESET.sub.-- CENTRAL.sub.-- STAT List.sub.-- stats SQL Cache Utility Program (304-7) LIST.sub.-- STATISTICS Directive Application Interface X.sub.-- SQL.sub.-- CACHE.sub.-- GEN.sub.-- CENTRAL.sub.-- REPORT List.sub.-- models SQL Cache Utility Program (304-7) LIST.sub.-- MODELS.sub.-- IN Directive List.sub.-- tables SQL Cache Utility Program (304-7) LIST.sub.-- TABLES.sub.-- IN Directive Get.sub.-- cnodes SQL Cache Utility Program (304-7) DISPLAY.sub.-- CODE.sub.-- INFO.sub.-- IN Directive Get.sub.-- code SQL Cache Utility Program (304-7) DISPLAY.sub.-- CODE.sub.-- INFO.sub.-- IN Directive Report.sub.-- code SQL Cache Utility Program (304-7) (for debug and analysis) Create.sub.-- cache SQL Cache Utility Program (304-7) CREATE.sub.-- CENTRAL.sub.-- CACHE Directive Delete.sub.-- cache SQL Cache Utility Program (304-7) DELETE.sub.-- CENTRAL.sub.-- CACHE Directive List.sub.-- caches SQL Cache Utihty Program (304-7) LIST.sub.-- CACHES Directive Delete.sub.-- obsolete.sub.-- entries Common (302-6), ODI (302-12) DDL occurrence __________________________________________________________________________

FIG. 8a

Referring to FIG. 8a, it is seen from block 800 that control mechanism 560 begins operations by first validating parameters of the call made to the central cache system 304-5 via interface 304-1. Parameters are passed that describe the code, when searching the Central Cache system for appropriate generated code. The parameters contain description information such as the normalized text of the SQL statement, attributes of the host variables, if any, cursor name, the owner and model names, etc. This information is passed in structures that are referenced by the descriptors that are passed as some of the actual parameters. If the caller of the Central Cache system does not pass a suitable descriptor that is supposed to reference the SQL statement description information, attempts to reference the information may result in a hardware fault. Another parameter that is passed is a descriptor to the area of memory of the caller that is to hold the generated code copied from the Central Cache system if it is found in the cache. If the descriptor does not reference sufficient memory and an attempt is made to copy the found code into this area, a hardware fault may occur. When references such as these result :n faults while the software is in a period of exclusive access to central cache structures, service may be denied to subsequent Central Cache system callers. For this reason, validation of parameters is performed prior to entry to any of the monitors described herein.

Following the validation operation, control mechanism 560 performs the main operations of the Central Cache System 304-5 as indicated in block 840. These operations require exclusive access to the various data structures illustrated in FIG. 5. Therefore, before the control mechanism 560 passes control to functions of block 840, it performs the "registration of exclusive access". As indicated above, in the preferred embodiment, exclusive access to shared cache resources (i.e., shared structures) is controlled through the use of a queue monitor mechanism. It will be appreciated that a central cache system may be implemented using other types of exclusive access mechanisms.

As indicated in block 820, the one or more monitors is entered prior to the execution of the main function requested by the user of the cache system, and following such execution, the monitor(s) are exited can otherwise terminated as indicated in block 860. Finally, the system sequences to block 880 where exit processing is performed prior to returning to the caller (i.e., requesting process).

FIGS. 8b through 8d illustrate in greater detail of the operations performed by control mechanism 560 in executing the control flow illustrated in blocks 820, 840, and 860.

FIG. 8b

FIG. 8b illustrates the processing performed by control mechanisms 560 involved in entering the monitors that enforce the exclusive access to the structures of the Central Cache System illustrated in FIG. 5. FIG. 8d illustrates the processing performed by control mechanism 560 involved in exiting the monitors that enforce the exclusive access to the structures of FIG. 5. These figures indicate by the listings of functions (i.e., functions find.sub.-- entry through delete.sub.-- obsolete.sub.-- entries) that the processing which occurs depends on the particular function of the Central Cache System being requested.

As discussed above, in the preferred embodiment, different monitors are used to protect the global shared control structures of the Central Cache System 304-5 and the structures 510 for each cache. One monitor referred to in FIGS. 8b and 8d as the Directory Monitor is used to protect access to the Cache Directory 500. As indicated, a monitor protects the structures for each specific central cache. Thus, there is one such monitor for each central cache that exists.

FIG. 8b shows that for most functions performed by the control mechanism 560 of the Central Cache system 304-5 proceed in the following manner. First, the Directory Monitor is entered as indicated in block 820-21. Next, the control mechanism
560 searches Cache Directory 500 for an entry representing the requested central cache as indicated in block 820-22. If an entry for the requested central cache cannot be found, then the requested central cache is deemed to not exist and the control mechanism 560 sequences to block 820-91 where the Directory Monitor is exited. If the requested central cache exists, that is, an entry for the cache is found in the Cache Directory 500, the control mechanism 560 exits the Directory Monitor as indicated in block 820-23, and the monitor associated with the requested central cache is entered as indicated in block 820-24. The control mechanism 560 then exits as indicated in block 820 of FIG. 8a and the control mechanism 560 sequences to the Perform Main Operation block 840.

For the Create Cache function, control mechanism 560 begins by entering the Directory monitor as indicated in block 820-31 of FIG. 8b. Next, control mechanism 560 makes a check to determine if there is a OCM delete operation in progress as indicated in block 820-32. As discussed above, the Obsolete Code Manager, OCM 304-10 is a component of the preferred embodiment used to remove generated code from the central cache system when it no longer applies to the current state of the relational tables, or permissions thereof It will be appreciated that the OCM component 304-10 is not a required component of a central cache system.

If control mechanism 560 determines that there is an OCM delete operation in progress as indicated block 820-32, the Directory Monitor is exited and control mechanism 560 waits until that operation is completed as indicated in block 820-33. Once that occurs, the control mechanism 560 resumes operation by entering the Directory Monitor as indicated in block 820-31. If there is no OCM delete in progress as indicated in block 820-30, then control mechanism 560 checks to see if the specified central cache exists as indicated in block 820-34. If it already exists, another cache with the same name cannot be created so control mechanism 560 exits the directory monitor as indicated in block 820-91. If the specified cache does not yet exist, the control mechanism 560 can exit to block 820 of FIG. 8a so that the main function, namely the Create Cache, can be executed or processed.

For the Delete Cache function, control mechanism 560 begins by entering the monitors (i.e., Directory Monitor) as indicated in block 820-41. As with the Create Cache function, if an OCM delete function is in progress 820-42, the control mechanism 560 exits the Directory Monitor and the cache system control mechanism 560 waits until that function is completed as indicated in block 820-43. Then the control mechanism 560 resumes control by re-entering the Directory Monitor 820-41. If there is no OCM delete function in progress 820-42, control mechanism 560 checks to see if the specified cache exists 820-44. If the named cache does not exist there is nothing to delete, so the control mechanism exits the Directory Monitor as indicated in block 820-91. If the specified cache exists 820-44, the control mechanism 560 sets the cache state in the Directory to delete-pending as indicated in block 820-45 and then exits the Directory Monitor as indicated in block 820-46. The control mechanism 560 then enters the monitor associated with the named cache as indicated in block 820-47 and reenters the Directory Monitor as indicated in block 820-48. The control mechanism 560 exits its flow to block 820 of FIG. 8a, ready to perform the main operation portion of Delete Cache function.

As indicated in FIG. 8b, for the List Caches function, the control mechanism 560 enters the Directory Monitor as indicated in block 820-51 and exits control from outer block 820. For the Delete Obsolete Entries function, associated with the Obsolete Code Manager, OCM, control mechanism 560 begins by entering the Directory Monitor as indicated in block 820-61. If an OCM delete is in progress in block 820-62, the control mechanism exits the Directory Monitor and the cache system waits until OCM delete is complete as indicated in block 820-62. If an OCM delete function is not in progress 820-62, control mechanism proceeds by setting an OCM Delete in Progress flag as indicated in block 820-64, and then exits the Directory Monitor as indicated in block 820-65. Then, for each operational central cache listed in the Cache Directory 500, the control mechanism 560 enters the monitor associated with that cache as indicated in block 820-66. The control mechanism 560 then exits from the outer block 820, ready to perform the main operation portion of the Delete Obsolete Entries function

FIG. 8d

FIG. 8d illustrates in greater detail, the operations of block 860 of FIG. 8a which is reached following the execution of the main operation requested functions of block 840. These operations are required to exit, or otherwise wrap-up the monitors left in the entered state from performing the operations of FIG. 8b. As in FIG. 8b, the flow executed by control mechanism 560 depends on the particular cache function requested. For most of the functions, as indicated in block 861-21, all that is required is to have the control mechanism 560 exit the monitor for the specific central cache that was accessed by the function. Once this

occurs, control mechanism 560 exits control from outer block 860.

For the Create Cache function, control mechanism 560 begins by creating and initializing the monitor for the central cache that is being created as indicated in block 860-31. The control mechanism 560 then exits the Directory Monitor as indicated in block 860-32 and then exits the outer block 860. For the Delete Cache function, control mechanism 560 begins by setting a delete-in-progress flag as indicated in block 860-41. Then control mechanism 560 attempts to terminate the monitor associated with the specific central cache. It will be noted that in the preferred embodiment, monitors utilize limited resources, so when a particular monitor is no longer required, such resources are returned to the operating system by terminating the monitor.

If there is a process waiting to enter the monitor, the termination request will fail. If the monitor termination fails due to this condition in block 860-42, control mechanism 560 sends a Signal event to the waiting processes as indicated in block 860-44 and then makes another attempt to terminate the monitor 860-42. Control mechanism 560 continues this operation until there are no more processes waiting to enter the monitor causing the check of block 860-43 to take the "no" path. The control mechanism 560 then exits the Directory Monitor as indicated in block 860-45. Since the monitor is contained within a critical section, which was entered when the terminated monitor was entered, the critical section must be explicitly exited. Therefore, control mechanism 560 exits the critical section as indicated in 860-46, and then exits the outer block 860.

For the List Caches function, control mechanism 560 only needs to exit the Directory Monitor as indicated in block 860-51. For the Delete Obsolete Entries function, associated with the Obsolete Code Manager, OCM, control mechanism 560 begins with block 860-61. For each operational central cache listed in the Cache Directory 500, the control mechanism 560 exits the associated monitor. The monitors are exited in reverse order from the order in which they were entered in block 820-66 in FIG.
8b. Control mechanism 560 resumes operation with block 860-62 by entering the Directory Monitor. The control mechanism 560 resets the OCM delete-in-progress flag as indicated in block 860-63, and signals any processes waiting for OCM delete to complete as indicated in block 860-64. The control mechanism exits the Directory Monitor as indicated in 860-65 and then exits the outer block 860.

FIG. 8c

FIG. 8c illustrates in greater detail, the operations of block 840 corresponding to the main operation of the cache function requested. As indicated, control mechanism 560 sequences to a different place/operation based on the cache function being requested. The main functions of the Central Cache System 304-5 include the Find Entry function of block 840-10, the Insert Entry function of block 840-20, the Delete Entry function of block 840-30, the Create Cache function of block 840-40, and the Delete Cache function of 840-50). These functions are shown in greater detail in FIGS. 8c1 through 8c5.

FIGS. 8c1 through 8c3

The Find Entry function of FIG. 8c1 begins with control mechanism 560 performing a search of the cache as indicated in block 840-110. This search operation is illustrated in greater detail in FIG. 4b. If there is a cache "hit", that is, the desired entry in the cache is found in the central cache 840-120, control mechanism 560 sequences to block 840-130 wherein the code associated with the found entry is copied by control mechanism 560 to the location specified by the caller (i.e., the SQL Cache Manager Interface Component 304-1). The control mechanism 560 relinks the Cnode representing the found cache entry at the head of the most-recently-used (MRU) list as indicated in block 840-140. In this case, the control mechanism function will return with a "cache hit" status. If the cache search results in a cache "miss", that is, the desired entry is not found in the central cache as indicated in block 840-120, the control mechanism function will return a "cache miss" status.

The control mechanism 560 begins Insert Entry function processing of FIG. 8c2 with a search of the cache as indicated in block 840-210. This search is illustrated in greater detail in FIG. 4b. If there is a cache "hit" 840-220, this means that the entry has already been placed in the central cache. Normally this will not be the case since an Insert Entry function usually follows a Find Entry function that has resulted in a "miss". However, when there are multiple processes accessing the central cache, the particular entry may have been inserted between the time of the Find Entry that resulted in a "miss" and the time of the current Insert Entry function. The search indicated in block 840-210 is used to make sure that duplicate entries are not put into the cache. Therefore, if control mechanism 560 detects a "hit" in block 840-220, most of the processing of the Insert Entry function may be skipped and control mechanism 560 returns to exit block 840. If the cache search does not result in a "hit", control mechanism 560 takes the "no" path of block 840-220.

Control mechanism 560 performs a calculation to see if the memory required by the current entries in the cache plus the code for the entry being inserted exceeds the configured maximum as indicated in block 840-230. If so, the control mechanism
560 deletes the excess code as indicated in block 840-240. This operation consists of deleting one or more entries starting from the end of the MRU list until the memory required for the code in the cache including the code being inserted is less than or equal to the configured maximum. If the memory required for the current entries in the cache plus that required for the entry being inserted is less than or equal to the configured maximum as indicated in block 840-230 "no" path, or the excess code has been deleted as indicated in block 840-240, control mechanism 560 resumes or sequences to block 840-250 in which it performs the operation of inserting the Cnode representing the new entry. This operation involves linking the Cnode into the appropriate bucket and placing the Cnode at the head of the MRU list. Then control mechanism 560 creates a code segment 540 to hold the generated code being inserted into the cache 840-260. The code is copied into the created segment 840-270. The code is then linked into the OCM structures 840-280 and control returns to exit block 840.

The control mechanism 560 begins Delete Entry function of FIG. 8c3 with a search of the cache as indicated in block 840-310. This search is shown in greater detail in FIG. 4b. If the search does not result in a cache "hit", that is, it results in a cache "miss", the entry does not currently exist in the cache and control mechanism 560 returns to exit block 860. If the search results in a cache "hit" as indicated in block 840-320, control mechanism 560 continues the deletion of the entry by unlinking the code from the OCM structures as indicated in block 840-330, deleting the code segment as indicated in block 840-340, and the freeing the Cnode as indicated in block 840-350. Freeing a Cnode involves removing the it from the bucket list in which it existed, moving the Cnode to the end of the MRU list, and marking the node as "available". Moving the node to the end of the MRU list makes it available for reuse ahead of any active Cnodes.

FIGS. 8c4 and 8c5

FIGS. 8c4 and 8c5 show in greater detail, the Central Cache System functions Create Cache and Delete Cache. The control mechanism 560 begins the Create Cache function of FIG. 8c4 by searching for an available slot in Directory Table 500 as indicated in block 840-410. If an available slot is not found 840-420, the control mechanism function returns an error condition to the caller when the Central Cache System control mechanism software is exited. If an available slot is found in the Directory Table, the control mechanism 560 makes an entry into the Directory Table 500 and enters information related to the cache, such as the cache name, the date, and the time into this entry as indicated in block 840-430. The control mechanism 560
then creates the segments required for the cache as indicated in block 840-440. These segments include the Bucket segment 510b, the Cnode segment 510c, the Code Descriptor segment 510d and the obsolete code manager segments 510e, consisting of the TMO Bucket segment and the TMO Entry segment. The control mechanism 560 allocates a rotation set from the linkage segment 520. This set consists of the descriptors that specify the cache data segment to be used for the cache 510a, as well as the condition id slot to be used by the monitor for the central cache. The control mechanism 560 stores data describing the characteristics of the cache being created in the cache data segment as indicated in block 840-460, and initializes the Cnode structures as indicated in block 840-470. This initialization includes initialization of the bucket structures and the linking of all the nodes into the MRU list. Then, the control mechanism 560 initializes the OCM structures as indicated in block 840-480, and sets the cache state in the Cache Directory 500 to "operational". The control mechanism 560 returns to exit block 840.

Control mechanism 560 begins the Delete Cache function of FIG. 8c5 with block 840-510, wherein the code segments associated with each entry in the cache are deleted. Then, as indicated in block 840-520, control mechanism 560 resets the data-segment-in-use flag in the Cache Data segment 510a. The segments associated with this cache are deleted as indicated in block 840-530. These segments include the Bucket segment 510b, the Cnode segment 510c, the Code Descriptor segment 510d and the obsolete code manager segments 510e, consisting of the TMO Bucket segment and the TMO Entry segment. Finally, as indicted in block 840-540, control mechanism 560 deletes the entry for this cache from the Cache Directory 500. The control mechanism 560
returns to exit block 840.

From the above, it is seen how the multicache organization of the present invention can be configured as a function of the type of applications being run by the system and the level of performance desired based on available memory resources. While many of the same mechanisms may be used by both local and central cache systems, the dynamic creation of persistent central cache structures provides a level of performance which is substantially greater than that previously provided by the prior art local cache systems.

While the present invention was described relative to processing SQL statements, it will be obvious to those skilled in the art that the multicache organization of the present invention may be used in conjunction with other languages, code, etc.

APPENDICES

I. Glossary

II. Description of Code Generation Support Routines

III. Description of Cache Utility Interface Commands

IV. Description of Configuration Interf