US 5,560,007 AGranted

B-tree key-range bit map index optimization of 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.

Claims19

Dependent claims

In a system for processing data records, each record including at least one field for storing information, the system including means for logically ordering the records by an index, said index comprising a tree structure storing key values derived from values stored by said at least one field of each record, said index including a plurality of leaf nodes, each leaf node comprising a particular key value together with a record identifier for indicating a particular record which stores said particular key value, said leaf nodes being sorted by the key values stored thereat according to a user-specified sort order, said leaf nodes being linked via pointers, a method for identifying from said index records of interest to a user comprising:

(a) receiving a query expression specifying at least one condition for selecting particular records of interest to the user;
(b) with the index that logically orders the records according to key values, locating first and second leaf nodes of said plurality of leaf nodes which store a bottom and a top key value of the index, respectively, which satisfies said at least one condition, said bottom key value identifying a first record of interest and said top key value identifying a second record of interest, said method locating said first and second leaf nodes before attempting to locate other leaf nodes storing key values which satisfy said at least one condition;
and
(c) after locating said first and second leaf nodes, identifying others of said records of interest without reading key values stored at leaf nodes by traversing pointers of leaf nodes which lie between said first and second leaf nodes, for locating all nodes storing key values of the index which logically lie between said bottom and top key values, wherein each located key value occurs at a leaf node storing a record identifier which identifies a record satisfying said at least one condition.

1 more element

An information retrieval system comprising:

(a) a computer having a processor and a memory;
(b) means for storing information in the memory as a plurality of information records, each record including at least one field for storing values;
(c) means for logically ordering the plurality of information records by an index comprising a tree structure, said index including a plurality of leaf nodes each leaf node comprising a particular key value together with a record identifier for indicating a particular record which stores said particular key value said leaf nodes being sorted by the key value stored thereat according to a user-specified sort order, each leaf node being linked to any neighboring leaf nodes via pointers;
(d) means for selecting records of interest by specifying a filter condition;
and
(e) means for determining the records of interest, said means including:
(i) means for identifying a first record of interest by locating a first leaf node from the index which stores a lowest value of key values which satisfies said filter condition,
(ii) means for identifying a last record of interest by locating a second leaf node from the index which stores a highest value of key values which satisfies said filter condition, and
(iii) means for identifying others of said records of interest by determining, based on said pointers, which nodes lie between said first and said second leaf nodes, thereby locating from the index all leaf nodes storing key values which are greater than said lowest value and less than said highest value, wherein each located leaf node identifies a record satisfying said filter condition.

6 more elements

Dependencies are inferred from the claim text.

Facts

Application: 08/544,679Filed 18 Oct 1995 · continuation
Priority: 30 Jun 1993
Granted: 24 Sep 1996
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