A method and system for estimating cardinalities for a plurality of columns in a database system is disclosed. The method and system include obtaining statistics collected for the plurality of columns. A first portion of the statistics indicates at least one relationship between at least a portion of the plurality of columns, while a second portion of the statistics includes single column statistics. The method and system also include utilizing the first portion and the second portion of the statistics to estimate the cardinality for the plurality of columns.