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