Function initHyperLogLog

src/backend/lib/hyperloglog.c:65–109

* Initialize HyperLogLog track state, by bit width * * bwidth is bit width (so register size will be 2 to the power of bwidth). * Must be between 4 and 16 inclusive. */

 * Must be between 4 and 16 inclusive.
 */
void
initHyperLogLog(hyperLogLogState *cState, uint8 bwidth)
{
	double		alpha;

	if (bwidth < 4 || bwidth > 16)
		elog(ERROR, "bit width must be between 4 and 16 inclusive");

	cState->registerWidth = bwidth;
	cState->nRegisters = (Size) 1 << bwidth;
	cState->arrSize = sizeof(uint8) * cState->nRegisters + 1;

	/*
	 * Initialize hashes array to zero, not negative infinity, per discussion
	 * of the coupon collector problem in the HyperLogLog paper
	 */
	cState->hashesArr = palloc0(cState->arrSize);

	/*
	 * "alpha" is a value that for each possible number of registers (m) is
	 * used to correct a systematic multiplicative bias present in m ^ 2 Z (Z
	 * is "the indicator function" through which we finally compute E,
	 * estimated cardinality).
	 */
	switch (cState->nRegisters)
	{
		case 16:
			alpha = 0.673;
			break;
		case 32:
			alpha = 0.697;
			break;
		case 64:
			alpha = 0.709;
			break;
		default:
			alpha = 0.7213 / (1.0 + 1.079 / cState->nRegisters);
	}

	/*
	 * Precalculate alpha m ^ 2, later used to generate "raw" HyperLogLog
	 * estimate E
	 */
	cState->alphaMM = alpha * cState->nRegisters * cState->nRegisters;
}

/*
 * Initialize HyperLogLog track state, by error rate