Re: Proposed Patch to Improve Performance of Multi-BatchHash Join for Skewed Data Sets

The estimation functions assume the inner relation join column is
unique. But it freezes (flushes back to the main hash table) one skew
bucket at a time in order of least importance so if 100 inner tuples
can fit in the skew buckets then the skew buckets are only fully blown
out if the best tuple (the single most common value) occurs more than
100 times in the inner relation. And up until that point you still
have the tuples in memory that are the best "per tuple worth of
memory". But yes, after that point (more than 100 tuples of that best
MCV) the entire effort was wasted. The skew buckets are dynamically
flushed just like buckets in a dynamic hash join would be.

- Bryce Cutt

On Fri, Mar 20, 2009 at 5:51 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
> On Fri, Mar 20, 2009 at 8:45 PM, Bryce Cutt <pandasuit(at)gmail(dot)com> wrote:
>> On Fri, Mar 20, 2009 at 5:35 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
>>> If the inner relation isn't fairly close to unique you shouldn't be
>>> using this optimization in the first place.
>> Not necessarily true.  Seeing as (when the statistics are correct) we
>> know each of these inner tuples will match with the largest amount of
>> outer tuples it is just as much of a win per inner tuple as when they
>> are unique.  There is just a chance you will have to give up on the
>> optimization part way through if too many inner tuples fall into the
>> new "skew buckets" (formerly IM buckets) and dump the tuples back into
>> the main buckets.  The potential win is still pretty high though.
>>
>> - Bryce Cutt
>
> Maybe I'm remembering wrong, but I thought the estimating functions
> assuemd that the inner relation was unique.  So if there turn out to
> be 2, 3, 4, or more copies of each value, the chances of blowing out
> the skew hash table are almost 100%, I would think...  am I wrong?
>
> ...Robert
>