Horton

Thread

  1. Re: Patch: add conversion from pg_wchar to multibyte

    Erik Rijkers <er@xs4all.nl> — 2012-04-29T12:12:49Z

    Hi Alexander,


Perhaps I'm too early with these tests, but FWIW I reran my earlier test program against three
instances.  (the patches compiled fine, and make check was without problem).

-- 3 instances:
HEAD                 port 6542
trgm_regex           port 6547  HEAD + trgm-regexp patch (22 Nov 2011) [1]
trgm_regex_wchar2mb  port 6549  HEAD + trgm-regexp + wchar2mb patch (23 Apr 2012) [2]

[1] http://archives.postgresql.org/pgsql-hackers/2011-11/msg01297.php
[2] http://archives.postgresql.org/pgsql-hackers/2012-04/msg01095.php

-- table sizes:
  azjunk4  10^4 rows     1 MB
  azjunk5  10^5 rows    11 MB
  azjunk6  10^6 rows   112 MB
  azjunk7  10^7 rows  1116 MB

for table creation/structure, see:
[3] http://archives.postgresql.org/pgsql-hackers/2012-01/msg01094.php

Results for three instances with 4 repetitions per instance are attached.

Although the regexes I chose are somewhat arbitrary, it does show some of the good, the bad and
the ugly of the patch(es).  (Also: I've limited the tests to a range of 'workable' regexps, i.e.
avoiding unbounded regexps)

hth (and thanks, great work!),


Erik Rijkers

  2. Re: Patch: add conversion from pg_wchar to multibyte

    Robert Haas <robertmhaas@gmail.com> — 2012-04-30T18:07:26Z

    On Sun, Apr 29, 2012 at 8:12 AM, Erik Rijkers <er@xs4all.nl> wrote:
> Perhaps I'm too early with these tests, but FWIW I reran my earlier test program against three
> instances.  (the patches compiled fine, and make check was without problem).

These tests results seem to be more about the pg_trgm changes than the
patch actually on this thread, unless I'm missing something.  But the
executive summary seems to be that pg_trgm might need to be a bit
smarter about costing the trigram-based search, because when the
number of trigrams is really big, using the index is
counterproductive.  Hopefully that's not too hard to fix; the basic
approach seems quite promising.

(I haven't actually looked at the patch on this thread yet to
understand how it fits in; the above comments are about the pg_trgm
regex stuff.)

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

  3. Re: Patch: add conversion from pg_wchar to multibyte

    Kevin Grittner <kevin.grittner@wicourts.gov> — 2012-04-30T21:48:31Z

    Robert Haas <robertmhaas@gmail.com> wrote:
 
> Hopefully that's not too hard to fix; the basic approach seems
> quite promising.
 
After playing with trigram searches for name searches against copies
of production database with appropriate indexing, our shop has
chosen it as the new way to do name searches here.  It's really
nice.
 
My biggest complaint is related to setting the threshold for the %
operator.  It seems to me that there should be a GUC to control the
default, and that there should be a way to set the threshold for
each % operator in a query (if there is more than one).  The
function names which must be used on the connection before running
the queries don't give any clue that they are related to trigrams:
show_limit() and set_limit() are nearly useless for conveying the
semantics of what they do.
 
Even with those issues, trigram similarity searching is IMO one of
the top five coolest things about PostgreSQL and should be promoted
heavily.
 
-Kevin

  4. Re: Patch: add conversion from pg_wchar to multibyte

    Alexander Korotkov <aekorotkov@gmail.com> — 2012-05-01T21:45:57Z

    Hi Erik


On Sun, Apr 29, 2012 at 4:12 PM, Erik Rijkers <er@xs4all.nl> wrote:

> Perhaps I'm too early with these tests, but FWIW I reran my earlier test
> program against three
> instances.  (the patches compiled fine, and make check was without
> problem).
>
> -- 3 instances:
> HEAD                 port 6542
> trgm_regex           port 6547  HEAD + trgm-regexp patch (22 Nov 2011) [1]
> trgm_regex_wchar2mb  port 6549  HEAD + trgm-regexp + wchar2mb patch (23
> Apr 2012) [2]
>

