Branch data Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * ts_selfuncs.c
4 : : * Selectivity estimation functions for text search operators.
5 : : *
6 : : * Portions Copyright (c) 1996-2026, PostgreSQL Global Development Group
7 : : *
8 : : *
9 : : * IDENTIFICATION
10 : : * src/backend/tsearch/ts_selfuncs.c
11 : : *
12 : : *-------------------------------------------------------------------------
13 : : */
14 : : #include "postgres.h"
15 : :
16 : : #include "access/htup_details.h"
17 : : #include "catalog/pg_statistic.h"
18 : : #include "catalog/pg_type.h"
19 : : #include "miscadmin.h"
20 : : #include "nodes/nodes.h"
21 : : #include "tsearch/ts_type.h"
22 : : #include "utils/fmgrprotos.h"
23 : : #include "utils/lsyscache.h"
24 : : #include "utils/selfuncs.h"
25 : :
26 : :
27 : : /*
28 : : * The default text search selectivity is chosen to be small enough to
29 : : * encourage indexscans for typical table densities. See selfuncs.h and
30 : : * DEFAULT_EQ_SEL for details.
31 : : */
32 : : #define DEFAULT_TS_MATCH_SEL 0.005
33 : :
34 : : /* lookup table type for binary searching through MCELEMs */
35 : : typedef struct
36 : : {
37 : : text *element;
38 : : float4 frequency;
39 : : } TextFreq;
40 : :
41 : : /* type of keys for bsearch'ing through an array of TextFreqs */
42 : : typedef struct
43 : : {
44 : : char *lexeme;
45 : : int length;
46 : : } LexemeKey;
47 : :
48 : : static Selectivity tsquerysel(VariableStatData *vardata, Datum constval);
49 : : static Selectivity mcelem_tsquery_selec(TSQuery query,
50 : : const Datum *mcelem, int nmcelem,
51 : : const float4 *numbers, int nnumbers);
52 : : static Selectivity tsquery_opr_selec(QueryItem *item, char *operand,
53 : : TextFreq *lookup, int length, float4 minfreq);
54 : : static int compare_lexeme_textfreq(const void *e1, const void *e2);
55 : :
56 : : #define tsquery_opr_selec_no_stats(query) \
57 : : tsquery_opr_selec(GETQUERY(query), GETOPERAND(query), NULL, 0, 0)
58 : :
59 : :
60 : : /*
61 : : * tsmatchsel -- Selectivity of "@@"
62 : : *
63 : : * restriction selectivity function for tsvector @@ tsquery and
64 : : * tsquery @@ tsvector
65 : : */
66 : : Datum
67 : 171 : tsmatchsel(PG_FUNCTION_ARGS)
68 : : {
69 : 171 : PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
70 : :
71 : : #ifdef NOT_USED
72 : : Oid operator = PG_GETARG_OID(1);
73 : : #endif
74 : 171 : List *args = (List *) PG_GETARG_POINTER(2);
75 : 171 : int varRelid = PG_GETARG_INT32(3);
76 : 171 : VariableStatData vardata;
77 : 171 : Node *other;
78 : 171 : bool varonleft;
79 : 171 : Selectivity selec;
80 : :
81 : : /*
82 : : * If expression is not variable = something or something = variable, then
83 : : * punt and return a default estimate.
84 : : */
85 [ - + ]: 171 : if (!get_restriction_variable(root, args, varRelid,
86 : : &vardata, &other, &varonleft))
87 : 0 : PG_RETURN_FLOAT8(DEFAULT_TS_MATCH_SEL);
88 : :
89 : : /*
90 : : * Can't do anything useful if the something is not a constant, either.
91 : : */
92 [ + - ]: 171 : if (!IsA(other, Const))
93 : : {
94 [ # # ]: 0 : ReleaseVariableStats(vardata);
95 : 0 : PG_RETURN_FLOAT8(DEFAULT_TS_MATCH_SEL);
96 : : }
97 : :
98 : : /*
99 : : * The "@@" operator is strict, so we can cope with NULL right away
100 : : */
101 [ - + ]: 171 : if (((Const *) other)->constisnull)
102 : : {
103 [ # # ]: 0 : ReleaseVariableStats(vardata);
104 : 0 : PG_RETURN_FLOAT8(0.0);
105 : : }
106 : :
107 : : /*
108 : : * OK, there's a Var and a Const we're dealing with here. We need the
109 : : * Const to be a TSQuery, else we can't do anything useful. We have to
110 : : * check this because the Var might be the TSQuery not the TSVector.
111 : : */
112 [ + - ]: 171 : if (((Const *) other)->consttype == TSQUERYOID)
113 : : {
114 : : /* tsvector @@ tsquery or the other way around */
115 [ + - ]: 171 : Assert(vardata.vartype == TSVECTOROID);
116 : :
117 : 171 : selec = tsquerysel(&vardata, ((Const *) other)->constvalue);
118 : 171 : }
119 : : else
120 : : {
121 : : /* If we can't see the query structure, must punt */
122 : 0 : selec = DEFAULT_TS_MATCH_SEL;
123 : : }
124 : :
125 [ + + ]: 171 : ReleaseVariableStats(vardata);
126 : :
127 [ - + + - ]: 342 : CLAMP_PROBABILITY(selec);
128 : :
129 : 171 : PG_RETURN_FLOAT8((float8) selec);
130 : 171 : }
131 : :
132 : :
133 : : /*
134 : : * tsmatchjoinsel -- join selectivity of "@@"
135 : : *
136 : : * join selectivity function for tsvector @@ tsquery and tsquery @@ tsvector
137 : : */
138 : : Datum
139 : 0 : tsmatchjoinsel(PG_FUNCTION_ARGS)
140 : : {
141 : : /* for the moment we just punt */
142 : 0 : PG_RETURN_FLOAT8(DEFAULT_TS_MATCH_SEL);
143 : : }
144 : :
145 : :
146 : : /*
147 : : * @@ selectivity for tsvector var vs tsquery constant
148 : : */
149 : : static Selectivity
150 : 171 : tsquerysel(VariableStatData *vardata, Datum constval)
151 : : {
152 : 171 : Selectivity selec;
153 : 171 : TSQuery query;
154 : :
155 : : /* The caller made sure the const is a TSQuery, so get it now */
156 : 171 : query = DatumGetTSQuery(constval);
157 : :
158 : : /* Empty query matches nothing */
159 [ + - ]: 171 : if (query->size == 0)
160 : 0 : return (Selectivity) 0.0;
161 : :
162 [ + + ]: 171 : if (HeapTupleIsValid(vardata->statsTuple))
163 : : {
164 : 165 : Form_pg_statistic stats;
165 : 165 : AttStatsSlot sslot;
166 : :
167 : 165 : stats = (Form_pg_statistic) GETSTRUCT(vardata->statsTuple);
168 : :
169 : : /* MCELEM will be an array of TEXT elements for a tsvector column */
170 [ + - ]: 165 : if (get_attstatsslot(&sslot, vardata->statsTuple,
171 : : STATISTIC_KIND_MCELEM, InvalidOid,
172 : : ATTSTATSSLOT_VALUES | ATTSTATSSLOT_NUMBERS))
173 : : {
174 : : /*
175 : : * There is a most-common-elements slot for the tsvector Var, so
176 : : * use that.
177 : : */
178 : 330 : selec = mcelem_tsquery_selec(query, sslot.values, sslot.nvalues,
179 : 165 : sslot.numbers, sslot.nnumbers);
180 : 165 : free_attstatsslot(&sslot);
181 : 165 : }
182 : : else
183 : : {
184 : : /* No most-common-elements info, so do without */
185 : 0 : selec = tsquery_opr_selec_no_stats(query);
186 : : }
187 : :
188 : : /*
189 : : * MCE stats count only non-null rows, so adjust for null rows.
190 : : */
191 : 165 : selec *= (1.0 - stats->stanullfrac);
192 : 165 : }
193 : : else
194 : : {
195 : : /* No stats at all, so do without */
196 : 6 : selec = tsquery_opr_selec_no_stats(query);
197 : : /* we assume no nulls here, so no stanullfrac correction */
198 : : }
199 : :
200 : 171 : return selec;
201 : 171 : }
202 : :
203 : : /*
204 : : * Extract data from the pg_statistic arrays into useful format.
205 : : */
206 : : static Selectivity
207 : 165 : mcelem_tsquery_selec(TSQuery query, const Datum *mcelem, int nmcelem,
208 : : const float4 *numbers, int nnumbers)
209 : : {
210 : 165 : float4 minfreq;
211 : 165 : TextFreq *lookup;
212 : 165 : Selectivity selec;
213 : 165 : int i;
214 : :
215 : : /*
216 : : * There should be two more Numbers than Values, because the last two
217 : : * cells are taken for minimal and maximal frequency. Punt if not.
218 : : *
219 : : * (Note: the MCELEM statistics slot definition allows for a third extra
220 : : * number containing the frequency of nulls, but we're not expecting that
221 : : * to appear for a tsvector column.)
222 : : */
223 [ - + ]: 165 : if (nnumbers != nmcelem + 2)
224 : 0 : return tsquery_opr_selec_no_stats(query);
225 : :
226 : : /*
227 : : * Transpose the data into a single array so we can use bsearch().
228 : : */
229 : 165 : lookup = palloc_array(TextFreq, nmcelem);
230 [ + + ]: 165165 : for (i = 0; i < nmcelem; i++)
231 : : {
232 : : /*
233 : : * The text Datums came from an array, so it cannot be compressed or
234 : : * stored out-of-line -- it's safe to use VARSIZE_ANY*.
235 : : */
236 [ + - ]: 165000 : Assert(!VARATT_IS_COMPRESSED(DatumGetPointer(mcelem[i])) && !VARATT_IS_EXTERNAL(DatumGetPointer(mcelem[i])));
237 : 165000 : lookup[i].element = (text *) DatumGetPointer(mcelem[i]);
238 : 165000 : lookup[i].frequency = numbers[i];
239 : 165000 : }
240 : :
241 : : /*
242 : : * Grab the lowest MCE frequency. compute_tsvector_stats() stored it for
243 : : * us in the one before the last cell of the Numbers array.
244 : : */
245 : 165 : minfreq = numbers[nnumbers - 2];
246 : :
247 : 330 : selec = tsquery_opr_selec(GETQUERY(query), GETOPERAND(query), lookup,
248 : 165 : nmcelem, minfreq);
249 : :
250 : 165 : pfree(lookup);
251 : :
252 : 165 : return selec;
253 : 165 : }
254 : :
255 : : /*
256 : : * Traverse the tsquery in preorder, calculating selectivity as:
257 : : *
258 : : * selec(left_oper) * selec(right_oper) in AND & PHRASE nodes,
259 : : *
260 : : * selec(left_oper) + selec(right_oper) -
261 : : * selec(left_oper) * selec(right_oper) in OR nodes,
262 : : *
263 : : * 1 - select(oper) in NOT nodes
264 : : *
265 : : * histogram-based estimation in prefix VAL nodes
266 : : *
267 : : * freq[val] in exact VAL nodes, if the value is in MCELEM
268 : : * min(freq[MCELEM]) / 2 in VAL nodes, if it is not
269 : : *
270 : : * The MCELEM array is already sorted (see ts_typanalyze.c), so we can use
271 : : * binary search for determining freq[MCELEM].
272 : : *
273 : : * If we don't have stats for the tsvector, we still use this logic,
274 : : * except we use default estimates for VAL nodes. This case is signaled
275 : : * by lookup == NULL.
276 : : */
277 : : static Selectivity
278 : 513 : tsquery_opr_selec(QueryItem *item, char *operand,
279 : : TextFreq *lookup, int length, float4 minfreq)
280 : : {
281 : 513 : Selectivity selec;
282 : :
283 : : /* since this function recurses, it could be driven to stack overflow */
284 : 513 : check_stack_depth();
285 : :
286 [ + + ]: 513 : if (item->type == QI_VAL)
287 : : {
288 : 307 : QueryOperand *oper = (QueryOperand *) item;
289 : 307 : LexemeKey key;
290 : :
291 : : /*
292 : : * Prepare the key for bsearch().
293 : : */
294 : 307 : key.lexeme = operand + oper->distance;
295 : 307 : key.length = oper->length;
296 : :
297 [ + + ]: 307 : if (oper->prefix)
298 : : {
299 : : /* Prefix match, ie the query item is lexeme:* */
300 : 17 : Selectivity matched,
301 : : allmces;
302 : 17 : int i,
303 : : n_matched;
304 : :
305 : : /*
306 : : * Our strategy is to scan through the MCELEM list and combine the
307 : : * frequencies of the ones that match the prefix. We then
308 : : * extrapolate the fraction of matching MCELEMs to the remaining
309 : : * rows, assuming that the MCELEMs are representative of the whole
310 : : * lexeme population in this respect. (Compare
311 : : * histogram_selectivity().) Note that these are most common
312 : : * elements not most common values, so they're not mutually
313 : : * exclusive. We treat occurrences as independent events.
314 : : *
315 : : * This is only a good plan if we have a pretty fair number of
316 : : * MCELEMs available; we set the threshold at 100. If no stats or
317 : : * insufficient stats, arbitrarily use DEFAULT_TS_MATCH_SEL*4.
318 : : */
319 [ + + - + ]: 17 : if (lookup == NULL || length < 100)
320 : 5 : return (Selectivity) (DEFAULT_TS_MATCH_SEL * 4);
321 : :
322 : 12 : matched = allmces = 0;
323 : 12 : n_matched = 0;
324 [ + + ]: 12012 : for (i = 0; i < length; i++)
325 : : {
326 : 12000 : TextFreq *t = lookup + i;
327 : 12000 : int tlen = VARSIZE_ANY_EXHDR(t->element);
328 : :
329 [ + - + + ]: 12000 : if (tlen >= key.length &&
330 : 24000 : strncmp(key.lexeme, VARDATA_ANY(t->element),
331 : 24000 : key.length) == 0)
332 : : {
333 : 432 : matched += t->frequency - matched * t->frequency;
334 : 432 : n_matched++;
335 : 432 : }
336 : 12000 : allmces += t->frequency - allmces * t->frequency;
337 : 12000 : }
338 : :
339 : : /* Clamp to ensure sanity in the face of roundoff error */
340 [ - + + - ]: 24 : CLAMP_PROBABILITY(matched);
341 [ - + + - ]: 24 : CLAMP_PROBABILITY(allmces);
342 : :
343 : 12 : selec = matched + (1.0 - allmces) * ((double) n_matched / length);
344 : :
345 : : /*
346 : : * In any case, never believe that a prefix match has selectivity
347 : : * less than we would assign for a non-MCELEM lexeme. This
348 : : * preserves the property that "word:*" should be estimated to
349 : : * match at least as many rows as "word" would be.
350 : : */
351 [ - + - + : 12 : selec = Max(Min(DEFAULT_TS_MATCH_SEL, minfreq / 2), selec);
# # ]
352 [ + + ]: 17 : }
353 : : else
354 : : {
355 : : /* Regular exact lexeme match */
356 : 290 : TextFreq *searchres;
357 : :
358 : : /* If no stats for the variable, use DEFAULT_TS_MATCH_SEL */
359 [ + + ]: 290 : if (lookup == NULL)
360 : 2 : return (Selectivity) DEFAULT_TS_MATCH_SEL;
361 : :
362 : 288 : searchres = (TextFreq *) bsearch(&key, lookup, length,
363 : : sizeof(TextFreq),
364 : : compare_lexeme_textfreq);
365 : :
366 [ + + ]: 288 : if (searchres)
367 : : {
368 : : /*
369 : : * The element is in MCELEM. Return precise selectivity (or
370 : : * at least as precise as ANALYZE could find out).
371 : : */
372 : 268 : selec = searchres->frequency;
373 : 268 : }
374 : : else
375 : : {
376 : : /*
377 : : * The element is not in MCELEM. Estimate its frequency as
378 : : * half that of the least-frequent MCE. (We know it cannot be
379 : : * more than minfreq, and it could be a great deal less. Half
380 : : * seems like a good compromise.) For probably-historical
381 : : * reasons, clamp to not more than DEFAULT_TS_MATCH_SEL.
382 : : */
383 [ - + ]: 20 : selec = Min(DEFAULT_TS_MATCH_SEL, minfreq / 2);
384 : : }
385 [ + + ]: 290 : }
386 [ + + ]: 307 : }
387 : : else
388 : : {
389 : : /* Current TSQuery node is an operator */
390 : 206 : Selectivity s1,
391 : : s2;
392 : :
393 [ + + + - ]: 206 : switch (item->qoperator.oper)
394 : : {
395 : : case OP_NOT:
396 : 140 : selec = 1.0 - tsquery_opr_selec(item + 1, operand,
397 : 70 : lookup, length, minfreq);
398 : 70 : break;
399 : :
400 : : case OP_PHRASE:
401 : : case OP_AND:
402 : 190 : s1 = tsquery_opr_selec(item + 1, operand,
403 : 95 : lookup, length, minfreq);
404 : 190 : s2 = tsquery_opr_selec(item + item->qoperator.left, operand,
405 : 95 : lookup, length, minfreq);
406 : 95 : selec = s1 * s2;
407 : 95 : break;
408 : :
409 : : case OP_OR:
410 : 82 : s1 = tsquery_opr_selec(item + 1, operand,
411 : 41 : lookup, length, minfreq);
412 : 82 : s2 = tsquery_opr_selec(item + item->qoperator.left, operand,
413 : 41 : lookup, length, minfreq);
414 : 41 : selec = s1 + s2 - s1 * s2;
415 : 41 : break;
416 : :
417 : : default:
418 [ # # # # ]: 0 : elog(ERROR, "unrecognized operator: %d", item->qoperator.oper);
419 : 0 : selec = 0; /* keep compiler quiet */
420 : 0 : break;
421 : : }
422 : 206 : }
423 : :
424 : : /* Clamp intermediate results to stay sane despite roundoff error */
425 [ - + + - ]: 1012 : CLAMP_PROBABILITY(selec);
426 : :
427 : 506 : return selec;
428 : 513 : }
429 : :
430 : : /*
431 : : * bsearch() comparator for a lexeme (non-NULL terminated string with length)
432 : : * and a TextFreq. Use length, then byte-for-byte comparison, because that's
433 : : * how ANALYZE code sorted data before storing it in a statistic tuple.
434 : : * See ts_typanalyze.c for details.
435 : : */
436 : : static int
437 : 2224 : compare_lexeme_textfreq(const void *e1, const void *e2)
438 : : {
439 : 2224 : const LexemeKey *key = (const LexemeKey *) e1;
440 : 2224 : const TextFreq *t = (const TextFreq *) e2;
441 : 2224 : int len1,
442 : : len2;
443 : :
444 : 2224 : len1 = key->length;
445 : 2224 : len2 = VARSIZE_ANY_EXHDR(t->element);
446 : :
447 : : /* Compare lengths first, possibly avoiding a strncmp call */
448 [ + + ]: 2224 : if (len1 > len2)
449 : 180 : return 1;
450 [ - + ]: 2044 : else if (len1 < len2)
451 : 0 : return -1;
452 : :
453 : : /* Fall back on byte-for-byte comparison */
454 : 2044 : return strncmp(key->lexeme, VARDATA_ANY(t->element), len1);
455 : 2224 : }
|
