Method for accelerating access to a database clustered partitioning

• US 5,710,915 A
• Filed: 12/21/1995
• Issued: 01/20/1998
• Est. Priority Date: 12/21/1995
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Electronic Data Systems Corporation (Perspecta, Inc.)
• Inventors: McElhiney, James David
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Alam, Hosain T.
• Application Number:
  US08/576,102
• Time in Patent Office: 761 Days
• Field of Search: 395/602-606
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning
• CPC Class Codes: G06Q 40/00 Finance; Insurance; Tax strategies; Processing of corporate or income taxes
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99953 Recoverability

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.

Claims

1. 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.

2. The method of claim 1 further comprising the step of:

(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.

3. The method of claim 1 wherein step (b4) further comprises defining the bit-interleave key field in most significant to least significant order.

4. The method of claim 1 wherein step (b5) further comprises reducing the percentage of queries for the field by half.

5. The method of claim 1 wherein fewer than all fields selected in step (a) are defined within the bit-interleaved key field in step (b).

6. The method of claim 1 wherein step (d) further comprises the following steps (d3) and (d4), and wherein step (f) further comprises the following steps (f1a) and (f2a):

(d3) when the number of search records exceeds a first predetermined amount, splitting the search table into two sub-tables;

(d4) when a sub-table as created in step (d3) exceeds the predetermined amount, splitting the sub-table into two additional sub-tables;

(f1a) when the search table has been split into sub-tables, determining whether at least one record from each search sub-table may satisfy the set of value constraints; and

(f2a) when the search table has been split into multiple search sub-tables, comparing the values of the fields in each record in each search sub-table to the set of value constraints, for only those search sub-tables determined to be candidates in step (f1a).

7. The method of claim 6 wherein splitting the search table or a sub-table comprises selecting records for a first sub-table having a first value in a most significant bit of the bit-interleaved key that varies within the sub-table, and selecting records for a second sub-table having a second value in the most significant bit of the bit-interleave key that varies within the sub-table.

8. The method of claim 6 wherein step (d) further comprises the following step (d5), and wherein step (f) further comprises the following step (f4):

(d5) defining a statistics record for each sub-table, comprising the steps of

(d5a) storing a minimum value for each field of the records of the search sub-table,

(d5b) storing a maximum value for each field of the records of the search sub-table,

(d5c) storing a minimum value for the key field within each record in the search sub-table,

(d5d) storing the maximum value for the key field within each record in the search sub-table,

(d5e) storing a sum value of each summable field of the search sub-table, and

(d5f) storing a count of records in the search sub-table; and

(f4) when data for a request comprises statistics, retuning the statistics from the statistics record.

9. The method of claim 6 wherein step (f1) further comprises:

(f1a) performing the search of at least two sub-tables in parallel processes.

10. The method of claim 9 wherein the parallel processes are performed in separate interconnected processors.

11. The method of claim 1 wherein step (e) further comprises the steps of:

(e2) when the number of detail records exceeds a second predetermined amount, splitting the search table into two detail sub-tables; and

(e3) when one of the detail sub-tables created in step (d3) exceeds the predetermined amount, splitting the one detail sub-table into two additional detail sub-tables.

12. 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.

13. The method of claim 12 wherein fewer than all fields selected in step (a) are defined within the bit-interleaved key field in step (b).

14. The method of claim 12 wherein step (d) further comprises the following steps (d3) and (d4), and wherein step (f) further comprises the following steps (f1a) and (f2a):

(d3) when the number of search records exceeds a first predetermined amount, splitting the search table into two sub-tables;

(d4) when a sub-table as created in step (d3) exceeds the predetermined amount, splitting the sub-table into two additional sub-tables;

(f1a) when the search table has been split into sub-tables, determining whether at least one record from each search sub-table may satisfy the set of value constraints; and

(f2a) when the search table has been split into multiple search sub-tables, comparing the values of the fields in each record in each search sub-table to the set of value constraints, for only those search sub-tables determined to be candidates in step (f1a).

15. The method of claim 14 wherein splitting the search table or a sub-table comprises selecting records for a first sub-table having a first value in a most significant bit of the bit-interleaved key that varies within the sub-table, and selecting records for a second sub-table having a second value in the most significant bit of the bit-interleave key that varies within the sub-table.

16. The method of claim 14 wherein step (d) further comprises the following step (d5), and wherein step (f) further comprises the following step (f4):

(d5) defining a statistics record for each sub-table, comprising the steps of

(d5a) storing a minimum value for each field of the records of the search sub-table,

(d5b) storing a maximum value for each field of the records of the search sub-table,

(d5c) storing a minimum value for the key field within each record in the search sub-table,

(d5d) storing the maximum value for the key field within each record in the search sub-table,

(d5e) storing a sum value of each summable field of the search sub-table, and

(d5f) storing a count of records in the search sub-table; and

(f4) when data for a request comprises statistics, returning the statistics from the statistics record.

17. The method of claim 14 wherein step (f1) further comprises:

(f1a) performing the search of at least two sub-tables in parallel processes.

18. The method of claim 17 wherein the parallel processes are performed in separate interconnected processors.

19. The method of claim 12 wherein step (e) further comprises the steps of:

(e2) when the number of detail records exceeds a second predetermined amount, splitting the search table into two detail sub-tables; and

(e3) when one of the detail sub-tables created in step (d3) exceeds the predetermined amount, splitting the one detail sub-table into two additional detail sub-tables.