Database engine

Abstract

A processor functioning as a coprocessor attached to a central processing complex provides efficient execution of the functions required for database processing: sorting, merging, joining, searching and manipulating fields in a host memory system. The specialized functional units: a memory interface and field extractor/assembler, a Predicate Evaluator, a combined sort/merge/join unit, a hasher, and a microcoded control processor, are all centered around a partitioned Working Store. Each functional unit is pipelined and optimized according to the function it performs, and executes its portion of the query efficiently. All functional units execute simultaneously under the control processor to achieve the desired results. Many different database functions can be performed by chaining simple operations together. The processor can effectively replace the CPU bound portions of complex database operations with functions that run at the maximum memory access rate improving performance on complex queries.

Claims

Having thus described our invention, what we claim as new and desire to secure by Letters Patent is:

1. An attached coprocessor for processing database records stored in a system memory of a host system, responsive to database processing commands stored in the system memory and generated by a database processing program, said coprocessor comprising:

first bus means for carrying control information;

second bus means for carrying data;

extractor means for extracting fields from the records and for reordering said fields based on said commands, the extractor means being in communication with the system memory, the first bus means and the second bus means;

controls means communicating with said host system, for providing control information on the first bus means responsive to the commands, the control means being in communication with the first bus means and the second bus means;

search means for processing search queries responsive to the control means, the search means being in communication with the first bus means and the second bus means;

sort means for performing sort and merge operations on the database records responsive to the control means, the sort means being in communication with the first bus means and the second bus means;

hash generator means for generating a hash code from keys provided in the database processing commands the hash generator means being responsive to the control means and in communication with the first bus means and the second bus means; and

memory means for temporarily storing internal data, the memory means being in communication with the second bus means whereby said search means, said sort means, and said hash generator means utilize said memory means in common.

2. The attached coprocessor of claim 1 wherein the sort means comprises codeword tree means for performing tournament tree codeword sorting of the database records.

3. The attached coprocessor of claim 1 wherein the system memory comprises a paging memory coupled to the host system and wherein the extractor means comprises means for directly accessing the paging memory.

4. The attached coprocessor of claim 3 wherein the paging memory is multiported and wherein the extractor means comprises a data and address bus connected to a port of the paging memory.

5. The attached coprocessor of claim 1 wherein the sort means comprises means for performing a front-back merge of the database records.

6. An attached coprocessor for performing a plurality of database functions on database records stored in a system memory of a host computer, said coprocessor comprising:

control bus means;

data bus means;

control processor means communicating with said host computer, for parsing a database command received from said system memory, said parsed database command including a selected set of said plurality of database functions, said control processor means controlling said control bus means in accordance with said selected set of said plurality of database functions, said control processor means being in communication with said control bus means and said data bus means;

processing means for selecting database fields from the database records and for manipulating said database fields in accordance with said selected set of said plurality of database functions, said control bus means and said data bus means connecting said processing means with said system memory; said processing means including

a plurality of processing elements for performing said plurality of database functions, said processing elements being invoked in accordance with said selected set of said plurality of database functions, said plurality of processing elements including,

search means for selecting desired ones of said database fields, said search means being responsive to said control processor means and said search means being in communication with said control bus means and said data bus means;

sort means for performing sort and merge operations on said database records, said sort means being responsive to said control processor means and said sort means being in communication with said control bus means and said data bus means;

hash code generator means for generating a hash code based on a key field in said database record, said hash code being used by said plurality of processing elements, said hash code generator means being responsive to said control processor means and said hash code generator means being in communication with said control bus means and said data bus means; and

memory means for temporarily storing internal data, the memory means being in communication with said data bus means whereby each of said plurality of processing elements utilize said memory means in common.

7. An attached coprocessor, as recited in claim 6, wherein said sort means comprises codeword tree means for performing tournament tree codeword sorting of said database records.

8. An attached coprocessor, as recited in claim 6, wherein said system memory comprises a paging memory coupled to said host computer and wherein said control processor means comprises means for directly accessing said paging memory.

9. An attached coprocessor, as recited in claim 8, wherein said paging memory is multiport and wherein said control processor means comprises a data and address bus connected to a port of said paging memory.

10. An attached coprocessor, as recited in claim 6, wherein said sort means comprises means for performing a front-back merge of said database records.

Description

BACKGROUND OF THE INVENTION

1. Field of the Invention

This invention relates to database processing.

2. Related Art

Database processing is a widely known and commercially significant aspect of the data processing field. A database is a collection of data organized into records. Computer operations which are performed on and/or using these data records are referred to as database processing. A database manager is the package of database processing operations used to access and manipulate the database.

