Secondary index search

• US 6,266,660 B1
• Filed: 07/31/1998
• Issued: 07/24/2001
• Est. Priority Date: 07/31/1998
• Status: Expired due to Term

• Current Assignee: Unisys Corporation
• Original Assignee: Unisys Corporation
• Inventors: Yoneda, Kenji, Liu, Lee-Chin Hsu
• Primary Examiner(s): Black, Thomas
• Assistant Examiner(s): Mizrahi, Diane D.
• Application Number:
  US09/135,311
• Time in Patent Office: 1,089 Days
• Field of Search: 707/1, 707/2, 707/3, 707/4, 707/100, 707/201, 717/1, 717/2, 717/5, 382/232, 382/283
• US Class Current: 707/769
• CPC Class Codes: G06F 16/284 Relational databases
• 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
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users

Abstract

A secondary index search in a relational database system compares primary key selection criteria against a primary key value stored in a secondary index record that satisfies secondary key selection criteria instead of searching a primary index for a primary key value that satisfies the primary key selection criteria.

Claims

1. In a computer system, a method for selecting a data record from a database using a selection criteria that specifies values for a primary key and a secondary key of the data record where the database stores the values of the primary key and the secondary key for the data record in a secondary index record for the data record, the method comprising the steps of:

searching the database for a secondary index record that satisfies the secondary key value of the selection criteria;

comparing the primary key value of the selection criteria against the primary key value stored in the secondary index record that satisfies the secondary key value of the selection criteria; and

selecting a data record identified by the primary key value in the secondary index record if the primary key value satisfies the primary key value of the selection criteria.

2. The method of claim 1, wherein the steps of searching, comparing and selecting are repeatedly performed until no secondary index record satisfies the secondary key value of the selection criteria.

3. The method of claim 1, wherein the secondary index record is stored in a secondary index balanced tree structure and the step of searching the database searches the secondary index balanced tree structure.

4. The method of claim 1, wherein the data record is stored in a primary index balanced tree structure and the step of selecting a data record searches the primary index balanced tree structure.

5. A computer-readable medium having computer-executable instructions for performing the steps of:

searching a database table indexed on a primary and a secondary key using a secondary key value in a selection criteria to locate a secondary index record that satisfies the secondary key value of the selection criteria;

comparing a primary key value of the selection criteria against a primary key value stored in the secondary index record that satisfies the secondary key value of the selection criteria; and

selecting a data record identified by the primary key value in the secondary index record if the primary key value satisfies the primary key value of the selection criteria.

6. The computer-readable medium of claim 5, wherein the steps of searching, comparing and selecting are repeatedly performed until no secondary index record satisfies the secondary key value of the selection criteria.

7. The computer-readable medium of claim 5, wherein the secondary index record is stored in a secondary index balanced tree structure and the step of searching the database searches the secondary index balanced tree structure.

8. The computer-readable medium of claim 5, wherein the data record is stored in a primary index balanced tree structure and the step of selecting a data record searches the primary index balanced tree structure.

9. In a computer system, a method for selecting data records from a database using a selection criteria that specifies values for a primary key and a secondary key of the data record where the database stores the values of the primary key and the secondary key for the data record in a secondary index record for the data record, the method comprising the steps of:

creating a set of secondary index records that satisfy the primary and secondary key values in the selection criteria; and

selecting a data record identified by the primary key value for each secondary index record in the set.

10. The method of claim 9, wherein the secondary index records are stored in a secondary index balanced tree structure and the step of searching the database searches the secondary index balanced tree structure.

11. The method of claim 9, wherein the data record is stored in a primary index balanced tree structure and the step of selecting a data record searches the primary index balanced tree structure.

12. A secondary index search for selecting a data record from a database using a selection criteria that specifies values for a primary key and a secondary key of the data record where the database stores the values of the primary key and the secondary key for the data record in a secondary index record for the data record, the secondary index search comprising:

search means for searching the database for a secondary index record that satisfies the secondary key value of the selection criteria;

comparison means for comparing primary key values, wherein the primary key value of the selection criteria is compared against the primary key value stored in the secondary index record found by the searching means; and

retrieval means for retrieving a data record, wherein the primary key value in the secondary index record identifies the data record to be retrieved when the comparision means indicates that the selection criteria is satisfied.

13. The secondary index search of claim 12, wherein the search means, the comparision means, and the retrieval means operate until the search means finds no secondary index record that satisfies the secondary key value of the selection criteria.

14. The secondary index search of claim 12, wherein the secondary index record is stored in a secondary index balanced tree structure and the search means searches the secondary index balanced tree structure.

15. The secondary index search of claim 12, wherein the data record is stored in a primary index balanced tree structure and the retrieval means locates the data record to be retrieved using the primary index balanced tree structure.