Re: text_position worst case runtime

Mark Dilger <pgsql(at)markdilger(dot)com> writes:
> The function
> static int32 text_position(text *t1, text *t2, int matchnum)
> defined in src/backend/utils/adt/varlena.c uses repeated calls to
> strncmp (or pg_wchar_strncmp) to find the location of the pattern in
> the text. The worst case runtime for such an approach is O(n*m) where
> n and m are the lengths of the pattern and text. The best case would
> be O(n), I guess, because it only takes n comparisons to find the
> pattern at the very start of the text. I'm not sure how to determine
> the average case runtime, because it depends what your data looks like
> on average.

I would think that the worst-case times would be fairly improbable.
I'm disinclined to push something as complicated as Boyer-Moore matching
into this function without considerable evidence that it's a performance
bottleneck for real applications.

The question that comes to mind for me is why we're not using simple
strncmp in all cases in that code. The conversion to pg_wchar format
looks expensive and unnecessary ...

regards, tom lane