Thread: Partial match in GIN
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/pgdoc/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/
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
> 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/
"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!
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
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
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
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.
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
> 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/
http://www.sigaev.ru/misc/partial_match_gin-0.8.gz Reworked interface as it suggested by Gregory (http://archives.postgresql.org/pgsql-patches/2008-04/msg00199.php) and move check of index into expand_indexqual_opclause() as suggested by Heikki (http://archives.postgresql.org/pgsql-patches/2008-04/msg00200.php) http://www.sigaev.ru/misc/tsearch_prefix-0.7.gz Sync with current CVS and partial match GIN patch. Allow full scan index, so now GIN supports search with queries like '!foo'. Implemented via using empty string for prefix search. http://www.sigaev.ru/misc/wildspeed-0.11.tgz Sync with CVS changes and partial match GIN patch. Teach opclass to correct use of recheck feature. -- Teodor Sigaev E-mail: teodor@sigaev.ru WWW: http://www.sigaev.ru/
http://www.sigaev.ru/misc/partial_match_gin-0.9.gz Sync with CVS. -- Teodor Sigaev E-mail: teodor@sigaev.ru WWW: http://www.sigaev.ru/
Teodor Sigaev <teodor@sigaev.ru> writes: > http://www.sigaev.ru/misc/partial_match_gin-0.9.gz > Sync with CVS. Looking at this now. Wouldn't it be a good idea for comparePartial to get the strategy number of the operator? As you have it set up, I doubt that an opclass can support more than one partial-match operator. regards, tom lane
> Looking at this now. Wouldn't it be a good idea for comparePartial
> to get the strategy number of the operator? As you have it set up,
> I doubt that an opclass can support more than one partial-match
> operator.
It might be useful, although I don't see any usage of that right now. I'll add
this option.
--
Teodor Sigaev E-mail: teodor@sigaev.ru
WWW: http://www.sigaev.ru/
Teodor Sigaev <teodor@sigaev.ru> writes:
>> Looking at this now. Wouldn't it be a good idea for comparePartial
>> to get the strategy number of the operator? As you have it set up,
>> I doubt that an opclass can support more than one partial-match
>> operator.
> It might be useful, although I don't see any usage of that right now. I'll add
> this option.
Ping? I'd like to get this patch out of the way.
regards, tom lane
>> It might be useful, although I don't see any usage of that right now. I'll add >> this option. > Ping? I'd like to get this patch out of the way. I'm very sorry for long delay. http://www.sigaev.ru/misc/partial_match_gin-0.10.gz http://www.sigaev.ru/misc/tsearch_prefix-0.8.gz http://www.sigaev.ru/misc/wildspeed-0.12.tgz Changes: - Sync with CVS HEAD - add third option (StrategyNumber) for comparePartialFn. -- Teodor Sigaev E-mail: teodor@sigaev.ru WWW: http://www.sigaev.ru/
Teodor Sigaev <teodor@sigaev.ru> writes: > http://www.sigaev.ru/misc/partial_match_gin-0.10.gz > http://www.sigaev.ru/misc/tsearch_prefix-0.8.gz > http://www.sigaev.ru/misc/wildspeed-0.12.tgz There seems to be something broken here: it's acting like prefix search is on all the time, eg regression=# select 'supernova'::tsvector @@ 'super'::tsquery; ?column? ---------- t (1 row) regards, tom lane
> There seems to be something broken here: it's acting like prefix search > is on all the time, eg I'm in sackcloth and ashes... Fixed and extended regression tests. http://www.sigaev.ru/misc/tsearch_prefix-0.9.gz -- Teodor Sigaev E-mail: teodor@sigaev.ru WWW: http://www.sigaev.ru/
Teodor Sigaev <teodor@sigaev.ru> writes: > http://www.sigaev.ru/misc/partial_match_gin-0.10.gz > http://www.sigaev.ru/misc/tsearch_prefix-0.9.gz > http://www.sigaev.ru/misc/wildspeed-0.12.tgz I've applied the first two of these with minor editorialization (mostly fixing documentation). However, I'm having a hard time convincing myself that anyone will find wildspeed useful in its current form. I did a simple experiment using a table of titles of database papers: contrib_regression=# select count(*), avg(length(title)) from pub; count | avg --------+--------------------- 236984 | 64.7647520507713601 (1 row) This takes about 22MB on disk as a Postgres table. I was expecting the wildspeed index to be about 65 times as large, which is bad enough already, but actually it weighed in at 2165MB or nearly 100X bigger. Plus it took forever to build: 35 minutes on a fairly fast machine with maintenance_work_mem set to 512MB. In comparison, building a conventional full-text-search index (GIN tsvector) took about 22 seconds including constructing the tsvector column, and the tsvectors plus index take about 54MB. The relative search performance is about what you'd expect from the difference in index sizes, ie, wildspeed loses. So I'm thinking wildspeed really needs to be redesigned if it's to be anything but a toy. I can't see putting it into contrib in this form. One idea that I had was to break the given string into words (splitting at spaces or punctuation) and store the rotations of individual words instead of the whole string. (Actually, maybe you only need suffixes not rotations, ie for 'abcd' store 'abcd', 'bcd', 'cd', 'd'.) Then similarly break the LIKE pattern apart at words to create word-fragment search keys. In this scheme the operator would always(?) require rechecking since any part of the pattern involving punctuation wouldn't be checkable by the index. The advantage is that the index bloat factor is governed by the average word length not the average whole-string length. There are probably other approaches that would help, too. regards, tom lane
Wildspeed was designed as an example application of the GIN's partial match and as a useful extension for *short* strings. It's also good standalone demonstration of GIN API. We tried to stay away from full text search, parser, word delimiters and etc. From that point of view it might be useful contrib, but I agree we have to think better to let it more usable. Oleg On Fri, 16 May 2008, Tom Lane wrote: > Teodor Sigaev <teodor@sigaev.ru> writes: >> http://www.sigaev.ru/misc/partial_match_gin-0.10.gz >> http://www.sigaev.ru/misc/tsearch_prefix-0.9.gz >> http://www.sigaev.ru/misc/wildspeed-0.12.tgz > > I've applied the first two of these with minor editorialization (mostly > fixing documentation). However, I'm having a hard time convincing myself > that anyone will find wildspeed useful in its current form. I did a > simple experiment using a table of titles of database papers: > > contrib_regression=# select count(*), avg(length(title)) from pub; > count | avg > --------+--------------------- > 236984 | 64.7647520507713601 > (1 row) > > This takes about 22MB on disk as a Postgres table. I was expecting the > wildspeed index to be about 65 times as large, which is bad enough > already, but actually it weighed in at 2165MB or nearly 100X bigger. > Plus it took forever to build: 35 minutes on a fairly fast machine > with maintenance_work_mem set to 512MB. > > In comparison, building a conventional full-text-search index (GIN > tsvector) took about 22 seconds including constructing the tsvector > column, and the tsvectors plus index take about 54MB. The relative > search performance is about what you'd expect from the difference in > index sizes, ie, wildspeed loses. > > So I'm thinking wildspeed really needs to be redesigned if it's to be > anything but a toy. I can't see putting it into contrib in this form. > > One idea that I had was to break the given string into words (splitting > at spaces or punctuation) and store the rotations of individual words > instead of the whole string. (Actually, maybe you only need suffixes > not rotations, ie for 'abcd' store 'abcd', 'bcd', 'cd', 'd'.) Then > similarly break the LIKE pattern apart at words to create word-fragment > search keys. In this scheme the operator would always(?) require > rechecking since any part of the pattern involving punctuation wouldn't > be checkable by the index. The advantage is that the index bloat factor > is governed by the average word length not the average whole-string > length. > > There are probably other approaches that would help, too. > > regards, tom lane > Regards, Oleg _____________________________________________________________ Oleg Bartunov, Research Scientist, Head of AstroNet (www.astronet.ru), Sternberg Astronomical Institute, Moscow University, Russia Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/ phone: +007(495)939-16-83, +007(495)939-23-83