Multi-level partitioned database system

• US 6,845,375 B1
• Filed: 10/20/2001
• Issued: 01/18/2005
• Est. Priority Date: 10/20/2001
• Status: Active Grant

• Current Assignee: Teradata US, Inc. (Teradata Corporation)
• Original Assignee: NCR Corporation
• Inventors: Sinclair, Paul Laurence
• Primary Examiner(s): KINDRED, ALFORD W
• Application Number:
  US09/986,229
• Time in Patent Office: 1,186 Days
• Field of Search: 707 1- 2, 707100-101, 707/200, 707/205, 709/215, 711/153
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2282 Tablespace storage structures; Management thereof
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A database system with multi-level partitioning is disclosed. The system includes a plurality of storage facilities with each storage facility storing data that represents rows of database tables. In each storage facility table rows corresponding to a specific table are logically ordered according to a row identifier, also called the row ID. The row ID includes a first value that is based on one or more columns of the table. The row ID also includes a second value that is based on one or more columns of the table. The row ID also includes a third value. The first value is calculated based on a single-level function. The single-level function is a combination of a plurality of functions. The single-level function produces different values for two rows when any of the plurality of functions produces different values for the two rows. The first value of the row ID is predominate in determining the order of the rows in the storage facilities. The second value determines the order of those rows with identical first values. If any rows have identical first and second values, the third value determines the order of those rows.

Claims

1. A multi-level partitioned database system, comprising:

a plurality of storage facilities, each storage facility including data representing a plurality of table rows;

wherein table rows in each storage facility that correspond to a specific table are logically ordered according to a row identifier (row ID);

the row ID comprises a first value based on one or more columns of the table, a second value based on one or more columns of the table, and a third value;

the first value is calculated based on a single-level function that results from the combination of a plurality of functions, each function of the plurality of functions based one or more columns of the table, the single-level function producing different values for two rows when any of the plurality of functions produces different values for the two rows; and

the first value of the row ID is predominate in determining the order of the rows in the storage facilities, the second value determines the order of those rows with identical first values, and the third value determines the order of rows with identical first and second values.

2. The partitioned database system of claim 1, wherein:

the plurality of functions includes at least one function based on ranges of values in a column.

3. The partitioned database system of claim 2, wherein the ranges of values in a column are ranges of dates.

4. The partitioned database system of claim 1, wherein the second value is a value in a specified column.

5. The partitioned database system of claim 1, wherein the second value is the result of applying a hash function to a value in a specified column.

6. The partitioned database system of claim 1, wherein the row ID is 80 bits.

7. The partitioned database system of claim 1, wherein the first value is specified by 16 bits.

8. The partitioned database system of claim 1, wherein table rows are distributed among the plurality of storage facilities based on the second value.

9. The partitioned database system of claim 1, wherein the third value is a uniqueness value that differentiates rows having equal first and second values.

10. The partitioned database system of claim 1, wherein the single-level function is calculated in accordance with the formula:

P=( . . . ((P₁−

mn₁)*(mx₂−

mn₂+1)+P₂−

mn₂)*(mx₃−

mn₃+1)+ . . . +P<sub>(n−

1)</sub>−

mn<sub>(n−

1)</sub>)* (mx_n−

mn_n+1)+P_n−

mn_n)

where P is the single-level function, P_i is an i^th function of the plurality of functions, and mn_i and mx_i are a minimum and a maximum resulting values of P_i.

11. A method for building a table in a multi-level partitioned database system, comprising the steps of:

defining columns in the table;

selecting a plurality of functions, each function of the plurality of functions based on one or more columns of the table;

selecting a second group of one or more columns;

selecting a second function based on the third group of columns;

creating rows of the table;

generating a single-level function that results from the combination of the plurality of functions;

storing rows of the table in a logical order corresponding to the result of the single-level function for each row; and

if more than one row of the table has an identical result of the single-level function, storing those rows in a logical order corresponding to the result of the second function; and

if more than one row of the table has identical results of the single-level and second functions, storing those rows in a logical order corresponding to a third value.

12. The method of claim 11, wherein the third value is an assigned uniqueness number for each row.

13. A method for building a table in a multi-level partitioned database system, comprising the steps of:

defining columns in the table;

selecting a plurality of functions, each function of the plurality of functions based on one or more columns of the table;

selecting a second group of one or more columns;

selecting a second function based on the third group of columns;

creating rows of the table;

generating a single-level function that results from the combination of the plurality of functions;

storing rows of the table in a logical order corresponding to the result of the single-level function for each row; and

if more than one row of the table has an identical result of the single-level function, storing those rows in a logical order corresponding to the result of the second function, wherein the step of storing rows comprises;

distributing rows of the table to a plurality of storage facilities based on the result of the second function; and

in each storage facility, storing rows of the table in a logical order corresponding to the result of the single-level function for each row and, if more than one row of the table has an identical result of the single-level function, storing those rows in a logical order corresponding to the result of the second function.

14. A method for building a table in a multi-level partitioned database system, comprising the steps of:

defining columns in the table;

selecting a plurality of functions, each function of the plurality of functions based on one or more columns of the table;

selecting a second group of one or more columns;

selecting a second function based on the third group of columns;

creating rows of the table;

