Method and apparatus for generating dynamic and hybrid sparse indices for workfiles used in SQL queries

• US 5,978,792 A
• Filed: 01/13/1998
• Issued: 11/02/1999
• Est. Priority Date: 02/24/1995
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Perlman, William Samuel, Lin, Fen-Ling, Bhargava, Gautam, Iyer, Balakrishna Raghavendra, Mukai, Jerry, Tie, Hong Sang, Desai, Paramesh Sampatrai, Goel, Piyush, Hoa, Peter
• Primary Examiner(s): Fetting, Anton
• Assistant Examiner(s): Corrielus, Jean M.
• Application Number:
  US09/006,745
• Time in Patent Office: 658 Days
• Field of Search: 707/2, 707/1, 707/3, 707/4, 707/6, 707/7
• US Class Current: 707/692
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• 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/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A method and apparatus for generating static, dynamic and hybrid sparse indices for use with workfiles used by SQL queries in a relational database management system.

Claims

1. A method of performing a query in a computer-implemented database management system, comprising:

(a) probing a sparse index to determine a starting location of a next search of a key value in the query, wherein the sparse index stores entries containing key values indicating only an approximate location of data records stored in an associated file and is comprised of a static part that is created during a merge phase of file creation;

(b) returning an entry from the sparse index without performing the next search when the entry matches the key value; and

(c) performing the next search using a closest starting entry from the sparse index when no entry in the sparse index matches the key value.

2. The method of claim 1 above, wherein the performing step (c) further comprises inserting a new entry into the sparse index based on the next search results.

3. The method of claim 1 above, further comprising removing one or more entries from the sparse index.

4. The method of claim 1 above, wherein the static part of sparse index is never changed.

5. The method of claim 1, wherein the static part of the sparse index comprises a fixed number of the key values along with their record identifiers (RIDs) in a file.

6. The method of claim 1, further comprising eliminating duplicate entries during the merge phase of file creation.

7. The method of claim 1 above, further comprising creating a dynamic part of the sparse index during a search phase of file access.

8. The method of claim 7, further comprising updating the dynamic part of the sparse index as required.

9. The method of claim 1, further comprising determining an exact location of the data record in the file using an auxiliary search and the approximate location provided by the sparse index.

10. The method of claim 1, wherein each entry in the sparse index comprises a key value and a record id (RID).

11. The method of claim 10, wherein the RID provides a location of a data record matching the key value.

12. An apparatus for performing a query in a computer-implemented database management system, comprising:

(a) means, performed by a computer, for probing a sparse index to determine a starting location of a next search of a key value in the query, wherein the sparse index stores entries containing key values indicating only an approximate location of data records stored in an associated file and is comprised of a static part that is created during a merge phase of file creation;

(b) means, performed by a computer, for returning an entry from the sparse index without performing the next search when the entry matches the key value; and

(c) means, performed by a computer, for performing the next search using a closest starting entry from the sparse index when no entry in the sparse index matches the key value.

13. The apparatus of claim 12 above, wherein the means for performing (c) further comprises means for inserting a new entry into the sparse index based on the next search results.

14. The apparatus of claim 12 above, further comprising means for removing one or more entries from the sparse index.

15. The apparatus of claim 12, wherein the static part of sparse index is never changed.

16. The apparatus of claim 12, wherein the static part of the sparse index comprises a fixed number of the key values along with their record identifiers (RIDs) in a file.

17. The apparatus of claim 12, further comprising means for eliminating duplicate entries during the merge phase of file creation.

18. The apparatus of claim 12 above, further comprising means for creating a dynamic part of the sparse index during a search phase of file access.

19. The apparatus of claim 18, further comprising means for updating the dynamic part of the sparse index as required.

20. The apparatus of claim 12, further comprising means for determining an exact location of the data record in the file using an auxiliary search and the approximate location provided by the sparse index.

21. The apparatus of claim 12, wherein each entry in the sparse index comprises a key value and a record id (RID).

22. The apparatus of claim 21, wherein the RID provides a location of a data record matching the key value.

23. A program storage device readable by a computer, tangibly embodying one or more instructions executed by the computer to perform a query a computer-implemented database management system, the method comprising:

(a) probing a sparse index to determine a starting location of a next search of a key value in the query, wherein the sparse index stores entries containing key values indicating only an approximate location of data records stored in an associated file and is comprised of a static part that is created during a merge phase of file creation;

(b) returning an entry from the sparse index without performing the next search when the entry matches the key value; and

(c) performing the next search using a closest starting entry from the sparse index when no entry in the sparse index matches the key value.

24. The article of manufacture of claim 23 above, wherein the performing step (c) further comprises inserting a new entry into the sparse index based on the next search results.

25. The article of manufacture of claim 23 above, further comprising removing one or more entries from the sparse index.

26. The article of manufacture of claim 23, wherein the static part of sparse index is never changed.

27. The article of manufacture of claim 23, wherein the static part of the sparse index comprises a fixed number of the key values along with their record identifiers (RIDs) in a file.

28. The article of manufacture of claim 23, further comprising eliminating duplicate entries during the merge phase of file creation.

29. The article of manufacture of claim 23 above, further comprising creating a dynamic part of the sparse index during a search phase of file access.

30. The article of manufacture of claim 29, further comprising updating the dynamic part of the sparse index as required.

31. The article of manufacture of claim 23, further comprising determining an exact location of the data record in the file using an auxiliary search and the approximate location provided by the sparse index.

32. The article of manufacture of claim 23, wherein each entry in the sparse index comprises a key value and a record id (RID).

33. The article of manufacture of claim 32, wherein the RID provides a location of a data record matching the key value.

34. A data structure for use by a query performed by a database management system, comprising a hybrid sparse index stored in an electronic memory, wherein the hybrid sparse index stores entries containing key values indicating only an approximate location of data records stored in an associated file and is comprised of:

(1) a static part that is built during a merge phase of file creation and is never changed, and (2) a dynamic part that is created during a search phase of file access.

35. The data structure of claim 34, wherein the hybrid sparse index is probed to determine a starting location of a next search of a key value in the query.

36. The data structure of claim 34, wherein an entry is returned from the hybrid sparse index without performing the next search when the entry matches the key value.

37. The data structure of claim 34, wherein the next search is performed using a closest starting entry from the hybrid sparse index when no entry in the hybrid sparse index matches the key value.

38. The data structure of claim 37 above, wherein a new entry is inserted into the hybrid sparse index based on the next search results.

39. The data structure of claim 34, wherein the static part of the hybrid sparse index comprises a fixed number of the key values along with their record identifiers (RIDs) in a file.

40. The data structure of claim 34, wherein duplicate entries are eliminated during the merge phase of file creation.

41. The data structure of claim 34, wherein the dynamic part of the sparse index is updated as required.

42. The data structure of claim 34, wherein an exact location of the data record in the file is determined using an auxiliary search and the approximate location provided by the hybrid sparse index.

43. The data structure of claim 34, wherein each entry in the hybrid sparse index comprises a key value and a record id (RID).

44. The data structure of claim 34, wherein the RID provides a location of a data record matching the key value.