SEO

We (Oleg and me) would like to present patch implements partial match for GIN
index and two extensions which use this new feature. We hope that after short
review they will be committed to CVS.

This work was sponsored by EnterpriseDB.

http://www.sigaev.ru/misc/partial_match_gin-0.7.gz
Implements partial match for GIN. It extends interface of support function but
keeps backward compatibility. The basic idea is to find first greater or equal
value in index and scan sequentially until support function says stop. For each
matched entry all corresponding ItemPointers are collected in TIDBitmap
structure to effective merge ItemPointers from different entries. Patch
introduces following changes in interface:
- compare function has third (optional) argument, of boolean type, it points to
kind of compare: partial or exact match. If argument is equal to 'false',
function should produce comparing as usual, else function's result is
treated as:
= 0 - match
< 0 - doesn't match but continue scan
> 0 - stop scan
- extractQuery function has fourth (optional) argument of bool** type. Function
is responsible to allocate correct memory for that array with the same size
as returning array of searching entries. if extractQuery wishs to point
partial match for some entry it should set corresponding element of bool
array to true.

If function described above hasn't extra arguments then GIN will not be able to
use partial match.

http://www.sigaev.ru/misc/tsearch_prefix-0.6.gz
Implements prefix search. This was one of the most wanted feature of text
search. Lexeme to partial match should be labeled with asterisk:

select count(*) from apod where fti @@ 'star:*';
or even
select count(*) from apod where fti @@ to_tsquery('star:*');

Dictionary may set a normalized lexeme with flag (TSL_PREFIX) to point to its
prefix path.

Here there is a unclean issue: now tsquery has new flag to label prefix search
and cstring representation has backward compatibility, but external binary
hasn't it now. Now, extra byte is used for storage of this flag. In other hand,
there 4 unused bits in external binary representation (in byte stores weights of
lexeme), so it's possible to use one of them to store this flag. What are opinions?

http://www.sigaev.ru/misc/wildspeed-0.10.tgz
docs: http://mira.sai.msu.su/~megera/pgsql...wildspeed.html
http://www.sai.msu.su/~megera/wiki/wildspeed
In short, it's a contrib module that speeds up LIKE operation with any kind of
expression, like 'foo%bar' or '%foo%' or even '%foo%bar'. This module is based
on partial match patch of GIN.

NOTICE 1: current index support of LIKE believes that only BTree can speed up
LIKE and becomes confused with this module with error 'unexpected opfamily' in
prefix_quals(). For this reason, partial match patch adds small check before
calling expand_indexqual_opclause().

NOTICE 2: it seems to me, that similar technique could be implemented for
ordinary BTree to eliminate hack around LIKE support.

--
Teodor Sigaev E-mail: teodor@sigaev.ru
WWW: http://www.sigaev.ru/


