You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@kylin.apache.org by lu...@apache.org on 2015/01/15 13:26:50 UTC
[34/50] [abbrv] incubator-kylin git commit: ongoing
ongoing
Project: http://git-wip-us.apache.org/repos/asf/incubator-kylin/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-kylin/commit/b3ac6741
Tree: http://git-wip-us.apache.org/repos/asf/incubator-kylin/tree/b3ac6741
Diff: http://git-wip-us.apache.org/repos/asf/incubator-kylin/diff/b3ac6741
Branch: refs/heads/inverted-index
Commit: b3ac6741303e75144a90be924810b573d7aa55ea
Parents: b4bfe41
Author: honma <ho...@ebay.com>
Authored: Tue Jan 13 17:31:58 2015 +0800
Committer: honma <ho...@ebay.com>
Committed: Wed Jan 14 18:05:45 2015 +0800
----------------------------------------------------------------------
.../invertedindex/index/BitMapContainer.java | 30 +-
.../index/ColumnValueContainer.java | 2 +-
.../index/CompressedValueContainer.java | 327 ++++++++++---------
.../storage/filter/BitMapFilterEvaluator.java | 11 +-
.../endpoint/SliceBitMapProvider.java | 4 +-
.../filter/BitMapFilterEvaluatorTest.java | 29 ++
6 files changed, 234 insertions(+), 169 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-kylin/blob/b3ac6741/invertedindex/src/main/java/com/kylinolap/invertedindex/index/BitMapContainer.java
----------------------------------------------------------------------
diff --git a/invertedindex/src/main/java/com/kylinolap/invertedindex/index/BitMapContainer.java b/invertedindex/src/main/java/com/kylinolap/invertedindex/index/BitMapContainer.java
index 8c686b3..0b86bc2 100644
--- a/invertedindex/src/main/java/com/kylinolap/invertedindex/index/BitMapContainer.java
+++ b/invertedindex/src/main/java/com/kylinolap/invertedindex/index/BitMapContainer.java
@@ -16,6 +16,7 @@
package com.kylinolap.invertedindex.index;
+import com.kylinolap.metadata.model.ParameterDesc;
import it.uniroma3.mat.extendedset.intset.ConciseSet;
import java.nio.ByteBuffer;
@@ -74,8 +75,35 @@ public class BitMapContainer implements ColumnValueContainer {
valueBytes.set(temp, 0, valueLen);
}
+ /**
+ * if endExclusiveId == startInclusiveId + 1, the performance should be
+ * nearly as good as {@link #getBitMap(int startInclusiveId )}
+ */
@Override
- public ConciseSet getBitMap(int valueId) {
+ public ConciseSet getBitMap(int startInclusiveId, int endExclusiveId) {
+ if (startInclusiveId == endExclusiveId) {
+ //entry for getting null value
+ return sets[this.nValues];
+ }
+
+ ConciseSet ret = null;
+ for (int i = startInclusiveId; i < endExclusiveId; ++i) {
+ ConciseSet temp = getBitMap(i);
+ if (ret == null) {
+ ret = temp;
+ } else {
+ ret.addAll(temp);
+ }
+ }
+
+ if (ret != null) {
+ return ret;
+ } else {
+ return new ConciseSet();
+ }
+ }
+
+ private ConciseSet getBitMap(int valueId) {
if (valueId >= 0 && valueId <= getMaxValueId())
return sets[valueId];
else
http://git-wip-us.apache.org/repos/asf/incubator-kylin/blob/b3ac6741/invertedindex/src/main/java/com/kylinolap/invertedindex/index/ColumnValueContainer.java
----------------------------------------------------------------------
diff --git a/invertedindex/src/main/java/com/kylinolap/invertedindex/index/ColumnValueContainer.java b/invertedindex/src/main/java/com/kylinolap/invertedindex/index/ColumnValueContainer.java
index 90dae0d..0cb9957 100644
--- a/invertedindex/src/main/java/com/kylinolap/invertedindex/index/ColumnValueContainer.java
+++ b/invertedindex/src/main/java/com/kylinolap/invertedindex/index/ColumnValueContainer.java
@@ -33,7 +33,7 @@ public interface ColumnValueContainer {
// works only after closeForChange()
void getValueAt(int i, ImmutableBytesWritable valueBytes);
- ConciseSet getBitMap(int valueId);
+ ConciseSet getBitMap(int startIncludsiveId, int endExclusiveId);
int getMaxValueId();
http://git-wip-us.apache.org/repos/asf/incubator-kylin/blob/b3ac6741/invertedindex/src/main/java/com/kylinolap/invertedindex/index/CompressedValueContainer.java
----------------------------------------------------------------------
diff --git a/invertedindex/src/main/java/com/kylinolap/invertedindex/index/CompressedValueContainer.java b/invertedindex/src/main/java/com/kylinolap/invertedindex/index/CompressedValueContainer.java
index 31e96fd..043105f 100644
--- a/invertedindex/src/main/java/com/kylinolap/invertedindex/index/CompressedValueContainer.java
+++ b/invertedindex/src/main/java/com/kylinolap/invertedindex/index/CompressedValueContainer.java
@@ -19,171 +19,186 @@ package com.kylinolap.invertedindex.index;
import java.io.IOException;
import java.util.Arrays;
-import it.uniroma3.mat.extendedset.intset.ConciseSet;
import org.apache.hadoop.hbase.io.ImmutableBytesWritable;
import org.apache.hadoop.hbase.util.Bytes;
import com.kylinolap.common.util.BytesUtil;
import com.ning.compress.lzf.LZFDecoder;
import com.ning.compress.lzf.LZFEncoder;
+import it.uniroma3.mat.extendedset.intset.ConciseSet;
/**
* @author yangli9
*/
public class CompressedValueContainer implements ColumnValueContainer {
- int valueLen;
- int nValues;
- int cap;
- int size;
- byte[] uncompressed;
- byte[] compressed;
-
- public CompressedValueContainer(TableRecordInfoDigest digest, int col,
- int cap) {
- this.valueLen = digest.length(col);
- this.nValues = digest.getMaxID(col) + 1;
- this.cap = cap;
- this.size = 0;
- this.uncompressed = null;
- this.compressed = null;
- }
-
- @Override
- public void append(ImmutableBytesWritable valueBytes) {
- checkUpdateMode();
- System.arraycopy(valueBytes.get(), valueBytes.getOffset(),
- uncompressed, valueLen * size, valueLen);
- size++;
- }
-
-
- @Override
- public void getValueAt(int i, ImmutableBytesWritable valueBytes) {
- valueBytes.set(uncompressed, valueLen * i, valueLen);
- }
-
- @Override
- public ConciseSet getBitMap(int valueId) {
- createBitMapWrapperIfNecessary();
- return wrapper.getBitMap(valueId);
- }
-
- @Override
- public int getMaxValueId() {
- return nValues - 1;
- }
-
- private void checkUpdateMode() {
- if (isClosedForChange()) {
- throw new IllegalArgumentException();
- }
- if (uncompressed == null) {
- uncompressed = new byte[valueLen * cap];
- }
- }
-
- private boolean isClosedForChange() {
- return compressed != null;
- }
-
- @Override
- public void closeForChange() {
- checkUpdateMode();
- try {
- compressed = LZFEncoder.encode(uncompressed, 0, valueLen * size);
- } catch (Exception e) {
- throw new RuntimeException("LZF encode failure", e);
- }
- }
-
- @Override
- public int getSize() {
- return size;
- }
-
- public ImmutableBytesWritable toBytes() {
- if (isClosedForChange() == false)
- closeForChange();
- return new ImmutableBytesWritable(compressed);
- }
-
- public void fromBytes(ImmutableBytesWritable bytes) {
- try {
- uncompressed = LZFDecoder.decode(bytes.get(), bytes.getOffset(),
- bytes.getLength());
- } catch (IOException e) {
- throw new RuntimeException("LZF decode failure", e);
- }
- size = cap = uncompressed.length / valueLen;
- compressed = BytesUtil.EMPTY_BYTE_ARRAY; // mark closed
- }
-
- @Override
- public int hashCode() {
- final int prime = 31;
- int result = 1;
- result = prime * result + size;
- result = prime * result + valueLen;
- result = prime * result + Arrays.hashCode(uncompressed);
- return result;
- }
-
- @Override
- public boolean equals(Object obj) {
- if (this == obj)
- return true;
- if (obj == null)
- return false;
- if (getClass() != obj.getClass())
- return false;
- CompressedValueContainer other = (CompressedValueContainer) obj;
- if (size != other.size)
- return false;
- if (valueLen != other.valueLen)
- return false;
- if (!Bytes.equals(uncompressed, 0, size * valueLen, uncompressed, 0,
- size * valueLen))
- return false;
- return true;
- }
-
- private BitmapWrapper wrapper = null;
-
- private void createBitMapWrapperIfNecessary() {
- if (wrapper == null)
- wrapper = new BitmapWrapper();
- }
-
- private class BitmapWrapper {
- private ConciseSet[] sets;
-
- BitmapWrapper() {
- sets = new ConciseSet[nValues + 1];
- for (int i = 0; i < sets.length; ++i) {
- sets[i] = new ConciseSet();
- }
-
- for (int i = 0; i < size; ++i) {
- int valueID = BytesUtil.readUnsigned(uncompressed,
- i * valueLen, valueLen);
- if (notNullValue(valueID)) {
- sets[valueID].add(i);
- } else {
- sets[nValues].add(i);
- }
- }
- }
-
- private boolean notNullValue(int valueId) {
- return valueId >= 0 && valueId <= getMaxValueId();
- }
-
- ConciseSet getBitMap(int valueId) {
- if (notNullValue(valueId)) {
- return sets[valueId];
- } else {
- return sets[nValues];
- }
- }
- }
+ int valueLen;
+ int nValues;
+ int cap;
+ int size;
+ byte[] uncompressed;
+ byte[] compressed;
+
+ public CompressedValueContainer(TableRecordInfoDigest digest, int col, int cap) {
+ this.valueLen = digest.length(col);
+ this.nValues = digest.getMaxID(col) + 1;
+ this.cap = cap;
+ this.size = 0;
+ this.uncompressed = null;
+ this.compressed = null;
+ }
+
+ @Override
+ public void append(ImmutableBytesWritable valueBytes) {
+ checkUpdateMode();
+ System.arraycopy(valueBytes.get(), valueBytes.getOffset(), uncompressed, valueLen * size, valueLen);
+ size++;
+ }
+
+ @Override
+ public void getValueAt(int i, ImmutableBytesWritable valueBytes) {
+ valueBytes.set(uncompressed, valueLen * i, valueLen);
+ }
+
+ @Override
+ public ConciseSet getBitMap(int startInclusiveId, int endExclusiveId) {
+ ConciseSet ret = new ConciseSet();
+
+ if (startInclusiveId == endExclusiveId) {
+ //entry for getting null values
+ int nullId = com.kylinolap.dict.Dictionary.NULL_ID[valueLen];
+ for (int i = 0; i < size; ++i) {
+ int valueID = BytesUtil.readUnsigned(uncompressed, i * valueLen, valueLen);
+ if (nullId == valueID) {
+ ret.add(i);
+ }
+ }
+ return ret;
+ }
+
+ //normal values
+ for (int i = 0; i < size; ++i) {
+ int valueID = BytesUtil.readUnsigned(uncompressed, i * valueLen, valueLen);
+ if (valueID >= startInclusiveId && valueID < endExclusiveId) {
+ ret.add(i);
+ }
+ }
+ return ret;
+
+ }
+
+ @Override
+ public int getMaxValueId() {
+ return nValues - 1;
+ }
+
+ private void checkUpdateMode() {
+ if (isClosedForChange()) {
+ throw new IllegalArgumentException();
+ }
+ if (uncompressed == null) {
+ uncompressed = new byte[valueLen * cap];
+ }
+ }
+
+ private boolean isClosedForChange() {
+ return compressed != null;
+ }
+
+ @Override
+ public void closeForChange() {
+ checkUpdateMode();
+ try {
+ compressed = LZFEncoder.encode(uncompressed, 0, valueLen * size);
+ } catch (Exception e) {
+ throw new RuntimeException("LZF encode failure", e);
+ }
+ }
+
+ @Override
+ public int getSize() {
+ return size;
+ }
+
+ public ImmutableBytesWritable toBytes() {
+ if (isClosedForChange() == false)
+ closeForChange();
+ return new ImmutableBytesWritable(compressed);
+ }
+
+ public void fromBytes(ImmutableBytesWritable bytes) {
+ try {
+ uncompressed = LZFDecoder.decode(bytes.get(), bytes.getOffset(), bytes.getLength());
+ } catch (IOException e) {
+ throw new RuntimeException("LZF decode failure", e);
+ }
+ size = cap = uncompressed.length / valueLen;
+ compressed = BytesUtil.EMPTY_BYTE_ARRAY; // mark closed
+ }
+
+ @Override
+ public int hashCode() {
+ final int prime = 31;
+ int result = 1;
+ result = prime * result + size;
+ result = prime * result + valueLen;
+ result = prime * result + Arrays.hashCode(uncompressed);
+ return result;
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (this == obj)
+ return true;
+ if (obj == null)
+ return false;
+ if (getClass() != obj.getClass())
+ return false;
+ CompressedValueContainer other = (CompressedValueContainer) obj;
+ if (size != other.size)
+ return false;
+ if (valueLen != other.valueLen)
+ return false;
+ if (!Bytes.equals(uncompressed, 0, size * valueLen, uncompressed, 0, size * valueLen))
+ return false;
+ return true;
+ }
+
+ private BitmapWrapper wrapper = null;
+
+ private void createBitMapWrapperIfNecessary() {
+ if (wrapper == null)
+ wrapper = new BitmapWrapper();
+ }
+
+ private class BitmapWrapper {
+ private ConciseSet[] sets;
+
+ BitmapWrapper() {
+ sets = new ConciseSet[nValues + 1];
+ for (int i = 0; i < sets.length; ++i) {
+ sets[i] = new ConciseSet();
+ }
+
+ for (int i = 0; i < size; ++i) {
+ int valueID = BytesUtil.readUnsigned(uncompressed, i * valueLen, valueLen);
+ if (notNullValue(valueID)) {
+ sets[valueID].add(i);
+ } else {
+ sets[nValues].add(i);
+ }
+ }
+ }
+
+ private boolean notNullValue(int valueId) {
+ return valueId >= 0 && valueId <= getMaxValueId();
+ }
+
+ ConciseSet getBitMap(int valueId) {
+ if (notNullValue(valueId)) {
+ return sets[valueId];
+ } else {
+ return sets[nValues];
+ }
+ }
+ }
}
http://git-wip-us.apache.org/repos/asf/incubator-kylin/blob/b3ac6741/storage/src/main/java/com/kylinolap/storage/filter/BitMapFilterEvaluator.java
----------------------------------------------------------------------
diff --git a/storage/src/main/java/com/kylinolap/storage/filter/BitMapFilterEvaluator.java b/storage/src/main/java/com/kylinolap/storage/filter/BitMapFilterEvaluator.java
index 8f249e6..b857432 100644
--- a/storage/src/main/java/com/kylinolap/storage/filter/BitMapFilterEvaluator.java
+++ b/storage/src/main/java/com/kylinolap/storage/filter/BitMapFilterEvaluator.java
@@ -21,7 +21,7 @@ public class BitMapFilterEvaluator {
public static interface BitMapProvider {
/** return records whose specified column having specified value */
- ConciseSet getBitMap(TblColRef col, int valueId);
+ ConciseSet getBitMap(TblColRef col, int startIncludsiveId, int endExclusiveId);
/** return the size of the group */
int getRecordCount();
@@ -101,14 +101,7 @@ public class BitMapFilterEvaluator {
}
private ConciseSet collectRange(TblColRef column, int from, int to) {
- ConciseSet set = new ConciseSet();
- for (int i = from; i <= to; i++) {
- ConciseSet bitMap = provider.getBitMap(column, i);
- if (bitMap == null)
- return null;
- set.addAll(bitMap);
- }
- return set;
+ return provider.getBitMap(column,from,to+1);
}
private ConciseSet evalCompareEqual(CompareTupleFilter filter) {
http://git-wip-us.apache.org/repos/asf/incubator-kylin/blob/b3ac6741/storage/src/main/java/com/kylinolap/storage/hbase/coprocessor/endpoint/SliceBitMapProvider.java
----------------------------------------------------------------------
diff --git a/storage/src/main/java/com/kylinolap/storage/hbase/coprocessor/endpoint/SliceBitMapProvider.java b/storage/src/main/java/com/kylinolap/storage/hbase/coprocessor/endpoint/SliceBitMapProvider.java
index 0cf39bc..5535a4e 100644
--- a/storage/src/main/java/com/kylinolap/storage/hbase/coprocessor/endpoint/SliceBitMapProvider.java
+++ b/storage/src/main/java/com/kylinolap/storage/hbase/coprocessor/endpoint/SliceBitMapProvider.java
@@ -22,8 +22,8 @@ public class SliceBitMapProvider implements BitMapFilterEvaluator.BitMapProvider
}
@Override
- public ConciseSet getBitMap(TblColRef col, int valueId) {
- return slice.getColumnValueContainer(type.getColIndexByTblColRef(col)).getBitMap(valueId);
+ public ConciseSet getBitMap(TblColRef col, int startIncludsiveId, int endExclusiveId) {
+ return slice.getColumnValueContainer(type.getColIndexByTblColRef(col)).getBitMap(startIncludsiveId,endExclusiveId);
}
@Override
http://git-wip-us.apache.org/repos/asf/incubator-kylin/blob/b3ac6741/storage/src/test/java/com/kylinolap/storage/filter/BitMapFilterEvaluatorTest.java
----------------------------------------------------------------------
diff --git a/storage/src/test/java/com/kylinolap/storage/filter/BitMapFilterEvaluatorTest.java b/storage/src/test/java/com/kylinolap/storage/filter/BitMapFilterEvaluatorTest.java
index 5d3f012..3c14fae 100644
--- a/storage/src/test/java/com/kylinolap/storage/filter/BitMapFilterEvaluatorTest.java
+++ b/storage/src/test/java/com/kylinolap/storage/filter/BitMapFilterEvaluatorTest.java
@@ -43,6 +43,35 @@ public class BitMapFilterEvaluatorTest {
private static final int REC_COUNT = 10;
@Override
+ public ConciseSet getBitMap(TblColRef col, int startInclusiveId, int endExclusiveId) {
+ if (!col.equals(colA))
+ return null;
+
+ // i-th record has value ID i, and last record has value null
+ if (startInclusiveId == endExclusiveId) {
+ //entry for getting null value
+ ConciseSet s = new ConciseSet();
+ s.add(getRecordCount() - 1);
+ return s;
+ }
+
+ ConciseSet ret = null;
+ for (int i = startInclusiveId; i < endExclusiveId; ++i) {
+ ConciseSet temp = getBitMap(col,i);
+ if (ret == null) {
+ ret = temp;
+ } else {
+ ret.addAll(temp);
+ }
+ }
+
+ if (ret != null) {
+ return ret;
+ } else {
+ return new ConciseSet();
+ }
+ }
+
public ConciseSet getBitMap(TblColRef col, int valueId) {
if (!col.equals(colA))
return null;