| 106 | } |
| 107 | |
| 108 | IMPALA_UDF_EXPORT |
| 109 | StringVal HllFinalize(FunctionContext* ctx, const StringVal& src) { |
| 110 | assert(!src.is_null); |
| 111 | assert(src.len == pow(2, HLL_PRECISION)); |
| 112 | |
| 113 | const int num_streams = pow(2, HLL_PRECISION); |
| 114 | // Empirical constants for the algorithm. |
| 115 | float alpha = 0; |
| 116 | if (num_streams == 16) { |
| 117 | alpha = 0.673f; |
| 118 | } else if (num_streams == 32) { |
| 119 | alpha = 0.697f; |
| 120 | } else if (num_streams == 64) { |
| 121 | alpha = 0.709f; |
| 122 | } else { |
| 123 | alpha = 0.7213f / (1 + 1.079f / num_streams); |
| 124 | } |
| 125 | |
| 126 | float harmonic_mean = 0; |
| 127 | int num_zero_registers = 0; |
| 128 | for (int i = 0; i < src.len; ++i) { |
| 129 | harmonic_mean += powf(2.0f, -src.ptr[i]); |
| 130 | if (src.ptr[i] == 0) ++num_zero_registers; |
| 131 | } |
| 132 | harmonic_mean = 1.0f / harmonic_mean; |
| 133 | int64_t estimate = alpha * num_streams * num_streams * harmonic_mean; |
| 134 | |
| 135 | if (num_zero_registers != 0) { |
| 136 | // Estimated cardinality is too low. Hll is too inaccurate here, instead use |
| 137 | // linear counting. |
| 138 | estimate = num_streams * log(static_cast<float>(num_streams) / num_zero_registers); |
| 139 | } |
| 140 | |
| 141 | // Output the estimate as ascii string |
| 142 | stringstream out; |
| 143 | out << estimate; |
| 144 | string out_str = out.str(); |
| 145 | StringVal result_str(ctx, out_str.size()); |
| 146 | memcpy(result_str.ptr, out_str.c_str(), result_str.len); |
| 147 | ctx->Free(src.ptr); |
| 148 | return result_str; |
| 149 | } |