generating a single-level function that results from the combination of the plurality of functions;

storing rows of the table in a logical order corresponding to the result of the single-level function for each row; and

if more than one row of the table has an identical result of the single-level function, storing those rows in a logical order corresponding to the result of the second function, wherein the first function of the plurality of functions assigns a value to each of several ranges of values in a date column.

15. A method for building a table in a multi-level partitioned database system comprising the steps of:

defining columns in the table;

selecting a plurality of functions, each function of the plurality of functions based on one or more columns of the table;

selecting a second group of one or more columns;

selecting a second function based on the third group of columns;

creating rows of the table;

generating a single-level function that results from the combination of the plurality of functions;

storing rows of the table in a logical order corresponding to the result of the single-level function for each row; and

if more than one row of the table has an identical result of the single-level function, storing those rows in a logical order corresponding to the result of the second function, wherein the second function is a hash function.

16. A method for building a table in a multi-level partitioned database system, comprising the steps of:

defining columns in the table;

selecting a plurality of functions, each function of the plurality of functions based on one or more columns of the table;

selecting a second group of one or more columns;

selecting a second function based on the third group of columns;

creating rows of the table;

generating a single-level function that results from the combination of the plurality of functions;

storing rows of the table in a logical order corresponding to the result of the single-level function for each row; and

if more than one row of the table has an identical result of the single-level function, storing those rows in a logical order corresponding to the result of the second function, wherein the results of the single-level and second functions for each row are included in a row ID.

17. A method for building a table in a multi-level partitioned database system, comprising the steps of:

defining columns in the table;

selecting a plurality of functions, each function of the plurality of functions based on one or more columns of the table;

selecting a second group of one or more columns;

selecting a second function based on the third group of columns;

creating rows of the table;

generating a single-level function that results from the combination of the plurality of functions;

storing rows of the table in a logical order corresponding to the result of the single-level function for each row; and

if more than one row of the table has an identical result of the single-level function, storing those rows in a logical order corresponding to the result of the second function, wherein the plurality of functions are two functions and the single-level function is generated in accordance with the formula;

P=((P₁−

mn₁)*(mx₂−

mn₂+1)+P₂−

mn₂)

where P is the single-level function, P₁ is the first function of the plurality of functions, P₂ is the second function of the plurality of functions, and mn_i and mx_i are a minimum and a maximum resulting values of P_i.

18. A method for building a table in a multi-level partitioned database system comprising the steps of:

defining columns in the table;

selecting a plurality of functions, each function of the plurality of functions based on one or more columns of the table;

selecting a second group of one or more columns;

selecting a second function based on the third group of columns;

creating rows of the table;

generating a single-level function that results from the combination of the plurality of functions;

storing rows of the table in a logical order corresponding to the result of the single-level function for each row; and

if more than one row of the table has an identical result of the single-level function, storing those rows in a logical order corresponding to the result of the second function, wherein the single-level function is generated in accordance with the formula;

P=( . . . ((P₁−

mn₁)*(mx₂−

mn₂+1)+P₂−

mn₂)*(mx₃−

mn₃+1) + . . . +P<sub>(n−

1)</sub>−

mn<sub>(n−

1)</sub>)*(mx_n−

mn_n+1)+P_n−

mn_n)

where P is the single-level function, P_i is an i^th function of the plurality of functions, and mn_i and mx_i are a minimum and a maximum resulting values of P_i.

19. A computer program, stored in a tangible medium, for building a table in a multi-level partitioned database system, the program comprising executable instructions that cause a computer to:

store column definitions of the table;

store a plurality of functions, each based on values in one or more columns;

store a second group of one or more columns;

store a second function based on values in each column of the second group of columns;

receive data for rows of the table;

generate a single-level function that results from the combination of the plurality of functions;

store rows of the table in a logical order corresponding to the single-level function for each row; and

if more than one row of the table has an identical result of the single-level function, store those rows in a logical order corresponding to the result of the second function, where the computer stores rows by;

distributing rows of the table to a plurality of storage facilities based on the result of the second function; and

in each storage facility, storing rows of the table in a logical order corresponding to the result of the single-level function for each row and, if more than one row of the table has an identical result of the single-level function, storing those rows in a logical order corresponding to the result of the second function.

20. A computer program, stored in a tangible medium, for building a table in a multi-level partitioned database system, the program comprising executable instructions that cause a computer to:

store column definitions of the table;

store a plurality of functions, each based on values in one or more columns;

store a second group of one or more columns;

store a second function based on values in each column of the second group of columns;

receive data for rows of the table;

generate a single-level function that results from the combination of the plurality of functions;

store rows of the table in a logical order corresponding to the single-level function for each row; and

if more than one row of the table has an identical result of the single-level function, store those rows in a logical order corresponding to the result of the second function, where the single-level function is generated in accordance with the formula;

P= . . . ((P₁−

mn₁)*(mx₂−

mn₂+1)+P₂−

mn₂) *(mx₃−

mn₃+1)+( . . . +P<sub>(n−

1)</sub>−

mn<sub>n−

1</sub>))* (mx_n−

mn_n+1)+P_n−

mn_n)

where P is the single-level function, P_iis an i^th function of the plurality of functions, and mn_i and mx_i are a minimum and a maximum resulting values of P_i.