Debian Codegraph @

src/backend/utils/adt/like_support.c

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