Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * like_support.c
4 : * Planner support functions for LIKE, regex, and related operators.
5 : *
6 : * These routines handle special optimization of operators that can be
7 : * used with index scans even though they are not known to the executor's
8 : * indexscan machinery. The key idea is that these operators allow us
9 : * to derive approximate indexscan qual clauses, such that any tuples
10 : * that pass the operator clause itself must also satisfy the simpler
11 : * indexscan condition(s). Then we can use the indexscan machinery
12 : * to avoid scanning as much of the table as we'd otherwise have to,
13 : * while applying the original operator as a qpqual condition to ensure
14 : * we deliver only the tuples we want. (In essence, we're using a regular
15 : * index as if it were a lossy index.)
16 : *
17 : * An example of what we're doing is
18 : * textfield LIKE 'abc%def'
19 : * from which we can generate the indexscanable conditions
20 : * textfield >= 'abc' AND textfield < 'abd'
21 : * which allow efficient scanning of an index on textfield.
22 : * (In reality, character set and collation issues make the transformation
23 : * from LIKE to indexscan limits rather harder than one might think ...
24 : * but that's the basic idea.)
25 : *
26 : * Portions Copyright (c) 1996-2020, PostgreSQL Global Development Group
27 : * Portions Copyright (c) 1994, Regents of the University of California
28 : *
29 : *
30 : * IDENTIFICATION
31 : * src/backend/utils/adt/like_support.c
32 : *
33 : *-------------------------------------------------------------------------
34 : */
35 : #include "postgres.h"
36 :
37 : #include <math.h>
38 :
39 : #include "access/htup_details.h"
40 : #include "access/stratnum.h"
41 : #include "catalog/pg_collation.h"
42 : #include "catalog/pg_operator.h"
43 : #include "catalog/pg_opfamily.h"
44 : #include "catalog/pg_statistic.h"
45 : #include "catalog/pg_type.h"
46 : #include "mb/pg_wchar.h"
47 : #include "nodes/makefuncs.h"
48 : #include "nodes/nodeFuncs.h"
49 : #include "nodes/supportnodes.h"
50 : #include "utils/builtins.h"
51 : #include "utils/datum.h"
52 : #include "utils/lsyscache.h"
53 : #include "utils/pg_locale.h"
54 : #include "utils/selfuncs.h"
55 : #include "utils/varlena.h"
56 :
57 :
58 : typedef enum
59 : {
60 : Pattern_Type_Like,
61 : Pattern_Type_Like_IC,
62 : Pattern_Type_Regex,
63 : Pattern_Type_Regex_IC,
64 : Pattern_Type_Prefix
65 : } Pattern_Type;
66 :
67 : typedef enum
68 : {
69 : Pattern_Prefix_None, Pattern_Prefix_Partial, Pattern_Prefix_Exact
70 : } Pattern_Prefix_Status;
71 :
72 : static Node *like_regex_support(Node *rawreq, Pattern_Type ptype);
73 : static List *match_pattern_prefix(Node *leftop,
74 : Node *rightop,
75 : Pattern_Type ptype,
76 : Oid expr_coll,
77 : Oid opfamily,
78 : Oid indexcollation);
79 : static double patternsel_common(PlannerInfo *root,
80 : Oid oprid,
81 : Oid opfuncid,
82 : List *args,
83 : int varRelid,
84 : Oid collation,
85 : Pattern_Type ptype,
86 : bool negate);
87 : static Pattern_Prefix_Status pattern_fixed_prefix(Const *patt,
88 : Pattern_Type ptype,
89 : Oid collation,
90 : Const **prefix,
91 : Selectivity *rest_selec);
92 : static Selectivity prefix_selectivity(PlannerInfo *root,
93 : VariableStatData *vardata,
94 : Oid eqopr, Oid ltopr, Oid geopr,
95 : Const *prefixcon);
96 : static Selectivity like_selectivity(const char *patt, int pattlen,
97 : bool case_insensitive);
98 : static Selectivity regex_selectivity(const char *patt, int pattlen,
99 : bool case_insensitive,
100 : int fixed_prefix_len);
101 : static int pattern_char_isalpha(char c, bool is_multibyte,
102 : pg_locale_t locale, bool locale_is_c);
103 : static Const *make_greater_string(const Const *str_const, FmgrInfo *ltproc,
104 : Oid collation);
105 : static Datum string_to_datum(const char *str, Oid datatype);
106 : static Const *string_to_const(const char *str, Oid datatype);
107 : static Const *string_to_bytea_const(const char *str, size_t str_len);
108 :
109 :
110 : /*
111 : * Planner support functions for LIKE, regex, and related operators
112 : */
113 : Datum
114 4446 : textlike_support(PG_FUNCTION_ARGS)
115 : {
116 4446 : Node *rawreq = (Node *) PG_GETARG_POINTER(0);
117 :
118 4446 : PG_RETURN_POINTER(like_regex_support(rawreq, Pattern_Type_Like));
119 : }
120 :
121 : Datum
122 96 : texticlike_support(PG_FUNCTION_ARGS)
123 : {
124 96 : Node *rawreq = (Node *) PG_GETARG_POINTER(0);
125 :
126 96 : PG_RETURN_POINTER(like_regex_support(rawreq, Pattern_Type_Like_IC));
127 : }
128 :
129 : Datum
130 8198 : textregexeq_support(PG_FUNCTION_ARGS)
131 : {
132 8198 : Node *rawreq = (Node *) PG_GETARG_POINTER(0);
133 :
134 8198 : PG_RETURN_POINTER(like_regex_support(rawreq, Pattern_Type_Regex));
135 : }
136 :
137 : Datum
138 64 : texticregexeq_support(PG_FUNCTION_ARGS)
139 : {
140 64 : Node *rawreq = (Node *) PG_GETARG_POINTER(0);
141 :
142 64 : PG_RETURN_POINTER(like_regex_support(rawreq, Pattern_Type_Regex_IC));
143 : }
144 :
145 : /* Common code for the above */
146 : static Node *
147 12804 : like_regex_support(Node *rawreq, Pattern_Type ptype)
148 : {
149 12804 : Node *ret = NULL;
150 :
151 12804 : if (IsA(rawreq, SupportRequestSelectivity))
152 : {
153 : /*
154 : * Make a selectivity estimate for a function call, just as we'd do if
155 : * the call was via the corresponding operator.
156 : */
157 0 : SupportRequestSelectivity *req = (SupportRequestSelectivity *) rawreq;
158 : Selectivity s1;
159 :
160 0 : if (req->is_join)
161 : {
162 : /*
163 : * For the moment we just punt. If patternjoinsel is ever
164 : * improved to do better, this should be made to call it.
165 : */
166 0 : s1 = DEFAULT_MATCH_SEL;
167 : }
168 : else
169 : {
170 : /* Share code with operator restriction selectivity functions */
171 0 : s1 = patternsel_common(req->root,
172 : InvalidOid,
173 : req->funcid,
174 : req->args,
175 : req->varRelid,
176 : req->inputcollid,
177 : ptype,
178 : false);
179 : }
180 0 : req->selectivity = s1;
181 0 : ret = (Node *) req;
182 : }
183 12804 : else if (IsA(rawreq, SupportRequestIndexCondition))
184 : {
185 : /* Try to convert operator/function call to index conditions */
186 3466 : SupportRequestIndexCondition *req = (SupportRequestIndexCondition *) rawreq;
187 :
188 : /*
189 : * Currently we have no "reverse" match operators with the pattern on
190 : * the left, so we only need consider cases with the indexkey on the
191 : * left.
192 : */
193 3466 : if (req->indexarg != 0)
194 0 : return NULL;
195 :
196 3466 : if (is_opclause(req->node))
197 : {
198 3466 : OpExpr *clause = (OpExpr *) req->node;
199 :
200 : Assert(list_length(clause->args) == 2);
201 : ret = (Node *)
202 3466 : match_pattern_prefix((Node *) linitial(clause->args),
203 3466 : (Node *) lsecond(clause->args),
204 : ptype,
205 : clause->inputcollid,
206 : req->opfamily,
207 : req->indexcollation);
208 : }
209 0 : else if (is_funcclause(req->node)) /* be paranoid */
210 : {
211 0 : FuncExpr *clause = (FuncExpr *) req->node;
212 :
213 : Assert(list_length(clause->args) == 2);
214 : ret = (Node *)
215 0 : match_pattern_prefix((Node *) linitial(clause->args),
216 0 : (Node *) lsecond(clause->args),
217 : ptype,
218 : clause->inputcollid,
219 : req->opfamily,
220 : req->indexcollation);
221 : }
222 : }
223 :
224 12804 : return ret;
225 : }
226 :
227 : /*
228 : * match_pattern_prefix
229 : * Try to generate an indexqual for a LIKE or regex operator.
230 : */
231 : static List *
232 3466 : match_pattern_prefix(Node *leftop,
233 : Node *rightop,
234 : Pattern_Type ptype,
235 : Oid expr_coll,
236 : Oid opfamily,
237 : Oid indexcollation)
238 : {
239 : List *result;
240 : Const *patt;
241 : Const *prefix;
242 : Pattern_Prefix_Status pstatus;
243 : Oid ldatatype;
244 : Oid rdatatype;
245 : Oid eqopr;
246 : Oid ltopr;
247 : Oid geopr;
248 : bool collation_aware;
249 : Expr *expr;
250 : FmgrInfo ltproc;
251 : Const *greaterstr;
252 :
253 : /*
254 : * Can't do anything with a non-constant or NULL pattern argument.
255 : *
256 : * Note that since we restrict ourselves to cases with a hard constant on
257 : * the RHS, it's a-fortiori a pseudoconstant, and we don't need to worry
258 : * about verifying that.
259 : */
260 3466 : if (!IsA(rightop, Const) ||
261 3466 : ((Const *) rightop)->constisnull)
262 0 : return NIL;
263 3466 : patt = (Const *) rightop;
264 :
265 : /*
266 : * Not supported if the expression collation is nondeterministic. The
267 : * optimized equality or prefix tests use bytewise comparisons, which is
268 : * not consistent with nondeterministic collations. The actual
269 : * pattern-matching implementation functions will later error out that
270 : * pattern-matching is not supported with nondeterministic collations. (We
271 : * could also error out here, but by doing it later we get more precise
272 : * error messages.) (It should be possible to support at least
273 : * Pattern_Prefix_Exact, but no point as long as the actual
274 : * pattern-matching implementations don't support it.)
275 : *
276 : * expr_coll is not set for a non-collation-aware data type such as bytea.
277 : */
278 3466 : if (expr_coll && !get_collation_isdeterministic(expr_coll))
279 0 : return NIL;
280 :
281 : /*
282 : * Try to extract a fixed prefix from the pattern.
283 : */
284 3466 : pstatus = pattern_fixed_prefix(patt, ptype, expr_coll,
285 : &prefix, NULL);
286 :
287 : /* fail if no fixed prefix */
288 3466 : if (pstatus == Pattern_Prefix_None)
289 118 : return NIL;
290 :
291 : /*
292 : * Identify the operators we want to use, based on the type of the
293 : * left-hand argument. Usually these are just the type's regular
294 : * comparison operators, but if we are considering one of the semi-legacy
295 : * "pattern" opclasses, use the "pattern" operators instead. Those are
296 : * not collation-sensitive but always use C collation, as we want. The
297 : * selected operators also determine the needed type of the prefix
298 : * constant.
299 : */
300 3348 : ldatatype = exprType(leftop);
301 3348 : switch (ldatatype)
302 : {
303 24 : case TEXTOID:
304 24 : if (opfamily == TEXT_PATTERN_BTREE_FAM_OID ||
305 : opfamily == TEXT_SPGIST_FAM_OID)
306 : {
307 0 : eqopr = TextEqualOperator;
308 0 : ltopr = TextPatternLessOperator;
309 0 : geopr = TextPatternGreaterEqualOperator;
310 0 : collation_aware = false;
311 : }
312 : else
313 : {
314 24 : eqopr = TextEqualOperator;
315 24 : ltopr = TextLessOperator;
316 24 : geopr = TextGreaterEqualOperator;
317 24 : collation_aware = true;
318 : }
319 24 : rdatatype = TEXTOID;
320 24 : break;
321 3308 : case NAMEOID:
322 :
323 : /*
324 : * Note that here, we need the RHS type to be text, so that the
325 : * comparison value isn't improperly truncated to NAMEDATALEN.
326 : */
327 3308 : eqopr = NameEqualTextOperator;
328 3308 : ltopr = NameLessTextOperator;
329 3308 : geopr = NameGreaterEqualTextOperator;
330 3308 : collation_aware = true;
331 3308 : rdatatype = TEXTOID;
332 3308 : break;
333 16 : case BPCHAROID:
334 16 : if (opfamily == BPCHAR_PATTERN_BTREE_FAM_OID)
335 : {
336 0 : eqopr = BpcharEqualOperator;
337 0 : ltopr = BpcharPatternLessOperator;
338 0 : geopr = BpcharPatternGreaterEqualOperator;
339 0 : collation_aware = false;
340 : }
341 : else
342 : {
343 16 : eqopr = BpcharEqualOperator;
344 16 : ltopr = BpcharLessOperator;
345 16 : geopr = BpcharGreaterEqualOperator;
346 16 : collation_aware = true;
347 : }
348 16 : rdatatype = BPCHAROID;
349 16 : break;
350 0 : case BYTEAOID:
351 0 : eqopr = ByteaEqualOperator;
352 0 : ltopr = ByteaLessOperator;
353 0 : geopr = ByteaGreaterEqualOperator;
354 0 : collation_aware = false;
355 0 : rdatatype = BYTEAOID;
356 0 : break;
357 0 : default:
358 : /* Can't get here unless we're attached to the wrong operator */
359 0 : return NIL;
360 : }
361 :
362 : /*
363 : * If necessary, verify that the index's collation behavior is compatible.
364 : * For an exact-match case, we don't have to be picky. Otherwise, insist
365 : * that the index collation be "C". Note that here we are looking at the
366 : * index's collation, not the expression's collation -- this test is *not*
367 : * dependent on the LIKE/regex operator's collation.
368 : */
369 3348 : if (collation_aware)
370 : {
371 4328 : if (!(pstatus == Pattern_Prefix_Exact ||
372 980 : lc_collate_is_c(indexcollation)))
373 8 : return NIL;
374 : }
375 :
376 : /*
377 : * If necessary, coerce the prefix constant to the right type. The given
378 : * prefix constant is either text or bytea type, therefore the only case
379 : * where we need to do anything is when converting text to bpchar. Those
380 : * two types are binary-compatible, so relabeling the Const node is
381 : * sufficient.
382 : */
383 3340 : if (prefix->consttype != rdatatype)
384 : {
385 : Assert(prefix->consttype == TEXTOID &&
386 : rdatatype == BPCHAROID);
387 16 : prefix->consttype = rdatatype;
388 : }
389 :
390 : /*
391 : * If we found an exact-match pattern, generate an "=" indexqual.
392 : *
393 : * Here and below, check to see whether the desired operator is actually
394 : * supported by the index opclass, and fail quietly if not. This allows
395 : * us to not be concerned with specific opclasses (except for the legacy
396 : * "pattern" cases); any index that correctly implements the operators
397 : * will work.
398 : */
399 3340 : if (pstatus == Pattern_Prefix_Exact)
400 : {
401 2368 : if (!op_in_opfamily(eqopr, opfamily))
402 8 : return NIL;
403 2360 : expr = make_opclause(eqopr, BOOLOID, false,
404 : (Expr *) leftop, (Expr *) prefix,
405 : InvalidOid, indexcollation);
406 2360 : result = list_make1(expr);
407 2360 : return result;
408 : }
409 :
410 : /*
411 : * Otherwise, we have a nonempty required prefix of the values.
412 : *
413 : * We can always say "x >= prefix".
414 : */
415 972 : if (!op_in_opfamily(geopr, opfamily))
416 8 : return NIL;
417 964 : expr = make_opclause(geopr, BOOLOID, false,
418 : (Expr *) leftop, (Expr *) prefix,
419 : InvalidOid, indexcollation);
420 964 : result = list_make1(expr);
421 :
422 : /*-------
423 : * If we can create a string larger than the prefix, we can say
424 : * "x < greaterstr". NB: we rely on make_greater_string() to generate
425 : * a guaranteed-greater string, not just a probably-greater string.
426 : * In general this is only guaranteed in C locale, so we'd better be
427 : * using a C-locale index collation.
428 : *-------
429 : */
430 964 : if (!op_in_opfamily(ltopr, opfamily))
431 0 : return result;
432 964 : fmgr_info(get_opcode(ltopr), <proc);
433 964 : greaterstr = make_greater_string(prefix, <proc, indexcollation);
434 964 : if (greaterstr)
435 : {
436 964 : expr = make_opclause(ltopr, BOOLOID, false,
437 : (Expr *) leftop, (Expr *) greaterstr,
438 : InvalidOid, indexcollation);
439 964 : result = lappend(result, expr);
440 : }
441 :
442 964 : return result;
443 : }
444 :
445 :
446 : /*
447 : * patternsel_common - generic code for pattern-match restriction selectivity.
448 : *
449 : * To support using this from either the operator or function paths, caller
450 : * may pass either operator OID or underlying function OID; we look up the
451 : * latter from the former if needed. (We could just have patternsel() call
452 : * get_opcode(), but the work would be wasted if we don't have a need to
453 : * compare a fixed prefix to the pg_statistic data.)
454 : *
455 : * Note that oprid and/or opfuncid should be for the positive-match operator
456 : * even when negate is true.
457 : */
458 : static double
459 4986 : patternsel_common(PlannerInfo *root,
460 : Oid oprid,
461 : Oid opfuncid,
462 : List *args,
463 : int varRelid,
464 : Oid collation,
465 : Pattern_Type ptype,
466 : bool negate)
467 : {
468 : VariableStatData vardata;
469 : Node *other;
470 : bool varonleft;
471 : Datum constval;
472 : Oid consttype;
473 : Oid vartype;
474 : Oid rdatatype;
475 : Oid eqopr;
476 : Oid ltopr;
477 : Oid geopr;
478 : Pattern_Prefix_Status pstatus;
479 : Const *patt;
480 4986 : Const *prefix = NULL;
481 4986 : Selectivity rest_selec = 0;
482 4986 : double nullfrac = 0.0;
483 : double result;
484 :
485 : /*
486 : * Initialize result to the appropriate default estimate depending on
487 : * whether it's a match or not-match operator.
488 : */
489 4986 : if (negate)
490 568 : result = 1.0 - DEFAULT_MATCH_SEL;
491 : else
492 4418 : result = DEFAULT_MATCH_SEL;
493 :
494 : /*
495 : * If expression is not variable op constant, then punt and return the
496 : * default estimate.
497 : */
498 4986 : if (!get_restriction_variable(root, args, varRelid,
499 : &vardata, &other, &varonleft))
500 64 : return result;
501 4922 : if (!varonleft || !IsA(other, Const))
502 : {
503 0 : ReleaseVariableStats(vardata);
504 0 : return result;
505 : }
506 :
507 : /*
508 : * If the constant is NULL, assume operator is strict and return zero, ie,
509 : * operator will never return TRUE. (It's zero even for a negator op.)
510 : */
511 4922 : if (((Const *) other)->constisnull)
512 : {
513 0 : ReleaseVariableStats(vardata);
514 0 : return 0.0;
515 : }
516 4922 : constval = ((Const *) other)->constvalue;
517 4922 : consttype = ((Const *) other)->consttype;
518 :
519 : /*
520 : * The right-hand const is type text or bytea for all supported operators.
521 : * We do not expect to see binary-compatible types here, since
522 : * const-folding should have relabeled the const to exactly match the
523 : * operator's declared type.
524 : */
525 4922 : if (consttype != TEXTOID && consttype != BYTEAOID)
526 : {
527 24 : ReleaseVariableStats(vardata);
528 24 : return result;
529 : }
530 :
531 : /*
532 : * Similarly, the exposed type of the left-hand side should be one of
533 : * those we know. (Do not look at vardata.atttype, which might be
534 : * something binary-compatible but different.) We can use it to identify
535 : * the comparison operators and the required type of the comparison
536 : * constant, much as in match_pattern_prefix().
537 : *
538 : * NOTE: this logic does not consider collations. Ideally we'd force use
539 : * of "C" collation, but since ANALYZE only generates statistics for the
540 : * column's specified collation, we have little choice but to use those.
541 : * But our results are so approximate anyway that it probably hardly
542 : * matters.
543 : */
544 4898 : vartype = vardata.vartype;
545 :
546 4898 : switch (vartype)
547 : {
548 1012 : case TEXTOID:
549 1012 : eqopr = TextEqualOperator;
550 1012 : ltopr = TextLessOperator;
551 1012 : geopr = TextGreaterEqualOperator;
552 1012 : rdatatype = TEXTOID;
553 1012 : break;
554 3838 : case NAMEOID:
555 :
556 : /*
557 : * Note that here, we need the RHS type to be text, so that the
558 : * comparison value isn't improperly truncated to NAMEDATALEN.
559 : */
560 3838 : eqopr = NameEqualTextOperator;
561 3838 : ltopr = NameLessTextOperator;
562 3838 : geopr = NameGreaterEqualTextOperator;
563 3838 : rdatatype = TEXTOID;
564 3838 : break;
565 40 : case BPCHAROID:
566 40 : eqopr = BpcharEqualOperator;
567 40 : ltopr = BpcharLessOperator;
568 40 : geopr = BpcharGreaterEqualOperator;
569 40 : rdatatype = BPCHAROID;
570 40 : break;
571 4 : case BYTEAOID:
572 4 : eqopr = ByteaEqualOperator;
573 4 : ltopr = ByteaLessOperator;
574 4 : geopr = ByteaGreaterEqualOperator;
575 4 : rdatatype = BYTEAOID;
576 4 : break;
577 4 : default:
578 : /* Can't get here unless we're attached to the wrong operator */
579 4 : ReleaseVariableStats(vardata);
580 4 : return result;
581 : }
582 :
583 : /*
584 : * Grab the nullfrac for use below.
585 : */
586 4894 : if (HeapTupleIsValid(vardata.statsTuple))
587 : {
588 : Form_pg_statistic stats;
589 :
590 3458 : stats = (Form_pg_statistic) GETSTRUCT(vardata.statsTuple);
591 3458 : nullfrac = stats->stanullfrac;
592 : }
593 :
594 : /*
595 : * Pull out any fixed prefix implied by the pattern, and estimate the
596 : * fractional selectivity of the remainder of the pattern. Unlike many
597 : * other selectivity estimators, we use the pattern operator's actual
598 : * collation for this step. This is not because we expect the collation
599 : * to make a big difference in the selectivity estimate (it seldom would),
600 : * but because we want to be sure we cache compiled regexps under the
601 : * right cache key, so that they can be re-used at runtime.
602 : */
603 4894 : patt = (Const *) other;
604 4894 : pstatus = pattern_fixed_prefix(patt, ptype, collation,
605 : &prefix, &rest_selec);
606 :
607 : /*
608 : * If necessary, coerce the prefix constant to the right type. The only
609 : * case where we need to do anything is when converting text to bpchar.
610 : * Those two types are binary-compatible, so relabeling the Const node is
611 : * sufficient.
612 : */
613 4894 : if (prefix && prefix->consttype != rdatatype)
614 : {
615 : Assert(prefix->consttype == TEXTOID &&
616 : rdatatype == BPCHAROID);
617 16 : prefix->consttype = rdatatype;
618 : }
619 :
620 4894 : if (pstatus == Pattern_Prefix_Exact)
621 : {
622 : /*
623 : * Pattern specifies an exact match, so estimate as for '='
624 : */
625 2368 : result = var_eq_const(&vardata, eqopr, prefix->constvalue,
626 : false, true, false);
627 : }
628 : else
629 : {
630 : /*
631 : * Not exact-match pattern. If we have a sufficiently large
632 : * histogram, estimate selectivity for the histogram part of the
633 : * population by counting matches in the histogram. If not, estimate
634 : * selectivity of the fixed prefix and remainder of pattern
635 : * separately, then combine the two to get an estimate of the
636 : * selectivity for the part of the column population represented by
637 : * the histogram. (For small histograms, we combine these
638 : * approaches.)
639 : *
640 : * We then add up data for any most-common-values values; these are
641 : * not in the histogram population, and we can get exact answers for
642 : * them by applying the pattern operator, so there's no reason to
643 : * approximate. (If the MCVs cover a significant part of the total
644 : * population, this gives us a big leg up in accuracy.)
645 : */
646 : Selectivity selec;
647 : int hist_size;
648 : FmgrInfo opproc;
649 : double mcv_selec,
650 : sumcommon;
651 :
652 : /* Try to use the histogram entries to get selectivity */
653 2526 : if (!OidIsValid(opfuncid))
654 2526 : opfuncid = get_opcode(oprid);
655 2526 : fmgr_info(opfuncid, &opproc);
656 :
657 2526 : selec = histogram_selectivity(&vardata, &opproc, constval, true,
658 : 10, 1, &hist_size);
659 :
660 : /* If not at least 100 entries, use the heuristic method */
661 2526 : if (hist_size < 100)
662 : {
663 : Selectivity heursel;
664 : Selectivity prefixsel;
665 :
666 1888 : if (pstatus == Pattern_Prefix_Partial)
667 1400 : prefixsel = prefix_selectivity(root, &vardata,
668 : eqopr, ltopr, geopr,
669 : prefix);
670 : else
671 488 : prefixsel = 1.0;
672 1888 : heursel = prefixsel * rest_selec;
673 :
674 1888 : if (selec < 0) /* fewer than 10 histogram entries? */
675 1796 : selec = heursel;
676 : else
677 : {
678 : /*
679 : * For histogram sizes from 10 to 100, we combine the
680 : * histogram and heuristic selectivities, putting increasingly
681 : * more trust in the histogram for larger sizes.
682 : */
683 92 : double hist_weight = hist_size / 100.0;
684 :
685 92 : selec = selec * hist_weight + heursel * (1.0 - hist_weight);
686 : }
687 : }
688 :
689 : /* In any case, don't believe extremely small or large estimates. */
690 2526 : if (selec < 0.0001)
691 658 : selec = 0.0001;
692 1868 : else if (selec > 0.9999)
693 74 : selec = 0.9999;
694 :
695 : /*
696 : * If we have most-common-values info, add up the fractions of the MCV
697 : * entries that satisfy MCV OP PATTERN. These fractions contribute
698 : * directly to the result selectivity. Also add up the total fraction
699 : * represented by MCV entries.
700 : */
701 2526 : mcv_selec = mcv_selectivity(&vardata, &opproc, constval, true,
702 : &sumcommon);
703 :
704 : /*
705 : * Now merge the results from the MCV and histogram calculations,
706 : * realizing that the histogram covers only the non-null values that
707 : * are not listed in MCV.
708 : */
709 2526 : selec *= 1.0 - nullfrac - sumcommon;
710 2526 : selec += mcv_selec;
711 2526 : result = selec;
712 : }
713 :
714 : /* now adjust if we wanted not-match rather than match */
715 4894 : if (negate)
716 492 : result = 1.0 - result - nullfrac;
717 :
718 : /* result should be in range, but make sure... */
719 4894 : CLAMP_PROBABILITY(result);
720 :
721 4894 : if (prefix)
722 : {
723 4512 : pfree(DatumGetPointer(prefix->constvalue));
724 4512 : pfree(prefix);
725 : }
726 :
727 4894 : ReleaseVariableStats(vardata);
728 :
729 4894 : return result;
730 : }
731 :
732 : /*
733 : * Fix impedance mismatch between SQL-callable functions and patternsel_common
734 : */
735 : static double
736 4986 : patternsel(PG_FUNCTION_ARGS, Pattern_Type ptype, bool negate)
737 : {
738 4986 : PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
739 4986 : Oid operator = PG_GETARG_OID(1);
740 4986 : List *args = (List *) PG_GETARG_POINTER(2);
741 4986 : int varRelid = PG_GETARG_INT32(3);
742 4986 : Oid collation = PG_GET_COLLATION();
743 :
744 : /*
745 : * If this is for a NOT LIKE or similar operator, get the corresponding
746 : * positive-match operator and work with that.
747 : */
748 4986 : if (negate)
749 : {
750 568 : operator = get_negator(operator);
751 568 : if (!OidIsValid(operator))
752 0 : elog(ERROR, "patternsel called for operator without a negator");
753 : }
754 :
755 4986 : return patternsel_common(root,
756 : operator,
757 : InvalidOid,
758 : args,
759 : varRelid,
760 : collation,
761 : ptype,
762 : negate);
763 : }
764 :
765 : /*
766 : * regexeqsel - Selectivity of regular-expression pattern match.
767 : */
768 : Datum
769 2794 : regexeqsel(PG_FUNCTION_ARGS)
770 : {
771 2794 : PG_RETURN_FLOAT8(patternsel(fcinfo, Pattern_Type_Regex, false));
772 : }
773 :
774 : /*
775 : * icregexeqsel - Selectivity of case-insensitive regex match.
776 : */
777 : Datum
778 40 : icregexeqsel(PG_FUNCTION_ARGS)
779 : {
780 40 : PG_RETURN_FLOAT8(patternsel(fcinfo, Pattern_Type_Regex_IC, false));
781 : }
782 :
783 : /*
784 : * likesel - Selectivity of LIKE pattern match.
785 : */
786 : Datum
787 1520 : likesel(PG_FUNCTION_ARGS)
788 : {
789 1520 : PG_RETURN_FLOAT8(patternsel(fcinfo, Pattern_Type_Like, false));
790 : }
791 :
792 : /*
793 : * prefixsel - selectivity of prefix operator
794 : */
795 : Datum
796 20 : prefixsel(PG_FUNCTION_ARGS)
797 : {
798 20 : PG_RETURN_FLOAT8(patternsel(fcinfo, Pattern_Type_Prefix, false));
799 : }
800 :
801 : /*
802 : *
803 : * iclikesel - Selectivity of ILIKE pattern match.
804 : */
805 : Datum
806 44 : iclikesel(PG_FUNCTION_ARGS)
807 : {
808 44 : PG_RETURN_FLOAT8(patternsel(fcinfo, Pattern_Type_Like_IC, false));
809 : }
810 :
811 : /*
812 : * regexnesel - Selectivity of regular-expression pattern non-match.
813 : */
814 : Datum
815 506 : regexnesel(PG_FUNCTION_ARGS)
816 : {
817 506 : PG_RETURN_FLOAT8(patternsel(fcinfo, Pattern_Type_Regex, true));
818 : }
819 :
820 : /*
821 : * icregexnesel - Selectivity of case-insensitive regex non-match.
822 : */
823 : Datum
824 12 : icregexnesel(PG_FUNCTION_ARGS)
825 : {
826 12 : PG_RETURN_FLOAT8(patternsel(fcinfo, Pattern_Type_Regex_IC, true));
827 : }
828 :
829 : /*
830 : * nlikesel - Selectivity of LIKE pattern non-match.
831 : */
832 : Datum
833 42 : nlikesel(PG_FUNCTION_ARGS)
834 : {
835 42 : PG_RETURN_FLOAT8(patternsel(fcinfo, Pattern_Type_Like, true));
836 : }
837 :
838 : /*
839 : * icnlikesel - Selectivity of ILIKE pattern non-match.
840 : */
841 : Datum
842 8 : icnlikesel(PG_FUNCTION_ARGS)
843 : {
844 8 : PG_RETURN_FLOAT8(patternsel(fcinfo, Pattern_Type_Like_IC, true));
845 : }
846 :
847 : /*
848 : * patternjoinsel - Generic code for pattern-match join selectivity.
849 : */
850 : static double
851 0 : patternjoinsel(PG_FUNCTION_ARGS, Pattern_Type ptype, bool negate)
852 : {
853 : /* For the moment we just punt. */
854 0 : return negate ? (1.0 - DEFAULT_MATCH_SEL) : DEFAULT_MATCH_SEL;
855 : }
856 :
857 : /*
858 : * regexeqjoinsel - Join selectivity of regular-expression pattern match.
859 : */
860 : Datum
861 0 : regexeqjoinsel(PG_FUNCTION_ARGS)
862 : {
863 0 : PG_RETURN_FLOAT8(patternjoinsel(fcinfo, Pattern_Type_Regex, false));
864 : }
865 :
866 : /*
867 : * icregexeqjoinsel - Join selectivity of case-insensitive regex match.
868 : */
869 : Datum
870 0 : icregexeqjoinsel(PG_FUNCTION_ARGS)
871 : {
872 0 : PG_RETURN_FLOAT8(patternjoinsel(fcinfo, Pattern_Type_Regex_IC, false));
873 : }
874 :
875 : /*
876 : * likejoinsel - Join selectivity of LIKE pattern match.
877 : */
878 : Datum
879 0 : likejoinsel(PG_FUNCTION_ARGS)
880 : {
881 0 : PG_RETURN_FLOAT8(patternjoinsel(fcinfo, Pattern_Type_Like, false));
882 : }
883 :
884 : /*
885 : * prefixjoinsel - Join selectivity of prefix operator
886 : */
887 : Datum
888 0 : prefixjoinsel(PG_FUNCTION_ARGS)
889 : {
890 0 : PG_RETURN_FLOAT8(patternjoinsel(fcinfo, Pattern_Type_Prefix, false));
891 : }
892 :
893 : /*
894 : * iclikejoinsel - Join selectivity of ILIKE pattern match.
895 : */
896 : Datum
897 0 : iclikejoinsel(PG_FUNCTION_ARGS)
898 : {
899 0 : PG_RETURN_FLOAT8(patternjoinsel(fcinfo, Pattern_Type_Like_IC, false));
900 : }
901 :
902 : /*
903 : * regexnejoinsel - Join selectivity of regex non-match.
904 : */
905 : Datum
906 0 : regexnejoinsel(PG_FUNCTION_ARGS)
907 : {
908 0 : PG_RETURN_FLOAT8(patternjoinsel(fcinfo, Pattern_Type_Regex, true));
909 : }
910 :
911 : /*
912 : * icregexnejoinsel - Join selectivity of case-insensitive regex non-match.
913 : */
914 : Datum
915 0 : icregexnejoinsel(PG_FUNCTION_ARGS)
916 : {
917 0 : PG_RETURN_FLOAT8(patternjoinsel(fcinfo, Pattern_Type_Regex_IC, true));
918 : }
919 :
920 : /*
921 : * nlikejoinsel - Join selectivity of LIKE pattern non-match.
922 : */
923 : Datum
924 0 : nlikejoinsel(PG_FUNCTION_ARGS)
925 : {
926 0 : PG_RETURN_FLOAT8(patternjoinsel(fcinfo, Pattern_Type_Like, true));
927 : }
928 :
929 : /*
930 : * icnlikejoinsel - Join selectivity of ILIKE pattern non-match.
931 : */
932 : Datum
933 0 : icnlikejoinsel(PG_FUNCTION_ARGS)
934 : {
935 0 : PG_RETURN_FLOAT8(patternjoinsel(fcinfo, Pattern_Type_Like_IC, true));
936 : }
937 :
938 :
939 : /*-------------------------------------------------------------------------
940 : *
941 : * Pattern analysis functions
942 : *
943 : * These routines support analysis of LIKE and regular-expression patterns
944 : * by the planner/optimizer. It's important that they agree with the
945 : * regular-expression code in backend/regex/ and the LIKE code in
946 : * backend/utils/adt/like.c. Also, the computation of the fixed prefix
947 : * must be conservative: if we report a string longer than the true fixed
948 : * prefix, the query may produce actually wrong answers, rather than just
949 : * getting a bad selectivity estimate!
950 : *
951 : *-------------------------------------------------------------------------
952 : */
953 :
954 : /*
955 : * Extract the fixed prefix, if any, for a pattern.
956 : *
957 : * *prefix is set to a palloc'd prefix string (in the form of a Const node),
958 : * or to NULL if no fixed prefix exists for the pattern.
959 : * If rest_selec is not NULL, *rest_selec is set to an estimate of the
960 : * selectivity of the remainder of the pattern (without any fixed prefix).
961 : * The prefix Const has the same type (TEXT or BYTEA) as the input pattern.
962 : *
963 : * The return value distinguishes no fixed prefix, a partial prefix,
964 : * or an exact-match-only pattern.
965 : */
966 :
967 : static Pattern_Prefix_Status
968 2522 : like_fixed_prefix(Const *patt_const, bool case_insensitive, Oid collation,
969 : Const **prefix_const, Selectivity *rest_selec)
970 : {
971 : char *match;
972 : char *patt;
973 : int pattlen;
974 2522 : Oid typeid = patt_const->consttype;
975 : int pos,
976 : match_pos;
977 2522 : bool is_multibyte = (pg_database_encoding_max_length() > 1);
978 2522 : pg_locale_t locale = 0;
979 2522 : bool locale_is_c = false;
980 :
981 : /* the right-hand const is type text or bytea */
982 : Assert(typeid == BYTEAOID || typeid == TEXTOID);
983 :
984 2522 : if (case_insensitive)
985 : {
986 60 : if (typeid == BYTEAOID)
987 0 : ereport(ERROR,
988 : (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
989 : errmsg("case insensitive matching not supported on type bytea")));
990 :
991 : /* If case-insensitive, we need locale info */
992 60 : if (lc_ctype_is_c(collation))
993 60 : locale_is_c = true;
994 0 : else if (collation != DEFAULT_COLLATION_OID)
995 : {
996 0 : if (!OidIsValid(collation))
997 : {
998 : /*
999 : * This typically means that the parser could not resolve a
1000 : * conflict of implicit collations, so report it that way.
1001 : */
1002 0 : ereport(ERROR,
1003 : (errcode(ERRCODE_INDETERMINATE_COLLATION),
1004 : errmsg("could not determine which collation to use for ILIKE"),
1005 : errhint("Use the COLLATE clause to set the collation explicitly.")));
1006 : }
1007 0 : locale = pg_newlocale_from_collation(collation);
1008 : }
1009 : }
1010 :
1011 2522 : if (typeid != BYTEAOID)
1012 : {
1013 2514 : patt = TextDatumGetCString(patt_const->constvalue);
1014 2514 : pattlen = strlen(patt);
1015 : }
1016 : else
1017 : {
1018 8 : bytea *bstr = DatumGetByteaPP(patt_const->constvalue);
1019 :
1020 8 : pattlen = VARSIZE_ANY_EXHDR(bstr);
1021 8 : patt = (char *) palloc(pattlen);
1022 8 : memcpy(patt, VARDATA_ANY(bstr), pattlen);
1023 : Assert((Pointer) bstr == DatumGetPointer(patt_const->constvalue));
1024 : }
1025 :
1026 2522 : match = palloc(pattlen + 1);
1027 2522 : match_pos = 0;
1028 13494 : for (pos = 0; pos < pattlen; pos++)
1029 : {
1030 : /* % and _ are wildcard characters in LIKE */
1031 13454 : if (patt[pos] == '%' ||
1032 11572 : patt[pos] == '_')
1033 : break;
1034 :
1035 : /* Backslash escapes the next character */
1036 10992 : if (patt[pos] == '\\')
1037 : {
1038 116 : pos++;
1039 116 : if (pos >= pattlen)
1040 0 : break;
1041 : }
1042 :
1043 : /* Stop if case-varying character (it's sort of a wildcard) */
1044 11076 : if (case_insensitive &&
1045 84 : pattern_char_isalpha(patt[pos], is_multibyte, locale, locale_is_c))
1046 20 : break;
1047 :
1048 10972 : match[match_pos++] = patt[pos];
1049 : }
1050 :
1051 2522 : match[match_pos] = '\0';
1052 :
1053 2522 : if (typeid != BYTEAOID)
1054 2514 : *prefix_const = string_to_const(match, typeid);
1055 : else
1056 8 : *prefix_const = string_to_bytea_const(match, match_pos);
1057 :
1058 2522 : if (rest_selec != NULL)
1059 1598 : *rest_selec = like_selectivity(&patt[pos], pattlen - pos,
1060 : case_insensitive);
1061 :
1062 2522 : pfree(patt);
1063 2522 : pfree(match);
1064 :
1065 : /* in LIKE, an empty pattern is an exact match! */
1066 2522 : if (pos == pattlen)
1067 40 : return Pattern_Prefix_Exact; /* reached end of pattern, so exact */
1068 :
1069 2482 : if (match_pos > 0)
1070 2188 : return Pattern_Prefix_Partial;
1071 :
1072 294 : return Pattern_Prefix_None;
1073 : }
1074 :
1075 : static Pattern_Prefix_Status
1076 5818 : regex_fixed_prefix(Const *patt_const, bool case_insensitive, Oid collation,
1077 : Const **prefix_const, Selectivity *rest_selec)
1078 : {
1079 5818 : Oid typeid = patt_const->consttype;
1080 : char *prefix;
1081 : bool exact;
1082 :
1083 : /*
1084 : * Should be unnecessary, there are no bytea regex operators defined. As
1085 : * such, it should be noted that the rest of this function has *not* been
1086 : * made safe for binary (possibly NULL containing) strings.
1087 : */
1088 5818 : if (typeid == BYTEAOID)
1089 0 : ereport(ERROR,
1090 : (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
1091 : errmsg("regular-expression matching not supported on type bytea")));
1092 :
1093 : /* Use the regexp machinery to extract the prefix, if any */
1094 5818 : prefix = regexp_fixed_prefix(DatumGetTextPP(patt_const->constvalue),
1095 : case_insensitive, collation,
1096 : &exact);
1097 :
1098 5818 : if (prefix == NULL)
1099 : {
1100 432 : *prefix_const = NULL;
1101 :
1102 432 : if (rest_selec != NULL)
1103 : {
1104 382 : char *patt = TextDatumGetCString(patt_const->constvalue);
1105 :
1106 382 : *rest_selec = regex_selectivity(patt, strlen(patt),
1107 : case_insensitive,
1108 : 0);
1109 382 : pfree(patt);
1110 : }
1111 :
1112 432 : return Pattern_Prefix_None;
1113 : }
1114 :
1115 5386 : *prefix_const = string_to_const(prefix, typeid);
1116 :
1117 5386 : if (rest_selec != NULL)
1118 : {
1119 2894 : if (exact)
1120 : {
1121 : /* Exact match, so there's no additional selectivity */
1122 2348 : *rest_selec = 1.0;
1123 : }
1124 : else
1125 : {
1126 546 : char *patt = TextDatumGetCString(patt_const->constvalue);
1127 :
1128 1092 : *rest_selec = regex_selectivity(patt, strlen(patt),
1129 : case_insensitive,
1130 546 : strlen(prefix));
1131 546 : pfree(patt);
1132 : }
1133 : }
1134 :
1135 5386 : pfree(prefix);
1136 :
1137 5386 : if (exact)
1138 4696 : return Pattern_Prefix_Exact; /* pattern specifies exact match */
1139 : else
1140 690 : return Pattern_Prefix_Partial;
1141 : }
1142 :
1143 : static Pattern_Prefix_Status
1144 8360 : pattern_fixed_prefix(Const *patt, Pattern_Type ptype, Oid collation,
1145 : Const **prefix, Selectivity *rest_selec)
1146 : {
1147 : Pattern_Prefix_Status result;
1148 :
1149 8360 : switch (ptype)
1150 : {
1151 2462 : case Pattern_Type_Like:
1152 2462 : result = like_fixed_prefix(patt, false, collation,
1153 : prefix, rest_selec);
1154 2462 : break;
1155 60 : case Pattern_Type_Like_IC:
1156 60 : result = like_fixed_prefix(patt, true, collation,
1157 : prefix, rest_selec);
1158 60 : break;
1159 5786 : case Pattern_Type_Regex:
1160 5786 : result = regex_fixed_prefix(patt, false, collation,
1161 : prefix, rest_selec);
1162 5786 : break;
1163 32 : case Pattern_Type_Regex_IC:
1164 32 : result = regex_fixed_prefix(patt, true, collation,
1165 : prefix, rest_selec);
1166 32 : break;
1167 20 : case Pattern_Type_Prefix:
1168 : /* Prefix type work is trivial. */
1169 20 : result = Pattern_Prefix_Partial;
1170 20 : *rest_selec = 1.0; /* all */
1171 20 : *prefix = makeConst(patt->consttype,
1172 : patt->consttypmod,
1173 : patt->constcollid,
1174 : patt->constlen,
1175 : datumCopy(patt->constvalue,
1176 20 : patt->constbyval,
1177 : patt->constlen),
1178 20 : patt->constisnull,
1179 20 : patt->constbyval);
1180 20 : break;
1181 0 : default:
1182 0 : elog(ERROR, "unrecognized ptype: %d", (int) ptype);
1183 : result = Pattern_Prefix_None; /* keep compiler quiet */
1184 : break;
1185 : }
1186 8360 : return result;
1187 : }
1188 :
1189 : /*
1190 : * Estimate the selectivity of a fixed prefix for a pattern match.
1191 : *
1192 : * A fixed prefix "foo" is estimated as the selectivity of the expression
1193 : * "variable >= 'foo' AND variable < 'fop'".
1194 : *
1195 : * The selectivity estimate is with respect to the portion of the column
1196 : * population represented by the histogram --- the caller must fold this
1197 : * together with info about MCVs and NULLs.
1198 : *
1199 : * We use the specified btree comparison operators to do the estimation.
1200 : * The given variable and Const must be of the associated datatype(s).
1201 : *
1202 : * XXX Note: we make use of the upper bound to estimate operator selectivity
1203 : * even if the locale is such that we cannot rely on the upper-bound string.
1204 : * The selectivity only needs to be approximately right anyway, so it seems
1205 : * more useful to use the upper-bound code than not.
1206 : */
1207 : static Selectivity
1208 1400 : prefix_selectivity(PlannerInfo *root, VariableStatData *vardata,
1209 : Oid eqopr, Oid ltopr, Oid geopr,
1210 : Const *prefixcon)
1211 : {
1212 : Selectivity prefixsel;
1213 : FmgrInfo opproc;
1214 : AttStatsSlot sslot;
1215 : Const *greaterstrcon;
1216 : Selectivity eq_sel;
1217 :
1218 : /* Estimate the selectivity of "x >= prefix" */
1219 1400 : fmgr_info(get_opcode(geopr), &opproc);
1220 :
1221 1400 : prefixsel = ineq_histogram_selectivity(root, vardata,
1222 : &opproc, true, true,
1223 : prefixcon->constvalue,
1224 : prefixcon->consttype);
1225 :
1226 1400 : if (prefixsel < 0.0)
1227 : {
1228 : /* No histogram is present ... return a suitable default estimate */
1229 916 : return DEFAULT_MATCH_SEL;
1230 : }
1231 :
1232 : /*-------
1233 : * If we can create a string larger than the prefix, say
1234 : * "x < greaterstr". We try to generate the string referencing the
1235 : * collation of the var's statistics, but if that's not available,
1236 : * use DEFAULT_COLLATION_OID.
1237 : *-------
1238 : */
1239 968 : if (HeapTupleIsValid(vardata->statsTuple) &&
1240 484 : get_attstatsslot(&sslot, vardata->statsTuple,
1241 : STATISTIC_KIND_HISTOGRAM, InvalidOid, 0))
1242 : /* sslot.stacoll is set up */ ;
1243 : else
1244 0 : sslot.stacoll = DEFAULT_COLLATION_OID;
1245 484 : fmgr_info(get_opcode(ltopr), &opproc);
1246 484 : greaterstrcon = make_greater_string(prefixcon, &opproc, sslot.stacoll);
1247 484 : if (greaterstrcon)
1248 : {
1249 : Selectivity topsel;
1250 :
1251 484 : topsel = ineq_histogram_selectivity(root, vardata,
1252 : &opproc, false, false,
1253 : greaterstrcon->constvalue,
1254 : greaterstrcon->consttype);
1255 :
1256 : /* ineq_histogram_selectivity worked before, it shouldn't fail now */
1257 : Assert(topsel >= 0.0);
1258 :
1259 : /*
1260 : * Merge the two selectivities in the same way as for a range query
1261 : * (see clauselist_selectivity()). Note that we don't need to worry
1262 : * about double-exclusion of nulls, since ineq_histogram_selectivity
1263 : * doesn't count those anyway.
1264 : */
1265 484 : prefixsel = topsel + prefixsel - 1.0;
1266 : }
1267 :
1268 : /*
1269 : * If the prefix is long then the two bounding values might be too close
1270 : * together for the histogram to distinguish them usefully, resulting in a
1271 : * zero estimate (plus or minus roundoff error). To avoid returning a
1272 : * ridiculously small estimate, compute the estimated selectivity for
1273 : * "variable = 'foo'", and clamp to that. (Obviously, the resultant
1274 : * estimate should be at least that.)
1275 : *
1276 : * We apply this even if we couldn't make a greater string. That case
1277 : * suggests that the prefix is near the maximum possible, and thus
1278 : * probably off the end of the histogram, and thus we probably got a very
1279 : * small estimate from the >= condition; so we still need to clamp.
1280 : */
1281 484 : eq_sel = var_eq_const(vardata, eqopr, prefixcon->constvalue,
1282 : false, true, false);
1283 :
1284 484 : prefixsel = Max(prefixsel, eq_sel);
1285 :
1286 484 : return prefixsel;
1287 : }
1288 :
1289 :
1290 : /*
1291 : * Estimate the selectivity of a pattern of the specified type.
1292 : * Note that any fixed prefix of the pattern will have been removed already,
1293 : * so actually we may be looking at just a fragment of the pattern.
1294 : *
1295 : * For now, we use a very simplistic approach: fixed characters reduce the
1296 : * selectivity a good deal, character ranges reduce it a little,
1297 : * wildcards (such as % for LIKE or .* for regex) increase it.
1298 : */
1299 :
1300 : #define FIXED_CHAR_SEL 0.20 /* about 1/5 */
1301 : #define CHAR_RANGE_SEL 0.25
1302 : #define ANY_CHAR_SEL 0.9 /* not 1, since it won't match end-of-string */
1303 : #define FULL_WILDCARD_SEL 5.0
1304 : #define PARTIAL_WILDCARD_SEL 2.0
1305 :
1306 : static Selectivity
1307 1598 : like_selectivity(const char *patt, int pattlen, bool case_insensitive)
1308 : {
1309 1598 : Selectivity sel = 1.0;
1310 : int pos;
1311 :
1312 : /* Skip any leading wildcard; it's already factored into initial sel */
1313 3176 : for (pos = 0; pos < pattlen; pos++)
1314 : {
1315 2082 : if (patt[pos] != '%' && patt[pos] != '_')
1316 504 : break;
1317 : }
1318 :
1319 4184 : for (; pos < pattlen; pos++)
1320 : {
1321 : /* % and _ are wildcard characters in LIKE */
1322 2586 : if (patt[pos] == '%')
1323 448 : sel *= FULL_WILDCARD_SEL;
1324 2138 : else if (patt[pos] == '_')
1325 64 : sel *= ANY_CHAR_SEL;
1326 2074 : else if (patt[pos] == '\\')
1327 : {
1328 : /* Backslash quotes the next character */
1329 28 : pos++;
1330 28 : if (pos >= pattlen)
1331 0 : break;
1332 28 : sel *= FIXED_CHAR_SEL;
1333 : }
1334 : else
1335 2046 : sel *= FIXED_CHAR_SEL;
1336 : }
1337 : /* Could get sel > 1 if multiple wildcards */
1338 1598 : if (sel > 1.0)
1339 0 : sel = 1.0;
1340 1598 : return sel;
1341 : }
1342 :
1343 : static Selectivity
1344 1034 : regex_selectivity_sub(const char *patt, int pattlen, bool case_insensitive)
1345 : {
1346 1034 : Selectivity sel = 1.0;
1347 1034 : int paren_depth = 0;
1348 1034 : int paren_pos = 0; /* dummy init to keep compiler quiet */
1349 : int pos;
1350 :
1351 8996 : for (pos = 0; pos < pattlen; pos++)
1352 : {
1353 7978 : if (patt[pos] == '(')
1354 : {
1355 94 : if (paren_depth == 0)
1356 90 : paren_pos = pos; /* remember start of parenthesized item */
1357 94 : paren_depth++;
1358 : }
1359 7884 : else if (patt[pos] == ')' && paren_depth > 0)
1360 : {
1361 94 : paren_depth--;
1362 184 : if (paren_depth == 0)
1363 90 : sel *= regex_selectivity_sub(patt + (paren_pos + 1),
1364 90 : pos - (paren_pos + 1),
1365 : case_insensitive);
1366 : }
1367 7790 : else if (patt[pos] == '|' && paren_depth == 0)
1368 : {
1369 : /*
1370 : * If unquoted | is present at paren level 0 in pattern, we have
1371 : * multiple alternatives; sum their probabilities.
1372 : */
1373 48 : sel += regex_selectivity_sub(patt + (pos + 1),
1374 16 : pattlen - (pos + 1),
1375 : case_insensitive);
1376 16 : break; /* rest of pattern is now processed */
1377 : }
1378 7774 : else if (patt[pos] == '[')
1379 : {
1380 60 : bool negclass = false;
1381 :
1382 60 : if (patt[++pos] == '^')
1383 : {
1384 0 : negclass = true;
1385 0 : pos++;
1386 : }
1387 60 : if (patt[pos] == ']') /* ']' at start of class is not special */
1388 0 : pos++;
1389 284 : while (pos < pattlen && patt[pos] != ']')
1390 224 : pos++;
1391 60 : if (paren_depth == 0)
1392 60 : sel *= (negclass ? (1.0 - CHAR_RANGE_SEL) : CHAR_RANGE_SEL);
1393 : }
1394 7714 : else if (patt[pos] == '.')
1395 : {
1396 260 : if (paren_depth == 0)
1397 184 : sel *= ANY_CHAR_SEL;
1398 : }
1399 7454 : else if (patt[pos] == '*' ||
1400 7230 : patt[pos] == '?' ||
1401 7198 : patt[pos] == '+')
1402 : {
1403 : /* Ought to be smarter about quantifiers... */
1404 448 : if (paren_depth == 0)
1405 180 : sel *= PARTIAL_WILDCARD_SEL;
1406 : }
1407 7186 : else if (patt[pos] == '{')
1408 : {
1409 232 : while (pos < pattlen && patt[pos] != '}')
1410 164 : pos++;
1411 68 : if (paren_depth == 0)
1412 56 : sel *= PARTIAL_WILDCARD_SEL;
1413 : }
1414 7118 : else if (patt[pos] == '\\')
1415 : {
1416 : /* backslash quotes the next character */
1417 40 : pos++;
1418 40 : if (pos >= pattlen)
1419 0 : break;
1420 40 : if (paren_depth == 0)
1421 24 : sel *= FIXED_CHAR_SEL;
1422 : }
1423 : else
1424 : {
1425 7078 : if (paren_depth == 0)
1426 6564 : sel *= FIXED_CHAR_SEL;
1427 : }
1428 : }
1429 : /* Could get sel > 1 if multiple wildcards */
1430 1034 : if (sel > 1.0)
1431 16 : sel = 1.0;
1432 1034 : return sel;
1433 : }
1434 :
1435 : static Selectivity
1436 928 : regex_selectivity(const char *patt, int pattlen, bool case_insensitive,
1437 : int fixed_prefix_len)
1438 : {
1439 : Selectivity sel;
1440 :
1441 : /* If patt doesn't end with $, consider it to have a trailing wildcard */
1442 928 : if (pattlen > 0 && patt[pattlen - 1] == '$' &&
1443 78 : (pattlen == 1 || patt[pattlen - 2] != '\\'))
1444 : {
1445 : /* has trailing $ */
1446 78 : sel = regex_selectivity_sub(patt, pattlen - 1, case_insensitive);
1447 : }
1448 : else
1449 : {
1450 : /* no trailing $ */
1451 850 : sel = regex_selectivity_sub(patt, pattlen, case_insensitive);
1452 850 : sel *= FULL_WILDCARD_SEL;
1453 : }
1454 :
1455 : /* If there's a fixed prefix, discount its selectivity */
1456 928 : if (fixed_prefix_len > 0)
1457 546 : sel /= pow(FIXED_CHAR_SEL, fixed_prefix_len);
1458 :
1459 : /* Make sure result stays in range */
1460 928 : CLAMP_PROBABILITY(sel);
1461 928 : return sel;
1462 : }
1463 :
1464 : /*
1465 : * Check whether char is a letter (and, hence, subject to case-folding)
1466 : *
1467 : * In multibyte character sets or with ICU, we can't use isalpha, and it does
1468 : * not seem worth trying to convert to wchar_t to use iswalpha or u_isalpha.
1469 : * Instead, just assume any non-ASCII char is potentially case-varying, and
1470 : * hard-wire knowledge of which ASCII chars are letters.
1471 : */
1472 : static int
1473 84 : pattern_char_isalpha(char c, bool is_multibyte,
1474 : pg_locale_t locale, bool locale_is_c)
1475 : {
1476 84 : if (locale_is_c)
1477 84 : return (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z');
1478 0 : else if (is_multibyte && IS_HIGHBIT_SET(c))
1479 0 : return true;
1480 0 : else if (locale && locale->provider == COLLPROVIDER_ICU)
1481 0 : return IS_HIGHBIT_SET(c) ||
1482 0 : (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z');
1483 : #ifdef HAVE_LOCALE_T
1484 0 : else if (locale && locale->provider == COLLPROVIDER_LIBC)
1485 0 : return isalpha_l((unsigned char) c, locale->info.lt);
1486 : #endif
1487 : else
1488 0 : return isalpha((unsigned char) c);
1489 : }
1490 :
1491 :
1492 : /*
1493 : * For bytea, the increment function need only increment the current byte
1494 : * (there are no multibyte characters to worry about).
1495 : */
1496 : static bool
1497 0 : byte_increment(unsigned char *ptr, int len)
1498 : {
1499 0 : if (*ptr >= 255)
1500 0 : return false;
1501 0 : (*ptr)++;
1502 0 : return true;
1503 : }
1504 :
1505 : /*
1506 : * Try to generate a string greater than the given string or any
1507 : * string it is a prefix of. If successful, return a palloc'd string
1508 : * in the form of a Const node; else return NULL.
1509 : *
1510 : * The caller must provide the appropriate "less than" comparison function
1511 : * for testing the strings, along with the collation to use.
1512 : *
1513 : * The key requirement here is that given a prefix string, say "foo",
1514 : * we must be able to generate another string "fop" that is greater than
1515 : * all strings "foobar" starting with "foo". We can test that we have
1516 : * generated a string greater than the prefix string, but in non-C collations
1517 : * that is not a bulletproof guarantee that an extension of the string might
1518 : * not sort after it; an example is that "foo " is less than "foo!", but it
1519 : * is not clear that a "dictionary" sort ordering will consider "foo!" less
1520 : * than "foo bar". CAUTION: Therefore, this function should be used only for
1521 : * estimation purposes when working in a non-C collation.
1522 : *
1523 : * To try to catch most cases where an extended string might otherwise sort
1524 : * before the result value, we determine which of the strings "Z", "z", "y",
1525 : * and "9" is seen as largest by the collation, and append that to the given
1526 : * prefix before trying to find a string that compares as larger.
1527 : *
1528 : * To search for a greater string, we repeatedly "increment" the rightmost
1529 : * character, using an encoding-specific character incrementer function.
1530 : * When it's no longer possible to increment the last character, we truncate
1531 : * off that character and start incrementing the next-to-rightmost.
1532 : * For example, if "z" were the last character in the sort order, then we
1533 : * could produce "foo" as a string greater than "fonz".
1534 : *
1535 : * This could be rather slow in the worst case, but in most cases we
1536 : * won't have to try more than one or two strings before succeeding.
1537 : *
1538 : * Note that it's important for the character incrementer not to be too anal
1539 : * about producing every possible character code, since in some cases the only
1540 : * way to get a larger string is to increment a previous character position.
1541 : * So we don't want to spend too much time trying every possible character
1542 : * code at the last position. A good rule of thumb is to be sure that we
1543 : * don't try more than 256*K values for a K-byte character (and definitely
1544 : * not 256^K, which is what an exhaustive search would approach).
1545 : */
1546 : static Const *
1547 1448 : make_greater_string(const Const *str_const, FmgrInfo *ltproc, Oid collation)
1548 : {
1549 1448 : Oid datatype = str_const->consttype;
1550 : char *workstr;
1551 : int len;
1552 : Datum cmpstr;
1553 1448 : char *cmptxt = NULL;
1554 : mbcharacter_incrementer charinc;
1555 :
1556 : /*
1557 : * Get a modifiable copy of the prefix string in C-string format, and set
1558 : * up the string we will compare to as a Datum. In C locale this can just
1559 : * be the given prefix string, otherwise we need to add a suffix. Type
1560 : * BYTEA sorts bytewise so it never needs a suffix either.
1561 : */
1562 1448 : if (datatype == BYTEAOID)
1563 : {
1564 0 : bytea *bstr = DatumGetByteaPP(str_const->constvalue);
1565 :
1566 0 : len = VARSIZE_ANY_EXHDR(bstr);
1567 0 : workstr = (char *) palloc(len);
1568 0 : memcpy(workstr, VARDATA_ANY(bstr), len);
1569 : Assert((Pointer) bstr == DatumGetPointer(str_const->constvalue));
1570 0 : cmpstr = str_const->constvalue;
1571 : }
1572 : else
1573 : {
1574 1448 : if (datatype == NAMEOID)
1575 0 : workstr = DatumGetCString(DirectFunctionCall1(nameout,
1576 : str_const->constvalue));
1577 : else
1578 1448 : workstr = TextDatumGetCString(str_const->constvalue);
1579 1448 : len = strlen(workstr);
1580 1448 : if (lc_collate_is_c(collation) || len == 0)
1581 1448 : cmpstr = str_const->constvalue;
1582 : else
1583 : {
1584 : /* If first time through, determine the suffix to use */
1585 : static char suffixchar = 0;
1586 : static Oid suffixcollation = 0;
1587 :
1588 0 : if (!suffixchar || suffixcollation != collation)
1589 : {
1590 : char *best;
1591 :
1592 0 : best = "Z";
1593 0 : if (varstr_cmp(best, 1, "z", 1, collation) < 0)
1594 0 : best = "z";
1595 0 : if (varstr_cmp(best, 1, "y", 1, collation) < 0)
1596 0 : best = "y";
1597 0 : if (varstr_cmp(best, 1, "9", 1, collation) < 0)
1598 0 : best = "9";
1599 0 : suffixchar = *best;
1600 0 : suffixcollation = collation;
1601 : }
1602 :
1603 : /* And build the string to compare to */
1604 0 : if (datatype == NAMEOID)
1605 : {
1606 0 : cmptxt = palloc(len + 2);
1607 0 : memcpy(cmptxt, workstr, len);
1608 0 : cmptxt[len] = suffixchar;
1609 0 : cmptxt[len + 1] = '\0';
1610 0 : cmpstr = PointerGetDatum(cmptxt);
1611 : }
1612 : else
1613 : {
1614 0 : cmptxt = palloc(VARHDRSZ + len + 1);
1615 0 : SET_VARSIZE(cmptxt, VARHDRSZ + len + 1);
1616 0 : memcpy(VARDATA(cmptxt), workstr, len);
1617 0 : *(VARDATA(cmptxt) + len) = suffixchar;
1618 0 : cmpstr = PointerGetDatum(cmptxt);
1619 : }
1620 : }
1621 : }
1622 :
1623 : /* Select appropriate character-incrementer function */
1624 1448 : if (datatype == BYTEAOID)
1625 0 : charinc = byte_increment;
1626 : else
1627 1448 : charinc = pg_database_encoding_character_incrementer();
1628 :
1629 : /* And search ... */
1630 1448 : while (len > 0)
1631 : {
1632 : int charlen;
1633 : unsigned char *lastchar;
1634 :
1635 : /* Identify the last character --- for bytea, just the last byte */
1636 1448 : if (datatype == BYTEAOID)
1637 0 : charlen = 1;
1638 : else
1639 1448 : charlen = len - pg_mbcliplen(workstr, len, len - 1);
1640 1448 : lastchar = (unsigned char *) (workstr + len - charlen);
1641 :
1642 : /*
1643 : * Try to generate a larger string by incrementing the last character
1644 : * (for BYTEA, we treat each byte as a character).
1645 : *
1646 : * Note: the incrementer function is expected to return true if it's
1647 : * generated a valid-per-the-encoding new character, otherwise false.
1648 : * The contents of the character on false return are unspecified.
1649 : */
1650 1448 : while (charinc(lastchar, charlen))
1651 : {
1652 : Const *workstr_const;
1653 :
1654 1448 : if (datatype == BYTEAOID)
1655 0 : workstr_const = string_to_bytea_const(workstr, len);
1656 : else
1657 1448 : workstr_const = string_to_const(workstr, datatype);
1658 :
1659 1448 : if (DatumGetBool(FunctionCall2Coll(ltproc,
1660 : collation,
1661 : cmpstr,
1662 : workstr_const->constvalue)))
1663 : {
1664 : /* Successfully made a string larger than cmpstr */
1665 1448 : if (cmptxt)
1666 0 : pfree(cmptxt);
1667 1448 : pfree(workstr);
1668 1448 : return workstr_const;
1669 : }
1670 :
1671 : /* No good, release unusable value and try again */
1672 0 : pfree(DatumGetPointer(workstr_const->constvalue));
1673 0 : pfree(workstr_const);
1674 : }
1675 :
1676 : /*
1677 : * No luck here, so truncate off the last character and try to
1678 : * increment the next one.
1679 : */
1680 0 : len -= charlen;
1681 0 : workstr[len] = '\0';
1682 : }
1683 :
1684 : /* Failed... */
1685 0 : if (cmptxt)
1686 0 : pfree(cmptxt);
1687 0 : pfree(workstr);
1688 :
1689 0 : return NULL;
1690 : }
1691 :
1692 : /*
1693 : * Generate a Datum of the appropriate type from a C string.
1694 : * Note that all of the supported types are pass-by-ref, so the
1695 : * returned value should be pfree'd if no longer needed.
1696 : */
1697 : static Datum
1698 9348 : string_to_datum(const char *str, Oid datatype)
1699 : {
1700 : Assert(str != NULL);
1701 :
1702 : /*
1703 : * We cheat a little by assuming that CStringGetTextDatum() will do for
1704 : * bpchar and varchar constants too...
1705 : */
1706 9348 : if (datatype == NAMEOID)
1707 0 : return DirectFunctionCall1(namein, CStringGetDatum(str));
1708 9348 : else if (datatype == BYTEAOID)
1709 0 : return DirectFunctionCall1(byteain, CStringGetDatum(str));
1710 : else
1711 9348 : return CStringGetTextDatum(str);
1712 : }
1713 :
1714 : /*
1715 : * Generate a Const node of the appropriate type from a C string.
1716 : */
1717 : static Const *
1718 9348 : string_to_const(const char *str, Oid datatype)
1719 : {
1720 9348 : Datum conval = string_to_datum(str, datatype);
1721 : Oid collation;
1722 : int constlen;
1723 :
1724 : /*
1725 : * We only need to support a few datatypes here, so hard-wire properties
1726 : * instead of incurring the expense of catalog lookups.
1727 : */
1728 9348 : switch (datatype)
1729 : {
1730 9348 : case TEXTOID:
1731 : case VARCHAROID:
1732 : case BPCHAROID:
1733 9348 : collation = DEFAULT_COLLATION_OID;
1734 9348 : constlen = -1;
1735 9348 : break;
1736 :
1737 0 : case NAMEOID:
1738 0 : collation = C_COLLATION_OID;
1739 0 : constlen = NAMEDATALEN;
1740 0 : break;
1741 :
1742 0 : case BYTEAOID:
1743 0 : collation = InvalidOid;
1744 0 : constlen = -1;
1745 0 : break;
1746 :
1747 0 : default:
1748 0 : elog(ERROR, "unexpected datatype in string_to_const: %u",
1749 : datatype);
1750 : return NULL;
1751 : }
1752 :
1753 9348 : return makeConst(datatype, -1, collation, constlen,
1754 : conval, false, false);
1755 : }
1756 :
1757 : /*
1758 : * Generate a Const node of bytea type from a binary C string and a length.
1759 : */
1760 : static Const *
1761 8 : string_to_bytea_const(const char *str, size_t str_len)
1762 : {
1763 8 : bytea *bstr = palloc(VARHDRSZ + str_len);
1764 : Datum conval;
1765 :
1766 8 : memcpy(VARDATA(bstr), str, str_len);
1767 8 : SET_VARSIZE(bstr, VARHDRSZ + str_len);
1768 8 : conval = PointerGetDatum(bstr);
1769 :
1770 8 : return makeConst(BYTEAOID, -1, InvalidOid, -1, conval, false, false);
1771 : }
|
