Skip to content

Improve like/nlike performance #88

Closed

Description

@alamb

Note: migrated from original JIRA: https://issues.apache.org/jira/browse/ARROW-8681

Currently, the implementation of  like_utf8 and nlike_utf8 is based on regex, which is simple and readable, but poor at the performance.

 

I do some benchmark in [https://github.com/TennyZhuang/like-bench/] , in this repo, I compare three like algorithm.

like(includes partial_like): this is the first naive version, using the recursive approach, which will cause terrible performance on special attack input, such as a%a%a%a%a%a%a%a%b.

like_to_regex: which is almost the same as the current implementation in arrow.

like_optimize: the like problem is similar to glob in shell, so a perfect solution is proposed in [https://research.swtch.com/glob] . The code in the research is written golang but I translate it to rust.

 

In my benchmark result, the recursive solution can be ignored due to bad time complexity lower bound.

the regex solution will cost about 1000x time including regex compiling, and about 4x time without regex compiling then solution 3. And It seems that the code complexity of solution 3 is acceptable.

Everyone can reproduce the benchmark result using this repo with a few codes.

 

I have submitted a PR to TiKV to optimize the like performance ([https://github.com/tikv/tikv/pull/5866/files|https://github.com/tikv/tikv/pull/5866/files)], without UTF-8 support), and add collation support in [https://github.com/tikv/tikv/pull/6592], which can be simply port to data-fusion.

 

 

 

 

Activity

  1. alamb commented on Apr 26, 2021

    @alamb
    ContributorAuthor

    Comment from Andrew Lamb(alamb) @ 2021-04-26T12:30:42.598+0000:

    Migrated to github: https://github.com/apache/arrow-rs/issues/71
  2. alamb commented on Mar 10, 2023

    @alamb
    ContributorAuthor

    I am pretty sure the arrow-rs kernels now do the standard tricks like using substring matching with %% eetc -- see https://github.com/apache/arrow-rs/blob/61c4f12e84330db243789fc98375512d67628e57/arrow-string/src/like.rs#L303-L306 so I am closing this issue

  3. added a commit that references this issue on Oct 7, 2025
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions