drill-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "ASF GitHub Bot (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (DRILL-5879) Optimize "Like" operator
Date Wed, 17 Jan 2018 17:40:00 GMT

    [ https://issues.apache.org/jira/browse/DRILL-5879?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16329082#comment-16329082
] 

ASF GitHub Bot commented on DRILL-5879:
---------------------------------------

Github user sachouche commented on a diff in the pull request:

    https://github.com/apache/drill/pull/1072#discussion_r162120115
  
    --- Diff: exec/java-exec/src/main/java/org/apache/drill/exec/expr/fn/impl/SqlPatternContainsMatcher.java
---
    @@ -19,44 +19,286 @@
     
     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 == 0) {
    +      matcherFcn = new MatcherZero();
    +    } else if (patternLength == 1) {
    +      matcherFcn = new MatcherOne();
    +    } else if (patternLength == 2) {
    +      matcherFcn = new MatcherTwo();
    +    } else if (patternLength == 3) {
    +      matcherFcn = new MatcherThree();
    +    } 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 MatcherZero extends MatcherFcn {
     
    -    if (patternLength == 0) { // Everything should match for null pattern string
    +    private MatcherZero() {
    +    }
    +
    +    /** {@inheritDoc} */
    +    @Override
    +    protected final int match(int start, int end, DrillBuf drillBuf) {
           return 1;
         }
    +  }
    +
    +  /** Handles patterns with length one */
    +  private final class MatcherOne extends MatcherFcn {
    +
    +    private MatcherOne() {
    +      super();
    --- End diff --
    
    removed.


> Optimize "Like" operator
> ------------------------
>
>                 Key: DRILL-5879
>                 URL: https://issues.apache.org/jira/browse/DRILL-5879
>             Project: Apache Drill
>          Issue Type: Improvement
>          Components: Execution - Relational Operators
>         Environment: * 
>            Reporter: salim achouche
>            Assignee: salim achouche
>            Priority: Minor
>             Fix For: 1.13.0
>
>
> Query: select <column-list> from <table> where colA like '%a%' or colA like
'%xyz%';
> Improvement Opportunities
> # Avoid isAscii computation (full access of the input string) since we're dealing with
the same column twice
> # Optimize the "contains" for-loop 
> Implementation Details
> 1)
> * Added a new integer variable "asciiMode" to the VarCharHolder class
> * The default value is -1 which indicates this info is not known
> * Otherwise this value will be set to either 1 or 0 based on the string being in ASCII
mode or Unicode
> * The execution plan already shares the same VarCharHolder instance for all evaluations
of the same column value
> * The asciiMode will be correctly set during the first LIKE evaluation and will be reused
across other LIKE evaluations
> 2) 
> * The "Contains" LIKE operation is quite expensive as the code needs to access the input
string to perform character based comparisons
> * Created 4 versions of the same for-loop to a) make the loop simpler to optimize (Vectorization)
and b) minimize comparisons
> Benchmarks
> * Lineitem table 100GB
> * Query: select l_returnflag, count(*) from dfs.`<source>` where l_comment not
like '%a%' or l_comment like '%the%' group by l_returnflag
> * Before changes: 33sec
> * After changes    : 27sec



--
This message was sent by Atlassian JIRA
(v7.6.3#76005)

Mime
View raw message