US 5,852,821 A · High-speed data base query method and apparatus

Abstract

A server performing an indexing method of data management to create and maintain indexes more efficiently than existing indexing approaches is described. The server is disposed between an application program and a DBMS and is coupled to a data base located within the DBMS. The data base has an ordered set of data values stored in memory. Each data value has a bit pattern and an identifier associated therewith. The server creates a plurality of bit vectors such that the number of bit vectors created equals the longest length bit pattern for the values. The server accesses one of the values stored in the data base. Each bit of the bit pattern for the value is then assigned by the server to a unique position in successive bit vectors. The bits are assigned to identical unique positions in each of the successive bit vectors. The server repeats the above-described accessing and assigning steps for each remaining value of the set to form an index of bit vectors for the values. Methods are provided for improving the performance of database queries when using bit-vector or HighNonGroup (HNG) indexes. Such queries include, for instance, aggregate operations specified in an SQL statement, such as SUM, MAX, MIN, and AVG operations. Specific methods described include optimizing "range" comparisons by reducing bit operations, optimization of MAX and MIN operations, optimization of SUM and AVG operations, implementation of a "Datepart" index, and execution of SUBSTRING predicates in an HNG index.

Claims30

Dependent claims

In a database system for representing information in database tables and for retrieving information from database tables in response to database queries, each database table comprising data records storing information categorized into one or more database fields, each database field storing information in a particular data type, a method for optimizing database range queries, the method comprising:

(a) receiving a database range query having a query condition which specifies selection of data records satisfying a particular range;
(b) if the query condition specifies selection of values of a particular database field of the data records which are less than or equal to a maximum key value, performing substeps of:
(i) if the maximum key value represents the maximum value possible for the particular data type of the particular database field, creating a result set indicating that all data records have values for the particular database field which satisfy the query condition, otherwise
(ii) incrementing the maximum key value by one and creating a result set indicating those data records having values for the particular database field which are less than the incremented maximum key value;
and
(c) if the query condition specifies selection of values of a particular database field of the data records which are greater than or equal to a minimum key value, performing substeps of:
(i) if the minimum key value represents the minimum value possible for the particular data type of the particular database field, creating a result set indicating that all data records have values for the particular database field which satisfy the query condition, otherwise
(ii) decrementing the minimum key value by one and creating a result set indicating those data records having values for the particular database field which are greater than the decremented minimum key value.

5 more elements

In a database system for representing information in database tables and for retrieving information from database tables in response to database queries, each database table comprising data records storing information categorized into one or more data fields, each data field storing information in a particular data type, a method for optimizing database range queries, the method comprising:

(a) receiving a database range query having a query condition which specifies that values of a particular data field must be less than or equal to a maximum key value and must be greater than or equal to a minimum key value;
(b) creating a first result set by performing substeps of:
(i) if the minimum key value represents the minimum value possible for the particular data type of the particular data field, creating a first result set indicating that all data records have values for the particular data field which are greater than or equal to the minimum key value, otherwise
(ii) decrementing the minimum key value by one and creating a first result set indicating those data records having values for the particular data field which are greater than the decremented minimum key value, said first result set being created by only examining those bits of the values of the particular data field up to the largest 1 bit of the maximum key value plus 1;
(c) creating a second result set by performing substeps of:
(i) if the maximum key value represents the maximum value possible for the particular data type of the particular data field, creating a second result set indicating that all data records have values for the particular data field which satisfy the query condition, otherwise
(ii) incrementing the maximum key value by one and creating a second result set indicating those data records having values for the particular data field which are less than the incremented maximum key value;
and
(d) performing a logical AND operation between said first and second result sets for creating a final result set indicating those data records having values of the data field which are less than or equal to the maximum key value and greater than or equal to the minimum key value.

6 more elements

In a database system for representing information in database tables and for retrieving information from database tables in response to database queries, each database table comprising data records storing information categorized into one or more data fields, a method for optimizing database MAX queries performed on a particular data field having a bit-vector index, said bit-vector index comprising a plurality of bit vectors each of which comprises a bit slice through a corresponding bit position of the data field, the method comprising:

(a) receiving a query requiring determination of a maximum value for the data field;
(b) initializing a found set for specifying at least one data record having the maximum value;
(c) starting from a highest order bit vector, successively scanning each bit vector by:
(i) creating a temporary found set for the bit vector for specifying those data records having 1s for the corresponding bit position of the data field, thereby eliminating from the temporary found set all data records having 0s for the corresponding bit position of the data field,
(ii) if the temporary found set specifies no records, proceeding to step (d),
(iii) if the temporary found set specifies at least one record, combining the temporary found set with the previously-initialized found set and repeating step (c) for any remaining bit vectors;
and
(d) determining the maximum value from at least one record which remains in the found set.

5 more elements

In a database system for representing information in database tables and for retrieving information from database tables in response to database queries, each database table comprising data records storing information categorized into one or more data fields, a method for optimizing database MIN queries performed on a particular data field having a bit-vector index, said bit-vector index comprising a plurality of bit vectors each of which comprises a bit slice through a corresponding bit position of the data field, the method comprising:

(a) receiving a query requiring determination of a minimum value for the data field;
(b) initializing a found set for specifying at least one data record having the minimum value;
(c) starting from a highest order bit vector, successively scanning each bit vector by:
(i) creating a temporary found set for the bit vector for specifying those data records having 0s for the corresponding bit position of the data field, thereby eliminating from the temporary found set all data records having 1s for the corresponding bit position of the data field,
(ii) if the temporary found set specifies no records, proceeding to step
(iii) if the temporary found set specifies at least one record, combining the temporary found set with the previously-initialized found set and repeating step (c) for any remaining bit vectors;
and
(d) determining the minimum value from at least one record which remains in the found set.

5 more elements

Dependencies are inferred from the claim text.

High-speed data base query method and apparatus

Life of this patent

High-speed data base query method and apparatus

Life of this patent

Abstract

Claims30