Method and apparatus for cross-node sharing of cached dynamic SQL in a multiple relational database management system environment

[0002] This invention relates to database management systems, and has particular application to relational database management systems (RDBMS) and more particularly to a method and apparatus for efficiently sharing of instructions, especially cached dynamic SQL statements between applications connected at different nodes in a multiple node database while maintaining cache and application integrity across the nodes.

[0003] Structured Query Language (SQL) is the database access language most commonly used to access relational databases (such as the DB2 product sold by IBM Corporation) in an open, heterogeneous environment. Although this disclosure refers to the DB2 relational database product sold by IBM, individuals skilled in the art will recognize that the caching of database access statements is applicable to any relational database management system (RDBMS).

[0004] Within this specification including the claims, the following terms will be used:

[0005] There are two basic types of SQL statements, static and dynamic. In using static SQL the user embeds SQL requests for data in an application program. An SQL precompiler removes these statements from the application program and replaces them with function calls whose parameters indicate a specific section entry for the package corresponding to the current source file. The removed SQL statement is then sent to the database management system for compilation. Compiling (also known as preparing) a SQL statement is the process by which the database management system SQL compiler chooses and builds an access plan to efficiently resolve the SQL statement. The access plan is saved in its executable format, a section, in the system catalogues.

[0006] The parsing of the statement and building of the access plan can be relatively long and complicated. Compilation of static SQL improves run time performance by building the access plan before the application is executed.

[0007] Dynamic SQL is SQL issued by an application that is not compiled until the time the application issues the query, and is often used for ad hoc SQL requests. For example, in a database used to track sales of individual products, a dynamic SQL query may be invoked to list the top ten products sold, by sales region. Depending upon the nature of a dynamic SQL request, the time required to parse it and create an access plan to satisfy the user request can be significant. Furthermore, if the dynamic SQL request is repeated later in the application by the same agent or perhaps by a different agent, a new access plan must be created in each instance. Thus, the creation of an identical access plan may often have to be repeated, thereby impacting performance of the application.

[0008] In such a scenario, each of the nodes involved in processing the query must have a copy of the “section” in order that the query runs completely. Including all the data from all the nodes. As a basic solution to this requirement, the dynamic SQL statement is compiled at the node where the application is running. The resulting section is then sent or “shipped” to the remote nodes. At each of the nodes “agents” on behalf of the application can then execute the query using the shipped section. Similarly, applications that are running on other nodes of the database that issue dynamic SQL, require the SQL to be compiled on the resulting section be shipped to all of this remote nodes that are involved in the transaction.

[0009] Given the potentially high cost of compilation and of SQL sections, it is desirable to avoid repeated compilation of the identical SQL request, and rely on previously compiled sections.

[0010] In accordance with another aspect of the present invention there is provided a database system comprising:

[0011] a) a plurality of nodes

[0012] b) a plurality of databases stored on the nodes; and

[0013] c) a global dynamic SQL statement cache stored on at least one node; the global dynamic SQL cache being accessible to a plurality of applications in the database system.

[0014] In accordance with the present invention there is also provided a method of maintaining cache and application integrity across a relational database system comprising a plurality of nodes and a plurality of databases shared on the nodes, the method comprising the steps of: (a) providing for at least some of the databases, a global cached including information to enable agents to access the databases; (b) origination a request through a coordinating node, the coordinating node sending information on the dynamic SQL request to be executed to remote nodes: (c) having each remote node receive the request and check the global cache on the respective remote node for a current copy of the dynamic SQL entry; and (d) if the remote node does not have the current entry, the remote node requesting the coordination node to send the current version of the dynamic SQL entry and its section (e) having the global dynamic SQL cache be accessible for applications that are running at any node in the database system so that an application is able to re-use a cached copy of a previously inserted dynamic SQL entry and its section regardless of the node at which it was originally compiled.

[0015] Various aspects of the invention provide a data processing system, a method, and software for operating it where the data processing system includes a number of interconnected nodes. At least one data partition resides on one of the nodes, and one or more tables reside in a data partition. One of the nodes has a catalogue containing metadata describing tables and other objects and relationships therebetween in the data processing system. There is a global instruction cache at each node having a statement portion storing instruction statements and associated executables; each of the executable is designed for a particular environment; the instruction cache includes a dependency portion which lists objects and links them to the corresponding executable entries that depend on the objects; the instruction cache includes a shipped variation portion, each entry of the shipped variation portion refers to one executable entry and identifies the node from which the statement associated with the executable was originally shipped and the identification of such executable in the node from which it was originally shipped. The cache includes an invalidations in progress portion, each entry of the invalidations in progress portion refers to an object entry in the dependency portion.

[0016] In a further aspect of the invention the data processing system a catalogue node has a catalogue containing metadata describing tables and other SQL objects and relationships therebetween in the data processing system; wherein the SQL objects may include tables views of tables, aliases of tables, functions, and user defined types among others; a global SQL instruction cache at each node having a statement portion storing dynamic SQL statements and associated executables; each the executable being designed for a particular environment; the SQL cache includes a dependency portion which lists SQL objects and links them to the corresponding executable entries that depend on the objects; the SQL cache includes a shipped variation portion, each entry of the shipped variation portion refers to one executable entry and identifies the node at which the SQL statement associated with the executable was originally compiled and identification of such executable in the node at which it was compiled; the SQL cache includes an invalidations in progress portion, each entry of the invalidations in progress portion refers to an object entry in the dependency portion.

[0017] In yet a further aspect of the invention the data processing system the global SQL instruction cache includes a statement entry which includes:

[0018] SQL instruction statement text and a list of associated environment entries;

[0019] each the environment entry includes a description of the environment and a list of variations, each the variation includes: an identification number; the executable itself; a list of required privileges; a reference available to the entry in the shipped variation list portion of the cache.

