Ordering keys in a table using an ordering mask

Details Ordering keys in a table using an ordering mask Ordering keys in a table using an ordering mask

1999-12-09

2002-05-28

Lintz, Paul R. (Department: 2771)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000, C709S241000, C709S241000, C709S221000, C717S152000, C717S152000

Reexamination Certificate

active

06397216

ABSTRACT:

BACKGROUND OF THE INVENTION
The present invention relates to a mask ordering method which controls the way primary keys are compared and relates to a coupling facility (CF) and the accessing of objects within a coupling facility.
A coupling facility (CF) provides a structured means of connecting multiple central processing complexes (CPCs) to allow efficient interchange of data between multiple physical systems while maintaining coherency of the data across all systems. The coupling facility consists of high-speed intersystem (IS) channels, central processing units (CPUs), random-access memory (AND storage that is accessed by the IS channels and CPUs, and control software running in the CPUs.
A coupling facility structure represents a set of objects maintained on behalf of attaching systems. A structure is similar to a shared file in a direct-access storage device (DASD) except that structures are maintained in the coupling facility's storage. The coupling facility receives commands from attaching CPCs via the IS channels, executes the commands, and returns responses over the IS channels. The commands create, write, read, update, or delete structures on behalf of the attaching CPCs.
In a structure, entries comprise one class of objects that are maintained in storage. Entries may contain name, index, and other values that must be examined and/or updated by the CPU to successfully complete a CF command. The term name in the present specification means the same thing as the term key. The term key is frequently used generically to mean any value for locating an entry in an ordered table. The term name sometimes refers to a key formed of alpha characters, alphanumeric characters or to other limiting characteristics. In coupling facility products and the preset specification, name has no limiting characteristics and is used most generally and interchangeably with key unless the context indicates otherwise.
Coupling facility products from Amdahl Corporation of Sunnyvale, Cailf. and IBM Corporation of Armonk, N.Y., and others have been implemented using S/390-based platforms but coupling facilities can be implemented on any hardware platform. In machines from Amdahl, Amdahl Coupling Control Code (ACCC) is the code that implements the coupling facility functions. In machines from IBM, Coupling Facility Control Code (CFCC) is the code that implements the coupling facility functions.
The S/390 architecture is well-known to represent the foundation for robust, high-performance, high-reliability computing platforms. In IBM-derived publications, such as U.S. Pat. No. 5,537,574 entitled SYSPLEX SHARED DATA COHERENCY METHOD and U.S. Pat. No. 5,317,739 entitled METHOD AND APPARATUS FOR COUPLING DATA PROCESSING SYSTEMS, the coupling facility is referred to as shared cache or shared electronic storage (SES).
A cache structure represents an intermediate level of a three-tiered data hierarchy where the highest level is the local cache copies of data objects within a CPC and the lowest level is copies of data on shared DASD. Application programs that participate in such a data hierarchy can write and read cache entries in a CF cache structure. Each cache entry is identified by a name. The entries are organized in a logical construct referred to as the directory. A command issued to the CF may request processing of one specific entry or a group of related entries.
In cache structures, several cache commands process cache entries having a name that matches the input name under an input name mask. One such a command is the invalidate-name command. (The invalidate-name command is referred to as the IXLCACHE REQUEST=DELETE_NAME request in the OS/390 MVS Programming: Sysplex Services Guide (GC28-1771) from IBM [hereafter Sysplex Services Guide]). In the Sysplex Services Guide, the input name mask is 16 bits and the input name is 16 bytes. The 16 bits correspond one for one with the 16 bytes of the name. The name comparison is successful when all the name bytes having a corresponding name mask bit of one, are equal. A mask of all zeros causes all names to be processed. A mask of all ones identifies a single name to be processed. Processing, in the case of the invalidate-name command, for example, can range from updating the cache entry to deleting the entry, depending on the values of the other input parameters.
An example that illustrates the naming and masking concepts is given where, for purposes of the example, keys are 4-character names consisting of only the alphabet letters A and B. Assume a cache structure has the following set of name entries:
AABA, ABAA, ABAB, BAAA, BABA, BBAB.
For the above set of name entries, an invalidate-name command specifying an input name AAAA and an input mask of b‘0100’ invalidates the following entries:
AABA, BAAA and BABA.
For good performance, the utilization of the cache structure requires that an entry corresponding to a specified name be quickly located. Different methods for quickly locating names have been used and proposed. For IBM systems, directories in the form of hash tables have been employed and for Amdahl systems, directories in the form of binary trees have been employed.
For operations of coupling facilities in systems prior to IBM CFLEVEL=7, when the name mask is not all ones, all entries in the cache structure directory have to be scanned to find all the names matching the specified name mask. In cases where the set of entries which match the specified name mask is small compared to the total number of entries in the structure, this scanning process is inefficient and time-consuming.
Some applications on CPCs use invalidate-name with a name mask to perform selective deletion of entries from the cache when, for example, a particular data set is closed, shut down, or ceases to have a shared interest that requires its data to reside in the cache. In these cases, a known naming convention defines the name mask which is used to select the entries to be deleted. In such cases, the full directory scan performed by the invalidate-namne operation adversely impacts the performance of the applications which are using it to perform cleanup.
For operations using IBM CF-Level 7 Improvements (CFLEVEL=7 and higher), a cache structure supports ‘name classes’ for names adhering to a naming convention defined when the structure is created (via the name class mask). Specifically, names that are identical in byte positions corresponding to bits which are on in the name class mask belong to the same name class. In the IBM implementation, name class queues are used to group together all entries that are processed as a group given the defined naming convention. Later, when an invalidate-name command is requested using a name mask equal to the name class mask for the structure, all of the entries to be deleted can be located efficiently by running through the name class queue, avoiding the overhead of scanning through all of the entries in the structure. The efficiency of application processes that invoke invalidate-name for cleanup purposes is therefore improved. Examples of name classes can be found in the section “Using Name Classes in a Coupling Facility” in the Sysplex Services Guide.
Again, consider the following set of name entries:
AABA, ABAA, ABAB, BAAA, BABA, BBAB.
For that set of name entries and with a name class mask of ‘0110’ specified at structure creation time, the following name classes and members are created where underscores indicate name bytes that identify the name class:
Name class AA: B
AA
A
Name class AB: A
AB
A, B
AB
A
Name class BA: A
BA
A, A
BA
B, B
BA
B
Name class BB: (empty)
In the IBM CFLEVEL=7 implementation, two programming constructs are used for performance enhancement, one for quickly locating a single cache entry by name and another one for locating entries in a specified name class. For locating a single entry by name, a hash table construct is used as described in the section “Hash Accessing of SES Directory Entries” in U.S. Pat. No. 5,537,574. For locating entries in a name class, name class

Affiliated with

Also associated with

Rating

Ordering keys in a table using an ordering mask does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Ordering keys in a table using an ordering mask, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Ordering keys in a table using an ordering mask will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2900177