Re: multibyte charater set in levenshtein function

SELECT SUM(levenshtein(a, 'foo')) from words;
SELECT SUM(levenshtein(a, 'Urbański')) FROM words;
SELECT SUM(levenshtein(a, 'ańs')) FROM words;
SELECT SUM(levenshtein(a, 'foo')) from words2;
SELECT SUM(levenshtein(a, 'дом')) FROM words2;
SELECT SUM(levenshtein(a, 'компьютер')) FROM words2;

Before this patch results was:
67 98 63 102 108 177
And after patch:
65 100 65 104 111 182
It is slower a bit, but I think it is a price for having less code
duplication.

Now test for levenshtein_less_equal performance.

test=# SELECT * FROM words WHERE levenshtein(a, 'extensize') <= 2;
a
-----------
expensive
extension
extensive
(3 rows)

Time: 98,083 ms

test=# SELECT * FROM words WHERE levenshtein_less_equal(a, 'extensize', 2)
<= 2;
a
-----------
expensive
extension
extensive
(3 rows)

Time: 48,069 ms

test=# SELECT * FROM words2 WHERE levenshtein(a, 'клубничный') <= 2;
a
------------
кузничный
кубичный
клубочный
клубничный
(4 rows)

Time: 197,499 ms

test=# SELECT * FROM words2 WHERE levenshtein_less_equal(a, 'клубничный', 3)
<= 2;
a
------------
кузничный
кубичный
клубочный
клубничный
(4 rows)

Time: 100,073 ms

It gives some speedup for search on word with small distances.

test=# SELECT sum(levenshtein(a, 'extensize')) from words;
sum
--------
835545
(1 row)

Time: 96,253 ms

test=# SELECT sum(levenshtein_less_equal(a, 'extensize', 20)) from words;
sum
--------
835545
(1 row)

Time: 98,438 ms

With big distances it gives similar performance because in this case similar
branch of code is used.
In order to test it with longer words I created a table with random
combinations of words.

test=# create table phrases (a text primary key);
test=# insert into phrases select string_agg(y.a, ' ') from (select x.a,
row_number() over () from (select a from words order by random()) x) y group
by (y.row_number / 10);

test=# select * from phrases limit 10;

a
--------------------------------------------------------------------------------------------------------------
hosiery's spermatozoa Haleakala disco greenness beehive paranoids atrophy
unfair
Weinberg's all profanity's individualized bellowed perishables Romanov's
communicant's landlady's pauperized
Ito seasoned jawbreakers you'll hurling's showcasing anecdota cauliflower
intellectualism facilitate
infantryman's busheled designing lucid nutritionists Aesculapius's rifle
clefting exult Milosevic
foresight lurking capitulation's pantsuits traumatizes moonlighting
lancer's Longfellow rising unclasps
permutes centralest cavalryman Dwight granddaughter knight tallyho's sober
graduate locket's
knucklehead courtliest sapphires baize coniferous emolument antarctic
Laocoon's deadens unseemly
Tartars utopians Pekingese's Cartwright badge's Dollie's spryness Ajax's
Amber's bookkeeper
spouting concordant Indus carbonation cinnamon's stockbrokers Evita's
Canaries Waldorf's rampage
Amparo exertions Kuznetsk's divots humongous wolverine chugged laurels
Goliaths hazelnut
(10 rows)

test=# select * from phrases where levenshtein('kkkknucklehead courtliest
sapphires be coniferous emolument antarctic Laocoon''s deadens unseemly', a)
<= 10;

a
--------------------------------------------------------------------------------------------------
knucklehead courtliest sapphires baize coniferous emolument antarctic
Laocoon's deadens unseemly
(1 row)

Time: 581,850 ms

test=# select * from phrases where levenshtein_less_equal('kkkknucklehead
courtliest sapphires be coniferous emolument antarctic Laocoon''s deadens
unseemly', a, 10) <= 10;

a
--------------------------------------------------------------------------------------------------
knucklehead courtliest sapphires baize coniferous emolument antarctic
Laocoon's deadens unseemly
(1 row)

Time: 22,876 ms

It gives great speedup for search with small distances on relatively long
strings.

test=# select sum(levenshtein('kkkknucklehead courtliest sapphires be
coniferous emolument antarctic Laocoon''s deadens unseemly', a)) from
phrases;
sum
--------
794601
(1 row)

Time: 571,138 ms

test=# select sum(levenshtein_less_equal('kkkknucklehead courtliest
sapphires be coniferous emolument antarctic Laocoon''s deadens unseemly', a,
100)) from phrases;
sum
--------
794601
(1 row)

Time: 562,895 ms

Similar results appears for multi-byte strings.

test=# create table phrases2 (a text primary key);
test=# insert into phrases2 select string_agg(y.a, ' ') from (select x.a,
row_number() over () from (select a from words2 order by random()) x) y
group by (y.row_number / 10);
INSERT 0 14584

test=# select * from phrases2 limit 10;

a

-----------------------------------------------------------------------------------------------------------------------------------
борис спиннинг растопочный цифра выдохнуть иридий гнёздышко омоновский
базовый
пожжёте закосить насыщающий паратый продрых обеспложивание милливатт
бамбуковый отпекающий книжница
приложиться разный устремляющийся отучающийся абрикосовка протоколируются
сострадательный отрясший вывалить браманизм
наполниться агафоновна испольный подтаскивающий запруживавшийся трофимович
перетаскиваемый обручавший процентщица передов
вихрастый отволочённый дискотека пришей распасовывавший полиция возделавший
трехглавый битва загазованный
обовьетесь перехитривший инулин стелить недоброжелательность изотрёте
пятиалтынный жабовидный щелочно дефицитность
сиротиночка хлорбензол вгрызаться прокрашивать никарагуанец валентный
понесённый перестегивание воспретительный переименовываемый
таявший раскупорившийся передислоцируется юлианович праздничный лачужка
присыхать отбеливший фехтовальный удобряющий
слепнул зонт уластить удобрение тормозивший ушибся ошибся мкс
сейсмологический лесомелиорация
рабовладельцем неудачный самовоспламенение карбидный круглопильный кубинцем
подлакированный наблюдение исцарапавшийся издёргавший
(10 rows)

test=# select * from phrases2 where levenshtein('таяй раскупорившийся
передислоцируется юлианович праздничный лачужка присыхать опппливший
ффехтовальный уууудобряющий', a) <= 10;

a

------------------------------------------------------------------------------------------------------------------
----
таявший раскупорившийся передислоцируется юлианович праздничный лачужка
присыхать отбеливший фехтовальный удобряющий
(1 row)

Time: 1291,318 ms

test=# select * from phrases2 where levenshtein_less_equal('таяй
раскупорившийся передислоцируется юлианович праздничный лачужка присыхать
опппливший ффехтовальный уууудобряющий', a, 10) <= 10;

a

------------------------------------------------------------------------------------------------------------------
----
таявший раскупорившийся передислоцируется юлианович праздничный лачужка
присыхать отбеливший фехтовальный удобряющий
(1 row)

Time: 55,405 ms

test=# select sum(levenshtein_less_equal('таяй раскупорившийся
передислоцируется юлианович праздничный лачужка присыхать опппливший
ффехтовальный уууудобряющий', a, 200)) from phrases;
sum
---------
1091878
(1 row)

Time: 674,734 ms

test=# select sum(levenshtein('таяй раскупорившийся передислоцируется
юлианович праздничный лачужка присыхать опппливший ффехтовальный
уууудобряющий', a)) from phrases;
sum
---------
1091878
(1 row)

Time: 673,515 ms

----
With best regards,
Alexander Korotkov.