Salient sampling for query size estimation

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.