Database processing commonly involves operations such as sorting, merging, searching and joining. Set operations such as union, intersection and difference are also common aspects of database processing. Conventionally, these operations have been performed by software algorithms requiring significant amounts of processor execution time. In large databases, the processor execution time can be prohibitive, significantly degrading the performance of software database managers.

One aspect of database processing involves searching for records that meet a certain criteria. For example, a search might scan all records in the database and return every record that has column "X" equal to some value. In a more complex case, the search might scan and retrieve records based on a predicate equation involving many columns and values. Since the databases can be very large, (e.g. hundreds of millions of records), the searching algorithms used in conventional software database management systems can take hours to process.

Another aspect of database processing involves the extraction of sort keys and search fields from the database records. In sorting and searching applications, the sort key or field on which a search is defined are often spread throughout the records and must be extracted into a useable format before the operation can proceed. For sorting this means getting each key field and concatenating them in precedence order so that they can be treated as one large key. For searching, the columns of a table that are being searched or selected must be extracted from the rows. Conventionally, these and many other database operations can use significant amounts of CPU time.

There have been a number of attempts to provide solutions which "off-load" the CPU of some of the database processing tasks. One such solution was to provide a computer system with a specialized sort processor to handle sorting tasks which would otherwise be executed by the CPU. FIG. 1 is an illustration of a such a prior art sort processor.

The sort processor 100 of FIG. 1 shares a main memory bus 102 with a central processing unit 104. A main memory 106 communicates with the central processing unit 104 through a first set of communications lines 108 and with the sort processor 100 through a second set of communications lines 110. The central processing unit 104 and the sort processor 100 are interconnected by a start control line 112 and and interrupt line 114.

During database processing, random records stored in a peripheral file 116 are transferred to the main memory 106. A control program then initiates the action of the sort processor 100. Under firmware control, the key words are transferred from the main memory 106 to the sort processor 100 and then sorted. The autonomous action of the sort processor 100 results in savings of Central Processing Unit time and simplification and reduction of programming efforts.

While the sort processor 100 of FIG. 1 provided an advance over contemporaneous software database processors, the solution was only partial. Sorting is but one aspect of database processing. Other operations such as searching, joining of tables and set operations also take up significant amounts of CPU time. Further, although the sort processor of FIG. 1 operated relatively autonomously from the remainder of the system, its internal sorting algorithm was implemented in microcode. Thus the sort processor of FIG. 1 was limited by many of the same constraints as sort programs which would otherwise be executed by the CPU.

The sort processor 100 of FIG. 1 is also subject to performance limitations in that it shares the main memory 106 with the central processor 104 on a low priority basis and along a single memory bus 102. The competition for main memory access time along the single bus path (albeit reduced relative to systems having no sort processor) can cause a bottleneck for data traffic between the main memory 106 and the sort processor 100.

Another approach to database processing off-loads some of the database processing tasks traditionally handled by the CPU to a vector processing element. FIG. 2 is an illustration of one such prior art relational data base managing system utilizing a vector processor. A central processor 200 includes a scalar processor 202 and a vector processor 204. Both the vector and scalar processors have access to a main memory 206 and a subsidiary storage 208.

In operation, a database command issued from an application program 210 is examined by a relational database managing program 212. The database managing program 212 identifies the command, analyzes it, and then generates codes which which designate a determined process sequence. During database processing, required data is loaded into a data buffer area 214 in the main memory 206 from a page area in in the subsidiary storage 208. Under control of the process sequence codes, the data in the buffer area 214 is rearranged in the form of a vector structure. The resultant vector data elements are stored in a vector area 216.

When the process sequence codes indicate the processing of the vector data, a sequence of vector instructions are executed by the vector processor 204. Under control of the vector instructions, the vector processor 204 processes the data in the vector area 216 in accordance with the designated processes sequence.

One constraint of the database managing system of FIG. 2 is that as a consequence of its reliance on vector processing, the database must be generated in or converted to a vector format prior to being processed. This conversion process can, in itself, take a significant amount of time and can slow the data base processing operation.

A second constraint of the database managing system of FIG. 2 is that the associated vector processing hardware is programmed at the instruction level (i.e. it is left to the programmer to write the instruction primitives required to perform the database processing functions). These instructions are executed by the vector processing hardware synchronously within the database management program. Thus, the database manager program is dedicated to a single task while the instructions are being executed. Further, as each primitive instruction is executed it requires CPU time. The CPU is, therefore, not completely free of database processing duties until the entire series of primitives is executed.

Yet a third constraint of the database managing system of FIG. 2 is that the vector processing approach adds levels of indirection to the database processing operation. In vector formatted databases, a series of pointers are used to locate the actual data of interest. A location in one table will often point to another location in another table and so on. This indirection can increase processing time of database operations.

