PostgreSQL Source Code: src/backend/tsearch/ts_selfuncs.c Source File

PostgreSQL Source Code git master
ts_selfuncs.c
Go to the documentation of this file.
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
48static Selectivity tsquerysel(VariableStatData *vardata, Datum constval);
49static Selectivity mcelem_tsquery_selec(TSQuery query,
50 Datum *mcelem, int nmcelem,
51 float4 *numbers, int nnumbers);
52static Selectivity tsquery_opr_selec(QueryItem *item, char *operand,
53 TextFreq *lookup, int length, float4 minfreq);
54static 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 */
66Datum
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 if (((Const *) other)->consttype == TSQUERYOID)
113 {
114 /* tsvector @@ tsquery or the other way around */
115 Assert(vardata.vartype == TSVECTOROID);
116
117 selec = tsquerysel(&vardata, ((Const *) other)->constvalue);
118 }
119 else
120 {
121 /* If we can't see the query structure, must punt */
122 selec = DEFAULT_TS_MATCH_SEL;
123 }
124
125 ReleaseVariableStats(vardata);
126
127 CLAMP_PROBABILITY(selec);
128
129 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 */
138Datum
139 tsmatchjoinsel(PG_FUNCTION_ARGS)
140{
141 /* for the moment we just punt */
142 PG_RETURN_FLOAT8(DEFAULT_TS_MATCH_SEL);
143}
144
145
146/*
147 * @@ selectivity for tsvector var vs tsquery constant
148 */
149static Selectivity
150 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 */
156 query = DatumGetTSQuery(constval);
157
158 /* Empty query matches nothing */
159 if (query->size == 0)
160 return (Selectivity) 0.0;
161
162 if (HeapTupleIsValid(vardata->statsTuple))
163 {
164 Form_pg_statistic stats;
165 AttStatsSlot sslot;
166
167 stats = (Form_pg_statistic) GETSTRUCT(vardata->statsTuple);
168
169 /* MCELEM will be an array of TEXT elements for a tsvector column */
170 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 selec = mcelem_tsquery_selec(query, sslot.values, sslot.nvalues,
179 sslot.numbers, sslot.nnumbers);
180 free_attstatsslot(&sslot);
181 }
182 else
183 {
184 /* No most-common-elements info, so do without */
185 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 selec *= (1.0 - stats->stanullfrac);
192 }
193 else
194 {
195 /* No stats at all, so do without */
196 selec = tsquery_opr_selec_no_stats(query);
197 /* we assume no nulls here, so no stanullfrac correction */
198 }
199
200 return selec;
201}
202
203/*
204 * Extract data from the pg_statistic arrays into useful format.
205 */
206static Selectivity
207 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 if (nnumbers != nmcelem + 2)
224 return tsquery_opr_selec_no_stats(query);
225
226 /*
227 * Transpose the data into a single array so we can use bsearch().
228 */
229 lookup = (TextFreq *) palloc(sizeof(TextFreq) * nmcelem);
230 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 Assert(!VARATT_IS_COMPRESSED(DatumGetPointer(mcelem[i])) && !VARATT_IS_EXTERNAL(DatumGetPointer(mcelem[i])));
237 lookup[i].element = (text *) DatumGetPointer(mcelem[i]);
238 lookup[i].frequency = numbers[i];
239 }
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 minfreq = numbers[nnumbers - 2];
246
247 selec = tsquery_opr_selec(GETQUERY(query), GETOPERAND(query), lookup,
248 nmcelem, minfreq);
249
250 pfree(lookup);
251
252 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 */
277static Selectivity
278 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 check_stack_depth();
285
286 if (item->type == QI_VAL)
287 {
288 QueryOperand *oper = (QueryOperand *) item;
289 LexemeKey key;
290
291 /*
292 * Prepare the key for bsearch().
293 */
294 key.lexeme = operand + oper->distance;
295 key.length = oper->length;
296
297 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 if (lookup == NULL || length < 100)
320 return (Selectivity) (DEFAULT_TS_MATCH_SEL * 4);
321
322 matched = allmces = 0;
323 n_matched = 0;
324 for (i = 0; i < length; i++)
325 {
326 TextFreq *t = lookup + i;
327 int tlen = VARSIZE_ANY_EXHDR(t->element);
328
329 if (tlen >= key.length &&
330 strncmp(key.lexeme, VARDATA_ANY(t->element),
331 key.length) == 0)
332 {
333 matched += t->frequency - matched * t->frequency;
334 n_matched++;
335 }
336 allmces += t->frequency - allmces * t->frequency;
337 }
338
339 /* Clamp to ensure sanity in the face of roundoff error */
340 CLAMP_PROBABILITY(matched);
341 CLAMP_PROBABILITY(allmces);
342
343 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 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 */
359 if (lookup == NULL)
360 return (Selectivity) DEFAULT_TS_MATCH_SEL;
361
362 searchres = (TextFreq *) bsearch(&key, lookup, length,
363 sizeof(TextFreq),
364 compare_lexeme_textfreq);
365
366 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 selec = searchres->frequency;
373 }
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 selec = Min(DEFAULT_TS_MATCH_SEL, minfreq / 2);
384 }
385 }
386 }
387 else
388 {
389 /* Current TSQuery node is an operator */
390 Selectivity s1,
391 s2;
392
393 switch (item->qoperator.oper)
394 {
395 case OP_NOT:
396 selec = 1.0 - tsquery_opr_selec(item + 1, operand,
397 lookup, length, minfreq);
398 break;
399
400 case OP_PHRASE:
401 case OP_AND:
402 s1 = tsquery_opr_selec(item + 1, operand,
403 lookup, length, minfreq);
404 s2 = tsquery_opr_selec(item + item->qoperator.left, operand,
405 lookup, length, minfreq);
406 selec = s1 * s2;
407 break;
408
409 case OP_OR:
410 s1 = tsquery_opr_selec(item + 1, operand,
411 lookup, length, minfreq);
412 s2 = tsquery_opr_selec(item + item->qoperator.left, operand,
413 lookup, length, minfreq);
414 selec = s1 + s2 - s1 * s2;
415 break;
416
417 default:
418 elog(ERROR, "unrecognized operator: %d", item->qoperator.oper);
419 selec = 0; /* keep compiler quiet */
420 break;
421 }
422 }
423
424 /* Clamp intermediate results to stay sane despite roundoff error */
425 CLAMP_PROBABILITY(selec);
426
427 return selec;
428}
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 */
436static int
437 compare_lexeme_textfreq(const void *e1, const void *e2)
438{
439 const LexemeKey *key = (const LexemeKey *) e1;
440 const TextFreq *t = (const TextFreq *) e2;
441 int len1,
442 len2;
443
444 len1 = key->length;
445 len2 = VARSIZE_ANY_EXHDR(t->element);
446
447 /* Compare lengths first, possibly avoiding a strncmp call */
448 if (len1 > len2)
449 return 1;
450 else if (len1 < len2)
451 return -1;
452
453 /* Fall back on byte-for-byte comparison */
454 return strncmp(key->lexeme, VARDATA_ANY(t->element), len1);
455}
#define GETQUERY(x)
Definition: _int.h:157
#define Min(x, y)
Definition: c.h:1003
#define Max(x, y)
Definition: c.h:997
double float8
Definition: c.h:635
float float4
Definition: c.h:634
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:226
#define PG_GETARG_OID(n)
Definition: fmgr.h:275
#define PG_RETURN_FLOAT8(x)
Definition: fmgr.h:367
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:276
#define PG_GETARG_INT32(n)
Definition: fmgr.h:269
#define PG_FUNCTION_ARGS
Definition: fmgr.h:193
Assert(PointerIsAligned(start, uint64))
#define HeapTupleIsValid(tuple)
Definition: htup.h:78
static void * GETSTRUCT(const HeapTupleData *tuple)
Definition: htup_details.h:728
i
int i
Definition: isn.c:77
void free_attstatsslot(AttStatsSlot *sslot)
Definition: lsyscache.c:3511
bool get_attstatsslot(AttStatsSlot *sslot, HeapTuple statstuple, int reqkind, Oid reqop, int flags)
Definition: lsyscache.c:3401
#define ATTSTATSSLOT_NUMBERS
Definition: lsyscache.h:44
#define ATTSTATSSLOT_VALUES
Definition: lsyscache.h:43
#define GETOPERAND(x)
Definition: ltree.h:165
void pfree(void *pointer)
Definition: mcxt.c:1594
void * palloc(Size size)
Definition: mcxt.c:1365
args
#define IsA(nodeptr, _type_)
Definition: nodes.h:164
double Selectivity
Definition: nodes.h:260
Operator oper(ParseState *pstate, List *opname, Oid ltypeId, Oid rtypeId, bool noError, int location)
Definition: parse_oper.c:371
FormData_pg_statistic * Form_pg_statistic
Definition: pg_statistic.h:135
uint64_t Datum
Definition: postgres.h:70
static Pointer DatumGetPointer(Datum X)
Definition: postgres.h:322
#define InvalidOid
Definition: postgres_ext.h:37
unsigned int Oid
Definition: postgres_ext.h:32
char * s1
char * s2
tree ctl root
Definition: radixtree.h:1857
bool get_restriction_variable(PlannerInfo *root, List *args, int varRelid, VariableStatData *vardata, Node **other, bool *varonleft)
Definition: selfuncs.c:5180
#define ReleaseVariableStats(vardata)
Definition: selfuncs.h:101
#define CLAMP_PROBABILITY(p)
Definition: selfuncs.h:63
void check_stack_depth(void)
Definition: stack_depth.c:95
Datum * values
Definition: lsyscache.h:54
float4 * numbers
Definition: lsyscache.h:57
int nnumbers
Definition: lsyscache.h:58
int nvalues
Definition: lsyscache.h:55
Definition: primnodes.h:324
char * lexeme
Definition: ts_selfuncs.c:44
int length
Definition: ts_selfuncs.c:45
Definition: pg_list.h:54
Definition: nodes.h:135
int8 oper
Definition: ts_type.h:195
uint32 left
Definition: ts_type.h:197
int32 size
Definition: ts_type.h:221
text * element
Definition: ts_selfuncs.c:37
float4 frequency
Definition: ts_selfuncs.c:38
HeapTuple statsTuple
Definition: selfuncs.h:89
Definition: zic.c:304
Definition: c.h:692
#define tsquery_opr_selec_no_stats(query)
Definition: ts_selfuncs.c:56
#define DEFAULT_TS_MATCH_SEL
Definition: ts_selfuncs.c:32
Datum tsmatchjoinsel(PG_FUNCTION_ARGS)
Definition: ts_selfuncs.c:139
static Selectivity tsquery_opr_selec(QueryItem *item, char *operand, TextFreq *lookup, int length, float4 minfreq)
Definition: ts_selfuncs.c:278
static Selectivity tsquerysel(VariableStatData *vardata, Datum constval)
Definition: ts_selfuncs.c:150
Datum tsmatchsel(PG_FUNCTION_ARGS)
Definition: ts_selfuncs.c:67
static int compare_lexeme_textfreq(const void *e1, const void *e2)
Definition: ts_selfuncs.c:437
static Selectivity mcelem_tsquery_selec(TSQuery query, Datum *mcelem, int nmcelem, float4 *numbers, int nnumbers)
Definition: ts_selfuncs.c:207
static TSQuery DatumGetTSQuery(Datum X)
Definition: ts_type.h:249
#define QI_VAL
Definition: ts_type.h:149
#define OP_AND
Definition: ts_type.h:180
#define OP_PHRASE
Definition: ts_type.h:182
#define OP_OR
Definition: ts_type.h:181
#define OP_NOT
Definition: ts_type.h:179
QueryOperator qoperator
Definition: ts_type.h:209
QueryItemType type
Definition: ts_type.h:208
static Size VARSIZE_ANY_EXHDR(const void *PTR)
Definition: varatt.h:472
static bool VARATT_IS_EXTERNAL(const void *PTR)
Definition: varatt.h:354
static char * VARDATA_ANY(const void *PTR)
Definition: varatt.h:486
static bool VARATT_IS_COMPRESSED(const void *PTR)
Definition: varatt.h:347

AltStyle によって変換されたページ (->オリジナル) /