Is there any indexing technique available I can use when joining tables
with a regular expression pattern in pgsql?

I know one method for indexing strings that will be matched with regular
expression patterns, and that is using so called k-gram indexes.
Indexing the string "kjartan" with k-gram index where k = 3 would
create "kja", "jar", "art", "rta", "tan" as an index. Ofcourse it is hard to
decide the size of k and I'm sure in many cases mulitple k values might
be needed, depending on the situation.

I have not done any major survey of available techniques, but I was
hoping I could get some pointers here.

I assume pgsql always uses nested loop join when joining relations which are
joined with regular expression pattern?
-- 
Kjartan ï¿½sï¿½ï¿½rsson
http://www.kjarri.net 
Tel: +46 (0)730 556705



Sun, 7 Apr 2002 12:09:36 +0200
=?ISO-8859-1?B?S2phcnRhbiDBc/7zcnNzb24=?= <a98kjaas@student.his.se>
Indexing and regular expressions
On Sun, 7 Apr 2002, [ISO-8859-1] Kjartan О©╫sО©╫О©╫rsson wrote:

> Is there any indexing technique available I can use when joining tables
> with a regular expression pattern in pgsql?
>
> I know one method for indexing strings that will be matched with regular
> expression patterns, and that is using so called k-gram indexes.
> Indexing the string "kjartan" with k-gram index where k = 3 would
> create "kja", "jar", "art", "rta", "tan" as an index. Ofcourse it is hard to

Usually, k-grams technique is used to match patterns with errors and
3-grams produce "__k", "_kj", "kja", "jar", "art", "rta", "ta_", "a__"
where leading and trailing spaces are used to compensate 'boundary' effect.

But I dont' quite understand your question. Are you looking for fuzzy match ?
If so, take a look on contrib modules.

> decide the size of k and I'm sure in many cases mulitple k values might
> be needed, depending on the situation.
>
> I have not done any major survey of available techniques, but I was
> hoping I could get some pointers here.
>
> I assume pgsql always uses nested loop join when joining relations which are
> joined with regular expression pattern?
>

	Regards,
		Oleg
_____________________________________________________________
Oleg Bartunov, sci.researcher, hostmaster of AstroNet,
Sternberg Astronomical Institute, Moscow University (Russia)
Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
phone: +007(095)939-16-83, +007(095)939-23-83


Sun, 7 Apr 2002 13:54:27 +0300 (GMT)
Oleg Bartunov <oleg@sai.msu.su>
Re: Indexing and regular expressions
Thank you for your reply.

No, I am not looking for a fuzzy match. I am simply wondering if there
are some methods available that can speed up joining of tables when
the join is done with a regular expression operator (one table
contains regular expression patterns, and the other strings that
should be matched against the pattern).

If no indexes are used, a full table scan of the string table is
needed if we want to select all strings that matches a given pattern.

My question is if there are any indexing methods available that can
be used to prone the search space in the string table when using
the regular expression operator.

I hope I made myself more clear now. Best regards,
Kjartan


Sunday, April 7, 2002, 12:54:27 PM, you wrote:

> On Sun, 7 Apr 2002, [ISO-8859-1] Kjartan О©╫sО©╫О©╫rsson wrote:

>> Is there any indexing technique available I can use when joining tables
>> with a regular expression pattern in pgsql?
>>
>> I know one method for indexing strings that will be matched with regular
>> expression patterns, and that is using so called k-gram indexes.
>> Indexing the string "kjartan" with k-gram index where k = 3 would
>> create "kja", "jar", "art", "rta", "tan" as an index. Ofcourse it is hard to

> Usually, k-grams technique is used to match patterns with errors and
> 3-grams produce "__k", "_kj", "kja", "jar", "art", "rta", "ta_", "a__"
> where leading and trailing spaces are used to compensate 'boundary' effect.

> But I dont' quite understand your question. Are you looking for fuzzy match ?
> If so, take a look on contrib modules.

>> decide the size of k and I'm sure in many cases mulitple k values might
>> be needed, depending on the situation.
>>
>> I have not done any major survey of available techniques, but I was
>> hoping I could get some pointers here.
>>
>> I assume pgsql always uses nested loop join when joining relations which are
>> joined with regular expression pattern?
>>

>         Regards,
>                 Oleg
> _____________________________________________________________
> Oleg Bartunov, sci.researcher, hostmaster of AstroNet,
> Sternberg Astronomical Institute, Moscow University (Russia)
> Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
> phone: +007(095)939-16-83, +007(095)939-23-83


> ---------------------------(end of broadcast)---------------------------
> TIP 1: subscribe and unsubscribe commands go to majordomo@postgresql.org



Sun, 7 Apr 2002 13:49:08 +0200
=?koi8-r?B?S2phcnRhbiDic8DVcnNzb24=?= <a98kjaas@student.his.se>
Re: Indexing and regular expressions
On Sun, 7 Apr 2002 13:49:08 +0200
"Kjartan " <a98kjaas@student.his.se> wrote:
> Thank you for your reply.
> 
> No, I am not looking for a fuzzy match. I am simply wondering if there
> are some methods available that can speed up joining of tables when
> the join is done with a regular expression operator (one table
> contains regular expression patterns, and the other strings that
> should be matched against the pattern).
> 
> If no indexes are used, a full table scan of the string table is
> needed if we want to select all strings that matches a given pattern.

If the pattern is arbitrary, I'm not sure that any indexing technique
will be able to significantly improve performance (or at least, I'd
be *very* interested to see such a technique).

If you're storing the regular expressions in another table, you
could also store the pre-compiled patterns and use those for a
seqscan, but that won't net you a large improvement, particularly
if your set of patterns is much smaller than your set of strings
to match against (in which case the time to compile the pattern
becomes insignificant).

If your regular expressions contain common sub-elements (e.g.
many of them include "match string beginning with xxx" or whatever),
you could perhaps use indexes to optimize those sub-elements,
and then run the rest of the pattern on the tuples found by the
index. But if your patterns are truly arbitrary, this will be
unlikely to help.

Therefore, the answer is no AFAICT -- regular expressions are too
flexible to allow for optimization in advance.

Cheers,

Neil

-- 
Neil Conway <neilconway@rogers.com>
PGP Key ID: DB3C29FC

Sun, 7 Apr 2002 15:08:44 -0400
Neil Conway <nconway@klamath.dyndns.org>
Re: Indexing and regular expressions