Debian Codegraph @

src/backend/tsearch/ts_selfuncs.c

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