Github user sachouche commented on a diff in the pull request: https://github.com/apache/drill/pull/1072#discussion_r158085723 --- 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; --- End diff -- will do.
---