Implemented `simplify` for the `starts_with` function to convert it into a LIKE expression. by jatin510 · Pull Request #14119 · apache/datafusion

jatin510 · 2025-01-14T06:04:47Z

Implemented simplify for the starts_with function to convert it into a LIKE expression

Which issue does this PR close?

Rationale for this change

Using 'LIKE' expr for 'starts_with' to enable predicate pruning.

What changes are included in this PR?

Implemented simplify for the starts_with function to convert it into a LIKE expression, enabling predicate pruning optimization.

Are these changes tested?

Ues

Are there any user-facing changes?

No

…nto a LIKE expression, enabling predicate pruning optimization.

alamb

Thank you @jatin510 -- this looks great

Can you please add some tests for this?

Specifically, I think you can use an explain test in sqllogictests, something like the following. The EXPLAIN should show LIKE being used in the physical plan

> create table t(x varchar) as values ('foo'), ('bar');
0 row(s) fetched.
Elapsed 0.013 seconds.

> explain select starts_with(x, 'fo') from t;
+---------------+----------------------------------------------------------------------------+
| plan_type     | plan                                                                       |
+---------------+----------------------------------------------------------------------------+
| logical_plan  | Projection: starts_with(t.x, Utf8("fo"))                                   |
|               |   TableScan: t projection=[x]                                              |
| physical_plan | ProjectionExec: expr=[starts_with(x@0, fo) as starts_with(t.x,Utf8("fo"))] |
|               |   MemoryExec: partitions=1, partition_sizes=[1]                            |
|               |                                                                            |
+---------------+----------------------------------------------------------------------------+
2 row(s) fetched.
Elapsed 0.003 seconds.

alamb · 2025-01-15T15:23:51Z

datafusion/functions/src/string/starts_with.rs

+    ) -> Result<ExprSimplifyResult> {
+        if let Expr::Literal(ScalarValue::Utf8(Some(pattern))) = &args[1] {
+            // Convert starts_with (col, 'prefix') to col LIKE 'prefix%'
+            let like_pattern = format!("{}%", pattern);


I think we probably need to escape any % that appears in the pattern (or avoid doing this replacement when such a pattern exists)

alamb · 2025-01-16T20:23:15Z

Marking as draft as I think this PR is no longer waiting on feedback. Please mark it as ready for review when it is ready for another look

…ype. and updated the coresponding test

…with-expr

alamb

Thank you @jatin510 -- this looks really nice

cc @adriangb (this should support pruning on starts_with, though it might be good to add some tests for that explicitly)

I merged this PR up from main and added some more test coverage as I had it checked out and was messing with it

alamb · 2025-01-22T21:04:53Z

datafusion/sqllogictest/test_files/string/string_view.slt

 ----
 logical_plan
-01)Projection: starts_with(test.column1_utf8view, Utf8View("äöüß")) AS c1, starts_with(test.column1_utf8view, Utf8View("")) AS c2, starts_with(test.column1_utf8view, Utf8View(NULL)) AS c3, starts_with(Utf8View(NULL), test.column1_utf8view) AS c4
+01)Projection: test.column1_utf8view LIKE Utf8View("äöüß%") AS c1, CASE test.column1_utf8view IS NOT NULL WHEN Boolean(true) THEN Boolean(true) END AS c2, starts_with(test.column1_utf8view, Utf8View(NULL)) AS c3, starts_with(Utf8View(NULL), test.column1_utf8view) AS c4


this is actually pretty cool -- it figured out that STARTS_WITH(column1_utf8view, '') as c2, is true if column1_utf8view is NOT NULL

alamb · 2025-01-22T21:16:09Z

datafusion/functions/src/string/starts_with.rs

+        _info: &dyn SimplifyInfo,
+    ) -> Result<ExprSimplifyResult> {
+        if let Expr::Literal(scalar_value) = &args[1] {
+            // Convert starts_with(col, 'prefix') to col LIKE 'prefix%' with proper escaping


I double checked the escaping logic and I think this looks good to me.

alamb · 2025-01-22T21:30:33Z

This is really sweet. You an see it working to prune parquet files here:

> copy (values ('foo'), ('bar'), ('baz')) to '/tmp/foo.parquet' STORED AS parquet;
+-------+
| count |
+-------+
| 3     |
+-------+
1 row(s) fetched.
Elapsed 0.010 seconds.

> explain select * from '/tmp/foo.parquet' where starts_with(column1, 'f');
+---------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| plan_type     | plan                                                                                                                                                                                                                                                  |
+---------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| logical_plan  | Filter: /tmp/foo.parquet.column1 LIKE Utf8View("f%")                                                                                                                                                                                                  |
|               |   TableScan: /tmp/foo.parquet projection=[column1], partial_filters=[/tmp/foo.parquet.column1 LIKE Utf8View("f%")]                                                                                                                                    |
| physical_plan | CoalesceBatchesExec: target_batch_size=8192                                                                                                                                                                                                           |
|               |   FilterExec: column1@0 LIKE f%                                                                                                                                                                                                                       |
|               |     RepartitionExec: partitioning=RoundRobinBatch(16), input_partitions=1                                                                                                                                                                             |
|               |       ParquetExec: file_groups={1 group: [[tmp/foo.parquet]]}, projection=[column1], predicate=column1@0 LIKE f%, pruning_predicate=column1_null_count@2 != column1_row_count@3 AND column1_min@0 <= g AND f <= column1_max@1, required_guarantees=[] |
|               |                                                                                                                                                                                                                                                       |
+---------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
2 row(s) fetched.
Elapsed 0.019 seconds.

Specifically the predicate AND column1_min@0 <= g AND f <= column1_max@1 shows it has translated the like into a min/max range on column_1 🤯

I will also add a test to this PR demonstrating this too

alamb · 2025-01-22T21:35:17Z

datafusion/sqllogictest/test_files/parquet.slt

+01)CoalesceBatchesExec: target_batch_size=8192
+02)--FilterExec: column1@0 LIKE f%
+03)----RepartitionExec: partitioning=RoundRobinBatch(2), input_partitions=1
+04)------ParquetExec: file_groups={1 group: [[WORKSPACE_ROOT/datafusion/sqllogictest/test_files/scratch/parquet/foo.parquet]]}, projection=[column1], predicate=column1@0 LIKE f%, pruning_predicate=column1_null_count@2 != column1_row_count@3 AND column1_min@0 <= g AND f <= column1_max@1, required_guarantees=[]