[0020] Another aspect of the invention provides a method of executing an SQL request issued by an application from a node (a coordinator node) comprising: searching in a global SQL cache at the coordinator node for an executable that is associated with an SQL statement and environment corresponding to the SQL request; if the executable is not found in the global cache then the database management system compiles the SQL request at the coordinator node then inserts an executable entry into the global cache at the coordinator node; searching at the coordinator node in the global SQL cache for an SQL statement entry, the text of which matches the text of the SQL request; if the entry is not present at the coordinator node, inserting, by the database management system, a new SQL statement entry, the text of which matches the SQL request; if the entry is present then the database management system searches for environment entries associated with the SQL statement entry for an environment entry that matches the environment for which the SQL request was issued; if the entry is not present then the database management system inserts into the cache a new environment entry matching the environment of the SQL request; the database management system searches for a variation entry comprising a valid executable corresponding to the SQL request, which includes the SQL statement and environment entry, and, if a valid executable is not found then the database management system compiles the SQL request, referring to the appropriate environment, into an executable (a set of one or more executable instructions) to carry out the SQL request; inserting into a variation entry the compiled executable, including a list of required privileges, a list of dependent objects, an identification number of the variation entry, and identification of the validity of the entry; and, for each object in the list of dependent objects searching in the dependency portion of the global SQL cache for an object entry with a matching object name and object type, and if it does not exist in the cache, inserting a new entry.

[0021] The invention also provides for a data processing system having a plurality of nodes at which processing may be performed, a method of identifying an executable comprising identifying the executable by node identification and entry identification associated with the first node of the data processing system that shipped the executable to any other node in the data processing system.

[0022] Preferably the executable is identified by node and entry identification associated with the first node of the data processing system that compiled and shipped the executable to any other node in the data processing system.

[0023] Another aspect of the invention provides a method of indexing data and instructions for storage and retrieval for a multi-node data processing system comprising:

[0024] storing identification of the data and instructions in a list wherein the data and instructions are identified by node identification and entry identification associated with the first node that shipped the data and instructions to any other node.

[0025] Preferably the node list comprises an entry portion and a lookup portion wherein:

[0026] the entry portion stores the following:

[0027] SQL statements;

[0028] executables;

[0029] environment parameters;

[0030] entry identification for that entry in the list; and,

[0031] wherein the lookup portion includes the following:

[0032] the entry identification;

[0033] the identification of the node that first shipped or compiled the executable;

[0034] entry identification of the executable at the node that first shipped or compiled the executable.

[0035] In still another aspect of the invention which may be used in a data base system, having a plurality of interconnected nodes, managed by a database management system, each of the nodes having an unique identification, the nodes being capable of storing or processing information, each node having a cache, the cache having a statement portion and a shipped variation portion;

[0036] the statement portion of the cache at each node for storing SQL statements, executables associated with the SQL statements, and environments with which the executables are associated, wherein the executables are each identified by an unique entry identification;

[0037] the shipped variation portion (list) for storing identification entries for the executables including:

[0038] identification (ID number) of the executable which corresponds to the identification (ID number) of the associated entry in the statement portion of the cache;

[0039] the node identification (ID number) of the node from which the executable was originally shipped from or compiled; and,

[0040] the identification (ID number) of the executable at the node from which the executable was first shipped;

[0041] a method of executing a data processing request from a node (the coordinator node) in a manner adapted to avoid redundant shipping of executables comprising:

[0042] finding a suitable executable for carrying out the request by:

[0043] searching the statement portion of the cache at the coordinating node for an executable that is associated matching the request and environment in which the request was issued; and,

[0044] if the matching statement and environment were not found in the statement portion of the cache of the coordinating node, then compiling the request and inserting the request into the cache;

[0045] sending a request to all other nodes of the data base management system that are necessary to process the request (subordinate nodes of the coordinating node) wherein the request to all other such nodes includes: the identification of the coordinator node and the entry identification of the executable, and if there is a entry in the shipped variation list associated with the executable on the coordinator node cache then the database management system also ships identification of the node and entry.

[0046] In yet another aspect the invention provides for use in a database system having a plurality of nodes, and being managed by a database management system, each node having a storage cache for indexing and storing instructions including statements, executables and environment information, a method of executing a request by an application at a first node wherein the application identifies the executable that is desired to be executed, searches at the first node for the executable, and, if the executable is not found at the node compiling the executable, then, using identification of the node by the node and entry identification of the executable on the node from which it was first shipped or compiled, requesting execution by all other nodes required for executing the executable;

[0047] the other nodes searching in their respective caches by the node and entry identification of the executable assigned by the node from which it was initially shipped or compiled; and,

[0048] if the executable is found at each the other node executing it at each node at which it is found; and,

[0049] if it is not found at one or more of the other nodes requesting that the executable be shipped from the first node to the nodes where the executable was not found; and, then executing the executable at each of the other nodes receiving it.

[0050] Another aspect of the invention also provides a method of performing data processing in a multi-node data processing system by sharing dynamic compiled (SQL) executable data processing statements between nodes of the data processing system comprising:

[0051] identifying each compiled SQL statement with a (numerical) identifier;

[0052] at a node receiving statements (a receiving node) storing a list of statements received at the receiving node listing the originating node and identifier for each of the received statements;

[0053] upon receiving a request for processing with a specified statement having the receiving node check its list of statements received for the specified statement by its originating node and identifier;

[0054] comparing the identification of the specified statement with the statements in the list of the receiving node, and if a match if found then accessing the statement stored at the receiving node;

[0055] if a match is not found, having the receiving node request the specified statement from another node, and when it is received then loading it into its local cache;

[0056] having the receiving node update its list of statements;

[0057] executing the statement at the receiving node.

[0058] In another aspect the invention provides a method for use in a data base management system having a plurality of interconnected nodes, each of the nodes having an unique identification, the nodes being capable of storing or processing information,

[0059] one of the nodes comprising a catalogue node having metadata describing tables and other SQL objects and relationships between them in the data processing system;

[0060] each node having a cache, the cache having a statement portion and a dependency portion;

[0061] the statement portion of the cache at each node for storing SQL statements, executables associated with the SQL statements, and environments with which the executables are associated, wherein the executables are each identified by an unique entry identification;

[0062] the dependency portion for storing object entries for the SQL objects including:

[0063] identification of the object which corresponds to the object name and object type;

[0064] a list of entries referring to executable entries in the statement portion of the cache whose execution relies on the definition and existence of the object;

[0065] a method of updating entries in the cache at each node when object definition entries in the catalogue are changed comprising:

[0066] updating the catalogue node by removing all invalid entries and broadcasting instructions to other known nodes of system to remove invalid entries from their respective caches, by:

