Thread: multibyte charater set in levenshtein function

Excerpts from Alexander Korotkov's message of lun may 10 11:35:02 -0400 2010:
> Hackers,
> 
> The current version of levenshtein function in fuzzystrmatch contrib modulte
> doesn't work properly with multibyte charater sets.

> My patch make this function works properly with multibyte charater sets.

Great.  Please add it to the next commitfest:
http://commitfest.postgresql.org

On a quick look, I didn't like the way you separated the 
"pg_database_encoding_max_length() > 1" cases.  There seem to be too
much common code.  Can that be refactored a bit better?
-- 

Alexander Korotkov escribió:
> On Wed, May 12, 2010 at 11:04 PM, Alvaro Herrera <alvherre@alvh.no-ip.org>wrote:
> 
> > On a quick look, I didn't like the way you separated the
> > "pg_database_encoding_max_length() > 1" cases.  There seem to be too
> > much common code.  Can that be refactored a bit better?
> >
> I did a little refactoring in order to avoid some similar code.
> I'm not quite sure about my CHAR_CMP macro. Is it a good idea?

Well, since it's only used in one place, why are you defining a macro at
all?

-- 
Alvaro Herrera                                http://www.CommandPrompt.com/
The PostgreSQL Company - Command Prompt, Inc.

Hi, I'm reviewing "Multibyte charater set in levenshtein function" patch.
https://commitfest.postgresql.org/action/patch_view?id=304

The main logic seems to be good, but I have some comments about
the coding style and refactoring.

* levenshtein_internal() and levenshtein_less_equal_internal() are very similar. Can you merge the code? We can always
useless_equal_internal() if the overhead is ignorable. Did you compare them? 

* There are many "if (!multibyte_encoding)" in levenshtein_internal(). How about split the function into two funcs for
single-bytechars and multi-byte chars? (ex. levenshtein_internal_mb() ) Or, we can always use multi-byte version if the
overheadis small. 

* I prefer a struct rather than an array.  "4 * m" and "3 * m" look like magic numbers for me. Could you name the
entrieswith definition of a struct?   /*    * For multibyte encoding we'll also store array of lengths of    *
charactersand array with character offsets in first string    * in order to avoid great number of pg_mblen calls.    */
 prev = (int *) palloc(4 * m * sizeof(int)); 

* There are some compiler warnings. Avoid them if possible.
fuzzystrmatch.c: In function ‘levenshtein_less_equal_internal’:
fuzzystrmatch.c:428: warning: ‘char_lens’ may be used uninitialized in
this function
fuzzystrmatch.c:428: warning: ‘offsets’ may be used uninitialized in
this function
fuzzystrmatch.c:430: warning: ‘curr_right’ may be used uninitialized
in this function
fuzzystrmatch.c: In function ‘levenshtein_internal’:
fuzzystrmatch.c:222: warning: ‘char_lens’ may be used uninitialized in
this function

* Coding style: Use "if (m == 0)" instead of "if (!m)" when the type
of 'm' is an integer.

* Need to fix the caution in docs.
http://developer.postgresql.org/pgdocs/postgres/fuzzystrmatch.html
| Caution: At present, fuzzystrmatch does not work well with
| multi-byte encodings (such as UTF-8).
but now levenshtein supports multi-byte encoding!  We should
mention which function supports mbchars not to confuse users.

* (Not an issue for the patch, but...) Could you rewrite PG_GETARG_TEXT_P, VARDATA, and VARSIZE to PG_GETARG_TEXT_PP,
VARDATA_ANY,and VARSIZE_ANY_EXHDR? Unpacking versions make the core a bit faster. 

--
Itagaki Takahiro

2010/7/13 Alexander Korotkov <aekorotkov@gmail.com>:
> Anyway I think that overhead is not ignorable. That's why I have splited
> levenshtein_internal into levenshtein_internal and levenshtein_internal_mb,
> and levenshtein_less_equal_internal into levenshtein_less_equal_internal and
> levenshtein_less_equal_internal_mb.

Thank you for good measurement! Then, it's reasonable to have multiple
implementations. It also has documentation. I'll change status of the
patch to "Ready for Committer".

The patch is good enough except argument types for some functions.
For example: - char* vs. const char* - text* vs. const char* + length
I hope committers would check whether there are better types for them.

-- 
Itagaki Takahiro