Actually wchar2mb patch doesn't affect behaviour of trgm-regexp. It provide
correct way to do some work of encoding conversion which last published
version of trgm-regexp does internally. So "HEAD + trgm-regexp patch" and
"HEAD + trgm-regexp + wchar2mb patch" should behave similarly.


> [1] http://archives.postgresql.org/pgsql-hackers/2011-11/msg01297.php
> [2] http://archives.postgresql.org/pgsql-hackers/2012-04/msg01095.php
>
> -- table sizes:
>  azjunk4  10^4 rows     1 MB
>  azjunk5  10^5 rows    11 MB
>  azjunk6  10^6 rows   112 MB
>  azjunk7  10^7 rows  1116 MB
>
> for table creation/structure, see:
> [3] http://archives.postgresql.org/pgsql-hackers/2012-01/msg01094.php
>
> Results for three instances with 4 repetitions per instance are attached.
>
> Although the regexes I chose are somewhat arbitrary, it does show some of
> the good, the bad and
> the ugly of the patch(es).  (Also: I've limited the tests to a range of
> 'workable' regexps, i.e.
> avoiding unbounded regexps)
>

Thank you for testing!
Such synthetical tests are very valuable for finding corner cases of the
patch, bugs etc.
But also, it would be nice to do some tests on reallife datasets with
reallife regexps in order to see real benefit of this approach of indexing
and do some comparison with other approaches. May be you or somebody else
could obtain such datasets?

Also, I did some optimizations in algorithm. Automaton analysis stage
should become less CPU and memory consuming. I'll publish new version soon.

------
With best regards,
Alexander Korotkov.

  5. Re: Patch: add conversion from pg_wchar to multibyte

    Alexander Korotkov <aekorotkov@gmail.com> — 2012-05-01T22:02:23Z

    On Mon, Apr 30, 2012 at 10:07 PM, Robert Haas <robertmhaas@gmail.com> wrote:

> On Sun, Apr 29, 2012 at 8:12 AM, Erik Rijkers <er@xs4all.nl> wrote:
> > Perhaps I'm too early with these tests, but FWIW I reran my earlier test
> program against three
> > instances.  (the patches compiled fine, and make check was without
> problem).
>
> These tests results seem to be more about the pg_trgm changes than the
> patch actually on this thread, unless I'm missing something.  But the
> executive summary seems to be that pg_trgm might need to be a bit
> smarter about costing the trigram-based search, because when the
> number of trigrams is really big, using the index is
> counterproductive.  Hopefully that's not too hard to fix; the basic
> approach seems quite promising.


Right. When number of trigrams is big, it is slow to scan posting list of
all of them. The solution is this case is to exclude most frequent trigrams
from index scan. But, it require some kind of statistics of trigrams
frequencies which we don't have. We could estimate frequencies using some
hard-coded assumptions about natural languages. Or we could exclude
arbitrary trigrams. But I don't like both these ideas. This problem is also
relevant for LIKE/ILIKE search using trigram indexes.

Something similar could occur in tsearch when we search for "frequent_term
& rare_term". In some situations (depending on terms frequencies) it's
better to exclude  frequent_term from index scan and do recheck. We have
relevant statistics to do such decision, but it doesn't seem to be feasible
to get it using current GIN interface.

Probably you have some comments on idea of conversion from pg_wchar to
multibyte? Is it acceptable at all?

------
With best regards,
Alexander Korotkov.

  6. Re: Patch: add conversion from pg_wchar to multibyte

    Alexander Korotkov <aekorotkov@gmail.com> — 2012-05-01T22:08:30Z

    On Tue, May 1, 2012 at 1:48 AM, Kevin Grittner
<Kevin.Grittner@wicourts.gov>wrote:

> My biggest complaint is related to setting the threshold for the %
> operator.  It seems to me that there should be a GUC to control the
> default, and that there should be a way to set the threshold for
> each % operator in a query (if there is more than one).  The
> function names which must be used on the connection before running
> the queries don't give any clue that they are related to trigrams:
> show_limit() and set_limit() are nearly useless for conveying the
> semantics of what they do.
>

I think this problem can be avoided by introducing composite type
representing trigram similarity query. It could consists of a query text
and similarity threshold. This type would have similar purpose as tsquery
or query_int. It would make queries more heavy, but would allow to use
distinct similarity threshold in the same query.

