Apache Arrow project uses regular expression matching to implement the LIKE
predicate by translating SQL pattern into a regular expression pattern:
While this approach works it has issues:
replace
function always allocates a new string, even ifpat
contains neither%
nor_
leading to wasted memory and allocation overheadeach
replace
invocation results in a full scan of thepat
resulting in unnecessary repeated work
It's a fairly common problem, so unsurprisingly it has a generic solution - function call fusion. Thanks to referential transparency this optimization has been available for Haskell developers for a long time. For example, map
fusion transforms a composition of map
s
is transformed into a map
of compositions:
which is more efficient since we iterate over input list and produce the output list only once.
So what does it mean for the original problem with SQL pattern translation? To compare the efficiency, we'll fuse repeated replace
invocations in the original implementation
into a single function
It's not the most efficient implementation but is sufficient to deliver significantly better performance for cases when there are and there are not any matches. Benchmarks
show almost 3X improvement for the case without matches and ~25% speed up for the case with matches even for a fairly short input strings, foobarbazz
and foo%bar_bazz
:
Until your compiler supports fuse optimization, it's an important and useful technique for improving performance and efficiency.