SUMMARY OF THE INVENTION

It is an object of the invention to exploit functional level parallelism to enhance the overall processing speed of database operations beyond that achieved by prior art database processors.

It is a further object of the invention to process database operations at or near system memory bandwidth speeds.

It is a further object of this invention to process, in an attached coprocessor environment, a command list generated by a conventional software database processing program.

In accordance with these objectives, the inventors have provided a Database Engine (DBE), which provides fast processing for basic database functions. In the preferred embodiment, the Database Engine includes an extractor/memory interface unit which provides access to a system memory and extracts the data to be processed therefrom, a local working memory which temporarily stores the data to be processed, a plurality of autonomous processing elements which each perform a specialized database processing function, and a control processor which parses database commands from a database manager into subfunctions and distributes the subfunctions among the processing elements.

By providing hardware to assist and accelerate the processing of basic database functions, the Database Engine can significantly reduce the execution time of many database operations.

Advantageously, the Database Engine overcomes many of the constraints of prior art database coprocessors. In contrast to the system of FIG. 2, the Database Engine does not require vector formatted records. Thus, the database engine eliminates much of the processing overhead present in the FIG. 2 system. Further, unlike the vector processor of FIG. 2, the Database Engine can be controlled with macro commands rather than requiring central processor instruction level programming.

Unlike the system of FIG. 1, the Database Engine does not need to compete with the CPU for main memory access time by way of a common data bus. In one embodiment, the database engine is coupled to the systems page storage. The page storage acts as a directly addressable main memory for the database engine but appears only as a paging memory to the systems central processors. This enables large databases to be fixed in the paging memory and minimizes competition with the central processors for main memory accesses.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is diagram of a prior art sort processor system.

FIG. 2 is a diagram of a prior art database managing system.

FIG. 3 is a block diagram overview of the Database Engine according to a preferred embodiment of the present invention.

FIG. 4 is a block diagram illustration of the logical connection of the Database Engine of FIG. 3 into a computer system having a paging memory and a main memory.

FIGS. 5A and 5B are, respectively, top and bottom halves of a diagram illustrating an embodiment of the Control Processor of FIG. 3.

FIGS. 6A and 6B are, respectively, top and bottom halves of a diagram illustrating an embodiment of the Predicate Evaluator (DBPE) of FIG. 1.

FIG. 7 is a diagram illustrating an embodiment of the Sort/Merge Unit of FIG. 3. The interaction between the Sort/Merge Unit and the Working Store of FIG. 3 is also illustrated.

FIG. 8 is an example of a block sort.

FIG. 9 is an illustration of the state of the Working Store and pointer arrays during a block sort using the sort/merge unit of FIG. 7.

FIGS. 10A and 10B are, respectively, top and bottom halves of a flow chart of the binary sort/merge algorithm used by the Sort/Merge Unit (DBSM) of FIG. 3.

FIG. 11 is an illustration of the hardware additions to the Sort/Merge Unit of FIG. 7 which implement Tournament Tree Codeword Techniques.

FIG. 12 is an illustration of a conventional tournament tree.

FIGS. 13A-13C illustrate progressive states of a tournament tree implemented in the Working Store and pointer arrays of FIG. 7.

FIGS. 14A, 14B are flow charts of a sort algorithm using codeword techniques implemented using the additional hardware of FIG. 11.

FIG. 15 is a more detailed diagram illustrating the structure of the Hash-code Generator (DBHG) of FIG. 3.

FIG. 16 is a block diagram of the Extractor/Memory Interface Unit (DBEM) of FIG. 3.

FIGS. 17A, 17B are, respectively, top and bottom halves of a more detailed diagram illustrating the structure of the Extractor/Memory Interface Unit (DBEM) of FIGS. 3 and 16.

FIGS. 18A, 18B and 18C are a flowchart of the operation of the DBEM of FIGS. 17A, 17B.

FIG. 19 is a block diagram of a DBSM modified to perform a front-back merge.

FIG. 20 is a block diagram of a 16-way merge tree with a 4-way comparator.

FIG. 21 is a diagram of a 4-way merge sort comparator which produces an ordered list of pointers to four input keys.

FIG. 22 is a diagram of a four pipe, 4-way comparator sort engine.

Like elements which appear in more than one figure have been assigned like reference numerals.

IV. DESCRIPTION OF THE PREFERRED EMBODIMENTS

a. Database Engine

The Database Engine (DBE) is a special purpose processor designed to quickly evaluate relational databases and provide fast sorting of data. The Database Engine performs the core functions required for database processing including sorting, merging, joining, searching, and manipulating fields. The Database Engine provides performance improvements over many of the best known software approaches to the same problems by taking advantage of the overlap between processing and memory access time that can be obtained in a specialized hardware implementation.

