You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@hive.apache.org by px...@apache.org on 2017/07/15 08:07:01 UTC
[22/24] hive git commit: HIVE-16996: Add HLL as an alternative to FM
sketch to compute stats (Pengcheng Xiong, reviewed by Ashutosh Chauhan,
Prasanth Jayachandran)
http://git-wip-us.apache.org/repos/asf/hive/blob/b883d313/common/src/java/org/apache/hadoop/hive/common/ndv/hll/HLLRegister.java
----------------------------------------------------------------------
diff --git a/common/src/java/org/apache/hadoop/hive/common/ndv/hll/HLLRegister.java b/common/src/java/org/apache/hadoop/hive/common/ndv/hll/HLLRegister.java
new file mode 100644
index 0000000..eefc60f
--- /dev/null
+++ b/common/src/java/org/apache/hadoop/hive/common/ndv/hll/HLLRegister.java
@@ -0,0 +1,50 @@
+/**
+ * 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.hadoop.hive.common.ndv.hll;
+
+public interface HLLRegister {
+
+ /**
+ * Specify a hashcode to add to hyperloglog register.
+ * @param hashcode
+ * - hashcode to add
+ * @return true if register value is updated else false
+ */
+ public boolean add(long hashcode);
+
+ /**
+ * Instead of specifying hashcode, this interface can be used to directly
+ * specify the register index and register value. This interface is useful
+ * when reconstructing hyperloglog from a serialized representation where its
+ * not possible to regenerate the hashcode.
+ * @param idx
+ * - register index
+ * @param value
+ * - register value
+ * @return true if register value is updated else false
+ */
+ public boolean set(int idx, byte value);
+
+ /**
+ * Merge hyperloglog registers of the same type (SPARSE or DENSE register)
+ * @param reg
+ * - register to be merged
+ */
+ public void merge(HLLRegister reg);
+}
http://git-wip-us.apache.org/repos/asf/hive/blob/b883d313/common/src/java/org/apache/hadoop/hive/common/ndv/hll/HLLSparseRegister.java
----------------------------------------------------------------------
diff --git a/common/src/java/org/apache/hadoop/hive/common/ndv/hll/HLLSparseRegister.java b/common/src/java/org/apache/hadoop/hive/common/ndv/hll/HLLSparseRegister.java
new file mode 100644
index 0000000..a4a5ba9
--- /dev/null
+++ b/common/src/java/org/apache/hadoop/hive/common/ndv/hll/HLLSparseRegister.java
@@ -0,0 +1,260 @@
+/**
+ * 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.hadoop.hive.common.ndv.hll;
+
+import java.util.Map;
+import java.util.TreeMap;
+
+public class HLLSparseRegister implements HLLRegister {
+
+ private TreeMap<Integer,Byte> sparseMap;
+
+ // for a better insertion performance values are added to temporary unsorted
+ // list which will be merged to sparse map after a threshold
+ private int[] tempList;
+ private int tempListIdx;
+
+ // number of register bits
+ private final int p;
+
+ // new number of register bits for higher accuracy
+ private final int pPrime;
+
+ // number of bits to store the number of zero runs
+ private final int qPrime;
+
+ // masks for quicker extraction of p, pPrime, qPrime values
+ private final int mask;
+ private final int pPrimeMask;
+ private final int qPrimeMask;
+
+ public HLLSparseRegister(int p, int pp, int qp) {
+ this.p = p;
+ this.sparseMap = new TreeMap<Integer,Byte>();
+ this.tempList = new int[HLLConstants.TEMP_LIST_DEFAULT_SIZE];
+ this.tempListIdx = 0;
+ this.pPrime = pp;
+ this.qPrime = qp;
+ this.mask = ((1 << pPrime) - 1) ^ ((1 << p) - 1);
+ this.pPrimeMask = ((1 << pPrime) - 1);
+ this.qPrimeMask = (1 << qPrime) - 1;
+ }
+
+ public boolean add(long hashcode) {
+ boolean updated = false;
+
+ // fill the temp list before merging to sparse map
+ if (tempListIdx < tempList.length) {
+ int encodedHash = encodeHash(hashcode);
+ tempList[tempListIdx++] = encodedHash;
+ updated = true;
+ } else {
+ updated = mergeTempListToSparseMap();
+ }
+
+ return updated;
+ }
+
+ /**
+ * Adds temp list to sparse map. The key for sparse map entry is the register
+ * index determined by pPrime and value is the number of trailing zeroes.
+ * @return
+ */
+ private boolean mergeTempListToSparseMap() {
+ boolean updated = false;
+ for (int i = 0; i < tempListIdx; i++) {
+ int encodedHash = tempList[i];
+ int key = encodedHash & pPrimeMask;
+ byte value = (byte) (encodedHash >>> pPrime);
+ byte nr = 0;
+ // if MSB is set to 1 then next qPrime MSB bits contains the value of
+ // number of zeroes.
+ // if MSB is set to 0 then number of zeroes is contained within pPrime - p
+ // bits.
+ if (encodedHash < 0) {
+ nr = (byte) (value & qPrimeMask);
+ } else {
+ nr = (byte) (Integer.numberOfTrailingZeros(encodedHash >>> p) + 1);
+ }
+ updated = set(key, nr);
+ }
+
+ // reset temp list index
+ tempListIdx = 0;
+ return updated;
+ }
+
+ /**
+ * <pre>
+ * <b>Input:</b> 64 bit hashcode
+ *
+ * |---------w-------------| |------------p'----------|
+ * 10101101.......1010101010 10101010101 01010101010101
+ * |------p-----|
+ *
+ * <b>Output:</b> 32 bit int
+ *
+ * |b| |-q'-| |------------p'----------|
+ * 1 010101 01010101010 10101010101010
+ * |------p-----|
+ *
+ *
+ * The default values of p', q' and b are 25, 6, 1 (total 32 bits) respectively.
+ * This function will return an int encoded in the following format
+ *
+ * p - LSB p bits represent the register index
+ * p' - LSB p' bits are used for increased accuracy in estimation
+ * q' - q' bits after p' are left as such from the hashcode if b = 0 else
+ * q' bits encodes the longest trailing zero runs from in (w-p) input bits
+ * b - 0 if longest trailing zero run is contained within (p'-p) bits
+ * 1 if longest trailing zero run is computeed from (w-p) input bits and
+ * its value is stored in q' bits
+ * </pre>
+ * @param hashcode
+ * @return
+ */
+ public int encodeHash(long hashcode) {
+ // x = p' - p
+ int x = (int) (hashcode & mask);
+ if (x == 0) {
+ // more bits should be considered for finding q (longest zero runs)
+ // set MSB to 1
+ int ntr = Long.numberOfTrailingZeros(hashcode >> p) + 1;
+ long newHashCode = hashcode & pPrimeMask;
+ newHashCode |= ntr << pPrime;
+ newHashCode |= 0x80000000;
+ return (int) newHashCode;
+ } else {
+ // q is contained within p' - p
+ // set MSB to 0
+ return (int) (hashcode & 0x7FFFFFFF);
+ }
+ }
+
+ public int getSize() {
+
+ // merge temp list before getting the size of sparse map
+ if (tempListIdx != 0) {
+ mergeTempListToSparseMap();
+ }
+ return sparseMap.size();
+ }
+
+ public void merge(HLLRegister hllRegister) {
+ if (hllRegister instanceof HLLSparseRegister) {
+ HLLSparseRegister hsr = (HLLSparseRegister) hllRegister;
+
+ // retain only the largest value for a register index
+ for (Map.Entry<Integer, Byte> entry : hsr.getSparseMap().entrySet()) {
+ int key = entry.getKey();
+ byte value = entry.getValue();
+ set(key, value);
+ }
+ } else {
+ throw new IllegalArgumentException("Specified register not instance of HLLSparseRegister");
+ }
+ }
+
+ public boolean set(int key, byte value) {
+ boolean updated = false;
+
+ // retain only the largest value for a register index
+ if (sparseMap.containsKey(key)) {
+ byte containedVal = sparseMap.get(key);
+ if (value > containedVal) {
+ sparseMap.put(key, value);
+ updated = true;
+ }
+ } else {
+ sparseMap.put(key, value);
+ updated = true;
+ }
+ return updated;
+ }
+
+ public TreeMap<Integer,Byte> getSparseMap() {
+ return sparseMap;
+ }
+
+ public TreeMap<Integer,Byte> getMergedSparseMap() {
+ if (tempListIdx != 0) {
+ mergeTempListToSparseMap();
+ }
+ return sparseMap;
+ }
+
+ public int getP() {
+ return p;
+ }
+
+ public int getPPrime() {
+ return pPrime;
+ }
+
+ @Override
+ public String toString() {
+ StringBuilder sb = new StringBuilder();
+ sb.append("HLLSparseRegister - ");
+ sb.append("p: ");
+ sb.append(p);
+ sb.append(" pPrime: ");
+ sb.append(pPrime);
+ sb.append(" qPrime: ");
+ sb.append(qPrime);
+ return sb.toString();
+ }
+
+ public String toExtendedString() {
+ return toString() + " register: " + sparseMap.toString();
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (!(obj instanceof HLLSparseRegister)) {
+ return false;
+ }
+ HLLSparseRegister other = (HLLSparseRegister) obj;
+ boolean result = p == other.p && pPrime == other.pPrime && qPrime == other.qPrime
+ && tempListIdx == other.tempListIdx;
+ if (result) {
+ for (int i = 0; i < tempListIdx; i++) {
+ if (tempList[i] != other.tempList[i]) {
+ return false;
+ }
+ }
+
+ result = result && sparseMap.equals(other.sparseMap);
+ }
+ return result;
+ }
+
+ @Override
+ public int hashCode() {
+ int hashcode = 0;
+ hashcode += 31 * p;
+ hashcode += 31 * pPrime;
+ hashcode += 31 * qPrime;
+ for (int i = 0; i < tempListIdx; i++) {
+ hashcode += 31 * tempList[tempListIdx];
+ }
+ hashcode += sparseMap.hashCode();
+ return hashcode;
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/hive/blob/b883d313/common/src/java/org/apache/hadoop/hive/common/ndv/hll/HyperLogLog.java
----------------------------------------------------------------------
diff --git a/common/src/java/org/apache/hadoop/hive/common/ndv/hll/HyperLogLog.java b/common/src/java/org/apache/hadoop/hive/common/ndv/hll/HyperLogLog.java
new file mode 100644
index 0000000..d195546
--- /dev/null
+++ b/common/src/java/org/apache/hadoop/hive/common/ndv/hll/HyperLogLog.java
@@ -0,0 +1,629 @@
+/**
+ * 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.hadoop.hive.common.ndv.hll;
+
+import java.io.ByteArrayInputStream;
+import java.io.ByteArrayOutputStream;
+import java.io.IOException;
+import java.io.InputStream;
+import java.nio.ByteBuffer;
+import java.nio.charset.Charset;
+import java.util.Map;
+import java.util.TreeMap;
+
+import org.apache.commons.codec.binary.Base64;
+import org.apache.hadoop.hive.common.ndv.NumDistinctValueEstimator;
+import org.apache.hadoop.hive.common.type.HiveDecimal;
+import org.apache.hadoop.hive.ql.util.JavaDataModel;
+import org.apache.hive.common.util.Murmur3;
+
+/**
+ * <pre>
+ * This is an implementation of the following variants of hyperloglog (HLL)
+ * algorithm
+ * Original - Original HLL algorithm from Flajolet et. al from
+ * http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf
+ * HLLNoBias - Google's implementation of bias correction based on lookup table
+ * http://static.googleusercontent.com/media/research.google.com/en//pubs/archive/40671.pdf
+ * HLL++ - Google's implementation of HLL++ algorithm that uses SPARSE registers
+ * http://static.googleusercontent.com/media/research.google.com/en//pubs/archive/40671.pdf
+ *
+ * Following are the constructor parameters that determines which algorithm is
+ * used
+ * <b>numRegisterIndexBits</b> - number of LSB hashcode bits to be used as register index.
+ * <i>Default is 14</i>. min = 4 and max = 16
+ * <b>numHashBits</b> - number of bits for hashcode. <i>Default is 64</i>. min = 32 and max = 128
+ * <b>encoding</b> - Type of encoding to use (SPARSE or DENSE). The algorithm automatically
+ * switches to DENSE beyond a threshold. <i>Default: SPARSE</i>
+ * <b>enableBitPacking</b> - To enable bit packing or not. Bit packing improves compression
+ * at the cost of more CPU cycles. <i>Default: true</i>
+ * <b>noBias</b> - Use Google's bias table lookup for short range bias correction.
+ * Enabling this will highly improve the estimation accuracy for short
+ * range values. <i>Default: true</i>
+ *
+ * </pre>
+ */
+public class HyperLogLog implements NumDistinctValueEstimator{
+ private final static int DEFAULT_HASH_BITS = 64;
+ private final static long HASH64_ZERO = Murmur3.hash64(new byte[] {0});
+ private final static long HASH64_ONE = Murmur3.hash64(new byte[] {1});
+ private final static ByteBuffer SHORT_BUFFER = ByteBuffer.allocate(Short.BYTES);
+ private final static ByteBuffer INT_BUFFER = ByteBuffer.allocate(Integer.BYTES);
+ private final static ByteBuffer LONG_BUFFER = ByteBuffer.allocate(Long.BYTES);
+
+ public enum EncodingType {
+ SPARSE, DENSE
+ }
+
+ // number of bits to address registers
+ private final int p;
+
+ // number of registers - 2^p
+ private final int m;
+
+ // refer paper
+ private float alphaMM;
+
+ // enable/disable bias correction using table lookup
+ private final boolean noBias;
+
+ // enable/disable bitpacking
+ private final boolean bitPacking;
+
+ // Not making it configurable for perf reasons (avoid checks)
+ private final int chosenHashBits = DEFAULT_HASH_BITS;
+
+ private HLLDenseRegister denseRegister;
+ private HLLSparseRegister sparseRegister;
+
+ // counts are cached to avoid repeated complex computation. If register value
+ // is updated the count will be computed again.
+ private long cachedCount;
+ private boolean invalidateCount;
+
+ private EncodingType encoding;
+
+ // threshold to switch from SPARSE to DENSE encoding
+ private int encodingSwitchThreshold;
+
+ private HyperLogLog(HyperLogLogBuilder hllBuilder) {
+ if (hllBuilder.numRegisterIndexBits < HLLConstants.MIN_P_VALUE
+ || hllBuilder.numRegisterIndexBits > HLLConstants.MAX_P_VALUE) {
+ throw new IllegalArgumentException("p value should be between " + HLLConstants.MIN_P_VALUE
+ + " to " + HLLConstants.MAX_P_VALUE);
+ }
+ this.p = hllBuilder.numRegisterIndexBits;
+ this.m = 1 << p;
+ this.noBias = hllBuilder.noBias;
+ this.bitPacking = hllBuilder.bitPacking;
+
+ // the threshold should be less than 12K bytes for p = 14.
+ // The reason to divide by 5 is, in sparse mode after serialization the
+ // entriesin sparse map are compressed, and delta encoded as varints. The
+ // worst case size of varints are 5 bytes. Hence, 12K/5 ~= 2400 entries in
+ // sparse map.
+ if (bitPacking) {
+ this.encodingSwitchThreshold = ((m * 6) / 8) / 5;
+ } else {
+ // if bitpacking is disabled, all register values takes 8 bits and hence
+ // we can be more flexible with the threshold. For p=14, 16K/5 = 3200
+ // entries in sparse map can be allowed.
+ this.encodingSwitchThreshold = m / 3;
+ }
+
+ // initializeAlpha(DEFAULT_HASH_BITS);
+ // alphaMM value for 128 bits hash seems to perform better for default 64 hash bits
+ this.alphaMM = 0.7213f / (1 + 1.079f / m);
+ // For efficiency alpha is multiplied by m^2
+ this.alphaMM = this.alphaMM * m * m;
+
+ this.cachedCount = -1;
+ this.invalidateCount = false;
+ this.encoding = hllBuilder.encoding;
+ if (encoding.equals(EncodingType.SPARSE)) {
+ this.sparseRegister = new HLLSparseRegister(p, HLLConstants.P_PRIME_VALUE,
+ HLLConstants.Q_PRIME_VALUE);
+ this.denseRegister = null;
+ } else {
+ this.sparseRegister = null;
+ this.denseRegister = new HLLDenseRegister(p, bitPacking);
+ }
+ }
+
+ public static HyperLogLogBuilder builder() {
+ return new HyperLogLogBuilder();
+ }
+
+ public static class HyperLogLogBuilder {
+ private int numRegisterIndexBits = 14;
+ private EncodingType encoding = EncodingType.SPARSE;
+ private boolean bitPacking = true;
+ private boolean noBias = true;
+
+ public HyperLogLogBuilder() {
+ }
+
+ public HyperLogLogBuilder setNumRegisterIndexBits(int b) {
+ this.numRegisterIndexBits = b;
+ return this;
+ }
+
+ public HyperLogLogBuilder setEncoding(EncodingType enc) {
+ this.encoding = enc;
+ return this;
+ }
+
+ public HyperLogLogBuilder enableBitPacking(boolean b) {
+ this.bitPacking = b;
+ return this;
+ }
+
+ public HyperLogLogBuilder enableNoBias(boolean nb) {
+ this.noBias = nb;
+ return this;
+ }
+
+ public HyperLogLog build() {
+ return new HyperLogLog(this);
+ }
+ }
+
+ // see paper for alpha initialization.
+ private void initializeAlpha(final int hashBits) {
+ if (hashBits <= 16) {
+ alphaMM = 0.673f;
+ } else if (hashBits <= 32) {
+ alphaMM = 0.697f;
+ } else if (hashBits <= 64) {
+ alphaMM = 0.709f;
+ } else {
+ alphaMM = 0.7213f / (float) (1 + 1.079f / m);
+ }
+
+ // For efficiency alpha is multiplied by m^2
+ alphaMM = alphaMM * m * m;
+ }
+
+ public void addBoolean(boolean val) {
+ add(val ? HASH64_ONE : HASH64_ZERO);
+ }
+
+ public void addByte(byte val) {
+ add(Murmur3.hash64(new byte[] {val}));
+ }
+
+ public void addBytes(byte[] val) {
+ add(Murmur3.hash64(val));
+ }
+
+ public void addShort(short val) {
+ SHORT_BUFFER.putShort(0, val);
+ add(Murmur3.hash64(SHORT_BUFFER.array()));
+ }
+
+ public void addInt(int val) {
+ INT_BUFFER.putInt(0, val);
+ add(Murmur3.hash64(INT_BUFFER.array()));
+ }
+
+ public void addLong(long val) {
+ LONG_BUFFER.putLong(0, val);
+ add(Murmur3.hash64(LONG_BUFFER.array()));
+ }
+
+ public void addFloat(float val) {
+ INT_BUFFER.putFloat(0, val);
+ add(Murmur3.hash64(INT_BUFFER.array()));
+ }
+
+ public void addDouble(double val) {
+ LONG_BUFFER.putDouble(0, val);
+ add(Murmur3.hash64(LONG_BUFFER.array()));
+ }
+
+ public void addChar(char val) {
+ SHORT_BUFFER.putChar(0, val);
+ add(Murmur3.hash64(SHORT_BUFFER.array()));
+ }
+
+ /**
+ * Java's default charset will be used for strings.
+ * @param val
+ * - input string
+ */
+ public void addString(String val) {
+ add(Murmur3.hash64(val.getBytes()));
+ }
+
+ public void addString(String val, Charset charset) {
+ add(Murmur3.hash64(val.getBytes(charset)));
+ }
+
+ public void add(long hashcode) {
+ if (encoding.equals(EncodingType.SPARSE)) {
+ if (sparseRegister.add(hashcode)) {
+ invalidateCount = true;
+ }
+
+ // if size of sparse map excess the threshold convert the sparse map to
+ // dense register and switch to DENSE encoding
+ if (sparseRegister.getSize() > encodingSwitchThreshold) {
+ encoding = EncodingType.DENSE;
+ denseRegister = sparseToDenseRegister(sparseRegister);
+ sparseRegister = null;
+ invalidateCount = true;
+ }
+ } else {
+ if (denseRegister.add(hashcode)) {
+ invalidateCount = true;
+ }
+ }
+ }
+
+ public long estimateNumDistinctValues() {
+ return count();
+ }
+
+ public long count() {
+ // compute count only if the register values are updated else return the
+ // cached count
+ if (invalidateCount || cachedCount < 0) {
+ if (encoding.equals(EncodingType.SPARSE)) {
+
+ // if encoding is still SPARSE use linear counting with increase
+ // accuracy (as we use pPrime bits for register index)
+ int mPrime = 1 << sparseRegister.getPPrime();
+ cachedCount = linearCount(mPrime, mPrime - sparseRegister.getSize());
+ } else {
+
+ // for DENSE encoding, use bias table lookup for HLLNoBias algorithm
+ // else fallback to HLLOriginal algorithm
+ double sum = denseRegister.getSumInversePow2();
+ long numZeros = denseRegister.getNumZeroes();
+
+ // cardinality estimate from normalized bias corrected harmonic mean on
+ // the registers
+ cachedCount = (long) (alphaMM * (1.0 / sum));
+ long pow = (long) Math.pow(2, chosenHashBits);
+
+ // when bias correction is enabled
+ if (noBias) {
+ cachedCount = cachedCount <= 5 * m ? (cachedCount - estimateBias(cachedCount))
+ : cachedCount;
+ long h = cachedCount;
+ if (numZeros != 0) {
+ h = linearCount(m, numZeros);
+ }
+
+ if (h < getThreshold()) {
+ cachedCount = h;
+ }
+ } else {
+ // HLL algorithm shows stronger bias for values in (2.5 * m) range.
+ // To compensate for this short range bias, linear counting is used
+ // for values before this short range. The original paper also says
+ // similar bias is seen for long range values due to hash collisions
+ // in range >1/30*(2^32). For the default case, we do not have to
+ // worry about this long range bias as the paper used 32-bit hashing
+ // and we use 64-bit hashing as default. 2^64 values are too high to
+ // observe long range bias (hash collisions).
+ if (cachedCount <= 2.5 * m) {
+
+ // for short range use linear counting
+ if (numZeros != 0) {
+ cachedCount = linearCount(m, numZeros);
+ }
+ } else if (chosenHashBits < 64 && cachedCount > (0.033333 * pow)) {
+
+ // long range bias for 32-bit hashcodes
+ if (cachedCount > (1 / 30) * pow) {
+ cachedCount = (long) (-pow * Math.log(1.0 - (double) cachedCount / (double) pow));
+ }
+ }
+ }
+ }
+ invalidateCount = false;
+ }
+
+ return cachedCount;
+ }
+
+ private long getThreshold() {
+ return (long) (HLLConstants.thresholdData[p - 4] + 0.5);
+ }
+
+ /**
+ * Estimate bias from lookup table
+ * @param count
+ * - cardinality before bias correction
+ * @return cardinality after bias correction
+ */
+ private long estimateBias(long count) {
+ double[] rawEstForP = HLLConstants.rawEstimateData[p - 4];
+
+ // compute distance and store it in sorted map
+ TreeMap<Double,Integer> estIndexMap = new TreeMap<>();
+ double distance = 0;
+ for (int i = 0; i < rawEstForP.length; i++) {
+ distance = Math.pow(count - rawEstForP[i], 2);
+ estIndexMap.put(distance, i);
+ }
+
+ // take top-k closest neighbors and compute the bias corrected cardinality
+ long result = 0;
+ double[] biasForP = HLLConstants.biasData[p - 4];
+ double biasSum = 0;
+ int kNeighbors = HLLConstants.K_NEAREST_NEIGHBOR;
+ for (Map.Entry<Double, Integer> entry : estIndexMap.entrySet()) {
+ biasSum += biasForP[entry.getValue()];
+ kNeighbors--;
+ if (kNeighbors <= 0) {
+ break;
+ }
+ }
+
+ // 0.5 added for rounding off
+ result = (long) ((biasSum / HLLConstants.K_NEAREST_NEIGHBOR) + 0.5);
+ return result;
+ }
+
+ public void setCount(long count) {
+ this.cachedCount = count;
+ this.invalidateCount = true;
+ }
+
+ private long linearCount(int mVal, long numZeros) {
+ return (long) (Math.round(mVal * Math.log(mVal / ((double) numZeros))));
+ }
+
+ // refer paper
+ public double getStandardError() {
+ return 1.04 / Math.sqrt(m);
+ }
+
+ public HLLDenseRegister getHLLDenseRegister() {
+ return denseRegister;
+ }
+
+ public HLLSparseRegister getHLLSparseRegister() {
+ return sparseRegister;
+ }
+
+ /**
+ * Reconstruct sparse map from serialized integer list
+ * @param reg
+ * - uncompressed and delta decoded integer list
+ */
+ public void setHLLSparseRegister(int[] reg) {
+ for (int i : reg) {
+ int key = i >>> HLLConstants.Q_PRIME_VALUE;
+ byte value = (byte) (i & 0x3f);
+ sparseRegister.set(key, value);
+ }
+ }
+
+ /**
+ * Reconstruct dense registers from byte array
+ * @param reg
+ * - unpacked byte array
+ */
+ public void setHLLDenseRegister(byte[] reg) {
+ int i = 0;
+ for (byte b : reg) {
+ denseRegister.set(i, b);
+ i++;
+ }
+ }
+
+ /**
+ * Merge the specified hyperloglog to the current one. Encoding switches
+ * automatically after merge if the encoding switch threshold is exceeded.
+ * @param hll
+ * - hyperloglog to be merged
+ * @throws IllegalArgumentException
+ */
+ public void merge(HyperLogLog hll) {
+ if (p != hll.p || chosenHashBits != hll.chosenHashBits) {
+ throw new IllegalArgumentException(
+ "HyperLogLog cannot be merged as either p or hashbits are different. Current: "
+ + toString() + " Provided: " + hll.toString());
+ }
+
+ EncodingType otherEncoding = hll.getEncoding();
+
+ if (encoding.equals(EncodingType.SPARSE) && otherEncoding.equals(EncodingType.SPARSE)) {
+ sparseRegister.merge(hll.getHLLSparseRegister());
+ // if after merge the sparse switching threshold is exceeded then change
+ // to dense encoding
+ if (sparseRegister.getSize() > encodingSwitchThreshold) {
+ encoding = EncodingType.DENSE;
+ denseRegister = sparseToDenseRegister(sparseRegister);
+ sparseRegister = null;
+ }
+ } else if (encoding.equals(EncodingType.DENSE) && otherEncoding.equals(EncodingType.DENSE)) {
+ denseRegister.merge(hll.getHLLDenseRegister());
+ } else if (encoding.equals(EncodingType.SPARSE) && otherEncoding.equals(EncodingType.DENSE)) {
+ denseRegister = sparseToDenseRegister(sparseRegister);
+ denseRegister.merge(hll.getHLLDenseRegister());
+ sparseRegister = null;
+ encoding = EncodingType.DENSE;
+ } else if (encoding.equals(EncodingType.DENSE) && otherEncoding.equals(EncodingType.SPARSE)) {
+ HLLDenseRegister otherDenseRegister = sparseToDenseRegister(hll.getHLLSparseRegister());
+ denseRegister.merge(otherDenseRegister);
+ }
+
+ invalidateCount = true;
+ }
+
+ /**
+ * Converts sparse to dense hll register
+ * @param sparseRegister
+ * - sparse register to be converted
+ * @return converted dense register
+ */
+ private HLLDenseRegister sparseToDenseRegister(HLLSparseRegister sparseRegister) {
+ if (sparseRegister == null) {
+ return null;
+ }
+ int p = sparseRegister.getP();
+ int pMask = (1 << p) - 1;
+ HLLDenseRegister result = new HLLDenseRegister(p, bitPacking);
+ for (Map.Entry<Integer, Byte> entry : sparseRegister.getSparseMap().entrySet()) {
+ int key = entry.getKey();
+ int idx = key & pMask;
+ result.set(idx, entry.getValue());
+ }
+ return result;
+ }
+
+ @Override
+ public String toString() {
+ StringBuilder sb = new StringBuilder();
+ sb.append("Encoding: ");
+ sb.append(encoding);
+ sb.append(", p: ");
+ sb.append(p);
+ sb.append(", estimatedCardinality: ");
+ sb.append(estimateNumDistinctValues());
+ return sb.toString();
+ }
+
+ public String toStringExtended() {
+ if (encoding.equals(EncodingType.DENSE)) {
+ return toString() + ", " + denseRegister.toExtendedString();
+ } else if (encoding.equals(EncodingType.SPARSE)) {
+ return toString() + ", " + sparseRegister.toExtendedString();
+ }
+
+ return toString();
+ }
+
+ public int getNumRegisterIndexBits() {
+ return p;
+ }
+
+ public EncodingType getEncoding() {
+ return encoding;
+ }
+
+ public void setEncoding(EncodingType encoding) {
+ this.encoding = encoding;
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (!(obj instanceof HyperLogLog)) {
+ return false;
+ }
+
+ HyperLogLog other = (HyperLogLog) obj;
+ long count = estimateNumDistinctValues();
+ long otherCount = other.estimateNumDistinctValues();
+ boolean result = p == other.p && chosenHashBits == other.chosenHashBits
+ && encoding.equals(other.encoding) && count == otherCount;
+ if (encoding.equals(EncodingType.DENSE)) {
+ result = result && denseRegister.equals(other.getHLLDenseRegister());
+ }
+
+ if (encoding.equals(EncodingType.SPARSE)) {
+ result = result && sparseRegister.equals(other.getHLLSparseRegister());
+ }
+ return result;
+ }
+
+ @Override
+ public int hashCode() {
+ int hashcode = 0;
+ hashcode += 31 * p;
+ hashcode += 31 * chosenHashBits;
+ hashcode += encoding.hashCode();
+ hashcode += 31 * estimateNumDistinctValues();
+ if (encoding.equals(EncodingType.DENSE)) {
+ hashcode += 31 * denseRegister.hashCode();
+ }
+
+ if (encoding.equals(EncodingType.SPARSE)) {
+ hashcode += 31 * sparseRegister.hashCode();
+ }
+ return hashcode;
+ }
+
+ @Override
+ public void reset() {
+ }
+
+ @Override
+ public String serialize() {
+ ByteArrayOutputStream bos = new ByteArrayOutputStream();
+ // write bytes to bos ...
+ try {
+ HyperLogLogUtils.serializeHLL(bos, this);
+ } catch (IOException e) {
+ throw new RuntimeException(e);
+ }
+ return Base64.encodeBase64String(bos.toByteArray());
+ }
+
+ @Override
+ public NumDistinctValueEstimator deserialize(String s) {
+ InputStream is = new ByteArrayInputStream(Base64.decodeBase64(s));
+ try {
+ return HyperLogLogUtils.deserializeHLL(is);
+ } catch (IOException e) {
+ throw new RuntimeException(e);
+ }
+ }
+
+ @Override
+ public void addToEstimator(long v) {
+ addLong(v);
+ }
+
+ @Override
+ public void addToEstimator(String s) {
+ addString(s);
+ }
+
+ @Override
+ public void addToEstimator(double d) {
+ addDouble(d);
+ }
+
+ @Override
+ public void addToEstimator(HiveDecimal decimal) {
+ addDouble(decimal.doubleValue());
+ }
+
+ @Override
+ public void mergeEstimators(NumDistinctValueEstimator o) {
+ merge((HyperLogLog) o);
+ }
+
+ @Override
+ public int lengthFor(JavaDataModel model) {
+ // 5 is the head, 1<<p means the number of bytes for register
+ return (5 + (1 << p));
+ }
+
+ @Override
+ public boolean canMerge(NumDistinctValueEstimator o) {
+ return o instanceof HyperLogLog;
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/hive/blob/b883d313/common/src/java/org/apache/hadoop/hive/common/ndv/hll/HyperLogLogUtils.java
----------------------------------------------------------------------
diff --git a/common/src/java/org/apache/hadoop/hive/common/ndv/hll/HyperLogLogUtils.java b/common/src/java/org/apache/hadoop/hive/common/ndv/hll/HyperLogLogUtils.java
new file mode 100644
index 0000000..2d82bd0
--- /dev/null
+++ b/common/src/java/org/apache/hadoop/hive/common/ndv/hll/HyperLogLogUtils.java
@@ -0,0 +1,392 @@
+/**
+ * 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.hadoop.hive.common.ndv.hll;
+
+import java.io.EOFException;
+import java.io.IOException;
+import java.io.InputStream;
+import java.io.OutputStream;
+import java.util.Arrays;
+import java.util.Map;
+import java.util.TreeMap;
+
+import org.apache.hadoop.hive.common.ndv.hll.HyperLogLog.EncodingType;
+
+/**
+ * HyperLogLog serialization utilities.
+ */
+public class HyperLogLogUtils {
+
+ public static final byte[] MAGIC = new byte[] { 'H', 'L', 'L' };
+
+ /**
+ * HyperLogLog is serialized using the following format
+ *
+ * <pre>
+ * |-4 byte-|------varlong----|varint (optional)|----------|
+ * ---------------------------------------------------------
+ * | header | estimated-count | register-length | register |
+ * ---------------------------------------------------------
+ *
+ * <b>4 byte header</b> is encoded like below
+ * 3 bytes - HLL magic string to identify serialized stream
+ * 4 bits - p (number of bits to be used as register index)
+ * 1 - spare bit (not used)
+ * 3 bits - encoding (000 - sparse, 001..110 - n bit packing, 111 - no bit packing)
+ *
+ * Followed by header are 3 fields that are required for reconstruction
+ * of hyperloglog
+ * Estimated count - variable length long to store last computed estimated count.
+ * This is just for quick lookup without deserializing registers
+ * Register length - number of entries in the register (required only for
+ * for sparse representation. For bit-packing, the register
+ * length can be found from p)
+ * </pre>
+ * @param out
+ * - output stream to write to
+ * @param hll
+ * - hyperloglog that needs to be serialized
+ * @throws IOException
+ */
+ public static void serializeHLL(OutputStream out, HyperLogLog hll) throws IOException {
+
+ // write header
+ out.write(MAGIC);
+ int fourthByte = 0;
+ int p = hll.getNumRegisterIndexBits();
+ fourthByte = (p & 0xff) << 4;
+
+ int bitWidth = 0;
+ EncodingType enc = hll.getEncoding();
+
+ // determine bit width for bitpacking and encode it in header
+ if (enc.equals(EncodingType.DENSE)) {
+ int lzr = hll.getHLLDenseRegister().getMaxRegisterValue();
+ bitWidth = getBitWidth(lzr);
+
+ // the max value of number of zeroes for 64 bit hash can be encoded using
+ // only 6 bits. So we will disable bit packing for any values >6
+ if (bitWidth > 6) {
+ fourthByte |= 7;
+ bitWidth = 8;
+ } else {
+ fourthByte |= (bitWidth & 7);
+ }
+ }
+
+ // write fourth byte of header
+ out.write(fourthByte);
+
+ // write estimated count
+ long estCount = hll.estimateNumDistinctValues();
+ writeVulong(out, estCount);
+
+ // serialize dense/sparse registers. Dense registers are bitpacked whereas
+ // sparse registers are delta and variable length encoded
+ if (enc.equals(EncodingType.DENSE)) {
+ byte[] register = hll.getHLLDenseRegister().getRegister();
+ bitpackHLLRegister(out, register, bitWidth);
+ } else if (enc.equals(EncodingType.SPARSE)) {
+ TreeMap<Integer, Byte> sparseMap = hll.getHLLSparseRegister().getSparseMap();
+
+ // write the number of elements in sparse map (required for
+ // reconstruction)
+ writeVulong(out, sparseMap.size());
+
+ // compute deltas and write the values as varints
+ int prev = 0;
+ for (Map.Entry<Integer, Byte> entry : sparseMap.entrySet()) {
+ if (prev == 0) {
+ prev = (entry.getKey() << HLLConstants.Q_PRIME_VALUE) | entry.getValue();
+ writeVulong(out, prev);
+ } else {
+ int curr = (entry.getKey() << HLLConstants.Q_PRIME_VALUE) | entry.getValue();
+ int delta = curr - prev;
+ writeVulong(out, delta);
+ prev = curr;
+ }
+ }
+ }
+ }
+
+ /**
+ * Refer serializeHLL() for format of serialization. This funtions
+ * deserializes the serialized hyperloglogs
+ * @param in
+ * - input stream
+ * @return deserialized hyperloglog
+ * @throws IOException
+ */
+ public static HyperLogLog deserializeHLL(InputStream in) throws IOException {
+ checkMagicString(in);
+ int fourthByte = in.read() & 0xff;
+ int p = fourthByte >>> 4;
+
+ // read type of encoding
+ int enc = fourthByte & 7;
+ EncodingType encoding = null;
+ int bitSize = 0;
+ if (enc == 0) {
+ encoding = EncodingType.SPARSE;
+ } else if (enc > 0 && enc < 7) {
+ bitSize = enc;
+ encoding = EncodingType.DENSE;
+ } else {
+ // bit packing disabled
+ bitSize = 8;
+ encoding = EncodingType.DENSE;
+ }
+
+ // estimated count
+ long estCount = readVulong(in);
+
+ HyperLogLog result = null;
+ if (encoding.equals(EncodingType.SPARSE)) {
+ result = HyperLogLog.builder().setNumRegisterIndexBits(p)
+ .setEncoding(EncodingType.SPARSE).build();
+ int numRegisterEntries = (int) readVulong(in);
+ int[] reg = new int[numRegisterEntries];
+ int prev = 0;
+
+ // reconstruct the sparse map from delta encoded and varint input stream
+ if (numRegisterEntries > 0) {
+ prev = (int) readVulong(in);
+ reg[0] = prev;
+ }
+ int delta = 0;
+ int curr = 0;
+ for (int i = 1; i < numRegisterEntries; i++) {
+ delta = (int) readVulong(in);
+ curr = prev + delta;
+ reg[i] = curr;
+ prev = curr;
+ }
+ result.setHLLSparseRegister(reg);
+ } else {
+
+ // explicitly disable bit packing
+ if (bitSize == 8) {
+ result = HyperLogLog.builder().setNumRegisterIndexBits(p)
+ .setEncoding(EncodingType.DENSE).enableBitPacking(false).build();
+ } else {
+ result = HyperLogLog.builder().setNumRegisterIndexBits(p)
+ .setEncoding(EncodingType.DENSE).enableBitPacking(true).build();
+ }
+ int m = 1 << p;
+ byte[] register = unpackHLLRegister(in, m, bitSize);
+ result.setHLLDenseRegister(register);
+ }
+
+ result.setCount(estCount);
+
+ return result;
+ }
+
+ private static void bitpackHLLRegister(OutputStream out, byte[] register, int bitWidth)
+ throws IOException {
+ int bitsLeft = 8;
+ byte current = 0;
+
+ if (bitWidth == 8) {
+ fastPathWrite(out, register);
+ return;
+ }
+
+ // write the blob
+ for (byte value : register) {
+ int bitsToWrite = bitWidth;
+ while (bitsToWrite > bitsLeft) {
+ // add the bits to the bottom of the current word
+ current |= value >>> (bitsToWrite - bitsLeft);
+ // subtract out the bits we just added
+ bitsToWrite -= bitsLeft;
+ // zero out the bits above bitsToWrite
+ value &= (1 << bitsToWrite) - 1;
+ out.write(current);
+ current = 0;
+ bitsLeft = 8;
+ }
+ bitsLeft -= bitsToWrite;
+ current |= value << bitsLeft;
+ if (bitsLeft == 0) {
+ out.write(current);
+ current = 0;
+ bitsLeft = 8;
+ }
+ }
+
+ out.flush();
+ }
+
+ private static void fastPathWrite(OutputStream out, byte[] register) throws IOException {
+ for (byte b : register) {
+ out.write(b);
+ }
+ }
+
+ /**
+ * Unpack the bitpacked HyperLogLog register.
+ * @param in
+ * - input stream
+ * @param length
+ * - serialized length
+ * @return unpacked HLL register
+ * @throws IOException
+ */
+ private static byte[] unpackHLLRegister(InputStream in, int length, int bitSize)
+ throws IOException {
+ int mask = (1 << bitSize) - 1;
+ int bitsLeft = 8;
+
+ if (bitSize == 8) {
+ return fastPathRead(in, length);
+ }
+
+ byte current = (byte) (0xff & in.read());
+
+ byte[] output = new byte[length];
+ for (int i = 0; i < output.length; i++) {
+ byte result = 0;
+ int bitsLeftToRead = bitSize;
+ while (bitsLeftToRead > bitsLeft) {
+ result <<= bitsLeft;
+ result |= current & ((1 << bitsLeft) - 1);
+ bitsLeftToRead -= bitsLeft;
+ current = (byte) (0xff & in.read());
+ bitsLeft = 8;
+ }
+ if (bitsLeftToRead > 0) {
+ result <<= bitsLeftToRead;
+ bitsLeft -= bitsLeftToRead;
+ result |= (current >>> bitsLeft) & ((1 << bitsLeftToRead) - 1);
+ }
+ output[i] = (byte) (result & mask);
+ }
+ return output;
+ }
+
+ private static byte[] fastPathRead(InputStream in, int length) throws IOException {
+ byte[] result = new byte[length];
+ for (int i = 0; i < length; i++) {
+ result[i] = (byte) in.read();
+ }
+ return result;
+ }
+
+ /**
+ * Get estimated cardinality without deserializing HLL
+ * @param in
+ * - serialized HLL
+ * @return - cardinality
+ * @throws IOException
+ */
+ public static long getEstimatedCountFromSerializedHLL(InputStream in) throws IOException {
+ checkMagicString(in);
+ in.read();
+ return readVulong(in);
+ }
+
+ /**
+ * Check if the specified input stream is actually a HLL stream
+ * @param in
+ * - input stream
+ * @throws IOException
+ */
+ private static void checkMagicString(InputStream in) throws IOException {
+ byte[] magic = new byte[3];
+ magic[0] = (byte) in.read();
+ magic[1] = (byte) in.read();
+ magic[2] = (byte) in.read();
+
+ if (!Arrays.equals(magic, MAGIC)) {
+ throw new IllegalArgumentException("The input stream is not a HyperLogLog stream.");
+ }
+ }
+
+ /**
+ * Minimum bits required to encode the specified value
+ * @param val
+ * - input value
+ * @return
+ */
+ private static int getBitWidth(int val) {
+ int count = 0;
+ while (val != 0) {
+ count++;
+ val = (byte) (val >>> 1);
+ }
+ return count;
+ }
+
+ /**
+ * Return relative error between actual and estimated cardinality
+ * @param actualCount
+ * - actual count
+ * @param estimatedCount
+ * - estimated count
+ * @return relative error
+ */
+ public static float getRelativeError(long actualCount, long estimatedCount) {
+ float err = (1.0f - ((float) estimatedCount / (float) actualCount)) * 100.0f;
+ return err;
+ }
+
+ /**
+ * Write variable length encoded longs to output stream
+ * @param output
+ * - out stream
+ * @param value
+ * - long
+ * @throws IOException
+ */
+ private static void writeVulong(OutputStream output, long value) throws IOException {
+ while (true) {
+ if ((value & ~0x7f) == 0) {
+ output.write((byte) value);
+ return;
+ } else {
+ output.write((byte) (0x80 | (value & 0x7f)));
+ value >>>= 7;
+ }
+ }
+ }
+
+ /**
+ * Read variable length encoded longs from input stream
+ * @param in
+ * - input stream
+ * @return decoded long value
+ * @throws IOException
+ */
+ private static long readVulong(InputStream in) throws IOException {
+ long result = 0;
+ long b;
+ int offset = 0;
+ do {
+ b = in.read();
+ if (b == -1) {
+ throw new EOFException("Reading Vulong past EOF");
+ }
+ result |= (0x7f & b) << offset;
+ offset += 7;
+ } while (b >= 0x80);
+ return result;
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/hive/blob/b883d313/common/src/java/org/apache/hadoop/hive/conf/HiveConf.java
----------------------------------------------------------------------
diff --git a/common/src/java/org/apache/hadoop/hive/conf/HiveConf.java b/common/src/java/org/apache/hadoop/hive/conf/HiveConf.java
index c7afe2b..9c954be 100644
--- a/common/src/java/org/apache/hadoop/hive/conf/HiveConf.java
+++ b/common/src/java/org/apache/hadoop/hive/conf/HiveConf.java
@@ -1724,7 +1724,9 @@ public class HiveConf extends Configuration {
HIVE_STATS_COLLECT_SCANCOLS("hive.stats.collect.scancols", false,
"Whether column accesses are tracked in the QueryPlan.\n" +
"This is useful to identify how tables are accessed and to determine if there are wasted columns that can be trimmed."),
- // standard error allowed for ndv estimates. A lower value indicates higher accuracy and a
+ HIVE_STATS_NDV_ALGO("hive.stats.ndv.algo", "hll", new PatternSet("hll", "fm"),
+ "hll and fm stand for HyperLogLog and FM-sketch, respectively for computing ndv."),
+ // standard error allowed for ndv estimates for FM-sketch. A lower value indicates higher accuracy and a
// higher compute cost.
HIVE_STATS_NDV_ERROR("hive.stats.ndv.error", (float)20.0,
"Standard error expressed in percentage. Provides a tradeoff between accuracy and compute cost. \n" +
http://git-wip-us.apache.org/repos/asf/hive/blob/b883d313/common/src/test/org/apache/hadoop/hive/common/ndv/hll/TestHLLNoBias.java
----------------------------------------------------------------------
diff --git a/common/src/test/org/apache/hadoop/hive/common/ndv/hll/TestHLLNoBias.java b/common/src/test/org/apache/hadoop/hive/common/ndv/hll/TestHLLNoBias.java
new file mode 100644
index 0000000..30f5ca3
--- /dev/null
+++ b/common/src/test/org/apache/hadoop/hive/common/ndv/hll/TestHLLNoBias.java
@@ -0,0 +1,114 @@
+/**
+ * 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.hadoop.hive.common.ndv.hll;
+
+import static org.junit.Assert.assertEquals;
+
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.HashSet;
+import java.util.Random;
+import java.util.Set;
+
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameters;
+
+@RunWith(value = Parameterized.class)
+public class TestHLLNoBias {
+
+ // 1.5% tolerance for long range bias (when no bias enabled) and 5% when (no
+ // bias is disabled) and
+ // 0.5% for short range bias
+ private float noBiaslongRangeTolerance = 2.0f;
+ private float biasedlongRangeTolerance = 5.0f;
+ private float shortRangeTolerance = 0.5f;
+
+ private int size;
+
+ public TestHLLNoBias(int n) {
+ this.size = n;
+ }
+
+ @Parameters
+ public static Collection<Object[]> data() {
+ Object[][] data = new Object[][] { { 30000 }, { 41000 }, { 50000 }, { 60000 }, { 75000 },
+ { 80000 }, { 81920 } };
+ return Arrays.asList(data);
+ }
+
+ @Test
+ public void testHLLAdd() {
+ Random rand = new Random(size);
+ HyperLogLog hll = HyperLogLog.builder().build();
+ int size = 100;
+ for (int i = 0; i < size; i++) {
+ hll.addLong(rand.nextLong());
+ }
+ double threshold = size > 40000 ? noBiaslongRangeTolerance : shortRangeTolerance;
+ double delta = threshold * size / 100;
+ assertEquals((double) size, (double) hll.count(), delta);
+ }
+
+ @Test
+ public void testHLLAddHalfDistinct() {
+ Random rand = new Random(size);
+ HyperLogLog hll = HyperLogLog.builder().build();
+ int unique = size / 2;
+ Set<Long> hashset = new HashSet<Long>();
+ for (int i = 0; i < size; i++) {
+ long val = rand.nextInt(unique);
+ hashset.add(val);
+ hll.addLong(val);
+ }
+ double threshold = size > 40000 ? noBiaslongRangeTolerance : shortRangeTolerance;
+ double delta = threshold * hashset.size() / 100;
+ assertEquals((double) hashset.size(), (double) hll.count(), delta);
+ }
+
+ @Test
+ public void testHLLNoBiasDisabled() {
+ Random rand = new Random(size);
+ HyperLogLog hll = HyperLogLog.builder().enableNoBias(false).build();
+ int size = 100;
+ for (int i = 0; i < size; i++) {
+ hll.addLong(rand.nextLong());
+ }
+ double threshold = size > 40000 ? biasedlongRangeTolerance : shortRangeTolerance;
+ double delta = threshold * size / 100;
+ assertEquals((double) size, (double) hll.count(), delta);
+ }
+
+ @Test
+ public void testHLLNoBiasDisabledHalfDistinct() {
+ Random rand = new Random(size);
+ HyperLogLog hll = HyperLogLog.builder().enableNoBias(false).build();
+ int unique = size / 2;
+ Set<Long> hashset = new HashSet<Long>();
+ for (int i = 0; i < size; i++) {
+ long val = rand.nextInt(unique);
+ hashset.add(val);
+ hll.addLong(val);
+ }
+ double threshold = size > 40000 ? biasedlongRangeTolerance : shortRangeTolerance;
+ double delta = threshold * hashset.size() / 100;
+ assertEquals((double) hashset.size(), (double) hll.count(), delta);
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/hive/blob/b883d313/common/src/test/org/apache/hadoop/hive/common/ndv/hll/TestHLLSerialization.java
----------------------------------------------------------------------
diff --git a/common/src/test/org/apache/hadoop/hive/common/ndv/hll/TestHLLSerialization.java b/common/src/test/org/apache/hadoop/hive/common/ndv/hll/TestHLLSerialization.java
new file mode 100644
index 0000000..b4b8df1
--- /dev/null
+++ b/common/src/test/org/apache/hadoop/hive/common/ndv/hll/TestHLLSerialization.java
@@ -0,0 +1,267 @@
+/**
+ * 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.hadoop.hive.common.ndv.hll;
+
+import static org.junit.Assert.assertEquals;
+
+import java.io.DataInputStream;
+import java.io.DataOutputStream;
+import java.io.File;
+import java.io.FileInputStream;
+import java.io.FileOutputStream;
+import java.io.IOException;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.HashSet;
+import java.util.Random;
+import java.util.Set;
+
+import org.apache.hadoop.hive.common.ndv.hll.HyperLogLog.EncodingType;
+import org.junit.After;
+import org.junit.Rule;
+import org.junit.Test;
+import org.junit.rules.TestName;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameters;
+
+@RunWith(value = Parameterized.class)
+public class TestHLLSerialization {
+
+ private int size;
+ private File testFile;
+ private static final String pathPrefix = ".";
+ private static final int SEED = 100;
+ // 5% tolerance for long range bias and 2.5% for short range bias
+ private float longRangeTolerance = 5.0f;
+ private float shortRangeTolerance = 2.5f;
+
+ public TestHLLSerialization(int n) {
+ this.size = n;
+ this.testFile = new File(pathPrefix + testCaseName.getMethodName() + "_" + size + ".hll");
+ }
+
+ @Parameters
+ public static Collection<Object[]> data() {
+ Object[][] data = new Object[][] { { 2 }, { 10 }, { 100 }, { 1000 }, { 2000 }, { 3000 },
+ { 5000 }, { 6000 }, { 10000 }, { 100000 }, { 1000000 } };
+ return Arrays.asList(data);
+ }
+
+ @After
+ public void close() {
+ if (testFile.exists()) {
+ testFile.delete();
+ }
+ }
+
+ @Rule
+ public TestName testCaseName = new TestName();
+
+ @Test
+ public void testHLLSparseSerialization() throws IOException {
+ HyperLogLog hll = HyperLogLog.builder().setEncoding(EncodingType.SPARSE).build();
+ Random rand = new Random(SEED);
+ for (int i = 0; i < size; i++) {
+ hll.addLong(rand.nextLong());
+ }
+ FileOutputStream fos = new FileOutputStream(testFile);
+ DataOutputStream out = new DataOutputStream(fos);
+ HyperLogLogUtils.serializeHLL(out, hll);
+ FileInputStream fis = new FileInputStream(testFile);
+ DataInputStream in = new DataInputStream(fis);
+ HyperLogLog deserializedHLL = HyperLogLogUtils.deserializeHLL(in);
+ assertEquals(hll, deserializedHLL);
+ assertEquals(hll.toString(), deserializedHLL.toString());
+ assertEquals(hll.toStringExtended(), deserializedHLL.toStringExtended());
+ assertEquals(hll.hashCode(), deserializedHLL.hashCode());
+ assertEquals(hll.count(), deserializedHLL.count());
+ }
+
+ @Test
+ public void testHLLSparseSerializationHalfDistinct() throws IOException {
+ HyperLogLog hll = HyperLogLog.builder().setEncoding(EncodingType.SPARSE).build();
+ Random rand = new Random(SEED);
+ Set<Integer> hashset = new HashSet<Integer>();
+ for (int i = 0; i < size; i++) {
+ int val = rand.nextInt(size / 2);
+ hll.addLong(val);
+ hashset.add(val);
+ }
+ FileOutputStream fos = new FileOutputStream(testFile);
+ DataOutputStream out = new DataOutputStream(fos);
+ HyperLogLogUtils.serializeHLL(out, hll);
+ double threshold = size > 40000 ? longRangeTolerance : shortRangeTolerance;
+ double delta = threshold * hashset.size() / 100;
+ FileInputStream fis = new FileInputStream(testFile);
+ DataInputStream in = new DataInputStream(fis);
+ HyperLogLog deserializedHLL = HyperLogLogUtils.deserializeHLL(in);
+ assertEquals(hll, deserializedHLL);
+ assertEquals(hll.toString(), deserializedHLL.toString());
+ assertEquals(hll.toStringExtended(), deserializedHLL.toStringExtended());
+ assertEquals(hll.hashCode(), deserializedHLL.hashCode());
+ assertEquals(hll.count(), deserializedHLL.count());
+ assertEquals(hashset.size(), hll.count(), delta);
+ assertEquals(hashset.size(), deserializedHLL.count(), delta);
+ }
+
+ @Test
+ public void testHLLSparseNoBitPacking() throws IOException {
+ HyperLogLog hll = HyperLogLog.builder().setEncoding(EncodingType.SPARSE)
+ .enableBitPacking(false).build();
+ Random rand = new Random(SEED);
+ for (int i = 0; i < size; i++) {
+ hll.addLong(rand.nextLong());
+ }
+ FileOutputStream fos = new FileOutputStream(testFile);
+ DataOutputStream out = new DataOutputStream(fos);
+ HyperLogLogUtils.serializeHLL(out, hll);
+ FileInputStream fis = new FileInputStream(testFile);
+ DataInputStream in = new DataInputStream(fis);
+ HyperLogLog deserializedHLL = HyperLogLogUtils.deserializeHLL(in);
+ assertEquals(hll, deserializedHLL);
+ assertEquals(hll.toString(), deserializedHLL.toString());
+ assertEquals(hll.toStringExtended(), deserializedHLL.toStringExtended());
+ assertEquals(hll.hashCode(), deserializedHLL.hashCode());
+ assertEquals(hll.count(), deserializedHLL.count());
+ }
+
+ @Test
+ public void testHLLSparseNoBitPackingHalfDistinct() throws IOException {
+ HyperLogLog hll = HyperLogLog.builder().setEncoding(EncodingType.SPARSE)
+ .enableBitPacking(false).build();
+ Random rand = new Random(SEED);
+ Set<Integer> hashset = new HashSet<Integer>();
+ for (int i = 0; i < size; i++) {
+ int val = rand.nextInt(size / 2);
+ hll.addLong(val);
+ hashset.add(val);
+ }
+ FileOutputStream fos = new FileOutputStream(testFile);
+ DataOutputStream out = new DataOutputStream(fos);
+ HyperLogLogUtils.serializeHLL(out, hll);
+ double threshold = size > 40000 ? longRangeTolerance : shortRangeTolerance;
+ double delta = threshold * hashset.size() / 100;
+ FileInputStream fis = new FileInputStream(testFile);
+ DataInputStream in = new DataInputStream(fis);
+ HyperLogLog deserializedHLL = HyperLogLogUtils.deserializeHLL(in);
+ assertEquals(hll, deserializedHLL);
+ assertEquals(hll.toString(), deserializedHLL.toString());
+ assertEquals(hll.toStringExtended(), deserializedHLL.toStringExtended());
+ assertEquals(hll.hashCode(), deserializedHLL.hashCode());
+ assertEquals(hll.count(), deserializedHLL.count());
+ assertEquals(hashset.size(), hll.count(), delta);
+ assertEquals(hashset.size(), deserializedHLL.count(), delta);
+ }
+
+ @Test
+ public void testHLLDenseSerialization() throws IOException {
+ HyperLogLog hll = HyperLogLog.builder().setEncoding(EncodingType.DENSE).build();
+ Random rand = new Random(SEED);
+ for (int i = 0; i < size; i++) {
+ hll.addLong(rand.nextLong());
+ }
+ FileOutputStream fos = new FileOutputStream(testFile);
+ DataOutputStream out = new DataOutputStream(fos);
+ HyperLogLogUtils.serializeHLL(out, hll);
+ FileInputStream fis = new FileInputStream(testFile);
+ DataInputStream in = new DataInputStream(fis);
+ HyperLogLog deserializedHLL = HyperLogLogUtils.deserializeHLL(in);
+ assertEquals(hll, deserializedHLL);
+ assertEquals(hll.toString(), deserializedHLL.toString());
+ assertEquals(hll.toStringExtended(), deserializedHLL.toStringExtended());
+ assertEquals(hll.hashCode(), deserializedHLL.hashCode());
+ assertEquals(hll.count(), deserializedHLL.count());
+ }
+
+ @Test
+ public void testHLLDenseSerializationHalfDistinct() throws IOException {
+ HyperLogLog hll = HyperLogLog.builder().setEncoding(EncodingType.DENSE).build();
+ Random rand = new Random(SEED);
+ Set<Integer> hashset = new HashSet<Integer>();
+ for (int i = 0; i < size; i++) {
+ int val = rand.nextInt(size / 2);
+ hll.addLong(val);
+ hashset.add(val);
+ }
+ FileOutputStream fos = new FileOutputStream(testFile);
+ DataOutputStream out = new DataOutputStream(fos);
+ HyperLogLogUtils.serializeHLL(out, hll);
+ double threshold = size > 40000 ? longRangeTolerance : shortRangeTolerance;
+ double delta = threshold * hashset.size() / 100;
+ FileInputStream fis = new FileInputStream(testFile);
+ DataInputStream in = new DataInputStream(fis);
+ HyperLogLog deserializedHLL = HyperLogLogUtils.deserializeHLL(in);
+ assertEquals(hll, deserializedHLL);
+ assertEquals(hll.toString(), deserializedHLL.toString());
+ assertEquals(hll.toStringExtended(), deserializedHLL.toStringExtended());
+ assertEquals(hll.hashCode(), deserializedHLL.hashCode());
+ assertEquals(hll.count(), deserializedHLL.count());
+ assertEquals(hashset.size(), hll.count(), delta);
+ assertEquals(hashset.size(), deserializedHLL.count(), delta);
+ }
+
+ @Test
+ public void testHLLDenseNoBitPacking() throws IOException {
+ HyperLogLog hll = HyperLogLog.builder().setEncoding(EncodingType.DENSE).enableBitPacking(false)
+ .build();
+ Random rand = new Random(SEED);
+ for (int i = 0; i < size; i++) {
+ hll.addLong(rand.nextLong());
+ }
+ FileOutputStream fos = new FileOutputStream(testFile);
+ DataOutputStream out = new DataOutputStream(fos);
+ HyperLogLogUtils.serializeHLL(out, hll);
+ FileInputStream fis = new FileInputStream(testFile);
+ DataInputStream in = new DataInputStream(fis);
+ HyperLogLog deserializedHLL = HyperLogLogUtils.deserializeHLL(in);
+ assertEquals(hll, deserializedHLL);
+ assertEquals(hll.toString(), deserializedHLL.toString());
+ assertEquals(hll.toStringExtended(), deserializedHLL.toStringExtended());
+ assertEquals(hll.hashCode(), deserializedHLL.hashCode());
+ assertEquals(hll.count(), deserializedHLL.count());
+ }
+
+ @Test
+ public void testHLLDenseNoBitPackingHalfDistinct() throws IOException {
+ HyperLogLog hll = HyperLogLog.builder().setEncoding(EncodingType.DENSE).enableBitPacking(false)
+ .build();
+ Random rand = new Random(SEED);
+ Set<Integer> hashset = new HashSet<Integer>();
+ for (int i = 0; i < size; i++) {
+ int val = rand.nextInt(size / 2);
+ hll.addLong(val);
+ hashset.add(val);
+ }
+ FileOutputStream fos = new FileOutputStream(testFile);
+ DataOutputStream out = new DataOutputStream(fos);
+ HyperLogLogUtils.serializeHLL(out, hll);
+ double threshold = size > 40000 ? longRangeTolerance : shortRangeTolerance;
+ double delta = threshold * hashset.size() / 100;
+ FileInputStream fis = new FileInputStream(testFile);
+ DataInputStream in = new DataInputStream(fis);
+ HyperLogLog deserializedHLL = HyperLogLogUtils.deserializeHLL(in);
+ assertEquals(hll, deserializedHLL);
+ assertEquals(hll.toString(), deserializedHLL.toString());
+ assertEquals(hll.toStringExtended(), deserializedHLL.toStringExtended());
+ assertEquals(hll.hashCode(), deserializedHLL.hashCode());
+ assertEquals(hll.count(), deserializedHLL.count());
+ assertEquals(hashset.size(), hll.count(), delta);
+ assertEquals(hashset.size(), deserializedHLL.count(), delta);
+ }
+}
http://git-wip-us.apache.org/repos/asf/hive/blob/b883d313/common/src/test/org/apache/hadoop/hive/common/ndv/hll/TestHyperLogLog.java
----------------------------------------------------------------------
diff --git a/common/src/test/org/apache/hadoop/hive/common/ndv/hll/TestHyperLogLog.java b/common/src/test/org/apache/hadoop/hive/common/ndv/hll/TestHyperLogLog.java
new file mode 100644
index 0000000..635073f
--- /dev/null
+++ b/common/src/test/org/apache/hadoop/hive/common/ndv/hll/TestHyperLogLog.java
@@ -0,0 +1,227 @@
+/**
+ * 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.hadoop.hive.common.ndv.hll;
+
+import static org.junit.Assert.assertEquals;
+
+import org.apache.hadoop.hive.common.ndv.hll.HyperLogLog.EncodingType;
+import org.junit.Test;
+
+public class TestHyperLogLog {
+ // 5% tolerance for estimated count
+ private float longRangeTolerance = 5.0f;
+ private float shortRangeTolerance = 2.0f;
+
+ @Test(expected = IllegalArgumentException.class)
+ public void testHLLDenseMerge() {
+ HyperLogLog hll = HyperLogLog.builder().setEncoding(EncodingType.DENSE).build();
+ HyperLogLog hll2 = HyperLogLog.builder().setEncoding(EncodingType.DENSE).build();
+ HyperLogLog hll3 = HyperLogLog.builder().setEncoding(EncodingType.DENSE).build();
+ HyperLogLog hll4 = HyperLogLog.builder().setNumRegisterIndexBits(16)
+ .setEncoding(EncodingType.DENSE).build();
+ int size = 1000;
+ for (int i = 0; i < size; i++) {
+ hll.addLong(i);
+ hll2.addLong(size + i);
+ hll3.addLong(2 * size + i);
+ }
+ double threshold = size > 40000 ? longRangeTolerance : shortRangeTolerance;
+ double delta = threshold * size / 100;
+ assertEquals((double) size, (double) hll.count(), delta);
+ assertEquals((double) size, (double) hll2.count(), delta);
+
+ // merge
+ hll.merge(hll2);
+ assertEquals((double) 2 * size, (double) hll.count(), delta);
+ assertEquals(EncodingType.DENSE, hll.getEncoding());
+
+ // merge should update registers and hence the count
+ hll.merge(hll2);
+ assertEquals((double) 2 * size, (double) hll.count(), delta);
+ assertEquals(EncodingType.DENSE, hll.getEncoding());
+
+ // new merge
+ hll.merge(hll3);
+ assertEquals((double) 3 * size, (double) hll.count(), delta);
+ assertEquals(EncodingType.DENSE, hll.getEncoding());
+
+ // invalid merge -- register set size doesn't match
+ hll.merge(hll4);
+ }
+
+ @Test(expected = IllegalArgumentException.class)
+ public void testHLLSparseMerge() {
+ HyperLogLog hll = HyperLogLog.builder().setEncoding(EncodingType.SPARSE).build();
+ HyperLogLog hll2 = HyperLogLog.builder().setEncoding(EncodingType.SPARSE).build();
+ HyperLogLog hll3 = HyperLogLog.builder().setEncoding(EncodingType.SPARSE).build();
+ HyperLogLog hll4 = HyperLogLog.builder().setNumRegisterIndexBits(16)
+ .setEncoding(EncodingType.SPARSE).build();
+ int size = 500;
+ for (int i = 0; i < size; i++) {
+ hll.addLong(i);
+ hll2.addLong(size + i);
+ hll3.addLong(2 * size + i);
+ }
+ double threshold = size > 40000 ? longRangeTolerance : shortRangeTolerance;
+ double delta = threshold * size / 100;
+ assertEquals((double) size, (double) hll.count(), delta);
+ assertEquals((double) size, (double) hll2.count(), delta);
+
+ // merge
+ hll.merge(hll2);
+ assertEquals((double) 2 * size, (double) hll.count(), delta);
+ assertEquals(EncodingType.SPARSE, hll.getEncoding());
+
+ // merge should update registers and hence the count
+ hll.merge(hll2);
+ assertEquals((double) 2 * size, (double) hll.count(), delta);
+ assertEquals(EncodingType.SPARSE, hll.getEncoding());
+
+ // new merge
+ hll.merge(hll3);
+ assertEquals((double) 3 * size, (double) hll.count(), delta);
+ assertEquals(EncodingType.SPARSE, hll.getEncoding());
+
+ // invalid merge -- register set size doesn't match
+ hll.merge(hll4);
+ }
+
+ @Test(expected = IllegalArgumentException.class)
+ public void testHLLSparseDenseMerge() {
+ HyperLogLog hll = HyperLogLog.builder().setEncoding(EncodingType.SPARSE).build();
+ HyperLogLog hll2 = HyperLogLog.builder().setEncoding(EncodingType.SPARSE).build();
+ HyperLogLog hll3 = HyperLogLog.builder().setEncoding(EncodingType.DENSE).build();
+ HyperLogLog hll4 = HyperLogLog.builder().setNumRegisterIndexBits(16)
+ .setEncoding(EncodingType.DENSE).build();
+ int size = 1000;
+ for (int i = 0; i < size; i++) {
+ hll.addLong(i);
+ hll2.addLong(size + i);
+ hll3.addLong(2 * size + i);
+ }
+ double threshold = size > 40000 ? longRangeTolerance : shortRangeTolerance;
+ double delta = threshold * size / 100;
+ assertEquals((double) size, (double) hll.count(), delta);
+ assertEquals((double) size, (double) hll2.count(), delta);
+
+ // sparse-sparse merge
+ hll.merge(hll2);
+ assertEquals((double) 2 * size, (double) hll.count(), delta);
+ assertEquals(EncodingType.SPARSE, hll.getEncoding());
+
+ // merge should update registers and hence the count
+ hll.merge(hll2);
+ assertEquals((double) 2 * size, (double) hll.count(), delta);
+ assertEquals(EncodingType.SPARSE, hll.getEncoding());
+
+ // sparse-dense merge
+ hll.merge(hll3);
+ assertEquals((double) 3 * size, (double) hll.count(), delta);
+ assertEquals(EncodingType.DENSE, hll.getEncoding());
+
+ // invalid merge -- register set size doesn't match
+ hll.merge(hll4);
+ }
+
+ @Test(expected = IllegalArgumentException.class)
+ public void testHLLDenseSparseMerge() {
+ HyperLogLog hll = HyperLogLog.builder().setEncoding(EncodingType.DENSE).build();
+ HyperLogLog hll2 = HyperLogLog.builder().setEncoding(EncodingType.DENSE).build();
+ HyperLogLog hll3 = HyperLogLog.builder().setEncoding(EncodingType.SPARSE).build();
+ HyperLogLog hll4 = HyperLogLog.builder().setNumRegisterIndexBits(16)
+ .setEncoding(EncodingType.SPARSE).build();
+ int size = 1000;
+ for (int i = 0; i < size; i++) {
+ hll.addLong(i);
+ hll2.addLong(size + i);
+ hll3.addLong(2 * size + i);
+ }
+ double threshold = size > 40000 ? longRangeTolerance : shortRangeTolerance;
+ double delta = threshold * size / 100;
+ assertEquals((double) size, (double) hll.count(), delta);
+ assertEquals((double) size, (double) hll2.count(), delta);
+
+ // sparse-sparse merge
+ hll.merge(hll2);
+ assertEquals((double) 2 * size, (double) hll.count(), delta);
+ assertEquals(EncodingType.DENSE, hll.getEncoding());
+
+ // merge should update registers and hence the count
+ hll.merge(hll2);
+ assertEquals((double) 2 * size, (double) hll.count(), delta);
+ assertEquals(EncodingType.DENSE, hll.getEncoding());
+
+ // sparse-dense merge
+ hll.merge(hll3);
+ assertEquals((double) 3 * size, (double) hll.count(), delta);
+ assertEquals(EncodingType.DENSE, hll.getEncoding());
+
+ // invalid merge -- register set size doesn't match
+ hll.merge(hll4);
+ }
+
+ @Test(expected = IllegalArgumentException.class)
+ public void testHLLSparseOverflowMerge() {
+ HyperLogLog hll = HyperLogLog.builder().setEncoding(EncodingType.SPARSE).build();
+ HyperLogLog hll2 = HyperLogLog.builder().setEncoding(EncodingType.SPARSE).build();
+ HyperLogLog hll3 = HyperLogLog.builder().setEncoding(EncodingType.SPARSE).build();
+ HyperLogLog hll4 = HyperLogLog.builder().setNumRegisterIndexBits(16)
+ .setEncoding(EncodingType.SPARSE).build();
+ int size = 1000;
+ for (int i = 0; i < size; i++) {
+ hll.addLong(i);
+ hll2.addLong(size + i);
+ hll3.addLong(2 * size + i);
+ }
+ double threshold = size > 40000 ? longRangeTolerance : shortRangeTolerance;
+ double delta = threshold * size / 100;
+ assertEquals((double) size, (double) hll.count(), delta);
+ assertEquals((double) size, (double) hll2.count(), delta);
+
+ // sparse-sparse merge
+ hll.merge(hll2);
+ assertEquals((double) 2 * size, (double) hll.count(), delta);
+ assertEquals(EncodingType.SPARSE, hll.getEncoding());
+
+ // merge should update registers and hence the count
+ hll.merge(hll2);
+ assertEquals((double) 2 * size, (double) hll.count(), delta);
+ assertEquals(EncodingType.SPARSE, hll.getEncoding());
+
+ // sparse-sparse overload to dense
+ hll.merge(hll3);
+ assertEquals((double) 3 * size, (double) hll.count(), delta);
+ assertEquals(EncodingType.DENSE, hll.getEncoding());
+
+ // invalid merge -- register set size doesn't match
+ hll.merge(hll4);
+ }
+
+ @Test
+ public void testHLLSparseMoreRegisterBits() {
+ HyperLogLog hll = HyperLogLog.builder().setEncoding(EncodingType.SPARSE)
+ .setNumRegisterIndexBits(16).build();
+ int size = 1000;
+ for (int i = 0; i < size; i++) {
+ hll.addLong(i);
+ }
+ double threshold = size > 40000 ? longRangeTolerance : shortRangeTolerance;
+ double delta = threshold * size / 100;
+ assertEquals((double) size, (double) hll.count(), delta);
+ }
+}
http://git-wip-us.apache.org/repos/asf/hive/blob/b883d313/common/src/test/org/apache/hadoop/hive/common/ndv/hll/TestHyperLogLogDense.java
----------------------------------------------------------------------
diff --git a/common/src/test/org/apache/hadoop/hive/common/ndv/hll/TestHyperLogLogDense.java b/common/src/test/org/apache/hadoop/hive/common/ndv/hll/TestHyperLogLogDense.java
new file mode 100644
index 0000000..00fd785
--- /dev/null
+++ b/common/src/test/org/apache/hadoop/hive/common/ndv/hll/TestHyperLogLogDense.java
@@ -0,0 +1,82 @@
+/**
+ * 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.hadoop.hive.common.ndv.hll;
+
+import static org.junit.Assert.assertEquals;
+
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.HashSet;
+import java.util.Random;
+import java.util.Set;
+
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameters;
+
+@RunWith(value = Parameterized.class)
+public class TestHyperLogLogDense {
+
+ // 5% tolerance for long range bias and 3% for short range bias
+ private float longRangeTolerance = 5.0f;
+ private float shortRangeTolerance = 3.0f;
+
+ private int size;
+
+ public TestHyperLogLogDense(int n) {
+ this.size = n;
+ }
+
+ @Parameters
+ public static Collection<Object[]> data() {
+ Object[][] data = new Object[][] { { 2 }, { 10 }, { 100 }, { 1000 }, { 10000 }, { 100000 },
+ { 1000000 } };
+ return Arrays.asList(data);
+ }
+
+ @Test
+ public void testHLLAdd() {
+ Random rand = new Random(size);
+ HyperLogLog hll = HyperLogLog.builder().setEncoding(HyperLogLog.EncodingType.DENSE).build();
+ int size = 100;
+ for (int i = 0; i < size; i++) {
+ hll.addLong(rand.nextLong());
+ }
+ double threshold = size > 40000 ? longRangeTolerance : shortRangeTolerance;
+ double delta = threshold * size / 100;
+ assertEquals((double) size, (double) hll.count(), delta);
+ }
+
+ @Test
+ public void testHLLAddHalfDistinct() {
+ Random rand = new Random(size);
+ HyperLogLog hll = HyperLogLog.builder().setEncoding(HyperLogLog.EncodingType.DENSE).build();
+ int unique = size / 2;
+ Set<Long> hashset = new HashSet<Long>();
+ for (int i = 0; i < size; i++) {
+ long val = rand.nextInt(unique);
+ hashset.add(val);
+ hll.addLong(val);
+ }
+ double threshold = size > 40000 ? longRangeTolerance : shortRangeTolerance;
+ double delta = threshold * hashset.size() / 100;
+ assertEquals((double) hashset.size(), (double) hll.count(), delta);
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/hive/blob/b883d313/common/src/test/org/apache/hadoop/hive/common/ndv/hll/TestHyperLogLogSparse.java
----------------------------------------------------------------------
diff --git a/common/src/test/org/apache/hadoop/hive/common/ndv/hll/TestHyperLogLogSparse.java b/common/src/test/org/apache/hadoop/hive/common/ndv/hll/TestHyperLogLogSparse.java
new file mode 100644
index 0000000..cfa5886
--- /dev/null
+++ b/common/src/test/org/apache/hadoop/hive/common/ndv/hll/TestHyperLogLogSparse.java
@@ -0,0 +1,81 @@
+/**
+ * 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.hadoop.hive.common.ndv.hll;
+
+import static org.junit.Assert.assertEquals;
+
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.HashSet;
+import java.util.Random;
+import java.util.Set;
+
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameters;
+
+@RunWith(value = Parameterized.class)
+public class TestHyperLogLogSparse {
+
+ // 5% tolerance for long range bias and 1% for short range bias
+ private float longRangeTolerance = 5.0f;
+ private float shortRangeTolerance = 1.0f;
+
+ private int size;
+
+ public TestHyperLogLogSparse(int n) {
+ this.size = n;
+ }
+
+ @Parameters
+ public static Collection<Object[]> data() {
+ Object[][] data = new Object[][] { { 2 }, { 10 }, { 100 }, { 1000 }, { 10000 }, { 100000 },
+ { 1000000 } };
+ return Arrays.asList(data);
+ }
+
+ @Test
+ public void testHLLAdd() {
+ Random rand = new Random(size);
+ HyperLogLog hll = HyperLogLog.builder().build();
+ int size = 100;
+ for (int i = 0; i < size; i++) {
+ hll.addLong(rand.nextLong());
+ }
+ double threshold = size > 40000 ? longRangeTolerance : shortRangeTolerance;
+ double delta = threshold * size / 100;
+ assertEquals((double) size, (double) hll.count(), delta);
+ }
+
+ @Test
+ public void testHLLAddHalfDistinct() {
+ Random rand = new Random(size);
+ HyperLogLog hll = HyperLogLog.builder().build();
+ int unique = size / 2;
+ Set<Long> hashset = new HashSet<Long>();
+ for (int i = 0; i < size; i++) {
+ long val = rand.nextInt(unique);
+ hashset.add(val);
+ hll.addLong(val);
+ }
+ double threshold = size > 40000 ? longRangeTolerance : shortRangeTolerance;
+ double delta = threshold * hashset.size() / 100;
+ assertEquals((double) hashset.size(), (double) hll.count(), delta);
+ }
+}
http://git-wip-us.apache.org/repos/asf/hive/blob/b883d313/common/src/test/org/apache/hadoop/hive/common/ndv/hll/TestSparseEncodeHash.java
----------------------------------------------------------------------
diff --git a/common/src/test/org/apache/hadoop/hive/common/ndv/hll/TestSparseEncodeHash.java b/common/src/test/org/apache/hadoop/hive/common/ndv/hll/TestSparseEncodeHash.java
new file mode 100644
index 0000000..2c7e89b
--- /dev/null
+++ b/common/src/test/org/apache/hadoop/hive/common/ndv/hll/TestSparseEncodeHash.java
@@ -0,0 +1,56 @@
+/**
+ * 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.hadoop.hive.common.ndv.hll;
+
+import static org.junit.Assert.assertEquals;
+
+import java.util.Arrays;
+import java.util.Collection;
+
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameters;
+
+@RunWith(value = Parameterized.class)
+public class TestSparseEncodeHash {
+
+ private long input;
+ private int expected;
+
+ public TestSparseEncodeHash(long i, int e) {
+ this.input = i;
+ this.expected = e;
+ }
+
+ @Parameters
+ public static Collection<Object[]> data() {
+ Object[][] data = new Object[][] { { 11111111111L, 373692871 },
+ { 4314495982023L, -1711269433 }, { 4314529536455L, -1744823865 },
+ { 4314563074503L, 268425671 }, { 17257983908295L, -1644160569 }, { 536861127L, 536861127 },
+ { 536844743L, 536844743 }, { 144115188075862471L, -671082041 } };
+ return Arrays.asList(data);
+ }
+
+ @Test
+ public void testEncodeHash() {
+ HLLSparseRegister reg = new HLLSparseRegister(14, 25, 6);
+ int got = reg.encodeHash(input);
+ assertEquals(expected, got);
+ }
+}
http://git-wip-us.apache.org/repos/asf/hive/blob/b883d313/itests/hive-unit/src/test/java/org/apache/hadoop/hive/ql/txn/compactor/TestCompactor.java
----------------------------------------------------------------------
diff --git a/itests/hive-unit/src/test/java/org/apache/hadoop/hive/ql/txn/compactor/TestCompactor.java b/itests/hive-unit/src/test/java/org/apache/hadoop/hive/ql/txn/compactor/TestCompactor.java
index e0c05bd..44b244b 100644
--- a/itests/hive-unit/src/test/java/org/apache/hadoop/hive/ql/txn/compactor/TestCompactor.java
+++ b/itests/hive-unit/src/test/java/org/apache/hadoop/hive/ql/txn/compactor/TestCompactor.java
@@ -412,7 +412,7 @@ public class TestCompactor {
Assert.assertEquals("maxColLen b", 3, colBStats.getMaxColLen());
Assert.assertEquals("avgColLen b", 3.0, colBStats.getAvgColLen(), 0.01);
Assert.assertEquals("numNulls b", 0, colBStats.getNumNulls());
- Assert.assertEquals("nunDVs", 2, colBStats.getNumDVs());
+ Assert.assertEquals("nunDVs", 3, colBStats.getNumDVs());
//now save stats for partition we won't modify
stats = msClient.getPartitionColumnStatistics(ciPart2.dbname,
@@ -484,7 +484,7 @@ public class TestCompactor {
//cast it to long to get rid of periodic decimal
Assert.assertEquals("avgColLen b", (long)6.1111111111, (long)colBStats.getAvgColLen());
Assert.assertEquals("numNulls b", 0, colBStats.getNumNulls());
- Assert.assertEquals("nunDVs", 10, colBStats.getNumDVs());
+ Assert.assertEquals("nunDVs", 8, colBStats.getNumDVs());
//now check that stats for partition we didn't modify did not change
stats = msClient.getPartitionColumnStatistics(ciPart2.dbname, ciPart2.tableName,