[GitHub] incubator-carbondata pull request #627: fix jira CARBONDATA-748 for version ...

[qiuchenjian-2]

GitHub user simafengyun opened a pull request:

    https://github.com/apache/incubator-carbondata/pull/627

    fix jira CARBONDATA-748 for version 0.2

    fix jira CARBONDATA-748, use binary search to replace linear search
    the performance is much better no ,from more than 10 seconds to a few millisecond

You can merge this pull request into a Git repository by running:

    $ git pull https://github.com/simafengyun/incubator-carbondata Fix-CARBONDATA-748

Alternatively you can review and apply these changes as the patch at:

    https://github.com/apache/incubator-carbondata/pull/627.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 #627
   
----
commit 29466d3a9f5a9508581dfa55a12ed49a64aac14e
Author: mayun <mayun@10.100.56.61>
Date:   2017-03-07T07:57:32Z

    fix jira CARBONDATA-748 for version 0.2

----


---
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 [hidden email] or file a JIRA ticket
with INFRA.
---

[qiuchenjian-2]

Github user CarbonDataQA commented on the issue:

    https://github.com/apache/incubator-carbondata/pull/627
 
    Can one of the admins verify this patch?


---
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 [hidden email] or file a JIRA ticket
with INFRA.
---

[qiuchenjian-2]

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

    https://github.com/apache/incubator-carbondata/pull/627#discussion_r104611743
 
    --- Diff: core/src/main/java/org/apache/carbondata/core/util/ByteUtil.java ---
    @@ -152,6 +152,159 @@ static boolean lessThanUnsigned(long x1, long x2) {
           return (x1 + Long.MIN_VALUE) < (x2 + Long.MIN_VALUE);
         }
     
    +
    --- End diff --
   
    please delete this annotation if not use any more.


---
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 [hidden email] or file a JIRA ticket
with INFRA.
---

