Re: multibyte charater set in levenshtein function - Mailing list pgsql-hackers

SELECT SUM(levenshtein(a, 'foo')) from words;<br />SELECT SUM(levenshtein(a, 'Urbański')) FROM words;<br />SELECT
SUM(levenshtein(a,'ańs')) FROM words;<br />SELECT SUM(levenshtein(a, 'foo')) from words2;<br /> SELECT
SUM(levenshtein(a,'дом')) FROM words2;<br />SELECT SUM(levenshtein(a, 'компьютер')) FROM words2;<br /><br />Before this
patchresults was:<br />67 98 63 102 108 177<br />And after patch:<br />65 100 65 104 111 182<br /> It is slower a bit,
butI think it is a price for having less code duplication.<br /><br />Now test for levenshtein_less_equal
performance.<br/><br />test=# SELECT * FROM words WHERE levenshtein(a, 'extensize') <= 2;<br />      a     <br
/>-----------<br/> expensive<br /> extension<br /> extensive<br />(3 rows)<br /><br />Time: 98,083 ms<br /><br />test=#
SELECT* FROM words WHERE levenshtein_less_equal(a, 'extensize', 2) <= 2;<br />     a     <br /> -----------<br
/> expensive<br/> extension<br /> extensive<br />(3 rows)<br /><br />Time: 48,069 ms<br /><br />test=# SELECT * FROM
words2WHERE levenshtein(a, 'клубничный') <= 2;<br />      a      <br /> ------------<br />  кузничный<br />
 кубичный<br/>  клубочный<br />  клубничный<br /> (4 rows)<br /><br /> Time: 197,499 ms<br /><br />test=# SELECT * FROM
words2WHERE levenshtein_less_equal(a, 'клубничный', 3) <= 2;<br />     a      <br />------------<br /> кузничный<br
/> кубичный<br/> клубочный<br /> клубничный<br />(4 rows)<br /><br />Time: 100,073 ms<br /><br />It gives some speedup
forsearch on word with small distances.<br /><br />test=# SELECT sum(levenshtein(a, 'extensize')) from words;<br /> 
sum  <br />--------<br /> 835545<br />(1 row)<br /><br />Time: 96,253 ms<br /><br />test=# SELECT
sum(levenshtein_less_equal(a,'extensize', 20)) from words;<br />   sum   <br />--------<br /> 835545<br />(1 row)<br
/><br/>Time: 98,438 ms<br /><br />With big distances it gives similar performance because in this case similar branch
ofcode is used.<br />In order to test it with longer words I created a table with random combinations of words.<br
/><br/>test=# create table phrases (a text primary key);<br />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);<br/><br />test=# select * from phrases limit 10;<br />                                                     
a                                                      <br
/>--------------------------------------------------------------------------------------------------------------<br/>
 hosiery'sspermatozoa Haleakala disco greenness beehive paranoids atrophy unfair<br /> Weinberg's all profanity's
individualizedbellowed perishables Romanov's communicant's landlady's pauperized<br />  Ito seasoned jawbreakers you'll
hurling'sshowcasing anecdota cauliflower intellectualism facilitate<br /> infantryman's busheled designing lucid
nutritionistsAesculapius's rifle clefting exult Milosevic<br />  foresight lurking capitulation's pantsuits traumatizes
moonlightinglancer's Longfellow rising unclasps<br /> permutes centralest cavalryman Dwight granddaughter knight
tallyho'ssober graduate locket's<br />  knucklehead courtliest sapphires baize coniferous emolument antarctic Laocoon's
deadensunseemly<br /> Tartars utopians Pekingese's Cartwright badge's Dollie's spryness Ajax's Amber's bookkeeper<br />
 spoutingconcordant Indus carbonation cinnamon's stockbrokers Evita's Canaries Waldorf's rampage<br /> Amparo exertions