On Tue, Jul 20, 2010 at 3:37 AM, Itagaki Takahiro
<itagaki.takahiro@gmail.com> wrote:
> 2010/7/13 Alexander Korotkov <aekorotkov@gmail.com>:
>> Anyway I think that overhead is not ignorable. That's why I have splited
>> levenshtein_internal into levenshtein_internal and levenshtein_internal_mb,
>> and levenshtein_less_equal_internal into levenshtein_less_equal_internal and
>> levenshtein_less_equal_internal_mb.
>
> Thank you for good measurement! Then, it's reasonable to have multiple
> implementations. It also has documentation. I'll change status of the
> patch to "Ready for Committer".
>
> The patch is good enough except argument types for some functions.
> For example:
>  - char* vs. const char*
>  - text* vs. const char* + length
> I hope committers would check whether there are better types for them.

This patch still needs some work.  It includes a bunch of stylistic
changes that aren't relevant to the purpose of the patch.  There's no
reason that I can see to change the existing levenshtein_internal
function to take text arguments instead of char *, or to change !m to
m == 0 in existing code, or to change the whitespace in the comments
of that function.  All of those need to be reverted before we can
consider committing this.

There is a huge amount of duplicated code here.  I think it makes
sense to have the multibyte version of the function be separate, but
perhaps we can merge the less-than-or-equal to bits  into the main
code, so that we only have two copies instead of four.  Perhaps we
can't just add a max_d argument max_distance to levenshtein_internal;
and if this value is >=0 then it represents the max allowable
distance, but if it is <0 then there is no limit.  Sure, that might
slow down the existing code a bit, but it might not be significant.
I'd at least like to see some numbers showing that it is significant
before we go to this much trouble.

The code doesn't follow the project coding style.  Braces must be
uncuddled.  Comment paragraphs will be reflowed unless they begin and
end with ------.  Function definitions should have the type
declaration on one line and the function name at the start of the
next.

Freeing memory with pfree is likely a waste of time; is there any
reason not to just rely on the memory context reset, as the original
coding did?

I think we might need to remove the acknowledgments section from this
code.  If everyone who touches this code adds their name, we're
quickly going to have a mess.  If we're not going to remove the
acknowledgments section, then please add my name, too, because I've
already patched this code once...

I'm going to set this back to "Waiting on Author".

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise Postgres Company

On Wed, Jul 21, 2010 at 7:40 AM, Alexander Korotkov
<aekorotkov@gmail.com> wrote:
> On Wed, Jul 21, 2010 at 5:54 AM, Robert Haas <robertmhaas@gmail.com> wrote:
>> This patch still needs some work.  It includes a bunch of stylistic
>> changes that aren't relevant to the purpose of the patch.  There's no
>> reason that I can see to change the existing levenshtein_internal
>> function to take text arguments instead of char *, or to change !m to
>> m == 0 in existing code, or to change the whitespace in the comments
>> of that function.  All of those need to be reverted before we can
>> consider committing this.
>
> I changed arguments of function from char * to text * in order to avoid
> text_to_cstring call.

*scratches head*  Aren't you just moving the same call to a different place?

> Same benefit can be achived by replacing char * with
> char * and length.
> I changed !m to m == 0 because Itagaki asked me to make it conforming coding
> style. Do you think there is no reason to fix coding style in existing
> code?

Yeah, we usually try to avoid changing that sort of thing in existing
code, unless there's a very good reason.

>> There is a huge amount of duplicated code here.  I think it makes
>> sense to have the multibyte version of the function be separate, but
>> perhaps we can merge the less-than-or-equal to bits  into the main
>> code, so that we only have two copies instead of four.  Perhaps we
>> can't just add a max_d argument max_distance to levenshtein_internal;
>> and if this value is >=0 then it represents the max allowable
>> distance, but if it is <0 then there is no limit.  Sure, that might
>> slow down the existing code a bit, but it might not be significant.
>> I'd at least like to see some numbers showing that it is significant
>> before we go to this much trouble.
>
> In these case we should add many checks of max_d in levenshtein_internal
> function which make code more complex.

When you say "many" checks, how many?

> Actually, we can merge all four functions into one function. But such
> function will have many checks about multibyte encoding and max_d. So, I see
> four cases here:
> 1) one function with checks for multibyte encoding and max_d
> 2) two functions with checks for multibyte encoding
> 3) two functions with checks for max_d
> 4) four separate functions
> If you prefer case number 3 you should argue your position little more.

