You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@drill.apache.org by ppadma <gi...@git.apache.org> on 2017/08/16 17:05:16 UTC
[GitHub] drill pull request #907: DRILL-5697: Improve performance of filter operator ...
GitHub user ppadma opened a pull request:
https://github.com/apache/drill/pull/907
DRILL-5697: Improve performance of filter operator for pattern matching
Implement character by character matching for simple patterns and fallback to regex for more complicated patterns. See DRILL-5697 for more details.
You can merge this pull request into a Git repository by running:
$ git pull https://github.com/ppadma/drill DRILL-5697
Alternatively you can review and apply these changes as the patch at:
https://github.com/apache/drill/pull/907.patch
To close this pull request, make a commit to your master/trunk branch
with (at least) the following in the commit message:
This closes #907
----
commit f384475baea0ab05e84b3ac7b45118bb0b0ea5ce
Author: Padma Penumarthy <pp...@yahoo.com>
Date: 2017-08-07T22:11:00Z
DRILL-5697: Improve performance of filter operator for pattern matching
----
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] drill pull request #907: DRILL-5697: Improve performance of filter operator ...
Posted by paul-rogers <gi...@git.apache.org>.
Github user paul-rogers commented on a diff in the pull request:
https://github.com/apache/drill/pull/907#discussion_r134035089
--- Diff: exec/java-exec/src/main/java/org/apache/drill/exec/expr/fn/impl/RegexpUtil.java ---
@@ -96,20 +145,46 @@ public static String sqlToRegexLike(
|| (nextChar == '%')
|| (nextChar == escapeChar)) {
javaPattern.append(nextChar);
+ simplePattern.append(nextChar);
i++;
} else {
throw invalidEscapeSequence(sqlPattern, i);
}
} else if (c == '_') {
+ // if we find _, it is not simple pattern, we are looking for only %
+ notSimple = true;
javaPattern.append('.');
} else if (c == '%') {
+ if (i == 0) {
+ // % at the start could potentially be one of the simple cases i.e. ENDS_WITH.
+ endsWith = true;
+ } else if (i == (len-1)) {
+ // % at the end could potentially be one of the simple cases i.e. STARTS_WITH
+ startsWith = true;
+ } else {
+ // If we find % anywhere other than start or end, it is not a simple case.
+ notSimple = true;
+ }
javaPattern.append(".");
javaPattern.append('*');
} else {
javaPattern.append(c);
+ simplePattern.append(c);
}
}
- return javaPattern.toString();
+
+ if (!notSimple) {
--- End diff --
Yeah, the zillion-flags approach is too complex to follow. Really need a good-old state machine.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] drill pull request #907: DRILL-5697: Improve performance of filter operator ...
Posted by paul-rogers <gi...@git.apache.org>.
Github user paul-rogers commented on a diff in the pull request:
https://github.com/apache/drill/pull/907#discussion_r134032343
--- Diff: exec/java-exec/src/main/java/org/apache/drill/exec/expr/fn/impl/RegexpUtil.java ---
@@ -47,18 +47,55 @@
"[:alnum:]", "\\p{Alnum}"
};
+ // type of pattern string.
+ public enum sqlPatternType {
--- End diff --
Class name format: `SqlPatternType`
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] drill pull request #907: DRILL-5697: Improve performance of filter operator ...
Posted by kkhatua <gi...@git.apache.org>.
Github user kkhatua commented on a diff in the pull request:
https://github.com/apache/drill/pull/907#discussion_r133859807
--- Diff: exec/java-exec/src/main/java/org/apache/drill/exec/expr/fn/impl/RegexpUtil.java ---
@@ -96,20 +145,46 @@ public static String sqlToRegexLike(
|| (nextChar == '%')
|| (nextChar == escapeChar)) {
javaPattern.append(nextChar);
+ simplePattern.append(nextChar);
i++;
} else {
throw invalidEscapeSequence(sqlPattern, i);
}
} else if (c == '_') {
+ // if we find _, it is not simple pattern, we are looking for only %
+ notSimple = true;
javaPattern.append('.');
} else if (c == '%') {
+ if (i == 0) {
+ // % at the start could potentially be one of the simple cases i.e. ENDS_WITH.
+ endsWith = true;
+ } else if (i == (len-1)) {
+ // % at the end could potentially be one of the simple cases i.e. STARTS_WITH
+ startsWith = true;
+ } else {
+ // If we find % anywhere other than start or end, it is not a simple case.
--- End diff --
Consider ABC%XYZ.
It might be worthwhile to decide whether to leverage a pattern or fall back to Java's Regex util based on the number of occurrences of '%' as a criteria.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] drill issue #907: DRILL-5697: Improve performance of filter operator for pat...
Posted by ppadma <gi...@git.apache.org>.
Github user ppadma commented on the issue:
https://github.com/apache/drill/pull/907
@kkhatua Kunal, we can add more patterns later if we want. For now, let us get the most simple cases done first.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] drill pull request #907: DRILL-5697: Improve performance of filter operator ...
Posted by paul-rogers <gi...@git.apache.org>.
Github user paul-rogers commented on a diff in the pull request:
https://github.com/apache/drill/pull/907#discussion_r134035411
--- Diff: exec/java-exec/src/main/java/org/apache/drill/exec/expr/fn/impl/StringFunctions.java ---
@@ -57,22 +57,120 @@ private StringFunctions() {}
@Output BitHolder out;
@Workspace java.util.regex.Matcher matcher;
@Workspace org.apache.drill.exec.expr.fn.impl.CharSequenceWrapper charSequenceWrapper;
+ @Workspace org.apache.drill.exec.expr.fn.impl.RegexpUtil.sqlPatternInfo patternInfo;
@Override
public void setup() {
- matcher = java.util.regex.Pattern.compile(org.apache.drill.exec.expr.fn.impl.RegexpUtil.sqlToRegexLike( //
- org.apache.drill.exec.expr.fn.impl.StringFunctionHelpers.toStringFromUTF8(pattern.start, pattern.end, pattern.buffer))).matcher("");
+ patternInfo = org.apache.drill.exec.expr.fn.impl.RegexpUtil.sqlToRegexLike(
+ org.apache.drill.exec.expr.fn.impl.StringFunctionHelpers.toStringFromUTF8(pattern.start, pattern.end, pattern.buffer));
charSequenceWrapper = new org.apache.drill.exec.expr.fn.impl.CharSequenceWrapper();
- matcher.reset(charSequenceWrapper);
+
+ // Use java regex and compile pattern only if it is not a simple pattern.
+ if (patternInfo.getPatternType() == org.apache.drill.exec.expr.fn.impl.RegexpUtil.sqlPatternType.NOT_SIMPLE) {
--- End diff --
You have an enum to describe the cases, and a class to capture the info. That is the perfect place to encode the information about how to process. In particular, the pattern class should act as a factory for a pattern executor: will create an instance of the class needed to do the work. That will also allow this stuff to be unit tested without needing all of Drill.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] drill pull request #907: DRILL-5697: Improve performance of filter operator ...
Posted by paul-rogers <gi...@git.apache.org>.
Github user paul-rogers commented on a diff in the pull request:
https://github.com/apache/drill/pull/907#discussion_r134035728
--- Diff: exec/java-exec/src/main/java/org/apache/drill/exec/expr/fn/impl/StringFunctions.java ---
@@ -85,23 +183,118 @@ public void eval() {
@Output BitHolder out;
@Workspace java.util.regex.Matcher matcher;
@Workspace org.apache.drill.exec.expr.fn.impl.CharSequenceWrapper charSequenceWrapper;
+ @Workspace org.apache.drill.exec.expr.fn.impl.RegexpUtil.sqlPatternInfo patternInfo;
@Override
public void setup() {
- matcher = java.util.regex.Pattern.compile(org.apache.drill.exec.expr.fn.impl.RegexpUtil.sqlToRegexLike( //
+ patternInfo = org.apache.drill.exec.expr.fn.impl.RegexpUtil.sqlToRegexLike(
org.apache.drill.exec.expr.fn.impl.StringFunctionHelpers.toStringFromUTF8(pattern.start, pattern.end, pattern.buffer),
- org.apache.drill.exec.expr.fn.impl.StringFunctionHelpers.toStringFromUTF8(escape.start, escape.end, escape.buffer))).matcher("");
+ org.apache.drill.exec.expr.fn.impl.StringFunctionHelpers.toStringFromUTF8(escape.start, escape.end, escape.buffer));
charSequenceWrapper = new org.apache.drill.exec.expr.fn.impl.CharSequenceWrapper();
- matcher.reset(charSequenceWrapper);
+
+ // Use java regex and compile pattern only if it is not a simple pattern.
+ if (patternInfo.getPatternType() == org.apache.drill.exec.expr.fn.impl.RegexpUtil.sqlPatternType.NOT_SIMPLE) {
+ java.lang.String javaPatternString = patternInfo.getJavaPatternString();
+ matcher = java.util.regex.Pattern.compile(javaPatternString).matcher("");
+ matcher.reset(charSequenceWrapper);
+ }
}
@Override
public void eval() {
charSequenceWrapper.setBuffer(input.start, input.end, input.buffer);
// Reusing same charSequenceWrapper, no need to pass it in.
// This saves one method call since reset(CharSequence) calls reset()
- matcher.reset();
- out.value = matcher.matches()? 1:0;
+
+ // Not a simple case. Just use Java regex.
+ if (patternInfo.getPatternType() == org.apache.drill.exec.expr.fn.impl.RegexpUtil.sqlPatternType.NOT_SIMPLE) {
--- End diff --
We are doing a switch (actually, chain of ifs) per value. This is a tight inner loop. Far better to simply generate an instance of the proper class and call a single method to do the work.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] drill pull request #907: DRILL-5697: Improve performance of filter operator ...
Posted by paul-rogers <gi...@git.apache.org>.
Github user paul-rogers commented on a diff in the pull request:
https://github.com/apache/drill/pull/907#discussion_r134034498
--- Diff: exec/java-exec/src/main/java/org/apache/drill/exec/expr/fn/impl/RegexpUtil.java ---
@@ -76,12 +113,24 @@ public static String sqlToRegexLike(
/**
* Translates a SQL LIKE pattern to Java regex pattern.
*/
- public static String sqlToRegexLike(
+ public static sqlPatternInfo sqlToRegexLike(
String sqlPattern,
char escapeChar) {
int i;
final int len = sqlPattern.length();
final StringBuilder javaPattern = new StringBuilder(len + len);
+ final StringBuilder simplePattern = new StringBuilder(len);
+
+ // Figure out the pattern type and build simplePatternString
+ // as we are going through the sql pattern string
+ // to build java regex pattern string. This is better instead of using
+ // regex later for determining if a pattern is simple or not.
+ // Saves CPU cycles.
+ sqlPatternType patternType = sqlPatternType.NOT_SIMPLE;
+ boolean startsWith = false;
+ boolean endsWith = false;
+ boolean notSimple = false;
--- End diff --
Or, since your enum represents terminal states, create a new enum with internal states. CONST_ONLY, WILDCARD, COMPLEX with transitions
```
initial: CONST_ONLY
all constant caracters, CONST_ONLY: -> CONST_ONLY
%, CONST_ONLY --> WILDCARD
any other special char, any state --> COMPLEX
%, WILDCARD --> COMPLEX
```
Or, even better, define a simple recursive decent parser in which states are encoded as methods rather than as state variables.
```
parseConstant() ...
- parseWildcard()
- parseComplex()
parseWildcard() ...
- parseComplex()
parseComplex() ...
```
Here, I'm ignoring the details of detecting abc, abc%, ab%c, %abc. These can also be represented as states with the resulting transitions.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] drill pull request #907: DRILL-5697: Improve performance of filter operator ...
Posted by paul-rogers <gi...@git.apache.org>.
Github user paul-rogers commented on a diff in the pull request:
https://github.com/apache/drill/pull/907#discussion_r134035974
--- Diff: exec/java-exec/src/test/java/org/apache/drill/exec/expr/fn/impl/TestStringFunctions.java ---
@@ -157,6 +157,967 @@ public void testRegexpReplace() throws Exception {
}
@Test
+ public void testLikeStartsWith() throws Exception {
+
+ // all ASCII.
+ testBuilder()
--- End diff --
The regex parsing and execution code is becoming complex. Let's test it with a true unit test, not just a system-level test using a query. See the test frameworks available. We can also discuss in person.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] drill pull request #907: DRILL-5697: Improve performance of filter operator ...
Posted by paul-rogers <gi...@git.apache.org>.
Github user paul-rogers commented on a diff in the pull request:
https://github.com/apache/drill/pull/907#discussion_r134034748
--- Diff: exec/java-exec/src/main/java/org/apache/drill/exec/expr/fn/impl/RegexpUtil.java ---
@@ -96,20 +145,46 @@ public static String sqlToRegexLike(
|| (nextChar == '%')
|| (nextChar == escapeChar)) {
javaPattern.append(nextChar);
+ simplePattern.append(nextChar);
i++;
} else {
throw invalidEscapeSequence(sqlPattern, i);
}
} else if (c == '_') {
+ // if we find _, it is not simple pattern, we are looking for only %
+ notSimple = true;
javaPattern.append('.');
} else if (c == '%') {
+ if (i == 0) {
+ // % at the start could potentially be one of the simple cases i.e. ENDS_WITH.
+ endsWith = true;
+ } else if (i == (len-1)) {
--- End diff --
A bit of a funky way to do this. Might was well actually wait to the end. This is why we need states (as an enum or via recursive descent.) At end:
If all constants: CONST
If one wildcard: one of the simple cases
Otherwise: COMPLEX
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] drill pull request #907: DRILL-5697: Improve performance of filter operator ...
Posted by paul-rogers <gi...@git.apache.org>.
Github user paul-rogers commented on a diff in the pull request:
https://github.com/apache/drill/pull/907#discussion_r134032668
--- Diff: exec/java-exec/src/main/java/org/apache/drill/exec/expr/fn/impl/RegexpUtil.java ---
@@ -76,12 +113,24 @@ public static String sqlToRegexLike(
/**
* Translates a SQL LIKE pattern to Java regex pattern.
*/
- public static String sqlToRegexLike(
+ public static sqlPatternInfo sqlToRegexLike(
String sqlPattern,
char escapeChar) {
int i;
final int len = sqlPattern.length();
final StringBuilder javaPattern = new StringBuilder(len + len);
+ final StringBuilder simplePattern = new StringBuilder(len);
+
+ // Figure out the pattern type and build simplePatternString
+ // as we are going through the sql pattern string
+ // to build java regex pattern string. This is better instead of using
+ // regex later for determining if a pattern is simple or not.
+ // Saves CPU cycles.
+ sqlPatternType patternType = sqlPatternType.NOT_SIMPLE;
+ boolean startsWith = false;
+ boolean endsWith = false;
+ boolean notSimple = false;
--- End diff --
These are not independent states. Probably better to use your enum, with the initial value as null (unknown).
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] drill pull request #907: DRILL-5697: Improve performance of filter operator ...
Posted by paul-rogers <gi...@git.apache.org>.
Github user paul-rogers commented on a diff in the pull request:
https://github.com/apache/drill/pull/907#discussion_r134035511
--- Diff: exec/java-exec/src/main/java/org/apache/drill/exec/expr/fn/impl/StringFunctions.java ---
@@ -57,22 +57,120 @@ private StringFunctions() {}
@Output BitHolder out;
@Workspace java.util.regex.Matcher matcher;
@Workspace org.apache.drill.exec.expr.fn.impl.CharSequenceWrapper charSequenceWrapper;
+ @Workspace org.apache.drill.exec.expr.fn.impl.RegexpUtil.sqlPatternInfo patternInfo;
@Override
public void setup() {
- matcher = java.util.regex.Pattern.compile(org.apache.drill.exec.expr.fn.impl.RegexpUtil.sqlToRegexLike( //
- org.apache.drill.exec.expr.fn.impl.StringFunctionHelpers.toStringFromUTF8(pattern.start, pattern.end, pattern.buffer))).matcher("");
+ patternInfo = org.apache.drill.exec.expr.fn.impl.RegexpUtil.sqlToRegexLike(
+ org.apache.drill.exec.expr.fn.impl.StringFunctionHelpers.toStringFromUTF8(pattern.start, pattern.end, pattern.buffer));
charSequenceWrapper = new org.apache.drill.exec.expr.fn.impl.CharSequenceWrapper();
- matcher.reset(charSequenceWrapper);
+
+ // Use java regex and compile pattern only if it is not a simple pattern.
+ if (patternInfo.getPatternType() == org.apache.drill.exec.expr.fn.impl.RegexpUtil.sqlPatternType.NOT_SIMPLE) {
+ java.lang.String javaPatternString = patternInfo.getJavaPatternString();
+ matcher = java.util.regex.Pattern.compile(javaPatternString).matcher("");
+ matcher.reset(charSequenceWrapper);
+ }
}
@Override
public void eval() {
charSequenceWrapper.setBuffer(input.start, input.end, input.buffer);
// Reusing same charSequenceWrapper, no need to pass it in.
// This saves one method call since reset(CharSequence) calls reset()
- matcher.reset();
- out.value = matcher.matches()? 1:0;
+
+ // Not a simple case. Just use Java regex.
+ if (patternInfo.getPatternType() == org.apache.drill.exec.expr.fn.impl.RegexpUtil.sqlPatternType.NOT_SIMPLE) {
+ matcher.reset();
+ out.value = matcher.matches() ? 1 : 0;
+ }
+
+ // This is a simple pattern that ends with a constant string i.e. %ABC
+ // Compare the characters starting from end.
+ if (patternInfo.getPatternType() == org.apache.drill.exec.expr.fn.impl.RegexpUtil.sqlPatternType.ENDS_WITH) {
--- End diff --
Chains of ifs are rather old-school. Do a switch on the enum. And, do it in the pattern class so it can be unit tested.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] drill pull request #907: DRILL-5697: Improve performance of filter operator ...
Posted by kkhatua <gi...@git.apache.org>.
Github user kkhatua commented on a diff in the pull request:
https://github.com/apache/drill/pull/907#discussion_r133859377
--- Diff: exec/java-exec/src/main/java/org/apache/drill/exec/expr/fn/impl/RegexpUtil.java ---
@@ -47,18 +47,55 @@
"[:alnum:]", "\\p{Alnum}"
};
+ // type of pattern string.
+ public enum sqlPatternType {
+ STARTS_WITH, // Starts with a constant string followed by any string values (ABC%)
+ ENDS_WITH, // Ends with a constant string, starts with any string values (%ABC)
+ CONTAINS, // Contains a constant string, starts and ends with any string values (%ABC%)
--- End diff --
You should add a pattern of the form 'Starts with a constant, ends with another constant, and has any string in between'
(ABC%XYZ)
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] drill pull request #907: DRILL-5697: Improve performance of filter operator ...
Posted by asfgit <gi...@git.apache.org>.
Github user asfgit closed the pull request at:
https://github.com/apache/drill/pull/907
---
[GitHub] drill pull request #907: DRILL-5697: Improve performance of filter operator ...
Posted by paul-rogers <gi...@git.apache.org>.
Github user paul-rogers commented on a diff in the pull request:
https://github.com/apache/drill/pull/907#discussion_r134032943
--- Diff: exec/java-exec/src/main/java/org/apache/drill/exec/expr/fn/impl/RegexpUtil.java ---
@@ -96,20 +145,46 @@ public static String sqlToRegexLike(
|| (nextChar == '%')
|| (nextChar == escapeChar)) {
javaPattern.append(nextChar);
+ simplePattern.append(nextChar);
i++;
} else {
throw invalidEscapeSequence(sqlPattern, i);
}
} else if (c == '_') {
+ // if we find _, it is not simple pattern, we are looking for only %
+ notSimple = true;
--- End diff --
`type = NOT_SIMPLE`
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] drill issue #907: DRILL-5697: Improve performance of filter operator for pat...
Posted by ppadma <gi...@git.apache.org>.
Github user ppadma commented on the issue:
https://github.com/apache/drill/pull/907
@paul-rogers Paul, thanks a lot for the review. I made changes as per your comments. Please review updated diffs.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---