Age Owner Branch data TLA Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * ts_selfuncs.c
4 : : * Selectivity estimation functions for text search operators.
5 : : *
6 : : * Portions Copyright (c) 1996-2024, 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
5686 tgl@sss.pgh.pa.us 67 :CBC 513 : tsmatchsel(PG_FUNCTION_ARGS)
68 : : {
69 : 513 : PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
70 : :
71 : : #ifdef NOT_USED
72 : : Oid operator = PG_GETARG_OID(1);
73 : : #endif
74 : 513 : List *args = (List *) PG_GETARG_POINTER(2);
75 : 513 : 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 [ - + ]: 513 : if (!get_restriction_variable(root, args, varRelid,
86 : : &vardata, &other, &varonleft))
5686 tgl@sss.pgh.pa.us 87 :UBC 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 : : */
5686 tgl@sss.pgh.pa.us 92 [ - + ]:CBC 513 : if (!IsA(other, Const))
93 : : {
5686 tgl@sss.pgh.pa.us 94 [ # # ]:UBC 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 : : */
5686 tgl@sss.pgh.pa.us 101 [ - + ]:CBC 513 : if (((Const *) other)->constisnull)
102 : : {
5686 tgl@sss.pgh.pa.us 103 [ # # ]:UBC 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 : : */
5006 tgl@sss.pgh.pa.us 112 [ + - ]:CBC 513 : if (((Const *) other)->consttype == TSQUERYOID)
113 : : {
114 : : /* tsvector @@ tsquery or the other way around */
115 [ - + ]: 513 : Assert(vardata.vartype == TSVECTOROID);
116 : :
5686 117 : 513 : selec = tsquerysel(&vardata, ((Const *) other)->constvalue);
118 : : }
119 : : else
120 : : {
121 : : /* If we can't see the query structure, must punt */
5686 tgl@sss.pgh.pa.us 122 :UBC 0 : selec = DEFAULT_TS_MATCH_SEL;
123 : : }
124 : :
5686 tgl@sss.pgh.pa.us 125 [ + + ]:CBC 513 : ReleaseVariableStats(vardata);
126 : :
127 [ - + - + ]: 513 : CLAMP_PROBABILITY(selec);
128 : :
129 : 513 : PG_RETURN_FLOAT8((float8) selec);
130 : : }
131 : :
132 : :
133 : : /*
134 : : * tsmatchjoinsel -- join selectivity of "@@"
135 : : *
136 : : * join selectivity function for tsvector @@ tsquery and tsquery @@ tsvector
137 : : */
138 : : Datum
5686 tgl@sss.pgh.pa.us 139 :UBC 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
5686 tgl@sss.pgh.pa.us 150 :CBC 513 : tsquerysel(VariableStatData *vardata, Datum constval)
151 : : {
152 : : Selectivity selec;
153 : : TSQuery query;
154 : :
155 : : /* The caller made sure the const is a TSQuery, so get it now */
5429 156 : 513 : query = DatumGetTSQuery(constval);
157 : :
158 : : /* Empty query matches nothing */
159 [ - + ]: 513 : if (query->size == 0)
5429 tgl@sss.pgh.pa.us 160 :UBC 0 : return (Selectivity) 0.0;
161 : :
5686 tgl@sss.pgh.pa.us 162 [ + + ]:CBC 513 : if (HeapTupleIsValid(vardata->statsTuple))
163 : : {
164 : : Form_pg_statistic stats;
165 : : AttStatsSlot sslot;
166 : :
167 : 495 : stats = (Form_pg_statistic) GETSTRUCT(vardata->statsTuple);
168 : :
169 : : /* MCELEM will be an array of TEXT elements for a tsvector column */
2528 170 [ + - ]: 495 : 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 : 495 : selec = mcelem_tsquery_selec(query, sslot.values, sslot.nvalues,
179 : : sslot.numbers, sslot.nnumbers);
180 : 495 : free_attstatsslot(&sslot);
181 : : }
182 : : else
183 : : {
184 : : /* No most-common-elements info, so do without */
5006 tgl@sss.pgh.pa.us 185 :UBC 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 : : */
4805 tgl@sss.pgh.pa.us 191 :CBC 495 : selec *= (1.0 - stats->stanullfrac);
192 : : }
193 : : else
194 : : {
195 : : /* No stats at all, so do without */
5006 196 : 18 : selec = tsquery_opr_selec_no_stats(query);
197 : : /* we assume no nulls here, so no stanullfrac correction */
198 : : }
199 : :
5686 200 : 513 : return selec;
201 : : }
202 : :
203 : : /*
204 : : * Extract data from the pg_statistic arrays into useful format.
205 : : */
206 : : static Selectivity
207 : 495 : mcelem_tsquery_selec(TSQuery query, Datum *mcelem, int nmcelem,
208 : : float4 *numbers, int nnumbers)
209 : : {
210 : : float4 minfreq;
211 : : TextFreq *lookup;
212 : : Selectivity selec;
213 : : 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 [ - + ]: 495 : if (nnumbers != nmcelem + 2)
5006 tgl@sss.pgh.pa.us 224 :UBC 0 : return tsquery_opr_selec_no_stats(query);
225 : :
226 : : /*
227 : : * Transpose the data into a single array so we can use bsearch().
228 : : */
5686 tgl@sss.pgh.pa.us 229 :CBC 495 : lookup = (TextFreq *) palloc(sizeof(TextFreq) * nmcelem);
230 [ + + ]: 495495 : 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 [ + - - + ]: 495000 : Assert(!VARATT_IS_COMPRESSED(mcelem[i]) && !VARATT_IS_EXTERNAL(mcelem[i]));
237 : 495000 : lookup[i].element = (text *) DatumGetPointer(mcelem[i]);
238 : 495000 : lookup[i].frequency = numbers[i];
239 : : }
240 : :
241 : : /*
242 : : * Grab the lowest frequency. compute_tsvector_stats() stored it for us in
243 : : * the one before the last cell of the Numbers array. See ts_typanalyze.c
244 : : */
245 : 495 : minfreq = numbers[nnumbers - 2];
246 : :
247 : 495 : selec = tsquery_opr_selec(GETQUERY(query), GETOPERAND(query), lookup,
248 : : nmcelem, minfreq);
249 : :
250 : 495 : pfree(lookup);
251 : :
252 : 495 : return selec;
253 : : }
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 : 1539 : tsquery_opr_selec(QueryItem *item, char *operand,
279 : : TextFreq *lookup, int length, float4 minfreq)
280 : : {
281 : : Selectivity selec;
282 : :
283 : : /* since this function recurses, it could be driven to stack overflow */
284 : 1539 : check_stack_depth();
285 : :
286 [ + + ]: 1539 : if (item->type == QI_VAL)
287 : : {
288 : 921 : QueryOperand *oper = (QueryOperand *) item;
289 : : LexemeKey key;
290 : :
291 : : /*
292 : : * Prepare the key for bsearch().
293 : : */
294 : 921 : key.lexeme = operand + oper->distance;
295 : 921 : key.length = oper->length;
296 : :
5005 297 [ + + ]: 921 : if (oper->prefix)
298 : : {
299 : : /* Prefix match, ie the query item is lexeme:* */
300 : : Selectivity matched,
301 : : allmces;
302 : : 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 [ + + - + ]: 51 : if (lookup == NULL || length < 100)
320 : 21 : return (Selectivity) (DEFAULT_TS_MATCH_SEL * 4);
321 : :
4233 322 : 36 : matched = allmces = 0;
323 : 36 : n_matched = 0;
5005 324 [ + + ]: 36036 : for (i = 0; i < length; i++)
325 : : {
326 : 36000 : TextFreq *t = lookup + i;
327 [ - + - - : 36000 : int tlen = VARSIZE_ANY_EXHDR(t->element);
- - - - -
+ ]
328 : :
329 [ + - ]: 36000 : if (tlen >= key.length &&
330 [ + + ]: 36000 : strncmp(key.lexeme, VARDATA_ANY(t->element),
331 [ - + ]: 36000 : key.length) == 0)
332 : : {
4233 333 : 1296 : matched += t->frequency - matched * t->frequency;
334 : 1296 : n_matched++;
335 : : }
336 : 36000 : allmces += t->frequency - allmces * t->frequency;
337 : : }
338 : :
339 : : /* Clamp to ensure sanity in the face of roundoff error */
340 [ - + - + ]: 36 : CLAMP_PROBABILITY(matched);
341 [ - + - + ]: 36 : CLAMP_PROBABILITY(allmces);
342 : :
343 : 36 : 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 [ - + - + : 36 : selec = Max(Min(DEFAULT_TS_MATCH_SEL, minfreq / 2), selec);
- - ]
352 : : }
353 : : else
354 : : {
355 : : /* Regular exact lexeme match */
356 : : TextFreq *searchres;
357 : :
358 : : /* If no stats for the variable, use DEFAULT_TS_MATCH_SEL */
5005 359 [ + + ]: 870 : if (lookup == NULL)
360 : 6 : return (Selectivity) DEFAULT_TS_MATCH_SEL;
361 : :
362 : 864 : searchres = (TextFreq *) bsearch(&key, lookup, length,
363 : : sizeof(TextFreq),
364 : : compare_lexeme_textfreq);
365 : :
366 [ + + ]: 864 : 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 : 804 : selec = searchres->frequency;
373 : : }
374 : : else
375 : : {
376 : : /*
377 : : * The element is not in MCELEM. Punt, but assume that the
378 : : * selectivity cannot be more than minfreq / 2.
379 : : */
380 [ - + ]: 60 : selec = Min(DEFAULT_TS_MATCH_SEL, minfreq / 2);
381 : : }
382 : : }
383 : : }
384 : : else
385 : : {
386 : : /* Current TSQuery node is an operator */
387 : : Selectivity s1,
388 : : s2;
389 : :
390 [ + + + - ]: 618 : switch (item->qoperator.oper)
391 : : {
392 : 210 : case OP_NOT:
393 : 210 : selec = 1.0 - tsquery_opr_selec(item + 1, operand,
394 : : lookup, length, minfreq);
395 : 210 : break;
396 : :
2929 teodor@sigaev.ru 397 : 285 : case OP_PHRASE:
398 : : case OP_AND:
5005 tgl@sss.pgh.pa.us 399 : 285 : s1 = tsquery_opr_selec(item + 1, operand,
400 : : lookup, length, minfreq);
401 : 285 : s2 = tsquery_opr_selec(item + item->qoperator.left, operand,
402 : : lookup, length, minfreq);
403 : 285 : selec = s1 * s2;
404 : 285 : break;
405 : :
406 : 123 : case OP_OR:
407 : 123 : s1 = tsquery_opr_selec(item + 1, operand,
408 : : lookup, length, minfreq);
409 : 123 : s2 = tsquery_opr_selec(item + item->qoperator.left, operand,
410 : : lookup, length, minfreq);
411 : 123 : selec = s1 + s2 - s1 * s2;
412 : 123 : break;
413 : :
5005 tgl@sss.pgh.pa.us 414 :UBC 0 : default:
415 [ # # ]: 0 : elog(ERROR, "unrecognized operator: %d", item->qoperator.oper);
416 : : selec = 0; /* keep compiler quiet */
417 : : break;
418 : : }
419 : : }
420 : :
421 : : /* Clamp intermediate results to stay sane despite roundoff error */
5686 tgl@sss.pgh.pa.us 422 [ - + - + ]:CBC 1518 : CLAMP_PROBABILITY(selec);
423 : :
424 : 1518 : return selec;
425 : : }
426 : :
427 : : /*
428 : : * bsearch() comparator for a lexeme (non-NULL terminated string with length)
429 : : * and a TextFreq. Use length, then byte-for-byte comparison, because that's
430 : : * how ANALYZE code sorted data before storing it in a statistic tuple.
431 : : * See ts_typanalyze.c for details.
432 : : */
433 : : static int
434 : 6672 : compare_lexeme_textfreq(const void *e1, const void *e2)
435 : : {
5421 bruce@momjian.us 436 : 6672 : const LexemeKey *key = (const LexemeKey *) e1;
437 : 6672 : const TextFreq *t = (const TextFreq *) e2;
438 : : int len1,
439 : : len2;
440 : :
5686 tgl@sss.pgh.pa.us 441 : 6672 : len1 = key->length;
442 [ - + - - : 6672 : len2 = VARSIZE_ANY_EXHDR(t->element);
- - - - -
+ ]
443 : :
444 : : /* Compare lengths first, possibly avoiding a strncmp call */
445 [ + + ]: 6672 : if (len1 > len2)
446 : 540 : return 1;
447 [ - + ]: 6132 : else if (len1 < len2)
5686 tgl@sss.pgh.pa.us 448 :UBC 0 : return -1;
449 : :
450 : : /* Fall back on byte-for-byte comparison */
5686 tgl@sss.pgh.pa.us 451 [ - + ]:CBC 6132 : return strncmp(key->lexeme, VARDATA_ANY(t->element), len1);
452 : : }
|