I'm somewhat convinced that separating the multibyte case out has a
performance benefit both by intuition and because you posted some
numbers, but I haven't seen any argument for separating out the other
case, so I'm asking if you've checked and whether there is an effect
and whether it's significant.  The default is always to try to avoid
maintaining multiple copies of substantially identical code, due to
the danger that a future patch might fail to update all of them and
thus introduce a bug.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise Postgres Company

Excerpts from Robert Haas's message of mié jul 21 14:25:47 -0400 2010:
> On Wed, Jul 21, 2010 at 7:40 AM, Alexander Korotkov
> <aekorotkov@gmail.com> wrote:
> > On Wed, Jul 21, 2010 at 5:54 AM, Robert Haas <robertmhaas@gmail.com> wrote:

> > Same benefit can be achived by replacing char * with
> > char * and length.
> > I changed !m to m == 0 because Itagaki asked me to make it conforming coding
> > style. Do you think there is no reason to fix coding style in existing
> > code?
> 
> Yeah, we usually try to avoid changing that sort of thing in existing
> code, unless there's a very good reason.

I think fixing a stylistic issue in code that's being edited for other
purposes is fine, and a good idea going forward.  We wouldn't commit a
patch that would *only* fix those, because that would cause a problem
for backpatches for no benefit, but if the patch touches something else,
then a backpatch of another patch is going to need manual intervention
anyway.

On Wed, Jul 21, 2010 at 2:47 PM, Alexander Korotkov
<aekorotkov@gmail.com> wrote:
> On Wed, Jul 21, 2010 at 10:25 PM, Robert Haas <robertmhaas@gmail.com> wrote:
>>
>> *scratches head*  Aren't you just moving the same call to a different
>> place?
>
> So, where you can find this different place? :) In this patch
> null-terminated strings are not used at all.

I can't.  You win.  :-)

Actually, I wonder if there's enough performance improvement there
that we might think about extracting that part of the patch and apply
it separately.  Then we could continue trying to figure out what to do
with the rest.  Sometimes it's simpler to deal with one change at a
time.

> I tested it with american-english dictionary with 98569 words.
>
> test=# select sum(levenshtein(word, 'qwerqwerqwer')) from words;
>    sum
> ---------
>  1074376
> (1 row)
>
> Time: 131,435 ms
> test=# select sum(levenshtein_less_equal(word, 'qwerqwerqwer',100)) from
> words;
>    sum
> ---------
>  1074376
> (1 row)
>
> Time: 221,078 ms
> test=# select sum(levenshtein_less_equal(word, 'qwerqwerqwer',-1)) from
> words;
>    sum
> ---------
>  1074376
> (1 row)
>
> Time: 254,819 ms
>
> The function with negative value of max_d didn't become faster than with
> just big value of max_d.

Ah, I see.  That's pretty compelling, I guess.  Although it still
seems like a lot of code...

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise Postgres Company

On Thu, Jul 22, 2010 at 3:21 AM, Alexander Korotkov
<aekorotkov@gmail.com> wrote:
> On Thu, Jul 22, 2010 at 1:59 AM, Robert Haas <robertmhaas@gmail.com> wrote:
>>
>> Ah, I see.  That's pretty compelling, I guess.  Although it still
>> seems like a lot of code...
>
> I think there is a way to merge single-byte and multi-byte versions of
> functions without loss in performance using macros and includes (like in
> 'backend/utils/adt/like.c'). Do you think it is acceptable in this case?

I'm not sure.  I'd like to get a second opinion from someone else on
which way to go with this, but unfortunately 2 or 3 of the main
committers are on vacation at the moment.

Does anyone else have an opinion on what to do about this?

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise Postgres Company

