drill-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From sachouche <...@git.apache.org>
Subject [GitHub] drill pull request #1072: DRILL-5879: Improved SQL Pattern Contains Performa...
Date Wed, 10 Jan 2018 21:09:49 GMT
Github user sachouche commented on a diff in the pull request:

    https://github.com/apache/drill/pull/1072#discussion_r160763490
  
    --- 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) {
    +        return 1;
    +      }
    +
    +      final int inputLength = end - start;
    +
    +      for (int idx1 = patternLength - 1, idx2; idx1 < inputLength;) {
    --- End diff --
    
    idx2 is initialized in the inner loop; it is defined before because its value is needed
immediately after the inner loop. 


---

Mime
View raw message