On Thu, Dec 11, 2008 at 2:06 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> "Vladimir Sitnikov" <sitnikov.vladimir@gmail.com> writes:
>> Do you consider using hash tables?
>
> Doubt it's really worth it, unless there's some way to amortize the
> setup cost across multiple selectivity estimations; which would surely
> complicate life.
>
> One thing that just now occurred to me is that as long as we maintain
> the convention that MCV lists are in decreasing frequency order, one can
> take any prefix of the list and it's a perfectly good MCV list of less
> resolution. So one way to reduce the time taken in eqjoinsel is to set
> an upper limit on the number of entries considered *by that routine*,
> whereas other estimator functions could use larger lists.
To what extent will that negate the benefit of having those statistics
in the first place?
Here's another idea. If you have a < operator, you could use a
quicksort-type strategy to partition the search space. Pick an
arbitrary element of either list and apply it to all elements of both
lists to divide the initial problem into two problems that are each
half as large. When the subproblems fall below some size threshold,
then solve them according to the existing algorithm. This is O(n^2)
in the worst case, just like quicksort, but the worst case is
difficult to construct.
...Robert