[0067] making a first broadcast of instructions to the nodes to secure entries in the dependency portion of each cache by first:

[0068] finding an object entry associated with the object that is being changed in the dependency portion of the cache;

[0069] if such an object entry in the dependency portion of the cache is not found, inserting a new object entry;

[0070] securing the object entry in the dependency portion of caches of the other nodes; marking all the executables currently listed as being associated with the object as invalid;

[0071] reporting to the database management system at the catalog node that the object entry in each of the caches have been marked as secured;

[0072] examining any executable newly arriving in a cache of a node and determining if it depends on an object that has been secured, and if so, marking it as invalid;

[0073] making a second broadcast from the catalog node to all known nodes to:

[0074] mark all entries in the caches which are dependent on a secured object or an invalid object as being invalid; and,

[0075] removing the secured marking of all secured objects;

[0076] removing all invalid entries and objects.

[0077] In a further aspect of the immediately above method entries are updated in the cache at each node when a node is added to the database comprising:

[0078] when a new node is added to the database system, sending from the catalogue node a list of all secured objects to the new node;

[0079] at the new node, for all the objects in the list of the objects secured at the catalog node, creating and securing a new object entry in the dependency portion of the cache of the new node;

[0080] at the new, nodes examining any executable newly arriving in the cache of the new node and determining if the executable depends on an object that has been secured, and if so, marking it as invalid.

[0081] A further aspect of the invention provides a computer program product comprising computer readable storage for storing statements or instructions for use in execution in a computer in accordance with one or more aspects of the invention described above.

[0082] FIG. 1 depicts a multi-node database management system.

[0083] FIG. 2 depicts a dynamic SQL cache.

[0084] FIG. 3 depicts the structure of the dynamics SQL portion of a global cache.

[0085] FIG. 4 depicts the basic unit of the dependency portion of a dynamic SQL cache.

[0086] FIG. 5 depicts the shipped variation portion of a dynamic SQL cache.

[0087] FIG. 6 depicts the invalidation in progress portion of the cache.

[0088] FIGS. 7A, 7B, and 7C depict a flow chart illustrating an embodiment of the present invention for executing SQL requests in a multi-node environment.

[0089] FIGS. 8A, 8B, and 8C depict a flow chart for a multi-node database management system in accordance with an embodiment of the present invention.

[0090] FIG. 9 depicts a flow chart of anew node registering with a database management system in accordance with the invention.

[0091] FIG. 1 is a conceptual diagram of a Relational Database Management System (RDBMS) 10. The RDBMS of 10 of FIG. 1 illustrates only one of many configurations available in an RDBMS and is intended only to show a networked system that may utilize the present invention. In the configuration as shown, RDBMS 10 contains a plurality of nodes (12, 14, 16, 18). Each node (12, 14, 16, 18) may contain a partition or all of a database. In the example of FIG. 1, the RDBMS has two databases, although any number of databases can be provided, the content of which is partitioned among the plurality of nodes. The first of these databases is divided into a partition 20 and a partition 21. The catalogue 22 for this first database is stored on catalogue node 18. The catalogue 22 contains tables in which resides all the “meta-data” such as the structure, tables, packages and functions relating to the first database. The second database is divided into partitions 23, 24 and 25. Note that in the illustrated example, the partition 24 of the second database also contains the catalogue tables for the second database. Thus, a catalogue node 18 may contain data as well as catalogue tables. Catalogue tables are per database and can be located at different nodes for different databases. This means that the term “catalogue node” is relative per database, i.e. the catalogue could reside on any node.

[0092] The global cache acts as a repository for package and section information for static SQL and statement and section information for dynamic SQL as detailed below.

[0093] In this disclosure, we discuss the method and apparatus for the dynamic SQL cache only.

[0094] In the preferred embodiment, the global cache is kept at the database level, and is accessible to all agents for a database at a particular node of the database (physical or logical). It is allocated from the same memory set as other database-level entities, such as the lock list or buffer pool; it is created when the database is initialized, and it remains active until the database is shut down. The global cache acts like a “public” library for all the agents using the database at a given node. Agents simply copy the package information and the modifiable portions of the sections (e.g. buffers and flags).

[0095] Referring to FIG. 2, the dynamic SQL portion 40 of the global cache is subdivided into four portions: the statement portion 41, the dependency portion 42, the shipped variation portion 43 invalidations in progress list portion 44. The statement portion 41, also known more generally as the entry portion of the cache contains SQL statement entries 62 which contain the text of the cached dynamic SQL statements as well as the different sections compiled for each SQL statement. The statement portion 41 of the dynamic cache 40 is used to support application requests to prepare the dynamic SQL statement 64 and obtain an executable section. The dependency portion 42 of the dynamic cache 40 contains entries for all the objects upon which the cached dynamic SQL sections are dependent. This information is used to support cached object invalidation due to data definition language statements and other database activities. The shipped variation portion 43, also known as the lookup portion of the cache is a list used to lookup entries that have been shipped from other nodes of the database system. The invalidations in progress portion 44, contains a list of objects that are currently being modified in the database management system.

[0096] Referring to FIG. 3, the primary structure of the dynamic SQL portion 40 of the global cache is based upon the unique text for a given SQL statement 64, which is stored within SQL statement entry 62. A SQL statement entry 62 contains characteristic information about the SQL statement 64 that is determined once the first occurrence of the statement text 64 is compiled. This information is invariant since the statement text 64 is constant and these characteristics are inherent in the statement text 64 itself, independent of the environment in which it was compiled.

[0097] The compilation environment 66 contains information on the environment used to generate or compile the section. The compilation environment 66 contains all information not already contained in the catalogue tables, that influence or control an access plan created by the SQL compiler, and thus the section.

[0098] Below each compilation environment 66 are stored individual units known as “variations” 68. A variation 68 represents a unique section for the statement text 64, where the uniqueness is specified by the compilation environment 66 used to generate the section. The compilation environment 66 encompasses all those elements that affect the nature and result of the section generated by the SQL compiler for a dynamic SQL statement (e.g., special registers, relevant package compilation defaults, use of default qualifiers, use of function path, etc.). Note that since privileges do not affect the actual section generated, only whether it is allowed to be executed, the prerequisite privileges for a dynamic SQL statement 64 are irrelevant to the compilation environment 66. In the preferred embodiment, privileges are not part of the compilation environment 66.

