Re: A better way than tweaking NTUP_PER_BUCKET

On Saturday, June 22, 2013, Simon Riggs wrote:

> On 22 June 2013 21:40, Stephen Frost <sfrost(at)snowman(dot)net <javascript:;>>
> wrote:
>
> > I'm actually not a huge fan of this as it's certainly not cheap to do.
> If it
> > can be shown to be better than an improved heuristic then perhaps it
> would
> > work but I'm not convinced.
>
> We need two heuristics, it would seem:
>
> * an initial heuristic to overestimate the number of buckets when we
> have sufficient memory to do so
>
> * a heuristic to determine whether it is cheaper to rebuild a dense
> hash table into a better one.
>
> Although I like Heikki's rebuild approach we can't do this every x2
> overstretch. Given large underestimates exist we'll end up rehashing
> 5-12 times, which seems bad. Better to let the hash table build and
> then re-hash once, it we can see it will be useful.
>
> OK?
>

I've been thinking a bit more on your notion of simply using as much memory
as we're permitted, but maybe adjust it down based on how big the input to
the hash table is (which I think we have better stats on, and even if we
don't, we could easily keep track of how many tuples we've seen and
consider rehashing as we go). Still doesn't really address the issue of
dups though. It may still be much larger than it should be if there's a lot
of duplicates in the input that hash into a much smaller set of buckets.

Will think on it more.

Thanks,

Stephen