this is so cool!

adriangb · 2025-01-23T00:23:57Z

This looks great!

jayzhan211 · 2025-02-21T14:54:53Z

I wonder if converting starts_with to like add overhead.

https://github.com/apache/arrow-rs/blob/a0c3186c55ac8ed3f6b8a15d1305548fd6305ebb/arrow-string/src/predicate.rs#L45-L60

The difference between starts_with and like is that like check string to find a suitable kernel for processing whereas starts_with directly checks for a prefix match.

While benchmarking is necessary to confirm the exact performance difference, converting starts_with to like is likely slower, though the impact may be negligible

jayzhan211 · 2025-02-21T15:06:05Z

The challenge at the moment is that PruningPredicate can't refer directly to the function implementations

I see. This might be the tradeoff

adriangb · 2025-02-21T15:08:44Z

Yes that makes sense, but presumably that should happen once per pattern not once per row and be quite fast, especially for the common case of a prefix search, so I'd guess it's negligible?

…ert it into a LIKE expression. (apache#14119)" This reverts commit 49f95af.

Implemented simplify for the starts_with function to convert it i…

a373693

…nto a LIKE expression, enabling predicate pruning optimization.

github-actions bot added the functions Changes to functions implementation label Jan 14, 2025

alamb reviewed Jan 15, 2025

View reviewed changes

alamb marked this pull request as draft January 16, 2025 20:23

jatin510 added 2 commits January 19, 2025 09:35

fix: escape special characters in starts_with to LIKE conversion

b4c1f37

updated simply function to handle utf8, largeutf8 and utf8view data t…

90b0cad

…ype. and updated the coresponding test

github-actions bot added the sqllogictest SQL Logic Tests (.slt) label Jan 19, 2025

jatin510 marked this pull request as ready for review January 19, 2025 16:09

jatin510 requested a review from alamb January 21, 2025 15:57

alamb added 2 commits January 22, 2025 16:19

Add some more tests

66dfac3

Merge remote-tracking branch 'apache/main' into feat/simplify-starts_…

4fa3f17

…with-expr

alamb approved these changes Jan 22, 2025

View reviewed changes

Add pruning test

5829d46

alamb reviewed Jan 22, 2025

View reviewed changes

alamb merged commit 49f95af into apache:main Jan 23, 2025
25 checks passed

alamb mentioned this pull request Feb 4, 2025

Feb 4, 2025: This week(s) in DataFusion #14491

Closed

pepijnve mentioned this pull request Dec 3, 2025

fix: escape underscores when simplifying starts_with #19077

Merged

avantgardnerio added a commit to coralogix/arrow-datafusion that referenced this pull request Jan 8, 2026

Revert "Implemented simplify for the starts_with function to conv…

d425a94

…ert it into a LIKE expression. (apache#14119)" This reverts commit 49f95af.

Comments

Conversation

jatin510 commented Jan 14, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Which issue does this PR close?

Rationale for this change

What changes are included in this PR?

Are these changes tested?

Are there any user-facing changes?

Uh oh!

alamb left a comment

Choose a reason for hiding this comment

Uh oh!

alamb Jan 15, 2025

Choose a reason for hiding this comment

Uh oh!

alamb commented Jan 16, 2025

Uh oh!

alamb left a comment

Choose a reason for hiding this comment

Uh oh!

alamb Jan 22, 2025

Choose a reason for hiding this comment

Uh oh!

alamb Jan 22, 2025

Choose a reason for hiding this comment

Uh oh!

alamb commented Jan 22, 2025

Uh oh!

alamb Jan 22, 2025

Choose a reason for hiding this comment

Uh oh!

adriangb commented Jan 23, 2025

Uh oh!

Uh oh!

jayzhan211 commented Feb 21, 2025

Uh oh!

jayzhan211 commented Feb 21, 2025

Uh oh!

adriangb commented Feb 21, 2025

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

jatin510 commented Jan 14, 2025 •

edited

Loading