US6439783B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Range-based query optimizer
Assignee: Oracle International Corp
•
Filing: 1997-01-16
•
Granted: 2002-08-27
•
Expires: 2017-01-16
Abstract
Abstract A computerized query optimizer for use with a database system having an ordered set of records. The optimizer employs a scanner and an evaluator. A query is composed as ranges of record values related by logical operators. The query is converted to a Boolean tree in canonical form. The tree is optimized to express the ranges as a set of disjoint semi-open ranges. The scanner reads a next record from the database. The evaluator, using the query, delivers a logical true or false condition for the record. In addition, the evaluator also delivers an interval of values having the same logical condition as the logical condition of the record. If this logical condition is false, the scanner skips over records having values of the interval, otherwise, if the logical condition is true, records having values of the interval are selected.
Inventors
- 👤 Gennady Antoshenkov
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 13:44
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2452; G06F16/24524; G06F16/24526; G06F16/2455; G06F16/24553; G06F16/24554; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99934
Claims Analysis
Total Claims: 10
Claim 1
Independent Claim
219 words
A method for processing a query that specifies at least one range condition, the method comprising the steps of: (A) creating a Boolean expression that corresponds to the query; (B) evaluating the Boolean expression for a current key value; (C) before evaluating the Boolean expression for a next key value, performing the steps of (C1) determining a limit key based on said Boolean expression and said current key value; (C2) if the Boolean expression evaluates to TRUE for said current key value, then (C2a) fetching a next key value without evaluating the Boolean expression for the next key value; (C2b) repeating step C2a until reaching a next key value that is equal to or greater than the limit key; (C2c) establishing the next key value that is equal to or greater than the limit key as a new current key value and repeating steps (B) through (C) using the new current key value; (C3) if the Boolean expression evaluates to FALSE for said current key value, then (C3a) skipping to a next key value that is equal to or greater than the limit key; and (C3b) establishing the next key value that is equal to or greater than the limit key as a new current key value and repeating steps (B) through (C) using the new current key value.
Claim 2
Independent Claim
219 words
A method for processing a query that specifies at least one range condition, the method comprising the steps of: (A) creating a Boolean expression that corresponds to the query; (B) evaluating the Boolean expression for a current key value; (C) before evaluating the Boolean expression for a next key value, performing the steps of (C1) determining a limit key based on said Boolean expression and said current key value; (C2) if the Boolean expression evaluates to TRUE for said current key value, then (C2a) fetching a next key value without evaluating the Boolean expression for the next key value; (C2b) repeating step C2a until reaching a next key value that is equal to or greater than the limit key; (C2c) establishing the next key value that is equal to or greater than the limit key as a new current key value and repeating steps (B) through (C) using the new current key value; (C3) if the Boolean expression evaluates to FALSE for said current key value, then (C3a) skipping to a next key value that is equal to or greater than the limit key; and (C3b) establishing the next key value that is equal to or greater than the limit key as a new current key value and repeating steps (B) through (C) using the new current key value.
Claim 3
Dependent Claim
72 words
The method of claim 1 further comprising the steps of: incrementing a limit count when the next key value that is equal to or greater than the limit key is the next consecutive key value after the current key value; and if the limit count exceeds a predetermined threshold, then evaluating the Boolean expression for the new current key value without determining a limit key based on the new current key value.
Claim 4
Dependent Claim
40 words
The method of claim 2 further comprising the step of setting the limit count to zero when the next key value that is greater than the limit key is not the next consecutive key value after the current key value.
Claim 5
Dependent Claim
73 words
The method of claim 2 wherein: the step of evaluating the new current key value without determining a limit key based on the new current key value is performed as long as the limit count exceeds the predetermined threshold; and the method further comprises the step of setting the limit count to zero if the Boolean expression evaluates to a particular logical state for a predetermined number of consecutive new current key values.
Claim 6
Dependent Claim
258 words
A computer-readable medium carrying one or more sequences of instructions for processing a query that specifies at least one range condition, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of: (A) creating a Boolean expression that corresponds to the query; (B) evaluating the Boolean expression for a current key value; (C) before evaluating the Boolean expression for a next key value, performing the steps of (C1) determining a limit key based on said Boolean expression and said current key value: (C2) if the Boolean expression evaluates to TRUE for said current key value, then (C2 a ) fetching a next key value without evaluating the Boolean expression for the next key value; (C2 b ) repeating step C2 a until reaching a next key value that is equal to or greater than the limit key; (C2 c ) establishing the next key value that is equal to or greater than the limit key as a new current key value and repeating steps (B) through (C) using the new current key value; (C3) if the Boolean expression evaluates to FALSE for said current key value, then (C3 a ) skipping to a next key value that is equal to or greater than the limit key; and (C3 b ) establishing the next key value that is equal to or greater than the limit key as a new current key value and repeating steps (B) through (C) using the new current key value.
Claim 7
Dependent Claim
258 words
A computer-readable medium carrying one or more sequences of instructions for processing a query that specifies at least one range condition, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of: (A) creating a Boolean expression that corresponds to the query; (B) evaluating the Boolean expression for a current key value; (C) before evaluating the Boolean expression for a next key value, performing the steps of (C1) determining a limit key based on said Boolean expression and said current key value: (C2) if the Boolean expression evaluates to TRUE for said current key value, then (C2 a ) fetching a next key value without evaluating the Boolean expression for the next key value; (C2 b ) repeating step C2 a until reaching a next key value that is equal to or greater than the limit key; (C2 c ) establishing the next key value that is equal to or greater than the limit key as a new current key value and repeating steps (B) through (C) using the new current key value; (C3) if the Boolean expression evaluates to FALSE for said current key value, then (C3 a ) skipping to a next key value that is equal to or greater than the limit key; and (C3 b ) establishing the next key value that is equal to or greater than the limit key as a new current key value and repeating steps (B) through (C) using the new current key value.
Claim 8
Dependent Claim
73 words
The computer-readable medium of claim 5 wherein the steps further comprise: incrementing a limit count when the next key value that is equal to or greater than the limit key is the next consecutive key value after the current key value; and if the limit count exceeds a predetermined threshold, then evaluating the Boolean expression for the new current key value without determining a limit key based on the new current key value.
Claim 9
Dependent Claim
41 words
The computer-readable medium of claim 6 wherein the steps further comprise setting the limit count to zero when the next key value that is greater than the limit key is not the next consecutive key value after the current key value.
Claim 10
Dependent Claim
71 words
The computer-readable medium of claim 6 wherein: the step of evaluating the new current key value without determining a limit key based on the new current key value is performed as long as the limit count exceeds the predetermined threshold; and the steps further comprise setting the limit count to zero if the Boolean expression evaluates to a particular logical state for a predetermined number of consecutive new current key values.
References Cited (Backward Citations)
US3964029A
Cited
US4118788A
Cited
US4255796A
Cited
US4606022A
Cited
US4677550A
Cited
US4829427A
Cited
US4817036A
Cited
US4811217A
Cited
US4774657A
Cited
US4945475A
Cited
US4827462A
Cited
US4811199A
Cited
US5237678A
Cited
US4947320A
Cited
US5043872A
Cited
US4956774A
Cited
US5241648A
Cited
US5257365A
Cited
WO1992006440A1
Cited
US5398199A
Cited
US5649181A
Cited
US5560007A
Cited
US5657437A
Cited
US5897632A
Cited
US6199063B1
Cited
US6125360A
Cited
US6134543A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2005-08-26 | 2006-02-25 | 2006-08-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2009-08-26 | 2010-02-25 | 2010-08-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2013-08-26 | 2014-02-25 | 2014-08-27 | $7700.00 | Window Closed / Lapsed |