Kuznetsk'sdivots humongous wolverine chugged laurels Goliaths hazelnut<br />(10 rows)<br /><br />test=# select * from
phraseswhere levenshtein('kkkknucklehead courtliest   sapphires be coniferous emolument antarctic Laocoon''s deadens
unseemly',a) <= 10;<br />                                               
a                                                <br />
--------------------------------------------------------------------------------------------------<br/> knucklehead
courtliestsapphires baize coniferous emolument antarctic Laocoon's deadens unseemly<br />(1 row)<br /><br /> Time:
581,850ms<br /><br />test=# select * from phrases where levenshtein_less_equal('kkkknucklehead courtliest   sapphires
beconiferous emolument antarctic Laocoon''s deadens unseemly', a, 10) <= 10;<br />
                                               a                                                 <br />
--------------------------------------------------------------------------------------------------<br/>  knucklehead
courtliestsapphires baize coniferous emolument antarctic Laocoon's deadens unseemly<br /> (1 row)<br /><br /> Time:
22,876ms<br /><br />It gives great speedup for search with small distances on relatively long strings.<br /><br
/>test=#select sum(levenshtein('kkkknucklehead courtliest   sapphires be coniferous emolument antarctic Laocoon''s
deadensunseemly', a)) from phrases;<br />   sum   <br />--------<br /> 794601<br />(1 row)<br /><br />Time: 571,138
ms<br/><br />test=# select sum(levenshtein_less_equal('kkkknucklehead courtliest   sapphires be coniferous emolument
antarcticLaocoon''s deadens unseemly', a, 100)) from phrases;<br />   sum   <br />--------<br /> 794601<br />(1 row)<br
/><br/>Time: 562,895 ms<br /><br />Similar results appears for multi-byte strings.<br /><br />test=# create table
phrases2(a text primary key);<br /> 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);<br />INSERT 0
14584<br/><br /><br />test=# select * from phrases2 limit 10;<br />
                                                                a                                                <br
/>                <br
/>-----------------------------------------------------------------------------------------------------------------------------------<br
/> борис спиннинг растопочный цифра выдохнуть иридий гнёздышко омоновский базовый<br /> пожжёте закосить насыщающий
паратыйпродрых обеспложивание милливатт бамбуковый отпекающий книжница<br /> приложиться разный устремляющийся
отучающийсяабрикосовка протоколируются сострадательный отрясший вывалить браманизм<br />  наполниться агафоновна
испольныйподтаскивающий запруживавшийся трофимович перетаскиваемый обручавший процентщица передов<br /> вихрастый
отволочённыйдискотека пришей распасовывавший полиция возделавший трехглавый битва загазованный<br />  обовьетесь
перехитрившийинулин стелить недоброжелательность изотрёте пятиалтынный жабовидный щелочно дефицитность<br
/> сиротиночкахлорбензол вгрызаться прокрашивать никарагуанец валентный понесённый перестегивание воспретительный
переименовываемый<br/>  таявший раскупорившийся передислоцируется юлианович праздничный лачужка присыхать отбеливший
фехтовальныйудобряющий<br /> слепнул зонт уластить удобрение тормозивший ушибся ошибся мкс сейсмологический
лесомелиорация<br/> рабовладельцем неудачный самовоспламенение карбидный круглопильный кубинцем подлакированный
наблюдениеисцарапавшийся издёргавший<br /> (10 rows)<br /><br />test=# select * from phrases2 where levenshtein('таяй
раскупорившийсяпередислоцируется юлианович праздничный лачужка присыхать опппливший ффехтовальный уууудобряющий', a)
<=10;<br />                                                         
a                                                      <br />     <br
/>------------------------------------------------------------------------------------------------------------------<br
/>----<br/> таявший раскупорившийся передислоцируется юлианович праздничный лачужка присыхать отбеливший фехтовальный
удобряющий<br/> (1 row)<br /><br />Time: 1291,318 ms<br /><br />test=# select * from phrases2 where
levenshtein_less_equal('таяйраскупорившийся передислоцируется юлианович праздничный лачужка присыхать опппливший
ффехтовальныйуууудобряющий', a, 10) <= 10;<br />                                                          
a                                                      <br />     <br />
------------------------------------------------------------------------------------------------------------------<br/>
----<br/>  таявший раскупорившийся передислоцируется юлианович праздничный лачужка присыхать отбеливший фехтовальный
удобряющий<br/> (1 row)<br /><br /> Time: 55,405 ms<br /><br />test=# select sum(levenshtein_less_equal('таяй
раскупорившийсяпередислоцируется юлианович праздничный лачужка присыхать опппливший ффехтовальный уууудобряющий', a,
200))from phrases;<br />   sum   <br />---------<br />  1091878<br />(1 row)<br /><br />Time: 674,734 ms<br /><br
/>test=#select sum(levenshtein('таяй раскупорившийся передислоцируется юлианович праздничный лачужка присыхать
оппплившийффехтовальный уууудобряющий', a)) from phrases;<br />    sum   <br />---------<br /> 1091878<br />(1 row)<br
/><br/>Time: 673,515 ms<br /><br />----<br />With best regards,<br />Alexander Korotkov. <br />