Re: 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(at)sai(dot)msu(dot)su, http://www.sai.msu.su/~megera/
phone: +007(095)939-16-83, +007(095)939-23-83