Database engine

• US 5,548,769 A
• Filed: 12/18/1992
• Issued: 08/20/1996
• Est. Priority Date: 03/27/1990
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Lindquist, David B., Baum, Richard I., Brent, Glen A., Gibson, Donald H.
• Primary Examiner(s): Coleman, Eric
• Assistant Examiner(s): HARRITY, JOHN E
• Application Number:
  US07/993,253
• Time in Patent Office: 1,341 Days
• Field of Search: 395/800, 395/600, 364/228.6, 364/229.2, 364/282.1, 364/DIG. 1
• US Class Current: 707/752
• CPC Class Codes: F02B 2075/027 four
• CPC Class Codes: G06F 15/78 comprising a single central processing unit
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users

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

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.