US5590362A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Database engine predicate evaluator
Assignee: International Business Machines Corp
•
Filing: 1995-01-24
•
Granted: 1996-12-31
•
Expires: 2015-01-24
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-10-30 15:35
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: 6
Claim 1
Independent Claim
260 words
An apparatus for performing predicate evaluation, said apparatus comprising instruction table means for storing a predicate evaluation program, the instruction table means comprising means for receiving the predicate evaluation program from an external processor; instruction register means, coupled with the instruction table means, for receiving an instruction to be executed from the instruction table means, said instruction register means including a field for storing a branching condition and a field for storing a branching address; internal processor means coupled with the instruction table means, coupled with the instruction register means, for controlling a sequence of operations within the predicate evaluation apparatus in accordance with the predicate evaluation program, said internal processor being programmable by said predicate evaluation program; next field branching means, coupled with the instruction register means and responsive to a branch condition stored in said field for storing a branch condition, for determining when a processing operation of a predicate evaluation query causing processing of records in operations on sequential portions produces a result matching said branch condition, without processing the entire record, and for causing the internal processor means to branch to said branch address and around unnecessary instructions for processing the rest of the record in the predicate evaluation program for processing the query; a stack for temporarily holding data during the processing of the predicate evaluation program, said data being other than said predicate evaluation program; and comparator means, coupled with the internal processor means, for comparing a first value from the top of the stack with a second value obtained from the working storage.
Claim 2
Independent Claim
260 words
An apparatus for performing predicate evaluation, said apparatus comprising instruction table means for storing a predicate evaluation program, the instruction table means comprising means for receiving the predicate evaluation program from an external processor; instruction register means, coupled with the instruction table means, for receiving an instruction to be executed from the instruction table means, said instruction register means including a field for storing a branching condition and a field for storing a branching address; internal processor means coupled with the instruction table means, coupled with the instruction register means, for controlling a sequence of operations within the predicate evaluation apparatus in accordance with the predicate evaluation program, said internal processor being programmable by said predicate evaluation program; next field branching means, coupled with the instruction register means and responsive to a branch condition stored in said field for storing a branch condition, for determining when a processing operation of a predicate evaluation query causing processing of records in operations on sequential portions produces a result matching said branch condition, without processing the entire record, and for causing the internal processor means to branch to said branch address and around unnecessary instructions for processing the rest of the record in the predicate evaluation program for processing the query; a stack for temporarily holding data during the processing of the predicate evaluation program, said data being other than said predicate evaluation program; and comparator means, coupled with the internal processor means, for comparing a first value from the top of the stack with a second value obtained from the working storage.
Claim 3
Dependent Claim
63 words
The apparatus of claim 1 wherein said instruction register means comprises flag bits which control said next field branching means, a first next field which specifies an instruction address to be branched to if execution of said instruction results in true, and a second next field which specifies an instruction address to be branched to if execution of said instruction results in false.
Claim 4
Dependent Claim
16 words
An apparatus, as recited in claim 1 wherein said predicate evaluation program utilizes a postfix processing.
Claim 5
Independent Claim
278 words
An apparatus for performing predicate evaluation, said apparatus comprising instruction table means for storing a predicate evaluation program, the instruction table means comprising means for receiving the predicate evaluation program from an external processor; instruction register means, coupled with the instruction table means, for receiving an instruction to be executed from the instruction table means, said instruction register means including a field for storing a branching condition and a field for storing a branching address; internal processor means having a pipeline length coupled with the instruction table means, coupled with the instruction register means, for controlling a sequence of operations within the predicate evaluation apparatus in accordance with the predicate evaluation program, said internal processor being programmable by said predicate evaluation program; next field branching means, coupled with the instruction register means and responsive to a branch condition in said field for storing a branch condition, for determining when a processing operation of a predicate evaluation query causing processing of records in portions has been resolved by producing an operation result which matches said branch condition, allowing an early exit out of the current predicate term or out of the entire predicate and for causing the internal processor means to branch around unnecessary instructions in the predicate evaluation program for processing the query if the number of instructions to said branch address exceeds said pipeline length; a stack for temporarily holding data during the processing of the predicate evaluation program, said data being other than said predicate evaluation program; and comparator means, coupled with the internal processor means, for comparing a first value from the top of the stack with a second value obtained from the working storage.
Claim 6
Independent Claim
278 words
An apparatus for performing predicate evaluation, said apparatus comprising instruction table means for storing a predicate evaluation program, the instruction table means comprising means for receiving the predicate evaluation program from an external processor; instruction register means, coupled with the instruction table means, for receiving an instruction to be executed from the instruction table means, said instruction register means including a field for storing a branching condition and a field for storing a branching address; internal processor means having a pipeline length coupled with the instruction table means, coupled with the instruction register means, for controlling a sequence of operations within the predicate evaluation apparatus in accordance with the predicate evaluation program, said internal processor being programmable by said predicate evaluation program; next field branching means, coupled with the instruction register means and responsive to a branch condition in said field for storing a branch condition, for determining when a processing operation of a predicate evaluation query causing processing of records in portions has been resolved by producing an operation result which matches said branch condition, allowing an early exit out of the current predicate term or out of the entire predicate and for causing the internal processor means to branch around unnecessary instructions in the predicate evaluation program for processing the query if the number of instructions to said branch address exceeds said pipeline length; a stack for temporarily holding data during the processing of the predicate evaluation program, said data being other than said predicate evaluation program; and comparator means, coupled with the internal processor means, for comparing a first value from the top of the stack with a second value obtained from the working storage.
References Cited (Backward Citations)
EP0066061A2
Cited
EP0070119A2
Cited
US4674066A
Cited
US5239663A
Cited
WO1989012277A1
Cited
US5050075A
Cited
GB2235798A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-12-31 | 2000-07-01 | 2000-12-31 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-12-31 | 2004-07-01 | 2004-12-31 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-12-31 | 2008-07-01 | 2008-12-31 | $7700.00 | Window Closed / Lapsed |