Github user sachouche commented on a diff in the pull request:
https://github.com/apache/drill/pull/1072#discussion_r158086368
--- Diff:
exec/java-exec/src/main/java/org/apache/drill/exec/expr/fn/impl/SqlPatternContainsMatcher.java
---
@@ -19,44 +19,283 @@
import io.netty.buffer.DrillBuf;
-public class SqlPatternContainsMatcher extends AbstractSqlPatternMatcher {
+/** SQL Pattern Contains implementation */
+public final class SqlPatternContainsMatcher extends
AbstractSqlPatternMatcher {
+ private final MatcherFcn matcherFcn;
public SqlPatternContainsMatcher(String patternString) {
super(patternString);
+
+ // Pattern matching is 1) a CPU intensive operation and 2) pattern and
input dependent. The conclusion is
+ // that there is no single implementation that can do it all well. So,
we use multiple implementations
+ // chosen based on the pattern length.
+ if (patternLength == 1) {
+ matcherFcn = new Matcher1();
+ } else if (patternLength == 2) {
+ matcherFcn = new Matcher2();
+ } else if (patternLength == 3) {
+ matcherFcn = new Matcher3();
+ } else if (patternLength < 10) {
+ matcherFcn = new MatcherN();
+ } else {
+ matcherFcn = new BoyerMooreMatcher();
+ }
}
@Override
public int match(int start, int end, DrillBuf drillBuf) {
+ return matcherFcn.match(start, end, drillBuf);
+ }
+
+
//--------------------------------------------------------------------------
+ // Inner Data Structure
+ //
--------------------------------------------------------------------------
+
+ /** Abstract matcher class to allow us pick the most efficient
implementation */
+ private abstract class MatcherFcn {
+ protected final byte[] patternArray;
+
+ protected MatcherFcn() {
+ assert patternByteBuffer.hasArray();
+
+ patternArray = patternByteBuffer.array();
+ }
+
+ /**
+ * @return 1 if the pattern was matched; 0 otherwise
+ */
+ protected abstract int match(int start, int end, DrillBuf drillBuf);
+ }
+
+ /** Handles patterns with length one */
+ private final class Matcher1 extends MatcherFcn {
- if (patternLength == 0) { // Everything should match for null pattern
string
- return 1;
+ private Matcher1() {
+ super();
}
- final int txtLength = end - start;
+ /** {@inheritDoc} */
+ @Override
+ protected final int match(int start, int end, DrillBuf drillBuf) {
+ final int lengthToProcess = end - start;
+ final byte firstPattByte = patternArray[0];
- // no match if input string length is less than pattern length
- if (txtLength < patternLength) {
+ // simplePattern string has meta characters i.e % and _ and escape
characters removed.
+ // so, we can just directly compare.
+ for (int idx = 0; idx < lengthToProcess; idx++) {
+ byte inputByte = drillBuf.getByte(start + idx);
+
+ if (firstPattByte != inputByte) {
+ continue;
+ }
+ return 1;
+ }
return 0;
}
+ }
+ /** Handles patterns with length two */
+ private final class Matcher2 extends MatcherFcn {
- final int outerEnd = txtLength - patternLength;
+ private Matcher2() {
+ super();
+ }
- outer:
- for (int txtIndex = 0; txtIndex <= outerEnd; txtIndex++) {
+ /** {@inheritDoc} */
+ @Override
+ protected final int match(int start, int end, DrillBuf drillBuf) {
+ final int lengthToProcess = end - start - 1;
+ final byte firstPattByte = patternArray[0];
+ final byte secondPattByte = patternArray[1];
// simplePattern string has meta characters i.e % and _ and escape
characters removed.
// so, we can just directly compare.
- for (int patternIndex = 0; patternIndex < patternLength;
patternIndex++) {
- if (patternByteBuffer.get(patternIndex) != drillBuf.getByte(start
+ txtIndex + patternIndex)) {
- continue outer;
+ for (int idx = 0; idx < lengthToProcess; idx++) {
+ final byte firstInByte = drillBuf.getByte(start + idx);
+
+ if (firstPattByte != firstInByte) {
+ continue;
+ } else {
+ final byte secondInByte = drillBuf.getByte(start + idx +1);
+
+ if (secondInByte == secondPattByte) {
+ return 1;
+ }
}
}
+ return 0;
+ }
+ }
+
+ /** Handles patterns with length three */
+ private final class Matcher3 extends MatcherFcn {
- return 1;
+ private Matcher3() {
+ super();
}
- return 0;
+ /** {@inheritDoc} */
+ @Override
+ protected final int match(int start, int end, DrillBuf drillBuf) {
+ final int lengthToProcess = end - start -2;
+ final byte firstPattByte = patternArray[0];
+ final byte secondPattByte = patternArray[1];
+ final byte thirdPattByte = patternArray[2];
+
+ // simplePattern string has meta characters i.e % and _ and escape
characters removed.
+ // so, we can just directly compare.
+ for (int idx = 0; idx < lengthToProcess; idx++) {
+ final byte inputByte = drillBuf.getByte(start + idx);
+
+ if (firstPattByte != inputByte) {
+ continue;
+ } else {
+ final byte secondInByte = drillBuf.getByte(start + idx +1);
+ final byte thirdInByte = drillBuf.getByte(start + idx +2);
+
+ if (secondInByte == secondPattByte && thirdInByte ==
thirdPattByte) {
+ return 1;
+ }
+ }
+ }
+ return 0;
+ }
+ }
+
+ /** Handles patterns with arbitrary length */
+ private final class MatcherN extends MatcherFcn {
+
+ private MatcherN() {
+ super();
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ protected final int match(int start, int end, DrillBuf drillBuf) {
+
+ if (patternLength == 0) {
+ return 1;
+ }
+
+ final int lengthToProcess = end - start - patternLength + 1;
+ int patternIndex = 0;
+ final byte firstPattByte = patternArray[0];
+
+ // simplePattern string has meta characters i.e % and _ and escape
characters removed.
+ // so, we can just directly compare.
+ for (int idx = 0; idx < lengthToProcess; idx++) {
+ final byte inputByte = drillBuf.getByte(start + idx);
+
+ if (firstPattByte == inputByte) {
+ for (patternIndex = 1; patternIndex < patternLength;
++patternIndex) {
+ final byte currInByte = drillBuf.getByte(start + idx +
patternIndex);
+ final byte currPattByte = patternArray[patternIndex];
+
+ if (currInByte != currPattByte) {
+ break;
+ }
+ }
+
+ if (patternIndex == patternLength) {
+ break;
+ }
+ }
+ }
+ return patternIndex == patternLength ? 1 : 0;
+ }
+ }
+
+ /**
+ * Boyer-Moore matcher algorithm; excellent for large patterns and for
prefix patterns which appear
+ * frequently in the input.
+ */
+ private final class BoyerMooreMatcher extends MatcherFcn {
+ private final int[] offsetTable;
+ private final int[] characterTable;
+
+ private BoyerMooreMatcher() {
+ super();
+
+ this.offsetTable = makeOffsetTable();
+ this.characterTable = makeCharTable();
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ protected int match(int start, int end, DrillBuf drillBuf) {
+ if (patternLength == 0) {
--- End diff --
Yes, it would have come here; but for simplicity I guess I can handle that
use-case within the switch case.
---
