Patent ID: 7299226
Filing Date: 2007-11-20
Classification: G06F,Y10S

Abstract:
1. A method of estimating cardinality of a join of tables using multicolumn density values, comprising: identifying a number of distinct combination tuples, the combination tuples containing a combination of values of a plurality of attributes for each table; determining a number of duplicates for each identified distinct combination tuple; identifying a number of distinct subset tuples containing a value of a subset of the plurality of attributes for each table; determining a number of duplicates for each identified subset tuple; estimating a number of tuples from each table that participate in the join using a subset density factor, the subset density factor being equal to the determined number of duplicates for each identified subset tuple divided by the determined number of distinct subset tuples containing a value of a subset of the plurality of attributes for each table; estimating the cardinality of the join using a combination density factor for each table and the estimated number of tuples that participate in the join from each table, the combination density factor being equal to the determined number of duplicates for each identified distinct combination tuple divided by the determined number of distinct combination tuples containing a combination of values of a plurality of attributes for each table; outputting the estimated cardinality of the join.