Re: phrase search

I have attached a patch for phrase search with respect to the cvs head.
Basically it takes a a phrase (text) and a TSVector. It checks if the
relative positions of lexeme in the phrase are same as in their
positions in TSVector.

If the configuration for text search is "simple", then this will produce
exact phrase search. Otherwise the stopwords in a phrase will be ignored
and the words in a phrase will only be matched with the stemmed lexeme.

For my application I am using this as a separate shared object. I do not
know how to expose this function from the core. Can someone explain how
to do this?

I saw this discussion on phrase search and I am not sure what other
functionality is required.

http://archives.postgresql.org/pgsql-general/2008-02/msg01170.php

-Sushant.

> I have attached a patch for phrase search with respect to the cvs head.
> Basically it takes a a phrase (text) and a TSVector. It checks if the
> relative positions of lexeme in the phrase are same as in their
> positions in TSVector.

Ideally, phrase search should be implemented as new operator in tsquery, say #
with optional distance. So, tsquery 'foo #2 bar' means: find all texts where
'bar' is place no far than two word from 'foo'. The complexity is about complex
boolean expressions ( 'foo #1 ( bar1 & bar2 )' ) and about several languages as
norwegian or german. German language has combining words, like a footboolbar -
and they have several variants of splitting, so result of to_tsquery('foo #
footboolbar') will be a 'foo # ( ( football & bar ) | ( foot & ball & bar ) )'
where variants are connected with OR operation.

Of course, phrase search should be able to use indexes.
>
> If the configuration for text search is "simple", then this will produce
> exact phrase search. Otherwise the stopwords in a phrase will be ignored
> and the words in a phrase will only be matched with the stemmed lexeme.

Your solution can't be used as is, because user should use tsquery too to use an
index:

column @@ to_tsquery('phrase search') AND is_phrase_present('phrase search',
column)

First clause will be used for index scan and it will fast search a candidates.

> For my application I am using this as a separate shared object. I do not
> know how to expose this function from the core. Can someone explain how
> to do this?

Look at contrib/ directory in pgsql's source code - make a contrib module from
your patch. As an example, look at adminpack module - it's rather simple.

Comments of your code:
1)
+#ifdef PG_MODULE_MAGIC
+PG_MODULE_MAGIC;
+#endif

That isn't needed for compiled-in in core files, it's only needed for modules.

2)
use only /**/ comments, do not use a // (C++ style) comments
--
Teodor Sigaev E-mail: teodor(at)sigaev(dot)ru
WWW: http://www.sigaev.ru/

On Mon, 2008-06-02 at 19:39 +0400, Teodor Sigaev wrote:
>
> > I have attached a patch for phrase search with respect to the cvs head.
> > Basically it takes a a phrase (text) and a TSVector. It checks if the
> > relative positions of lexeme in the phrase are same as in their
> > positions in TSVector.
>
> Ideally, phrase search should be implemented as new operator in tsquery, say #
> with optional distance. So, tsquery 'foo #2 bar' means: find all texts where
> 'bar' is place no far than two word from 'foo'. The complexity is about complex
> boolean expressions ( 'foo #1 ( bar1 & bar2 )' ) and about several languages as
> norwegian or german. German language has combining words, like a footboolbar -
> and they have several variants of splitting, so result of to_tsquery('foo #
> footboolbar') will be a 'foo # ( ( football & bar ) | ( foot & ball & bar ) )'
> where variants are connected with OR operation.

This is far more complicated than I thought.

> Of course, phrase search should be able to use indexes.

I can probably look into how to use index. Any pointers on this?

> >
> > If the configuration for text search is "simple", then this will produce
> > exact phrase search. Otherwise the stopwords in a phrase will be ignored
> > and the words in a phrase will only be matched with the stemmed lexeme.
>
> Your solution can't be used as is, because user should use tsquery too to use an
> index:
>
> column @@ to_tsquery('phrase search') AND is_phrase_present('phrase search',
> column)
>
> First clause will be used for index scan and it will fast search a candidates.

Yes this is exactly how I am using in my application. Do you think this
will solve a lot of common case or we should try to get phrase search

1. Use index
2. Support arbitrary distance between lexemes
3. Support complex boolean queries

-Sushant.

>
> > For my application I am using this as a separate shared object. I do not
> > know how to expose this function from the core. Can someone explain how
> > to do this?
>
> Look at contrib/ directory in pgsql's source code - make a contrib module from
> your patch. As an example, look at adminpack module - it's rather simple.
>
> Comments of your code:
> 1)
> +#ifdef PG_MODULE_MAGIC
> +PG_MODULE_MAGIC;
> +#endif
>
> That isn't needed for compiled-in in core files, it's only needed for modules.
>
> 2)
> use only /**/ comments, do not use a // (C++ style) comments

