Patent US5758145A successfully refreshed from Google Patents.
US5758145A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for generating dynamic and hybrid sparse indices for workfiles used in SQL queries
Assignee: International Business Machines Corp
•
Filing: 1995-02-24
•
Granted: 1998-05-26
•
Expires: 2015-02-24
Abstract
Abstract A method, apparatus and article for manufacture for generating static, dynamic and hybrid sparse indices for use with workfiles used by SQL queries in a relational database management system. A workfile and a sparse index structure are temporarily created in the computer during execution of the query by the computer. The workfile stores intermediate relations resulting from execution of a portion of the SQL query, wherein the intermediate relations comprise sorted rows for an inner table referenced in the SQL query. The sparse index structure contains one or more entries indicating at least an approximate location for at least some of the rows in the workfile. As one or more rows from an outer table referenced in the SQL query are retrieved, the entries of the sparse index structure are searched for a closest matching entry for each retrieved row. The sorted workfile is then scanned for a row matching each retrieved row using the closest matching entry from the sparse index structure as a starting position. The sparse index structure is then updated with an entry corresponding to the row from the sorted workfile matching the retrieved row from the outer table.
Inventors
- 👤 Gautam Bhargava
- 👤 Paramesh Sampatrai Desai
- 👤 Piyush Goel
- 👤 Peter Hoa
- 👤 Fen-Ling Lin
- 👤 Balakrishna Raghavendra Iyer
- 👤 Jerry Mukai
- 👤 William Samuel Perlman
- 👤 Hong Sang Tie
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 04:38
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/22; G06F16/2228; G06F16/2246; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99934; Y10S707/99936; Y10S707/99937
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
253 words
A method of performing a query in a computer, the query being used by the computer to direct information retrieval from a database stored in an electronic storage device connected to the computer, the method comprising the steps of: (a) creating a workfile and a sparse index structure in the computer, wherein the workfile contains sorted rows for an inner table referenced in the query, the sparse index structure comprises a static portion and a dynamic portion, and the creating step comprises the steps of: (1) sorting the rows of the inner table to create a sorted list of rows, (2) merging the sorted rows of the inner table to eliminate duplicate rows in the sorted list, (3) selecting one or more of the merged rows at predefined intervals in the sorted list, and (4) inserting entries corresponding to the selected rows into the static portion of the sparse index structure; (b) retrieving one or more rows from an outer table referenced in the query; (c) searching the sparse index structure for a closest matching entry for the retrieved row from the outer table; (d) scanning the sorted workfile for a row matching the retrieved row from the outer table using the closest matching entry from the sparse index structure as a starting position in the workfile; (e) updating the sparse index structure with an entry corresponding to the row from the sorted workfile matching the retrieved row from the outer table; and (f) repeating steps (b)-(e) using the updated sparse index structure.
Claim 2
Independent Claim
253 words
A method of performing a query in a computer, the query being used by the computer to direct information retrieval from a database stored in an electronic storage device connected to the computer, the method comprising the steps of: (a) creating a workfile and a sparse index structure in the computer, wherein the workfile contains sorted rows for an inner table referenced in the query, the sparse index structure comprises a static portion and a dynamic portion, and the creating step comprises the steps of: (1) sorting the rows of the inner table to create a sorted list of rows, (2) merging the sorted rows of the inner table to eliminate duplicate rows in the sorted list, (3) selecting one or more of the merged rows at predefined intervals in the sorted list, and (4) inserting entries corresponding to the selected rows into the static portion of the sparse index structure; (b) retrieving one or more rows from an outer table referenced in the query; (c) searching the sparse index structure for a closest matching entry for the retrieved row from the outer table; (d) scanning the sorted workfile for a row matching the retrieved row from the outer table using the closest matching entry from the sparse index structure as a starting position in the workfile; (e) updating the sparse index structure with an entry corresponding to the row from the sorted workfile matching the retrieved row from the outer table; and (f) repeating steps (b)-(e) using the updated sparse index structure.
Claim 3
Dependent Claim
41 words
The method of claim 1 above, wherein the scanning step comprises scanning the sorted workfile for a row matching the retrieved row from the outer table when the closest matching entry from the sparse index structure is not an identical match.
Claim 4
Dependent Claim
83 words
The method of claim 1 above, wherein the static portion of the sparse index structure comprises a plurality of entries, each of the entries comprises an identifying key and a record identifier, and the inserting step (4) comprises the steps of selecting the key and the record identifier from each of the selected rows and inserting the key and the record identifier into one of the entries in the static portion of the sparse index structure in an order sorted by the key.
Claim 5
Dependent Claim
48 words
The method of claim 1 above, wherein the updating step comprises updating the dynamic portion of the sparse index structure by inserting an entry corresponding to the row from the workfile matching the retrieved row from the outer table into the dynamic portion of the sparse index structure.
Claim 6
Dependent Claim
85 words
The method of claim 4 above, wherein the sparse index structure comprises a plurality of entries, each of the entries comprises a key and a record identifier, and the inserting step comprises the steps of selecting the key and the record identifier from the row from the workfile matching the retrieved row from the outer table and inserting the key and the record identifier into one of the entries in the dynamic portion of the sparse index structure in an order sorted by the key.
Claim 7
Independent Claim
292 words
An apparatus for performing a query in a computer having a data storage device coupled thereto, the data storage device storing a database, the apparatus comprising: (a) means, performed by the computer, for accepting the query into the computer, the query being performed by the computer to retrieve data from the database; (b) means, performed by the computer, for creating a workfile and a sparse index structure in the computer, wherein the workfile contains sorted rows for an inner table referenced in the query, the sparse index structure comprises a static portion and a dynamic portion, and the means for creating comprises: (1) means for sorting the rows of the inner table to create a sorted list of rows, (2) means for merging the sorted rows of the inner table to eliminate duplicate rows in the sorted list, (3) means for selecting one or more of the merged rows at predefined intervals in the sorted list, and (4) means for inserting entries corresponding to the selected rows into the static portion of the sparse index structure; (c) means, performed by the computer, for retrieving one or more rows from an outer table referenced in the query; (d) means, performed by the computer, for searching the sparse index structure for a closest matching entry for the retrieved row from the outer table; (e) means, performed by the computer, for scanning the sorted workfile for a row matching the retrieved row from the outer table using the closest matching entry from the sparse index structure as a starting position in the workfile; and (f) means, performed by the computer, for updating the sparse index structure with an entry corresponding to the row from the sorted workfile matching the retrieved row from the outer table.
Claim 8
Independent Claim
292 words
An apparatus for performing a query in a computer having a data storage device coupled thereto, the data storage device storing a database, the apparatus comprising: (a) means, performed by the computer, for accepting the query into the computer, the query being performed by the computer to retrieve data from the database; (b) means, performed by the computer, for creating a workfile and a sparse index structure in the computer, wherein the workfile contains sorted rows for an inner table referenced in the query, the sparse index structure comprises a static portion and a dynamic portion, and the means for creating comprises: (1) means for sorting the rows of the inner table to create a sorted list of rows, (2) means for merging the sorted rows of the inner table to eliminate duplicate rows in the sorted list, (3) means for selecting one or more of the merged rows at predefined intervals in the sorted list, and (4) means for inserting entries corresponding to the selected rows into the static portion of the sparse index structure; (c) means, performed by the computer, for retrieving one or more rows from an outer table referenced in the query; (d) means, performed by the computer, for searching the sparse index structure for a closest matching entry for the retrieved row from the outer table; (e) means, performed by the computer, for scanning the sorted workfile for a row matching the retrieved row from the outer table using the closest matching entry from the sparse index structure as a starting position in the workfile; and (f) means, performed by the computer, for updating the sparse index structure with an entry corresponding to the row from the sorted workfile matching the retrieved row from the outer table.
Claim 9
Dependent Claim
44 words
The apparatus of claim 6 above, wherein the means for scanning comprises means for scanning the sorted workfile for a row matching the retrieved row from the outer table when the closest matching entry from the sparse index structure is not an identical match.
Claim 10
Dependent Claim
84 words
The apparatus of claim 6 above, wherein the static portion of the sparse index structure comprises a plurality of entries, each of the entries comprises a key and a record identifier, and the means for inserting (4) comprises means for selecting the key and the record identifier from each of the selected rows and means for inserting the key and the record identifier into one of the entries in the static portion of the sparse index structure in an order sorted by the key.
Claim 11
Dependent Claim
51 words
The apparatus of claim 6 above, wherein the means for updating comprises means for updating the dynamic portion of the sparse index structure by inserting an entry corresponding to the row from the workfile matching the retrieved row from the outer table into the dynamic portion of the sparse index structure.
Claim 12
Dependent Claim
87 words
The apparatus of claim 9 above, wherein the sparse index structure comprises a plurality of entries, each of the entries comprises a key and a record identifier, and the means for inserting comprises means for selecting the key and the record identifier from the row from the workfile matching the retrieved row from the outer table and means for inserting the key and the record identifier into one of the entries in the dynamic portion of the sparse index structure in an order sorted by the key.
Claim 13
Dependent Claim
272 words
A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform method steps for performing a query in a computer, the query being performed by the computer to retrieve data from a database stored in an electronic storage device coupled to the computer, the method comprising the steps of: (a) creating a workfile and a sparse index structure in the computer, wherein the workfile contains sorted rows for an inner table referenced in the query, the sparse index structure comprises a static portion and a dynamic portion, and the creating step comprises the steps of: (1) sorting the rows of the inner table to create a sorted list of rows, (2) merging the sorted rows of the inner table to eliminate duplicate rows in the sorted list, (3) selecting one or more of the merged rows at predefined intervals in the sorted list, and (4) inserting entries corresponding to the selected rows into the static portion of the sparse index structure; (b) retrieving one or more rows from an outer table referenced in the query; (c) searching the sparse index structure for a closest matching entry for the retrieved row from the outer table; (d) scanning the sorted workfile for a row matching the retrieved row from the outer table using the closest matching entry from the sparse index structure as a starting position in the workfile; (e) updating the sparse index structure with an entry corresponding to the row from the sorted workfile matching the retrieved row from the outer table; and (f) repeating steps (b)-(e) using the updated sparse index structure.
Claim 14
Dependent Claim
272 words
A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform method steps for performing a query in a computer, the query being performed by the computer to retrieve data from a database stored in an electronic storage device coupled to the computer, the method comprising the steps of: (a) creating a workfile and a sparse index structure in the computer, wherein the workfile contains sorted rows for an inner table referenced in the query, the sparse index structure comprises a static portion and a dynamic portion, and the creating step comprises the steps of: (1) sorting the rows of the inner table to create a sorted list of rows, (2) merging the sorted rows of the inner table to eliminate duplicate rows in the sorted list, (3) selecting one or more of the merged rows at predefined intervals in the sorted list, and (4) inserting entries corresponding to the selected rows into the static portion of the sparse index structure; (b) retrieving one or more rows from an outer table referenced in the query; (c) searching the sparse index structure for a closest matching entry for the retrieved row from the outer table; (d) scanning the sorted workfile for a row matching the retrieved row from the outer table using the closest matching entry from the sparse index structure as a starting position in the workfile; (e) updating the sparse index structure with an entry corresponding to the row from the sorted workfile matching the retrieved row from the outer table; and (f) repeating steps (b)-(e) using the updated sparse index structure.
Claim 15
Dependent Claim
41 words
The method of claim 11 above, wherein the scanning step comprises scanning the sorted workfile for a row matching the retrieved row from the outer table when the closest matching entry from the sparse index structure is not an identical match.
Claim 16
Dependent Claim
82 words
The method of claim 11 above, wherein the static portion of the sparse index structure comprises a plurality of entries, each of the entries comprises a key and a record identifier, and the inserting step (4) comprises the steps of selecting the key and the record identifier from each of the selected rows and inserting the key and the record identifier into one of the entries in the static portion of the sparse index structure in an order sorted by the key.
Claim 17
Dependent Claim
48 words
The method of claim 11 above, wherein the updating step comprises updating the dynamic portion of the sparse index structure by inserting an entry corresponding to the row from the workfile matching the retrieved row from the outer table into the dynamic portion of the sparse index structure.
Claim 18
Dependent Claim
85 words
The method of claim 14 above, wherein the sparse index structure comprises a plurality of entries, each of the entries comprises a key and a record identifier, and the inserting step comprises the steps of selecting the key and the record identifier from the row from the workfile matching the retrieved row from the outer table and inserting the key and the record identifier into one of the entries in the dynamic portion of the sparse index structure in an order sorted by the key.
References Cited (Backward Citations)
US4606002A
Cited
US4817036A
Cited
US5386556A
Cited
US5197005A
Cited
US5369762A
Cited
US5261093A
Cited
US5315709A
Cited
US5550971A
Cited
US5560007A
Cited
US5519859A
Cited
JPH09206440A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-05-25 | 2001-11-24 | 2002-05-26 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-05-25 | 2005-11-24 | 2006-05-26 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-05-25 | 2009-11-24 | 2010-05-26 | $7700.00 | Window Closed / Lapsed |