The overall structure of the Database Engine is illustrated in FIG. 3. The Database Engine 300 comprises five hardware processing elements (designated by reference numerals 302-310) and a Working Store 312. Two internal multibit data busses 316,318 provide data flow between the Working Store 312 and the processing elements 302-310. An internal multibit control bus 320 provides a control data path between the processing elements. Externally, a system memory bus 322 is provided between an extractor/memory interface unit 308 and the system memory (not shown in FIG. 3).

The processing elements 302-310 and the Working Store 312 work in concert to process database queries. The Sort/Merge unit 302 performs sorts, merges, joins, and set operations. Searching is performed by the Predicate Evaluator 304. A hardware Hash-Code Generator 306 is provided to improve the performance of EQUIJOINs on two databases. Record field extraction and memory access functions are performed by the Extractor/Memory Interface Unit 308. Operations performed by the foregoing processing elements are initiated under the control of the Control Processor 310.

The Database Engine 300 works in conjunction with database application software running on a host system. An example of such software is DB2 (an IBM database application program that runs under MVS.) The application software does all of the I/O required to read the database into system memory. The application software also creates the Database Engine commands, the database object descriptors, and the predicate; then puts them into the system memory where they can be accessed by the Database Engine 300.

FIG. 4 illustrates the system attachment of the Database Engine 300 in a exemplary system environment. In the system of FIG. 4, the Database Engine 300 is shown configured in a multiprocessor system having three central processors (CPs) 402-406, I/O channels 408, and a system memory comprising a main storage 410 and a page storage 412. The page storage acts as a paging memory to the central processors 402-406. Pages of data are transferred from the page storage to the main storage, under control of the central processors 402-406, by way of a memory data bus 414. The central processors then access the data in main storage by way of a switch or system controller 416. An example of such a system is described in U.S. Pat. Nos. 4,476,524 to Brown and 4,394,731 to Flusche et al., which are both incorporated by reference in their entireties, as if printed in full below.

The switch 416 is of the self routing, non-blocking crossbar type. Specifically, the switch 416 provides simultaneous multibit data paths between the main storage 410 and any one of the system elements (300, 402-408), and between the page storage 412 and any other one of the system elements. For example, the switch 416 can provide a first data path between the page storage 412 and the Database Engine 300 while at the same time providing a second data path between one of the central processors 402-406 and the main storage 410.

Alternatively, the system memory (main and page storages 410, 412) can be multi-ported and data transfer between the Database Engine 300 and the system memory (410, 412) can be provided by directly connected high bandwidth buses 420, 422. Further, the central processors can be provided with access the main storage through a port or ports by way of a CP data busses such as the one shown by reference numeral 424. A similar connection could be provided for the between the system memory and the I/O channels 408. In such an embodiment the switch 416 can be eliminated.

The configuration of FIG. 4 enables the Database Engine 300 to access system memory (410, 412) directly, without having to go through the central processor to generate requests. Thus, the Database Engine can access the page storage 412 as a main memory. As described above, in the system of FIG. 4 the page storage acts 412 as a paging memory to the CPs 402-406. This attachment system/method enables the Database Engine to run as a logically asynchronous processor in the system with minimal effect on the CPs.

Having direct access to both the main and page storages 410, 412 provides a number of ways for the database engine to access commands and data records. For example, the database can be accessed from the main storage and portions can be paged in as needed. Alternatively, the database can be fixed in the page storage 412 and accessed directly, thus avoiding the I/O costs entailed with saving and restoring the database to a direct access storage device (DASD). In any event, performance requirements, memory size, and the type of memory available in a particular system are factors which should be taken into account in determining where the database should reside in the system memory.

With respect to the system environment of FIG. 4, data that is needed by the Database Engine 300 is fixed in the system memory (either the main storage 410 or the page storage 412) by the operating system prior to issuing the start signal. A list of page or record addresses is then given to the Database Engine to tell it where in the system memory (410, 412) the data resides and in what order to access each fixed block.

A Database Engine operation is initiated via a command sequence that is constructed by the database application program. The command sequence is placed in the system memory through the operating system prior to invoking the operation of the Database Engine. Once the Database Engine 300 has been started, it runs asynchronously, accessing the commands, descriptors, and data (out of system memory) as it needs to without any interruption of the central processors 402-406. When the operation is complete, an interrupt is issued back to the calling program.