> This is far more complicated than I thought.
>> Of course, phrase search should be able to use indexes.
> I can probably look into how to use index. Any pointers on this?

src/backend/utils/adt/tsginidx.c, if you invent operation # in tsquery then you
will have index support with minimal effort.
>
> Yes this is exactly how I am using in my application. Do you think this
> will solve a lot of common case or we should try to get phrase search

Yeah, it solves a lot of useful case, for simple use it's needed to invent
function similar to existsing plaitnto_tsquery, say phraseto_tsquery. It should
produce correct tsquery with described above operations.

--
Teodor Sigaev E-mail: teodor(at)sigaev(dot)ru
WWW: http://www.sigaev.ru/

On Tue, 2008-06-03 at 22:16 +0400, Teodor Sigaev wrote:
> > This is far more complicated than I thought.
> >> Of course, phrase search should be able to use indexes.
> > I can probably look into how to use index. Any pointers on this?
>
> src/backend/utils/adt/tsginidx.c, if you invent operation # in tsquery then you
> will have index support with minimal effort.
> >
> > Yes this is exactly how I am using in my application. Do you think this
> > will solve a lot of common case or we should try to get phrase search
>
> Yeah, it solves a lot of useful case, for simple use it's needed to invent
> function similar to existsing plaitnto_tsquery, say phraseto_tsquery. It should
> produce correct tsquery with described above operations.
>

I can add index support and support for arbitrary distance between
lexeme.

It appears to me that supporting arbitrary boolean expression will be
complicated. Can we pull out something from TSQuery?

-Sushant.

> I can add index support and support for arbitrary distance between
> lexeme.
> It appears to me that supporting arbitrary boolean expression will be
> complicated. Can we pull out something from TSQuery?

I don't very like an idea to have separated interface for phrase search. Your
patch may be a module and used by people who really wants to have a phrase search.

Introducing new operator in tsquery allows to use already existing
infrastructure of tsquery such as concatenations (&&, ||, !!), rewrite subsystem
etc. But new operation/types specially designed for phrase search makes needing
to make that work again.

--
Teodor Sigaev E-mail: teodor(at)sigaev(dot)ru
WWW: http://www.sigaev.ru/

I looked at query operators for tsquery and here are some of the new
query operators for position based queries. I am just proposing some
changes and the questions I have.

1. What is the meaning of such a query operator?

foo #5 bar -> true if the document has word "foo" followed by "bar" at
5th position.

foo #<5 bar -> true if document has word "foo" followed by "bar" with in
5 positions

foo #>5 bar -> true if document has word "foo" followed by "bar" after 5
positions

