| 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 |
} |