Partition boundary determination using random sampling on very large databases

• US 20030004944A1
• Filed: 07/02/2001
• Published: 01/02/2003
• Est. Priority Date: 07/02/2001
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Harper, John William, Slishman, Gordon Robert
• Granted Patent: US 7,024,401 B2
• Time in Patent Office: Days
• US Class Current: 707/7
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A system and method utilizing random sampling for partition analysis on very large databases. The method utilizes a random sampling algorithm that provides results accurate to within a few percentage points for large homogeneous databases. The accuracy is not affected by the size of the database and is determined primarily by the size of the sample. The system and method for approximate partition analysis reduces the time required for an analysis to a fraction of the time required for an exact analysis. The reduction in time thereby permits more frequent and timely analyses of database partition sizes.

Claims

1. A method for database partition boundary determination, the method comprising the steps of:

providing a pre-configured number S defining a default sample size;

selectively receiving a particular number defining a desired sample size and setting said number S equal to said particular number;

providing a seed value for initializing a random number algorithm;

randomly sampling S records of the database using the random sampling algorithm, wherein said S records are different each time said method is utilized with different seed values, and wherein said S records are different for successive utilizations of said method if at least one record has been added to or deleted from said database between successive utilizations of said method;

storing statistics for each of said S records as stored statistics including a record key for each record; and

,

producing an approximation partition analysis based on said stored statistics, wherein said approximation partition analysis is not mathematically exact.

2. The method as set forth in claim 1, further comprising the step of sorting said stored statistics by key prior to producing said partition analysis.

3. The method as set forth in claim 1, wherein the step of randomly sampling S records further includes the steps of:

generating a table of S number pairs (Y_j,I_j), j=1,2, . . . ,S, wherein all Y and all I are initially set to zero;

initializing a reservoir of records to an empty state;

setting an index M to said reservoir equal to zero;

generating a sequence of N non-repeating random numbers U₁,U₂, . . . ,U_N, 0≦

U≦

1, wherein N is the number of records in the database;

performing additional steps for each random number U_k generated, k=1,2, . . . ,N, including;

skipping the next record in the database if U_k is less than the smallest value of Y in said table of number pairs; and

,

updating the table if a Y less than U_k exists by performing further steps including;

setting M equal to its current value plus one;

replacing the smallest Y in the table with U_k;

setting the I value paired with the smallest Y equal to M; and

,

storing all or part of the next record of the database in said reservoir of stored records, wherein the current value of M is a reservoir index to said stored record.

4. The method as set forth in claim 3, wherein the step of updating the table further includes the step of arranging the table in a heap with respect to Y.

5. The method as set forth in claim 1, wherein the step of randomly sampling S records further comprises the steps of:

generating a table of S number pairs (Y_j,I_j), j=1,2, . . . ,S, wherein all Y and all I are initially set to zero;

generating a sequence of N non-repeating random numbers U₁,U₂, . . . ,U_N, 0≦

U≦

1, wherein N is the number of records in the database;

performing additional steps for each random number U_i generated, i=1,2, . . . ,N, including;

ignoring u_i if U_i is less than the smallest value of Y in said table of number pairs; and

,

updating the table if a Y less than U_i exists by performing further steps including;

replacing the smallest Y in the table with U_i;

setting the I value paired with the smallest Y equal to i; and

,

reading S records from the database corresponding to I_j, j=1,2, . . . ,S, wherein I_j is an index to a record in the database.

6. The method as set forth in claim 5, wherein the step of updating the table further includes the step of arranging the table in a heap with respect to Y.

7. The method as set forth in claim 1, wherein the step of storing said statistics includes storing said statistics in a memory.

8. The method as set forth in claim 7, wherein the step of storing said statistics in said memory includes compressing the statistics prior to storing in said memory.

9. The method as set forth in claim 7, further including the step of sorting said stored statistics by key prior to producing said partition analysis.

