Range-based query optimizer

Claim 2

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.

Claim 3

The method of claim 1 further comprising: relating nodes at a particular level of the Boolean tree by a first logical operator; and relating nodes at an adjacent level by a second logical operator, the first and second logical operators being different.

Claim 4

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.

Claim 5

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.

Claim 6

The method of claim 3 further comprising: increasing the limit value to produce a higher limit value; and determining, using the query, the logical condition of the higher limit value; if the logical condition of the higher limit value is identical to the logical condition of the limit value, replacing the limit value with the higher limit value.

Claim 7

The method of claim 4 further comprising: 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.

Claim 8

The method of claim 5, further comprising: expressing the canonical form of the query as a Boolean tree, 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.

Claim 9

The method of claim 6 further comprising: relating nodes at a particular level of the Boolean tree by a first logical operator; and relating nodes at an adjacent level by a second logical operator, the first and second logical operators being different.

Claim 10

The method of claim 3 further comprising: arranging the plurality of ranges in an ascending order of the bounded set of attribute values; assigning, in the ascending order, a unique rank number to each range; identifying a particular range including the interval of attribute values; and associating the corresponding rank of the particular range with the interval of attribute values.

Claim 11

The method of claim 8 further comprising: reducing the plurality of ranges to a set of disjoint ranges; and relating the set of disjoint ranges by AND and OR logical operators to reduce the query to a canonical form; expressing the canonical form of the query as a Boolean tree, the Boolean tree comprising a plurality of nodes arranged at a plurality of levels, 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 complete logical condition of the value of the key of the record by the root node; and representing the logical operators by the interior nodes, and representing each disjoint range by one of the leaf nodes.

Claim 12

The method of claim 9 further comprising: associating the partial logical condition of the leading attribute value with the leaf node representing the disjoint range including the leading attribute value; propagating, as long as the partial logical condition remains definite, the partial logical condition to one of the nodes at a higher level; and setting the complete logical condition to the partial logical condition when the partial logical condition is propagated to the root node.