Method and system for rowcount estimation with multi-column statistics and histograms

A computer-implemented method for optimizing a database management system process of a query, the method comprising:

• collecting a plurality of single column statistics for a plurality of columns, the plurality of single column statistics providing estimates for row counts and unique entry counts for a single column operator;
• determining a first selectivity estimate as if the columns are substantially independent of each other;
• determining a first factor as a measure of a skew of the plurality of columns and as a measure of a dependence of a plurality of the columns;
• and
• determining a second selectivity estimate for predicates in the query using the first selectivity estimate and the first factor, the second selectivity estimate being used in optimizing processing of the query by the database management system;
• wherein the first factor is determined by computing a product of unique entry count selectivities from a sum of maximum unique entry counts for the plurality of columns,
• computing a product of maximum initial unique entry counts for the plurality of columns,
• computing a ratio of the product of unique entry count selectivities and the product of maximum initial entry counts,
• selecting a maximum multicolumn unique entry count from multicolumn entry counts for the plurality of columns, and
• computing the first factor from a product of the ratio and an inverse of the maximum multicolumn unique entry count.

A data processing system, comprising:

• a processor;
• a memory coupled to the processor;
• and
• wherein the memory stores a compiler that, when executed by the processor, determines a join selectivity value of columns based on a first selectivity value computed as if the two columns are dependent and a second selectivity value computed as if the two columns are independent,
• wherein the compiler performs a join operation based on the join selectivity value,
• wherein the compiler determines an intermediate selectivity value approximately halfway between the first selectivity value and the second selectivity value when a dependence between the two columns is unknown and wherein the compiler performs the join operation based on the intermediate selectivity value, and
• wherein the compiler determines the join selectivity of two columns further based on a cross product of row counts estimated for each of the two columns.

A storage medium containing computer-readable instructions that are executable by a computer and cause the computer to:

• produce a query tree based on a query posed by a computer language statement;
• transform the query tree into a form that represents a number of logically equivalent methods of processing the computer language statement;
• and
• estimate a cost associated with carrying out each of the logically equivalent methods,
• wherein said estimate the cost comprises determining a join selectivity for two columns based on a first selectivity value computed as if the two columns are dependent, a second selectivity value computed as if the two columns are independent and, when an independence of the two columns is unknown, an intermediate value between the first selectivity value and the second selectivity value, and
• wherein said determining the join selectivity for two columns is further based on a skew calculation that provides a correction if the two columns have different row count to unique entry count ratios.