[0099] A variation 68 is simply the representation of the fact that two application issuing the same dynamic SQL statement 64 in the same context with the exact same compilation environment 66 should generate the exact same section, although the results of execution may differ due to actions within the individual units of work. For example, two applications using the same section for SELECT C1 FROM T1 may return different results if the first application has inserted some rows into T1 but not committed its changes. The first application will get the row returned by the section, but the second application may not.

[0100] In addition to the identifying compilation environment, each variation 68 under a statement entry 62 and compilation environment 66 also contains: the required privileges list of privileges needed to execute the section, the dependency list for the section and the section generated for the specified compilation environment, and a pointer (reference) to an entry in the shipped list. The dependency list refers to those objects and entities in the catalogue tables required, either directly or indirectly, by the section for a variation 68. The dependency list is also used to determine whether the section is no longer valid when an object on the dependency list is dropped; if the variation 68 is in use at the time, the drop request is rejected. When a section is no longer valid, the variation 68 becomes an invalid variation 70 and must be regenerated. Details of the dependency list and its use to invalidate dynamic SQL sections is discussed below in the description of FIG. 4. The major difference between dependencies and privileges is that the loss of privileges does not result in any variation 68 being marked as an invalid variation 70 since, as noted previously, privileges do not affect the contents of the section. Since a variation 68 represents a dynamic SQL statement, and dynamic SQL always reflects the current environment, other actions such as issuing the RUNSTATS command against a table or creating a new User Defined Function (UDF) can cause a variation to be marked invalid.

[0101] Each dynamic SQL statement entry 62 may have one or more compilation environments 66, but each compilation environment 66 may contain only one valid variation 68. An invalid variation 70 will be flushed from the cache during cache space management. For example, an ALTER TABLE statement can cause a variation 68 to become an invalid variation 70 in the dynamic cache 44 and will eventually be flushed from the dynamic cache 44.

[0102] The variation entry includes a pointer or reference to an entry in the shipped variation list, if such an entry exists.

[0103] Referring now to FIG. 4, the basic unit of the dependency portion 42 of the dynamic SQL cache 40 is the object 72. An object 72 represents a database object upon which a dynamic SQL variation 68 is dependent. Each object 72 is associated with one or more variations 68. Each object 72 in the dependency portion 42 of the global cache is distinct and only one occurrence of the object 72 may appear at any one time. To facilitate access, each object 72 is associated with a specific object type anchor point 74 by hashing the qualified object name 76 to a unique anchor point 74. Once associated with an anchor point 74, the object 72 is inserted into the list of objects 78 off that anchor point 74 in alphabetical order based on the object name 76 followed by the qualifier. Anchor points 74 are type specific (i.e. an alias anchor point only holds aliases) and only objects 72 of the type represented by the anchor point 74 are to be found off that anchor point 74. In the present embodiment, this includes objects of types: view, alias, index, User Defined Functions (UDF), table, structured types, summary tables, hierarchies, pagesizes, summary tables and hierarchical tales. In addition, a field is kept for each object, indicating whether the entry is secured.

[0104] An essential characteristic of a dynamic SQL statement is that the running of it should reflects the current database environment as if it were compiled for everytime the query were issued; the dynamic SQL cache 44 does not alter this characteristic. If an environment change affects a dynamic SQL section, the variation 68 for that section will become an invalid variation 70. When invalidating a dynamic SQL variation 68 due to a change in a dependent object, the name of the affected object 76 is hashed to obtain the appropriate anchor point 74 for the same object type. The list of objects 78 is then scanned to find a matching object 72. Once a matching object 72 is found, the list of dependent variations below that object is scanned and an attempt is made to invalidate them in the statement portion of the cache.

[0105] Referring to FIG. 5, the shipped variation portion 43 of the cache is comprised of a list of zero or more “shipped” entries 102. Each shipped variation entry 102 refers to only one variation entry in the statement portion of the cache. The entry is identified by “original node” identification, that is it includes the node # at which the variation was originally compiled and shipped, as well as the variation ID at that node at which the variation was compiled. This original node information is used for lookup purposes. The shipped variation entry also includes the ID of the variation in that node's global SQL cache, so that once a match is found in the shipped variations list based on the original node information, the entry then refers to the actual local entry in the current node's cache. Note that the original node information does not necessarily correspond with the node, and variation ID corresponding to the coordinating node that actually shipped the query.

[0106] Referring to FIG. 6, the “invalidations in progress” portion 44 of the cache is comprised of zero or more entries 130. Each entry indicates an object that is in the process of being dropped, altered, or otherwise causing invalidation.

[0107] This object refers to an entry in the dependency portion of the cache. For the catalog node, entries are added to this list when an attempt to modify the definition of a specific object is made. At other nodes Entries are only added at node startup/registration time as noted in the description of node startup.

[0108] Referring to FIGS. 7A, 7B, and 7C, an algorithm is a method for executing SQL in a multi-node environment is described. In this method, it is ensured that the SQL request is carried out by the database management system on behalf of the application on all the nodes relevant to that query. As well the method of lookup and identification of the appropriate variation entry on the subordinate node is optimized for an environment where identical SQL requests are issued by applications at many different nodes of the application. By appropriately labeling the shipped variation entry with the node number and the id of the variation at which the section was originally compiled, needless duplication of entries is eliminated and communication costs are greatly reduced.

[0109] The method as noted in the diagram is as follows. An application issues a request to execute an SQL statement that is received by the database manager at the coordinator node. Searching for a match based on the SQL statement and environment of the application request, a search is made in the statement portion 41 of the dynamic SQL cache 40 at the coordinator node. If a match is not found, a new variation entry is inserted appropriately into the statement portion of the cache at that node. At this point the variation entry, identified by an id unique to the coordinator node, is in place; this variation entry includes the section (executable) that is to be executed at this node and a number of subordinate nodes. An ‘identifying’ request is sent to the subordinate node(s) to execute the section from an appropriate variation entry in the subordinator node that matches the variation entry at the coordinator. To do this, the request identifies the appropriate entry by the following information:

[0110] local node identification comprising the coordinator node id and the variation id at the coordinator node and