10. The method as set forth in claim 9, wherein the step of producing said approximation partition analysis includes the step of defining multiple partition boundaries.

11. The method as set forth in claim 10, further including the steps of:

accessing all database records in an arbitrary sequence;

iteratively filling all of said partitions except the last with said accessed records to a maximum byte count; and

,

storing remaining accessed records in the last of said partitions.

12. The method as set forth in claim 1, wherein the step of randomly sampling said S records includes randomly sampling the S records utilizing dataspaces including:

at least one index dataspace;

at least one key dataspace; and

,

at least one statistics dataspace.

14. The system of claim 13, further comprising a fourth computer program routine for sorting said stored statistics by key prior to producing said partition analysis.

15. The system of claim 13, wherein said random sampling facility further comprises:

a means for generating a table of S number pairs (Y_j,I_j), j=1,2, . . . ,S, wherein all Y and all I are initially zero;

a means for initializing a reservoir of records to an empty state;

a means for setting an index M to said reservoir equal to zero;

a means for generating a sequence of N non-repeating random numbers U₁,U₂, . . . ,U_N, 0≦

U≦

1, wherein N is the number of records in the database; and

,

a means, for each random number U_k generated, k=1,2, . . . ,N, comprising;

a means to skip the next record in said database if U_k is less than the smallest value of Y in said table of number pairs; and

,

a means to update the table if a Y less than U_k exists, comprising;

a means to set M equal to its current value plus one;

a means to replace the smallest Y in the table with U_k;

a means to set the I value paired with the smallest Y equal to M; and

,

a means to store all or part of the next record of said database in said reservoir of stored records, wherein the current value of M is a reservoir index to said stored record.

16. The database management system of claim 15 wherein the means to update the table further comprises a means to arrange the table in a heap with respect to Y.

17. The system of claim 13, wherein said random sampling facility further comprises:

a means for generating a table of S number pairs (Y_j,I_j), j=1,2, . . . ,S, wherein all Y and all I are initially zero;

a means for generating a sequence of N non-repeating random numbers U₁,U₂, . . . ,U_N, 0≦

U≦

1, wherein N is the number of records in the database;

a means, for each random number U_i generated, i=1,2, . . . ,N, comprising;

a means to ignore u_i if U_i is less than the smallest value of Y in said table of number pairs; and

,

a means to update the table if a Y less than U_i exists, comprising;

a means to replace the smallest Y in the table with U_i;

a means to set the I value paired with the smallest Y equal to i; and

,

a means for reading S records from the database corresponding to I_j, j=1,2, . . . ,S, wherein I_j is an index to a record in the database.

18. The database management system of claim 17 wherein the means to update the table further comprises a means to arrange the table in a heap with respect to Y.

19. The system of claim 13, further including a memory for storing said statistics.

20. The system of claim 19, further comprising a fourth computer program routine for sorting said stored statistics by key prior to producing said partition analysis.

21. The system of claim 20, wherein said partition analysis includes means for performing an analysis of multiple partition boundaries.

22. The system of claim 13, further comprising:

a means for accessing all database records in an arbitrary sequence;

a means for iteratively filling all of said partitions except the last with said accessed records to a maximum byte count; and

,

a means for storing remaining accessed records in the last of said partitions.

23. The system of claim 13, further comprising:

a means for utilizing at least one index dataspace;

a means for utilizing at least one key dataspace; and

,

a means for utilizing at least one statistics dataspace.

13. A database partition boundary determination system comprising:

a first computer program routine having a random number generating algorithm;

a second computer program routine having a random sampling facility utilizing said first program routine to randomly read records from a database and store statistics for each record read including a record key, wherein said records read are different each time said second routine is utilized with different seed values, and wherein said records read are different for successive utilizations of said second routine if at least one record has been added to or deleted from said database between successive utilizations of said second routine; and

,

a third computer program routine for generating a partition boundary analysis based on said stored statistics, wherein said partition boundary analysis is an approximation and is not mathematically exact.