The operation of the Database Engine 300 will now be explained in more detail by example of the processing of a search with sort command. Reference will be made to FIGS. 3 and 4. Through the receipt of a start signal, the Control Processor 310 is signaled that a database command, encountered by the host CPU, exists in the system memory. The start signalling is done through the memory interface portion of the Extractor/Memory Interface Unit 308 and includes the address of a database command block (described in detail elsewhere) in the system memory. On receiving the Start DBE signal, the Control Processor 310 fetches the database command block from the system memory and stores it internally.

Next, the Control Processor 310 parses the database command information into setup and processing information for each of the other processing elements 304-308. The database descriptor and field information is used to initialize the extractor/assembler function of the Extractor/Memory Interface Unit 308, the selection predicate is loaded into instruction and constant tables within Predicate Evaluator 304, and the sort key is used to set up the Sort/Merge unit 302. Once each processing element is loaded with its required information (function and initialization data), the execution phase begins.

The database command is executed by processing blocks of data through each processing element in a pipelined fashion until the entire database has been processed. In the case of a search with a sort, the data is first processed by the extractor portion of the Extractor/Memory Interface Unit 308 to put the needed data into the Working store 312. Next, the Predicate Evaluator 304 processes the records in Working Store 312 to select ones which meet the selection predicate. The Sort/Merge unit 302 then sorts the selected records into order based on the key.

The sorting and predicate evaluation operations are performed in blocks of the size of the Working Store 312 and are repeated until the entire database has been processed. The sort portion of the command, for example, may take several merge passes to be able to merge a large database. In such a case, an assembler function of the Extractor/Memory Interface Unit 308 is used to write intermediate results to a temporary memory area in the system memory. On the final merge pass, the output records are assembled into their correct format and written to an output memory area (designated by the command), by the assembler function of the Extractor/Memory Interface Unit 308.

Once the last record is assembled and placed into the system memory, the Control Processor 310 collects any operational or error status and places it in a status area in the system memory. The Control Processor 310 then signals the initiating host CPU that the operation is complete. The Database Engine 300 is then ready to process another command.

Advantageously, the Database Engine's System memory accesses can be overlapped with database processing time. Database records can be assembled by the Database Engine 300 and returned to system memory while still other records are in the midst of being processed. Further, once started by the Control Processor 310, each of the other processing elements 304-308 can operate in parallel, as long as the function can be partitioned to allow simultaneous access to the Working Store partitions. Thus the Database Engine can execute database queries at very close to the system memory access rate.

Although the above example describes a search with sort execution, it should be understood that the Database Engine can perform many different operations, including search, sort, merge, join, etc., which all execute in the same data-block pipelined fashion.

The Database Engine command set includes the core relational database functions that are used to process database queries. These functions are the basic components of the queries, and can be chained together to produce a complex database query. The core functions implemented by the Database Engine are:

1. Sorting. A database is sorted based on a given column or combination of columns and returned in sorted order. The sort key can be any length (up to 32K bytes long in the preferred embodiment).

2. Searching. The database is evaluated and the results are restricted to rows that match a given predicate, e.g., find all records where column 1='xyz' is a search operation. A subset of the full database is returned in which all records have column 1 equal to 'xyz'. The "column 1='xyz'" is called the predicate and can be simple (as in this case) or complex. The Database Engine allows the following comparison operators to be used: "equal", "greater than or equal", "less than or equal", "not equal", "less than" and "greater than". Complex predicates are composed of simple predicates connected with AND, OR, and NOT and other Boolean operators.

3. Selection. A subset of the columns in the database can be chosen from the database and returned by the selection operation. The selection operation returns a vertical subset of the database columns.

4. Set Operations. The set operators include union, intersection, difference, and cross product. These are performed as defined for general set theory.

5. Join Operations. Join operations are performed according to the type of join. The join operator can be "equal", "greater than or equal", "less than or equal", "not equal", "less than" and "greater than" or combinations of the above connected by the Boolean operators AND, OR, and NOT. Note that outer joins can be performed as well, although they create large resultant databases.

b. Command Format

The command block is a data structure that provides both command and address information to the Database Engine. The command block is constructed by the database application software and passed to the Database Engine 300, during initialization, by Way of the system memory. The Database Engine 300 is informed that the command block is present in the system memory through receipt of the Start DBE command. The command block contains the following information.

1. The type of command that is to be executed: sort, merge, join, selection, search, union, intersection, difference, cross product, or division.

2. The address of the database descriptor(s) in memory. There can be up to three database descriptors used, two inputs and an output. The output area is also used as the temporary work area during processing.

3. The address of the predicate to be used during command processing.

4. The fields from the databases that are to be used for the command and the output fields to be given.

5. If an index is available, it can also be specified in the command block.

The database descriptor is used by various commands to identify a particular database. For example, the MERGE command can have any number of databases (up to 128 in the preferred embodiment) as inputs and one database as an outpot. Each of the remaining commands preferably processes one or two databases as inputs and have a third as an output. Each of these databases are identified to the Database Engine by a database descriptor. Each descriptor contains the following information:

