US5537622A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Database engine
Assignee: International Business Machines Corp
•
Filing: 1994-10-14
•
Granted: 1996-07-16
•
Expires: 2014-10-14
Abstract
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.
Inventors
- 👤 Richard I. Baum
- 👤 Glen A. Brent
- 👤 Donald H. Gibson
- 👤 David B. Lindquist
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 20:02
CPC Classifications
G; G06; G06F; G06F15/00; G06F15/76; G06F15/78; G06F16/00; G06F16/20; G06F16/28; G06F16/284; F; F02; F02B; F02B75/00; F02B75/02; F02B2075/022; F02B2075/027; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99934; Y10S707/99937; Y10S707/99941; Y10S707/99943; Y10S707/99951; Y10S707/99952
Claims Analysis
Total Claims: 19
Claim 1
Independent Claim
220 words
A database coprocessor for use with a computer system, comprising: an internal control bus; an internal data bus; a control processor in communication with the internal control bus and the internal data bus; an internal memory in communication with the internal data bus; a system memory interface in communication with the internal control bus and the internal data bus; a hasher in communication with the internal control bus and the internal data bus; a Predicate Evaluator in communication with the internal control bus and the internal data bus; a sort-merge unit in communication with the internal control bus and the internal data bus; and an extractor for receiving a plurality of database commands from said computer system and for assembling final result data, said extractor in communication with said internal control bus and said internal data bus, said database commands corresponding to a plurality of database processing functions, said database processing functions being performable by said hasher, said Predicate Evaluator, said sort-merge unit and said extractor, a single invocation of said coprocessor being for executing said plurality of database functions, wherein the sort-merge unit, the Predicate Evaluator, the extractor, and the hasher are responsive to commands from the control processor and utilize said internal memory in common, said commands from said control processor being communicated via the internal control bus.
Claim 2
Dependent Claim
220 words
A database coprocessor for use with a computer system, comprising: an internal control bus; an internal data bus; a control processor in communication with the internal control bus and the internal data bus; an internal memory in communication with the internal data bus; a system memory interface in communication with the internal control bus and the internal data bus; a hasher in communication with the internal control bus and the internal data bus; a Predicate Evaluator in communication with the internal control bus and the internal data bus; a sort-merge unit in communication with the internal control bus and the internal data bus; and an extractor for receiving a plurality of database commands from said computer system and for assembling final result data, said extractor in communication with said internal control bus and said internal data bus, said database commands corresponding to a plurality of database processing functions, said database processing functions being performable by said hasher, said Predicate Evaluator, said sort-merge unit and said extractor, a single invocation of said coprocessor being for executing said plurality of database functions, wherein the sort-merge unit, the Predicate Evaluator, the extractor, and the hasher are responsive to commands from the control processor and utilize said internal memory in common, said commands from said control processor being communicated via the internal control bus.
Claim 3
Dependent Claim
50 words
The coprocessor of claim 1 wherein the sort-merge unit comprises means for selectively performing a plurality of algorithms, said plurality of algorithms and said database processing functions including at least one of join, union, intersection, difference, binary merge sorting, 4-way merge sorting, front-back merge sorting and tournament tree codeword sorting.
Claim 4
Dependent Claim
48 words
The coprocessor of claim 1 wherein said computer system includes a plurality of memories, the system memory interface is coupled to said plurality of memories in said computer system and wherein the system memory interface further comprises means for directly addressing data stored in said plurality of memories.
Claim 5
Dependent Claim
22 words
A database coprocessor, as recited in claim 1, wherein blocks of data are pipelined processed by said plurality of database processing functions.
Claim 6
Dependent Claim
52 words
A database coprocessor, as recited in claim 1, wherein said control processor receives said database commands from said extractor, said database commands including at least one of said plurality of database processing functions, an address, length and format for selected ones of database records, said database records processable by said database coprocessor.
Claim 7
Dependent Claim
38 words
A database coprocessor, as recited in claim 5, wherein said control processor further processes said database commands, with a subcommand being selectively generated for selected ones of said extractor, said Predicate Evaluator, said sort-merge unit and said hasher.
Claim 8
Dependent Claim
33 words
A database coprocessor, as recited in claim 6, wherein said subcommands being selectively loadable by said control processor into selected ones of said extractor, said Predicate Evaluator, said sort-merge unit and said hasher.
Claim 9
Dependent Claim
197 words
A database coprocessor for use with a computer system, comprising: an internal control bus; an internal data bus; a control processor in communication with the internal control bus and the internal data bus; an internal memory in communication with the internal data bus; a system memory interface in communication with the internal control bus and the internal data bus; an extractor for receiving a plurality of database commands from said computer system and for assembling final result data, said extractor in communication with said internal control bus and said internal data bus; a hasher in communication with the internal control bus and the internal data bus, said hasher computing hash indices for grouping database records; a Predicate Evaluator in communication with the internal control bus and the internal data bus; and a sort-merge unit in communication with the internal control bus and the internal data bus, wherein the sort-merge unit, the Predicate Evaluator, the extractor, and the hasher are responsive to commands from the control processor and utilize said internal memory in common, said commands from said control processor being communicated via the internal control bus and executed in response to a single invocation of said coprocessor.
Claim 10
Dependent Claim
197 words
A database coprocessor for use with a computer system, comprising: an internal control bus; an internal data bus; a control processor in communication with the internal control bus and the internal data bus; an internal memory in communication with the internal data bus; a system memory interface in communication with the internal control bus and the internal data bus; an extractor for receiving a plurality of database commands from said computer system and for assembling final result data, said extractor in communication with said internal control bus and said internal data bus; a hasher in communication with the internal control bus and the internal data bus, said hasher computing hash indices for grouping database records; a Predicate Evaluator in communication with the internal control bus and the internal data bus; and a sort-merge unit in communication with the internal control bus and the internal data bus, wherein the sort-merge unit, the Predicate Evaluator, the extractor, and the hasher are responsive to commands from the control processor and utilize said internal memory in common, said commands from said control processor being communicated via the internal control bus and executed in response to a single invocation of said coprocessor.
Claim 11
Dependent Claim
51 words
A database coprocessor, as recited in claim 8, wherein said control processor receives said database commands from said extractor, said database commands including at least one of said plurality of database functions, an address, length and format for selected ones of database records, said database records processable by said database coprocessor.
Claim 12
Dependent Claim
38 words
A database coprocessor, as recited in claim 9, wherein said control processor further processes said database commands, with a subcommand being selectively generated for selected ones of said extractor, said Predicate Evaluator, said sort-merge unit and said hasher.
Claim 13
Dependent Claim
33 words
A database coprocessor, as recited in claim 10, wherein said subcommands being selectively loadable by said control processor into selected ones of said extractor, said Predicate Evaluator, said sort-merge unit and said hasher.
Claim 14
Dependent Claim
203 words
A database coprocessor for use with a computer system, comprising: an internal control bus; an internal data bus; a control processor in communication with the internal control bus and the internal data bus; an internal memory in communication with the internal data bus; a system memory interface in communication with the internal control bus and the internal data bus; an extractor for receiving a plurality of database commands from said computer system and for assembling final result data, said extractor in communication with said internal control bus and said internal data bus; a hasher in communication with the internal control bus and the internal data bus; a Predicate Evaluator in communication with the internal control bus and the internal data bus; and a sort-merge unit in communication with the internal control bus and the internal data bus, said sort-merge unit including means for selectively performing a plurality of algorithms and database functions, wherein the sort-merge unit, the Predicate Evaluator, the extractor, and the hasher are responsive to commands from the control processor and utilize said internal memory in common, said commands from said control processor being communicated via the internal control bus and executed in response to a single invocation of said coprocessor.
Claim 15
Dependent Claim
203 words
A database coprocessor for use with a computer system, comprising: an internal control bus; an internal data bus; a control processor in communication with the internal control bus and the internal data bus; an internal memory in communication with the internal data bus; a system memory interface in communication with the internal control bus and the internal data bus; an extractor for receiving a plurality of database commands from said computer system and for assembling final result data, said extractor in communication with said internal control bus and said internal data bus; a hasher in communication with the internal control bus and the internal data bus; a Predicate Evaluator in communication with the internal control bus and the internal data bus; and a sort-merge unit in communication with the internal control bus and the internal data bus, said sort-merge unit including means for selectively performing a plurality of algorithms and database functions, wherein the sort-merge unit, the Predicate Evaluator, the extractor, and the hasher are responsive to commands from the control processor and utilize said internal memory in common, said commands from said control processor being communicated via the internal control bus and executed in response to a single invocation of said coprocessor.
Claim 16
Dependent Claim
40 words
A database coprocessor, as recited in claim 12, wherein said plurality of algorithms and database processing functions include at least one of join, union, intersection, difference, binary merge sorting, 4-way merge sorting, front-back merge sorting and tournament tree codeword sorting.
Claim 17
Dependent Claim
52 words
A database coprocessor, as recited in claim 12, wherein said control processor receives said database commands from said extractor, said database commands including at least one of said plurality of database processing functions, an address, length and format for selected ones of database records, said database records processable by said database coprocessor.
Claim 18
Dependent Claim
38 words
A database coprocessor, as recited in claim 14, wherein said control processor further processes said database commands, with a subcommand being selectively generated for selected ones of said extractor, said Predicate Evaluator, said sort-merge unit and said hasher.
Claim 19
Dependent Claim
33 words
A database coprocessor, as recited in claim 15, wherein said subcommands being selectively loadable by said control processor into selected ones of said extractor, said Predicate Evaluator, said sort-merge unit and said hasher.
References Cited (Backward Citations)
US5276899A
Cited
EP0066061A2
Cited
EP0070119A2
Cited
US4967341A
Cited
US4751635A
Cited
US5239663A
Cited
WO1989012277A1
Cited
US5179699A
Cited
GB2235798A
Cited
US5241648A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-07-16 | 2000-01-15 | 2000-07-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-07-16 | 2004-01-15 | 2004-07-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-07-16 | 2008-01-15 | 2008-07-16 | $7700.00 | Window Closed / Lapsed |