> 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.
MCV lists are updated only during "analyze" phase, don't they? If the "setup cost" is the cost of maintaining those "hash tables", it is not going to hurt much.
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.
That makes sense, however, linear search for single item in the list of 10'000 elements could take a while. Hash lookup might be better choice.
Regards,
Vladimir Sitnikov