Re: TODO item: Implement Boyer-Moore searching in LIKE queries

On Mon, Aug 1, 2016 at 1:19 PM, Karan Sikka <karanssikka(at)gmail(dot)com> wrote:
> Following the patch to implement strpos with Boyer-Moore-Horspool,
> it was proposed we bring BMH to LIKE as well.
>
> Original thread:
> https://www.postgresql.org/message-id/flat/27645(dot)1220635769%40sss(dot)pgh(dot)pa(dot)us#27645(dot)1220635769(at)sss(dot)pgh(dot)pa(dot)us
>
> I'm a first time hacker and I found this task on the TODO list. It seemed
> interesting and isolated enough. But after looking at the code in
> like_match.c, it's clearly a non-trivial task.
>
> How desirable is this feature? To begin answering that question,
> I did some initial benchmarking with an English text corpus to find how much
> faster BMH (Boyer-Moore-Horspool) would be compared to LIKE, and the results
> were as follows: BMH can be up to 20% faster than LIKE, but for short
> substrings, it's roughly comparable or slower.
>
> Here are the results visualized:
>
> http://ctrl-c.club/~ksikka/pg/like-strpos-short-1469975400.png
> http://ctrl-c.club/~ksikka/pg/like-strpos-long-1469975400.png

Based on these results, this looks to me like a pretty unexciting
thing upon which to spend time.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company