A. Starting address of the database.

B. The format of the database, either DB2 or compact.

The Database Engine can process the DB2 pageset format for any of the nonindex commands, however, improved performance will result if the Database Engine uses a compact sequential format instead. All workspace and temporary databases used by the Database Engine are stored with records placed sequentially in memory. The final result can be stored in either format.

C. The number of records in the database.

D. The format of the database, i.e., the number of fields, the type of data contained in the fields, and the maximum length.

As discussed above, the address of the predicate to be used during command processing is passed to the Database Engine as part of the command block. The predicate is the Boolean equation which restricts the output records to a subset of the original database. It can be just one term or many and will preferably be expressed in a Reverse-Polish notation to allow the Database Engine to process it more quickly. The Reverse-Polish notation removes any parentheses that exist in the original SQL query, allowing the query to be processed sequentially using a stack processor. For example, the following is a query in SQL:

Select POSITION,MANAGER from EMPLOYEES

where AGE<'25'

and LOCATION='TRENTON'

and VACATION<'10'

and GRADE<'85';

The where clause is the predicate and can be converted to the following Reverse-Polish form:

AGE,'25',<,

LOCATION, 'TRENTON',=&

VACATION,'10',<&,

GRADE,'85',<&

It is the responsibility of the calling procedure to convert the SQL query to this format before initiating the Database Engine operation. It is also the responsibility of the calling program to replace the English language names with the database and field number associated with each before giving the predicate to the Database Engine.

The Database Engine can evaluate predicates on either character or integer fields. Allowable arithmetic operations are equal, less than, greater than, less than or equal, greater than or equal, and not equal. These comparisons can be combined into more complex queries by using the Boolean operators OR, AND, and NOT. Any combination or integer or character comparisons can be made with the above operators.

c. Processing Elements

As has been previously described, the five Database Engine elements work in concert to solve the problems at hand, taking advantage of the overlap and pipelining of functions where possible. Again, by reference to FIG. 3 they are:

1. Control Processor (DBCP) 310;

2. Working Store 312;

3. Predicate Evaluator (DBPE) 304;

4. Sort/Merge Unit (DBSM) 302;

5. Hash-code Generator (DBHG) 306; and,

6. Extractor/Memory Interface Unit (DBEM) 308.

d. The Control Processor

The Control Processor 310 (FIG. 3) is the only element which communicates with the application and operating system programs that use the Database Engine. It is the function of the Control Processor 310 to obtain all of the command and database information from memory, schedule and control each of the other Database Engine elements, and to communicate status back to the calling programs. The complexity of these functions requires a processor capable of computing addresses and control information in parallel with the rest of the Database Engine.

The Control Processor 310 is preferably implemented using an an 801 processor plus extensions for the Database Engine functions. It should be understood that other conventional processor architectures could be used to perform the required processing functions, as long as they are provided with interfaces to the Working Store buses 316, 318, the control bus 320 and the computer system to which the Database Engine is attached.

The Control Processor 310 performs all of the command processing and control functions in the Database Engine. These functions include the setup and control of each functional element, as well as the determination of how the command is best processed. The following is a list of the functions that are performed by the Control Processor 310:

1. Reading the Database Engine command blocks from the system memory to determine what functions are to be performed. Each command and the data descriptor(s) associated with it is converted into a processing sequence to be performed. For example, a sort command is executed by scheduling the loading of blocks of the database into the Working Store 312, having the sort/merge unit 302 sort each block until the entire data base has been sorted into many blocks, having the sort/merge unit 302 perform a merge of these blocks to create the final output records, and then having the Extractor/Memory Interface Unit 308 write these records to the system memory.

2. Fetching and evaluating the data descriptors to determine the format of the data, how it should be accessed by the Extractor/Memory Interface Unit and in what order the columns should be extracted into the Working Store 312.

3. Fetching the predicate for each command and converting it into a program which the Predicate Evaluator will execute. The conversion comprises converting column numbers to corresponding Working Store offsets (where the data is to be loaded by the extractor) and computing the next instruction fields of each instruction. After creating the Predicate Evaluator program, the Predicate Evaluator instruction and constant tables are loaded via the control bus 320.

4. Coordinating all of the other elements in the system. To perform this function, the Control Processor 310 uses the control bus 320 to write to the control registers in the other processing elements, to initiate processing, and to read the status of any of the processing elements. Each processing element can be controlled directly by the Control Processor 310 through the control bus 320. All communication between processing elements of the Database Engine is sent over the control bus 320. The Control Processor 310 runs in parallel with the other processing elements 302-308. This enables the control processor to perform processing in the background while the other elements are processing their data. The Control Processor 310 intervenes only when an element needs a new block of data to process or has an error.

