Range-based query optimizer
AssigneeOracle Corporation
InventorGennady Antoshenkov
Life of this patent
Estimating the term…
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.
Claims10
In a computer, a method for selecting data from a plurality of records each record associated with a key having a key value, the keys arranged according to an ascending order of the key values, comprising:
- determining, using a query, a logical condition of a key value of a key of a record of the plurality of records, the logical condition being ether TRUE or FALSE, the query including a plurality of ranges and logical operators relating the ranges, each range specifying a bounded set of key values;
- identifying, using the query, an interval of key values, the logical condition of each key value in the interval of key values being identical to the logical condition of the key value of the key of the record, the interval of key values including a limit value which is greater than or equal to the key value of the key of the record;
- and
- if the logical condition of the key value of the key of the record is TRUE, selecting a set of records, the key values associated with the corresponding keys of the set of records being included in the interval of key values, otherwise,
- if the logical condition is FALSE, repeating the determining and identifying steps for a next record, the next record associated with a next key having an associated key value arranged in the ascending order of the key values after the key value of the key of the record;
- reducing the plurality of ranges to a set of disjoint ranges;
- and
- making each of the logical operators either an AND or an OR logical operators to reduce the query to a canonical form;
- expressing the canonical form of the query as a Boolean tree, the nodes and levels of the Boolean tree including a root node at a top level, interior nodes at intermediate levels, and leaf nodes at a bottom level;
- representing the logical condition of the value of the key of the record by the root node,
- representing the AND and OR logical operators relating the disjoint ranges by the interior nodes;
- and
- representing each disjoint range by one of the leaf nodes.
In a computer, a method for selecting data from a plurality of records, each record associated with a key having a key value, each key value formed by concatenating a plurality of attribute values, the concatenated attribute values of each key arranged in a left to right order, the keys arranged according to an ascending order of the key values, comprising;
- determining, using a query, a partial logical condition of a left-most attribute value of a key of a record of the plurality of records, the partial logical condition being either TRUE or FALSE, the query including a plurality of ranges and logical operators relating the ranges, each range associated with one of the plurality of attribute values, and each range specifying a bounded set of the associated attribute values;
- detecting, using the query and the partial logical condition, if the partial logical condition of the leftmost attribute value is a complete logical condition of the key value;
- and
- if the partial logical condition of the leftmost attribute value is not the complete logical condition of the key, repeating the determining and detecting steps for a next left-most attribute value, the next left-most attribute value arranged right adjacent to the left-most attribute value, otherwise, making the partial logical condition the complete logical condition of the key value;
- identifying, using the query, an interval of attribute values, the logical condition of each attribute value of the interval of attribute values being identical to the partial logical condition of the attribute value of the leftmost attribute of the key of the record, the interval of attribute values including a limit value which is greater than or equal to the attribute value of the leftmost attribute of the key of the record;
- and
- if the complete logical condition of the key value of the record is TRUE, selecting a set of records, each of the attribute values associated with each corresponding key of the set of records being included in the corresponding interval of attribute values, otherwise,
- if the complete logical condition of the key value is FALSE, repeating the determining and identifying steps for a next record associated with a next key having an associated key value arranged, in the ascending order, after the value of the key of the record.
Dependencies are inferred from the claim text.