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-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 {
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);
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
68 {
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))
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);
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  */
138 Datum
140 {
141  /* for the moment we just punt */
143 }
144 
145 
146 /*
147  * @@ selectivity for tsvector var vs tsquery constant
148  */
149 static 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,
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  */
206 static 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(mcelem[i]) && !VARATT_IS_EXTERNAL(mcelem[i]));
237  lookup[i].element = (text *) DatumGetPointer(mcelem[i]);
238  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  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  */
277 static 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 */
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)
361 
362  searchres = (TextFreq *) bsearch(&key, lookup, length,
363  sizeof(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. Punt, but assume that the
378  * selectivity cannot be more than minfreq / 2.
379  */
380  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  switch (item->qoperator.oper)
391  {
392  case OP_NOT:
393  selec = 1.0 - tsquery_opr_selec(item + 1, operand,
394  lookup, length, minfreq);
395  break;
396 
397  case OP_PHRASE:
398  case OP_AND:
399  s1 = tsquery_opr_selec(item + 1, operand,
400  lookup, length, minfreq);
401  s2 = tsquery_opr_selec(item + item->qoperator.left, operand,
402  lookup, length, minfreq);
403  selec = s1 * s2;
404  break;
405 
406  case OP_OR:
407  s1 = tsquery_opr_selec(item + 1, operand,
408  lookup, length, minfreq);
409  s2 = tsquery_opr_selec(item + item->qoperator.left, operand,
410  lookup, length, minfreq);
411  selec = s1 + s2 - s1 * s2;
412  break;
413 
414  default:
415  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 */
422  CLAMP_PROBABILITY(selec);
423 
424  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 compare_lexeme_textfreq(const void *e1, const void *e2)
435 {
436  const LexemeKey *key = (const LexemeKey *) e1;
437  const TextFreq *t = (const TextFreq *) e2;
438  int len1,
439  len2;
440 
441  len1 = key->length;
442  len2 = VARSIZE_ANY_EXHDR(t->element);
443 
444  /* Compare lengths first, possibly avoiding a strncmp call */
445  if (len1 > len2)
446  return 1;
447  else if (len1 < len2)
448  return -1;
449 
450  /* Fall back on byte-for-byte comparison */
451  return strncmp(key->lexeme, VARDATA_ANY(t->element), len1);
452 }
#define GETQUERY(x)
Definition: _int.h:157
#define Min(x, y)
Definition: c.h:1004
#define Max(x, y)
Definition: c.h:998
#define Assert(condition)
Definition: c.h:858
double float8
Definition: c.h:630
float float4
Definition: c.h:629
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:224
#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
#define HeapTupleIsValid(tuple)
Definition: htup.h:78
#define GETSTRUCT(TUP)
Definition: htup_details.h:653
int i
Definition: isn.c:73
void free_attstatsslot(AttStatsSlot *sslot)
Definition: lsyscache.c:3344
bool get_attstatsslot(AttStatsSlot *sslot, HeapTuple statstuple, int reqkind, Oid reqop, int flags)
Definition: lsyscache.c:3234
#define ATTSTATSSLOT_NUMBERS
Definition: lsyscache.h:43
#define ATTSTATSSLOT_VALUES
Definition: lsyscache.h:42
#define GETOPERAND(x)
Definition: ltree.h:165
void pfree(void *pointer)
Definition: mcxt.c:1520
void * palloc(Size size)
Definition: mcxt.c:1316
#define IsA(nodeptr, _type_)
Definition: nodes.h:158
double Selectivity
Definition: nodes.h:250
Operator oper(ParseState *pstate, List *opname, Oid ltypeId, Oid rtypeId, bool noError, int location)
Definition: parse_oper.c:370
FormData_pg_statistic * Form_pg_statistic
Definition: pg_statistic.h:135
void check_stack_depth(void)
Definition: postgres.c:3531
uintptr_t Datum
Definition: postgres.h:64
static Pointer DatumGetPointer(Datum X)
Definition: postgres.h:312
#define InvalidOid
Definition: postgres_ext.h:36
unsigned int Oid
Definition: postgres_ext.h:31
char * s1
char * s2
tree ctl root
Definition: radixtree.h:1884
bool get_restriction_variable(PlannerInfo *root, List *args, int varRelid, VariableStatData *vardata, Node **other, bool *varonleft)
Definition: selfuncs.c:4883
#define ReleaseVariableStats(vardata)
Definition: selfuncs.h:99
#define CLAMP_PROBABILITY(p)
Definition: selfuncs.h:63
Datum * values
Definition: lsyscache.h:53
float4 * numbers
Definition: lsyscache.h:56
int nnumbers
Definition: lsyscache.h:57
char * lexeme
Definition: ts_selfuncs.c:44
int length
Definition: ts_selfuncs.c:45
Definition: pg_list.h:54
Definition: nodes.h:129
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:687
#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:434
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
#define VARATT_IS_COMPRESSED(PTR)
Definition: varatt.h:288
#define VARDATA_ANY(PTR)
Definition: varatt.h:324
#define VARATT_IS_EXTERNAL(PTR)
Definition: varatt.h:289
#define VARSIZE_ANY_EXHDR(PTR)
Definition: varatt.h:317