Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit1faf866

Browse files
committed
Fix logical errors in tsquery selectivity estimation for prefix queries.
I made multiple errors in commit97532f7,stemming mostly from failure to think about the available frequency dataas being element frequencies not value frequencies (so that occurrences ofdifferent elements are not mutually exclusive). This led to sillinessessuch as estimating that "word" would match more rows than "word:*".The choice to clamp to a minimum estimate of DEFAULT_TS_MATCH_SEL alsoseems pretty ill-considered in hindsight, as it would frequently result inan estimate much larger than the available data suggests. We do need somesort of clamp, since a pattern not matching any of the MCELEMs probablystill needs a selectivity estimate of more than zero. I chose instead toclamp to at least what a non-MCELEM word would be estimated as, preservingthe property that "word:*" doesn't get an estimate less than plain "word",whether or not the word appears in MCELEM.Per investigation of a gripe from Bill Martin, though I suspect that hisexample case actually isn't even reaching the erroneous code.Back-patch to 9.1 where this code was introduced.
1 parent4bc0d2e commit1faf866

File tree

1 file changed

+28
-16
lines changed

1 file changed

+28
-16
lines changed

‎src/backend/tsearch/ts_selfuncs.c

Lines changed: 28 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -304,23 +304,29 @@ tsquery_opr_selec(QueryItem *item, char *operand,
304304
{
305305
/* Prefix match, ie the query item is lexeme:* */
306306
Selectivitymatched,
307-
allmcvs;
308-
inti;
307+
allmces;
308+
inti,
309+
n_matched;
309310

310311
/*
311-
* Our strategy is to scan through the MCV list and add up the
312-
* frequencies of the ones that match the prefix, thereby assuming
313-
* that the MCVs are representative of the whole lexeme population
314-
* in this respect. Compare histogram_selectivity().
312+
* Our strategy is to scan through the MCELEM list and combine the
313+
* frequencies of the ones that match the prefix. We then
314+
* extrapolate the fraction of matching MCELEMs to the remaining
315+
* rows, assuming that the MCELEMs are representative of the whole
316+
* lexeme population in this respect. (Compare
317+
* histogram_selectivity().) Note that these are most common
318+
* elements not most common values, so they're not mutually
319+
* exclusive. We treat occurrences as independent events.
315320
*
316321
* This is only a good plan if we have a pretty fair number of
317-
*MCVs available; we set the threshold at 100. If no stats or
322+
*MCELEMs available; we set the threshold at 100. If no stats or
318323
* insufficient stats, arbitrarily use DEFAULT_TS_MATCH_SEL*4.
319324
*/
320325
if (lookup==NULL||length<100)
321326
return (Selectivity) (DEFAULT_TS_MATCH_SEL*4);
322327

323-
matched=allmcvs=0;
328+
matched=allmces=0;
329+
n_matched=0;
324330
for (i=0;i<length;i++)
325331
{
326332
TextFreq*t=lookup+i;
@@ -329,20 +335,26 @@ tsquery_opr_selec(QueryItem *item, char *operand,
329335
if (tlen >=key.length&&
330336
strncmp(key.lexeme,VARDATA_ANY(t->element),
331337
key.length)==0)
332-
matched+=t->frequency;
333-
allmcvs+=t->frequency;
338+
{
339+
matched+=t->frequency-matched*t->frequency;
340+
n_matched++;
341+
}
342+
allmces+=t->frequency-allmces*t->frequency;
334343
}
335344

336-
if (allmcvs>0)/* paranoia about zero divide */
337-
selec=matched /allmcvs;
338-
else
339-
selec= (Selectivity) (DEFAULT_TS_MATCH_SEL*4);
345+
/* Clamp to ensure sanity in the face of roundoff error */
346+
CLAMP_PROBABILITY(matched);
347+
CLAMP_PROBABILITY(allmces);
348+
349+
selec=matched+ (1.0-allmces)* ((double)n_matched /length);
340350

341351
/*
342352
* In any case, never believe that a prefix match has selectivity
343-
* less than DEFAULT_TS_MATCH_SEL.
353+
* less than we would assign for a non-MCELEM lexeme. This
354+
* preserves the property that "word:*" should be estimated to
355+
* match at least as many rows as "word" would be.
344356
*/
345-
selec=Max(DEFAULT_TS_MATCH_SEL,selec);
357+
selec=Max(Min(DEFAULT_TS_MATCH_SEL,minfreq /2),selec);
346358
}
347359
else
348360
{

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp