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