[0111] original node identification, which comprises the node at which this variation entry was originally compiled and shipped from and the variation id at that original node. The original node identification is derived from the shipped variation entry associated with the local variation id. If the variation does not have a shipped variation id (which would be the case if this variation is new and the section was just compiled; it also would be the case if this node has always been a coordinator node with respect to this SQL request and never a subordinate node), then the original node identification is set to be identical to the coordinator node identification.

[0112] At the subordinate nodes, this request to run the section of the variation identified as indicated is received by the DBMS. The shipped variation lookup list is searched to find an entry that matches the original node identification indicated above. If a match is found in that list based on the original node identification, then it refers to a variation in the statement (entry) portion from the cache, the section of which can then be used to run the query at that node.

[0113] If the a matching shipped variation entry is not found based on the original node identification, then the DBMS creates a new shipped variation entry in the shipped variation list, whose original identification is as supplied in the request. At this point this shipped variation entry does not correspond to a variation entry in the cache. The DBMS then determines if the original node number identified in the request matches the node number of the current subordinate node. If it is, then, since his current subordinate node is the original node, then we search the statement portion of the cache for the original node variation id. If this id is found (which is not necessarily the case; it may have been removed from the cache at this node by this time), then the desired variation has been found and the new shipped variation entry created above is set to be associated with (pointing to) this variation.

