hyperloglog.c File Reference

#include "postgres.h"
#include <math.h>
#include "lib/hyperloglog.h"
#include "port/pg_bitutils.h"

Include dependency graph for hyperloglog.c:

Go to the source code of this file.

Macros
#define	POW_2_32   (4294967296.0)
#define	NEG_POW_2_32   (-4294967296.0)

Functions
static uint8	rho (uint32 x, uint8 b)
void	initHyperLogLog (hyperLogLogState *cState, uint8 bwidth)
void	initHyperLogLogError (hyperLogLogState *cState, double error)
void	freeHyperLogLog (hyperLogLogState *cState)
void	addHyperLogLog (hyperLogLogState *cState, uint32 hash)
double	estimateHyperLogLog (hyperLogLogState *cState)

Macro Definition Documentation

NEG_POW_2_32

#define NEG_POW_2_32   (-4294967296.0)

Definition at line 55 of file hyperloglog.c.

POW_2_32

#define POW_2_32   (4294967296.0)

Definition at line 54 of file hyperloglog.c.

Function Documentation

addHyperLogLog()

void addHyperLogLog	(	hyperLogLogState *	cState,
		uint32	hash
	)

Definition at line 167 of file hyperloglog.c.

{
    uint8       count;
    uint32      index;
 
    /* Use the first "k" (registerWidth) bits as a zero based index */
    index = hash >> (BITS_PER_BYTE * sizeof(uint32) - cState->registerWidth);
 
    /* Compute the rank of the remaining 32 - "k" (registerWidth) bits */
    count = rho(hash << cState->registerWidth,
                BITS_PER_BYTE * sizeof(uint32) - cState->registerWidth);
 
    cState->hashesArr[index] = Max(count, cState->hashesArr[index]);
}

References BITS_PER_BYTE, hash(), hyperLogLogState::hashesArr, Max, hyperLogLogState::registerWidth, and rho().

Referenced by hashagg_spill_tuple(), macaddr_abbrev_convert(), network_abbrev_convert(), uuid_abbrev_convert(), and varstr_abbrev_convert().

estimateHyperLogLog()

double estimateHyperLogLog

(

hyperLogLogState *

cState

)

Definition at line 186 of file hyperloglog.c.

{
    double      result;
    double      sum = 0.0;
    int         i;
 
    for (i = 0; i < cState->nRegisters; i++)
    {
        sum += 1.0 / pow(2.0, cState->hashesArr[i]);
    }
 
    /* result set to "raw" HyperLogLog estimate (E in the HyperLogLog paper) */
    result = cState->alphaMM / sum;
 
    if (result <= (5.0 / 2.0) * cState->nRegisters)
    {
        /* Small range correction */
        int         zero_count = 0;
 
        for (i = 0; i < cState->nRegisters; i++)
        {
            if (cState->hashesArr[i] == 0)
                zero_count++;
        }
 
        if (zero_count != 0)
            result = cState->nRegisters * log((double) cState->nRegisters /
                                              zero_count);
    }
    else if (result > (1.0 / 30.0) * POW_2_32)
    {
        /* Large range correction */
        result = NEG_POW_2_32 * log(1.0 - (result / POW_2_32));
    }
 
    return result;
}

References hyperLogLogState::alphaMM, hyperLogLogState::hashesArr, i, NEG_POW_2_32, hyperLogLogState::nRegisters, and POW_2_32.

Referenced by hashagg_spill_finish(), macaddr_abbrev_abort(), network_abbrev_abort(), numeric_abbrev_abort(), uuid_abbrev_abort(), and varstr_abbrev_abort().

freeHyperLogLog()

void freeHyperLogLog

(

hyperLogLogState *

cState

)

Definition at line 151 of file hyperloglog.c.

{
    Assert(cState->hashesArr != NULL);
    pfree(cState->hashesArr);
}

References Assert, hyperLogLogState::hashesArr, and pfree().

Referenced by hashagg_spill_finish().

initHyperLogLog()

void initHyperLogLog	(	hyperLogLogState *	cState,
		uint8	bwidth
	)

Definition at line 66 of file hyperloglog.c.

{
    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;
}

References hyperLogLogState::alphaMM, hyperLogLogState::arrSize, elog, ERROR, hyperLogLogState::hashesArr, hyperLogLogState::nRegisters, palloc0(), and hyperLogLogState::registerWidth.

Referenced by hashagg_spill_init(), initHyperLogLogError(), macaddr_sortsupport(), network_sortsupport(), numeric_sortsupport(), uuid_sortsupport(), and varstr_sortsupport().

initHyperLogLogError()

void initHyperLogLogError	(	hyperLogLogState *	cState,
		double	error
	)

Definition at line 128 of file hyperloglog.c.

{
    uint8       bwidth = 4;
 
    while (bwidth < 16)
    {
        double      m = (Size) 1 << bwidth;
 
        if (1.04 / sqrt(m) < error)
            break;
        bwidth++;
    }
 
    initHyperLogLog(cState, bwidth);
}

References error(), and initHyperLogLog().

rho()

static uint8 rho ( uint32  x, uint8  b  )

inlinestatic

Definition at line 242 of file hyperloglog.c.

{
    uint8       j = 1;
 
    if (x == 0)
        return b + 1;
 
    j = 32 - pg_leftmost_one_pos32(x);
 
    if (j > b)
        return b + 1;
 
    return j;
}

References b, j, pg_leftmost_one_pos32(), and x.

Referenced by addHyperLogLog().