--
Sent via pgsql-patches mailing list (pgsql-patches@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-patches

Teodor Sigaev wrote:
> For each
> matched entry all corresponding ItemPointers are collected in TIDBitmap
> structure to effective merge ItemPointers from different entries. Patch
> introduces following changes in interface:

Looking at the patch, you require that the TIDBitmap fits in work_mem in
non-lossy format. I don't think that's acceptable, it can easily exceed
work_mem if you search for some very common word. Failing to execute a
valid query is not good.

> Here there is a unclean issue: now tsquery has new flag to label prefix
> search and cstring representation has backward compatibility, but
> external binary hasn't it now. Now, extra byte is used for storage of
> this flag. In other hand, there 4 unused bits in external binary
> representation (in byte stores weights of lexeme), so it's possible to
> use one of them to store this flag. What are opinions?

I don't think the storage size of tsquery matters much, so whatever is
the best solution in terms of code readability etc.

> NOTICE 1: current index support of LIKE believes that only BTree can
> speed up LIKE and becomes confused with this module with error
> 'unexpected opfamily' in
> prefix_quals(). For this reason, partial match patch adds small check
> before
> calling expand_indexqual_opclause().

Hmm. match_special_index_operator() already checks that the index's
opfamily is pattern_ops, or text_ops with C-locale. Are you reusing the
same operator families for wildspeed? Doesn't it then also get confused
if you do a "WHERE textcol > 'foo'" query by hand?

> NOTICE 2: it seems to me, that similar technique could be implemented
> for ordinary BTree to eliminate hack around LIKE support.

Yep, if you created a b-tree index on the reversed key, that could be
used for LIKE '%foo' expressions. And if you had that in addition to a
regular b-tree index, you could use those two indexes together for any
LIKE expression. I wonder what the size and performance of that would be
like, in comparison to the proposed GIN solution?

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com

--
Sent via pgsql-patches mailing list (pgsql-patches@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-patches

> Looking at the patch, you require that the TIDBitmap fits in work_mem in
> non-lossy format. I don't think that's acceptable, it can easily exceed
> work_mem if you search for some very common word. Failing to execute a
> valid query is not good.
But way is better than nothing. In really, that way was chosen to have fast
merge of (potentially) hundreds of sorted lists of ItemPointers. Other ways is
much slower.

Some calculations: with 8Mb of mem_work TIDBimap in non-lossy mode can store at
least 200000 pages, which gives to us no less than 200000 tuples. For frequent
word, that number should multiplied to 10 or 100, because practically every
tuple will contain it. Practical limit to number of articles/document served by
one servers is about 10 millions.

There are no so many alternatives:
- collect all needed ItemPointers and sort then unique them.
- merge each posting list with already collected ones
- N-way merge, where N can be very big
- Rerun index scan with all possible combinations

All this ways will be much slower even for not very big collections.

> I don't think the storage size of tsquery matters much, so whatever is
> the best solution in terms of code readability etc.
That was about tsqueryesend/recv format? not a storage on disk. We don't require
compatibility of binary format of db's files, but I have some doubts about
binary dump.

>
> Hmm. match_special_index_operator() already checks that the index's
> opfamily is pattern_ops, or text_ops with C-locale. Are you reusing the
> same operator families for wildspeed? Doesn't it then also get confused
> if you do a "WHERE textcol > 'foo'" query by hand?
No, wildspeed use the same operator ~~
match_special_index_operator() isn't called at all: in
match_clause_to_indexcol() function is_indexable_operator() is called before
match_special_index_operator() and returns true.

expand_indexqual_opclause() sees that operation is a OID_TEXT_LIKE_OP and calls
prefix_quals() which fails because it wishes only several Btree opfamilies.


>
>> NOTICE 2: it seems to me, that similar technique could be implemented
>> for ordinary BTree to eliminate hack around LIKE support.
> LIKE expression. I wonder what the size and performance of that would be
> like, in comparison to the proposed GIN solution?

GIN speeds up '%foo%' too - which is impossible for btree. But I don't like a
hack around LIKE support in BTree. This support uses outflank ways missing
regular one.

I'm thinking about add new strategy to Btree and allow directly support of
prefix LIKE search. And BTree will scan index while compare method with option
returns true.

--
Teodor Sigaev E-mail: teodor@sigaev.ru
WWW: http://www.sigaev.ru/

--
Sent via pgsql-patches mailing list (pgsql-patches@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-patches

"Teodor Sigaev" <teodor@sigaev.ru> writes:

> - compare function has third (optional) argument, of boolean type, it points to
> kind of compare: partial or exact match. If argument is equal to 'false',
> function should produce comparing as usual, else function's result is
> treated as:
> = 0 - match
> < 0 - doesn't match but continue scan
> > 0 - stop scan

Perhaps a minor point but I think this would be cleaner as a separate opclass
function with a separate support number rather than overloading the comparison
function.

Then if the support function is there it supports that type of scan and if it
doesn't then it doesn't, rather than depending on a magic third argument to
completely change behaviour.

You can always share code using an internal function or if the behaviour is
identical just register the same function twice.

--
Gregory Stark
EnterpriseDB http://www.enterprisedb.com
Ask me about EnterpriseDB's Slony Replication support!

--
Sent via pgsql-patches mailing list (pgsql-patches@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-patches

Teodor Sigaev wrote:
>> Looking at the patch, you require that the TIDBitmap fits in work_mem
>> in non-lossy format. I don't think that's acceptable, it can easily
>> exceed work_mem if you search for some very common word. Failing to
>> execute a valid query is not good.
> But way is better than nothing. In really, that way was chosen to have
> fast merge of (potentially) hundreds of sorted lists of ItemPointers.
> Other ways is much slower.

How about forcing the use of a bitmap index scan, and modify the indexam
API so that GIN could a return a lossy bitmap, and let the bitmap heap
scan do the rechecking?

>> I don't think the storage size of tsquery matters much, so whatever is
>> the best solution in terms of code readability etc.
> That was about tsqueryesend/recv format? not a storage on disk. We don't
> require compatibility of binary format of db's files, but I have some
> doubts about binary dump.

We generally don't make any promises about cross-version compatibility
of binary dumps, though it would be nice not to break it if it's not too
much effort.

>> Hmm. match_special_index_operator() already checks that the index's
>> opfamily is pattern_ops, or text_ops with C-locale. Are you reusing
>> the same operator families for wildspeed? Doesn't it then also get
>> confused if you do a "WHERE textcol > 'foo'" query by hand?
> No, wildspeed use the same operator ~~
> match_special_index_operator() isn't called at all: in
> match_clause_to_indexcol() function is_indexable_operator() is called
> before match_special_index_operator() and returns true.
>
> expand_indexqual_opclause() sees that operation is a OID_TEXT_LIKE_OP
> and calls prefix_quals() which fails because it wishes only several
> Btree opfamilies.

Oh, I see. So this assumption mentioned in the comment there:

/*
* LIKE and regex operators are not members of any index opfamily,
* so if we find one in an indexqual list we can assume that it
* was accepted by match_special_index_operator().
*/

is no longer true with wildspeed. So we do need to check that in
expand_indexqual_opclause() then.

>>> NOTICE 2: it seems to me, that similar technique could be implemented
>>> for ordinary BTree to eliminate hack around LIKE support.
>> LIKE expression. I wonder what the size and performance of that would
>> be like, in comparison to the proposed GIN solution?
>
> GIN speeds up '%foo%' too - which is impossible for btree. But I don't
> like a hack around LIKE support in BTree. This support uses outflank
> ways missing regular one.

You could satisfy '%foo%' using a regular and a reverse B-tree index,
and a bitmap AND. Which is interestingly similar to the way you proposed
to use a TIDBitmap within GIN.

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com

--
Sent via pgsql-patches mailing list (pgsql-patches@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-patches

Heikki Linnakangas wrote:
> Teodor Sigaev wrote:

>> GIN speeds up '%foo%' too - which is impossible for btree. But I don't
>> like a hack around LIKE support in BTree. This support uses outflank
>> ways missing regular one.
>
> You could satisfy '%foo%' using a regular and a reverse B-tree index,
> and a bitmap AND. Which is interestingly similar to the way you proposed
> to use a TIDBitmap within GIN.

Huh, can you? I can see doing "col LIKE 'foo%' OR reverse(col) LIKE
reverse('%foo')" with two btree indexes, but not a true %foo% ...

--
Alvaro Herrera http://www.CommandPrompt.com/
PostgreSQL Replication, Consulting, Custom Development, 24x7 support

--
Sent via pgsql-patches mailing list (pgsql-patches@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-patches

Alvaro Herrera wrote:
> Heikki Linnakangas wrote:
>> Teodor Sigaev wrote:
>
>>> GIN speeds up '%foo%' too - which is impossible for btree. But I don't
>>> like a hack around LIKE support in BTree. This support uses outflank
>>> ways missing regular one.
>> You could satisfy '%foo%' using a regular and a reverse B-tree index,
>> and a bitmap AND. Which is interestingly similar to the way you proposed
>> to use a TIDBitmap within GIN.
>
> Huh, can you? I can see doing "col LIKE 'foo%' OR reverse(col) LIKE
> reverse('%foo')" with two btree indexes, but not a true %foo% ...

That should be AND, not OR..

Hmm. It is the same as far as I can see. Am I missing something?

You couldn't support more complex patterns directly, like 'foo%bar%foo',
but you could still split that into 'foo%' AND '%bar%' AND '%foo', and
recheck the matches against the original pattern

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com

--
Sent via pgsql-patches mailing list (pgsql-patches@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-patches

Heikki Linnakangas wrote:
> Alvaro Herrera wrote:
>> Heikki Linnakangas wrote:

>>> You could satisfy '%foo%' using a regular and a reverse B-tree index,
>>> and a bitmap AND. Which is interestingly similar to the way you
>>> proposed to use a TIDBitmap within GIN.
>>
>> Huh, can you? I can see doing "col LIKE 'foo%' OR reverse(col) LIKE
>> reverse('%foo')" with two btree indexes, but not a true %foo% ...
>
> That should be AND, not OR..
>
> Hmm. It is the same as far as I can see. Am I missing something?

Well, LIKE %foo% is supposed to match foo unanchored, but with a btree
(or two btrees) you can only get 'foo' anchored to either end of the
string (or both).

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

--
Sent via pgsql-patches mailing list (pgsql-patches@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-patches

Alvaro Herrera wrote:
> Well, LIKE %foo% is supposed to match foo unanchored, but with a btree
> (or two btrees) you can only get 'foo' anchored to either end of the
> string (or both).

Ah, true.

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com

--
Sent via pgsql-patches mailing list (pgsql-patches@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-patches

> How about forcing the use of a bitmap index scan, and modify the indexam
> API so that GIN could a return a lossy bitmap, and let the bitmap heap
> scan do the rechecking?

Partial match might be used only for one search entry from many. In sext search
example: 'a:* & qwertyuiop' - second lexeme has only a few matched tuples. But
GIN itself doesn't know about semantic meaning of operation and can not
distinguish following tsqueries:
'!a:* & qwertyuiop'
'!a:* & qwertyuiop'
'a:* & !qwertyuiop'

So, your suggestion is equivalent to mark all operation with RECHEK flag and
OR-ing all posting lists. That will be give a lot of false match and too slow.


>
>>> I don't think the storage size of tsquery matters much, so whatever
>>> is the best solution in terms of code readability etc.
>> That was about tsqueryesend/recv format? not a storage on disk. We
>> don't require compatibility of binary format of db's files, but I have
>> some doubts about binary dump.
>
> We generally don't make any promises about cross-version compatibility
> of binary dumps, though it would be nice not to break it if it's not too
> much effort.
>
>>> Hmm. match_special_index_operator() already checks that the index's
>>> opfamily is pattern_ops, or text_ops with C-locale. Are you reusing
>>> the same operator families for wildspeed? Doesn't it then also get
>>> confused if you do a "WHERE textcol > 'foo'" query by hand?
>> No, wildspeed use the same operator ~~
>> match_special_index_operator() isn't called at all: in
>> match_clause_to_indexcol() function is_indexable_operator() is called
>> before match_special_index_operator() and returns true.
>>
>> expand_indexqual_opclause() sees that operation is a OID_TEXT_LIKE_OP
>> and calls prefix_quals() which fails because it wishes only several
>> Btree opfamilies.
>
> Oh, I see. So this assumption mentioned in the comment there:
>
> /*
> * LIKE and regex operators are not members of any index opfamily,
> * so if we find one in an indexqual list we can assume that it
> * was accepted by match_special_index_operator().
> */
>
> is no longer true with wildspeed. So we do need to check that in
> expand_indexqual_opclause() then.
>
>>>> NOTICE 2: it seems to me, that similar technique could be
>>>> implemented for ordinary BTree to eliminate hack around LIKE support.
>>> LIKE expression. I wonder what the size and performance of that would
>>> be like, in comparison to the proposed GIN solution?
>>
>> GIN speeds up '%foo%' too - which is impossible for btree. But I don't
>> like a hack around LIKE support in BTree. This support uses outflank
>> ways missing regular one.
>
> You could satisfy '%foo%' using a regular and a reverse B-tree index,
> and a bitmap AND. Which is interestingly similar to the way you proposed
> to use a TIDBitmap within GIN.
>

--
Teodor Sigaev E-mail: teodor@sigaev.ru
WWW: http://www.sigaev.ru/

--
Sent via pgsql-patches mailing list (pgsql-patches@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-patches