[0114] However if the current subordinate node is not the same as the original node—or if they are the same, but the original variation entry was found to no longer exist in the cache, then the DBMS needs to request that this variation entry be ‘shipped’ from the coordinator node. (Note, it cannot assume that it can request from the original node to find the entry as the entry is not guaranteed to be in the original node's statement portion of the cache; however since the coordinator node originated the request, we know that it is guaranteed to have the entry still present in its cache). Thus a new ‘ship’ request is sent back to the coordinator node (as determined from the local node identification part of the first identifying request), requesting that that node send back the full information associated with its local variation, whose identification number is sent to the coordinator node as the ‘local’ variation id. This request is received at the coordinator node, which then finds the id of the variation specified and sends back all the relevant information (including the statement text, the environment entry, and all other information associated with the variation including the section (executable). At the subordinate node, this information is received and then, based on the statement and environment information, a new variation and its companion entries are placed in the statement portion of the cache (as well as any associated dependency entries in the dependency portion of the cache). The newly created shipped variation entry (which indicates the original node information of this variation) in the shipped variation portion of the cache is then associated with (pointed to) with this new variation in the statement portion of the cache.

[0115] By having the shipped variation list lookup based on the “original node ID” we allow much more efficient cross node sharing.

[0116] The alternate, prior art solution can be summarized, via example as follows:

[0117] Application A connected at node 1 inserts or finds an existing variation entry for the executable version of the dynamic SQL at the SQL cache at node 1. It has a unique id, say NNN.1. It sends a request to relevant nodes to execute validation NNN.1 from node 1. At each of these other nodes, a lookup is performed in its shipped variation list to determine if there is an entry for NNN.1 from node 1 that has already been shipped to this node. If not, it requests that node 1 ships that NNN.1 entry information to the current node; once shipped an executable entry for the original text is inserted into the cache at that node as well as an entry in the shipped list indicating that the new entry has been shipped as NNN.1 from node 1. As long as that entry is in the cache this entry in the shipped list ensures that anyone who issues the same text associated with entry NNN.1 at node 1 will also be able to have the SQL run on its behalf at other nodes without additional shipping.

[0118] In an environment where cross-node sharing is allowed, we find that this scheme by itself, while providing for a solution that works, will involve extra shipping of dynamic SQL entries. Consider the following three nodes of a multi-node database, in which different applications connected at each of the nodes issue the same dynamic SQL text: “INSERT into t1 values 1* ”, and where t1 is a table whose partitioning includes nodes 1, 2 and 3. In this case application A connects to the database at node 1, application B at node 2, and application C at node 3, and chronological execution at all 3 nodes proceeds down the diagram. The “values” entry “1” was merely chosen as an example.

[0119] It can be seen in this prior art implementation that when an attempt is made to share the cached dynamic SQL that has been shipped from another node we end up needlessly pulling extra copies of what is already in the cache to other nodes. This causes extra demands on the networks, poorer performance and extra demands on the memory of the nodes' SQL caches. Note that this needless shipping back and forth of the same SQL entry can continue if applications at each of the nodes continue to issue that same SQL text.

[0120] To solve this performance/resource problem, the identification of the dynamic SQL entry in the shipping process is based on original node information, which corresponds to the identification of the entry at node the request was originally compiled and shipped from. It is this compiled-at node information that is used to maintain and search the shipped list. The node at where the SQL is issued will send a request to all other nodes indicating not only which entry from the current node to execute, but also the node where the SQL was originally compiled. Further details can be seen in the revised flow of the previous scenario, where the same SQL request is issued in order from node 1, node 2 and node 3.:

[0121] Thus, by organizing the search in the shipped variation list based on the id and the node of the entry where it was first compiled, we are able to avoid needless shipping of entries and needless insertion of entries. In this example this method has changed the shipping situation: in which there are 3 insertions of entries on node 1 (one a compile, and two from shipping), 2 insertions of shipped entries on node 2, and 2 insertions of shipped entries on node 3 with the original scheme; with the proposed method each node has only one entry inserted, which implies an increase in performance by reducing the network traffic and the programming steps required to ship and entry from node to node and then insert it at the new node. By this identification schema, space usage in the cache is also reduced.

[0122] In order to minimize network traffic and to allow for the ignoring of nodes that are either down or have not connected to a particular database, a list of participating nodes for a database is built and maintained on the catalogue node. A participating node is a node which is active, connected to the database and has registered in the participating nodes list at the database catalogue node.

[0123] The list of participating nodes is used to define which nodes must be informed when a communication bulletin (described hereinbelow) is to be broadcast for a database. The information is broadcast to all nodes in the list of participating nodes other than the current one (catalogue node) by the agent wishing to send the information. Before any broadcast, the broadcasting agent must acquire the latch for the list of participating nodes to prevent any new nodes from being added. Processing for the cache at the catalogue node is handled by the broadcasting agent.

[0124] Certain actions affecting the definition of objects can be render a variation and its associate section (executable) invalid. That is, it should not be executed, otherwise internal system errors could occur. As an example, if the statement “SELECT*SNOWBELL.TI” is complied and inserted into the cache, then the action “DROP TABLE SNOWBELL.TI” must ensure that all variation in the cache, including the one for the statement above, are not being executed, and are marked as invalid, to prevent further execution.

[0125] In a multi-node environment, the request to invalidate based on an object drop/modification must be broadcast to all nodes from the catalogue node, in such a way that it is ensured that there are no variations that depend on the object on any other node that are still considered valid on any node.

[0126] The prior art for modifying objects involved sending a single broadcast from the catalog node to all nodes in the system. At each of the nodes in the system, the dependency portion 42 of the dynamic cache 40 is searched for an entry that matches the object name and object type of the object being modified. If an entry is found, then all the variations in the statement portion of the cache, that are referred to by this object entry in the dependency portion of the cache are marked as invalid. This proves to be adequate in a database management system that does not allow sharing. In that case a lookup in the statement portion of cache to match an SQL request will not be considered successful if it is found that the entry was in fact originally compiled at another node. However when the system allows sharing, there are situations in which, due to the timing of invalidation broadcasts and concurrent shipping of variations that may be happening on the system, a shipped variation may end up on one of the nodes caches that should be marked as invalid but in fact manages to remain marked as valid. If a new application issuing the same SQL on the shipped-to finds the entry in the cache, and sharing is allowed, it will use an invalid entry which could cause DBMS system failures. For illustrative purposes, on such a scenario is indicated in the 3 node table as follows (where chronological execution at all 3 nodes proceeds down the diagram; consider node 0 to be the catalog node).

[0127] It can be seen in this example that with respect to the application executing, the broadcast event reached the subordinate node before the variation entry had been shipped from the coordinator node, thus not finding an entry in the dependency portion 42 of the cache. A valid entry ends up at the subordinate node, and then if an application at that node later tries to ‘share’ that entry it would find an entry that looks to be valid.

[0128] FIGS. 8A, 8B, and 8C describe the general method for a multi-node invalidation that ensures that entries that should be invalid to not end up at any subordinate node, in which case sharing would then allow a new application at that node to run from an invalid variation and its section.

[0129] Referring to FIG. 8A, in this method, two separate broadcasts occur, the second of which does not complete until the first has completed successfully on all nodes. We consider generally a request originating at a node that is not necessarily the catalog node, to modify (in the example of FIG. 8A—dropping) an object. This request, since it involves a change in the definition of the object which is maintained in the catalog tables at the catalog node, is forwarded to the catalog node to control. At the catalog node, the request is received to modify/drop a specific object. When this happens a new entry is added to the invalidations in progress portion 44 of the cache (up list in FIG. 2), which indicates the object type, object name, as well as a unique identifier. (The purpose of this entry in the invalidations in progress list is discussed in the context of a modified node startup algorithm below.) Then phase 1 is executed at the catalog node and then a broadcast is issued to all nodes to execute phase 1 of the invalidation. Phase 1 (FIG. 8B) does not involve the active marking of variations as invalid. Instead it is performed to ensure that newly shipped variations that are dependent on the object that is being modified are immediately marked as invalid when being placed in the shipped-to node's cache. At each node in phase 1, this is done by searching in the dependency portion of the cache for an object entry that matches the object type and object name of the object being modified or dropped. If an entry does not exist, a new entry is created. At this entry the object is marked as “secured.” Once marked as secured, any new insertions of variations shipped from other nodes that attempt to insert a dependency entry (for the newly shipped variation) for the object being modified/dropped will note that the entry is secured, and will immediately mark the variation entry as invalid. Once the object entry in the dependency portion 42 of the cache is marked as secured, phase 1 is complete and control returns to the catalog node.

[0130] Once all nodes have completed phase 1, the DBMS then executes phase 2 of the invalidation—first locally at the catalog node, and then a broadcast request is sent to all nodes to execute phase 2 of invalidation for modifying/dropping a specific object.

[0131] In phase 2 (FIG. 8C), a search is performed in the dependency portion of the cache for the object that matches the name and the type of the object being modified. (This object entry should have been already marked as secured during the first phase.) Once this object has been located, all dependent variations, the list of which is maintained at the object entry, are marked as invalid in the statement portion of the cache. The invalidations in progress list is then searched for a matching object name and type. If one exists, it is dropped. Once this has been completed, the object entry in the dependency portion of the cache is then marked as not secured, and the second phase is complete. When the catalogue node is informed of the success of all second phases from all nodes, the object definition modification can then proceed.

[0132] In this 2 phase algorithm, the first phase has thus insured that the second phase can occur without regard for new shipping of variations that may occur while the second phase takes place, and thus ensures that all variations that should be marked as invalid are marked as invalid at all nodes of the system.

[0133] However this 2 phase algorithm alone still does not ensure that the invalidation is completely impervious to improperly marked variations. This is because the broadcast events only occur from the catalog node to all nodes that have been the catalog node recognizes; and those are only the nodes that have been registered (as described above). However, not all nodes of a system need to be active all the time, thus it is possible to have a new node start up and be added to the list of registered node in between the first two phases of the invalidation. In this case, the first phase which secured the objects until the second phase would not be performed at that node, thus re-opening the possibility that shipping a variation may end up missing the invalidation process and ending up on a shipped-to node marked as valid when it should be invalid. This scenario is illustrated by example in the following example, where for simplicity we have assumed that the “drop table” request is issued at node 0, which is the catalog:

[0134] In the example the ‘securing’ aspect of phase 1 of invalidation is missed by the node that has just started up. In order to ensure that the securing can occur on this node without the benefit of the first phase of the invalidation, the node registering process is enhanced whereby when a new node registering is made aware of invalidations that are in progress. This is described in FIG. 9. When a new node starts up, it sends a request to the catalog node to register itself as a ‘participating node’. The catalog node adds this node to its list of participating nodes, and then sends to this new node the list of all the current invalidations in progress entries from the invalidations in progress portion of the cache. The new node receives this list, and sets up on its node's cache and invalidations in progress list. For each of the entries therein, (each of which indicate the object name and type of an object being modified) a new entry in the dependency is created for that object and the object is secured as it would have been if phase 1 of the invalidation were to have been received on that node. Note that this algorithm relies on some of the elements described already for the 2 phase invalidation in FIG. 8, that is, the catalog node adds a new entry to the invalidations in progress list before even executing phase 1; also at the end of phase 2 every node examines the invalidations in progress for a matching entry for the object being modified—if found the entry is deleted.

[0135] In this way the new node when starting up has mimicked phase 1 of the invalidation by securing object entries to ensure new shipped insertions in the statement portion of the cache are aware whether they need to be marked invalid.

[0136] The pseudocode listed below when read in configuration with the description above and the drawings should assist those skilled in the art in appreciating the present invention.

[0137] Part I

[0138] Modules A-C are the pseudo code associated with running an SQL request/query in a multi-node environment

[0139] Accompanying FIGS. 7a-c.

[0140] Module A) Pseudocode for SQL request: coordinator node—part I):