Such version with macros and includes can look like this:<br /><br />#ifdef MULTIBYTE <br />#define NEXT_X (x+=
char_lens[i-1])<br/>#define NEXT_Y (y+= y_char_len)<br />#define CMP (char_cmp(x, char_lens[i-1], y, y_char_len))<br
/>#else<br/> #define NEXT_X (x++)<br />#define NEXT_Y (y++)<br />#define CMP (*x == *y)<br />#endif<br /><br />static
int<br/>levenshtein_internal(text *s, text *t, int ins_c, int del_c, int sub_c)<br />{<br />    int            m,<br
/>               n,<br />                 d;<br />    int           *prev;<br />    int           *curr;<br />   
int           i,<br />                j;<br />    const char *x;<br />    const char *y;<br />#ifdef MULTIBYTE <br
/>   int           *char_lens;<br />     int        y_char_len;<br />#endif<br /><br />    /*<br />     * We should
calculatenumber of characters for multibyte encodings<br />     */<br />    m = pg_mbstrlen_with_len(VARDATA_ANY(s),
VARSIZE_ANY_EXHDR(s));<br/>    n = pg_mbstrlen_with_len(VARDATA_ANY(t), VARSIZE_ANY_EXHDR(t));<br /><br />    /*<br
/>    * We can transform an empty s into t with n insertions, or a non-empty t<br />     * into an empty s with m
deletions.<br/>     */<br />    if (m == 0)<br />        return n * ins_c;<br />    if (n == 0)<br />        return m *
del_c;<br/><br />    /*<br />     * For security concerns, restrict excessive CPU+RAM usage. (This<br />     *
implementationuses O(m) memory and has O(mn) complexity.)<br />     */<br />    if (m > MAX_LEVENSHTEIN_STRLEN ||<br
/>       n > MAX_LEVENSHTEIN_STRLEN)<br />         ereport(ERROR,<br />               
(errcode(ERRCODE_INVALID_PARAMETER_VALUE),<br/>                 errmsg("argument exceeds the maximum length of %d
bytes",<br/>                        MAX_LEVENSHTEIN_STRLEN)));<br /><br />    /* One more cell for initialization
columnand row. */<br />    ++m;<br />    ++n;<br /><br />    /*<br />     * Instead of building an (m+1)x(n+1) array,
we'lluse two different<br />     * arrays of size m+1 for storing accumulated values. At each step one<br />      *
representsthe "previous" row and one is the "current" row of the<br />     * notional large array.<br />     * For
multibyteencoding we'll also store array of lengths of<br />     * characters of first string in order to avoid great
numberof<br />       * pg_mblen calls.<br />     */<br />#ifdef MULTIBYTE <br />    prev = (int *) palloc(3 * m *
sizeof(int));<br/>    curr = prev + m;<br />    char_lens = prev + 2 * m;<br />    for (i = 0, x = VARDATA_ANY(s); i
<m - 1; i++)<br />     {<br />        char_lens[i] = pg_mblen(x);<br />        x += char_lens[i];<br />    }<br
/>   char_lens[i] = 0;<br />#else<br />    prev = (int *) palloc(2 * m * sizeof(int));<br />    curr = prev + m;<br
/>#endif<br/><br />    /* Initialize the "previous" row to 0..cols */<br />     for (i = 0; i < m; i++)<br />       
prev[i]= i * del_c;<br /><br />    /*<br />     * For multibyte encoding we should increase x and y pointers by the<br
/>    * results of pg_mblen function. Also we should use CHAR_CMP macros<br />      * for character comparison.<br
/>    */<br />    for (y = VARDATA_ANY(t), j = 1; j < n; NEXT_Y, j++)<br />    {<br />        int          
*temp;<br/>#ifdef MULTIBYTE <br />        y_char_len = pg_mblen(y);<br />#endif<br /><br />         curr[0] = j *
ins_c;<br/><br />        for (x = VARDATA_ANY(s), i = 1; i < m; NEXT_X, i++)<br />        {<br />            int   
       ins;<br />            int            del;<br />            int            sub;<br /><br />             ins =
prev[i]+ ins_c;<br />            del = curr[i - 1] + del_c;<br />            sub = prev[i - 1] + (CMP ? 0 : sub_c); <br
/>           curr[i] = Min(ins, del);<br />            curr[i] = Min(curr[i], sub);<br />        }<br /><br />       
temp= curr;<br />        curr = prev;<br />        prev = temp;<br />    }<br /><br />    d = prev[m - 1];<br /><br
/>   /*<br />     * Because the final value was swapped from the previous row to the<br />     * current row, that's
wherewe'll find it.<br />      */<br />    return d;<br />}<br /><br />What do you thing about it?<br /><br />----<br
/>Withbest regards,<br />Alexander Korotkov.<br /> 

Excerpts from Alexander Korotkov's message of jue jul 22 03:21:57 -0400 2010:
> On Thu, Jul 22, 2010 at 1:59 AM, Robert Haas <robertmhaas@gmail.com> wrote:
> 
> > Ah, I see.  That's pretty compelling, I guess.  Although it still
> > seems like a lot of code...
> >
> I think there is a way to merge single-byte and multi-byte versions of
> functions without loss in performance using macros and includes (like in
> 'backend/utils/adt/like.c'). Do you think it is acceptable in this case?

Using the trick of a single source file similar to like_match.c that
implements all the different behaviors, and include that file more than
once with different macro definitions, is probably a good idea.

On Wed, Jul 21, 2010 at 5:59 PM, Robert Haas <robertmhaas@gmail.com> wrote:
> On Wed, Jul 21, 2010 at 2:47 PM, Alexander Korotkov
> <aekorotkov@gmail.com> wrote:
>> On Wed, Jul 21, 2010 at 10:25 PM, Robert Haas <robertmhaas@gmail.com> wrote:
>>>
>>> *scratches head*  Aren't you just moving the same call to a different
>>> place?
>>
>> So, where you can find this different place? :) In this patch
>> null-terminated strings are not used at all.
>
> I can't.  You win.  :-)
>
> Actually, I wonder if there's enough performance improvement there
> that we might think about extracting that part of the patch and apply
> it separately.  Then we could continue trying to figure out what to do
> with the rest.  Sometimes it's simpler to deal with one change at a
> time.

I tested this today and the answer was a resounding yes.  I ran
sum(levenshtein(t, 'foo')) over a dictionary file with about 2 million
words and got a speedup of around 15% just by eliminating the
text_to_cstring() calls.  So I've committed that part of this patch.

I'll try to look at the rest of the patch when I get a chance, but I'm
wondering if it might make sense to split it into two patches -
specifically, one patch to handle multi-byte characters correctly, and
then a second patch for the less-than-or-equal-to functions.  I think
that might simplify reviewing a bit.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise Postgres Company

On Fri, Jul 30, 2010 at 1:14 PM, Alexander Korotkov
<aekorotkov@gmail.com> wrote:
> Ok, here is the patch for multi-byte characters.
> I changed arguments of levenshtein_internal function from text * to const
> char * and int. I think that it makes levenshtein_internal more reusable.
> For example, this function can be used for calculation distance of two
> fragments of strings without need of copying of these fragments.
> Actullay, I'm not fully satisfied with my solution in merging of single-byte
> and multi-byte versions of function. There are "ifdef"'s in body of function
> and non context-free macros. This is due to multi-byte needs to store
> characters lengths returned by pg_mblen when single-byte version doesn't
> need that. I tried multi-byte version without storing characters lengths,
> but in this case function is about 1.5 times slower (function needs to call
> pg_mblen n*m times).

I reviewed this code in a fair amount of detail today and ended up
rewriting it.  In general terms, it's best to avoid changing things
that are not relevant to the central purpose of the patch.  This patch
randomly adds a whole bunch of whitespace and removes a whole bunch of
comments which I find useful and do not want to see removed.  It took
me about an hour to reverse out all of those changes, which then let
me get down to the business of actually analyzing the code.   The
biggest problem I found is that, as coded, this is more than 50%
slower on UTF-8 databases, because the multi-byte path is really slow,
even if there are actually no multi-byte characters present.

The attached patch takes the approach of using a fast-path for just
the innermost loop when neither string contains any multi-byte
characters (regardless of whether or not the encoding allows
multi-byte characters).  It's still slower than CVS HEAD, but for
strings containing no multi-byte characters it's only marginally, if
at all, slower than previous releases, because 9.0 doesn't contain
your fix to avoid the extra string copy; and it's faster than your
implementation even when multi-byte characters ARE present.  It is
slightly slower on single-byte encoding databases (I tested
SQL_ASCII), but still faster than previous releases.  It's also quite
a bit less code duplication.

Please review and let me know your thoughts.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise Postgres Company

2010/8/2 Alexander Korotkov <aekorotkov@gmail.com>:
> On Mon, Aug 2, 2010 at 5:20 AM, Robert Haas <robertmhaas@gmail.com> wrote:
>> I reviewed this code in a fair amount of detail today and ended up
>> rewriting it.  In general terms, it's best to avoid changing things
>> that are not relevant to the central purpose of the patch.  This patch
>> randomly adds a whole bunch of whitespace and removes a whole bunch of
>> comments which I find useful and do not want to see removed.  It took
>> me about an hour to reverse out all of those changes, which then let
>> me get down to the business of actually analyzing the code.
> I'm sorry. This is my first patch, I will be more accurate next time. But, I
> think there is no unified opinion about some changes like replacement "!m"
> with "m==0".

Sure; if that were the only such change, I wouldn't have mentioned it.

> I think this line is not correct:
> "if (m != s_bytes && n != t_bytes)"

Good catch, fixed in the attached version.

>> The attached patch takes the approach of using a fast-path for just
>> the innermost loop when neither string contains any multi-byte
>> characters (regardless of whether or not the encoding allows
>> multi-byte characters).  It's still slower than CVS HEAD, but for
>> strings containing no multi-byte characters it's only marginally, if
>> at all, slower than previous releases, because 9.0 doesn't contain
>> your fix to avoid the extra string copy; and it's faster than your
>> implementation even when multi-byte characters ARE present.  It is
>> slightly slower on single-byte encoding databases (I tested
>> SQL_ASCII), but still faster than previous releases.  It's also quite
>> a bit less code duplication.
>
> Can I look at the test which shows that your implementation is faster than
> my when multi-byte characters are present? My tests show reverse. For
> example, with russian dictionary of openoffice:

Hmm, with the correction you mention above, I'm getting about the same
results with multi-byte characters (but faster with only single-byte
characters).  I did this:

CREATE TABLE words (a text not null primary key);
COPY words from '/usr/share/dict/words';

SELECT SUM(levenshtein(a, 'foo')) from words;
SELECT SUM(levenshtein(a, 'Urbański')) FROM words;
SELECT SUM(levenshtein(a, 'ańs')) FROM words;

With the updated patch attached below, these ran about 102 ms, 222 ms,
129 ms.  With your patch, I get about 134 ms, 222 ms, 130 ms.  Perhaps
this is because I only have multi-byte characters in one of the
inputs, not both.  I don't have a dictionary handy with multi-byte
words in it.  Can you send me a file?

> I think that the cause of slow down slowdown is memcmp function. This
> function is very fast for long parts of memory, but of few bytes inline
> function is faster, because compiler have more freedom for optimization.
> After replacing memcmp with inline function like following in your
> implementation:

Yeah, that does seem to be slightly better.  I've done a version of
this in the attached patch.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise Postgres Company

2010/8/2 Alexander Korotkov <aekorotkov@gmail.com>:
> The dump of the table with russian dictionary is in attachment.
>
> I use following tests:
> 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;
>
> With your last version of patch results are:
> 63ms 94ms 61ms 100ms 121ms 217ms.
>
> But I found some other optimization. With this condition:
> if (x[x_char_len-1] == y[y_char_len-1] && x_char_len == y_char_len &&
>     (x_char_len == 1 || char_same(x, y, x_char_len - 1)))
> results become:
> 58ms 96ms 63ms 102ms 107ms 171ms
>
> On single-byte characters results almost didn't change, but they come better
> with multi-byte characters. Generally, this improvement is because first
> bytes of different characters are frequently same (for example, almost all
> Cyrillic characters start from same byte, and I think that there is similar
> situation in other alphabets), but match of last bytes is just a
> coincidence.

Hey, that's really cool.  It helps a lot here, too:

My previous patch, with your 5 test cases:
Time: 100.556 ms
Time: 205.254 ms
Time: 127.070 ms
Time: 77.734 ms
Time: 90.345 ms
Time: 166.954 ms

Your original patch, same 5 test cases:
Time: 131.489 ms
Time: 215.048 ms
Time: 125.471 ms
Time: 80.068 ms
Time: 87.110 ms
Time: 166.918 ms

My patch, with your proposed change to compare the last character
first, same 5 test cases:
Time: 96.489 ms
Time: 201.497 ms
Time: 121.876 ms
Time: 75.005 ms
Time: 80.219 ms
Time: 142.844 ms

Updated patch attached.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise Postgres Company

On Mon, Aug 2, 2010 at 5:07 PM, Alexander Korotkov <aekorotkov@gmail.com> wrote:
> Now I think patch is as good as can be. :)

OK, committed.

> I'm going to prepare less-or-equal function in same manner as this patch.

Sounds good.  Since we're now more than half-way through this
CommitFest and this patch has undergone quite a bit of change from
what we started out with, I'd like to ask that you submit the new
patch for the next CommitFest, to begin September 15th.

https://commitfest.postgresql.org/action/commitfest_view/open

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise Postgres Company

Now I think patch is as good as can be. :) <br />I'm going to prepare less-or-equal function in same manner as this
patch.<br/><br />----<br />With best regards,<br />Alexander Korotkov.  

Here is the patch which adds levenshtein_less_equal function. I'm going to add it to current commitfest.

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 /> 

2010/8/28 Alexander Korotkov <aekorotkov@gmail.com>:
> Now test for levenshtein_less_equal performance.

Nice results.  I'll try to find time to look at this.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise Postgres Company