Re: text_position worst case runtime

Tom Lane wrote:
> 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.

A common approach in biological data applications is to store nucleic and amino
acid sequences as text in a relational database. The smaller alphabet sizes and
the tendency for redundancy in these sequences increases the likelihood of a
performance problem. I have solved this problem by writing my own data types
with their own functions for sequence comparison and alignment, and I used
boyer-moore for some of that work. Whether the same technique should be used
for the text and varchar types was unclear to me, hence the question.

> 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 ...