US 5,666,528 AGranted

System and methods for optimizing database queries

AssigneeBorland International, Inc.

InventorLam H. Thai

Life of this patent

Estimating the term…

Loading patent…

Abstract

System and methods are provided for optimizing the access of information, particularly in response to ad hoc queries or filters. The system of the present invention includes a computer having a memory and a processor, a database for storing information in the memory as field values in a record, an indexing component for referencing a plurality of records by key values of the field(s), an input device for selecting desired records by entering a filter (query) condition corresponding to values stored in the field(s), and an optimization module for providing rapid access to the desired records. The optimization module employs one or more existing indices for optimizing data access, including using ones which do not directly support the filter expression. In instances where no indices are available, the optimization module may employ a "learned" optimization method of the invention for on-the-fly learning of records which meet the filter condition.

Claims10

Dependent claims

In a system for storing information as a plurality of data records on a storage device and for reading into a memory data records which are of interest to a user, a method for providing access to particular data records which is of interest to the user, the method comprising:

(a) specifying at least one criterion for filtering out records which are not of interest to the user, wherein said at least one criterion includes a condition such that records satisfying said at least one criterion cannot be determined by the system from an existing index of the data records;
(b) learning on-the-fly which records satisfy said at least one criterion as each record is first read from said storage device by:
(i) providing a bitmask comprising a plurality of bits, each bit corresponding to a single record of the data records, and each bit having a first state for indicating that a record satisfies said at least one criterion and a second state for indicating that a record does not satisfy said at least one criterion;
(ii) setting all of the bits to said first state, wherein said system initially assumes that all records satisfy said at least one criterion so that none of the records are filtered out which have yet to be read into said memory;
(iii) receiving a request for a desired range of records from the data records;
(iv) reading each record of the desired range into said memory whose bit is set to the first state and applying said at least one criterion as each record is read for determining whether the record being read actually satisfies said at least one criterion;
(v) for each record read in step (iv) which does not satisfy said at least one criterion, setting its corresponding bit to the second state for filtering out the record;
and
(c) providing access to each record of the desired range which has not been filtered out as said each record of the desired range currently resides in said memory.

6 more elements

An information retrieval system comprising:

a computer having a processor, a memory, and a storage device;
means for storing information as a plurality of data records on said storage device;
query means for receiving user input specifying a filter condition, for indicating particular information in said data records which is of interest to a user;
means for maintaining a bitmask comprising a plurality of bits, each bit for indicating that a particular data record satisfies the filter condition;
means for setting all bits in said bitmask to indicate that all data records initially satisfy the filter condition;
means for receiving user input requesting access to a first range of records from said plurality of data records and for retrieving from said storage device each record in said first range of records;
means for dynamically adjusting the bitmask as each record of the first range is retrieved, by comparing each data record of the first range retrieved from said storage device against the filter condition and resetting the bit which corresponds to any data record retrieved for the first range which does not satisfy the filter condition;
means for receiving user input requesting access to a second range of records from said plurality of data records and for retrieving from said storage device each record in said second range of records;
means for dynamically adjusting the bitmask as each record of the second range is retrieved, by comparing each data record of the second range retrieved from said storage device against the filter condition and resetting the bit which corresponds to any data record retrieved for the second range which does not satisfy the filter condition;
and
means for receiving user input again requesting access to said first range of records from said plurality of data records and for retrieving from said storage device only those records in said first range of records whose corresponding bits have not been reset.

8 more elements

Dependencies are inferred from the claim text.

Facts

Application: 08/664,961Filed 13 Jun 1996 · continuation
Priority: 30 Jun 1993
Granted: 9 Sep 1997
Term ends: Not estimatedThe source records don’t support an estimate.

Classification8 codes

G06F 16/24557
Unary operations; Data partitioning operations: efficient disk access during query execution
G06F 16/2237
Indexing structures: vectors, bitmaps or matrices
G06F 16/24561
Of query operations: intermediate data storage techniques for performance improvement
Y10S 707/99932
Database or file accessing: access augmentation or optimizing