Implementing descending indexes with a descend function

Details Implementing descending indexes with a descend function Implementing descending indexes with a descend function

2002-10-24

2004-08-17

Robinson, Greta (Department: 2177)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000

Reexamination Certificate

active

06778985

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to database management systems and more particularly to methods and apparatus for implementing indexes in database management systems.
BACKGROUND OF THE INVENTION
Database management systems provide users the ability to store, update, and retrieve information by submitting commands to a database server. To be correctly processed, the commands must comply with a database language that is supported by the database server. One popular database language is known as the Structured Query Language (SQL). SQL provides a user with the ability to create tables that can be used to store various types of information.
Database management systems typically create tables in the form of abstract data structures and/or objects for retaining information. The tables are generally organized in the form of rows and columns. Each row in the table represents an individual record. For example, a table that stores employee records may contain columns that store: last names, first names, date of birth, employee number, department, etc. Each row in the table stores the same column information for a different employee.
SQL also provides a user with the ability to generate complex queries that can be used to retrieve specific information from the tables. The information retrieved may be further organized into meaningful form for subsequent presentation and/or analysis. For example, a user may generate a query that results in the creation of an answer table containing only the last names and departments of all employees. This information can be subsequently organized by department in order to assess staffing requirements.
In a typical database system, data is stored in a table in an unordered form. As records are entered into the table, they are inserted into the next available location. Such a location can often be at a non-contiguous storage sector of a permanent storage device, such as a fixed disk drive or optical drive, relative to the location of the previous record. Consequently, it is not always possible to directly access and/or retrieve a specific record or a range of records. In the absence of supplemental data structures, every row in the table must be examined to properly execute a query that requires retrieval of one or more records.
Many database systems provide an object type called an index that can significantly increase the speed of certain data retrieval processes. A database index is conceptually similar to a normal index found at the end of a book, in that both kinds of indexes comprise an ordered list of information accompanied by a reference location within the book where the information can be found. The index is maintained separately from the actual database table for which the index is created.
A database index can be considered to be a mini table, where each “row” is an index entry that contains a key value and a pointer. The key value of an index entry is a value created from the values in one or more columns of a corresponding row of the table. Those columns are referred to as “key columns”. The pointer of an index entry points to the location of the row that corresponds to the index entry.
For example, assume that an index is built on the last name (or first name) column of the employee table mentioned above. Each entry in the index would include a key value formed from the last name (or first name) column found in a row of the employee table. Thus, a typically entry of the index would have the form <Smith, rowid> (or John, rowid), where “Smith” (or “John”) is the key value for the index entry, and rowid is a pointer to the corresponding row of the table which has “Smith” in the last name column (or “John” in the first name column).
Unlike the rows of a table, the entries in the index are maintained in a sorted order. For example, if a table contains a column that stores date information, an index ay be created on the date column. The resulting index would contain entries that are sorted in an order (typically chronological) that is based on the dates contained therein. Accordingly, information may be efficiently retrieved for a range of dates based on the sorted order of the index.
In order to improve processing of queries involving multiple column constraints, an index can be created on multiple columns of the table. Such an index would include composite key values in the form of column
1
.column
2
, where column
1
and column
2
are the constraint columns from the table. For example, an index built on a student information table can be created on both a grade_level column and a student_identification column. The index would include a composite key (grade_level.student_identification) that is sorted in ascending order based on the grade_level. In addition, within each grade level, the index would be further sorted in ascending order based on the student_identification of students in each particular grade_level.
There are situations where it may be desirable to create the index such that the grade_level sub_key is sorted in ascending order and, within each grade level, the student_identification sub_key is sorted in descending order. Similarly, a client may want the index created such that the grade_level sub_key is sorted in descending order and the student_identification sub_key is sorted in ascending order.
SQL does not provide the ability to sort an index in descending order. There exist, however, specific database systems that provide extended commands which allow sorting of an index in descending order. For example, some approaches to providing descending-ordered indexes do not actually create indexes with entries that are sorted in descending order. Rather, each “descending” index is created and sorted in ascending order, but read in reverse to simulate an index sorted in descending order. This ability does not allow sorting of indexes that have composite keys such that a first sub_key is sorted in ascending order, while a second sub_key is sorted in descending order.
Another approach to creating indexes having composite keys stores metadata that indicates whether a sub_key should be sorted in ascending order or descending order. The system then switches between two different comparison functions, based on the metadata, to sort each sub_key. Although this allows a first sub_key to sort in ascending order, while a second sub key sorts in descending order, it requires code that touches indexes to know which sub_keys sort in ascending order, and which sub_keys sort in descending order. Adding special cases such as this to code takes time, makes the code run slower, introduces bugs, and makes future code maintenance more difficult.
Based on the foregoing, a disadvantage associated with current methods of implementing database indexes is the inability to create an index on multiple columns of a table wherein various sub_keys of the index may be sorted in either ascending and/or descending order without requiring all the code that reads and modifies indexes to treat any sub_key as special.
SUMMARY OF THE INVENTION
There is a need for methods and apparatus that allow creation of indexes that include composite keys wherein the sub_keys may be individually sorted in ascending order, descending order, or a combination of ascending and descending order, while allowing all code that reads and manipulates indexes to sort all sub keys in ascending order.
These and other needs are addressed by the present invention, wherein a database server reverses the sortability of key values in an index that must be sorted in descending order, thereby allowing sorting of multiple sub_keys in any combination of ascending or descending order using only one sort function.
The sortability of a key value refers to the characteristic of the key value that determines the order of a key value relative to other key values. For example, a database server may sort based on a letter-by-letter comparison between key values, or based on a byte-by-byte comparison between key values. In a system where sorting is performed on a letter-by-letter basis,

Affiliated with

Also associated with

Rating

Implementing descending indexes with a descend function does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Implementing descending indexes with a descend function, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Implementing descending indexes with a descend function will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3309112