[0141] The following code is run by the DBMS coordinator agent on behalf of an application that issues an SQL request against a database:

[0142] 1) search statement part of dynamic SQL cache for matching statement entry

[0143] 2) if (matching statement entry not found)

[0144] 2.1) Create new statement entry containing the statement text of the SQL request issued by application

[0145] 2.2) Insert new statement entry into statement part of the cache

[0146] 2) end if

[0147] 3) search statement entry for a matching environment entry

[0148] 4) if (matching environment entry not found)

[0149] 4.1) Create new environment entry containing environment in which the SQL request was issued

[0150] 4.2) Insert new environment entry into cache as an environment of the matching statement

[0151] 4) end if

[0152] 5) search environment entry for a variation entry with a valid executable

[0153] 6) if (valid variation entry not found)

[0154] 6.1) Compile SQL request (supplying the statement, environment)

[0155] 6.2) Create new variation entry containing:

[0156] 6.2.1) compiled section (executable)

[0157] 6.2.2) privilege information

[0158] 6.2.3) dependent objects

[0159] 6.2.4) new variation id unique to this (coordinator) node's cache.

[0160] 6.3) Insert new variation entry into cache as a valid variation of the matching environment.

[0161] 6.3.1) For each dependent object in dependency list (step 6.2.3)

[0162] 6.3.1.2) Search in dependency portion of cache for a matching object entry (matching that in 6.3.1)

[0163] 6.3.1.3) If (matching object entry not found)

[0164] 6.3.1.3.1) Create new object entry in the dependency portion of the cache identifying the object (in 6.3.1)

[0165] 6.3.1.3.2) Insert new object entry into cache

[0166] 6.3.1.3) end if

[0167] 6.3.1.4) Create new dependent variation entry identifying the variation (6.2)

[0168] 6.3.1.5) Insert new dependent variation entry into dependency portion of cache as a dependent variation entry of the object entry

[0169] 6.3.1) end for

[0170] 6) end if (at this point the desired variation exists in the cache with a unique id)

[0171] 7) Determine from the section/executable which nodes are the subordinate nodes

[0172] 8) if (variation entry has a entry in the shipped variation list)

[0173] 8.1) original node id=original node id in the shipped variation list entry

[0174] 8.2) original variation id=original variation id in the shipped variation list entry

[0175] 8) else

[0176] 8.3) original node id=current (coordinator) node

[0177] 8.4) original variation id=id of variation at current (coordinator) node (6)

[0178] 8) end if

[0179] 9) Send request to all subordinate nodes to run a section from a variation identified by:

[0180] local node id=current (coordinator) node

[0181] local variation id=id of variation at current (coordinator) node (6)

[0182] original node id (step 8)

[0183] original variation id (step 8)

[0184] 10) Executes from the section in the variation at the coordinator

[0185] 11) Wait for execution from all subordinate nodes to complete, and results received from all nodes.

[0186] 12) Return result to application

[0187] 13) exit

[0188] Note steps 1-10 are in the first column of FIG. 7a), steps 11-13 are in the first column of FIG. 7c)

[0189] Module B) Pseudocode for SQL request coordinator node—part II)

[0190] The following logic is run by the another DBMS agent at the coordinator node as a response to a subordinate node request to ship a variation from the coordinator node over to that subordinate node (Module C, step 3.5.1):

[0191] 1) request is received from subordinate node to ship a variation of a particular id

[0192] 2) statement part of cache is searched for a variation of the requested id (1) (will be found)

[0193] 3) package together into one ‘delivery’, the variation entry with all its subcomponents, the parent environment entry of that variation, and the parent statement entry of the variation and environment

[0194] 4) send the delivery back to requesting subordinate node

[0195] 5) exit.

[0196] All steps of B) are on the first column of FIG. 7b) at coordinator node

[0197] Module C) Pseudocode for SQL request at subordinate node

[0198] The following logic is run a DBMS agent on the subordinate node in response to a request of step 9) in module A to execute a specific variation's section:

[0199] 1) request received from coordinator node to all subordinate nodes to run a section from a variation identified by:

[0200] local node id—this is coordinator node id

[0201] local variation id—this is the variation entry id at the coordinator

[0202] original node id

[0203] original variation id

[0204] 2) Search shipped variation portion of dynamic cache for entry matching the original node id, original variation id

[0205] 3) if (matching shipped variation entry found)

[0206] 3.1) The variation entry in the statement part of the cache that is associated the shipped entry is the desired variation whose section is to be run.

[0207] 3) else

[0208] 3.2) create new shipped variation entry with original node id and original variation id as supplied (1)

[0209] 3.3) insert new shipped variation entry in the shipped variation portion of cache (currently not associated with any variation in local (subordinate) cache

[0210] 3.4) if the original node id (step 1) same as the current (subordinate) node's id

[0211] 3.4.1) Search for the original node variation id in the current (subordinate node's cache)

[0212] 3.4.2) if variation entry is found in the cache with a matching id as the original node variation id

[0213] 3.4.3) Associate the new shipped variation entry (3.2) with the matching variation

[0214] (3.4.2). This is the desired section to be run.

[0215] 3.4) end if

[0216] 3.5) If the new shipped variation is still not associated with any local variation entry

[0217] 3.5.1) Send request to coordinator node (as identified as local node id in step 1) to ship local variation id (1). (This request is handled at the coordinator node by Module B)

[0218] 3.5.2) Receive variation information, as well as matching statement and environment entry from coordinator node

