Salient sampling for query size estimation
View Patent ↗Salient sampling for query size estimation includes identifying two or more columns in a database table that have corresponding columns in one or more other tables. One or more hash functions are applied to domains of each of the identified columns. A first hash function is applied to a domain of the first column and a second hash function to a domain of the second column. A subset of the rows in the database table is selected. The selecting includes selecting rows in the database table where results of the first hash function meet a first numeric threshold and selecting rows in the database table where results of the second hash function meet a second numeric threshold. A sample database table corresponding to the database table is created. The sample database table includes the selected subset of the rows in the database table.
1. A system for creating samples of database tables, the system comprising:
at least one memory having computer readable computer instructions; and
at least one 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 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 system of claim 1 , wherein the first hash function is different than the second hash function.
3. The system of claim 1 , wherein the first hash function is the same as the second hash function.
4. The system of claim 1 , wherein the first numeric threshold is different than the second numeric threshold.
5. The system of claim 1 , wherein the first numeric threshold is the same as the second numeric threshold.
6. The system 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.
7. The system of claim 1 , wherein the method further comprises computing the database query over the sample database table.
8. The system of claim 1 , 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.
9. The system of claim 1 , wherein one of the first hash function and second hash function is universal.
10. The system of claim 1 , wherein the method 1 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.
11. A non-transitory computer readable storage media for creating samples of database tables, the non-transitory computer readable storage media 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; 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.
12. The non-transitory computer-readable medium of claim 11 , wherein the first hash function is different than the second hash function.
13. The non-transitory computer-readable medium of claim 11 , wherein the first hash function is the same as the second hash function.
14. The non-transitory computer-readable medium of claim 11 , wherein the first numeric threshold is different than the second numeric threshold.
15. The non-transitory computer-readable medium of claim 11 , wherein the first numeric threshold is the same as the second numeric threshold.
16. The non-transitory computer-readable medium of claim 11 , 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.
17. The non-transitory computer-readable medium of claim 11 , wherein the method further comprises computing the database query over the sample database table.
18. The non-transitory computer-readable medium of claim 11 , 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.
19. The non-transitory computer-readable medium of claim 11 , wherein one of the first hash function and second hash function is universal.
20. The non-transitory computer-readable medium of claim 11 , wherein the method 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.