carbondata-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From ravipes...@apache.org
Subject [1/2] incubator-carbondata git commit: use binary search to improve the performance in method setFilterdIndexToBitSet
Date Sat, 11 Mar 2017 01:43:14 GMT
Repository: incubator-carbondata
Updated Branches:
  refs/heads/master 6713ffa1f -> 22eccf7c6


use binary search to improve the performance in method
setFilterdIndexToBitSet

add binary range search and add test case

revert previous change

format changed code

change code format to pass check style

revert the code to use inverted index

add comments and change variables definition style


Project: http://git-wip-us.apache.org/repos/asf/incubator-carbondata/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-carbondata/commit/bedaa59e
Tree: http://git-wip-us.apache.org/repos/asf/incubator-carbondata/tree/bedaa59e
Diff: http://git-wip-us.apache.org/repos/asf/incubator-carbondata/diff/bedaa59e

Branch: refs/heads/master
Commit: bedaa59ef298fdf12be4641d239b14c05368ea5b
Parents: 6713ffa
Author: mayun <mayun@10.100.56.61>
Authored: Thu Mar 9 13:13:22 2017 +0800
Committer: ravipesala <ravi.pesala@gmail.com>
Committed: Sat Mar 11 07:12:21 2017 +0530

----------------------------------------------------------------------
 .../executer/IncludeFilterExecuterImpl.java     |  47 ++-
 .../apache/carbondata/core/util/CarbonUtil.java |  94 ++++++
 .../executer/IncludeFilterExecuterImplTest.java | 299 +++++++++++++++++++
 .../carbondata/core/util/CarbonUtilTest.java    | 180 +++++++++++
 4 files changed, 596 insertions(+), 24 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/incubator-carbondata/blob/bedaa59e/core/src/main/java/org/apache/carbondata/core/scan/filter/executer/IncludeFilterExecuterImpl.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/carbondata/core/scan/filter/executer/IncludeFilterExecuterImpl.java
