To: Matteo Beccati <php@beccati.com>
cc: Andrea Arcangeli <andrea@cpushare.com>, pgsql-performance@postgresql.org
Subject: Re: NOT LIKE much faster than LIKE? 
In-reply-to: <43C3799D.5030103@beccati.com> 
References: <20060110014447.GB18474@opteron.random>
	<24021.1136858688@sss.pgh.pa.us>
	<20060110022303.GA20168@opteron.random>
	<24372.1136861684@sss.pgh.pa.us> <43C3799D.5030103@beccati.com>
Comments: In-reply-to Matteo Beccati <php@beccati.com>
	message dated "Tue, 10 Jan 2006 10:08:45 +0100"
Date: Tue, 10 Jan 2006 12:49:55 -0500
Message-ID: <1625.1136915395@sss.pgh.pa.us>
From: Tom Lane <tgl@sss.pgh.pa.us>

Matteo Beccati <php@beccati.com> writes:
>> I did just think of something we could improve though.  The pattern
>> selectivity code doesn't make any use of the statistics about "most
>> common values".  For a constant pattern, we could actually apply the
>> pattern test with each common value and derive answers that are exact
>> for the portion of the population represented by the most-common-values
>> list.

> This reminds me what I did in a patch which is currently on hold for the 
> next release:

I've applied a patch to make patternsel() compute the exact result for
the MCV list, and use its former heuristics only for the portion of the
column population not included in the MCV list.

After finishing that work it occurred to me that we could go a step
further: if the MCV list accounts for a substantial fraction of the
population, we could assume that the MCV list is representative of the
whole population, and extrapolate the pattern's selectivity over the MCV
list to the whole population instead of using the existing heuristics at
all.  In a situation like Andreas' example this would win big, although
you can certainly imagine cases where it would lose too.

Any thoughts about this?  What would be a reasonable threshold for
"substantial fraction"?  It would probably make sense to have different
thresholds depending on whether the pattern is left-anchored or not,
since the range heuristic only works for left-anchored patterns.

			regards, tom lane