US 5,710,915 AGranted

Method for accelerating access to a database clustered partitioning

AssigneeElectronic Data Systems Corporation

InventorJames David McElhiney

Life of this patent

Estimating the term…

Loading patent…

Abstract

A database organization system that separates fields used for record selection into a search table, leaving fields used solely for retrieval in a separate detail table. The system constructs a bit-interleaved key field within the search table, causing records with similar field values to cluster. The system further partitions the tables into multiple pairs of sub-tables as size increases, and builds a statistics table with information describing each partitioned sub-table. Each sub-table is searched separately and the results merged. The bits of the bit-interleaved key are ordered by likelihood of data query, and the partitioning is performed using the value of each bit. The system keeps statistics for each partition, and allows parallel searching of each partition. Query speed is enhanced by culling sub-tables from the search process, by reading only the search table data, and by eliminating record-level tests on tables completely within the desired result set.

Claims19

Dependent claims

A method for storing and accessing records in a database table, the method comprising the steps of:

(a) selecting at least two search fields from the input data table;
(b) defining a bit-interleaved key field comprising
(b1) for each field selected in step (a), determining a percentage of queries that will use the field,
(b2) from the fields selected in step (a), selecting a field having the highest percentage of queries as defined in step (b),
(b3) selecting a most significant bit from the field selected in step (b2),
(b4) assigning the bit selected in step (b3) as a bit of the bit-interleave key field,
(b5) reducing the percentage of queries for the field selected in step (b2) by a predetermined amount,
(b6) repeating steps (b2) through (b5) until the bit-interleave key field has all bits assigned;
(c) attaching a unique record identifier to each record in the input data table;
(d) defining a search table within the database comprising
(d1) building a key field as defined in step (b) for each record in the input data table, and
(d2) combining the record identifier defined in step (c), the key field as built in step (d1), and the fields selected in step (a), for each record in the input data table and writing this combination to the search table;
(e) defining a detail table within the database comprising
(e1) combining the record identifier defined in step (c) and the remaining fields from each record in the input data table, and writing this combination to the detail table;
and
(f) receiving a search request comprising a set of value constraints and retrieving a set of all records satisfying the value constraints from the search table and detail table comprising
(f1) determining whether at least one record in the search table may satisfy the set of value constraints,
(f2) when step (f1) determines that at least one record may satisfy the set of value constraints, comparing the values of the fields in each record in the search table to the set of value constraints, and
(f3) for each record selected in step (f2) using the record identifier to retrieve a corresponding record from the detail table.

16 more elements

A method for storing and accessing records in a database table, the method comprising the steps of:

(a) selecting at least two search fields from the input data table;
(b) defining a bit-interleaved key field comprising
(b1) for each field selected in step (a), determining a percentage of queries that will use the field,
(b2) from the fields selected in step (a), selecting a field having the highest percentage of queries as defined in step (b),
(b3) selecting a most significant bit from the field selected in step (C2),
(b4) assigning the bit selected in step (b3) as a least significant bit of the bit-interleave key field,
(b5) reducing the percentage of queries for the field selected in step (b2) by half,
(b6) repeating steps (b2) through (b5) until the bit-interleave key field has all bits assigned;
(c) attaching a unique record identifier to each record in the input data table;
(d) defining a search table within the database comprising
(d1) building a key field as defined in step (b) for each record in the input data table, and
(d2) combining the record identifier defined in step (c), the key field as built in step (d1), and the fields selected in step (a), for each record in the input data table and writing this combination to the search table;
(e) defining a detail table within the database comprising
(e1) combining the record identifier defined in step (c) and the remaining fields from each record in the input data table, and writing this combination to the detail table;
(f) receiving a search request comprising a set of value constraints and retrieving a set of all records satisfying the value constraints from the search table and detail table comprising
(f1) determining whether at least one record in the search table may satisfy the set of value constraints,
(f2) when step (f1) determines that at least one record may satisfy the set of value constraints, comparing the values of the fields in each record in the search table to the set of value constraints, and
(f3) for each record selected in step (f2) using the record identifier to retrieve a corresponding record from the detail table;
and
(g) receiving a search request comprising a scalar aggregate function of values in the search table and detail data table comprising
(g1) determining whether all records in the search table are known to match the scalar aggregate selection criteria,
(g2) when all records are known to match the scalar aggregate selection criteria, returning a predetermined scalar aggregate value for the records, and
(g3) when at least one record in the search table may not match the scalar aggregate selection criteria examining each record in the detail table to determine the value of the scalar aggregate function.

20 more elements

Dependencies are inferred from the claim text.