You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by GitBox <gi...@apache.org> on 2021/06/03 22:02:59 UTC
[GitHub] [arrow] lidavidm opened a new pull request #10448: ARROW-12949: [C++] Add starts_with and ends_with
lidavidm opened a new pull request #10448:
URL: https://github.com/apache/arrow/pull/10448
This adds a simple starts_with and ends_with.
Also, now match_like can optimize some patterns into prefix/suffix matches. This also fixes a bug (which I believe is also present in Apache Impala) where some LIKE patterns are mistakenly optimized into suffix or substring matches.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] cyb70289 commented on a change in pull request #10448: ARROW-12949: [C++] Add starts_with and ends_with
Posted by GitBox <gi...@apache.org>.
cyb70289 commented on a change in pull request #10448:
URL: https://github.com/apache/arrow/pull/10448#discussion_r645305540
##########
File path: cpp/src/arrow/compute/kernels/scalar_string.cc
##########
@@ -484,6 +484,42 @@ struct PlainSubstringMatcher {
bool Match(util::string_view current) const { return Find(current) >= 0; }
};
+struct PlainStartsWithMatcher {
+ const MatchSubstringOptions& options_;
+
+ explicit PlainStartsWithMatcher(const MatchSubstringOptions& options)
+ : options_(options) {}
+
+ static Result<std::unique_ptr<PlainStartsWithMatcher>> Make(
+ const MatchSubstringOptions& options) {
+ // Should be handled by partial template specialization below
Review comment:
Not sure what this comment means. Looks there's no template around.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] github-actions[bot] commented on pull request #10448: ARROW-12949: [C++] Add starts_with and ends_with
Posted by GitBox <gi...@apache.org>.
github-actions[bot] commented on pull request #10448:
URL: https://github.com/apache/arrow/pull/10448#issuecomment-854214913
https://issues.apache.org/jira/browse/ARROW-12949
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] lidavidm commented on a change in pull request #10448: ARROW-12949: [C++] Add starts_with and ends_with
Posted by GitBox <gi...@apache.org>.
lidavidm commented on a change in pull request #10448:
URL: https://github.com/apache/arrow/pull/10448#discussion_r646827535
##########
File path: cpp/src/arrow/compute/kernels/scalar_string.cc
##########
@@ -636,13 +728,15 @@ std::string MakeLikeRegex(const MatchSubstringOptions& options) {
}
// A LIKE pattern matching this regex can be translated into a substring search.
-static RE2 kLikePatternIsSubstringMatch("%+([^%_]*)%+");
+static RE2 kLikePatternIsSubstringMatch(R"(%+([^%_]*[^\\%_])?%+)");
+// A LIKE pattern matching this regex can be translated into a prefix search.
+static RE2 kLikePatternIsStartsWith(R"(([^%_]*[^\\%_])?%+)");
+// A LIKE pattern matching this regex can be translated into a suffix search.
+static RE2 kLikePatternIsEndsWith(R"(%+([^%_]*))");
Review comment:
I added a benchmark (the latest commit).
With RE2:
```
-----------------------------------------------------------------------------
Benchmark Time CPU Iterations UserCounters...
-----------------------------------------------------------------------------
MatchLike 24478428 ns 24474766 ns 29 bytes_per_second=647.127M/s items_per_second=42.8431M/s
MatchLikeSubstring 105684357 ns 105673666 ns 7 bytes_per_second=149.879M/s items_per_second=9.92277M/s
MatchLikePrefix 105720204 ns 105698786 ns 7 bytes_per_second=149.844M/s items_per_second=9.92042M/s
MatchLikeSuffix 105730852 ns 105712489 ns 7 bytes_per_second=149.824M/s items_per_second=9.91913M/s
```
With the optimization:
```
-----------------------------------------------------------------------------
Benchmark Time CPU Iterations UserCounters...
-----------------------------------------------------------------------------
MatchLike 24035525 ns 24035373 ns 31 bytes_per_second=658.958M/s items_per_second=43.6264M/s
MatchLikeSubstring 44747614 ns 44747029 ns 16 bytes_per_second=353.952M/s items_per_second=23.4334M/s
MatchLikePrefix 5927800 ns 5927691 ns 116 bytes_per_second=2.60929G/s items_per_second=176.895M/s
MatchLikeSuffix 5988512 ns 5988423 ns 118 bytes_per_second=2.58283G/s items_per_second=175.101M/s
```
This is actually a little surprising.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] lidavidm commented on a change in pull request #10448: ARROW-12949: [C++] Add starts_with and ends_with
Posted by GitBox <gi...@apache.org>.
lidavidm commented on a change in pull request #10448:
URL: https://github.com/apache/arrow/pull/10448#discussion_r646827535
##########
File path: cpp/src/arrow/compute/kernels/scalar_string.cc
##########
@@ -636,13 +728,15 @@ std::string MakeLikeRegex(const MatchSubstringOptions& options) {
}
// A LIKE pattern matching this regex can be translated into a substring search.
-static RE2 kLikePatternIsSubstringMatch("%+([^%_]*)%+");
+static RE2 kLikePatternIsSubstringMatch(R"(%+([^%_]*[^\\%_])?%+)");
+// A LIKE pattern matching this regex can be translated into a prefix search.
+static RE2 kLikePatternIsStartsWith(R"(([^%_]*[^\\%_])?%+)");
+// A LIKE pattern matching this regex can be translated into a suffix search.
+static RE2 kLikePatternIsEndsWith(R"(%+([^%_]*))");
Review comment:
I added a benchmark (the latest commit).
With RE2:
```
-----------------------------------------------------------------------------
Benchmark Time CPU Iterations UserCounters...
-----------------------------------------------------------------------------
MatchLike 24478428 ns 24474766 ns 29 bytes_per_second=647.127M/s items_per_second=42.8431M/s
MatchLikeSubstring 105684357 ns 105673666 ns 7 bytes_per_second=149.879M/s items_per_second=9.92277M/s
MatchLikePrefix 105720204 ns 105698786 ns 7 bytes_per_second=149.844M/s items_per_second=9.92042M/s
MatchLikeSuffix 105730852 ns 105712489 ns 7 bytes_per_second=149.824M/s items_per_second=9.91913M/s
```
With the optimization:
```
-----------------------------------------------------------------------------
Benchmark Time CPU Iterations UserCounters...
-----------------------------------------------------------------------------
MatchLike 24035525 ns 24035373 ns 31 bytes_per_second=658.958M/s items_per_second=43.6264M/s
MatchLikeSubstring 44747614 ns 44747029 ns 16 bytes_per_second=353.952M/s items_per_second=23.4334M/s
MatchLikePrefix 5927800 ns 5927691 ns 116 bytes_per_second=2.60929G/s items_per_second=176.895M/s
MatchLikeSuffix 5988512 ns 5988423 ns 118 bytes_per_second=2.58283G/s items_per_second=175.101M/s
```
This is actually a little surprising. I would have expected RE2 to do better here.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] cyb70289 commented on a change in pull request #10448: ARROW-12949: [C++] Add starts_with and ends_with
Posted by GitBox <gi...@apache.org>.
cyb70289 commented on a change in pull request #10448:
URL: https://github.com/apache/arrow/pull/10448#discussion_r645305540
##########
File path: cpp/src/arrow/compute/kernels/scalar_string.cc
##########
@@ -484,6 +484,42 @@ struct PlainSubstringMatcher {
bool Match(util::string_view current) const { return Find(current) >= 0; }
};
+struct PlainStartsWithMatcher {
+ const MatchSubstringOptions& options_;
+
+ explicit PlainStartsWithMatcher(const MatchSubstringOptions& options)
+ : options_(options) {}
+
+ static Result<std::unique_ptr<PlainStartsWithMatcher>> Make(
+ const MatchSubstringOptions& options) {
+ // Should be handled by partial template specialization below
Review comment:
Not sure what this comment means. Looks there's no template around.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] pitrou closed pull request #10448: ARROW-12949: [C++] Add starts_with and ends_with
Posted by GitBox <gi...@apache.org>.
pitrou closed pull request #10448:
URL: https://github.com/apache/arrow/pull/10448
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] github-actions[bot] commented on pull request #10448: ARROW-12949: [C++] Add starts_with and ends_with
Posted by GitBox <gi...@apache.org>.
github-actions[bot] commented on pull request #10448:
URL: https://github.com/apache/arrow/pull/10448#issuecomment-854214913
https://issues.apache.org/jira/browse/ARROW-12949
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] lidavidm commented on a change in pull request #10448: ARROW-12949: [C++] Add starts_with and ends_with
Posted by GitBox <gi...@apache.org>.
lidavidm commented on a change in pull request #10448:
URL: https://github.com/apache/arrow/pull/10448#discussion_r645542932
##########
File path: cpp/src/arrow/compute/kernels/scalar_string.cc
##########
@@ -484,6 +484,42 @@ struct PlainSubstringMatcher {
bool Match(util::string_view current) const { return Find(current) >= 0; }
};
+struct PlainStartsWithMatcher {
+ const MatchSubstringOptions& options_;
+
+ explicit PlainStartsWithMatcher(const MatchSubstringOptions& options)
+ : options_(options) {}
+
+ static Result<std::unique_ptr<PlainStartsWithMatcher>> Make(
+ const MatchSubstringOptions& options) {
+ // Should be handled by partial template specialization below
Review comment:
I mean L612-L653 below which are partial template specializations that convert a case-insensitive prefix/suffix match into an equivalent regex (to avoid having to do Unicode case folding ourselves): https://github.com/apache/arrow/pull/10448/files#diff-eb8300bc4dea7d1c46b2576b7dbd8e42b927ab7d42c031f4aecae892a72ee244R612-R653
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] pitrou commented on a change in pull request #10448: ARROW-12949: [C++] Add starts_with and ends_with
Posted by GitBox <gi...@apache.org>.
pitrou commented on a change in pull request #10448:
URL: https://github.com/apache/arrow/pull/10448#discussion_r647192569
##########
File path: cpp/src/arrow/compute/kernels/scalar_string.cc
##########
@@ -636,13 +728,15 @@ std::string MakeLikeRegex(const MatchSubstringOptions& options) {
}
// A LIKE pattern matching this regex can be translated into a substring search.
-static RE2 kLikePatternIsSubstringMatch("%+([^%_]*)%+");
+static RE2 kLikePatternIsSubstringMatch(R"(%+([^%_]*[^\\%_])?%+)");
+// A LIKE pattern matching this regex can be translated into a prefix search.
+static RE2 kLikePatternIsStartsWith(R"(([^%_]*[^\\%_])?%+)");
+// A LIKE pattern matching this regex can be translated into a suffix search.
+static RE2 kLikePatternIsEndsWith(R"(%+([^%_]*))");
Review comment:
Interesting, thank you.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] pitrou commented on a change in pull request #10448: ARROW-12949: [C++] Add starts_with and ends_with
Posted by GitBox <gi...@apache.org>.
pitrou commented on a change in pull request #10448:
URL: https://github.com/apache/arrow/pull/10448#discussion_r646740864
##########
File path: cpp/src/arrow/compute/kernels/scalar_string.cc
##########
@@ -573,13 +609,69 @@ struct MatchSubstring<Type, PlainSubstringMatcher> {
}
};
+template <typename Type>
+struct MatchSubstring<Type, PlainStartsWithMatcher> {
+ static Status Exec(KernelContext* ctx, const ExecBatch& batch, Datum* out) {
+ auto options = MatchSubstringState::Get(ctx);
+ if (options.ignore_case) {
+#ifdef ARROW_WITH_RE2
+ MatchSubstringOptions converted_options = options;
+ converted_options.pattern = "^" + RE2::QuoteMeta(options.pattern);
+ ARROW_ASSIGN_OR_RAISE(auto matcher, RegexSubstringMatcher::Make(converted_options));
+ return MatchSubstringImpl<Type, RegexSubstringMatcher>::Exec(ctx, batch, out,
+ matcher.get());
+#else
+ return Status::NotImplemented("ignore_case requires RE2");
+#endif
+ }
+ ARROW_ASSIGN_OR_RAISE(auto matcher, PlainStartsWithMatcher::Make(options));
+ return MatchSubstringImpl<Type, PlainStartsWithMatcher>::Exec(ctx, batch, out,
+ matcher.get());
+ }
+};
+
+template <typename Type>
+struct MatchSubstring<Type, PlainEndsWithMatcher> {
+ static Status Exec(KernelContext* ctx, const ExecBatch& batch, Datum* out) {
+ auto options = MatchSubstringState::Get(ctx);
+ if (options.ignore_case) {
+#ifdef ARROW_WITH_RE2
+ MatchSubstringOptions converted_options = options;
+ converted_options.pattern = RE2::QuoteMeta(options.pattern) + "$";
+ ARROW_ASSIGN_OR_RAISE(auto matcher, RegexSubstringMatcher::Make(converted_options));
+ return MatchSubstringImpl<Type, RegexSubstringMatcher>::Exec(ctx, batch, out,
+ matcher.get());
+#else
+ return Status::NotImplemented("ignore_case requires RE2");
+#endif
+ }
+ ARROW_ASSIGN_OR_RAISE(auto matcher, PlainEndsWithMatcher::Make(options));
+ return MatchSubstringImpl<Type, PlainEndsWithMatcher>::Exec(ctx, batch, out,
+ matcher.get());
+ }
+};
+
const FunctionDoc match_substring_doc(
"Match strings against literal pattern",
("For each string in `strings`, emit true iff it contains a given pattern.\n"
"Null inputs emit null. The pattern must be given in MatchSubstringOptions. "
"If ignore_case is set, only simple case folding is performed."),
{"strings"}, "MatchSubstringOptions");
+const FunctionDoc starts_with_doc(
+ "Check if strings start with a pattern",
Review comment:
"literal pattern" perhaps (to disambiguate with regex)?
##########
File path: cpp/src/arrow/compute/kernels/scalar_string.cc
##########
@@ -636,13 +728,15 @@ std::string MakeLikeRegex(const MatchSubstringOptions& options) {
}
// A LIKE pattern matching this regex can be translated into a substring search.
-static RE2 kLikePatternIsSubstringMatch("%+([^%_]*)%+");
+static RE2 kLikePatternIsSubstringMatch(R"(%+([^%_]*[^\\%_])?%+)");
+// A LIKE pattern matching this regex can be translated into a prefix search.
+static RE2 kLikePatternIsStartsWith(R"(([^%_]*[^\\%_])?%+)");
+// A LIKE pattern matching this regex can be translated into a suffix search.
+static RE2 kLikePatternIsEndsWith(R"(%+([^%_]*))");
Review comment:
Out of curiosity, did you try to benchmark with/without those optimizations? `re2` might be doing similar under the hood...
##########
File path: cpp/src/arrow/compute/kernels/scalar_string.cc
##########
@@ -484,6 +484,42 @@ struct PlainSubstringMatcher {
bool Match(util::string_view current) const { return Find(current) >= 0; }
};
+struct PlainStartsWithMatcher {
+ const MatchSubstringOptions& options_;
+
+ explicit PlainStartsWithMatcher(const MatchSubstringOptions& options)
+ : options_(options) {}
+
+ static Result<std::unique_ptr<PlainStartsWithMatcher>> Make(
+ const MatchSubstringOptions& options) {
+ // Should be handled by partial template specialization below
+ DCHECK(!options.ignore_case);
+ return ::arrow::internal::make_unique<PlainStartsWithMatcher>(options);
+ }
+
+ bool Match(util::string_view current) const {
+ return current.starts_with(options_.pattern);
+ }
+};
+
+struct PlainEndsWithMatcher {
+ const MatchSubstringOptions& options_;
+
+ explicit PlainEndsWithMatcher(const MatchSubstringOptions& options)
+ : options_(options) {}
+
+ static Result<std::unique_ptr<PlainEndsWithMatcher>> Make(
+ const MatchSubstringOptions& options) {
+ // Should be handled by partial template specialization below
+ DCHECK(!options.ignore_case);
+ return ::arrow::internal::make_unique<PlainEndsWithMatcher>(options);
+ }
+
+ bool Match(util::string_view current) const {
+ return current.ends_with(options_.pattern);
Review comment:
Same here.
##########
File path: cpp/src/arrow/compute/kernels/scalar_string.cc
##########
@@ -484,6 +484,42 @@ struct PlainSubstringMatcher {
bool Match(util::string_view current) const { return Find(current) >= 0; }
};
+struct PlainStartsWithMatcher {
+ const MatchSubstringOptions& options_;
+
+ explicit PlainStartsWithMatcher(const MatchSubstringOptions& options)
+ : options_(options) {}
+
+ static Result<std::unique_ptr<PlainStartsWithMatcher>> Make(
+ const MatchSubstringOptions& options) {
+ // Should be handled by partial template specialization below
+ DCHECK(!options.ignore_case);
+ return ::arrow::internal::make_unique<PlainStartsWithMatcher>(options);
+ }
+
+ bool Match(util::string_view current) const {
+ return current.starts_with(options_.pattern);
Review comment:
`starts_with` is C++20, so should probably use the expanded version to ease transition to C++17 :-)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org