------
With best regards,
Alexander Korotkov.

  7. Re: Patch: add conversion from pg_wchar to multibyte

    Robert Haas <robertmhaas@gmail.com> — 2012-05-02T12:50:04Z

    On Tue, May 1, 2012 at 6:02 PM, Alexander Korotkov <aekorotkov@gmail.com> wrote:
> Right. When number of trigrams is big, it is slow to scan posting list of
> all of them. The solution is this case is to exclude most frequent trigrams
> from index scan.  But, it require some kind of statistics of trigrams
> frequencies which we don't have. We could estimate frequencies using some
> hard-coded assumptions about natural languages. Or we could exclude
> arbitrary trigrams. But I don't like both these ideas. This problem is also
> relevant for LIKE/ILIKE search using trigram indexes.

I was thinking you could perhaps do it just based on the *number* of
trigrams, not necessarily their frequency.

> Probably you have some comments on idea of conversion from pg_wchar to
> multibyte? Is it acceptable at all?

Well, I'm not an expert on encodings, but it seems like a logical
extension of what we're doing right now, so I don't really see why
not.  I'm confused by the diff hunks in pg_mule2wchar_with_len,
though.  Presumably either the old code is right (in which case, don't
change it) or the new code is right (in which case, there's a bug fix
needed here that ought to be discussed and committed separately from
the rest of the patch).  Maybe I am missing something.

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

  8. Re: Patch: add conversion from pg_wchar to multibyte

    Alexander Korotkov <aekorotkov@gmail.com> — 2012-05-02T13:35:03Z

    On Wed, May 2, 2012 at 4:50 PM, Robert Haas <robertmhaas@gmail.com> wrote:

> On Tue, May 1, 2012 at 6:02 PM, Alexander Korotkov <aekorotkov@gmail.com>
> wrote:
> > Right. When number of trigrams is big, it is slow to scan posting list of
> > all of them. The solution is this case is to exclude most frequent
> trigrams
> > from index scan.  But, it require some kind of statistics of trigrams
> > frequencies which we don't have. We could estimate frequencies using some
> > hard-coded assumptions about natural languages. Or we could exclude
> > arbitrary trigrams. But I don't like both these ideas. This problem is
> also
> > relevant for LIKE/ILIKE search using trigram indexes.
>
> I was thinking you could perhaps do it just based on the *number* of
> trigrams, not necessarily their frequency.
>

Imagine we've two queries:
1) SELECT * FROM tbl WHERE col LIKE '%abcd%';
2) SELECT * FROM tbl WHERE col LIKE '%abcdefghijk%';

The first query require reading posting lists of trigrams "abc" and "bcd".
The second query require reading posting lists of trigrams "abc", "bcd",
"cde", "def", "efg", "fgh", "ghi", "hij" and "ijk".
We could decide to use index scan for first query and sequential scan for
second query because number of posting list to read is high. But it is
unreasonable because actually second query is narrower than the first one.
We can use same index scan for it, recheck will remove all false positives.
When number of trigrams is high we can just exclude some of them from index
scan. It would be better than just decide to do sequential scan. But the
question is what trigrams to exclude? Ideally we would leave most rare
trigrams to make index scan cheaper.


> > Probably you have some comments on idea of conversion from pg_wchar to
> > multibyte? Is it acceptable at all?
>
> Well, I'm not an expert on encodings, but it seems like a logical
> extension of what we're doing right now, so I don't really see why
> not.  I'm confused by the diff hunks in pg_mule2wchar_with_len,
> though.  Presumably either the old code is right (in which case, don't
> change it) or the new code is right (in which case, there's a bug fix
> needed here that ought to be discussed and committed separately from
> the rest of the patch).  Maybe I am missing something.


Unfortunately I didn't understand original logic of pg_mule2wchar_with_len.
I just did proposal about how it could be. I hope somebody more familiar
with this code would clarify this situation.

------
With best regards,
Alexander Korotkov.

  9. Re: Patch: add conversion from pg_wchar to multibyte

    Robert Haas <robertmhaas@gmail.com> — 2012-05-02T13:48:33Z

    On Wed, May 2, 2012 at 9:35 AM, Alexander Korotkov <aekorotkov@gmail.com> wrote:
