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 scan0 - 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.tgzI'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