[0219] 3.5.3) Create and insert new variation entry (and if necessary statement, environment entries) in statement portion of local cache

[0220] The steps for inserting the new variation are similar to steps 2-6 in Module A with the following exceptions:

[0221] 3.5.3.1) If a matching statement/environment entry already exists and a valid variation for that statement/environment is already present in the cache (Module A, step 6), that variation is marked as invalid; a new variation entry is always inserted

[0222] 3.5.3.2) The variation is not compiled at the local node (as in Module A step 6.1), rather the variation info obtained from the shipment from the coordinator node is used to fill in the new var; this includes info in Module A, 6.2.1, 6.2.2, 6.2.3. (the section, the privileges information and the dependency information). The variation id, however is a new variation id for this variation, chosen to be unique at the subordinate node.

[0223] 3.5.3.3) When inserting entries in the dependency portion of the subordinate node's cache (Module A, steps 6.3.1) an additional check is performed (which would take place after 6.3.1.5 in the Module A)

[0224] 3.5.3.3.1) If object entry is marked as secured, then mark the new variation entry as invalid

[0225] 3.5.4) Associate created shipped variation entry (3.2) with newly created variation (3.5.3).

[0226] This is the variation with the required section/executable.

[0227] 3) end if

[0228] 4) run from section from the indicated variation

[0229] 5) send results back to coordinator node (received in Module A) step 11)

[0230] 6) exit

[0231] Note all of Module C is in the second column of FIGS. 7band 7c.

[0232] Part 2

[0233] Modules D)-I) are associated with Invalidation logic in a multi-node system

[0234] Module D) Pseudocode for Invalidation—Coordinator node

[0235] 1) Request received from an application to change the definition of an SQL object or to drop the object itself.

[0236] 2) If the coordinator node is the catalog node

[0237] 2.1) Execute Module E)

[0238] 2) else

[0239] 2.2) Request is send to the catalog node to execute the request

[0240] 2.3) Waits for reply from catalog node

[0241] 2) end if

[0242] 3) Returns result of execution at the catalog node to the application

[0243] 4) exit;

[0244] The following code is run by the DBMS coordinator agent on behalf of an application that issues a request to change the definition (or drop the existence) of an SQL object:

[0245] Note all of Module D is in the first column of FIG. 8a

[0246] Module E) Pseudocode for Invalidation—Catalog node

[0247] The following logic is run a DBMS agent on the catalog node in response to a request from the coordinator node to change the definition of an SQL object:

[0248] 1) Request received from the coordinator to drop or modify the definition of an SQL object

[0249] 2) Add an entry to the invalidations in progress list identifying the object name and object type

[0250] 3) execute Phase 1 of the invalidation (Module F) at this (catalog) node, specifying the object name and object type in question (1)

[0251] 4) Broadcast request to all other known nodes to execute Phase 1 (Module F) of the invalidation

[0252] 5) Wait for response from all other known nodes

[0253] 6) If (confirmation received from all nodes that phase 1 is successful)

[0254] 6.1) Execute phase 2 of the invalidation (Module G) at this (catalog) node, specifying the object name and object type in question (1)

[0255] 6.2) Broadcast request to all other known nodes to execute Phase 2 (Module G) of the invalidation. (Note all the known nodes may not be the same list of known nodes as in the Phase 1 broadcast in 4)).

[0256] 6.2) Wait for response from all other known nodes

[0257] 6) end if

[0258] 7) If phase 1 and phase 2 are successful

[0259] 7.1) drop the object or modify the object in the catalogs as requested

[0260] 8) Return success/fail information to coordinating node

[0261] Note all of Module E is in the second column of FIG. 8a

[0262] Module F) Pseudocode for Invalidation—Phase 1 at all nodes

[0263] 1) Request received from catalog node to execute phase 1 of invalidation for an object, identified by its name, and object type

[0264] 2) Search dependency portion of cache for an object entry that matches the name, type identified in 1)

[0265] 3) If object entry does not exists in the dependency portion of the cache

[0266] 3.1) Create an object entry with the name, type identification from 1)

[0267] 3) end if

[0268] 3) Denote in the object entry that the entry has been secured.

[0269] 4) Send success/fail information back to catalog node

[0270] 5) exit;

[0271] Note all of Module F is in FIG. 8b

[0272] Module G) Pseudocode for Invalidation—Phase 2 at all nodes

[0273] 1) Request received from catalog node to execute phase 2 of invalidation for an object, identified by its name, and object type

[0274] 2) Search object entry in dependency portion of cache that matches the name, type identified in 1)

[0275] 3) If object entry exists in the dependency portion of the cache

[0276] 3.1) For all dependent variation entry listed for the object entry in the dependency portion of the cache

[0277] 3.1.1) find the variation entry in the statement portion of the cache (variation is indicated in the dependent variation entry).

[0278] 3.1.2) Wait until no other DBMS agents operating on this node is using the variation

[0279] 3.1.3) Mark the variation entry as invalid

[0280] 3.1) end for

[0281] 3.2) Denote in the object entry that the entry is no longer secured

[0282] 3.3) Search the invalidations in progress portion of the cache for an entry matching the object name, object type indicated in 1)

[0283] 3.4) If matching entry is found

[0284] 3.5) Delete the invalidations in progress entry

[0285] 3.4) end if

[0286] 3) end if

[0287] 4) exit

[0288] Note all of Module G is in FIG. 8b

[0289] Module H) Pseudocode for node start up logic—New node

[0290] The following code is run by an agent of the DBMS at the new node starting up before it acts on any other requests. Any request is received at the new node that until the point is currently inactive; in order to allow the node to activate the following is performed:

[0291] 1) A request is sent to the catalog node to register this new node. (Module I at the catalog node)

[0292] 2) The reply from the catalog node is received together with a list of invalidations in progress

[0293] 3) All entries of invalidations in progress received are created identically at the new node

[0294] 4) For all entries in the invalidations in progress list

[0295] 4.1) add a new object entry in the dependency portion of the cache with the object name, type matching that indicated in the invalidations in progress entry

[0296] 4.2) Denote in the object entry that the entry has been secured.

[0297] 4) end for

[0298] 5) exit

[0299] Note all of Module H is in the second column of FIG. 9.