Changeset: 4d0f6ba88845 for MonetDB
URL: https://dev.monetdb.org/hg/MonetDB/rev/4d0f6ba88845
Modified Files:
monetdb5/modules/mal/pcre.c
Branch: Jun2023
Log Message:
Optimize the ILIKE operator performance when the pattern is ASCII
If the pattern of the ILIKE operator only contains ASCII characters we
can avoid using UTF-8 routines for comparison and we can compare bytes
after doing a cheap transformation to lowercase.
diffs (truncated from 792 to 300 lines):
diff --git a/monetdb5/modules/mal/pcre.c b/monetdb5/modules/mal/pcre.c
--- a/monetdb5/modules/mal/pcre.c
+++ b/monetdb5/modules/mal/pcre.c
@@ -51,7 +51,7 @@ typedef regex_t pcre;
struct RE {
char *k;
uint32_t *w;
- bool search:1, atend:1;
+ bool search:1, atend:1, is_ascii:1, case_ignore:1;
size_t len;
struct RE *n;
};
@@ -337,6 +337,9 @@ re_is_pattern_properly_escaped(const cha
return escaped ? false : true;
}
+/* returns true if the pattern does not contain wildcard
+ * characters ('%' or '_') and no character is escaped
+ */
static inline bool
is_strcmpable(const char *pat, const char *esc)
{
@@ -345,24 +348,115 @@ is_strcmpable(const char *pat, const cha
return strlen(esc) == 0 || strNil(esc) || strstr(pat, esc) == NULL;
}
-static inline bool
-re_match_ignore(const char *restrict s, const struct RE *restrict pattern)
+/* Compare two strings ignoring case. When both strings are
+ * lower case this function returns the same result as strcmp.
+ */
+static int
+istrcmp(const char *s1, const char *s2)
{
- const struct RE *r;
+ char c1, c2;
+ const char *p1, *p2;
+ for (p1 = s1, p2 = s2; *p1 && *p2; p1++, p2++) {
+ c1 = *p1;
+ c2 = *p2;
- for (r = pattern; r; r = r->n) {
- if (*r->w == 0 && (r->search || *s == 0))
- return true;
- if (!*s ||
- (r->search
- ? (s = mywstrcasestr(s, r->w, r->atend)) == NULL
- : !mywstrncaseeq(s, r->w, r->len, r->atend)))
- return false;
- s += r->len;
+ if ('A' <= c1 && c1 <= 'Z')
+ c1 += 'a' - 'A';
+
+ if ('A' <= c2 && c2 <= 'Z')
+ c2 += 'a' - 'A';
+
+ if (c1 != c2)
+ return (c1 - c2);
}
- return true;
+
+ if (*p1 != *p2)
+ return *p1 - *p2;
+
+ return 0;
}
+/* Compare at most len characters of two strings ignoring
+ * case. When both strings are lowercase this function
+ * returns the same result as strncmp.
+ */
+static int
+istrncmp(const char *s1, const char *s2, size_t len)
+{
+ char c1, c2;
+ const char *p1, *p2;
+ size_t n = 0;
+
+ for (p1 = s1, p2 = s2; *p1 && *p2 && (n < len); p1++, p2++, n++) {
+ c1 = *p1;
+ c2 = *p2;
+
+ if ('A' <= c1 && c1 <= 'Z')
+ c1 += 'a' - 'A';
+
+ if ('A' <= c2 && c2 <= 'Z')
+ c2 += 'a' - 'A';
+
+ if (c1 != c2)
+ return c1 - c2;
+ }
+
+ if (*p1 != *p2 && n < len)
+ return *p1 - *p2;
+
+ return 0;
+}
+
+
+/* Find the first occurence of the substring needle in
+ * haystack ignoring case.
+ *
+ * NOTE: This function assumes that the needle is already
+ * lowercase.
+ */
+static const char *
+istrstr(const char *haystack, const char *needle)
+{
+ const char *ph;
+ const char *pn;
+ const char *p1;
+ bool match = true;
+
+ for (ph = haystack; *ph; ph++) {
+ match = true;
+ for (pn = needle, p1 = ph; *pn && *p1; pn++, p1++) {
+ char c1 = *pn;
+ char c2 = ('A' <= *p1 && *p1 <= 'Z') ? *p1 - 'A' + 'a'
: *p1;
+ if (c1 != c2) {
+ match = false;
+ break;
+ }
+ }
+
+ /* We reached the end of the haystack, but we still have
characters in
+ * needle. None of the future iterations will match.
+ */
+ if (*p1 == 0 && *pn != 0) {
+ break;
+ }
+
+ if (match) {
+ return ph;
+ }
+ }
+ return NULL;
+}
+
+/* Match regular expression by comparing bytes.
+ *
+ * This is faster than re_match_ignore, because it does not
+ * need to decode characters. This function should be used
+ * in all cases except when we need to perform UTF-8
+ * comparisons ignoring case.
+ *
+ * TODO: The name of the function is no longer accurate and
+ * needs to change.
+ */
static inline bool
re_match_no_ignore(const char *restrict s, const struct RE *restrict pattern)
{
@@ -375,10 +469,44 @@ re_match_no_ignore(const char *restrict
if (!*s ||
(r->search
? (r->atend
- ? (l = strlen(s)) < r->len || strcmp(s + l -
r->len, r->k) != 0
- : (s = strstr(s, r->k)) == NULL)
+ ? (r->case_ignore
+ ? (l = strlen(s)) < r->len || istrcmp(s + l
- r->len, r->k) != 0
+ : (l = strlen(s)) < r->len || strcmp(s + l -
r->len, r->k) != 0)
+ : (r->case_ignore ? (s = istrstr(s, r->k)) ==
NULL
+ : (s = strstr(s, r->k)) == NULL))
: (r->atend
- ? strcmp(s, r->k) != 0 : strncmp(s, r->k,
r->len) != 0)))
+ ? (r->case_ignore ? istrcmp(s, r->k) != 0
+ : strcmp(s, r->k) != 0)
+ : (r->case_ignore ? istrncmp(s, r->k, r->len)
!= 0
+ : strncmp(s, r->k, r->len) != 0))))
+ return false;
+ s += r->len;
+ }
+ return true;
+}
+
+/* Match a regular expression by comparing wide characters.
+ *
+ * This needs to be used when we need to perform a
+ * case-ignoring comparions involving UTF-8 characters.
+ */
+static inline bool
+re_match_ignore(const char *restrict s, const struct RE *restrict pattern)
+{
+ const struct RE *r;
+
+ /* Since the pattern is ascii, do the cheaper comparison */
+ if (pattern->is_ascii) {
+ return re_match_no_ignore(s, pattern);
+ }
+
+ for (r = pattern; r; r = r->n) {
+ if (*r->w == 0 && (r->search || *s == 0))
+ return true;
+ if (!*s ||
+ (r->search
+ ? (s = mywstrcasestr(s, r->w, r->atend)) == NULL
+ : !mywstrncaseeq(s, r->w, r->len, r->atend)))
return false;
s += r->len;
}
@@ -400,13 +528,16 @@ re_destroy(struct RE *p)
}
}
-/* Create a linked list of RE structures. Depending on the caseignore
- * flag, the w (if true) or the k (if false) field is used. These
- * fields in the first structure are allocated, whereas in all
- * subsequent structures the fields point into the allocated buffer of
- * the first. */
+/* Create a linked list of RE structures. Depending on the
+ * caseignore and the ascii_pattern flags, the w
+ * (if caseignore == true && ascii_pattern == false) or the k
+ * (in every other case) field is used. These in the first
+ * structure are allocated, whereas in all subsequent
+ * structures the fields point into the allocated buffer of
+ * the first.
+ */
static struct RE *
-re_create(const char *pat, bool caseignore, uint32_t esc)
+re_create(const char *pat, bool caseignore, bool ascii_pattern, uint32_t esc)
{
struct RE *r = GDKmalloc(sizeof(struct RE)), *n = r;
bool escaped = false;
@@ -419,7 +550,7 @@ re_create(const char *pat, bool caseigno
pat++; /* skip % */
r->search = true;
}
- if (caseignore) {
+ if (caseignore && !ascii_pattern) {
uint32_t *wp;
uint32_t *wq;
wp = utf8stoucs(pat);
@@ -465,6 +596,18 @@ re_create(const char *pat, bool caseigno
GDKfree(r);
return NULL;
}
+ if (ascii_pattern)
+ n->is_ascii = true;
+ if (caseignore)
+ n->case_ignore = true;
+
+ if (ascii_pattern && caseignore) {
+ for (q = p; *q != 0; q++) {
+ if ('A' <= *q && *q <= 'Z')
+ *q += 'a' - 'A';
+ }
+ }
+
r->k = p;
q = p;
while (*p) {
@@ -487,11 +630,21 @@ re_create(const char *pat, bool caseigno
.atend = true,
.k = p + 1
};
+ if (ascii_pattern) {
+ n->is_ascii = true;
+ }
+ if (caseignore) {
+ n->case_ignore = true;
+ }
}
*q = 0;
q = p + 1;
} else {
- *q++ = *p;
+ char c = *p;
+ if (ascii_pattern && caseignore && 'A' <= c &&
c <= 'Z') {
+ c += 'a' - 'A';
+ }
+ *q++ = c;
n->len++;
}
p++;
@@ -1299,15 +1452,30 @@ PCREsql2pcre(str *ret, const str *pat, c
return sql2pcre(ret, *pat, *esc);
}
+static bool
+is_ascii_str(const char *pat)
+{
+ size_t len = strlen(pat);
+ for (size_t i = 0; i < len; i++) {
+ if (pat[i] & 0x80)
+ return false;
+ }
+
+ return true;
+}
+
static inline str
choose_like_path(char **ppat, bool *use_re, bool *use_strcmp, bool *empty,
- const char *pat, const char *esc)
+ bool *ascii_pattern, const char *pat, const
char *esc)
{
str res = MAL_SUCCEED;
*use_re = false;
*use_strcmp = false;
*empty = false;
+
_______________________________________________
checkin-list mailing list -- [email protected]
To unsubscribe send an email to [email protected]