The functions of the Control Processor 310 can be performed without interfering with the rest of the Database Engine processing elements since the Control Processor 310 maintains all of the information it needs for processing in an internal local working store 510 (FIG. 5A). The local Working Store 510 provides the space required to maintain all of the address and command data. Thus, once the command information is read, there is no further interaction with the system memory by the Control Processor 310.

The hardware structure of the Control Processor 310 is illustrated in FIG. 5A/5B. The Control Processor 310 is designed around an 801 processor with a 64K byte microstore and a 32K byte local working store. Only a subset of the 801 instructions need be implemented since all (for example, floating point) are not applicable to the Database Engine function. The Control Processor hardware includes the signalling and maintenance interfaces to the rest of the system for the entire Database Engine.

Turning now to FIG. 5, a Control Processor embodied using conventional 801 architecture (less the floating point logic) is illustrated. The Control Processor 310 includes a control bus input register (CBIR) 502 which buffers data read from the control bus 320 to the Control Processor 310, and a control bus output register (CBOR) 504, which buffers data written to the control bus 320 from the Control Processor 310. The Control Processor 310 is also provided with a storage data input register (SDIR) 306 and a storage data output register (SDOR) 508. The storage data input register 506 and the storage data output register 508 form the read and write buffers for the Working Store busses 316, 318. The storage data input register 506 buffers data read from the Working Store 312 to the Control Processor 310. The storage data output register 508 buffers data written from the Control Processor 310 to the Working Store 312.

Internal storage for execution of operations and Control Processor data is provided by a local working store (LWS) 510. Data for the local working store 510 is provided from any of the Working Store 312 or the Control Processor arithmetic logic unit 512 via the storage data input register 506. A control store 514 contains the control program that is executed by the control logic 516.

The control logic 516 provides sequencing and control for the Control Processor 310. The control logic 516 is a conventional microsequencer which includes an instruction register (IR) 518 and an instruction counter (IC) 520. The instruction register 518 holds the currently executing instruction while the instruction counter 520 holds the address of the currently executing instruction.

The control processor includes 32 general purpose registers (GPR) 522 for storage of operands and program data. In addition, three temporary source registers 524-528 are provided for storing the operands of the currently executing instructions. The first temporary source register (RA) 524 is provided to temporarily store the first operand of the currently executing instruction. The second temporary source register (RB) 526 is provided to temporarily store the second operand of the currently executing instruction. The third temporary source register (RT) 528 is provided to temporarily store the second operand of the currently executing instruction as an input to the rotator 530 and And-Invert-Mask unit (AIM) 532. The third temporary source register (RT) 328 also holds partial results for the multiply and other operations.

The arithmetic logic unit (ALU) 512 performs arithmetic and logical operations on the operands in the RA and RB registers 524, 526 under control of the control logic 516. The address adder 534 receives the operands from the RA and RB registers 524, 526, the current instruction for the instruction register 518, the current instruction address from the instruction counter 520 and performs the address arithmetic for branching instructions.

The rotator 530 is a barrel shifter for shifting the contents of the RT register 528 right or left. The shifted result can be ANDed with the output of the mask generator 536 by the And-Invert-Mask unit 532.

The mask generator 536 receives its input from a starting address register (SAR) 540 and an ending address register (EAR) 542. The SAR 540 and EAR 542 hold, respectively, the starting and ending bit address for the mask generator 536, as supplied by the control logic 516.

The And-Invert-Mask unit (AIM) 532 performs rotating and masking operations on the contents of the RT register 528. One of the four inputs to the AIM 532 is the multiply quotient (MQ) register 538. The MQ register 538 holds the partial product for the 801 engine's multiply step instruction and is an operand for shift, rotate and store instructions.

The SIG, QBUS, INTRPT logic 538 provides the interface to the computer system. It is through the SIG, QBUS, INTRPT logic 538 that the computer system starts and terminates the operations of the Database Engine.

It should be understood that the above-described components are embodied in a conventional 801 engine. The paths to the Working Store busses 316, 318 and the control bus 320 have been added. The interface to the the computer system is of the conventional type embodied in the 801 engine. The 801 engine is described in more detail in the article THE 801 MINICOMPUTER, author: George Radin, 1982 ACM 0-89791-066-4 82/03/0039, which is incorporated by reference herein, in its entirety.

e. The Working Store