>> I was thinking you could perhaps do it just based on the *number* of
>> trigrams, not necessarily their frequency.
>
> Imagine we've two queries:
> 1) SELECT * FROM tbl WHERE col LIKE '%abcd%';
> 2) SELECT * FROM tbl WHERE col LIKE '%abcdefghijk%';
>
> The first query require reading posting lists of trigrams "abc" and "bcd".
> The second query require reading posting lists of trigrams "abc", "bcd",
> "cde", "def", "efg", "fgh", "ghi", "hij" and "ijk".
> We could decide to use index scan for first query and sequential scan for
> second query because number of posting list to read is high. But it is
> unreasonable because actually second query is narrower than the first one.
> We can use same index scan for it, recheck will remove all false positives.
> When number of trigrams is high we can just exclude some of them from index
> scan. It would be better than just decide to do sequential scan. But the
> question is what trigrams to exclude? Ideally we would leave most rare
> trigrams to make index scan cheaper.

True.  I guess I was thinking more of the case where you've got
abc|def|ghi|jkl|mno|pqr|stu|vwx|yza|....  There's probably some point
at which it becomes silly to think about using the index.

>> > Probably you have some comments on idea of conversion from pg_wchar to
>> > multibyte? Is it acceptable at all?
>>
>> Well, I'm not an expert on encodings, but it seems like a logical
>> extension of what we're doing right now, so I don't really see why
>> not.  I'm confused by the diff hunks in pg_mule2wchar_with_len,
>> though.  Presumably either the old code is right (in which case, don't
>> change it) or the new code is right (in which case, there's a bug fix
>> needed here that ought to be discussed and committed separately from
>> the rest of the patch).  Maybe I am missing something.
>
> Unfortunately I didn't understand original logic of pg_mule2wchar_with_len.
> I just did proposal about how it could be. I hope somebody more familiar
> with this code would clarify this situation.

Well, do you think the current code is buggy, or not?

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

  10. Re: Patch: add conversion from pg_wchar to multibyte

    Alexander Korotkov <aekorotkov@gmail.com> — 2012-05-02T13:57:05Z

    On Wed, May 2, 2012 at 5:48 PM, Robert Haas <robertmhaas@gmail.com> wrote:

> On Wed, May 2, 2012 at 9:35 AM, Alexander Korotkov <aekorotkov@gmail.com>
> wrote:
>  > Imagine we've two queries:
> > 1) SELECT * FROM tbl WHERE col LIKE '%abcd%';
> > 2) SELECT * FROM tbl WHERE col LIKE '%abcdefghijk%';
> >
> > The first query require reading posting lists of trigrams "abc" and
> "bcd".
> > The second query require reading posting lists of trigrams "abc", "bcd",
> > "cde", "def", "efg", "fgh", "ghi", "hij" and "ijk".
> > We could decide to use index scan for first query and sequential scan for
> > second query because number of posting list to read is high. But it is
> > unreasonable because actually second query is narrower than the first
> one.
> > We can use same index scan for it, recheck will remove all false
> positives.
> > When number of trigrams is high we can just exclude some of them from
> index
> > scan. It would be better than just decide to do sequential scan. But the
> > question is what trigrams to exclude? Ideally we would leave most rare
> > trigrams to make index scan cheaper.
>
> True.  I guess I was thinking more of the case where you've got
> abc|def|ghi|jkl|mno|pqr|stu|vwx|yza|....  There's probably some point
> at which it becomes silly to think about using the index.


Yes, such situations are also possible.

 >> Well, I'm not an expert on encodings, but it seems like a logical
> >> extension of what we're doing right now, so I don't really see why
> >> not.  I'm confused by the diff hunks in pg_mule2wchar_with_len,
> >> though.  Presumably either the old code is right (in which case, don't
> >> change it) or the new code is right (in which case, there's a bug fix
> >> needed here that ought to be discussed and committed separately from
> >> the rest of the patch).  Maybe I am missing something.
> >
> > Unfortunately I didn't understand original logic
> of pg_mule2wchar_with_len.
> > I just did proposal about how it could be. I hope somebody more familiar
> > with this code would clarify this situation.
>
> Well, do you think the current code is buggy, or not?


Probably, but I'm not sure. The conversion seems lossy to me unless I'm
missing something about mule encoding.

------
With best regards,
Alexander Korotkov.