1. In a relational database having records in the form of tables of tuples stored therein, a method for compiling a statistical representation of a given attribute for tuples that verify a user query wherein the user query comprises a join predicate that joins first and second database tables on a join attribute, the method comprising the steps of: scanning the tuples contained in the second database table; for each scanned tuple, determining a multiplicity value based on an approximate number of tuples from the first database table that have a matching join attribute with respect to the scanned tuple; adding a number of copies of the scanned tuple to a stream of tuples wherein the number of copies added corresponds to the multiplicity value determined for the scanned tuple; and sampling the stream of tuples to compile a statistical representation for values of the given attribute in the sampled tuples.