SEO

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.

The fastest worst-case algorithmic solutions (boyer-moore and similar) have an
O(n+m) worst-case runtime.

In practice, the current iterative strncmp solution may be faster than the
boyer-moore solution for average data, because the data may not be constructed
in such a way as to trigger worst-case or nearly worst-case run times. The
current solution also has the advantage of not requiring a palloc of O(n) space
for the pattern preprocessing that boyer-moore requires.

My question is, would the core development team entertain the idea of changing
this function if I supplied the new code?

Thanks,

mark

Mark Dilger <pgsql@markdilger.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

---------------------------(end of broadcast)---------------------------
TIP 3: Have you checked our extensive FAQ?

http://www.postgresql.org/docs/faq

Tom Lane wrote:
> Mark Dilger <pgsql@markdilger.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 ...

On Thu, May 18, 2006 at 06:49:38PM -0700, Mark Dilger wrote:
> > 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.

Perhaps it would be best to add a seperate set of functions that use
boyer-moore, and reference them in appropriate places in the
documentation. Unless someone has a better idea on how we can find out
what people are actually doing in the field...
--
Jim C. Nasby, Sr. Engineering Consultant jnasby@pervasive.com
Pervasive Software http://pervasive.com work: 512-231-6117
vcard: http://jim.nasby.net/pervasive.vcf cell: 512-569-9461

---------------------------(end of broadcast)---------------------------
TIP 1: if posting/reading through Usenet, please send an appropriate
subscribe-nomail command to majordomo@postgresql.org so that your
message can get through to the mailing list cleanly

"Jim C. Nasby" <jnasby@pervasive.com> writes:
> Perhaps it would be best to add a seperate set of functions that use
> boyer-moore, and reference them in appropriate places in the
> documentation. Unless someone has a better idea on how we can find out
> what people are actually doing in the field...

You've obviously missed the point of my concern, which is code bloat.
A parallel set of functions incorporating B-M would make things worse
not better from that standpoint. (Unless you are proposing that someone
do it as a separate pgfoundry project; which'd be fine with me. I'm
just concerned about how much we buy into as core features.)

regards, tom lane

---------------------------(end of broadcast)---------------------------
TIP 4: Have you searched our list archives?

http://archives.postgresql.org

Tom Lane wrote:
> "Jim C. Nasby" <jnasby@pervasive.com> writes:
> > Perhaps it would be best to add a seperate set of functions that use
> > boyer-moore, and reference them in appropriate places in the
> > documentation. Unless someone has a better idea on how we can find out
> > what people are actually doing in the field...
>
> You've obviously missed the point of my concern, which is code bloat.
> A parallel set of functions incorporating B-M would make things worse
> not better from that standpoint. (Unless you are proposing that someone
> do it as a separate pgfoundry project; which'd be fine with me. I'm
> just concerned about how much we buy into as core features.)

So why not just replace our code with better algorithms? We could use
Shift-Or or Shift-And which AFAIK are even better than Boyer-Moore.

--
Alvaro Herrera http://www.CommandPrompt.com/
The PostgreSQL Company - Command Prompt, Inc.

---------------------------(end of broadcast)---------------------------
TIP 3: Have you checked our extensive FAQ?

http://www.postgresql.org/docs/faq

Alvaro Herrera <alvherre@commandprompt.com> writes:
> Tom Lane wrote:
>> You've obviously missed the point of my concern, which is code bloat.

> So why not just replace our code with better algorithms? We could use
> Shift-Or or Shift-And which AFAIK are even better than Boyer-Moore.

And how much code would those take? The bottom line here is that we
don't have a pile of complaints about the performance of text_position,
so it's difficult to justify making it much more complicated than it
is now.

regards, tom lane

---------------------------(end of broadcast)---------------------------
TIP 9: In versions below 8.0, the planner will ignore your desire to
choose an index scan if your joining column's datatypes do not
match

Tom Lane <tgl@sss.pgh.pa.us> writes:

> Alvaro Herrera <alvherre@commandprompt.com> writes:
> > Tom Lane wrote:
> >> You've obviously missed the point of my concern, which is code bloat.
>
> > So why not just replace our code with better algorithms? We could use
> > Shift-Or or Shift-And which AFAIK are even better than Boyer-Moore.
>
> And how much code would those take? The bottom line here is that we
> don't have a pile of complaints about the performance of text_position,
> so it's difficult to justify making it much more complicated than it
> is now.

Even Boyer-Moore, while conceptually tricky isn't actually all that much code.

It seems somewhat contrary to the Postgres design philosophy to assume that
all strings are small.

Other databases have two different string data types, one that has a small
length limit (often only 255 bytes or so) and another that has all kinds of
awkward restrictions on how it can be used. Postgres allows text to contain
gigabytes of data and lets you use all the normal string functions on it.

It seems like having those string functions assuming the strings are small
compromises that design choice.

--
greg


---------------------------(end of broadcast)---------------------------
TIP 9: In versions below 8.0, the planner will ignore your desire to
choose an index scan if your joining column's datatypes do not
match

Greg Stark <gsstark@mit.edu> writes:
> Tom Lane <tgl@sss.pgh.pa.us> writes:
>> And how much code would those take? The bottom line here is that we
>> don't have a pile of complaints about the performance of text_position,
>> so it's difficult to justify making it much more complicated than it
>> is now.

> It seems somewhat contrary to the Postgres design philosophy to assume that
> all strings are small.

That is a straw-man argument. If we try to optimize every single
function in the system to the Nth degree, we'll end up with a system
that is unmaintainable (and likely unusably buggy as well). We've got
to set limits on the amount of complexity we're willing to accept in
the core code.

Note that I have not said "you can't put Boyer-Moore into core".
What I've said is that the case to justify doing that hasn't been made.
And handwaving about "design philosophy" isn't the kind of case I'm
looking for --- common applications in which it makes a real performance
difference are what I'm looking for.

At this point we haven't even been shown any evidence that text_position
itself is what to optimize if you need to do searches in large text
strings. It seems entirely likely to me that the TOAST mechanisms would
be the bottleneck, instead. And one should also consider other approaches
entirely, like indexes (tsearch2 anyone?).

regards, tom lane

---------------------------(end of broadcast)---------------------------
TIP 6: explain analyze is your friend

Ühel kenal päeval, R, 2006-05-19 kell 11:20, kirjutas Jim C. Nasby:
> On Thu, May 18, 2006 at 06:49:38PM -0700, Mark Dilger wrote:
> > > 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.
>
> Perhaps it would be best to add a seperate set of functions that use
> boyer-moore, and reference them in appropriate places in the
> documentation. Unless someone has a better idea on how we can find out
> what people are actually doing in the field...

I guess our regex implementation already uses boyer-moore or similar.
Why not just expose the match position of substring('text' in 'regex')
using some function, called match_position(int searched_text, int
regex, int matchnum) ?

--
----------------
Hannu Krosing
Database Architect
Skype Technologies OÜ
Akadeemia tee 21 F, Tallinn, 12618, Estonia

Skype me: callto:hkrosing
Get Skype for free: http://www.skype.com




---------------------------(end of broadcast)---------------------------
TIP 5: don't forget to increase your free space map settings