b/core/src/main/java/org/apache/carbondata/core/scan/filter/executer/IncludeFilterExecuterImpl.java
index e640d71..732e87c 100644
--- a/core/src/main/java/org/apache/carbondata/core/scan/filter/executer/IncludeFilterExecuterImpl.java
+++ b/core/src/main/java/org/apache/carbondata/core/scan/filter/executer/IncludeFilterExecuterImpl.java
@@ -116,30 +116,18 @@ public class IncludeFilterExecuterImpl implements FilterExecuter {
   private BitSet setFilterdIndexToBitSetWithColumnIndex(
       FixedLengthDimensionDataChunk dimensionColumnDataChunk, int numerOfRows) {
     BitSet bitSet = new BitSet(numerOfRows);
-    int start = 0;
-    int last = 0;
     int startIndex = 0;
     byte[][] filterValues = dimColumnExecuterInfo.getFilterKeys();
     for (int i = 0; i < filterValues.length; i++) {
-      start = CarbonUtil
-          .getFirstIndexUsingBinarySearch(dimensionColumnDataChunk, startIndex, numerOfRows
- 1,
-              filterValues[i], false);
-      if (start < 0) {
-        continue;
-      }
-      bitSet.set(dimensionColumnDataChunk.getInvertedIndex(start));
-      last = start;
-      for (int j = start + 1; j < numerOfRows; j++) {
-        if (dimensionColumnDataChunk.compareTo(j, filterValues[i]) == 0) {
-          bitSet.set(dimensionColumnDataChunk.getInvertedIndex(j));
-          last++;
-        } else {
-          break;
-        }
+      int[] rangeIndex = CarbonUtil.getRangeIndexUsingBinarySearch(dimensionColumnDataChunk,
+          startIndex, numerOfRows - 1, filterValues[i]);
+      for (int j = rangeIndex[0]; j <= rangeIndex[1]; j++) {
+
+        bitSet.set(dimensionColumnDataChunk.getInvertedIndex(j));
       }
-      startIndex = last;
-      if (startIndex >= numerOfRows) {
-        break;
+
+      if (rangeIndex[1] >= 0) {
+        startIndex = rangeIndex[1];
       }
     }
     return bitSet;
@@ -150,12 +138,23 @@ public class IncludeFilterExecuterImpl implements FilterExecuter {
     BitSet bitSet = new BitSet(numerOfRows);
     if (dimensionColumnDataChunk instanceof FixedLengthDimensionDataChunk) {
       byte[][] filterValues = dimColumnExecuterInfo.getFilterKeys();
-      for (int k = 0; k < filterValues.length; k++) {
-        for (int j = 0; j < numerOfRows; j++) {
-          if (dimensionColumnDataChunk.compareTo(j, filterValues[k]) == 0) {
-            bitSet.set(j);
+      for (int i = 0; i < numerOfRows; i++) {
+
+        if (filterValues.length > 1) {
+          int index = CarbonUtil.binarySearch(filterValues, 0, filterValues.length - 1,
+              dimensionColumnDataChunk.getChunkData(i));
+
+          if (index >= 0) {
+            bitSet.set(i);
+          }
+        } else if (filterValues.length == 1) {
+          if (dimensionColumnDataChunk.compareTo(i, filterValues[0]) == 0) {
+            bitSet.set(i);
           }
+        } else {
+          break;
         }
+
       }
     }
     return bitSet;

http://git-wip-us.apache.org/repos/asf/incubator-carbondata/blob/bedaa59e/core/src/main/java/org/apache/carbondata/core/util/CarbonUtil.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/carbondata/core/util/CarbonUtil.java b/core/src/main/java/org/apache/carbondata/core/util/CarbonUtil.java
index 5a656e0..36e75f3 100644
--- a/core/src/main/java/org/apache/carbondata/core/util/CarbonUtil.java
+++ b/core/src/main/java/org/apache/carbondata/core/util/CarbonUtil.java
@@ -420,6 +420,100 @@ public final class CarbonUtil {
   }
 
   /**
+   * search a specific compareValue's range index in a sorted byte array
+   *
+   * @param dimColumnDataChunk
+   * @param low
+   * @param high
+   * @param compareValue
+   * @return the compareValue's range index in the dimColumnDataChunk
+   */
+  public static int[] getRangeIndexUsingBinarySearch(
+      FixedLengthDimensionDataChunk dimColumnDataChunk, int low, int high, byte[] compareValue)
{
+
+    int[] rangeIndex = new int[2];
+    int cmpResult = 0;
+    while (high >= low) {
+      int mid = (low + high) / 2;
+      cmpResult = dimColumnDataChunk.compareTo(mid, compareValue);
+      if (cmpResult < 0) {
+        low = mid + 1;
+      } else if (cmpResult > 0) {
+        high = mid - 1;
+      } else {
+
+        int currentIndex = mid;
+        while (currentIndex - 1 >= 0
+            && dimColumnDataChunk.compareTo(currentIndex - 1, compareValue) == 0)
{
+          --currentIndex;
+        }
+        rangeIndex[0] = currentIndex;
+
+        currentIndex = mid;
+        while (currentIndex + 1 <= high
+            && dimColumnDataChunk.compareTo(currentIndex + 1, compareValue) == 0)
{
+          currentIndex++;
+        }
+        rangeIndex[1] = currentIndex;
+
+        return rangeIndex;
+      }
+    }
+
+    // key not found. return a not exist range
+    // rangeIndex[0] = 0;
+    rangeIndex[1] = -1;
+    return rangeIndex;
+  }
+
+  /**
+   * Checks that {@code fromIndex} and {@code toIndex} are in the range and
+   * throws an exception if they aren't.
+   */
+  private static void rangeCheck(int fromIndex, int toIndex) {
+    if (fromIndex > toIndex) {
+      throw new IllegalArgumentException("fromIndex(" + fromIndex + ") > toIndex(" + toIndex
+ ")");
+    }
+    if (fromIndex < 0) {
+      throw new ArrayIndexOutOfBoundsException(fromIndex);
+    }
+  }
+
+  /**
+   * search a specific key in sorted byte array
+   *
+   * @param filterValues
+   * @param low
+   * @param high
+   * @param compareValue
+   * @return the compareValue's index in the filterValues
+   */
+  public static int binarySearch(byte[][] filterValues, int low, int high,
+      byte[] compareValue) {
+
+    rangeCheck(low, high);
+
+    while (low <= high) {
+      int mid = (low + high) >>> 1;
+
+      int result = ByteUtil.UnsafeComparer.INSTANCE.compareTo(filterValues[mid], compareValue);
+
+      if (result < 0) {
+        low = mid + 1;
+      } else if (result > 0) {
+        high = mid - 1;
+      } else {
+
+        return mid; // key found
+      }
+
+    }
+    // key not found
+    return -(low + 1);
+  }
+
+
+  /**
    * Method will identify the value which is lesser than the pivot element
    * on which range filter is been applied.
    *

http://git-wip-us.apache.org/repos/asf/incubator-carbondata/blob/bedaa59e/core/src/test/java/org/apache/carbondata/core/scan/filter/executer/IncludeFilterExecuterImplTest.java
----------------------------------------------------------------------
diff --git a/core/src/test/java/org/apache/carbondata/core/scan/filter/executer/IncludeFilterExecuterImplTest.java
b/core/src/test/java/org/apache/carbondata/core/scan/filter/executer/IncludeFilterExecuterImplTest.java
new file mode 100644
index 0000000..b2aa855
--- /dev/null
+++ b/core/src/test/java/org/apache/carbondata/core/scan/filter/executer/IncludeFilterExecuterImplTest.java
@@ -0,0 +1,299 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.carbondata.core.scan.filter.executer;
+
+import java.util.BitSet;
+
+import org.apache.carbondata.core.datastore.chunk.DimensionColumnDataChunk;
+import org.apache.carbondata.core.datastore.chunk.impl.FixedLengthDimensionDataChunk;
+import org.apache.carbondata.core.util.CarbonUtil;
+import org.junit.Before;
+import org.junit.Test;
+
+import junit.framework.TestCase;
+
+public class IncludeFilterExecuterImplTest extends TestCase {
+
+  /**
+   * @throws Exception
+   */
+  @Before
+  public void setUp() throws Exception {
+
+  }
+
+  private BitSet setFilterdIndexToBitSetNew(DimensionColumnDataChunk dimensionColumnDataChunk,
+      int numerOfRows, byte[][] filterValues) {
+    BitSet bitSet = new BitSet(numerOfRows);
+    if (dimensionColumnDataChunk instanceof FixedLengthDimensionDataChunk) {
+      // byte[][] filterValues = dimColumnExecuterInfo.getFilterKeys();
+      for (int i = 0; i < numerOfRows; i++) {
+
+        if (filterValues.length > 1) {
+          int index = CarbonUtil.binarySearch(filterValues, 0, filterValues.length - 1,
+              dimensionColumnDataChunk.getChunkData(i));
+
+          if (index >= 0) {
+            bitSet.set(i);
+          }
+        } else if (filterValues.length == 1) {
+          if (dimensionColumnDataChunk.compareTo(i, filterValues[0]) == 0) {
+            bitSet.set(i);
+          }
+        } else {
+          break;
+        }
+
+      }
+    }
+    return bitSet;
+  }
+
+  private BitSet setFilterdIndexToBitSet(DimensionColumnDataChunk dimensionColumnDataChunk,
int numerOfRows,
+      byte[][] filterValues) {
+    BitSet bitSet = new BitSet(numerOfRows);
+    if (dimensionColumnDataChunk instanceof FixedLengthDimensionDataChunk) {
+      // byte[][] filterValues = dimColumnExecuterInfo.getFilterKeys();
+      for (int k = 0; k < filterValues.length; k++) {
+        for (int j = 0; j < numerOfRows; j++) {
+          if (dimensionColumnDataChunk.compareTo(j, filterValues[k]) == 0) {
+            bitSet.set(j);
+          }
+        }
+      }
+    }
+    return bitSet;
+  }
+
+  /**
+   * short int to byte
+   * 
+   * @param s
+   *          short int
+   * @return byte[]
+   */
+  private byte[] unsignedShortToByte2(int s) {
+    byte[] targets = new byte[2];
+    targets[0] = (byte) (s >> 8 & 0xFF);
+    targets[1] = (byte) (s & 0xFF);
+    return targets;
+  }
+
+  @Test
+  public void testPerformance() {
+
+    long oldTime = 0;
+    long newTime = 0;
+    long start;
+    int dataCnt = 120000;
+    int filterCnt = 800;
+    int queryCnt = 5;
+    int repeatCnt = 20;
+    byte[] keyWord = new byte[2];
+    FixedLengthDimensionDataChunk dimensionColumnDataChunk;
+    DimColumnExecuterFilterInfo dim = new DimColumnExecuterFilterInfo();
+
+    byte[] dataChunk = new byte[dataCnt * keyWord.length];
+    for (int i = 0; i < dataCnt; i++) {
+
+      if (i % repeatCnt == 0) {
+        repeatCnt++;
+      }
+
+      byte[] data = unsignedShortToByte2(repeatCnt);
+      dataChunk[2 * i] = data[0];
+      dataChunk[2 * i + 1] = data[1];
+
+    }
+
+    byte[][] filterKeys = new byte[filterCnt][2];
+    for (int ii = 0; ii < filterCnt; ii++) {
+      filterKeys[ii] = unsignedShortToByte2(100 + ii);
+    }
+    dim.setFilterKeys(filterKeys);
+
+    dimensionColumnDataChunk = new FixedLengthDimensionDataChunk(dataChunk, null, null,
+        dataChunk.length / keyWord.length, keyWord.length);
+
+    for (int j = 0; j < queryCnt; j++) {
+
+      start = System.currentTimeMillis();
+      BitSet bitOld = this.setFilterdIndexToBitSet(dimensionColumnDataChunk, dataCnt, filterKeys);
+      oldTime = oldTime + System.currentTimeMillis() - start;
+
+      start = System.currentTimeMillis();
+      BitSet bitNew = this.setFilterdIndexToBitSetNew((FixedLengthDimensionDataChunk) dimensionColumnDataChunk,
dataCnt,
+          filterKeys);
+      newTime = newTime + System.currentTimeMillis() - start;
+
+      assertTrue(bitOld.equals(bitNew));
+
+    }
+
+    assertTrue(newTime < oldTime);
+
+    System.out.println("old code performance time: " + oldTime);
+    System.out.println("new code performance time: " + newTime);
+
+  }
+
+  private BitSet setFilterdIndexToBitSetWithColumnIndex(FixedLengthDimensionDataChunk dimensionColumnDataChunk,
+      int numerOfRows, byte[][] filterValues) {
+    BitSet bitSet = new BitSet(numerOfRows);
+    int start = 0;
+    int last = 0;
+    int startIndex = 0;
+    // byte[][] filterValues = dimColumnExecuterInfo.getFilterKeys();
+    for (int i = 0; i < filterValues.length; i++) {
+      start = CarbonUtil.getFirstIndexUsingBinarySearch(dimensionColumnDataChunk, startIndex,
numerOfRows - 1,
+          filterValues[i], false);
+      if (start < 0) {
+        continue;
+      }
+      bitSet.set(start);
+      last = start;
+      for (int j = start + 1; j < numerOfRows; j++) {
+        if (dimensionColumnDataChunk.compareTo(j, filterValues[i]) == 0) {
+          bitSet.set(j);
+          last++;
+        } else {
+          break;
+        }
+      }
+      startIndex = last;
+      if (startIndex >= numerOfRows) {
+        break;
+      }
+    }
+    return bitSet;
+  }
+
+  private BitSet setFilterdIndexToBitSetWithColumnIndexOld(FixedLengthDimensionDataChunk
dimensionColumnDataChunk,
+      int numerOfRows, byte[][] filterValues) {
+    BitSet bitSet = new BitSet(numerOfRows);
+    int start = 0;
+    int last = 0;
+    int startIndex = 0;
+    // byte[][] filterValues = dimColumnExecuterInfo.getFilterKeys();
+    for (int i = 0; i < filterValues.length; i++) {
+      start = CarbonUtil.getFirstIndexUsingBinarySearch(dimensionColumnDataChunk, startIndex,
numerOfRows - 1,
+          filterValues[i], false);
+      if (start < 0) {
+        continue;
+      }
+      bitSet.set(start);
+      last = start;
+      for (int j = start + 1; j < numerOfRows; j++) {
+        if (dimensionColumnDataChunk.compareTo(j, filterValues[i]) == 0) {
+          bitSet.set(j);
+          last++;
+        } else {
+          break;
+        }
+      }
+      startIndex = last;
+      if (startIndex >= numerOfRows) {
+        break;
+      }
+    }
+    return bitSet;
+  }
+
+  private BitSet setFilterdIndexToBitSetWithColumnIndexNew(FixedLengthDimensionDataChunk
dimensionColumnDataChunk,
+      int numerOfRows, byte[][] filterValues) {
+    BitSet bitSet = new BitSet(numerOfRows);
+    int startIndex = 0;
+    // byte[][] filterValues = dimColumnExecuterInfo.getFilterKeys();
+    for (int i = 0; i < filterValues.length; i++) {
+      int[] rangeIndex = CarbonUtil.getRangeIndexUsingBinarySearch(dimensionColumnDataChunk,
startIndex,
+          numerOfRows - 1, filterValues[i]);
+      for (int j = rangeIndex[0]; j <= rangeIndex[1]; j++) {
+
+        bitSet.set(j);
+      }
+
+      if (rangeIndex[1] > -1) {
+        startIndex = rangeIndex[1];
+      }
+    }
+    return bitSet;
+  }
+
+  @Test
+  public void testRangBinarySearch() {
+
+    long oldTime = 0;
+    long newTime = 0;
+    long start;
+    long end;
+    int dataCnt = 120000;
+    int filterCnt = 800;
+    int queryCnt = 10000;
+    int repeatCnt = 200;
+    byte[] keyWord = new byte[2];
+    FixedLengthDimensionDataChunk dimensionColumnDataChunk;
+    DimColumnExecuterFilterInfo dim = new DimColumnExecuterFilterInfo();
+
+    byte[] dataChunk = new byte[dataCnt * keyWord.length];
+    for (int i = 0; i < dataCnt; i++) {
+
+      if (i % repeatCnt == 0) {
+        repeatCnt++;
+      }
+
+      byte[] data = unsignedShortToByte2(repeatCnt);
+      dataChunk[2 * i] = data[0];
+      dataChunk[2 * i + 1] = data[1];
+
+    }
+
+    byte[][] filterKeys = new byte[filterCnt][2];
+    for (int ii = 0; ii < filterCnt; ii++) {
+      filterKeys[ii] = unsignedShortToByte2(100 + ii);
+    }
+    dim.setFilterKeys(filterKeys);
+
+    dimensionColumnDataChunk = new FixedLengthDimensionDataChunk(dataChunk, null, null,
+        dataChunk.length / keyWord.length, keyWord.length);
+
+    // initial to run
+    BitSet bitOld = this.setFilterdIndexToBitSetWithColumnIndexOld(dimensionColumnDataChunk,
dataCnt, filterKeys);
+    BitSet bitNew = this.setFilterdIndexToBitSetWithColumnIndexNew(dimensionColumnDataChunk,
dataCnt, filterKeys);
+
+    // performance run
+    for (int j = 0; j < queryCnt; j++) {
+
+      start = System.currentTimeMillis();
+      bitOld = this.setFilterdIndexToBitSetWithColumnIndexOld(dimensionColumnDataChunk, dataCnt,
filterKeys);
+      end = System.currentTimeMillis();
+      oldTime = oldTime + end - start;
+
+      start = System.currentTimeMillis();
+      bitNew = this.setFilterdIndexToBitSetWithColumnIndexNew(dimensionColumnDataChunk, dataCnt,
filterKeys);
+      end = System.currentTimeMillis();
+      newTime = newTime + end - start;
+
+      assertTrue(bitOld.equals(bitNew));
+
+    }
+
+    System.out.println("old code performance time: " + oldTime);
+    System.out.println("new code performance time: " + newTime);
+
+  }
+
+}

http://git-wip-us.apache.org/repos/asf/incubator-carbondata/blob/bedaa59e/core/src/test/java/org/apache/carbondata/core/util/CarbonUtilTest.java
----------------------------------------------------------------------
diff --git a/core/src/test/java/org/apache/carbondata/core/util/CarbonUtilTest.java b/core/src/test/java/org/apache/carbondata/core/util/CarbonUtilTest.java
index 647c2f8..9beaac7 100644
--- a/core/src/test/java/org/apache/carbondata/core/util/CarbonUtilTest.java
+++ b/core/src/test/java/org/apache/carbondata/core/util/CarbonUtilTest.java
@@ -764,7 +764,187 @@ public class CarbonUtilTest {
         .getFirstIndexUsingBinarySearch(fixedLengthDimensionDataChunk, 1, 3, compareValue,
true);
     assertEquals(2, result);
   }
+  
+  @Test
+  public void testBinaryRangeSearch() {
+
+    byte[] dataChunk = new byte[10];
+    FixedLengthDimensionDataChunk fixedLengthDimensionDataChunk;
+    byte[] keyWord = new byte[1];
+    int[] range;
+
+    dataChunk = "abbcccddddeffgggh".getBytes();
+    byte[][] dataArr = new byte[dataChunk.length / keyWord.length][keyWord.length];
+    fixedLengthDimensionDataChunk = new FixedLengthDimensionDataChunk(dataChunk, null, null,
+        dataChunk.length / keyWord.length, keyWord.length);
+
+    for (int ii = 0; ii < dataChunk.length / keyWord.length; ii++) {
+      dataArr[ii] = fixedLengthDimensionDataChunk.getChunkData(ii);
+    }
+
+    keyWord[0] = Byte.valueOf("97");
+    int[] expectRangeIndex = new int[2];
+    expectRangeIndex[0] = 0;
+    expectRangeIndex[1] = 0;
+    assertRangeIndex(dataArr, dataChunk, fixedLengthDimensionDataChunk, keyWord, expectRangeIndex);
+
+    keyWord[0] = Byte.valueOf("104");
+    expectRangeIndex = new int[2];
+    expectRangeIndex[0] = 16;
+    expectRangeIndex[1] = 16;
+    assertRangeIndex(dataArr, dataChunk, fixedLengthDimensionDataChunk, keyWord, expectRangeIndex);
+
+    keyWord[0] = Byte.valueOf("101");
+    expectRangeIndex = new int[2];
+    expectRangeIndex[0] = 10;
+    expectRangeIndex[1] = 10;
+    assertRangeIndex(dataArr, dataChunk, fixedLengthDimensionDataChunk, keyWord, expectRangeIndex);
+
+    keyWord[0] = Byte.valueOf("99");
+    expectRangeIndex = new int[2];
+    expectRangeIndex[0] = 3;
+    expectRangeIndex[1] = 5;
+    assertRangeIndex(dataArr, dataChunk, fixedLengthDimensionDataChunk, keyWord, expectRangeIndex);
+
+    dataChunk = "ab".getBytes();
+    fixedLengthDimensionDataChunk = new FixedLengthDimensionDataChunk(dataChunk, null, null,
+        dataChunk.length / keyWord.length, keyWord.length);
+
+    keyWord[0] = Byte.valueOf("97");
+    range = CarbonUtil.getRangeIndexUsingBinarySearch(fixedLengthDimensionDataChunk, 0, dataChunk.length
- 1, keyWord);
+    assertEquals(0, range[0]);
+    assertEquals(0, range[1]);
+
+    keyWord[0] = Byte.valueOf("98");
+    range = CarbonUtil.getRangeIndexUsingBinarySearch(fixedLengthDimensionDataChunk, 0, dataChunk.length
- 1, keyWord);
+    assertEquals(1, range[0]);
+    assertEquals(1, range[1]);
+
+    dataChunk = "aabb".getBytes();
+    fixedLengthDimensionDataChunk = new FixedLengthDimensionDataChunk(dataChunk, null, null,
+        dataChunk.length / keyWord.length, keyWord.length);
+
+    keyWord[0] = Byte.valueOf("97");
+    range = CarbonUtil.getRangeIndexUsingBinarySearch(fixedLengthDimensionDataChunk, 0, dataChunk.length
- 1, keyWord);
+    assertEquals(0, range[0]);
+    assertEquals(1, range[1]);
+
+    keyWord[0] = Byte.valueOf("98");
+    range = CarbonUtil.getRangeIndexUsingBinarySearch(fixedLengthDimensionDataChunk, 0, dataChunk.length
- 1, keyWord);
+    assertEquals(2, range[0]);
+    assertEquals(3, range[1]);
+
+    dataChunk = "a".getBytes();
+    fixedLengthDimensionDataChunk = new FixedLengthDimensionDataChunk(dataChunk, null, null,
+        dataChunk.length / keyWord.length, keyWord.length);
+
+    keyWord[0] = Byte.valueOf("97");
+    range = CarbonUtil.getRangeIndexUsingBinarySearch(fixedLengthDimensionDataChunk, 0, dataChunk.length
- 1, keyWord);
+    assertEquals(0, range[0]);
+    assertEquals(0, range[1]);
+
+    dataChunk = "aa".getBytes();
+    fixedLengthDimensionDataChunk = new FixedLengthDimensionDataChunk(dataChunk, null, null,
+        dataChunk.length / keyWord.length, keyWord.length);
+
+    keyWord[0] = Byte.valueOf("97");
+    range = CarbonUtil.getRangeIndexUsingBinarySearch(fixedLengthDimensionDataChunk, 0, dataChunk.length
- 1, keyWord);
+    assertEquals(0, range[0]);
+    assertEquals(1, range[1]);
+
+    dataChunk = "aabbbbbbbbbbcc".getBytes();
+    fixedLengthDimensionDataChunk = new FixedLengthDimensionDataChunk(dataChunk, null, null,
+        dataChunk.length / keyWord.length, keyWord.length);
+    keyWord[0] = Byte.valueOf("98");
+    range = CarbonUtil.getRangeIndexUsingBinarySearch(fixedLengthDimensionDataChunk, 0, dataChunk.length
- 1, keyWord);
+    assertEquals(2, range[0]);
+    assertEquals(11, range[1]);
+
+  }
+
+  @Test
+  public void IndexUsingBinarySearchLengthTwo() {
+
+    byte[] dataChunk = new byte[10];
+    FixedLengthDimensionDataChunk fixedLengthDimensionDataChunk;
+
+    byte[] keyWord = new byte[2];
+
+    dataChunk = "aabbbbbbbbbbcc".getBytes();
+    byte[][] dataArr = new byte[dataChunk.length / keyWord.length][keyWord.length];
+
+    fixedLengthDimensionDataChunk = new FixedLengthDimensionDataChunk(dataChunk, null, null,
+        dataChunk.length / keyWord.length, keyWord.length);
+
+    for (int ii = 0; ii < dataChunk.length / keyWord.length; ii++) {
+      dataArr[ii] = fixedLengthDimensionDataChunk.getChunkData(ii);
+    }
+
+    keyWord[0] = Byte.valueOf("98");
+    keyWord[1] = Byte.valueOf("98");
+    int[] expectRangeIndex = new int[2];
+    expectRangeIndex[0] = 1;
+    expectRangeIndex[1] = 5;
+    assertRangeIndex(dataArr, dataChunk, fixedLengthDimensionDataChunk, keyWord, expectRangeIndex);
+
+    keyWord[0] = Byte.valueOf("97");
+    keyWord[1] = Byte.valueOf("97");
+
+    expectRangeIndex = new int[2];
+    expectRangeIndex[0] = 0;
+    expectRangeIndex[1] = 0;
+    assertRangeIndex(dataArr, dataChunk, fixedLengthDimensionDataChunk, keyWord, expectRangeIndex);
+
+    keyWord[0] = Byte.valueOf("99");
+    keyWord[1] = Byte.valueOf("99");
+    expectRangeIndex = new int[2];
+    expectRangeIndex[0] = 6;
+    expectRangeIndex[1] = 6;
+    assertRangeIndex(dataArr, dataChunk, fixedLengthDimensionDataChunk, keyWord, expectRangeIndex);
+
+  }
+
+  @Test
+  public void IndexUsingBinarySearchLengthThree() {
+
+    byte[] dataChunk = new byte[10];
+    FixedLengthDimensionDataChunk fixedLengthDimensionDataChunk;
 
+    byte[] keyWord = new byte[3];
+
+    dataChunk = "aaabbbbbbbbbccc".getBytes();
+    byte[][] dataArr = new byte[dataChunk.length / keyWord.length][keyWord.length];
+
+    fixedLengthDimensionDataChunk = new FixedLengthDimensionDataChunk(dataChunk, null, null,
+        dataChunk.length / keyWord.length, keyWord.length);
+
+    for (int ii = 0; ii < dataChunk.length / keyWord.length; ii++) {
+      dataArr[ii] = fixedLengthDimensionDataChunk.getChunkData(ii);
+    }
+
+    keyWord[0] = Byte.valueOf("98");
+    keyWord[1] = Byte.valueOf("98");
+    keyWord[2] = Byte.valueOf("98");
+    int[] expectRangeIndex = new int[2];
+    expectRangeIndex[0] = 1;
+    expectRangeIndex[1] = 3;
+    assertRangeIndex(dataArr, dataChunk, fixedLengthDimensionDataChunk, keyWord, expectRangeIndex);
+
+  }
+
+  private void assertRangeIndex(byte[][] dataArr, byte[] dataChunk,
+      FixedLengthDimensionDataChunk fixedLengthDimensionDataChunk, byte[] keyWord, int[]
expectRangeIndex) {
+    int[] range;
+    range = CarbonUtil.getRangeIndexUsingBinarySearch(fixedLengthDimensionDataChunk, 0,
+        (dataChunk.length - 1) / keyWord.length, keyWord);
+    assertEquals(expectRangeIndex[0], range[0]);
+    assertEquals(expectRangeIndex[1], range[1]);
+
+    int index = CarbonUtil.binarySearch(dataArr, 0, dataChunk.length / keyWord.length - 1,
keyWord);
+    assertTrue(expectRangeIndex[0] <= index && index <= range[1]);
+  }
+ 	
+ 	
   @AfterClass public static void testcleanUp() {
     new File("../core/src/test/resources/testFile.txt").deleteOnExit();
     new File("../core/src/test/resources/testDatabase/levelmetadata_testTable.metadata")


Mime
View raw message