Partition boundary determination using random sampling on very large databases
First Claim
Patent Images
1. A method for database partition boundary determination in a database management system (DBMS), the method comprising:
- providing a pre-configured number S defining a default sample size in a database analysis program;
selectively receiving by the database analysis program a particular number defining a desired sample size and setting said number S equal to said particular number;
providing a seed value to the database analysis program for initializing a random number algorithm;
randomly sampling S records of the database by the database analysis program 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.
1 Assignment
0 Petitions
Accused Products
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.
21 Citations
23 Claims
-
1. A method for database partition boundary determination in a database management system (DBMS), the method comprising:
-
providing a pre-configured number S defining a default sample size in a database analysis program;
selectively receiving by the database analysis program a particular number defining a desired sample size and setting said number S equal to said particular number;
providing a seed value to the database analysis program for initializing a random number algorithm;
randomly sampling S records of the database by the database analysis program 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. A method for database partition boundary determination comprising:
-
providing a pre-configured number S defining a default sample size;
selectively receiving by the database analysis program 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, wherein said randomly sampling S records further includes;
generating a table of S number pairs (Yj,Ij), 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 U1,U2, . . . ,UN, 0≦
U≦
1, wherein N is the number of records in the database;
performing additional steps for each random number Uk generated, k=1,2, . . . ,N, including;
skipping the next record in the database if Uk is less than the smallest value of Y in said table of number pairs; and
,updating the table if a Y less than Uk exists by performing further steps including;
setting M equal to its current value plus one;
replacing the smallest Y in the table with Uk;
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;
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. - View Dependent Claims (10)
-
-
11. A method for database partition boundary determination comprising:
-
providing a pre-configured number S defining a default sample size;
selectively receiving by the database analysis program 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, wherein said randomly sampling S records further comprises;
generating a table of S number pairs (Yj,Ij), j=1,2, . . . ,S, wherein all Y and all I are initially set to zero;
generating a sequence of N non-repeating random numbers U1, U2, . . . ,UN, 0≦
U≦
1, wherein N is the number of records in the database; and
,performing additional steps for each random number Ui generated, i=1,2, . . . ,N, including;
ignoring ui if Ui is less than the smallest value of Y in said table of number pairs; and
,updating the table if a Y less than Ui exists by performing further steps including;
replacing the smallest Y in the table with Ui;
setting the I value paired with the smallest Y equal to i; and
,reading S records from the database corresponding to Ij, j=1,2, . . . ,S, wherein Ij is an index to a record in the database 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. - View Dependent Claims (12)
-
-
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 read record including a record key, wherein said read records are different each time said second routine is utilized with different seed values, and wherein said read records 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. - View Dependent Claims (14, 15, 16, 17, 18, 19)
-
-
20. 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 read record including a record key, wherein said read records are different each time said second routine is utilized with different seed values, and wherein said read records 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, wherein said random sampling facility further comprises;
means for generating a table of S number pairs (Y.sub.j,I.sub.j), j=1,2, . . . ,S, wherein all Y and all I are initially zero;
means for initializing a reservoir of records to an empty state;
means for setting an index M to said reservoir equal to zero;
means for generating a sequence of N non-repeating random numbers U.sub.1,U.sub.2, . . . ,U.sub.N, 0.ltoreq.U.ltoreq.1, wherein N is the number of records in the database; and
,means, for each random number U.sub.k generated, k=1,2, . . . ,N, comprising;
means to skip the next record in said database if U.sub.k is less than the smallest value of Y in said table of number pairs; and
,means to update the table if a Y less than U.sub.k exists, comprising;
a means to set M equal to its current value plus one;
means to replace the smallest Y in the table with U.sub.k;
means to set the I value paired with the smallest Y equal to M; and
,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; 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. - View Dependent Claims (21)
-
-
22. 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 read record including a record key, wherein said read records are different each time said second routine is utilized with different seed values, and wherein said read records 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, wherein said random sampling facility further comprises;
means for generating a table of S number pairs (Y.sub.j,I.sub.j), j=1,2, . . . ,S, wherein all V and all I are initially zero;
means for generating a sequence of N non-repeating random numbers U.sub.1,U.sub.2, . . . ,U.sub.N, 0.ltoreq.U.ltoreq.1, wherein N is the number of records in the database;
means, for each random number U.sub.i generated, i=1,2, . . . ,N, comprising;
means to ignore u.sub.i if U.sub.i is less than the smallest value of Y in said table of number pairs; and
,means to update the table if a Y less than U.sub.i exists, comprising;
means to replace the smallest Y in the table with U.sub.i;
means to set the I value paired with the smallest Y equal to i; and
,means for reading S records from the database corresponding to I.sub.j, j=1,2, . . . ,S, wherein I.sub.j is an index to a record in the database; 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. - View Dependent Claims (23)
-
Specification