You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@doris.apache.org by "puranjay2597 (via GitHub)" <gi...@apache.org> on 2026/02/24 01:36:53 UTC
[PR] [feat](func) Add levenshtein, damerau_levenshtein, jaro_winkler, cosine_similarity, jaccard_similarity built-in scalar functions [doris]
puranjay2597 opened a new pull request, #60799:
URL: https://github.com/apache/doris/pull/60799
Adds 5 new built-in scalar functions for fuzzy string matching and similarity scoring, useful for record deduplication, search ranking, and data quality workflows:
| Function | Return type | Description |
|---|---|---|
| `levenshtein(str1, str2)` | INT | |
| `damerau_levenshtein(str1, str2)` | INT | True Damerau-Levenshtein distance (unrestricted transpositions) |
| `jaro_winkler(str1, str2)` | DOUBLE | Jaro-Winkler similarity [0.0, 1.0] |
| `cosine_similarity(str1, str2)` | DOUBLE | Cosine similarity on byte-frequency vectors [0.0, 1.0] |
| `jaccard_similarity(str1, str2)` | DOUBLE | Jaccard similarity on byte bigrams [0.0, 1.0] |
All functions accept `VARCHAR` and `STRING` inputs and propagate NULL.
### Release note
Add 5 built-in string similarity/distance functions: `levenshtein`, `damerau_levenshtein`, `jaro_winkler`, `cosine_similarity`, `jaccard_similarity`.
### Check List (For Author)
- Test
- [x] Manual test (add detailed scripts or steps below)
```sql
-- Levenshtein
SELECT levenshtein('kitten', 'sitting'); -- 3
SELECT levenshtein('', 'abc'); -- 3
-- Damerau-Levenshtein (true, not OSA)
SELECT damerau_levenshtein('ca', 'abc'); -- 2 (transposition ca->ac + insert b)
SELECT damerau_levenshtein('kitten', 'sitting'); -- 3
-- Jaro-Winkler
SELECT jaro_winkler('MARTHA', 'MARHTA'); -- ~0.9611
SELECT jaro_winkler('abc', 'abc'); -- 1.0
-- Cosine similarity
SELECT cosine_similarity('hello', 'hello'); -- 1.0
SELECT cosine_similarity('hello', 'world'); -- ~0.516
-- Jaccard similarity
SELECT jaccard_similarity('night', 'nacht'); -- ~0.222
SELECT jaccard_similarity('abc', 'abc'); -- 1.0
```
### Performance
Benchmarked against equivalent Java UDFs on Apache Doris 4.0.2
**Test setup:** 100M rows × 96-char strings (md5-generated), `SELECT count(func(a, b))` to isolate compute from I/O.
| Rows | C++ builtin | Java UDF | Speedup |
|---|---|---|---|
| 1M | 1.5s | 6.5s | 4.3x* |
| 100M | 2m 20s | 4m 25s | ~1.9x |
| 1B | 19m | 36m | ~1.89x |
| 400M production rows (repeated query) | 0.11s | 96s | ~870x |
\* 1M speedup is JVM-warmup-inflated; 100M and 1B represent fully JIT-compiled steady state.
Key observations:
- **Consistent ~2x speedup** at scale (100M and 1B confirm the JVM reaches full JIT compilation and the advantage stabilises).
- **Result cache**: C++ builtins benefit from Doris SQL-layer result caching keyed on query text + data version. Java UDFs bypass the result cache entirely and always recompute — explaining the ~870x gap on repeated queries.
- **Stack allocation**: `levenshtein`, `jaro_winkler`, and `jaccard_similarity` use stack-allocated arrays for strings ≤512 bytes, eliminating heap allocation for the common case.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](func) Add levenshtein, damerau_levenshtein, jaro_winkler, jaccard_similarity built-in scalar functions [doris]
Posted by "zclllyybb (via GitHub)" <gi...@apache.org>.
zclllyybb commented on PR #60799:
URL: https://github.com/apache/doris/pull/60799#issuecomment-4277601723
continue by https://github.com/apache/doris/pull/60412
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](func) Add levenshtein, damerau_levenshtein, jaro_winkler, jaccard_similarity built-in scalar functions [doris]
Posted by "doris-robot (via GitHub)" <gi...@apache.org>.
doris-robot commented on PR #60799:
URL: https://github.com/apache/doris/pull/60799#issuecomment-3992152577
# BE UT Coverage Report
Increment line coverage `78.50% (168/214)` :tada:
[Increment coverage report](http://coverage.selectdb-in.cc/coverage/54ddedd1a57e5d4232dc5735396482acc38d693d_54ddedd1a57e5d4232dc5735396482acc38d693d/increment_report/index.html)
[Complete coverage report](http://coverage.selectdb-in.cc/coverage/54ddedd1a57e5d4232dc5735396482acc38d693d_54ddedd1a57e5d4232dc5735396482acc38d693d/report/index.html)
| Category | Coverage |
|-------------------|--------------------|
| Function Coverage | 52.57% (19643/37364) |
| Line Coverage | 36.20% (183513/506901) |
| Region Coverage | 32.50% (142336/437987) |
| Branch Coverage | 33.46% (61760/184581) |
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](func) Add levenshtein, damerau_levenshtein, jaro_winkler, jaccard_similarity built-in scalar functions [doris]
Posted by "hello-stephen (via GitHub)" <gi...@apache.org>.
hello-stephen commented on PR #60799:
URL: https://github.com/apache/doris/pull/60799#issuecomment-3961934445
# BE Regression && UT Coverage Report
Increment line coverage `78.50% (168/214)` :tada:
[Increment coverage report](http://coverage.selectdb-in.cc/coverage/60799_0c3b86a6851ef55a2713bd99a18f326bc9d6c677_merge/increment_report/index.html)
[Complete coverage report](http://coverage.selectdb-in.cc/coverage/60799_0c3b86a6851ef55a2713bd99a18f326bc9d6c677_merge/report/index.html)
| Category | Coverage |
|-------------------|--------------------|
| Function Coverage | 57.17% (20887/36535) |
| Line Coverage | 40.23% (202862/504263) |
| Region Coverage | 36.90% (162695/440901) |
| Branch Coverage | 37.58% (69357/184543) |
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](func) Add levenshtein, damerau_levenshtein, jaro_winkler, jaccard_similarity built-in scalar functions [doris]
Posted by "linrrzqqq (via GitHub)" <gi...@apache.org>.
linrrzqqq commented on code in PR #60799:
URL: https://github.com/apache/doris/pull/60799#discussion_r2899069590
##########
be/src/vec/functions/function_string.cpp:
##########
@@ -290,6 +290,275 @@ struct FindInSetOp {
}
};
+struct NameLevenshtein {
+ static constexpr auto name = "levenshtein";
+};
+
+struct LevenshteinOp {
+ using ResultDataType = DataTypeInt32;
+ using ResultPaddedPODArray = PaddedPODArray<Int32>;
+
+ static void execute(const std::string_view& s, const std::string_view& t, int32_t& res) {
+ const size_t m = s.size();
+ const size_t n = t.size();
+ if (m == 0) {
+ res = static_cast<int32_t>(n);
+ return;
+ }
+ if (n == 0) {
+ res = static_cast<int32_t>(m);
+ return;
+ }
+ if (s == t) {
+ res = 0;
+ return;
+ }
+ // Guard against excessive O(m*n) computation on very large inputs.
+ // Limit each string to 65535 bytes (max VARCHAR length).
+ constexpr size_t MAX_INPUT_LEN = 65535;
+ if (m > MAX_INPUT_LEN || n > MAX_INPUT_LEN) {
+ throw doris::Exception(ErrorCode::INVALID_ARGUMENT,
+ "Input string too long for levenshtein, max {} bytes",
+ MAX_INPUT_LEN);
+ }
+ constexpr size_t STACK_MAX = 512;
+ int32_t prev_stk[STACK_MAX + 1], curr_stk[STACK_MAX + 1];
+ std::vector<int32_t> prev_heap, curr_heap;
+ int32_t* prev_row;
+ int32_t* curr_row;
+ if (n <= STACK_MAX) {
+ prev_row = prev_stk;
+ curr_row = curr_stk;
+ } else {
+ prev_heap.resize(n + 1);
+ curr_heap.resize(n + 1);
+ prev_row = prev_heap.data();
+ curr_row = curr_heap.data();
+ }
+ for (size_t j = 0; j <= n; ++j) prev_row[j] = static_cast<int32_t>(j);
+ for (size_t i = 1; i <= m; ++i) {
+ curr_row[0] = static_cast<int32_t>(i);
+ for (size_t j = 1; j <= n; ++j) {
+ if (s[i - 1] == t[j - 1]) {
+ curr_row[j] = prev_row[j - 1];
+ } else {
+ curr_row[j] = 1 + std::min({prev_row[j - 1], prev_row[j], curr_row[j - 1]});
+ }
+ }
+ std::swap(prev_row, curr_row);
+ }
+ res = prev_row[n];
+ }
+};
+
+struct NameDamerauLevenshtein {
+ static constexpr auto name = "damerau_levenshtein";
+};
+
+struct DamerauLevenshteinOp {
+ using ResultDataType = DataTypeInt32;
+ using ResultPaddedPODArray = PaddedPODArray<Int32>;
+
+ static void execute(const std::string_view& s, const std::string_view& t, int32_t& res) {
+ const size_t m = s.size(), n = t.size();
+ if (m == 0) {
+ res = static_cast<int32_t>(n);
+ return;
+ }
+ if (n == 0) {
+ res = static_cast<int32_t>(m);
+ return;
+ }
+ // Guard against OOM: the DP matrix allocates (m+2)*(n+2)*sizeof(int32_t) bytes.
+ // At 10000 chars each that is ~400 MB; cap well below VARCHAR max (65535).
+ constexpr size_t MAX_INPUT_LEN = 10000;
+ if (m > MAX_INPUT_LEN || n > MAX_INPUT_LEN) {
+ throw doris::Exception(ErrorCode::INVALID_ARGUMENT,
+ "Input string too long for damerau_levenshtein, max {} bytes",
+ MAX_INPUT_LEN);
+ }
+ const size_t stride = n + 2;
+ const int32_t max_dist = static_cast<int32_t>(m + n);
+ std::vector<int32_t> d((m + 2) * stride, 0);
+ d[0] = max_dist;
+ for (size_t i = 0; i <= m; ++i) {
+ d[(i + 1) * stride + 0] = max_dist;
+ d[(i + 1) * stride + 1] = static_cast<int32_t>(i);
+ }
+ for (size_t j = 0; j <= n; ++j) {
+ d[0 * stride + (j + 1)] = max_dist;
+ d[1 * stride + (j + 1)] = static_cast<int32_t>(j);
+ }
+ int32_t da[256] = {};
+ for (size_t i = 1; i <= m; ++i) {
+ int32_t db = 0;
+ for (size_t j = 1; j <= n; ++j) {
+ const int32_t k = da[(uint8_t)t[j - 1]];
+ const int32_t l = db;
+ int32_t cost;
+ if (s[i - 1] == t[j - 1]) {
+ cost = 0;
+ db = static_cast<int32_t>(j);
+ } else {
+ cost = 1;
+ }
+ const int32_t trans = d[static_cast<size_t>(k) * stride + static_cast<size_t>(l)] +
+ (static_cast<int32_t>(i) - k - 1) + 1 +
+ (static_cast<int32_t>(j) - l - 1);
+ d[(i + 1) * stride + (j + 1)] =
+ std::min({d[i * stride + j] + cost, d[(i + 1) * stride + j] + 1,
+ d[i * stride + (j + 1)] + 1, trans});
+ }
+ da[(uint8_t)s[i - 1]] = static_cast<int32_t>(i);
+ }
+ res = d[(m + 1) * stride + (n + 1)];
+ }
+};
+
+struct NameJaroWinkler {
+ static constexpr auto name = "jaro_winkler";
+};
+
+struct JaroWinklerOp {
+ using ResultDataType = DataTypeFloat64;
+ using ResultPaddedPODArray = PaddedPODArray<Float64>;
+
+ static void execute(const std::string_view& s, const std::string_view& t, double& res) {
+ if (s == t) {
+ res = 1.0;
+ return;
+ }
+ const size_t m = s.size(), n = t.size();
+ if (m == 0 || n == 0) {
+ res = 0.0;
+ return;
+ }
+ // Guard against O(m*n/2) matching loop and heap allocation of m+n bytes.
+ constexpr size_t MAX_INPUT_LEN = 65535;
+ if (m > MAX_INPUT_LEN || n > MAX_INPUT_LEN) {
+ throw doris::Exception(ErrorCode::INVALID_ARGUMENT,
+ "Input string too long for jaro_winkler, max {} bytes",
+ MAX_INPUT_LEN);
+ }
+ const size_t match_dist = std::max(m, n) / 2 - (std::max(m, n) >= 2 ? 1 : 0);
+ constexpr size_t STACK_MAX = 512;
+ uint8_t s_stk[STACK_MAX] = {};
+ uint8_t t_stk[STACK_MAX] = {};
+ std::vector<uint8_t> s_heap, t_heap;
+ uint8_t* sm;
+ uint8_t* tm;
+ if (m <= STACK_MAX && n <= STACK_MAX) {
+ sm = s_stk;
+ tm = t_stk;
+ } else {
+ s_heap.assign(m, 0);
+ t_heap.assign(n, 0);
+ sm = s_heap.data();
+ tm = t_heap.data();
+ }
+ double matches = 0;
+ for (size_t i = 0; i < m; ++i) {
+ const size_t start = (i >= match_dist) ? i - match_dist : 0;
+ const size_t end = std::min(i + match_dist + 1, n);
+ for (size_t j = start; j < end; ++j) {
+ if (!tm[j] && s[i] == t[j]) {
+ sm[i] = tm[j] = 1;
+ ++matches;
+ break;
+ }
+ }
+ }
+ if (matches == 0.0) {
+ res = 0.0;
+ return;
+ }
+ double transpositions = 0;
+ size_t k = 0;
+ for (size_t i = 0; i < m; ++i) {
+ if (sm[i]) {
+ while (!tm[k]) ++k;
+ if (s[i] != t[k]) ++transpositions;
+ ++k;
+ }
+ }
+ const double jaro = (matches / static_cast<double>(m) + matches / static_cast<double>(n) +
+ (matches - transpositions / 2.0) / matches) /
+ 3.0;
+ size_t prefix = 0;
+ const size_t max_prefix = std::min(static_cast<size_t>(4), std::min(m, n));
+ while (prefix < max_prefix && s[prefix] == t[prefix]) ++prefix;
+ res = jaro + static_cast<double>(prefix) * 0.1 * (1.0 - jaro);
+ }
+};
+
+struct NameJaccardSimilarity {
+ static constexpr auto name = "jaccard_similarity";
+};
+
+struct JaccardSimilarityOp {
+ using ResultDataType = DataTypeFloat64;
+ using ResultPaddedPODArray = PaddedPODArray<Float64>;
+
+ static void execute(const std::string_view& s, const std::string_view& t, double& res) {
+ if (s == t) {
+ res = 1.0;
+ return;
+ }
+ if (s.size() < 2 || t.size() < 2) {
+ res = 0.0;
+ return;
+ }
+ const size_t m = s.size(), n = t.size();
+ // Guard against heap allocation of 2*(m+n) bytes for very large STRING inputs.
+ constexpr size_t MAX_INPUT_LEN = 65535;
+ if (m > MAX_INPUT_LEN || n > MAX_INPUT_LEN) {
+ throw doris::Exception(ErrorCode::INVALID_ARGUMENT,
+ "Input string too long for jaccard_similarity, max {} bytes",
+ MAX_INPUT_LEN);
+ }
+
+ auto collect = [](const std::string_view& str, uint16_t* out) -> size_t {
+ size_t cnt = 0;
+ for (size_t i = 0; i + 1 < str.size(); ++i)
+ out[cnt++] = static_cast<uint16_t>((static_cast<uint16_t>((uint8_t)str[i]) << 8) |
+ (uint8_t)str[i + 1]);
+ std::sort(out, out + cnt);
Review Comment:
try to use bitmap to collect and do intersects/union
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](func) Add levenshtein, damerau_levenshtein, jaro_winkler, jaccard_similarity built-in scalar functions [doris]
Posted by "linrrzqqq (via GitHub)" <gi...@apache.org>.
linrrzqqq commented on code in PR #60799:
URL: https://github.com/apache/doris/pull/60799#discussion_r2899003759
##########
be/src/vec/functions/function_string.cpp:
##########
@@ -290,6 +290,275 @@ struct FindInSetOp {
}
};
+struct NameLevenshtein {
+ static constexpr auto name = "levenshtein";
+};
+
+struct LevenshteinOp {
+ using ResultDataType = DataTypeInt32;
+ using ResultPaddedPODArray = PaddedPODArray<Int32>;
+
+ static void execute(const std::string_view& s, const std::string_view& t, int32_t& res) {
+ const size_t m = s.size();
+ const size_t n = t.size();
+ if (m == 0) {
+ res = static_cast<int32_t>(n);
+ return;
+ }
+ if (n == 0) {
+ res = static_cast<int32_t>(m);
+ return;
+ }
+ if (s == t) {
+ res = 0;
+ return;
+ }
+ // Guard against excessive O(m*n) computation on very large inputs.
+ // Limit each string to 65535 bytes (max VARCHAR length).
+ constexpr size_t MAX_INPUT_LEN = 65535;
+ if (m > MAX_INPUT_LEN || n > MAX_INPUT_LEN) {
+ throw doris::Exception(ErrorCode::INVALID_ARGUMENT,
+ "Input string too long for levenshtein, max {} bytes",
+ MAX_INPUT_LEN);
+ }
+ constexpr size_t STACK_MAX = 512;
+ int32_t prev_stk[STACK_MAX + 1], curr_stk[STACK_MAX + 1];
+ std::vector<int32_t> prev_heap, curr_heap;
+ int32_t* prev_row;
+ int32_t* curr_row;
+ if (n <= STACK_MAX) {
+ prev_row = prev_stk;
+ curr_row = curr_stk;
+ } else {
+ prev_heap.resize(n + 1);
+ curr_heap.resize(n + 1);
+ prev_row = prev_heap.data();
+ curr_row = curr_heap.data();
+ }
+ for (size_t j = 0; j <= n; ++j) prev_row[j] = static_cast<int32_t>(j);
+ for (size_t i = 1; i <= m; ++i) {
+ curr_row[0] = static_cast<int32_t>(i);
+ for (size_t j = 1; j <= n; ++j) {
+ if (s[i - 1] == t[j - 1]) {
+ curr_row[j] = prev_row[j - 1];
+ } else {
+ curr_row[j] = 1 + std::min({prev_row[j - 1], prev_row[j], curr_row[j - 1]});
+ }
+ }
+ std::swap(prev_row, curr_row);
+ }
+ res = prev_row[n];
+ }
+};
+
+struct NameDamerauLevenshtein {
+ static constexpr auto name = "damerau_levenshtein";
+};
+
+struct DamerauLevenshteinOp {
+ using ResultDataType = DataTypeInt32;
+ using ResultPaddedPODArray = PaddedPODArray<Int32>;
+
+ static void execute(const std::string_view& s, const std::string_view& t, int32_t& res) {
+ const size_t m = s.size(), n = t.size();
+ if (m == 0) {
+ res = static_cast<int32_t>(n);
+ return;
+ }
+ if (n == 0) {
+ res = static_cast<int32_t>(m);
+ return;
+ }
+ // Guard against OOM: the DP matrix allocates (m+2)*(n+2)*sizeof(int32_t) bytes.
+ // At 10000 chars each that is ~400 MB; cap well below VARCHAR max (65535).
+ constexpr size_t MAX_INPUT_LEN = 10000;
+ if (m > MAX_INPUT_LEN || n > MAX_INPUT_LEN) {
+ throw doris::Exception(ErrorCode::INVALID_ARGUMENT,
+ "Input string too long for damerau_levenshtein, max {} bytes",
+ MAX_INPUT_LEN);
+ }
+ const size_t stride = n + 2;
+ const int32_t max_dist = static_cast<int32_t>(m + n);
+ std::vector<int32_t> d((m + 2) * stride, 0);
+ d[0] = max_dist;
+ for (size_t i = 0; i <= m; ++i) {
+ d[(i + 1) * stride + 0] = max_dist;
+ d[(i + 1) * stride + 1] = static_cast<int32_t>(i);
+ }
+ for (size_t j = 0; j <= n; ++j) {
+ d[0 * stride + (j + 1)] = max_dist;
+ d[1 * stride + (j + 1)] = static_cast<int32_t>(j);
+ }
+ int32_t da[256] = {};
+ for (size_t i = 1; i <= m; ++i) {
+ int32_t db = 0;
+ for (size_t j = 1; j <= n; ++j) {
+ const int32_t k = da[(uint8_t)t[j - 1]];
+ const int32_t l = db;
+ int32_t cost;
+ if (s[i - 1] == t[j - 1]) {
+ cost = 0;
+ db = static_cast<int32_t>(j);
+ } else {
+ cost = 1;
+ }
+ const int32_t trans = d[static_cast<size_t>(k) * stride + static_cast<size_t>(l)] +
+ (static_cast<int32_t>(i) - k - 1) + 1 +
+ (static_cast<int32_t>(j) - l - 1);
+ d[(i + 1) * stride + (j + 1)] =
+ std::min({d[i * stride + j] + cost, d[(i + 1) * stride + j] + 1,
+ d[i * stride + (j + 1)] + 1, trans});
+ }
+ da[(uint8_t)s[i - 1]] = static_cast<int32_t>(i);
+ }
+ res = d[(m + 1) * stride + (n + 1)];
+ }
+};
+
+struct NameJaroWinkler {
+ static constexpr auto name = "jaro_winkler";
+};
+
+struct JaroWinklerOp {
Review Comment:
ditto in other function
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](func) Add levenshtein, damerau_levenshtein, jaro_winkler, jaccard_similarity built-in scalar functions [doris]
Posted by "doris-robot (via GitHub)" <gi...@apache.org>.
doris-robot commented on PR #60799:
URL: https://github.com/apache/doris/pull/60799#issuecomment-3991095458
<details>
<summary>TPC-H: <b>Total hot run time: 28831 ms</b></summary>
```
machine: 'aliyun_ecs.c7a.8xlarge_32C64G'
scripts: https://github.com/apache/doris/tree/master/tools/tpch-tools
Tpch sf100 test result on commit 54ddedd1a57e5d4232dc5735396482acc38d693d, data reload: false
------ Round 1 ----------------------------------
============================================
q1 17626 4368 4286 4286
q2 q3 10642 772 514 514
q4 4681 353 252 252
q5 7553 1201 1038 1038
q6 178 181 147 147
q7 779 853 667 667
q8 9304 1497 1308 1308
q9 4768 4714 4710 4710
q10 6771 1861 1639 1639
q11 462 269 229 229
q12 708 565 465 465
q13 17760 4171 3429 3429
q14 235 232 217 217
q15 907 797 791 791
q16 733 734 678 678
q17 719 854 423 423
q18 5916 5391 5249 5249
q19 1175 976 631 631
q20 503 496 393 393
q21 4786 2019 1491 1491
q22 418 315 274 274
Total cold run time: 96624 ms
Total hot run time: 28831 ms
----- Round 2, with runtime_filter_mode=off -----
============================================
q1 4593 4537 4560 4537
q2 q3 1798 2199 1798 1798
q4 898 1192 756 756
q5 4035 4352 4333 4333
q6 178 195 143 143
q7 1785 1634 1524 1524
q8 2469 2848 2548 2548
q9 7453 7243 7489 7243
q10 2623 2849 2422 2422
q11 535 457 446 446
q12 520 627 442 442
q13 3915 4364 3562 3562
q14 277 293 279 279
q15 843 798 804 798
q16 739 769 764 764
q17 1188 1576 1319 1319
q18 7006 6782 6564 6564
q19 884 859 990 859
q20 2104 2285 2014 2014
q21 3989 3372 3284 3284
q22 472 424 382 382
Total cold run time: 48304 ms
Total hot run time: 46017 ms
```
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](func) Add levenshtein, damerau_levenshtein, jaro_winkler, jaccard_similarity built-in scalar functions [doris]
Posted by "hello-stephen (via GitHub)" <gi...@apache.org>.
hello-stephen commented on PR #60799:
URL: https://github.com/apache/doris/pull/60799#issuecomment-3992190426
# BE Regression && UT Coverage Report
Increment line coverage `88.32% (189/214)` :tada:
[Increment coverage report](http://coverage.selectdb-in.cc/coverage/60799_54ddedd1a57e5d4232dc5735396482acc38d693d_merge/increment_report/index.html)
[Complete coverage report](http://coverage.selectdb-in.cc/coverage/60799_54ddedd1a57e5d4232dc5735396482acc38d693d_merge/report/index.html)
| Category | Coverage |
|-------------------|--------------------|
| Function Coverage | 73.28% (26808/36582) |
| Line Coverage | 56.55% (285740/505243) |
| Region Coverage | 54.00% (238670/442020) |
| Branch Coverage | 55.61% (102932/185102) |
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](func) Add levenshtein, damerau_levenshtein, jaro_winkler, jaccard_similarity built-in scalar functions [doris]
Posted by "puranjay2597 (via GitHub)" <gi...@apache.org>.
puranjay2597 commented on PR #60799:
URL: https://github.com/apache/doris/pull/60799#issuecomment-3996770979
Addressed the AI code review comments:
Added input length guards to jaro_winkler and jaccard_similarity
Added negative regression test cases for all 4 functions using test { ... exception ... } pattern
Could you please run run buildall again?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](func) Add levenshtein, damerau_levenshtein, jaro_winkler, jaccard_similarity built-in scalar functions [doris]
Posted by "linrrzqqq (via GitHub)" <gi...@apache.org>.
linrrzqqq commented on code in PR #60799:
URL: https://github.com/apache/doris/pull/60799#discussion_r2896118000
##########
be/src/vec/functions/function_string.cpp:
##########
@@ -290,6 +290,275 @@ struct FindInSetOp {
}
};
+struct NameLevenshtein {
+ static constexpr auto name = "levenshtein";
+};
+
+struct LevenshteinOp {
Review Comment:
It seems like you are processing strings byte by byte, but I think we need to be compatible with UTF-8 here, just like Hive does:
```text
select levenshtein('你好', '世界')
+------+
| _c0 |
+------+
| 2 |
+------+
```
Check if it is all ASCII, if not, then proceed with the UTF-8 path, you can refer to `FunctionLeft`
ditto in another three functions
##########
be/src/vec/functions/function_string.cpp:
##########
@@ -290,6 +290,275 @@ struct FindInSetOp {
}
};
+struct NameLevenshtein {
+ static constexpr auto name = "levenshtein";
+};
+
+struct LevenshteinOp {
+ using ResultDataType = DataTypeInt32;
+ using ResultPaddedPODArray = PaddedPODArray<Int32>;
+
+ static void execute(const std::string_view& s, const std::string_view& t, int32_t& res) {
+ const size_t m = s.size();
+ const size_t n = t.size();
+ if (m == 0) {
+ res = static_cast<int32_t>(n);
+ return;
+ }
+ if (n == 0) {
+ res = static_cast<int32_t>(m);
+ return;
+ }
+ if (s == t) {
+ res = 0;
+ return;
+ }
+ // Guard against excessive O(m*n) computation on very large inputs.
+ // Limit each string to 65535 bytes (max VARCHAR length).
+ constexpr size_t MAX_INPUT_LEN = 65535;
+ if (m > MAX_INPUT_LEN || n > MAX_INPUT_LEN) {
+ throw doris::Exception(ErrorCode::INVALID_ARGUMENT,
+ "Input string too long for levenshtein, max {} bytes",
+ MAX_INPUT_LEN);
+ }
+ constexpr size_t STACK_MAX = 512;
+ int32_t prev_stk[STACK_MAX + 1], curr_stk[STACK_MAX + 1];
+ std::vector<int32_t> prev_heap, curr_heap;
+ int32_t* prev_row;
+ int32_t* curr_row;
+ if (n <= STACK_MAX) {
+ prev_row = prev_stk;
+ curr_row = curr_stk;
+ } else {
+ prev_heap.resize(n + 1);
+ curr_heap.resize(n + 1);
+ prev_row = prev_heap.data();
+ curr_row = curr_heap.data();
+ }
+ for (size_t j = 0; j <= n; ++j) prev_row[j] = static_cast<int32_t>(j);
+ for (size_t i = 1; i <= m; ++i) {
+ curr_row[0] = static_cast<int32_t>(i);
+ for (size_t j = 1; j <= n; ++j) {
+ if (s[i - 1] == t[j - 1]) {
+ curr_row[j] = prev_row[j - 1];
+ } else {
+ curr_row[j] = 1 + std::min({prev_row[j - 1], prev_row[j], curr_row[j - 1]});
+ }
+ }
+ std::swap(prev_row, curr_row);
+ }
+ res = prev_row[n];
+ }
+};
+
+struct NameDamerauLevenshtein {
+ static constexpr auto name = "damerau_levenshtein";
+};
+
+struct DamerauLevenshteinOp {
+ using ResultDataType = DataTypeInt32;
+ using ResultPaddedPODArray = PaddedPODArray<Int32>;
+
+ static void execute(const std::string_view& s, const std::string_view& t, int32_t& res) {
+ const size_t m = s.size(), n = t.size();
+ if (m == 0) {
+ res = static_cast<int32_t>(n);
+ return;
+ }
+ if (n == 0) {
+ res = static_cast<int32_t>(m);
+ return;
+ }
+ // Guard against OOM: the DP matrix allocates (m+2)*(n+2)*sizeof(int32_t) bytes.
+ // At 10000 chars each that is ~400 MB; cap well below VARCHAR max (65535).
+ constexpr size_t MAX_INPUT_LEN = 10000;
+ if (m > MAX_INPUT_LEN || n > MAX_INPUT_LEN) {
+ throw doris::Exception(ErrorCode::INVALID_ARGUMENT,
+ "Input string too long for damerau_levenshtein, max {} bytes",
+ MAX_INPUT_LEN);
+ }
+ const size_t stride = n + 2;
+ const int32_t max_dist = static_cast<int32_t>(m + n);
+ std::vector<int32_t> d((m + 2) * stride, 0);
+ d[0] = max_dist;
+ for (size_t i = 0; i <= m; ++i) {
+ d[(i + 1) * stride + 0] = max_dist;
+ d[(i + 1) * stride + 1] = static_cast<int32_t>(i);
+ }
+ for (size_t j = 0; j <= n; ++j) {
+ d[0 * stride + (j + 1)] = max_dist;
+ d[1 * stride + (j + 1)] = static_cast<int32_t>(j);
+ }
+ int32_t da[256] = {};
+ for (size_t i = 1; i <= m; ++i) {
+ int32_t db = 0;
+ for (size_t j = 1; j <= n; ++j) {
+ const int32_t k = da[(uint8_t)t[j - 1]];
+ const int32_t l = db;
+ int32_t cost;
+ if (s[i - 1] == t[j - 1]) {
+ cost = 0;
+ db = static_cast<int32_t>(j);
+ } else {
+ cost = 1;
+ }
+ const int32_t trans = d[static_cast<size_t>(k) * stride + static_cast<size_t>(l)] +
+ (static_cast<int32_t>(i) - k - 1) + 1 +
+ (static_cast<int32_t>(j) - l - 1);
+ d[(i + 1) * stride + (j + 1)] =
+ std::min({d[i * stride + j] + cost, d[(i + 1) * stride + j] + 1,
+ d[i * stride + (j + 1)] + 1, trans});
+ }
+ da[(uint8_t)s[i - 1]] = static_cast<int32_t>(i);
+ }
+ res = d[(m + 1) * stride + (n + 1)];
+ }
+};
+
+struct NameJaroWinkler {
+ static constexpr auto name = "jaro_winkler";
+};
+
+struct JaroWinklerOp {
Review Comment:
Add comments to clearly explain what each section is calculating.
##########
be/src/vec/functions/function_string.cpp:
##########
@@ -290,6 +290,275 @@ struct FindInSetOp {
}
};
+struct NameLevenshtein {
+ static constexpr auto name = "levenshtein";
+};
+
+struct LevenshteinOp {
+ using ResultDataType = DataTypeInt32;
+ using ResultPaddedPODArray = PaddedPODArray<Int32>;
+
+ static void execute(const std::string_view& s, const std::string_view& t, int32_t& res) {
+ const size_t m = s.size();
+ const size_t n = t.size();
+ if (m == 0) {
+ res = static_cast<int32_t>(n);
+ return;
+ }
+ if (n == 0) {
+ res = static_cast<int32_t>(m);
+ return;
+ }
+ if (s == t) {
+ res = 0;
+ return;
+ }
+ // Guard against excessive O(m*n) computation on very large inputs.
+ // Limit each string to 65535 bytes (max VARCHAR length).
+ constexpr size_t MAX_INPUT_LEN = 65535;
+ if (m > MAX_INPUT_LEN || n > MAX_INPUT_LEN) {
+ throw doris::Exception(ErrorCode::INVALID_ARGUMENT,
+ "Input string too long for levenshtein, max {} bytes",
+ MAX_INPUT_LEN);
+ }
+ constexpr size_t STACK_MAX = 512;
+ int32_t prev_stk[STACK_MAX + 1], curr_stk[STACK_MAX + 1];
+ std::vector<int32_t> prev_heap, curr_heap;
+ int32_t* prev_row;
+ int32_t* curr_row;
+ if (n <= STACK_MAX) {
+ prev_row = prev_stk;
+ curr_row = curr_stk;
+ } else {
+ prev_heap.resize(n + 1);
+ curr_heap.resize(n + 1);
+ prev_row = prev_heap.data();
+ curr_row = curr_heap.data();
+ }
+ for (size_t j = 0; j <= n; ++j) prev_row[j] = static_cast<int32_t>(j);
+ for (size_t i = 1; i <= m; ++i) {
+ curr_row[0] = static_cast<int32_t>(i);
+ for (size_t j = 1; j <= n; ++j) {
+ if (s[i - 1] == t[j - 1]) {
+ curr_row[j] = prev_row[j - 1];
+ } else {
+ curr_row[j] = 1 + std::min({prev_row[j - 1], prev_row[j], curr_row[j - 1]});
+ }
+ }
+ std::swap(prev_row, curr_row);
+ }
+ res = prev_row[n];
+ }
+};
+
+struct NameDamerauLevenshtein {
+ static constexpr auto name = "damerau_levenshtein";
+};
+
+struct DamerauLevenshteinOp {
+ using ResultDataType = DataTypeInt32;
+ using ResultPaddedPODArray = PaddedPODArray<Int32>;
+
+ static void execute(const std::string_view& s, const std::string_view& t, int32_t& res) {
+ const size_t m = s.size(), n = t.size();
+ if (m == 0) {
+ res = static_cast<int32_t>(n);
+ return;
+ }
+ if (n == 0) {
+ res = static_cast<int32_t>(m);
+ return;
+ }
+ // Guard against OOM: the DP matrix allocates (m+2)*(n+2)*sizeof(int32_t) bytes.
+ // At 10000 chars each that is ~400 MB; cap well below VARCHAR max (65535).
+ constexpr size_t MAX_INPUT_LEN = 10000;
+ if (m > MAX_INPUT_LEN || n > MAX_INPUT_LEN) {
+ throw doris::Exception(ErrorCode::INVALID_ARGUMENT,
+ "Input string too long for damerau_levenshtein, max {} bytes",
+ MAX_INPUT_LEN);
+ }
+ const size_t stride = n + 2;
+ const int32_t max_dist = static_cast<int32_t>(m + n);
+ std::vector<int32_t> d((m + 2) * stride, 0);
+ d[0] = max_dist;
+ for (size_t i = 0; i <= m; ++i) {
+ d[(i + 1) * stride + 0] = max_dist;
+ d[(i + 1) * stride + 1] = static_cast<int32_t>(i);
+ }
+ for (size_t j = 0; j <= n; ++j) {
+ d[0 * stride + (j + 1)] = max_dist;
+ d[1 * stride + (j + 1)] = static_cast<int32_t>(j);
+ }
+ int32_t da[256] = {};
+ for (size_t i = 1; i <= m; ++i) {
+ int32_t db = 0;
+ for (size_t j = 1; j <= n; ++j) {
+ const int32_t k = da[(uint8_t)t[j - 1]];
+ const int32_t l = db;
+ int32_t cost;
+ if (s[i - 1] == t[j - 1]) {
+ cost = 0;
+ db = static_cast<int32_t>(j);
+ } else {
+ cost = 1;
+ }
+ const int32_t trans = d[static_cast<size_t>(k) * stride + static_cast<size_t>(l)] +
+ (static_cast<int32_t>(i) - k - 1) + 1 +
+ (static_cast<int32_t>(j) - l - 1);
+ d[(i + 1) * stride + (j + 1)] =
+ std::min({d[i * stride + j] + cost, d[(i + 1) * stride + j] + 1,
+ d[i * stride + (j + 1)] + 1, trans});
+ }
+ da[(uint8_t)s[i - 1]] = static_cast<int32_t>(i);
+ }
+ res = d[(m + 1) * stride + (n + 1)];
+ }
+};
+
+struct NameJaroWinkler {
+ static constexpr auto name = "jaro_winkler";
+};
+
+struct JaroWinklerOp {
+ using ResultDataType = DataTypeFloat64;
+ using ResultPaddedPODArray = PaddedPODArray<Float64>;
+
+ static void execute(const std::string_view& s, const std::string_view& t, double& res) {
+ if (s == t) {
+ res = 1.0;
+ return;
+ }
+ const size_t m = s.size(), n = t.size();
+ if (m == 0 || n == 0) {
+ res = 0.0;
+ return;
+ }
+ // Guard against O(m*n/2) matching loop and heap allocation of m+n bytes.
+ constexpr size_t MAX_INPUT_LEN = 65535;
+ if (m > MAX_INPUT_LEN || n > MAX_INPUT_LEN) {
+ throw doris::Exception(ErrorCode::INVALID_ARGUMENT,
+ "Input string too long for jaro_winkler, max {} bytes",
+ MAX_INPUT_LEN);
+ }
+ const size_t match_dist = std::max(m, n) / 2 - (std::max(m, n) >= 2 ? 1 : 0);
+ constexpr size_t STACK_MAX = 512;
+ uint8_t s_stk[STACK_MAX] = {};
+ uint8_t t_stk[STACK_MAX] = {};
+ std::vector<uint8_t> s_heap, t_heap;
+ uint8_t* sm;
+ uint8_t* tm;
+ if (m <= STACK_MAX && n <= STACK_MAX) {
+ sm = s_stk;
+ tm = t_stk;
+ } else {
+ s_heap.assign(m, 0);
+ t_heap.assign(n, 0);
+ sm = s_heap.data();
+ tm = t_heap.data();
+ }
+ double matches = 0;
+ for (size_t i = 0; i < m; ++i) {
+ const size_t start = (i >= match_dist) ? i - match_dist : 0;
+ const size_t end = std::min(i + match_dist + 1, n);
+ for (size_t j = start; j < end; ++j) {
+ if (!tm[j] && s[i] == t[j]) {
+ sm[i] = tm[j] = 1;
+ ++matches;
+ break;
+ }
+ }
+ }
+ if (matches == 0.0) {
+ res = 0.0;
+ return;
+ }
+ double transpositions = 0;
+ size_t k = 0;
+ for (size_t i = 0; i < m; ++i) {
+ if (sm[i]) {
+ while (!tm[k]) ++k;
+ if (s[i] != t[k]) ++transpositions;
+ ++k;
+ }
+ }
+ const double jaro = (matches / static_cast<double>(m) + matches / static_cast<double>(n) +
Review Comment:
implement a new function `JARO`, move the above implementation into `JARO`, and call it directly here
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](func) Add levenshtein, damerau_levenshtein, jaro_winkler, jaccard_similarity built-in scalar functions [doris]
Posted by "zclllyybb (via GitHub)" <gi...@apache.org>.
zclllyybb commented on PR #60799:
URL: https://github.com/apache/doris/pull/60799#issuecomment-3959596890
run buildall
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](func) Add levenshtein, damerau_levenshtein, jaro_winkler, jaccard_similarity built-in scalar functions [doris]
Posted by "zclllyybb (via GitHub)" <gi...@apache.org>.
zclllyybb commented on PR #60799:
URL: https://github.com/apache/doris/pull/60799#issuecomment-3956985982
run buildall
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](func) Add levenshtein, damerau_levenshtein, jaro_winkler, jaccard_similarity built-in scalar functions [doris]
Posted by "zclllyybb (via GitHub)" <gi...@apache.org>.
zclllyybb closed pull request #60799: [feat](func) Add levenshtein, damerau_levenshtein, jaro_winkler, jaccard_similarity built-in scalar functions
URL: https://github.com/apache/doris/pull/60799
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](func) Add levenshtein, damerau_levenshtein, jaro_winkler, jaccard_similarity built-in scalar functions [doris]
Posted by "linrrzqqq (via GitHub)" <gi...@apache.org>.
linrrzqqq commented on PR #60799:
URL: https://github.com/apache/doris/pull/60799#issuecomment-4015667731
impl fold constant in `fe/fe-core/src/main/java/org/apache/doris/nereids/trees/expressions/functions/executable/StringArithmetic.java`
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](func) Add levenshtein, damerau_levenshtein, jaro_winkler, jaccard_similarity built-in scalar functions [doris]
Posted by "zclllyybb (via GitHub)" <gi...@apache.org>.
zclllyybb commented on PR #60799:
URL: https://github.com/apache/doris/pull/60799#issuecomment-3990876747
/review
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](func) Add levenshtein, damerau_levenshtein, jaro_winkler, jaccard_similarity built-in scalar functions [doris]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on code in PR #60799:
URL: https://github.com/apache/doris/pull/60799#discussion_r2878179104
##########
be/src/vec/functions/function_string.cpp:
##########
@@ -290,6 +290,261 @@ struct FindInSetOp {
}
};
+struct NameLevenshtein {
+ static constexpr auto name = "levenshtein";
+};
+
+struct LevenshteinOp {
+ using ResultDataType = DataTypeInt32;
+ using ResultPaddedPODArray = PaddedPODArray<Int32>;
+
+ static void execute(const std::string_view& s, const std::string_view& t, int32_t& res) {
+ const size_t m = s.size();
+ const size_t n = t.size();
+ if (m == 0) {
+ res = static_cast<int32_t>(n);
+ return;
+ }
+ if (n == 0) {
+ res = static_cast<int32_t>(m);
+ return;
+ }
+ if (s == t) {
+ res = 0;
+ return;
+ }
+ // Guard against excessive O(m*n) computation on very large inputs.
+ // Limit each string to 65535 bytes (max VARCHAR length).
+ constexpr size_t MAX_INPUT_LEN = 65535;
+ if (m > MAX_INPUT_LEN || n > MAX_INPUT_LEN) {
+ throw doris::Exception(ErrorCode::INVALID_ARGUMENT,
+ "Input string too long for levenshtein, max {} bytes",
+ MAX_INPUT_LEN);
+ }
+ constexpr size_t STACK_MAX = 512;
+ int32_t prev_stk[STACK_MAX + 1], curr_stk[STACK_MAX + 1];
+ std::vector<int32_t> prev_heap, curr_heap;
+ int32_t* prev_row;
+ int32_t* curr_row;
+ if (n <= STACK_MAX) {
+ prev_row = prev_stk;
+ curr_row = curr_stk;
+ } else {
+ prev_heap.resize(n + 1);
+ curr_heap.resize(n + 1);
+ prev_row = prev_heap.data();
+ curr_row = curr_heap.data();
+ }
+ for (size_t j = 0; j <= n; ++j) prev_row[j] = static_cast<int32_t>(j);
+ for (size_t i = 1; i <= m; ++i) {
+ curr_row[0] = static_cast<int32_t>(i);
+ for (size_t j = 1; j <= n; ++j) {
+ if (s[i - 1] == t[j - 1]) {
+ curr_row[j] = prev_row[j - 1];
+ } else {
+ curr_row[j] = 1 + std::min({prev_row[j - 1], prev_row[j], curr_row[j - 1]});
+ }
+ }
+ std::swap(prev_row, curr_row);
+ }
+ res = prev_row[n];
+ }
+};
+
+struct NameDamerauLevenshtein {
+ static constexpr auto name = "damerau_levenshtein";
+};
+
+struct DamerauLevenshteinOp {
+ using ResultDataType = DataTypeInt32;
+ using ResultPaddedPODArray = PaddedPODArray<Int32>;
+
+ static void execute(const std::string_view& s, const std::string_view& t, int32_t& res) {
+ const size_t m = s.size(), n = t.size();
+ if (m == 0) {
+ res = static_cast<int32_t>(n);
+ return;
+ }
+ if (n == 0) {
+ res = static_cast<int32_t>(m);
+ return;
+ }
+ // Guard against OOM: the DP matrix allocates (m+2)*(n+2)*sizeof(int32_t) bytes.
+ // At 10000 chars each that is ~400 MB; cap well below VARCHAR max (65535).
+ constexpr size_t MAX_INPUT_LEN = 10000;
+ if (m > MAX_INPUT_LEN || n > MAX_INPUT_LEN) {
+ throw doris::Exception(ErrorCode::INVALID_ARGUMENT,
+ "Input string too long for damerau_levenshtein, max {} bytes",
+ MAX_INPUT_LEN);
+ }
+ const size_t stride = n + 2;
+ const int32_t max_dist = static_cast<int32_t>(m + n);
+ std::vector<int32_t> d((m + 2) * stride, 0);
+ d[0] = max_dist;
+ for (size_t i = 0; i <= m; ++i) {
+ d[(i + 1) * stride + 0] = max_dist;
+ d[(i + 1) * stride + 1] = static_cast<int32_t>(i);
+ }
+ for (size_t j = 0; j <= n; ++j) {
+ d[0 * stride + (j + 1)] = max_dist;
+ d[1 * stride + (j + 1)] = static_cast<int32_t>(j);
+ }
+ int32_t da[256] = {};
+ for (size_t i = 1; i <= m; ++i) {
+ int32_t db = 0;
+ for (size_t j = 1; j <= n; ++j) {
+ const int32_t k = da[(uint8_t)t[j - 1]];
+ const int32_t l = db;
+ int32_t cost;
+ if (s[i - 1] == t[j - 1]) {
+ cost = 0;
+ db = static_cast<int32_t>(j);
+ } else {
+ cost = 1;
+ }
+ const int32_t trans = d[static_cast<size_t>(k) * stride + static_cast<size_t>(l)] +
+ (static_cast<int32_t>(i) - k - 1) + 1 +
+ (static_cast<int32_t>(j) - l - 1);
+ d[(i + 1) * stride + (j + 1)] =
+ std::min({d[i * stride + j] + cost, d[(i + 1) * stride + j] + 1,
+ d[i * stride + (j + 1)] + 1, trans});
+ }
+ da[(uint8_t)s[i - 1]] = static_cast<int32_t>(i);
+ }
+ res = d[(m + 1) * stride + (n + 1)];
+ }
+};
+
+struct NameJaroWinkler {
+ static constexpr auto name = "jaro_winkler";
+};
+
+struct JaroWinklerOp {
+ using ResultDataType = DataTypeFloat64;
+ using ResultPaddedPODArray = PaddedPODArray<Float64>;
+
+ static void execute(const std::string_view& s, const std::string_view& t, double& res) {
+ if (s == t) {
+ res = 1.0;
+ return;
+ }
+ const size_t m = s.size(), n = t.size();
+ if (m == 0 || n == 0) {
+ res = 0.0;
+ return;
+ }
+ const size_t match_dist = std::max(m, n) / 2 - (std::max(m, n) >= 2 ? 1 : 0);
Review Comment:
**[HIGH] Missing input length guard.** `JaroWinklerOp` has O(m * match_dist) = O(m * n/2) time complexity in its matching loop (lines 453-462 in the source), but unlike `LevenshteinOp` (capped at 65535 bytes) and `DamerauLevenshteinOp` (capped at 10000 bytes), there is no length guard here.
Since the function accepts `STRING` type (up to ~2GB), a malicious or accidental query like `SELECT jaro_winkler(repeat('x', 100000), repeat('y', 100000))` would perform ~5 billion iterations per row. Additionally, the heap allocation at the else-branch (`s_heap.assign(m, 0)`) could allocate gigabytes of memory without MemTracker awareness.
Suggested fix — add a guard after computing `m` and `n`, consistent with the other functions:
```cpp
constexpr size_t MAX_INPUT_LEN = 65535;
if (m > MAX_INPUT_LEN || n > MAX_INPUT_LEN) {
throw doris::Exception(ErrorCode::INVALID_ARGUMENT,
"Input string too long for jaro_winkler, max {} bytes",
MAX_INPUT_LEN);
}
```
##########
be/src/vec/functions/function_string.cpp:
##########
@@ -290,6 +290,261 @@ struct FindInSetOp {
}
};
+struct NameLevenshtein {
+ static constexpr auto name = "levenshtein";
+};
+
+struct LevenshteinOp {
+ using ResultDataType = DataTypeInt32;
+ using ResultPaddedPODArray = PaddedPODArray<Int32>;
+
+ static void execute(const std::string_view& s, const std::string_view& t, int32_t& res) {
+ const size_t m = s.size();
+ const size_t n = t.size();
+ if (m == 0) {
+ res = static_cast<int32_t>(n);
+ return;
+ }
+ if (n == 0) {
+ res = static_cast<int32_t>(m);
+ return;
+ }
+ if (s == t) {
+ res = 0;
+ return;
+ }
+ // Guard against excessive O(m*n) computation on very large inputs.
+ // Limit each string to 65535 bytes (max VARCHAR length).
+ constexpr size_t MAX_INPUT_LEN = 65535;
+ if (m > MAX_INPUT_LEN || n > MAX_INPUT_LEN) {
+ throw doris::Exception(ErrorCode::INVALID_ARGUMENT,
+ "Input string too long for levenshtein, max {} bytes",
+ MAX_INPUT_LEN);
+ }
+ constexpr size_t STACK_MAX = 512;
+ int32_t prev_stk[STACK_MAX + 1], curr_stk[STACK_MAX + 1];
+ std::vector<int32_t> prev_heap, curr_heap;
+ int32_t* prev_row;
+ int32_t* curr_row;
+ if (n <= STACK_MAX) {
+ prev_row = prev_stk;
+ curr_row = curr_stk;
+ } else {
+ prev_heap.resize(n + 1);
+ curr_heap.resize(n + 1);
+ prev_row = prev_heap.data();
+ curr_row = curr_heap.data();
+ }
+ for (size_t j = 0; j <= n; ++j) prev_row[j] = static_cast<int32_t>(j);
+ for (size_t i = 1; i <= m; ++i) {
+ curr_row[0] = static_cast<int32_t>(i);
+ for (size_t j = 1; j <= n; ++j) {
+ if (s[i - 1] == t[j - 1]) {
+ curr_row[j] = prev_row[j - 1];
+ } else {
+ curr_row[j] = 1 + std::min({prev_row[j - 1], prev_row[j], curr_row[j - 1]});
+ }
+ }
+ std::swap(prev_row, curr_row);
+ }
+ res = prev_row[n];
+ }
+};
+
+struct NameDamerauLevenshtein {
+ static constexpr auto name = "damerau_levenshtein";
+};
+
+struct DamerauLevenshteinOp {
+ using ResultDataType = DataTypeInt32;
+ using ResultPaddedPODArray = PaddedPODArray<Int32>;
+
+ static void execute(const std::string_view& s, const std::string_view& t, int32_t& res) {
+ const size_t m = s.size(), n = t.size();
+ if (m == 0) {
+ res = static_cast<int32_t>(n);
+ return;
+ }
+ if (n == 0) {
+ res = static_cast<int32_t>(m);
+ return;
+ }
+ // Guard against OOM: the DP matrix allocates (m+2)*(n+2)*sizeof(int32_t) bytes.
+ // At 10000 chars each that is ~400 MB; cap well below VARCHAR max (65535).
+ constexpr size_t MAX_INPUT_LEN = 10000;
+ if (m > MAX_INPUT_LEN || n > MAX_INPUT_LEN) {
+ throw doris::Exception(ErrorCode::INVALID_ARGUMENT,
+ "Input string too long for damerau_levenshtein, max {} bytes",
+ MAX_INPUT_LEN);
+ }
+ const size_t stride = n + 2;
+ const int32_t max_dist = static_cast<int32_t>(m + n);
+ std::vector<int32_t> d((m + 2) * stride, 0);
+ d[0] = max_dist;
+ for (size_t i = 0; i <= m; ++i) {
+ d[(i + 1) * stride + 0] = max_dist;
+ d[(i + 1) * stride + 1] = static_cast<int32_t>(i);
+ }
+ for (size_t j = 0; j <= n; ++j) {
+ d[0 * stride + (j + 1)] = max_dist;
+ d[1 * stride + (j + 1)] = static_cast<int32_t>(j);
+ }
+ int32_t da[256] = {};
+ for (size_t i = 1; i <= m; ++i) {
+ int32_t db = 0;
+ for (size_t j = 1; j <= n; ++j) {
+ const int32_t k = da[(uint8_t)t[j - 1]];
+ const int32_t l = db;
+ int32_t cost;
+ if (s[i - 1] == t[j - 1]) {
+ cost = 0;
+ db = static_cast<int32_t>(j);
+ } else {
+ cost = 1;
+ }
+ const int32_t trans = d[static_cast<size_t>(k) * stride + static_cast<size_t>(l)] +
+ (static_cast<int32_t>(i) - k - 1) + 1 +
+ (static_cast<int32_t>(j) - l - 1);
+ d[(i + 1) * stride + (j + 1)] =
+ std::min({d[i * stride + j] + cost, d[(i + 1) * stride + j] + 1,
+ d[i * stride + (j + 1)] + 1, trans});
+ }
+ da[(uint8_t)s[i - 1]] = static_cast<int32_t>(i);
+ }
+ res = d[(m + 1) * stride + (n + 1)];
+ }
+};
+
+struct NameJaroWinkler {
+ static constexpr auto name = "jaro_winkler";
+};
+
+struct JaroWinklerOp {
+ using ResultDataType = DataTypeFloat64;
+ using ResultPaddedPODArray = PaddedPODArray<Float64>;
+
+ static void execute(const std::string_view& s, const std::string_view& t, double& res) {
+ if (s == t) {
+ res = 1.0;
+ return;
+ }
+ const size_t m = s.size(), n = t.size();
+ if (m == 0 || n == 0) {
+ res = 0.0;
+ return;
+ }
+ const size_t match_dist = std::max(m, n) / 2 - (std::max(m, n) >= 2 ? 1 : 0);
+ constexpr size_t STACK_MAX = 512;
+ uint8_t s_stk[STACK_MAX] = {};
+ uint8_t t_stk[STACK_MAX] = {};
+ std::vector<uint8_t> s_heap, t_heap;
+ uint8_t* sm;
+ uint8_t* tm;
+ if (m <= STACK_MAX && n <= STACK_MAX) {
+ sm = s_stk;
+ tm = t_stk;
+ } else {
+ s_heap.assign(m, 0);
+ t_heap.assign(n, 0);
+ sm = s_heap.data();
+ tm = t_heap.data();
+ }
+ double matches = 0;
+ for (size_t i = 0; i < m; ++i) {
+ const size_t start = (i >= match_dist) ? i - match_dist : 0;
+ const size_t end = std::min(i + match_dist + 1, n);
+ for (size_t j = start; j < end; ++j) {
+ if (!tm[j] && s[i] == t[j]) {
+ sm[i] = tm[j] = 1;
+ ++matches;
+ break;
+ }
+ }
+ }
+ if (matches == 0.0) {
+ res = 0.0;
+ return;
+ }
+ double transpositions = 0;
+ size_t k = 0;
+ for (size_t i = 0; i < m; ++i) {
+ if (sm[i]) {
+ while (!tm[k]) ++k;
+ if (s[i] != t[k]) ++transpositions;
+ ++k;
+ }
+ }
+ const double jaro = (matches / static_cast<double>(m) + matches / static_cast<double>(n) +
+ (matches - transpositions / 2.0) / matches) /
+ 3.0;
+ size_t prefix = 0;
+ const size_t max_prefix = std::min(static_cast<size_t>(4), std::min(m, n));
+ while (prefix < max_prefix && s[prefix] == t[prefix]) ++prefix;
+ res = jaro + static_cast<double>(prefix) * 0.1 * (1.0 - jaro);
+ }
+};
+
+struct NameJaccardSimilarity {
+ static constexpr auto name = "jaccard_similarity";
+};
+
+struct JaccardSimilarityOp {
+ using ResultDataType = DataTypeFloat64;
+ using ResultPaddedPODArray = PaddedPODArray<Float64>;
+
+ static void execute(const std::string_view& s, const std::string_view& t, double& res) {
+ if (s == t) {
+ res = 1.0;
+ return;
+ }
+ if (s.size() < 2 || t.size() < 2) {
+ res = 0.0;
+ return;
+ }
+ const size_t m = s.size(), n = t.size();
Review Comment:
**[MEDIUM] Missing input length guard.** `JaccardSimilarityOp` has no input length validation. While its core algorithm is O(m log m + n log n) (less critical than Jaro-Winkler's quadratic), the heap path at line 539 (`std::vector<uint16_t>(m - 1)`) allocates `2 * (m-1)` bytes untracked by MemTracker. For a STRING-type input near the ~2GB limit, this could attempt a ~4GB heap allocation.
For consistency with the other functions and to prevent OOM, consider adding a length guard:
```cpp
constexpr size_t MAX_INPUT_LEN = 65535;
if (m > MAX_INPUT_LEN || n > MAX_INPUT_LEN) {
throw doris::Exception(ErrorCode::INVALID_ARGUMENT,
"Input string too long for jaccard_similarity, max {} bytes",
MAX_INPUT_LEN);
}
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](func) Add levenshtein, damerau_levenshtein, jaro_winkler, jaccard_similarity built-in scalar functions [doris]
Posted by "puranjay2597 (via GitHub)" <gi...@apache.org>.
puranjay2597 commented on PR #60799:
URL: https://github.com/apache/doris/pull/60799#issuecomment-3957298768
@zclllyybb - I force-pushed to address FE UT checkstyle failure and Copilot AI review comments
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](func) Add levenshtein, damerau_levenshtein, jaro_winkler, jaccard_similarity built-in scalar functions [doris]
Posted by "linrrzqqq (via GitHub)" <gi...@apache.org>.
linrrzqqq commented on code in PR #60799:
URL: https://github.com/apache/doris/pull/60799#discussion_r2899036742
##########
be/src/vec/functions/function_string.cpp:
##########
@@ -290,6 +290,275 @@ struct FindInSetOp {
}
};
+struct NameLevenshtein {
+ static constexpr auto name = "levenshtein";
+};
+
+struct LevenshteinOp {
+ using ResultDataType = DataTypeInt32;
+ using ResultPaddedPODArray = PaddedPODArray<Int32>;
+
+ static void execute(const std::string_view& s, const std::string_view& t, int32_t& res) {
+ const size_t m = s.size();
+ const size_t n = t.size();
+ if (m == 0) {
+ res = static_cast<int32_t>(n);
+ return;
+ }
+ if (n == 0) {
+ res = static_cast<int32_t>(m);
+ return;
+ }
+ if (s == t) {
+ res = 0;
+ return;
+ }
+ // Guard against excessive O(m*n) computation on very large inputs.
+ // Limit each string to 65535 bytes (max VARCHAR length).
+ constexpr size_t MAX_INPUT_LEN = 65535;
+ if (m > MAX_INPUT_LEN || n > MAX_INPUT_LEN) {
+ throw doris::Exception(ErrorCode::INVALID_ARGUMENT,
+ "Input string too long for levenshtein, max {} bytes",
+ MAX_INPUT_LEN);
+ }
+ constexpr size_t STACK_MAX = 512;
+ int32_t prev_stk[STACK_MAX + 1], curr_stk[STACK_MAX + 1];
+ std::vector<int32_t> prev_heap, curr_heap;
+ int32_t* prev_row;
+ int32_t* curr_row;
+ if (n <= STACK_MAX) {
+ prev_row = prev_stk;
+ curr_row = curr_stk;
+ } else {
+ prev_heap.resize(n + 1);
+ curr_heap.resize(n + 1);
+ prev_row = prev_heap.data();
+ curr_row = curr_heap.data();
+ }
+ for (size_t j = 0; j <= n; ++j) prev_row[j] = static_cast<int32_t>(j);
+ for (size_t i = 1; i <= m; ++i) {
+ curr_row[0] = static_cast<int32_t>(i);
+ for (size_t j = 1; j <= n; ++j) {
+ if (s[i - 1] == t[j - 1]) {
+ curr_row[j] = prev_row[j - 1];
+ } else {
+ curr_row[j] = 1 + std::min({prev_row[j - 1], prev_row[j], curr_row[j - 1]});
+ }
+ }
+ std::swap(prev_row, curr_row);
+ }
+ res = prev_row[n];
+ }
+};
+
+struct NameDamerauLevenshtein {
+ static constexpr auto name = "damerau_levenshtein";
+};
+
+struct DamerauLevenshteinOp {
+ using ResultDataType = DataTypeInt32;
+ using ResultPaddedPODArray = PaddedPODArray<Int32>;
+
+ static void execute(const std::string_view& s, const std::string_view& t, int32_t& res) {
+ const size_t m = s.size(), n = t.size();
+ if (m == 0) {
+ res = static_cast<int32_t>(n);
+ return;
+ }
+ if (n == 0) {
+ res = static_cast<int32_t>(m);
+ return;
+ }
+ // Guard against OOM: the DP matrix allocates (m+2)*(n+2)*sizeof(int32_t) bytes.
+ // At 10000 chars each that is ~400 MB; cap well below VARCHAR max (65535).
+ constexpr size_t MAX_INPUT_LEN = 10000;
+ if (m > MAX_INPUT_LEN || n > MAX_INPUT_LEN) {
+ throw doris::Exception(ErrorCode::INVALID_ARGUMENT,
+ "Input string too long for damerau_levenshtein, max {} bytes",
+ MAX_INPUT_LEN);
+ }
+ const size_t stride = n + 2;
+ const int32_t max_dist = static_cast<int32_t>(m + n);
+ std::vector<int32_t> d((m + 2) * stride, 0);
+ d[0] = max_dist;
+ for (size_t i = 0; i <= m; ++i) {
+ d[(i + 1) * stride + 0] = max_dist;
+ d[(i + 1) * stride + 1] = static_cast<int32_t>(i);
+ }
+ for (size_t j = 0; j <= n; ++j) {
+ d[0 * stride + (j + 1)] = max_dist;
+ d[1 * stride + (j + 1)] = static_cast<int32_t>(j);
+ }
+ int32_t da[256] = {};
+ for (size_t i = 1; i <= m; ++i) {
+ int32_t db = 0;
+ for (size_t j = 1; j <= n; ++j) {
+ const int32_t k = da[(uint8_t)t[j - 1]];
+ const int32_t l = db;
+ int32_t cost;
+ if (s[i - 1] == t[j - 1]) {
+ cost = 0;
+ db = static_cast<int32_t>(j);
+ } else {
+ cost = 1;
+ }
+ const int32_t trans = d[static_cast<size_t>(k) * stride + static_cast<size_t>(l)] +
+ (static_cast<int32_t>(i) - k - 1) + 1 +
+ (static_cast<int32_t>(j) - l - 1);
+ d[(i + 1) * stride + (j + 1)] =
+ std::min({d[i * stride + j] + cost, d[(i + 1) * stride + j] + 1,
+ d[i * stride + (j + 1)] + 1, trans});
+ }
+ da[(uint8_t)s[i - 1]] = static_cast<int32_t>(i);
+ }
+ res = d[(m + 1) * stride + (n + 1)];
+ }
+};
+
+struct NameJaroWinkler {
+ static constexpr auto name = "jaro_winkler";
+};
+
+struct JaroWinklerOp {
+ using ResultDataType = DataTypeFloat64;
+ using ResultPaddedPODArray = PaddedPODArray<Float64>;
+
+ static void execute(const std::string_view& s, const std::string_view& t, double& res) {
+ if (s == t) {
+ res = 1.0;
+ return;
+ }
+ const size_t m = s.size(), n = t.size();
+ if (m == 0 || n == 0) {
+ res = 0.0;
+ return;
+ }
+ // Guard against O(m*n/2) matching loop and heap allocation of m+n bytes.
+ constexpr size_t MAX_INPUT_LEN = 65535;
+ if (m > MAX_INPUT_LEN || n > MAX_INPUT_LEN) {
+ throw doris::Exception(ErrorCode::INVALID_ARGUMENT,
+ "Input string too long for jaro_winkler, max {} bytes",
+ MAX_INPUT_LEN);
+ }
+ const size_t match_dist = std::max(m, n) / 2 - (std::max(m, n) >= 2 ? 1 : 0);
+ constexpr size_t STACK_MAX = 512;
+ uint8_t s_stk[STACK_MAX] = {};
+ uint8_t t_stk[STACK_MAX] = {};
+ std::vector<uint8_t> s_heap, t_heap;
+ uint8_t* sm;
+ uint8_t* tm;
+ if (m <= STACK_MAX && n <= STACK_MAX) {
+ sm = s_stk;
+ tm = t_stk;
+ } else {
+ s_heap.assign(m, 0);
+ t_heap.assign(n, 0);
+ sm = s_heap.data();
+ tm = t_heap.data();
+ }
+ double matches = 0;
+ for (size_t i = 0; i < m; ++i) {
+ const size_t start = (i >= match_dist) ? i - match_dist : 0;
+ const size_t end = std::min(i + match_dist + 1, n);
+ for (size_t j = start; j < end; ++j) {
+ if (!tm[j] && s[i] == t[j]) {
+ sm[i] = tm[j] = 1;
+ ++matches;
+ break;
+ }
+ }
+ }
+ if (matches == 0.0) {
+ res = 0.0;
+ return;
+ }
+ double transpositions = 0;
+ size_t k = 0;
+ for (size_t i = 0; i < m; ++i) {
+ if (sm[i]) {
+ while (!tm[k]) ++k;
+ if (s[i] != t[k]) ++transpositions;
+ ++k;
+ }
+ }
+ const double jaro = (matches / static_cast<double>(m) + matches / static_cast<double>(n) +
+ (matches - transpositions / 2.0) / matches) /
+ 3.0;
+ size_t prefix = 0;
+ const size_t max_prefix = std::min(static_cast<size_t>(4), std::min(m, n));
+ while (prefix < max_prefix && s[prefix] == t[prefix]) ++prefix;
+ res = jaro + static_cast<double>(prefix) * 0.1 * (1.0 - jaro);
+ }
+};
+
+struct NameJaccardSimilarity {
+ static constexpr auto name = "jaccard_similarity";
+};
+
+struct JaccardSimilarityOp {
+ using ResultDataType = DataTypeFloat64;
+ using ResultPaddedPODArray = PaddedPODArray<Float64>;
+
+ static void execute(const std::string_view& s, const std::string_view& t, double& res) {
+ if (s == t) {
+ res = 1.0;
+ return;
+ }
+ if (s.size() < 2 || t.size() < 2) {
+ res = 0.0;
+ return;
+ }
+ const size_t m = s.size(), n = t.size();
+ // Guard against heap allocation of 2*(m+n) bytes for very large STRING inputs.
+ constexpr size_t MAX_INPUT_LEN = 65535;
+ if (m > MAX_INPUT_LEN || n > MAX_INPUT_LEN) {
+ throw doris::Exception(ErrorCode::INVALID_ARGUMENT,
+ "Input string too long for jaccard_similarity, max {} bytes",
+ MAX_INPUT_LEN);
+ }
+
+ auto collect = [](const std::string_view& str, uint16_t* out) -> size_t {
Review Comment:
why collect? I haven't seen this operation in [wiki](https://en.wikipedia.org/wiki/Jaccard_index) and [ck](https://github.com/ClickHouse/ClickHouse/blob/master/src/Functions/FunctionsStringDistance.cpp#L148). Can you provide the basis of your algorithm for me to refer?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](func) Add levenshtein, damerau_levenshtein, jaro_winkler, jaccard_similarity built-in scalar functions [doris]
Posted by "linrrzqqq (via GitHub)" <gi...@apache.org>.
linrrzqqq commented on code in PR #60799:
URL: https://github.com/apache/doris/pull/60799#discussion_r2899047115
##########
be/src/vec/functions/function_string.cpp:
##########
@@ -290,6 +290,275 @@ struct FindInSetOp {
}
};
+struct NameLevenshtein {
+ static constexpr auto name = "levenshtein";
+};
+
+struct LevenshteinOp {
+ using ResultDataType = DataTypeInt32;
+ using ResultPaddedPODArray = PaddedPODArray<Int32>;
+
+ static void execute(const std::string_view& s, const std::string_view& t, int32_t& res) {
+ const size_t m = s.size();
+ const size_t n = t.size();
+ if (m == 0) {
+ res = static_cast<int32_t>(n);
+ return;
+ }
+ if (n == 0) {
+ res = static_cast<int32_t>(m);
+ return;
+ }
+ if (s == t) {
+ res = 0;
+ return;
+ }
+ // Guard against excessive O(m*n) computation on very large inputs.
+ // Limit each string to 65535 bytes (max VARCHAR length).
+ constexpr size_t MAX_INPUT_LEN = 65535;
+ if (m > MAX_INPUT_LEN || n > MAX_INPUT_LEN) {
+ throw doris::Exception(ErrorCode::INVALID_ARGUMENT,
+ "Input string too long for levenshtein, max {} bytes",
+ MAX_INPUT_LEN);
+ }
+ constexpr size_t STACK_MAX = 512;
+ int32_t prev_stk[STACK_MAX + 1], curr_stk[STACK_MAX + 1];
+ std::vector<int32_t> prev_heap, curr_heap;
+ int32_t* prev_row;
+ int32_t* curr_row;
+ if (n <= STACK_MAX) {
+ prev_row = prev_stk;
+ curr_row = curr_stk;
+ } else {
+ prev_heap.resize(n + 1);
+ curr_heap.resize(n + 1);
+ prev_row = prev_heap.data();
+ curr_row = curr_heap.data();
+ }
+ for (size_t j = 0; j <= n; ++j) prev_row[j] = static_cast<int32_t>(j);
+ for (size_t i = 1; i <= m; ++i) {
+ curr_row[0] = static_cast<int32_t>(i);
+ for (size_t j = 1; j <= n; ++j) {
+ if (s[i - 1] == t[j - 1]) {
+ curr_row[j] = prev_row[j - 1];
+ } else {
+ curr_row[j] = 1 + std::min({prev_row[j - 1], prev_row[j], curr_row[j - 1]});
+ }
+ }
+ std::swap(prev_row, curr_row);
+ }
+ res = prev_row[n];
+ }
+};
+
+struct NameDamerauLevenshtein {
+ static constexpr auto name = "damerau_levenshtein";
+};
+
+struct DamerauLevenshteinOp {
+ using ResultDataType = DataTypeInt32;
+ using ResultPaddedPODArray = PaddedPODArray<Int32>;
+
+ static void execute(const std::string_view& s, const std::string_view& t, int32_t& res) {
+ const size_t m = s.size(), n = t.size();
+ if (m == 0) {
+ res = static_cast<int32_t>(n);
+ return;
+ }
+ if (n == 0) {
+ res = static_cast<int32_t>(m);
+ return;
+ }
+ // Guard against OOM: the DP matrix allocates (m+2)*(n+2)*sizeof(int32_t) bytes.
+ // At 10000 chars each that is ~400 MB; cap well below VARCHAR max (65535).
+ constexpr size_t MAX_INPUT_LEN = 10000;
+ if (m > MAX_INPUT_LEN || n > MAX_INPUT_LEN) {
+ throw doris::Exception(ErrorCode::INVALID_ARGUMENT,
+ "Input string too long for damerau_levenshtein, max {} bytes",
+ MAX_INPUT_LEN);
+ }
+ const size_t stride = n + 2;
+ const int32_t max_dist = static_cast<int32_t>(m + n);
+ std::vector<int32_t> d((m + 2) * stride, 0);
+ d[0] = max_dist;
+ for (size_t i = 0; i <= m; ++i) {
+ d[(i + 1) * stride + 0] = max_dist;
+ d[(i + 1) * stride + 1] = static_cast<int32_t>(i);
+ }
+ for (size_t j = 0; j <= n; ++j) {
+ d[0 * stride + (j + 1)] = max_dist;
+ d[1 * stride + (j + 1)] = static_cast<int32_t>(j);
+ }
+ int32_t da[256] = {};
+ for (size_t i = 1; i <= m; ++i) {
+ int32_t db = 0;
+ for (size_t j = 1; j <= n; ++j) {
+ const int32_t k = da[(uint8_t)t[j - 1]];
+ const int32_t l = db;
+ int32_t cost;
+ if (s[i - 1] == t[j - 1]) {
+ cost = 0;
+ db = static_cast<int32_t>(j);
+ } else {
+ cost = 1;
+ }
+ const int32_t trans = d[static_cast<size_t>(k) * stride + static_cast<size_t>(l)] +
+ (static_cast<int32_t>(i) - k - 1) + 1 +
+ (static_cast<int32_t>(j) - l - 1);
+ d[(i + 1) * stride + (j + 1)] =
+ std::min({d[i * stride + j] + cost, d[(i + 1) * stride + j] + 1,
+ d[i * stride + (j + 1)] + 1, trans});
+ }
+ da[(uint8_t)s[i - 1]] = static_cast<int32_t>(i);
+ }
+ res = d[(m + 1) * stride + (n + 1)];
+ }
+};
+
+struct NameJaroWinkler {
+ static constexpr auto name = "jaro_winkler";
+};
+
+struct JaroWinklerOp {
+ using ResultDataType = DataTypeFloat64;
+ using ResultPaddedPODArray = PaddedPODArray<Float64>;
+
+ static void execute(const std::string_view& s, const std::string_view& t, double& res) {
+ if (s == t) {
+ res = 1.0;
+ return;
+ }
+ const size_t m = s.size(), n = t.size();
+ if (m == 0 || n == 0) {
+ res = 0.0;
+ return;
+ }
+ // Guard against O(m*n/2) matching loop and heap allocation of m+n bytes.
+ constexpr size_t MAX_INPUT_LEN = 65535;
+ if (m > MAX_INPUT_LEN || n > MAX_INPUT_LEN) {
+ throw doris::Exception(ErrorCode::INVALID_ARGUMENT,
+ "Input string too long for jaro_winkler, max {} bytes",
+ MAX_INPUT_LEN);
+ }
+ const size_t match_dist = std::max(m, n) / 2 - (std::max(m, n) >= 2 ? 1 : 0);
+ constexpr size_t STACK_MAX = 512;
+ uint8_t s_stk[STACK_MAX] = {};
+ uint8_t t_stk[STACK_MAX] = {};
+ std::vector<uint8_t> s_heap, t_heap;
+ uint8_t* sm;
+ uint8_t* tm;
+ if (m <= STACK_MAX && n <= STACK_MAX) {
+ sm = s_stk;
+ tm = t_stk;
+ } else {
+ s_heap.assign(m, 0);
+ t_heap.assign(n, 0);
+ sm = s_heap.data();
+ tm = t_heap.data();
+ }
+ double matches = 0;
+ for (size_t i = 0; i < m; ++i) {
+ const size_t start = (i >= match_dist) ? i - match_dist : 0;
+ const size_t end = std::min(i + match_dist + 1, n);
+ for (size_t j = start; j < end; ++j) {
+ if (!tm[j] && s[i] == t[j]) {
+ sm[i] = tm[j] = 1;
+ ++matches;
+ break;
+ }
+ }
+ }
+ if (matches == 0.0) {
+ res = 0.0;
+ return;
+ }
+ double transpositions = 0;
+ size_t k = 0;
+ for (size_t i = 0; i < m; ++i) {
+ if (sm[i]) {
+ while (!tm[k]) ++k;
+ if (s[i] != t[k]) ++transpositions;
+ ++k;
+ }
+ }
+ const double jaro = (matches / static_cast<double>(m) + matches / static_cast<double>(n) +
+ (matches - transpositions / 2.0) / matches) /
+ 3.0;
+ size_t prefix = 0;
+ const size_t max_prefix = std::min(static_cast<size_t>(4), std::min(m, n));
+ while (prefix < max_prefix && s[prefix] == t[prefix]) ++prefix;
+ res = jaro + static_cast<double>(prefix) * 0.1 * (1.0 - jaro);
+ }
+};
+
+struct NameJaccardSimilarity {
+ static constexpr auto name = "jaccard_similarity";
+};
+
+struct JaccardSimilarityOp {
+ using ResultDataType = DataTypeFloat64;
+ using ResultPaddedPODArray = PaddedPODArray<Float64>;
+
+ static void execute(const std::string_view& s, const std::string_view& t, double& res) {
+ if (s == t) {
+ res = 1.0;
+ return;
+ }
+ if (s.size() < 2 || t.size() < 2) {
+ res = 0.0;
+ return;
+ }
+ const size_t m = s.size(), n = t.size();
+ // Guard against heap allocation of 2*(m+n) bytes for very large STRING inputs.
+ constexpr size_t MAX_INPUT_LEN = 65535;
+ if (m > MAX_INPUT_LEN || n > MAX_INPUT_LEN) {
+ throw doris::Exception(ErrorCode::INVALID_ARGUMENT,
+ "Input string too long for jaccard_similarity, max {} bytes",
+ MAX_INPUT_LEN);
+ }
+
+ auto collect = [](const std::string_view& str, uint16_t* out) -> size_t {
+ size_t cnt = 0;
+ for (size_t i = 0; i + 1 < str.size(); ++i)
+ out[cnt++] = static_cast<uint16_t>((static_cast<uint16_t>((uint8_t)str[i]) << 8) |
+ (uint8_t)str[i + 1]);
+ std::sort(out, out + cnt);
+ return static_cast<size_t>(std::unique(out, out + cnt) - out);
+ };
+ auto merge_count = [](const uint16_t* a, size_t ac, const uint16_t* b, size_t bc,
+ int32_t& intersect, int32_t& union_sz) {
+ intersect = 0;
+ size_t i = 0, j = 0;
+ while (i < ac && j < bc) {
+ if (a[i] == b[j]) {
+ ++intersect;
+ ++i;
+ ++j;
+ } else if (a[i] < b[j])
+ ++i;
+ else
+ ++j;
+ }
+ union_sz = static_cast<int32_t>(ac) + static_cast<int32_t>(bc) - intersect;
+ };
+ constexpr size_t STACK_MAX_LEN = 1001;
+ constexpr size_t STACK_MAX_BG = 1000;
+ int32_t intersect = 0, union_sz = 0;
+ if (m <= STACK_MAX_LEN && n <= STACK_MAX_LEN) {
+ uint16_t s_bg[STACK_MAX_BG], t_bg[STACK_MAX_BG];
+ const size_t sc = collect(s, s_bg);
+ const size_t tc = collect(t, t_bg);
+ merge_count(s_bg, sc, t_bg, tc, intersect, union_sz);
+ } else {
+ std::vector<uint16_t> s_bg(m - 1), t_bg(n - 1);
+ const size_t sc = collect(s, s_bg.data());
+ const size_t tc = collect(t, t_bg.data());
+ merge_count(s_bg.data(), sc, t_bg.data(), tc, intersect, union_sz);
+ }
+ res = (union_sz > 0) ? static_cast<double>(intersect) / union_sz : 1.0;
Review Comment:
```suggestion
res = static_cast<double>(intersect) / union_sz;
```
already check `s.size() < 2 || t.size() < 2` above
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](func) Add levenshtein, damerau_levenshtein, jaro_winkler, jaccard_similarity built-in scalar functions [doris]
Posted by "doris-robot (via GitHub)" <gi...@apache.org>.
doris-robot commented on PR #60799:
URL: https://github.com/apache/doris/pull/60799#issuecomment-3959992255
<details>
<summary>TPC-DS: <b>Total hot run time: 183534 ms</b></summary>
```
machine: 'aliyun_ecs.c7a.8xlarge_32C64G'
scripts: https://github.com/apache/doris/tree/master/tools/tpcds-tools
TPC-DS sf100 test result on commit 0c3b86a6851ef55a2713bd99a18f326bc9d6c677, data reload: false
query5 4882 625 526 526
query6 343 235 212 212
query7 4247 474 269 269
query8 347 251 237 237
query9 8789 2677 2703 2677
query10 535 391 342 342
query11 17025 17518 17100 17100
query12 216 137 126 126
query13 1327 481 381 381
query14 6895 3289 3024 3024
query14_1 3067 2892 2953 2892
query15 216 226 186 186
query16 4231 473 447 447
query17 1194 736 605 605
query18 2880 457 376 376
query19 222 211 192 192
query20 163 137 130 130
query21 218 137 117 117
query22 5147 4817 4860 4817
query23 17175 16803 16743 16743
query23_1 16521 16687 16674 16674
query24 7029 1614 1220 1220
query24_1 1226 1237 1219 1219
query25 536 458 405 405
query26 1187 254 160 160
query27 2758 485 279 279
query28 4449 1829 1857 1829
query29 742 542 470 470
query30 320 252 210 210
query31 869 721 635 635
query32 75 73 66 66
query33 495 333 311 311
query34 914 906 560 560
query35 640 671 598 598
query36 1122 1147 974 974
query37 129 92 83 83
query38 2917 2941 2914 2914
query39 890 867 848 848
query39_1 827 838 833 833
query40 230 140 136 136
query41 64 59 58 58
query42 102 100 98 98
query43 361 391 347 347
query44
query45 194 189 183 183
query46 879 976 612 612
query47 2148 2123 2060 2060
query48 308 311 226 226
query49 635 456 377 377
query50 682 267 208 208
query51 4165 4066 4032 4032
query52 105 105 96 96
query53 290 337 281 281
query54 281 259 255 255
query55 87 85 83 83
query56 312 297 321 297
query57 1376 1344 1297 1297
query58 287 274 264 264
query59 2530 2666 2556 2556
query60 348 325 314 314
query61 144 141 173 141
query62 625 570 507 507
query63 303 273 268 268
query64 4496 1252 968 968
query65
query66 1298 423 342 342
query67 16395 16415 16326 16326
query68
query69 392 308 278 278
query70 977 929 900 900
query71 339 299 301 299
query72 2833 2624 2394 2394
query73 545 542 320 320
query74 10044 9859 9796 9796
query75 2866 2735 2467 2467
query76 1883 1052 685 685
query77 375 386 318 318
query78 11149 11401 10704 10704
query79 1176 775 605 605
query80 795 666 554 554
query81 505 280 255 255
query82 1374 154 121 121
query83 337 263 251 251
query84 255 125 100 100
query85 1005 530 510 510
query86 380 325 291 291
query87 3138 3122 2961 2961
query88 3616 2681 2664 2664
query89 422 375 354 354
query90 1793 167 167 167
query91 164 156 129 129
query92 77 75 68 68
query93 915 813 500 500
query94 479 323 280 280
query95 582 397 312 312
query96 631 532 229 229
query97 2470 2476 2421 2421
query98 228 216 218 216
query99 1013 1002 929 929
Total cold run time: 255692 ms
Total hot run time: 183534 ms
```
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](func) Add levenshtein, damerau_levenshtein, jaro_winkler, cosine_similarity, jaccard_similarity built-in scalar functions [doris]
Posted by "Thearas (via GitHub)" <gi...@apache.org>.
Thearas commented on PR #60799:
URL: https://github.com/apache/doris/pull/60799#issuecomment-3948369800
Thank you for your contribution to Apache Doris.
Don't know what should be done next? See [How to process your PR](https://cwiki.apache.org/confluence/display/DORIS/How+to+process+your+PR).
Please clearly describe your PR:
1. What problem was fixed (it's best to include specific error reporting information). How it was fixed.
2. Which behaviors were modified. What was the previous behavior, what is it now, why was it modified, and what possible impacts might there be.
3. What features were added. Why was this function added?
4. Which code was refactored and why was this part of the code refactored?
5. Which functions were optimized and what is the difference before and after the optimization?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](func) Add levenshtein, damerau_levenshtein, jaro_winkler, jaccard_similarity built-in scalar functions [doris]
Posted by "hello-stephen (via GitHub)" <gi...@apache.org>.
hello-stephen commented on PR #60799:
URL: https://github.com/apache/doris/pull/60799#issuecomment-3991954315
# FE Regression Coverage Report
Increment line coverage ` 93.33% (56/60)` :tada:
[Increment coverage report](http://coverage.selectdb-in.cc/coverage/60799_54ddedd1a57e5d4232dc5735396482acc38d693d_merge_fe/increment_report/index.html)
[Complete coverage report](http://coverage.selectdb-in.cc/coverage/60799_54ddedd1a57e5d4232dc5735396482acc38d693d_merge_fe/report/index.html)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](func) Add levenshtein, damerau_levenshtein, jaro_winkler, jaccard_similarity built-in scalar functions [doris]
Posted by "linrrzqqq (via GitHub)" <gi...@apache.org>.
linrrzqqq commented on code in PR #60799:
URL: https://github.com/apache/doris/pull/60799#discussion_r2899069590
##########
be/src/vec/functions/function_string.cpp:
##########
@@ -290,6 +290,275 @@ struct FindInSetOp {
}
};
+struct NameLevenshtein {
+ static constexpr auto name = "levenshtein";
+};
+
+struct LevenshteinOp {
+ using ResultDataType = DataTypeInt32;
+ using ResultPaddedPODArray = PaddedPODArray<Int32>;
+
+ static void execute(const std::string_view& s, const std::string_view& t, int32_t& res) {
+ const size_t m = s.size();
+ const size_t n = t.size();
+ if (m == 0) {
+ res = static_cast<int32_t>(n);
+ return;
+ }
+ if (n == 0) {
+ res = static_cast<int32_t>(m);
+ return;
+ }
+ if (s == t) {
+ res = 0;
+ return;
+ }
+ // Guard against excessive O(m*n) computation on very large inputs.
+ // Limit each string to 65535 bytes (max VARCHAR length).
+ constexpr size_t MAX_INPUT_LEN = 65535;
+ if (m > MAX_INPUT_LEN || n > MAX_INPUT_LEN) {
+ throw doris::Exception(ErrorCode::INVALID_ARGUMENT,
+ "Input string too long for levenshtein, max {} bytes",
+ MAX_INPUT_LEN);
+ }
+ constexpr size_t STACK_MAX = 512;
+ int32_t prev_stk[STACK_MAX + 1], curr_stk[STACK_MAX + 1];
+ std::vector<int32_t> prev_heap, curr_heap;
+ int32_t* prev_row;
+ int32_t* curr_row;
+ if (n <= STACK_MAX) {
+ prev_row = prev_stk;
+ curr_row = curr_stk;
+ } else {
+ prev_heap.resize(n + 1);
+ curr_heap.resize(n + 1);
+ prev_row = prev_heap.data();
+ curr_row = curr_heap.data();
+ }
+ for (size_t j = 0; j <= n; ++j) prev_row[j] = static_cast<int32_t>(j);
+ for (size_t i = 1; i <= m; ++i) {
+ curr_row[0] = static_cast<int32_t>(i);
+ for (size_t j = 1; j <= n; ++j) {
+ if (s[i - 1] == t[j - 1]) {
+ curr_row[j] = prev_row[j - 1];
+ } else {
+ curr_row[j] = 1 + std::min({prev_row[j - 1], prev_row[j], curr_row[j - 1]});
+ }
+ }
+ std::swap(prev_row, curr_row);
+ }
+ res = prev_row[n];
+ }
+};
+
+struct NameDamerauLevenshtein {
+ static constexpr auto name = "damerau_levenshtein";
+};
+
+struct DamerauLevenshteinOp {
+ using ResultDataType = DataTypeInt32;
+ using ResultPaddedPODArray = PaddedPODArray<Int32>;
+
+ static void execute(const std::string_view& s, const std::string_view& t, int32_t& res) {
+ const size_t m = s.size(), n = t.size();
+ if (m == 0) {
+ res = static_cast<int32_t>(n);
+ return;
+ }
+ if (n == 0) {
+ res = static_cast<int32_t>(m);
+ return;
+ }
+ // Guard against OOM: the DP matrix allocates (m+2)*(n+2)*sizeof(int32_t) bytes.
+ // At 10000 chars each that is ~400 MB; cap well below VARCHAR max (65535).
+ constexpr size_t MAX_INPUT_LEN = 10000;
+ if (m > MAX_INPUT_LEN || n > MAX_INPUT_LEN) {
+ throw doris::Exception(ErrorCode::INVALID_ARGUMENT,
+ "Input string too long for damerau_levenshtein, max {} bytes",
+ MAX_INPUT_LEN);
+ }
+ const size_t stride = n + 2;
+ const int32_t max_dist = static_cast<int32_t>(m + n);
+ std::vector<int32_t> d((m + 2) * stride, 0);
+ d[0] = max_dist;
+ for (size_t i = 0; i <= m; ++i) {
+ d[(i + 1) * stride + 0] = max_dist;
+ d[(i + 1) * stride + 1] = static_cast<int32_t>(i);
+ }
+ for (size_t j = 0; j <= n; ++j) {
+ d[0 * stride + (j + 1)] = max_dist;
+ d[1 * stride + (j + 1)] = static_cast<int32_t>(j);
+ }
+ int32_t da[256] = {};
+ for (size_t i = 1; i <= m; ++i) {
+ int32_t db = 0;
+ for (size_t j = 1; j <= n; ++j) {
+ const int32_t k = da[(uint8_t)t[j - 1]];
+ const int32_t l = db;
+ int32_t cost;
+ if (s[i - 1] == t[j - 1]) {
+ cost = 0;
+ db = static_cast<int32_t>(j);
+ } else {
+ cost = 1;
+ }
+ const int32_t trans = d[static_cast<size_t>(k) * stride + static_cast<size_t>(l)] +
+ (static_cast<int32_t>(i) - k - 1) + 1 +
+ (static_cast<int32_t>(j) - l - 1);
+ d[(i + 1) * stride + (j + 1)] =
+ std::min({d[i * stride + j] + cost, d[(i + 1) * stride + j] + 1,
+ d[i * stride + (j + 1)] + 1, trans});
+ }
+ da[(uint8_t)s[i - 1]] = static_cast<int32_t>(i);
+ }
+ res = d[(m + 1) * stride + (n + 1)];
+ }
+};
+
+struct NameJaroWinkler {
+ static constexpr auto name = "jaro_winkler";
+};
+
+struct JaroWinklerOp {
+ using ResultDataType = DataTypeFloat64;
+ using ResultPaddedPODArray = PaddedPODArray<Float64>;
+
+ static void execute(const std::string_view& s, const std::string_view& t, double& res) {
+ if (s == t) {
+ res = 1.0;
+ return;
+ }
+ const size_t m = s.size(), n = t.size();
+ if (m == 0 || n == 0) {
+ res = 0.0;
+ return;
+ }
+ // Guard against O(m*n/2) matching loop and heap allocation of m+n bytes.
+ constexpr size_t MAX_INPUT_LEN = 65535;
+ if (m > MAX_INPUT_LEN || n > MAX_INPUT_LEN) {
+ throw doris::Exception(ErrorCode::INVALID_ARGUMENT,
+ "Input string too long for jaro_winkler, max {} bytes",
+ MAX_INPUT_LEN);
+ }
+ const size_t match_dist = std::max(m, n) / 2 - (std::max(m, n) >= 2 ? 1 : 0);
+ constexpr size_t STACK_MAX = 512;
+ uint8_t s_stk[STACK_MAX] = {};
+ uint8_t t_stk[STACK_MAX] = {};
+ std::vector<uint8_t> s_heap, t_heap;
+ uint8_t* sm;
+ uint8_t* tm;
+ if (m <= STACK_MAX && n <= STACK_MAX) {
+ sm = s_stk;
+ tm = t_stk;
+ } else {
+ s_heap.assign(m, 0);
+ t_heap.assign(n, 0);
+ sm = s_heap.data();
+ tm = t_heap.data();
+ }
+ double matches = 0;
+ for (size_t i = 0; i < m; ++i) {
+ const size_t start = (i >= match_dist) ? i - match_dist : 0;
+ const size_t end = std::min(i + match_dist + 1, n);
+ for (size_t j = start; j < end; ++j) {
+ if (!tm[j] && s[i] == t[j]) {
+ sm[i] = tm[j] = 1;
+ ++matches;
+ break;
+ }
+ }
+ }
+ if (matches == 0.0) {
+ res = 0.0;
+ return;
+ }
+ double transpositions = 0;
+ size_t k = 0;
+ for (size_t i = 0; i < m; ++i) {
+ if (sm[i]) {
+ while (!tm[k]) ++k;
+ if (s[i] != t[k]) ++transpositions;
+ ++k;
+ }
+ }
+ const double jaro = (matches / static_cast<double>(m) + matches / static_cast<double>(n) +
+ (matches - transpositions / 2.0) / matches) /
+ 3.0;
+ size_t prefix = 0;
+ const size_t max_prefix = std::min(static_cast<size_t>(4), std::min(m, n));
+ while (prefix < max_prefix && s[prefix] == t[prefix]) ++prefix;
+ res = jaro + static_cast<double>(prefix) * 0.1 * (1.0 - jaro);
+ }
+};
+
+struct NameJaccardSimilarity {
+ static constexpr auto name = "jaccard_similarity";
+};
+
+struct JaccardSimilarityOp {
+ using ResultDataType = DataTypeFloat64;
+ using ResultPaddedPODArray = PaddedPODArray<Float64>;
+
+ static void execute(const std::string_view& s, const std::string_view& t, double& res) {
+ if (s == t) {
+ res = 1.0;
+ return;
+ }
+ if (s.size() < 2 || t.size() < 2) {
+ res = 0.0;
+ return;
+ }
+ const size_t m = s.size(), n = t.size();
+ // Guard against heap allocation of 2*(m+n) bytes for very large STRING inputs.
+ constexpr size_t MAX_INPUT_LEN = 65535;
+ if (m > MAX_INPUT_LEN || n > MAX_INPUT_LEN) {
+ throw doris::Exception(ErrorCode::INVALID_ARGUMENT,
+ "Input string too long for jaccard_similarity, max {} bytes",
+ MAX_INPUT_LEN);
+ }
+
+ auto collect = [](const std::string_view& str, uint16_t* out) -> size_t {
+ size_t cnt = 0;
+ for (size_t i = 0; i + 1 < str.size(); ++i)
+ out[cnt++] = static_cast<uint16_t>((static_cast<uint16_t>((uint8_t)str[i]) << 8) |
+ (uint8_t)str[i + 1]);
+ std::sort(out, out + cnt);
Review Comment:
try to use bitset to collect and do intersects/union
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](func) Add levenshtein, damerau_levenshtein, jaro_winkler, jaccard_similarity built-in scalar functions [doris]
Posted by "linrrzqqq (via GitHub)" <gi...@apache.org>.
linrrzqqq commented on code in PR #60799:
URL: https://github.com/apache/doris/pull/60799#discussion_r2899064115
##########
regression-test/suites/function_p0/test_string_distance_functions.groovy:
##########
Review Comment:
more test, include column args, column and constant combination, and utf8 ......
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](func) Add levenshtein, damerau_levenshtein, jaro_winkler, jaccard_similarity built-in scalar functions [doris]
Posted by "hello-stephen (via GitHub)" <gi...@apache.org>.
hello-stephen commented on PR #60799:
URL: https://github.com/apache/doris/pull/60799#issuecomment-3957245398
# BE UT Coverage Report
Increment line coverage `81.55% (168/206)` :tada:
[Increment coverage report](http://coverage.selectdb-in.cc/coverage/e64286e51bb2d96eec1bd8d7121ccdfe71dc03f2_e64286e51bb2d96eec1bd8d7121ccdfe71dc03f2/increment_report/index.html)
[Complete coverage report](http://coverage.selectdb-in.cc/coverage/e64286e51bb2d96eec1bd8d7121ccdfe71dc03f2_e64286e51bb2d96eec1bd8d7121ccdfe71dc03f2/report/index.html)
| Category | Coverage |
|-------------------|--------------------|
| Function Coverage | 52.54% (19580/37269) |
| Line Coverage | 36.15% (182693/505384) |
| Region Coverage | 32.50% (141777/436281) |
| Branch Coverage | 33.45% (61454/183742) |
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](func) Add levenshtein, damerau_levenshtein, jaro_winkler, jaccard_similarity built-in scalar functions [doris]
Posted by "doris-robot (via GitHub)" <gi...@apache.org>.
doris-robot commented on PR #60799:
URL: https://github.com/apache/doris/pull/60799#issuecomment-3959916571
<details>
<summary>TPC-H: <b>Total hot run time: 28788 ms</b></summary>
```
machine: 'aliyun_ecs.c7a.8xlarge_32C64G'
scripts: https://github.com/apache/doris/tree/master/tools/tpch-tools
Tpch sf100 test result on commit 0c3b86a6851ef55a2713bd99a18f326bc9d6c677, data reload: false
------ Round 1 ----------------------------------
============================================
q1 17599 4610 4311 4311
q2 q3 10656 772 515 515
q4 4688 341 264 264
q5 7544 1190 1015 1015
q6 178 177 146 146
q7 765 829 680 680
q8 9296 1440 1363 1363
q9 4986 4677 4663 4663
q10 6844 1874 1640 1640
q11 443 259 234 234
q12 744 569 473 473
q13 17988 4203 3477 3477
q14 243 243 228 228
q15 987 807 798 798
q16 771 737 689 689
q17 729 900 406 406
q18 6228 5454 5270 5270
q19 1200 968 621 621
q20 501 495 388 388
q21 4802 1825 1371 1371
q22 351 291 236 236
Total cold run time: 97543 ms
Total hot run time: 28788 ms
----- Round 2, with runtime_filter_mode=off -----
============================================
q1 4392 4308 4328 4308
q2 q3 1752 2190 1718 1718
q4 849 1191 755 755
q5 4013 4299 4288 4288
q6 177 174 140 140
q7 1702 1594 1494 1494
q8 2438 2675 2495 2495
q9 7448 7496 7410 7410
q10 2702 2868 2379 2379
q11 527 435 429 429
q12 490 604 459 459
q13 3944 4361 3594 3594
q14 289 312 321 312
q15 914 834 831 831
q16 755 777 705 705
q17 1175 1562 1297 1297
q18 7281 6721 6578 6578
q19 894 880 901 880
q20 2168 2181 2151 2151
q21 4031 3499 3377 3377
q22 445 413 370 370
Total cold run time: 48386 ms
Total hot run time: 45970 ms
```
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](func) Add levenshtein, damerau_levenshtein, jaro_winkler, jaccard_similarity built-in scalar functions [doris]
Posted by "zclllyybb (via GitHub)" <gi...@apache.org>.
zclllyybb commented on PR #60799:
URL: https://github.com/apache/doris/pull/60799#issuecomment-3990876255
run buildall
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](func) Add levenshtein, damerau_levenshtein, jaro_winkler, jaccard_similarity built-in scalar functions [doris]
Posted by "doris-robot (via GitHub)" <gi...@apache.org>.
doris-robot commented on PR #60799:
URL: https://github.com/apache/doris/pull/60799#issuecomment-3991158023
<details>
<summary>TPC-DS: <b>Total hot run time: 183808 ms</b></summary>
```
machine: 'aliyun_ecs.c7a.8xlarge_32C64G'
scripts: https://github.com/apache/doris/tree/master/tools/tpcds-tools
TPC-DS sf100 test result on commit 54ddedd1a57e5d4232dc5735396482acc38d693d, data reload: false
query5 4953 631 521 521
query6 334 240 216 216
query7 4219 466 271 271
query8 349 267 248 248
query9 8744 2759 2713 2713
query10 515 364 361 361
query11 17024 16780 16604 16604
query12 190 134 130 130
query13 1276 451 353 353
query14 6520 3220 2983 2983
query14_1 2859 2782 2778 2778
query15 208 196 175 175
query16 971 470 459 459
query17 1081 751 632 632
query18 2616 443 349 349
query19 211 204 187 187
query20 149 132 137 132
query21 221 151 121 121
query22 4753 6039 5431 5431
query23 17365 17216 17079 17079
query23_1 17122 17036 16643 16643
query24 7266 1600 1227 1227
query24_1 1235 1233 1236 1233
query25 557 485 456 456
query26 1248 257 153 153
query27 2768 459 279 279
query28 4480 1874 1854 1854
query29 784 551 462 462
query30 311 245 215 215
query31 870 728 633 633
query32 78 71 71 71
query33 511 330 291 291
query34 927 906 555 555
query35 639 680 609 609
query36 1056 1129 1009 1009
query37 133 95 82 82
query38 2932 2966 2863 2863
query39 888 865 843 843
query39_1 829 829 835 829
query40 234 154 137 137
query41 62 62 59 59
query42 108 102 103 102
query43 389 402 352 352
query44
query45 197 189 190 189
query46 926 982 619 619
query47 2150 2165 2069 2069
query48 302 311 242 242
query49 627 468 386 386
query50 680 278 223 223
query51 4102 4106 3983 3983
query52 105 109 95 95
query53 289 338 289 289
query54 313 264 256 256
query55 89 86 82 82
query56 310 310 308 308
query57 1368 1364 1265 1265
query58 291 275 270 270
query59 2561 2724 2571 2571
query60 343 348 318 318
query61 153 148 149 148
query62 615 583 535 535
query63 316 282 276 276
query64 4890 1282 979 979
query65
query66 1395 461 360 360
query67 16212 16507 16247 16247
query68
query69 407 297 291 291
query70 1017 980 975 975
query71 342 305 288 288
query72 2780 2754 2387 2387
query73 536 552 316 316
query74 9986 10001 9676 9676
query75 2866 2758 2450 2450
query76 2299 1025 670 670
query77 376 401 317 317
query78 11171 11495 10708 10708
query79 1141 760 601 601
query80 998 612 536 536
query81 546 293 250 250
query82 1284 148 112 112
query83 354 274 241 241
query84 251 127 92 92
query85 1141 486 426 426
query86 416 328 304 304
query87 3096 3059 2963 2963
query88 3529 2685 2676 2676
query89 417 364 346 346
query90 1807 178 174 174
query91 165 158 135 135
query92 81 80 70 70
query93 887 868 507 507
query94 550 320 310 310
query95 605 347 393 347
query96 657 526 234 234
query97 2474 2506 2403 2403
query98 236 222 226 222
query99 1001 989 916 916
Total cold run time: 252918 ms
Total hot run time: 183808 ms
```
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](func) Add levenshtein, damerau_levenshtein, jaro_winkler, jaccard_similarity built-in scalar functions [doris]
Posted by "zclllyybb (via GitHub)" <gi...@apache.org>.
zclllyybb closed pull request #60799: [feat](func) Add levenshtein, damerau_levenshtein, jaro_winkler, jaccard_similarity built-in scalar functions
URL: https://github.com/apache/doris/pull/60799
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](func) Add levenshtein, damerau_levenshtein, jaro_winkler, cosine_similarity, jaccard_similarity built-in scalar functions [doris]
Posted by "zclllyybb (via GitHub)" <gi...@apache.org>.
zclllyybb commented on PR #60799:
URL: https://github.com/apache/doris/pull/60799#issuecomment-3952117380
btw, cosine_similarity is implemented in https://github.com/apache/doris/pull/60403. and I'd like to know why you add functions like `damerau_levenshtein`. seems rare. Is there any exist db system you are using supports them?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](func) Add levenshtein, damerau_levenshtein, jaro_winkler, jaccard_similarity built-in scalar functions [doris]
Posted by "puranjay2597 (via GitHub)" <gi...@apache.org>.
puranjay2597 commented on PR #60799:
URL: https://github.com/apache/doris/pull/60799#issuecomment-3952633963
@zclllyybb - I've added be-ut and regression-test cases, and also removed cosine_similarity since it conflicts with #60403.
Regarding damerau_levenshtein — ClickHouse has [damerauLevenshteinDistance] (https://clickhouse.com/docs/en/sql-reference/functions/string-functions#dameraulevensteindistance). The key difference from standard Levenshtein is that a single adjacent transposition (e.g. 'ab' → 'ba') costs 1 instead of 2, which matters for natural-language typo correction and deduplication
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](func) Add levenshtein, damerau_levenshtein, jaro_winkler, jaccard_similarity built-in scalar functions [doris]
Posted by "doris-robot (via GitHub)" <gi...@apache.org>.
doris-robot commented on PR #60799:
URL: https://github.com/apache/doris/pull/60799#issuecomment-3960606090
# BE UT Coverage Report
Increment line coverage `78.50% (168/214)` :tada:
[Increment coverage report](http://coverage.selectdb-in.cc/coverage/0c3b86a6851ef55a2713bd99a18f326bc9d6c677_0c3b86a6851ef55a2713bd99a18f326bc9d6c677/increment_report/index.html)
[Complete coverage report](http://coverage.selectdb-in.cc/coverage/0c3b86a6851ef55a2713bd99a18f326bc9d6c677_0c3b86a6851ef55a2713bd99a18f326bc9d6c677/report/index.html)
| Category | Coverage |
|-------------------|--------------------|
| Function Coverage | 52.53% (19593/37302) |
| Line Coverage | 36.14% (182795/505763) |
| Region Coverage | 32.50% (141939/436733) |
| Branch Coverage | 33.45% (61534/183957) |
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](func) Add levenshtein, damerau_levenshtein, jaro_winkler, jaccard_similarity built-in scalar functions [doris]
Posted by "Copilot (via GitHub)" <gi...@apache.org>.
Copilot commented on code in PR #60799:
URL: https://github.com/apache/doris/pull/60799#discussion_r2851043611
##########
be/src/vec/functions/function_string.cpp:
##########
@@ -290,6 +290,249 @@ struct FindInSetOp {
}
};
+struct NameLevenshtein {
+ static constexpr auto name = "levenshtein";
+};
+
+struct LevenshteinOp {
+ using ResultDataType = DataTypeInt32;
+ using ResultPaddedPODArray = PaddedPODArray<Int32>;
+
+ static void execute(const std::string_view& s, const std::string_view& t, int32_t& res) {
+ const size_t m = s.size();
+ const size_t n = t.size();
Review Comment:
`LevenshteinOp` is O(m×n) time and can become prohibitively expensive on large VARCHAR/STRING inputs (e.g., tens of thousands of bytes). Consider adding a length/cost guard (similar to other expensive functions) to prevent runaway CPU usage or query timeouts when users pass very long strings.
```suggestion
const size_t n = t.size();
// Guard against excessively expensive O(m * n) computation on very large inputs.
// If the estimated cost exceeds the threshold, return the maximal possible
// Levenshtein distance for these lengths (max(m, n)) without running DP.
constexpr size_t MAX_LEVENSHTEIN_COST = 4 * 1024 * 1024; // tunable upper bound
if (static_cast<unsigned long long>(m) * static_cast<unsigned long long>(n) >
static_cast<unsigned long long>(MAX_LEVENSHTEIN_COST)) {
res = static_cast<int32_t>(std::max(m, n));
return;
}
```
##########
be/src/vec/functions/function_string.cpp:
##########
@@ -290,6 +290,249 @@ struct FindInSetOp {
}
};
+struct NameLevenshtein {
+ static constexpr auto name = "levenshtein";
+};
+
+struct LevenshteinOp {
+ using ResultDataType = DataTypeInt32;
+ using ResultPaddedPODArray = PaddedPODArray<Int32>;
+
+ static void execute(const std::string_view& s, const std::string_view& t, int32_t& res) {
+ const size_t m = s.size();
+ const size_t n = t.size();
+ if (m == 0) {
+ res = static_cast<int32_t>(n);
+ return;
+ }
+ if (n == 0) {
+ res = static_cast<int32_t>(m);
+ return;
+ }
+ if (s == t) {
+ res = 0;
+ return;
+ }
+ constexpr size_t STACK_MAX = 512;
+ int32_t prev_stk[STACK_MAX + 1], curr_stk[STACK_MAX + 1];
+ std::vector<int32_t> prev_heap, curr_heap;
+ int32_t* prev_row;
+ int32_t* curr_row;
+ if (n <= STACK_MAX) {
+ prev_row = prev_stk;
+ curr_row = curr_stk;
+ } else {
+ prev_heap.resize(n + 1);
+ curr_heap.resize(n + 1);
+ prev_row = prev_heap.data();
+ curr_row = curr_heap.data();
+ }
+ for (size_t j = 0; j <= n; ++j) prev_row[j] = static_cast<int32_t>(j);
+ for (size_t i = 1; i <= m; ++i) {
+ curr_row[0] = static_cast<int32_t>(i);
+ for (size_t j = 1; j <= n; ++j) {
+ if (s[i - 1] == t[j - 1]) {
+ curr_row[j] = prev_row[j - 1];
+ } else {
+ curr_row[j] = 1 + std::min({prev_row[j - 1], prev_row[j], curr_row[j - 1]});
+ }
+ }
+ std::swap(prev_row, curr_row);
+ }
+ res = prev_row[n];
+ }
+};
+
+struct NameDamerauLevenshtein {
+ static constexpr auto name = "damerau_levenshtein";
+};
+
+struct DamerauLevenshteinOp {
+ using ResultDataType = DataTypeInt32;
+ using ResultPaddedPODArray = PaddedPODArray<Int32>;
+
+ static void execute(const std::string_view& s, const std::string_view& t, int32_t& res) {
+ const size_t m = s.size(), n = t.size();
+ if (m == 0) {
+ res = static_cast<int32_t>(n);
+ return;
+ }
+ if (n == 0) {
+ res = static_cast<int32_t>(m);
+ return;
+ }
+ const size_t stride = n + 2;
+ const int32_t max_dist = static_cast<int32_t>(m + n);
+ std::vector<int32_t> d((m + 2) * stride, 0);
+ d[0] = max_dist;
+ for (size_t i = 0; i <= m; ++i) {
+ d[(i + 1) * stride + 0] = max_dist;
+ d[(i + 1) * stride + 1] = static_cast<int32_t>(i);
+ }
+ for (size_t j = 0; j <= n; ++j) {
+ d[0 * stride + (j + 1)] = max_dist;
+ d[1 * stride + (j + 1)] = static_cast<int32_t>(j);
+ }
+ int32_t da[256] = {};
+ for (size_t i = 1; i <= m; ++i) {
+ int32_t db = 0;
+ for (size_t j = 1; j <= n; ++j) {
+ const int32_t k = da[(uint8_t)t[j - 1]];
+ const int32_t l = db;
+ int32_t cost;
+ if (s[i - 1] == t[j - 1]) {
+ cost = 0;
+ db = static_cast<int32_t>(j);
+ } else {
+ cost = 1;
+ }
+ const int32_t trans = d[static_cast<size_t>(k) * stride + static_cast<size_t>(l)] +
+ (static_cast<int32_t>(i) - k - 1) + 1 +
+ (static_cast<int32_t>(j) - l - 1);
+ d[(i + 1) * stride + (j + 1)] =
+ std::min({d[i * stride + j] + cost, d[(i + 1) * stride + j] + 1,
+ d[i * stride + (j + 1)] + 1, trans});
+ }
+ da[(uint8_t)s[i - 1]] = static_cast<int32_t>(i);
+ }
+ res = d[(m + 1) * stride + (n + 1)];
+ }
+};
+
+struct NameJaroWinkler {
+ static constexpr auto name = "jaro_winkler";
+};
+
+struct JaroWinklerOp {
+ using ResultDataType = DataTypeFloat64;
+ using ResultPaddedPODArray = PaddedPODArray<Float64>;
+
+ static void execute(const std::string_view& s, const std::string_view& t, double& res) {
+ if (s == t) {
+ res = 1.0;
+ return;
+ }
+ const size_t m = s.size(), n = t.size();
+ if (m == 0 || n == 0) {
+ res = 0.0;
+ return;
+ }
+ const size_t match_dist = std::max(m, n) / 2 - (std::max(m, n) >= 2 ? 1 : 0);
+ constexpr size_t STACK_MAX = 512;
+ uint8_t s_stk[STACK_MAX] = {};
+ uint8_t t_stk[STACK_MAX] = {};
+ std::vector<uint8_t> s_heap, t_heap;
+ uint8_t* sm;
+ uint8_t* tm;
+ if (m <= STACK_MAX && n <= STACK_MAX) {
+ sm = s_stk;
+ tm = t_stk;
+ } else {
+ s_heap.assign(m, 0);
+ t_heap.assign(n, 0);
+ sm = s_heap.data();
+ tm = t_heap.data();
+ }
+ double matches = 0;
+ for (size_t i = 0; i < m; ++i) {
+ const size_t start = (i >= match_dist) ? i - match_dist : 0;
+ const size_t end = std::min(i + match_dist + 1, n);
+ for (size_t j = start; j < end; ++j) {
+ if (!tm[j] && s[i] == t[j]) {
+ sm[i] = tm[j] = 1;
+ ++matches;
+ break;
+ }
+ }
+ }
+ if (matches == 0.0) {
+ res = 0.0;
+ return;
+ }
+ double transpositions = 0;
+ size_t k = 0;
+ for (size_t i = 0; i < m; ++i) {
+ if (sm[i]) {
+ while (!tm[k]) ++k;
+ if (s[i] != t[k]) ++transpositions;
+ ++k;
+ }
+ }
+ const double jaro = (matches / static_cast<double>(m) + matches / static_cast<double>(n) +
+ (matches - transpositions / 2.0) / matches) /
+ 3.0;
+ size_t prefix = 0;
+ const size_t max_prefix = std::min(static_cast<size_t>(4), std::min(m, n));
+ while (prefix < max_prefix && s[prefix] == t[prefix]) ++prefix;
+ res = jaro + static_cast<double>(prefix) * 0.1 * (1.0 - jaro);
+ }
+};
+
+struct NameJaccardSimilarity {
+ static constexpr auto name = "jaccard_similarity";
+};
+
+struct JaccardSimilarityOp {
+ using ResultDataType = DataTypeFloat64;
+ using ResultPaddedPODArray = PaddedPODArray<Float64>;
+
+ static void execute(const std::string_view& s, const std::string_view& t, double& res) {
+ if (s == t) {
+ res = 1.0;
+ return;
+ }
+ if (s.size() < 2 && t.size() < 2) {
+ res = 0.0;
+ return;
+ }
Review Comment:
In `JaccardSimilarityOp`, the two consecutive checks for `size() < 2` both return 0.0 (except for the earlier `s == t` fast path), so one of them is redundant. Simplifying this branch would make the edge-case behavior easier to follow and slightly reduce branching.
```suggestion
```
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/trees/expressions/functions/scalar/JaccardSimilarity.java:
##########
@@ -0,0 +1,78 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+package org.apache.doris.nereids.trees.expressions.functions.scalar;
+
+import org.apache.doris.catalog.FunctionSignature;
+import org.apache.doris.nereids.trees.expressions.Expression;
+import org.apache.doris.nereids.trees.expressions.functions.ExplicitlyCastableSignature;
+import org.apache.doris.nereids.trees.expressions.functions.PropagateNullable;
+import org.apache.doris.nereids.trees.expressions.shape.BinaryExpression;
+import org.apache.doris.nereids.trees.expressions.visitor.ExpressionVisitor;
+import org.apache.doris.nereids.types.DoubleType;
+import org.apache.doris.nereids.types.StringType;
+import org.apache.doris.nereids.types.VarcharType;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableList;
+
+import java.util.List;
+
+/**
+ * ScalarFunction 'jaccard_similarity'. Returns Jaccard similarity (0.0-1.0) based on character bigrams.
Review Comment:
The Javadoc says Jaccard similarity is based on “character bigrams”, but the implementation in BE builds bigrams from raw bytes. Please align the documentation with the actual semantics (e.g., “byte bigrams”) to avoid confusion for UTF-8 input.
```suggestion
* ScalarFunction 'jaccard_similarity'. Returns Jaccard similarity (0.0-1.0) based on byte bigrams of the input strings.
```
##########
be/src/vec/functions/function_string.cpp:
##########
@@ -290,6 +290,249 @@ struct FindInSetOp {
}
};
+struct NameLevenshtein {
+ static constexpr auto name = "levenshtein";
+};
+
+struct LevenshteinOp {
+ using ResultDataType = DataTypeInt32;
+ using ResultPaddedPODArray = PaddedPODArray<Int32>;
+
+ static void execute(const std::string_view& s, const std::string_view& t, int32_t& res) {
+ const size_t m = s.size();
+ const size_t n = t.size();
+ if (m == 0) {
+ res = static_cast<int32_t>(n);
+ return;
+ }
+ if (n == 0) {
+ res = static_cast<int32_t>(m);
+ return;
+ }
+ if (s == t) {
+ res = 0;
+ return;
+ }
+ constexpr size_t STACK_MAX = 512;
+ int32_t prev_stk[STACK_MAX + 1], curr_stk[STACK_MAX + 1];
+ std::vector<int32_t> prev_heap, curr_heap;
+ int32_t* prev_row;
+ int32_t* curr_row;
+ if (n <= STACK_MAX) {
+ prev_row = prev_stk;
+ curr_row = curr_stk;
+ } else {
+ prev_heap.resize(n + 1);
+ curr_heap.resize(n + 1);
+ prev_row = prev_heap.data();
+ curr_row = curr_heap.data();
+ }
+ for (size_t j = 0; j <= n; ++j) prev_row[j] = static_cast<int32_t>(j);
+ for (size_t i = 1; i <= m; ++i) {
+ curr_row[0] = static_cast<int32_t>(i);
+ for (size_t j = 1; j <= n; ++j) {
+ if (s[i - 1] == t[j - 1]) {
+ curr_row[j] = prev_row[j - 1];
+ } else {
+ curr_row[j] = 1 + std::min({prev_row[j - 1], prev_row[j], curr_row[j - 1]});
+ }
+ }
+ std::swap(prev_row, curr_row);
+ }
+ res = prev_row[n];
+ }
+};
+
+struct NameDamerauLevenshtein {
+ static constexpr auto name = "damerau_levenshtein";
+};
+
+struct DamerauLevenshteinOp {
+ using ResultDataType = DataTypeInt32;
+ using ResultPaddedPODArray = PaddedPODArray<Int32>;
+
+ static void execute(const std::string_view& s, const std::string_view& t, int32_t& res) {
+ const size_t m = s.size(), n = t.size();
+ if (m == 0) {
+ res = static_cast<int32_t>(n);
+ return;
+ }
+ if (n == 0) {
+ res = static_cast<int32_t>(m);
+ return;
+ }
+ const size_t stride = n + 2;
+ const int32_t max_dist = static_cast<int32_t>(m + n);
+ std::vector<int32_t> d((m + 2) * stride, 0);
+ d[0] = max_dist;
Review Comment:
`DamerauLevenshteinOp` allocates a full (m+2)×(n+2) `int32_t` matrix based directly on input lengths. With VARCHAR potentially up to 65533 bytes, this can attempt multi‑GB allocations (or overflow size computations) and lead to OOM/instability. Please add an explicit guard (max input length and/or max matrix cells with overflow-safe multiplication) and fail gracefully (e.g., throw a controlled exception or return NULL) before allocating.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](func) Add levenshtein, damerau_levenshtein, jaro_winkler, jaccard_similarity built-in scalar functions [doris]
Posted by "zclllyybb (via GitHub)" <gi...@apache.org>.
zclllyybb commented on PR #60799:
URL: https://github.com/apache/doris/pull/60799#issuecomment-3959599400
@puranjay2597 got it. I will review this pr in few days
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](func) Add levenshtein, damerau_levenshtein, jaro_winkler, jaccard_similarity built-in scalar functions [doris]
Posted by "puranjay2597 (via GitHub)" <gi...@apache.org>.
puranjay2597 commented on PR #60799:
URL: https://github.com/apache/doris/pull/60799#issuecomment-5505988344
GitHub does not allow reopening this PR because the branch was force-pushed after it was closed. I have addressed the review feedback (UTF-8 support, reduced duplication between jaro/jaro_winkler, reworked jaccard_similarity to match ClickHouse's stringJaccardIndex semantics, FE constant folding, expanded tests) and dropped levenshtein/damerau_levenshtein since they since landed separately (#60412, #65278). Continuing as #67436.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org