US5495608A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Dynamic index retrieval, bit mapping, and optimization of a single relation access
Assignee: Oracle International Corp
•
Filing: 1994-07-25
•
Granted: 1996-02-27
•
Expires: 2014-07-25
Abstract
Abstract Dynamic optimization of a database access. During execution, based on the actual number of retrieved keys, or on the actual number of fetches (I/O operations) used to retrieve keys, a decision is made between alternative paths for completing the access. The invention features deciding not to retrieve records using the keys retrieved using a particular index if that retrieval could be expected to take longer than retrieving all records. A second index scan is begun during the first index scan, and a decision between alternative paths is made based on the number of keys retrieved during the second scan, or on the number of fetches incurred in the second scan. Scanning of an index is terminated if the number of retrieved keys exceeds a threshold corresponding to the point at which record retrieval using keys is likely to be more costly than full record retrieval. If all index scans are terminated, a full, sequential retrieval of all records is done.
Inventors
- 👤 Gennady Antoshenkov
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 13:09
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2453; G06F16/24534; G06F16/24549; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933
Claims Analysis
Total Claims: 58
Claim 1
Independent Claim
183 words
A method for use in performing a database access to retrieve data records from a computer stored database table having records, fields and two indexes each corresponding to one of the fields, the method being performed in response to a command having two conditions, a first of the conditions selecting data values of a first indexed field, and a second condition selecting data values of a second and distinct one of the indexed fields, the method comprising the steps of, by computer: (a) searching the first index for index entries satisfying the first condition, and retrieving record addresses for the index entries satisfying the first condition; (b) concurrently with step (a), searching the second index for index entries satisfying the second condition, and retrieving record addresses for the index entries satisfying the second condition; and (c) before completion of either of the index searches, based on intermediate counts of record addresses retrieved by steps (a) and (b) or on a number of fetches required to retrieve the records corresponding to the retrieved record addresses, choosing an access path to complete the database access.
Claim 2
Independent Claim
183 words
A method for use in performing a database access to retrieve data records from a computer stored database table having records, fields and two indexes each corresponding to one of the fields, the method being performed in response to a command having two conditions, a first of the conditions selecting data values of a first indexed field, and a second condition selecting data values of a second and distinct one of the indexed fields, the method comprising the steps of, by computer: (a) searching the first index for index entries satisfying the first condition, and retrieving record addresses for the index entries satisfying the first condition; (b) concurrently with step (a), searching the second index for index entries satisfying the second condition, and retrieving record addresses for the index entries satisfying the second condition; and (c) before completion of either of the index searches, based on intermediate counts of record addresses retrieved by steps (a) and (b) or on a number of fetches required to retrieve the records corresponding to the retrieved record addresses, choosing an access path to complete the database access.
Claim 3
Dependent Claim
38 words
The method of claim 1 wherein: the choosing step comprises deciding not to retrieve records using the record addresses retrieved in the first index search if that retrieval could be expected to take longer than retrieving all records.
Claim 4
Dependent Claim
69 words
The method of claim 1 wherein the first index search is an index-only retrieval, and the method further comprises the step of delivering index fields as they are retrieved during the first index search; the second index search is not an index-only retrieval; and the choosing step comprises deciding whether to terminate the first index search and deliver fields using the record addresses retrieved during the second index search.
Claim 5
Dependent Claim
60 words
The method of claim 3 wherein: the decision to terminate the first index search and complete delivery using record addresses retrieved in the second index search is made if the number of record addresses retrieved in the second index search does not exceed a predetermined threshold and the second index search completes prior to completion of the first index search.
Claim 6
Dependent Claim
42 words
The method of claim 3 further comprising the step of: comparing the record addresses retrieved in the second index search to record addresses retrieved in the first index search so that only records not delivered by the first index search are delivered.
Claim 7
Dependent Claim
63 words
The method of claim 1 wherein: records are retrieved and delivered as their record addresses are retrieved by the first index search; the choosing step comprises deciding whether to filter record addresses retrieved in the first index search against record addresses retrieved in the second index search, and the decision is made to do the filtering after the second index search is complete.
Claim 8
Dependent Claim
24 words
The method of claim 6 wherein: the filtering comprises using a bit map built for the record addresses retrieved in the second index search.
Claim 9
Independent Claim
177 words
A method for use in performing a database access to retrieve data records from a computer stored database table having records, each one of the records having a plurality of fields, the method being performed in response to a command having two conditions, the first condition selecting data values of a first indexed one of the fields, and the second condition selecting data values of a second indexed one of the fields, the method comprising the steps of, by computer: (a) searching a first index corresponding to the first indexed one of the fields for index entries satisfying the first condition, and retrieving record addresses for the index enteries satisfying the first condition; and (b) concurrently with step (a), searching a second index corresponding to the second indexed one of the fields for index entries satisfying the second condition, and retrieving record addresses for the index entries satisfying the second condition and, (c) using intermediate or complete results of one of the index searches to modify the execution of or terminate the other of the index searches.
Claim 10
Independent Claim
177 words
A method for use in performing a database access to retrieve data records from a computer stored database table having records, each one of the records having a plurality of fields, the method being performed in response to a command having two conditions, the first condition selecting data values of a first indexed one of the fields, and the second condition selecting data values of a second indexed one of the fields, the method comprising the steps of, by computer: (a) searching a first index corresponding to the first indexed one of the fields for index entries satisfying the first condition, and retrieving record addresses for the index enteries satisfying the first condition; and (b) concurrently with step (a), searching a second index corresponding to the second indexed one of the fields for index entries satisfying the second condition, and retrieving record addresses for the index entries satisfying the second condition and, (c) using intermediate or complete results of one of the index searches to modify the execution of or terminate the other of the index searches.
Claim 11
Dependent Claim
49 words
The method of claim 8 wherein: the choosing step comprises deciding whether, after completion of the first index search, to initiate a third index search or whether instead to abandon any further index searches and instead retrieve records for which record addresses were retrieved in the first index search.
Claim 12
Dependent Claim
47 words
The method of claim 9 wherein: the decision to abandon any further index searches and retrieve all records using record addresses retrieved in the first index search is made if the number of record addresses retrieved in the first index search is less than a predetermined threshold.
Claim 13
Dependent Claim
29 words
The method of claim 8, further comprising the step of: concurrently with the second index search, retrieving records corresponding to the record addresses retrieved during the second index search.
Claim 14
Independent Claim
190 words
A method for use in performing a database access to retrieve data records from a computer stored database table having records, each one of the records having a plurality of fields, the method being performed in response to a command having two conditions, the first condition selecting data values of a first indexed one of the fields, and the second condition selecting data values of a second indexed one of the fields, the method comprising the steps of, by computer: (a) searching a first index corresponding to the first indexed one of the fields for index entries satisfying the first condition, and retrieving record addresses for the index enteries satisfying the first condition; and (b) concurrently with step (a), searching a second index corresponding to the second indexed one of the fields for index entries satisfying the second condition, and retrieving record addresses for the index entries satisfying the second condition; terminating the incomplete second index search; and using the record addresses retrieved by the first index search to retrieve records corresponding to record addresses retrieved by the first index search and not already retrieved during the second index search.
Claim 15
Independent Claim
190 words
A method for use in performing a database access to retrieve data records from a computer stored database table having records, each one of the records having a plurality of fields, the method being performed in response to a command having two conditions, the first condition selecting data values of a first indexed one of the fields, and the second condition selecting data values of a second indexed one of the fields, the method comprising the steps of, by computer: (a) searching a first index corresponding to the first indexed one of the fields for index entries satisfying the first condition, and retrieving record addresses for the index enteries satisfying the first condition; and (b) concurrently with step (a), searching a second index corresponding to the second indexed one of the fields for index entries satisfying the second condition, and retrieving record addresses for the index entries satisfying the second condition; terminating the incomplete second index search; and using the record addresses retrieved by the first index search to retrieve records corresponding to record addresses retrieved by the first index search and not already retrieved during the second index search.
Claim 16
Dependent Claim
44 words
The method of claim 12 further comprising the steps of: building a sorted record address buffer in memory for record addresses retrieved for the first index search; and filtering record addresses retrieved by the second index search against record addresses stored in the buffer.
Claim 17
Dependent Claim
47 words
The method of claim 13 further comprising the step of: comparing the record addresses retrieved in the second index search to record addresses retrieved in the first index search for which fields were delivered so that only fields not delivered in the first index search are delivered.
Claim 18
Dependent Claim
34 words
The method of claim 13 further comprising the step of: building a buffer containing record addresses for which fields are delivered during the first index search, and using that buffer to do the comparing.
Claim 19
Dependent Claim
29 words
The method of claim 13, wherein: the searching and retrieving are performed by a single computer processing unit, the concurrent searching steps being alternately worked by the processing unit.
Claim 20
Dependent Claim
31 words
The method of claim 12 wherein: the records retrieved by the second index search are retrieved without filtering against record addresses retrieved in earlier index searches of the same database access.
Claim 21
Dependent Claim
25 words
The method of claim 12 wherein: the terminating and using steps are initiated if the first index search completes before the second index search completes.
Claim 22
Independent Claim
243 words
A method for use in performing a database access to retrieve data records from a computer stored database table having records, each one of the records having a plurality of fields, the method being performed in response to a command having two conditions, the first condition selecting data values of a first indexed one of the fields, and the second condition selecting data values of a second indexed one of the fields, the method comprising the steps of, by computer: (a) searching a first index corresponding to the first indexed one of the fields for index entries satisfying the first condition, and retrieving record addresses for the index entries satisfying the first condition; (b) concurrently with step (a), searching a second index corresponding to the second indexed one of the fields for index entries satisfying the second condition, and retrieving record addresses for the index entries satisfying the second condition; (c) concurrently with the first index search, building a sorted record address buffer of record addresses retrieved for the first index search; (d) concurrently with the second index search, retrieving records corresponding to the record addresses retrieved during the second index search, without filtering the record addresses retrieved by the second search against record addresses retrieved by the first search before retrieving the records; and (e) if the first index search completes before the second index search completes: terminating the incomplete second index search; and using the record address buffer to retrieve records.
Claim 23
Independent Claim
243 words
A method for use in performing a database access to retrieve data records from a computer stored database table having records, each one of the records having a plurality of fields, the method being performed in response to a command having two conditions, the first condition selecting data values of a first indexed one of the fields, and the second condition selecting data values of a second indexed one of the fields, the method comprising the steps of, by computer: (a) searching a first index corresponding to the first indexed one of the fields for index entries satisfying the first condition, and retrieving record addresses for the index entries satisfying the first condition; (b) concurrently with step (a), searching a second index corresponding to the second indexed one of the fields for index entries satisfying the second condition, and retrieving record addresses for the index entries satisfying the second condition; (c) concurrently with the first index search, building a sorted record address buffer of record addresses retrieved for the first index search; (d) concurrently with the second index search, retrieving records corresponding to the record addresses retrieved during the second index search, without filtering the record addresses retrieved by the second search against record addresses retrieved by the first search before retrieving the records; and (e) if the first index search completes before the second index search completes: terminating the incomplete second index search; and using the record address buffer to retrieve records.
Claim 24
Dependent Claim
46 words
The method of claim 19, further comprising the step of: comparing the record addresses retrieved in the second index search to the contents of the record address buffer to remove from the record address buffer addresses of those records already retrieved by the second index search.
Claim 25
Dependent Claim
29 words
The method of claim 19, wherein: the searching and retrieving are performed by a single computer processing unit, the concurrent searching steps being alternately worked by the processing unit.
Claim 26
Independent Claim
222 words
A method for use in performing a database access to retrieve data records from a computer stored database table having records, each one of the records having a plurality of fields, the method being performed in response to a command having two conditions, the first condition selecting data values of a first indexed one of the fields, and the second condition selecting data values of a second indexed one of the fields, the method comprising the steps of, by computer: (a) searching a first index corresponding to the first indexed one of the fields for index entries satisfying the first condition, and retrieving record addresses for the index enteries satisfying the first condition; and (b) concurrently with step (a), searching a second index corresponding to the second indexed one of the fields for index entries satisfying the second condition, and retrieving record addresses for the index entries satisfying the second condition; (c) during the first index search, building a record address buffer of the record addresses retrieved by the first index search; and (d) before the second index search completes: terminating the first index search; allowing the second index search to continue; and using the record address buffer to filter record addresses retrieved by the second index search before retrieving records corresponding to the record addresses retrieved by the second index search.
Claim 27
Independent Claim
222 words
A method for use in performing a database access to retrieve data records from a computer stored database table having records, each one of the records having a plurality of fields, the method being performed in response to a command having two conditions, the first condition selecting data values of a first indexed one of the fields, and the second condition selecting data values of a second indexed one of the fields, the method comprising the steps of, by computer: (a) searching a first index corresponding to the first indexed one of the fields for index entries satisfying the first condition, and retrieving record addresses for the index enteries satisfying the first condition; and (b) concurrently with step (a), searching a second index corresponding to the second indexed one of the fields for index entries satisfying the second condition, and retrieving record addresses for the index entries satisfying the second condition; (c) during the first index search, building a record address buffer of the record addresses retrieved by the first index search; and (d) before the second index search completes: terminating the first index search; allowing the second index search to continue; and using the record address buffer to filter record addresses retrieved by the second index search before retrieving records corresponding to the record addresses retrieved by the second index search.
Claim 28
Dependent Claim
19 words
The method of claim 22, further comprising the step of: retrieving the records corresponding to the filtered record addresses.
Claim 29
Dependent Claim
26 words
The method of claim 22 further comprising the step of: before commencing the two concurrent index searches, determining that the second index is a sorted index.
Claim 30
Independent Claim
28 words
The method of 22, further comprising the step of: concurrently with the second index search, retrieving records corresponding to the record addresses retrieved during the second index search.
Claim 31
Independent Claim
28 words
The method of 22, further comprising the step of: concurrently with the second index search, retrieving records corresponding to the record addresses retrieved during the second index search.
Claim 32
Dependent Claim
22 words
The method of claim 22, wherein: step (e) is initiated when the first index search completes before the second index search completes.
Claim 33
Dependent Claim
29 words
The method of claim 22, wherein: the searching and retrieving are performed by a single computer processing unit, the concurrent searching steps being alternately worked by the processing unit.
Claim 34
Independent Claim
269 words
A method for use in performing a database access to retrieve data records from a computer stored database table having records, each one of the records having a plurality of fields, the method being performed in response to a command having two conditions, the first condition selecting data values of a first indexed one of the fields, and the second condition selecting data values of a second indexed one of the fields, the method comprising the steps of, by computer: (a) searching a first index corresponding to the first indexed one of the fields for index entries satisfying the first condition, and retrieving record addresses for the index entries satisfying the first condition; and (b) concurrently with step (a), searching a second index corresponding to the second indexed one of the fields for index entries satisfying the second condition, and retrieving record addresses for the index entries satisfying the second condition; before commencing the two concurrent index searches, determining that the second index is a sorted index; during the first index search, storing the record addresses retrieved by the first index search in a record address buffer; concurrently with the second index search, retrieving records corresponding to the record addresses retrieved during the second index search; and before the second index search completes: terminating the first index search; allowing the second index search to continue, but modifying its execution to use the record address buffer to filter record addresses retrieved by the second index search before retrieving records corresponding to the record addresses retrieved by the second index search; and retrieving the records corresponding to the filtered record addresses.
Claim 35
Independent Claim
269 words
A method for use in performing a database access to retrieve data records from a computer stored database table having records, each one of the records having a plurality of fields, the method being performed in response to a command having two conditions, the first condition selecting data values of a first indexed one of the fields, and the second condition selecting data values of a second indexed one of the fields, the method comprising the steps of, by computer: (a) searching a first index corresponding to the first indexed one of the fields for index entries satisfying the first condition, and retrieving record addresses for the index entries satisfying the first condition; and (b) concurrently with step (a), searching a second index corresponding to the second indexed one of the fields for index entries satisfying the second condition, and retrieving record addresses for the index entries satisfying the second condition; before commencing the two concurrent index searches, determining that the second index is a sorted index; during the first index search, storing the record addresses retrieved by the first index search in a record address buffer; concurrently with the second index search, retrieving records corresponding to the record addresses retrieved during the second index search; and before the second index search completes: terminating the first index search; allowing the second index search to continue, but modifying its execution to use the record address buffer to filter record addresses retrieved by the second index search before retrieving records corresponding to the record addresses retrieved by the second index search; and retrieving the records corresponding to the filtered record addresses.
Claim 36
Dependent Claim
29 words
The method of claim 28, wherein: the searching and retrieving are performed by a single computer processing unit, the concurrent searching steps being alternately worked by the processing unit.
Claim 37
Independent Claim
191 words
A method for use in performing a database access to retrieve data records from a computer stored database table having records, each one of the records having a plurality of fields, the method being performed in response to a command having two conditions, the first condition selecting data values of a first indexed one of the fields, and the second condition selecting data values of a second indexed one of the fields, the method comprising the steps of, by computer: (a) searching a first index corresponding to the first indexed one of the fields for index entries satisfying the first condition, and retrieving record addresses for the index enteries satisfying the first condition; and (b) concurrently with step (a), searching a second index corresponding to the second indexed one of the fields for index entries satisfying the second condition, and retrieving record addresses for the index entries satisfying the second condition; if the first index search completes before the second index search completes: terminating the second index search without allowing the second index search to complete; and retrieving the records corresponding to the record addresses retrieved by the first index search.
Claim 38
Independent Claim
191 words
A method for use in performing a database access to retrieve data records from a computer stored database table having records, each one of the records having a plurality of fields, the method being performed in response to a command having two conditions, the first condition selecting data values of a first indexed one of the fields, and the second condition selecting data values of a second indexed one of the fields, the method comprising the steps of, by computer: (a) searching a first index corresponding to the first indexed one of the fields for index entries satisfying the first condition, and retrieving record addresses for the index enteries satisfying the first condition; and (b) concurrently with step (a), searching a second index corresponding to the second indexed one of the fields for index entries satisfying the second condition, and retrieving record addresses for the index entries satisfying the second condition; if the first index search completes before the second index search completes: terminating the second index search without allowing the second index search to complete; and retrieving the records corresponding to the record addresses retrieved by the first index search.
Claim 39
Dependent Claim
23 words
The method of claim 30 wherein: the second index search searches an index containing all fields to be retrieved by the database access.
Claim 40
Independent Claim
29 words
The method of 30, further comprising the step of: during the first index search, building a record address buffer of the record addresses retrieved by the first index search.
Claim 41
Independent Claim
29 words
The method of 30, further comprising the step of: during the first index search, building a record address buffer of the record addresses retrieved by the first index search.
Claim 42
Dependent Claim
41 words
The method of claim 32, further comprising the step of: before retrieving the records corresponding to the record addresses retrieved by the first index search, filtering the record addresses by matching against the record addresses retrieved by the second index search.
Claim 43
Dependent Claim
29 words
The method of claim 30, wherein: the searching and retrieving are performed by a single computer processing unit, the concurrent searching steps being alternately worked by the processing unit.
Claim 44
Independent Claim
264 words
A method for use in performing a database access to retrieve data records from a computer stored database table having records, each one of the records having a plurality of fields, the method being performed in response to a command having two conditions, the first condition selecting data values of a first indexed one of the fields, and the second condition selecting data values of a second indexed one of the fields, the method comprising the steps of, by computer: (a) searching a first index corresponding to the first indexed one of the fields for index entries satisfying the first condition, and retrieving record addresses for the index enteries satisfying the first condition; and (b) concurrently with step (a), searching a second index corresponding to the second indexed one of the fields for index entries satisfying the second condition, and retrieving record addresses for the index entries satisfying the second condition; during the first index search, storing the record addresses retrieved by the first index search in a storage buffer; if the second index search, being a search of an index containing all fields to be retrieved by the database access, completes before the first index search, terminating the first index search without allowing the first index search to complete; and if the first index search completes before the second index search completes: terminating the second index search without allowing the second index search to complete; retrieving the records corresponding to the record addresses stored in the record address buffer; and applying the condition of the second search to the retrieved records before delivery.
Claim 45
Independent Claim
264 words
A method for use in performing a database access to retrieve data records from a computer stored database table having records, each one of the records having a plurality of fields, the method being performed in response to a command having two conditions, the first condition selecting data values of a first indexed one of the fields, and the second condition selecting data values of a second indexed one of the fields, the method comprising the steps of, by computer: (a) searching a first index corresponding to the first indexed one of the fields for index entries satisfying the first condition, and retrieving record addresses for the index enteries satisfying the first condition; and (b) concurrently with step (a), searching a second index corresponding to the second indexed one of the fields for index entries satisfying the second condition, and retrieving record addresses for the index entries satisfying the second condition; during the first index search, storing the record addresses retrieved by the first index search in a storage buffer; if the second index search, being a search of an index containing all fields to be retrieved by the database access, completes before the first index search, terminating the first index search without allowing the first index search to complete; and if the first index search completes before the second index search completes: terminating the second index search without allowing the second index search to complete; retrieving the records corresponding to the record addresses stored in the record address buffer; and applying the condition of the second search to the retrieved records before delivery.
Claim 46
Dependent Claim
29 words
The method of claim 35, wherein: the searching and retrieving are performed by a single computer processing unit, the concurrent searching steps being alternately worked by the processing unit.
Claim 47
Independent Claim
191 words
A method for use in performing a database access to retrieve data records from a computer stored database table having records, each one of the records having a plurality of fields, the method being performed in response to a command having two conditions, the first condition selecting data values of a first indexed one of the fields, and the second condition selecting data values of a second indexed one of the fields, the method comprising the steps of, by computer: (a) searching a first index corresponding to the first indexed one of the fields for index entries satisfying the first condition, and retrieving record addresses for the index enteries satisfying the first condition; and (b) concurrently with step (a), searching a second index corresponding to the second indexed one of the fields for index entries satisfying the second condition, and retrieving record addresses for the index entries satisfying the second condition; and wherein: a control for apportioning search effort between the first and second index searches ensures that a rate at which the first index is searched is on average greater than a rate at which the second index is searched.
Claim 48
Independent Claim
191 words
A method for use in performing a database access to retrieve data records from a computer stored database table having records, each one of the records having a plurality of fields, the method being performed in response to a command having two conditions, the first condition selecting data values of a first indexed one of the fields, and the second condition selecting data values of a second indexed one of the fields, the method comprising the steps of, by computer: (a) searching a first index corresponding to the first indexed one of the fields for index entries satisfying the first condition, and retrieving record addresses for the index enteries satisfying the first condition; and (b) concurrently with step (a), searching a second index corresponding to the second indexed one of the fields for index entries satisfying the second condition, and retrieving record addresses for the index entries satisfying the second condition; and wherein: a control for apportioning search effort between the first and second index searches ensures that a rate at which the first index is searched is on average greater than a rate at which the second index is searched.
Claim 49
Dependent Claim
39 words
The method of claim 37, wherein: the apportioning is accomplished by iteratively repeating the steps of: searching a first predetermined number of entries of the first index; and searching a second predetermined number of entries of the second index.
Claim 50
Independent Claim
226 words
A method for use in performing a database access to retrieve data records from a computer stored database table having records, each one of the records having a plurality of fields, the method being performed in response to a command having two conditions, the first condition selecting data values of a first indexed one of the fields, and the second condition selecting data values of a second indexed one of the fields, the method comprising the steps of, by computer: (a) searching a first index corresponding to the first indexed one of the fields for index entries satisfying the first condition, and retrieving record addresses for the index enteries satisfying the first condition; and (b) concurrently with step (a), searching a second index corresponding to the second indexed one of the fields for index entries satisfying the second condition, and retrieving record addresses for the index entries satisfying the second condition further comprising the step of; filtering lists of record addresses retrieved by different index searches to produce a final list of record addresses appearing on all lists; and wherein: the step of filtering lists of record addresses is carried out by (1) building in memory a sorted record address buffer of record addresses retrieved from the first index and (2) comparing record addresses retrieved from the second index to record addresses stored in the buffer.
Claim 51
Independent Claim
226 words
A method for use in performing a database access to retrieve data records from a computer stored database table having records, each one of the records having a plurality of fields, the method being performed in response to a command having two conditions, the first condition selecting data values of a first indexed one of the fields, and the second condition selecting data values of a second indexed one of the fields, the method comprising the steps of, by computer: (a) searching a first index corresponding to the first indexed one of the fields for index entries satisfying the first condition, and retrieving record addresses for the index enteries satisfying the first condition; and (b) concurrently with step (a), searching a second index corresponding to the second indexed one of the fields for index entries satisfying the second condition, and retrieving record addresses for the index entries satisfying the second condition further comprising the step of; filtering lists of record addresses retrieved by different index searches to produce a final list of record addresses appearing on all lists; and wherein: the step of filtering lists of record addresses is carried out by (1) building in memory a sorted record address buffer of record addresses retrieved from the first index and (2) comparing record addresses retrieved from the second index to record addresses stored in the buffer.
Claim 52
Independent Claim
190 words
A method for use in performing a database access to retrieve data records from a computer stored database table having records, each one of the records having a plurality of fields, the method being performed in response to a command having two conditions, the first condition selecting data values of a first indexed one of the fields, and the second condition selecting data values of a second indexed one of the fields, the method comprising the steps of, by computer: (a) searching a first index corresponding to the first indexed one of the fields for index entries satisfying the first condition, and retrieving record addresses for the index enteries satisfying the first condition; and (b) concurrently with step (a), searching a second index corresponding to the second indexed one of the fields for index entries satisfying the second condition, and retrieving record addresses for the index entries satisfying the second condition; and wherein: the first and second index searches have been preceded by an earlier index search for which a number of record addresses retrieved exceeded a threshold value at which the search strategy of the earlier search was modified.
Claim 53
Independent Claim
190 words
A method for use in performing a database access to retrieve data records from a computer stored database table having records, each one of the records having a plurality of fields, the method being performed in response to a command having two conditions, the first condition selecting data values of a first indexed one of the fields, and the second condition selecting data values of a second indexed one of the fields, the method comprising the steps of, by computer: (a) searching a first index corresponding to the first indexed one of the fields for index entries satisfying the first condition, and retrieving record addresses for the index enteries satisfying the first condition; and (b) concurrently with step (a), searching a second index corresponding to the second indexed one of the fields for index entries satisfying the second condition, and retrieving record addresses for the index entries satisfying the second condition; and wherein: the first and second index searches have been preceded by an earlier index search for which a number of record addresses retrieved exceeded a threshold value at which the search strategy of the earlier search was modified.
Claim 54
Dependent Claim
31 words
The method of claim 40 wherein: the records for which record addresses are retrieved in the first index search are retrieved without filtering with record addresses retrieved in earlier index searches.
Claim 55
Independent Claim
199 words
A method for use in performing a database access to retrieve data records from a computer stored database table having records, each one of the records having a plurality of fields, the method being performed in response to a command having two conditions, the first condition selecting data values of a first indexed one of the fields, and the second condition selecting data values of a second indexed one of the fields, the method comprising the steps of, by computer: (a) searching a first index corresponding to the first indexed one of the fields for index entries satisfying the first condition, and retrieving record addresses for the index enteries satisfying the first condition; and (b) concurrently with step (a), searching a second index corresponding to the second indexed one of the fields for index entries satisfying the second condition, and retrieving record addresses for the index entries satisfying the second condition; and deciding to terminate one of the index searches if a number of record addresses retrieved by the index search to be terminated exceeds a fetch limit, the fetch limit being less than a number of fetches required to retrieve all of the records in the database table.
Claim 56
Independent Claim
199 words
A method for use in performing a database access to retrieve data records from a computer stored database table having records, each one of the records having a plurality of fields, the method being performed in response to a command having two conditions, the first condition selecting data values of a first indexed one of the fields, and the second condition selecting data values of a second indexed one of the fields, the method comprising the steps of, by computer: (a) searching a first index corresponding to the first indexed one of the fields for index entries satisfying the first condition, and retrieving record addresses for the index enteries satisfying the first condition; and (b) concurrently with step (a), searching a second index corresponding to the second indexed one of the fields for index entries satisfying the second condition, and retrieving record addresses for the index entries satisfying the second condition; and deciding to terminate one of the index searches if a number of record addresses retrieved by the index search to be terminated exceeds a fetch limit, the fetch limit being less than a number of fetches required to retrieve all of the records in the database table.
Claim 57
Dependent Claim
33 words
The method of claim 42 wherein: the fetch limit is approximately equal to or less than one-half of the number of fetches required to retrieve all of the records in the database table.
Claim 58
Dependent Claim
61 words
The method of claim 42 wherein: the deciding step comprises the further decision of whether to terminate the second index search and initiate or continue a subsequent index search, and the decision is affirmative if the actual number of fetches required to retrieve records addressed in the second index search exceeds a second fetch limit smaller than the first fetch limit.
References Cited (Backward Citations)
US3964029A
Cited
US4468728A
Cited
US4451901A
Cited
US5091852A
Cited
US5089985A
Cited
US5043872A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-02-26 | 1999-08-28 | 2000-02-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-02-26 | 2003-08-28 | 2004-02-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-02-26 | 2007-08-28 | 2008-02-27 | $7700.00 | Window Closed / Lapsed |