The Working Store 312 (FIG. 3) preferably comprises at least 128K bytes of memory that is used to hold data while it is being processed by the Database Engine. The Working Store 312 is simultaneously accessible as two equal partitions via two quadword (16 byte) busses 316, 318. Read and write both take one cycle, thus the Working Store 312 is capable of 2 quadword accesses (read or write) per cycle. It should be understood that 128K bytes is the minimum preferable size. A larger size Working Store is even more preferable as cost and design constraints permit. Less preferably, smaller amounts of memory could be provided.

The Working Store 312 is directly addressable by all elements of the Database Engine system using the two quadword busses 316, 318. Each bus has 16 bytes of data plus parity and 16 bits of address and control signals. Thus each bus is 176 lines for a total of 352 lines.

f. Predicate Evaluator

The structure and operation of the Predicate Evaluator (DBPE) 304 will now be discussed with reference to FIGS. 3 and 6A/6B. The Predicate Evaluator 304 is a special purpose processing element that can perform a comparison of two quadwords (16-byte) of data in the Working Store 312 in two cycles or a comparison of a constant and a quadword of Working Store 312 in one cycle. The Predicate Evaluator 304 is a stack processor in that uses a boolean stack to process the reverse polish predicates that are created by the Control Processor 310. Instructions are loaded into an instruction table 602 by the Control Processor 310 via the control bus 320. The Predicate Evaluator 304 executes the instructions in a looping fashion until its count of records is exhausted.

The Predicate Evaluator 304 provides fast processing of search and join queries for several reasons. It can compare a two quadword operands from the Working Store 312 every two cycles. Search keys longer than a quadword are compared a quadword at a time. Further, the search execution process is overlapped with the memory access process. Specifically, the Extractor 308 writes into one partition of Working Store 312 while the Predicate Evaluator 304 processes data out of the other partition. Finally, the Predicate Evaluator instructions contain a "next field" which allows an early exit out of the current predicate term or out of the entire predicate if the current results uniquely define the search outcome. For example, when the first term of a sequence of AND terms is false, the other terms need not be evaluated. The result is false regardless of what they are.

The Predicate Evaluator 304 performs comparisons of quadword operands and uses a stack 632 to hold temporary results. It accesses the Working Store 312 through the Working Store busses 316, 318. Record operands are fetched from the Working Store 312, constants are fetched from the constant table, and the results are written back to the Working Store 312.

The constant table (CT) 604 is an array of constant quadwords used to hold comparison constants and Working Store addresses. The constant table 604 is read into the comparator 630 a quadword at a time for comparison operations. For address constants, only the least significant 16 bits are used out of a quadword. The constant table 604 is written one doubleword at a time by the Control Processor 310. The constant table 604 is initialized by the Control Processor 310 using the control bus 320. A representative size for the constant table is 2K deep by 128 bits wide.

The Instruction table 602 is a doubleword array of instructions that is loaded by the Control Processor 310 with the search program to be executed. The instruction table 602 is addressed by an instruction counter (IC) 606 and instructions are read into the instruction register (IR) 608. A representative size for the instruction table is 2K deep by 64 bits wide.

The Instruction Register (IR) 608 is a doubleword register which holds the instruction during execution. It has the following subfields:

    ______________________________________
    A, B, D   Offsets from the Base A, B, and D
              registers, respectively, for the operand
              fetch address from Working Store or the
              destination address for the result (D).
              The A, B and D fields can also specify a
              constant table address.
    C         Instruction type field.
    F         Flags. This field contains flag bits which
              control the operation, the post-ANDing or
              post-ORing of the stack, the looping for
              longer than doubleword comparisons, and the
              next field branching.
    Next      This field (N0, N1) specifies an instruc-
              tion address to be branched to if the
              result of this instruction is either true
              or false. The choice is specified in the F
              field. The next field allows the Predicate
              Evaluator to identify when a query is
              resolved early and to take a branch around
              the instructions that do not need to be
              executed. This saves execution time and
              improves performance. Due to the pipeline
              length and the two cycle delay caused by
              taking a next field branch, the next field
              branches only result in improved perfor-
              mance if the instructions are greater than
              two instructions apart, otherwise the next
              field should not be used.
    ______________________________________

    ______________________________________
    Two way merge L1(i);L2(j)
                       Perform two way merge.
    On L1(i), L2(j) meet
                       If join criteria is met
    selected join criteria
                       perform the following
    (any of >,<,=,NE)  steps. Otherwise
                       continue 2-way merge.
    Output L1(i), L2(j)
                       Write L1(i), L2(j)
                       record IDs to Working
                       Store.
    k=j                Initialize pointers.
    k=k+1              Increment window
                       pointer.
    compare L1(i):L2(k)
                       Check if join criteria
                       is met.
    if join criteria is met
    output L1(i), L2(k) and
    go to 40
    i=i+1
    Return to 5        Resume Merge
    ______________________________________