Patent ID: 6578026
Filing Date: 2003-06-10
Classification: G06F,Y10S

Abstract:
In a data processing system, a method executed by a data processor for scanning a reverse range defined by a start key value, a scan being conducted in an index for a table having an upper end and a lower end, the index having a set of keys representing a set of records and record attributes in the table, wherein each key having a record identifier (RID) designating a record in the table and a key value corresponding to an attribute of the record in the table, the method comprising the steps of:(a) searching the index for a start key having the start key value, wherein, if the start key value is exclusive, the start key is a lowest key in the index having the start key value and if the start key value is inclusive, the start key is a highest key in the index having the start key value; (b) selecting an upper bound of the reverse range to be: (i) if the start key is in the index and is inclusive, the upper bound is the upper end of the index, when the start key value is a highest key value in the index, and, when not, the upper bound is a next higher key after the start key in the index; (ii) if the start key is in the index and is exclusive, the upper bound is the start key; (iii) if the start key is not in the index and the start key value is lower than a lowest key value in the index, the upper bound is a first key in the index; and (iv) if the start key is not in the index and the lowest key value in the index is less than the start key value, the upper bound is the upper end of the table, when the start key value is higher than a highest key value in the index, and, when not, the upper bound is a lowest key in the index having a key value exceeding the start key value; (c) if the upper bound is the first key in the index, then indicating that the index does not contain any key values within the reverse range; and (d) if the upper bound is not the first key in the index, then fetching each key below the upper bound in the index.