builtins: support fuzzystrmatch builtins

[jordanlewis]

Postgres provides the fuzzystrmatch module, which includes several useful functions:

• [x] levenshtein, to calculate levenshtein distance between strings
• [ ] levenshtein_less_equal
• [x] soundex and difference to calculate Soundex codes for names
• [ ] daitch_mokotoff soundex
  • This is better for non-English names according to https://www.postgresql.org/docs/current/fuzzystrmatch.html#FUZZYSTRMATCH-DAITCH-MOKOTOFF
• [ ] metaphone, dmetaphone and dmetaphone_alt to compute "sounds like" strings for strings.

Out of these, the levenshtein functions are likely most important and widely-used.

To implement these, add functions in pkg/sql/sem/builtins/builtins.go and a new logic test in pkg/sql/logictest/testdata/logic_test/fuzzystrmatch.

Jira issue: CRDB-11073

[blathers-crl[bot]]

Hi @jordanlewis, please add a C-ategory label to your issue. Check out the label system docs.

_{:owl: Hoot! I am a Blathers, a bot for CockroachDB. My owner is otan.}

[rafiss]

Only one builtin was added in #56843 so keeping this open

[eaarranz]

I have improved a little bit the levenshtein implementation to be more similar to the one that Postgresql implements and that implements the levenshtein_less_equal builtin.

I will open a PR, but we may reopen this issue and I can try to implement also the: metaphone, dmetaphone and dmetaphone_alt missing ones!

[alimoosavi]

@jordanlewis @otan I am new to cockroachdb project and this issue seems attractive to me , please assign this issue to me.

[otan]

we generally don't assign issues. you are however free to work on it!

note there is already a PR for levenshtein_less_equal

[SentientRamen12]

Hi @otan @jordanlewis I see the levenshtein_less_equal PR still open. Can I pick this issue?

[jordanlewis]

Yes!

On Mon, Mar 27, 2023 at 3:58 PM LordThevenin @.***> wrote:

Hi @otan https://github.com/otan @jordanlewis https://github.com/jordanlewis I see the levenshtein_less_equal PR still open. Can I pick this issue?

— Reply to this email directly, view it on GitHub https://github.com/cockroachdb/cockroach/issues/56820#issuecomment-1485781174, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAAKWLLIKUOF6EQHFEGMQY3W6HWMXANCNFSM4TZBP6CQ . You are receiving this because you were mentioned.Message ID: @.***>

[Azanul]

No-one seems to be working on this. I think I can implement levenshtein_less_equal.

[giangpham712]

This affects efcore.pg tests

@fqazi

[fqazi]

@giangpham712 Let's skip these tests for now since I don't think we'll get the remaining ones quickly