Re: Statistics and selectivity estimation for ranges

On 04.01.2013 10:42, Alexander Korotkov wrote:
> /*
>  * Calculate selectivity of "&&" operator using histograms of range lower bounds
>  * and histogram of range lengths.
>  */
> static double
> calc_hist_selectivity_overlap(TypeCacheEntry *typcache, RangeBound *lower,
> 					RangeBound *upper, RangeBound *hist_lower, int hist_nvalues,
> 							Datum *length_hist_values, int length_hist_nvalues)

We already have code to estimate &&, based on the lower and upper bound 
histograms:

> 		case OID_RANGE_OVERLAP_OP:
> 		case OID_RANGE_CONTAINS_ELEM_OP:
> 			/*
> 			 * A && B <=> NOT (A << B OR A >> B).
> 			 *
> 			 * "range @> elem" is equivalent to "range && [elem,elem]". The
> 			 * caller already constructed the singular range from the element
> 			 * constant, so just treat it the same as &&.
> 			 */
> 			hist_selec =
> 				calc_hist_selectivity_scalar(typcache, &const_lower, hist_upper,
> 											 nhist, false);
> 			hist_selec +=
> 				(1.0 - calc_hist_selectivity_scalar(typcache, &const_upper, hist_lower,
> 												  nhist, true));
> 			hist_selec = 1.0 - hist_selec;
> 			break;

I don't think the method based on lower bound and length histograms is 
any better. In fact, my gut feeling is that it's less accurate. I'd 
suggest dropping that part of the patch.

- Heikki