then some other ways it can be used are
!(foo #<5 bar) -> true if document never has any "foo" followed by bar
with in 5 positions.

etc .....

2. How to implement such query operators?

Should we modify QueryItem to include additional distance information or
is there any other way to accomplish it?

Is the following list sufficient to accomplish this?
a. Modify to_tsquery
b. Modify TS_execute in tsvector_op.c to check new operator

Is there anything needed in rewrite subsystem?

3. Are these valid uses of the operators and if yes what would they
mean?

foo #5 (bar & cup)

If no then should the operator be applied to only two QI_VAL's?

4. If the operator only applies to two query items can we create an
index such that (foo, bar)-> documents[min distance, max distance]
How difficult it is to implement an index like this?

Thanks,
-Sushant.

On Thu, 2008-06-05 at 19:37 +0400, Teodor Sigaev wrote:
> > I can add index support and support for arbitrary distance between
> > lexeme.
> > It appears to me that supporting arbitrary boolean expression will be
> > complicated. Can we pull out something from TSQuery?
>
> I don't very like an idea to have separated interface for phrase search. Your
> patch may be a module and used by people who really wants to have a phrase search.
>
> Introducing new operator in tsquery allows to use already existing
> infrastructure of tsquery such as concatenations (&&, ||, !!), rewrite subsystem
> etc. But new operation/types specially designed for phrase search makes needing
> to make that work again.
>

Sushant,

the problem of phrase search not in implementation, but in the theoretical
basis. tsearch is query rich and phrase search should support all query
operations, so we need algebra for query operations. We need more time
to investigate this problem, but just have no spare time for this.
If you are interesting, you might think in this direction.

Oleg

On Sat, 19 Jul 2008, Sushant Sinha wrote:

> I looked at query operators for tsquery and here are some of the new
> query operators for position based queries. I am just proposing some
> changes and the questions I have.
>
> 1. What is the meaning of such a query operator?
>
> foo #5 bar -> true if the document has word "foo" followed by "bar" at
> 5th position.
>
> foo #<5 bar -> true if document has word "foo" followed by "bar" with in
> 5 positions
>
> foo #>5 bar -> true if document has word "foo" followed by "bar" after 5
> positions
>
> then some other ways it can be used are
> !(foo #<5 bar) -> true if document never has any "foo" followed by bar
> with in 5 positions.
>
> etc .....
>
> 2. How to implement such query operators?
>
> Should we modify QueryItem to include additional distance information or
> is there any other way to accomplish it?
>
> Is the following list sufficient to accomplish this?
> a. Modify to_tsquery
> b. Modify TS_execute in tsvector_op.c to check new operator
>
> Is there anything needed in rewrite subsystem?
>
> 3. Are these valid uses of the operators and if yes what would they
> mean?
>
> foo #5 (bar & cup)
>
> If no then should the operator be applied to only two QI_VAL's?
>
> 4. If the operator only applies to two query items can we create an
> index such that (foo, bar)-> documents[min distance, max distance]
> How difficult it is to implement an index like this?
>
>
> Thanks,
> -Sushant.
>
> On Thu, 2008-06-05 at 19:37 +0400, Teodor Sigaev wrote:
>>> I can add index support and support for arbitrary distance between
>>> lexeme.
>>> It appears to me that supporting arbitrary boolean expression will be
>>> complicated. Can we pull out something from TSQuery?
>>
>> I don't very like an idea to have separated interface for phrase search. Your
>> patch may be a module and used by people who really wants to have a phrase search.
>>
>> Introducing new operator in tsquery allows to use already existing
>> infrastructure of tsquery such as concatenations (&&, ||, !!), rewrite subsystem
>> etc. But new operation/types specially designed for phrase search makes needing
>> to make that work again.
>>
>
>
>

Regards,
Oleg
_____________________________________________________________
Oleg Bartunov, Research Scientist, Head of AstroNet (www.astronet.ru),
Sternberg Astronomical Institute, Moscow University, Russia
Internet: oleg(at)sai(dot)msu(dot)su, http://www.sai.msu.su/~megera/
phone: +007(495)939-16-83, +007(495)939-23-83

>> 1. What is the meaning of such a query operator?
>>
>> foo #5 bar -> true if the document has word "foo" followed by "bar" at
>> 5th position.
>>
>> foo #<5 bar -> true if document has word "foo" followed by "bar" with in
>> 5 positions
>>
>> foo #>5 bar -> true if document has word "foo" followed by "bar" after 5
>> positions

Sounds good, but, may be it's an overkill.

>> etc .....
>>
>> 2. How to implement such query operators?
>>
>> Should we modify QueryItem to include additional distance information or
>> is there any other way to accomplish it?
>>
>> Is the following list sufficient to accomplish this?
>> a. Modify to_tsquery
>> b. Modify TS_execute in tsvector_op.c to check new operator
Exactly

>>
>> Is there anything needed in rewrite subsystem?
Yes, of course - rewrite system should support that operation.

>>
>> 3. Are these valid uses of the operators and if yes what would they
>> mean?
>>
>> foo #5 (bar & cup)
It must support! Because of lexize might return subtsquery. For example,
russian ispell can return several lexemes: "adfg" can become a 'adf | adfs |
ad', norwegian and german languages are more complicated: "abc" -> " (ab & c) |
(a & bc) | abc"

>> 4. If the operator only applies to two query items can we create an
>> index such that (foo, bar)-> documents[min distance, max distance]
>> How difficult it is to implement an index like this?
No, index should execute query 'foo & bar' and mark recheck flag to true to
execute 'foo #<5 bar' on original tsvector from table.

--
Teodor Sigaev E-mail: teodor(at)sigaev(dot)ru
WWW: http://www.sigaev.ru/