Granted Patent B2

US 9,779,137 · App. 14/298,201 · Granted Oct 3, 2017

Abstract

Claims (51)

1. A method of creating samples of database tables, the method comprising:

identifying a first column and a second column in a first database table, each of the first and second columns having corresponding columns in one or more other database tables;

applying one or more hash functions to values in the first column and second column, the applying including applying a first hash function to the values of the first column and applying a second hash function to the values of the second column;

selecting a subset of the rows in the first database table where results of the first hash function meet a first numeric threshold, or where results of the second hash function meet a second numeric threshold;

creating a sample database table corresponding to the result of a join operation of the subset of rows of the first database table and the one or more other database tables; and

estimating a cardinality of a database query over the first database table by scaling the cardinality of the database query over the sample database table by a factor of 1/v where v is the volume of the selected subset of rows of the first database table relative to the first database table.

2. The method of claim 1 , further comprising executing a query against the sample database table.

3. The method of claim 1 , wherein the first hash function is different than the second hash function.

4. The method of claim 1 , wherein the first hash function is the same as the second hash function.

5. The method of claim 1 , wherein the first numeric threshold is different than the second numeric threshold.

6. The method of claim 1 , wherein the first numeric threshold is the same as the second numeric threshold.

7. The method of claim 1 , wherein the one of the one or more other database tables and the first and second columns are mentioned in a database query, and the identifying, applying, selecting and creating are performed for all of the database tables and columns being joined in the database query.

8. The method of claim 7 , wherein the method further comprises computing the database query over the sample database table.

9. The method of claim 7 , further comprising:

expressing the database query as the disjoint union of two or more subqueries; and

performing for each subquery:

computing the subquery over the sample database table; and

estimating a cardinality of the database query as a cardinality of the subquery over the sample database table divided by a volume of the selected subset of rows; and

adding the resulting estimates.

10. A system for creating samples of database tables, the system comprising: a memory having computer readable computer instructions; and

a processor for executing the computer readable instructions to perform a method comprising:

identifying a first column and a second column in a first database table, each of the first and second columns having corresponding columns in one or more other database tables;

applying one or more hash functions to values in the first column and second column, the applying including applying a first hash function to the values of the first column and applying a second hash function to the value of the second column;

selecting a subset of the rows in the first database table where results of the first hash function meet a first numeric threshold, or where results of the second hash function meet a second numeric threshold;

creating a sample database table corresponding to the result of a join operation of the subset of rows of the first database table and one or more other database tables; and

wherein

the first hash function is different than the second hash function.

11. The system of claim 10 , further comprising executing a query against the sample database table.

12. The system of claim 10 , wherein at least one of:

the first hash function is the same as the second hash function; and

the first numeric threshold is the same as the second numeric threshold.

13. The system of claim 10 , wherein the one or more other database tables and the first and second columns am mentioned in a database query, and the identifying, applying, selecting and creating are performed for all of the database tables and columns mentioned in the database query.

14. The system of claim 13 , wherein the method further comprises computing the database query over the sample database table.

15. The system of claim 14 , wherein the method further comprises estimating a cardinality of the database query over the first database table by scaling the cardinality of the database query over the sample database table by a factor of 1/v where v is the volume of the selected subset of rows of the first database table relative to the first database table.

16. The system of claim 13 , wherein the system further comprises:

expressing the database query as the disjoint union of two or more subqueries; and

performing for each subquery:

computing the subquery over the sample database tables; and

estimating a cardinality of the database query as a cardinality of the subquery over the sample database tables divided by a volume of the selected subset of rows; and

adding the resulting estimates.

17. A non-transitory computer readable storage medium for creating samples of database tables, the non-transitory computer readable storage medium having computer-readable program code embodied thereon, which when executed by a computer processor, causes the computer processor to implement a method, the method comprising:

identifying a first column and a second column in a first database table, each of the first and second columns having corresponding columns in one or more other database tables;

applying one or more hash functions to values in the first column and second column, the applying including applying a first hash function to the values of the first column and applying a second hash function to the values of the second column;

selecting a subset of the rows in the first database table where results of the first hash function meet a first numeric threshold, or where results of the second hash function meet a second numeric threshold;

creating a sample database table corresponding to the result of a join operation of the subset of rows of the first database table and the one or more other database tables, wherein the one or more other database tables and the first and second columns are mentioned in a database query, and the identifying, applying, selecting and creating are performed for all of the database tables and columns mentioned in the database query;

expressing the database query as the disjoint union of two or more subqueries; and

performing for each subquery:

computing the subquery over the sample database table; and

estimating a cardinality of the database query as a cardinality of the subquery over the sample database tables divided by a volume of the selected subset of rows; and

adding the resulting estimates.

18. The computer program product of claim 17 , wherein the method further comprises executing a query against the sample database table.

Assignments (8)