[qiuchenjian-2]

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

    https://github.com/apache/incubator-carbondata/pull/627#discussion_r104613452
 
    --- Diff: core/src/main/java/org/apache/carbondata/core/util/ByteUtil.java ---
    @@ -152,6 +152,159 @@ static boolean lessThanUnsigned(long x1, long x2) {
           return (x1 + Long.MIN_VALUE) < (x2 + Long.MIN_VALUE);
         }
     
    +
    +/* public static int binarySearch(byte[] a, int fromIndex, int toIndex, byte[] key) {
    + int keyLength = key.length;
    + rangeCheck(a.length, fromIndex, toIndex, keyLength);
    + return binarySearch0(a, fromIndex, toIndex / keyLength, key);
    + }
    +
    + // Like public version, but without range checks.
    + private static int binarySearch0(byte[] a, int fromIndex, int toIndex, byte[] key) {
    + int low = fromIndex;
    + int high = toIndex - 1;
    + int keyLength = key.length;
    + // int high = toIndex/keyLength;
    +
    + while (low <= high) {
    + int mid = (low + high) >>> 1;
    + // byte midVal = a[mid];
    +
    + int result = ByteUtil.UnsafeComparer.INSTANCE.compareTo(a, mid * keyLength, keyLength, key, 0,
    + keyLength);
    +
    + if (result < 0)
    + low = mid + keyLength;
    + else if (result > 0)
    + high = mid - keyLength;
    + else
    + return mid; // key found
    + }
    + return -(low + 1); // key not found.
    + }*/
    + /**
    + * Checks that {@code fromIndex} and {@code toIndex} are in the range and toIndex % keyLength = 0
    + * and throws an exception if they aren't.
    + */
    + private static void rangeCheck(int arrayLength, int fromIndex, int toIndex, int keyWordLength) {
    + if (fromIndex > toIndex || toIndex % keyWordLength != 0) {
    + throw new IllegalArgumentException("fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
    --- End diff --
   
    the exception msg may be misleading, please give some msg about `toIndex % keyWordLength != 0`.


---
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 [hidden email] or file a JIRA ticket
with INFRA.
---

[qiuchenjian-2]

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

    https://github.com/apache/incubator-carbondata/pull/627#discussion_r104614642
 
    --- Diff: core/src/main/java/org/apache/carbondata/scan/filter/executer/IncludeFilterExecuterImpl.java ---
    @@ -154,24 +154,45 @@ private BitSet setFilterdIndexToBitSetWithColumnIndex(
       }
     
       private BitSet setFilterdIndexToBitSet(DimensionColumnDataChunk dimensionColumnDataChunk,
    -      int numerOfRows) {
    -    BitSet bitSet = new BitSet(numerOfRows);
    -    if (dimensionColumnDataChunk instanceof FixedLengthDimensionDataChunk) {
    -      FixedLengthDimensionDataChunk fixedDimensionChunk =
    -          (FixedLengthDimensionDataChunk) dimensionColumnDataChunk;
    -      byte[][] filterValues = dimColumnExecuterInfo.getFilterKeys();
    -      for (int k = 0; k < filterValues.length; k++) {
    -        for (int j = 0; j < numerOfRows; j++) {
    -          if (ByteUtil.UnsafeComparer.INSTANCE
    -              .compareTo(fixedDimensionChunk.getCompleteDataChunk(), j * filterValues[k].length,
    -                  filterValues[k].length, filterValues[k], 0, filterValues[k].length) == 0) {
    -            bitSet.set(j);
    -          }
    -        }
    -      }
    -    }
    -    return bitSet;
    -  }
    +      int numerOfRows) {
    +
    +    BitSet bitSet = new BitSet(numerOfRows);
    +    //BitSet bitSet1 = new BitSet(numerOfRows);
    +    
    +    if (dimensionColumnDataChunk instanceof FixedLengthDimensionDataChunk) {
    +      FixedLengthDimensionDataChunk fixedDimensionChunk =
    +          (FixedLengthDimensionDataChunk) dimensionColumnDataChunk;
    +      byte[][] filterValues = dimColumnExecuterInfo.getFilterKeys();
    +      byte[] dataChunk= fixedDimensionChunk.getCompleteDataChunk();
    +
    +  //long start = System.currentTimeMillis();
    +      for (int k = 0; k < filterValues.length; k++) {
    +      
    +      int[] index = ByteUtil.UnsafeComparer.INSTANCE.binaryRangeSearch(dataChunk, 0, dataChunk.length, filterValues[k]);
    +      for(int i = index[0]; i<=index[1];i++){
    +      
    +      bitSet.set(i);
    +      }
    +      }
    +  
    +      //below comments code is used to confirm the binary range search is correct  
    --- End diff --
   
    please delete annotation if not used.


---
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 [hidden email] or file a JIRA ticket
with INFRA.
---

[qiuchenjian-2]

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

    https://github.com/apache/incubator-carbondata/pull/627#discussion_r104617853
 
    --- Diff: core/src/main/java/org/apache/carbondata/core/util/ByteUtil.java ---
    @@ -152,6 +152,159 @@ static boolean lessThanUnsigned(long x1, long x2) {
           return (x1 + Long.MIN_VALUE) < (x2 + Long.MIN_VALUE);
         }
     
    +
    +/* public static int binarySearch(byte[] a, int fromIndex, int toIndex, byte[] key) {
    + int keyLength = key.length;
    + rangeCheck(a.length, fromIndex, toIndex, keyLength);
    + return binarySearch0(a, fromIndex, toIndex / keyLength, key);
    + }
    +
    + // Like public version, but without range checks.
    + private static int binarySearch0(byte[] a, int fromIndex, int toIndex, byte[] key) {
    + int low = fromIndex;
    + int high = toIndex - 1;
    + int keyLength = key.length;
    + // int high = toIndex/keyLength;
    +
    + while (low <= high) {
    + int mid = (low + high) >>> 1;
    + // byte midVal = a[mid];
    +
    + int result = ByteUtil.UnsafeComparer.INSTANCE.compareTo(a, mid * keyLength, keyLength, key, 0,
    + keyLength);
    +
    + if (result < 0)
    + low = mid + keyLength;
    + else if (result > 0)
    + high = mid - keyLength;
    + else
    + return mid; // key found
    + }
    + return -(low + 1); // key not found.
    + }*/
    + /**
    + * Checks that {@code fromIndex} and {@code toIndex} are in the range and toIndex % keyLength = 0
    + * and throws an exception if they aren't.
    + */
    + private static void rangeCheck(int arrayLength, int fromIndex, int toIndex, int keyWordLength) {
    + if (fromIndex > toIndex || toIndex % keyWordLength != 0) {
    + throw new IllegalArgumentException("fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
    + }
    + if (fromIndex < 0) {
    + throw new ArrayIndexOutOfBoundsException(fromIndex);
    + }
    + if (toIndex > arrayLength) {
    + throw new ArrayIndexOutOfBoundsException(toIndex);
    + }
    + }
    +
    + /**
    + * search a specific key's range boundary in sorted byte array
    + *
    + * @param dataChunk
    + * @param fromIndex
    + * @param toIndex
    + *            it's max value should be word Number in dataChunk, equal to indataChunk.length/keyWord.length
    + * @param keyWord
    + * @return int[] contains a range's lower boundary and upper boundary
    + */
    + public static int[] binaryRangeSearch(byte[] dataChunk, int fromIndex, int toIndex, byte[] keyWord) {
    +
    +
    + int keyLength = keyWord.length;
    + rangeCheck(dataChunk.length, fromIndex, toIndex, keyLength);
    +
    + // reset to index =  word total number in the dataChunk
    + toIndex = toIndex/keyWord.length;
    +
    + int[] rangeIndex = new int[2];
    + int low = fromIndex;
    + int high = toIndex - 1;
    +
    + while (low <= high) {
    + int mid = (low + high) >>> 1;
    +
    + int result = ByteUtil.UnsafeComparer.INSTANCE.compareTo(dataChunk, mid * keyLength, keyLength, keyWord, 0,
    + keyLength);
    +
    + if (result < 0)
    + low = mid + 1;
    + else if (result > 0)
    + high = mid - 1;
    + else {
    + // key found  then find the range bound
    + rangeIndex[0] = binaryRangeBoundarySearch(dataChunk, low, mid, keyWord, false);
    + rangeIndex[1] = binaryRangeBoundarySearch(dataChunk, mid, high, keyWord, true);
    + return rangeIndex;
    + }
    +
    + }
    + // key not found. return a not exist range
    + rangeIndex[0] = 0;
    + rangeIndex[1] = -1;
    + return rangeIndex;
    + }
    +
    +  /**
    +   * use to search a specific keyword's lower boundary and upper boundary according to upFindFlg
    +   * @param dataChunk
    +   * @param fromIndex
    +   * @param toIndex
    +   * @param keyWord
    +   * @param upFindFlg true:find upper boundary  false: find lower boundary
    +   * @return boundary index
    +   */
    + public static int binaryRangeBoundarySearch(byte[] dataChunk, int fromIndex, int toIndex, byte[] keyWord, boolean upFindFlg) {
    --- End diff --
   
    1. there are some common codes between `binaryRangeSearch` and `binaryRangeBoundarySearch`, is it possible to merge them into one method?
    2. are you interesting to impl. a complete function about Interval (of Mathematics).
    FYI.


---
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 [hidden email] or file a JIRA ticket
with INFRA.
---

[qiuchenjian-2]

Github user Hexiaoqiao commented on the issue:

    https://github.com/apache/incubator-carbondata/pull/627
 
    @simafengyun
    thanks for your work, please rename title follow the format `[CARBONDATA-issue number>] Title of the pull request`.


---
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 [hidden email] or file a JIRA ticket
with INFRA.
---

[qiuchenjian-2]

Github user zzcclp commented on the issue:

    https://github.com/apache/incubator-carbondata/pull/627
 
    Is this pr just be fixed for branch-0.2?


---
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 [hidden email] or file a JIRA ticket
with INFRA.
---

[qiuchenjian-2]

Github user ravipesala commented on the issue:

    https://github.com/apache/incubator-carbondata/pull/627
 
    add to whitelist


---
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 [hidden email] or file a JIRA ticket
with INFRA.
---

[qiuchenjian-2]

Github user CarbonDataQA commented on the issue:

    https://github.com/apache/incubator-carbondata/pull/627
 
    Build Failed  with Spark 1.6.2, Please check CI http://136.243.101.176:8080/job/ApacheCarbonPRBuilder/1022/



---
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 [hidden email] or file a JIRA ticket
with INFRA.
---

[qiuchenjian-2]

Github user CarbonDataQA commented on the issue:

    https://github.com/apache/incubator-carbondata/pull/627
 
    Build Failed  with Spark 1.6.2, Please check CI http://136.243.101.176:8080/job/ApacheCarbonPRBuilder/1023/



---
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 [hidden email] or file a JIRA ticket
with INFRA.
---

[qiuchenjian-2]

Github user simafengyun commented on the issue:

    https://github.com/apache/incubator-carbondata/pull/627
 
    yes
    I just fixed on branch-0.2.
    If code is ok, I can continue to fix for version 1.0
   
   
   
   
   
   
   
   
   
   
    At 2017-03-07 17:20:44, "Zhichao Zhang" <[hidden email]> wrote:
   
   
    Is this pr just be fixed for branch-0.2?
   
    —
    You are receiving this because you were mentioned.
    Reply to this email directly, view it on GitHub, or mute the thread.


---
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 [hidden email] or file a JIRA ticket
with INFRA.
---

[qiuchenjian-2]

Github user ravipesala commented on the issue:

    https://github.com/apache/incubator-carbondata/pull/627
 
    @simafengyun Thanks for working on it.
    Range binary search is impressive. we can use same search in other places as well.
    But using this search in `setFilterdIndexToBitSet` is not always correct. Because here the data may not be sorted always, Only for the first column of dimensions is sorted naturally because of mdk order.
    And if the data is sorted explicitly(it means it has inverted index) then it goes to another method `setFilterdIndexToBitSetWithColumnIndex`.  So here we need extra checks to do binary search in the method `setFilterdIndexToBitSet` , that is like whether the column is naturally sorted or not.This information we may need get from store.  
    Please use this Range binary search in 'setFilterdIndexToBitSetWithColumnIndex' as well.


---
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 [hidden email] or file a JIRA ticket
with INFRA.
---

[qiuchenjian-2]

Github user ravipesala commented on the issue:

    https://github.com/apache/incubator-carbondata/pull/627
 
    @simafengyun Please raise this PR on master as we don't have any plans to provide patches on branch-0.2. And also please format the code.


---
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 [hidden email] or file a JIRA ticket
with INFRA.
---

[qiuchenjian-2]

Github user simafengyun commented on the issue:

    https://github.com/apache/incubator-carbondata/pull/627
 
   
   
    You mentioned the below,
    >>>>>>>>>>>>>>>>>>>>>>>>>>
    But using this search in setFilterdIndexToBitSet is not always correct. Because here the data may not be sorted always, Only for the first column of dimensions is sorted naturally because of mdk order.
    >>>>>>>>>>>>>>>>>>>>>>>>>>
     but i don't think so.
    the order you mentioned is the logical level order(MDK).
    As I know, for dimension column, it has physical order in chunk level.
    for dimension data which has dictionary encode, the dictionary data will sorted in blocklet level and keep the order in chunk on the physical  disk.
    So after the one chunk dimension data read, it will keep the order, so I think it is fit for the binary search.
   
   
    if I was wrong, please feel free to tell me, thanks
   
   
   
   
   
   
   
   
   
   
    At 2017-03-07 17:44:28, "Ravindra Pesala" <[hidden email]> wrote:
   
   
    @simafengyun Thanks for working on it.
    Range binary search is impressive. we can use same search in other places as well.
    But using this search in setFilterdIndexToBitSet is not always correct. Because here the data may not be sorted always, Only for the first column of dimensions is sorted naturally because of mdk order.
    And if the data is sorted explicitly(it means it has inverted index) then it goes to another method setFilterdIndexToBitSetWithColumnIndex. So here we need extra checks to do binary search in the method setFilterdIndexToBitSet , that is like whether the column is naturally sorted or not.This information we may need get from store.
    Please use this Range binary search in 'setFilterdIndexToBitSetWithColumnIndex' as well.
   
    —
    You are receiving this because you were mentioned.
    Reply to this email directly, view it on GitHub, or mute the thread.


---
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 [hidden email] or file a JIRA ticket
with INFRA.
---

[qiuchenjian-2]

Github user ravipesala commented on the issue:

    https://github.com/apache/incubator-carbondata/pull/627
 
    @simafengyun you are right, default we sort the data but we can avoid sorting using `no_inverted_index` property at tblproperties level. So if user uses this configuration then we cannot do binary search always.


---
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 [hidden email] or file a JIRA ticket
with INFRA.
---

[qiuchenjian-2]

Github user simafengyun commented on the issue:

    https://github.com/apache/incubator-carbondata/pull/627
 
    so binary search only fit the below cases，please comfirm thanks
   
    1 the first dimension column ， since it's logicl order are the same with physical order in blocklet level，so it does not need inverted index
   
    2 for dimension column which has inverted index
   
    question 1
   
    if a dimension column is not the first colmn and in a blocklet it just has the same order for both logical and physical，will carbondata create inverted index for it?
   
    question 2
   
    is there an easy way to identify whether a dimension column has no_inverted_index property config by user in source code ，so it will be helpful for me to add a condition to use binary search
   
   
   
    thanks
   
    在 2017-03-07 18:35:05，"Ravindra Pesala" <[hidden email]> 写道：
   
   
    @simafengyun you are right, default we sort the data but we can avoid sorting using no_inverted_index property at tblproperties level. So if user uses this configuration then we cannot do binary search always.
   
    —
    You are receiving this because you were mentioned.
    Reply to this email directly, view it on GitHub, or mute the thread.


---
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 [hidden email] or file a JIRA ticket
with INFRA.
---

[qiuchenjian-2]

Github user ravipesala commented on the issue:

    https://github.com/apache/incubator-carbondata/pull/627
 
    Yes, those are the 2 cases we can do binary search on dimension.
   
    Regarding question1 , no it does not create inverted index if the data is already sorted(naturally sorted).
   
    Regarding question2, it is an issue pending from long time, it requires changes from data writer and as well as data reader to update the sort state.  
    There are attributes like SortState and Encoders in DataChunk of format needs to updated properly while writing and get them back while reading to know the dimension has inverted_index or not, or it is naturally sorted or not.
   
    My suggestion is don't change the method of  `setFilterdIndexToBitSet` as the old logic is required for no_inverted index and non sorted columns. Update the the method `setFilterdIndexToBitSetWithColumnIndex` with your range search.  To know the dimension is naturally sorted or not we can add another PR to update the read/write logic.


---
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 [hidden email] or file a JIRA ticket
with INFRA.
---

[qiuchenjian-2]

Github user simafengyun closed the pull request at:

    https://github.com/apache/incubator-carbondata/pull/627


---
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 [hidden email] or file a JIRA ticket
with INFRA.
---