Patent ID: 7330848

Claim:
In a relational database having records in the form of tables of tuples stored therein, a method for compiling a statistical representation of an 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 statistical multiplicity value based on a 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 statistical multiplicity value determined for the scanned tuple; sampling the stream of tuples to compile a statistical representation for values of the attribute in the sampled tuples; and storing the statistical representation in at least one memory, wherein determining the statistical multiplicity value is performed by accessing statistical information about the first and second tables and based on the statistical information determining a number of tuples in the first table that have a matching join attribute value to the scanned tuple, and wherein the statistical information comprises a first histogram on the first table that has a first bucket containing the join attribute value of the scanned tuple and a second histogram on the second table that has a second bucket containing the join attribute value of the scanned tuple, wherein each bucket has a frequency and a number of distinct values contained in the bucket, and wherein the statistical multiplicity value is calculated as the frequency of the join attribute in the first table divided by a maximum of the number of distinct values in the first bucket and the number of distinct values in the second bucket.