Patent ID: 7685098
Filing Date: 2010-03-23
Classification: G06F,Y10S

Abstract:
1. A method of estimating a join size for first and second tables, the method comprising, in a computer including a hardware-implemented processor: (a) determining a plurality of merge regions from first and second histograms respectively associated with the first and second tables, wherein each histogram includes a plurality of regions, and wherein each merge region overlaps a region from at least one of the first or the second histograms; (b) for each merge region, calculating a partial join estimation for such merge region, wherein calculating the partial join estimation includes scaling a density for any region of the first and second histograms associated with the merge region by a width associated with such merge region; and (c) combining the partial join estimations, wherein calculating the partial join estimation for the merge region includes calculating a partial join estimation used in estimating a join size for the first and second tables meeting a condition A<B wherein the condition A<B is indicative of a number of data values in the first table that are less than data values in the second table using at a formula: where |currA| is the density of the region from the first histogram associated with the merge region, |currB| is the density of the region from the second histogram associated with the merge region, width(currM) is the width of the merge region, and the accum(currA) is an estimate of the number of data values in the first table that are smaller than a lower range of the merge region.