Range-based query optimizer

• US 6,439,783 B1
• Filed: 01/16/1997
• Issued: 08/27/2002
• Est. Priority Date: 07/19/1994
• Status: Expired due to Term

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle Corporation
• Inventors: Antoshenkov, Gennady
• Primary Examiner(s): Lintz, Paul R.
• Application Number:
  US08/784,227
• Time in Patent Office: 2,049 Days
• Field of Search: 395/602, 395/603, 395/601
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24524 Access plan code generation and invalidation; Reuse of access plans
• CPC Class Codes: G06F 16/24526 Internal representations for queries
• CPC Class Codes: G06F 16/24554 Unary operations; Data partitioning operations
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

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.

Claims

1. 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.

2. 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.

3. 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.

4. 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.

5. 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

(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.

6. 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.

7. 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.

8. 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.