1. A distinct sampling system for use with a database that accommodates distinct value queries having predicates, comprising: a scanning subsystem configured to scan each row in said database for a distinct target attribute, employ a hash function to map said distinct target attribute to an attribute priority level, maintain random samples of said each row based on a sample priority level and a sample size, and produce a distinct sample therefrom; and a distinct query estimator configured to receive said distinct value queries, cause said distinct value queries to be executed on said distinct sample to retrieve a result, and adjust said result to produce a distinct estimate therefrom.