PostgreSQL Source Code  git master
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.

Referenced by estimateHyperLogLog().

◆ POW_2_32

#define POW_2_32   (4294967296.0)

Definition at line 54 of file hyperloglog.c.

Referenced by estimateHyperLogLog().

Function Documentation

◆ addHyperLogLog()

void addHyperLogLog ( hyperLogLogState cState,
uint32  hash 
)

Definition at line 167 of file hyperloglog.c.

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

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

168 {
169  uint8 count;
170  uint32 index;
171 
172  /* Use the first "k" (registerWidth) bits as a zero based index */
173  index = hash >> (BITS_PER_BYTE * sizeof(uint32) - cState->registerWidth);
174 
175  /* Compute the rank of the remaining 32 - "k" (registerWidth) bits */
176  count = rho(hash << cState->registerWidth,
177  BITS_PER_BYTE * sizeof(uint32) - cState->registerWidth);
178 
179  cState->hashesArr[index] = Max(count, cState->hashesArr[index]);
180 }
#define BITS_PER_BYTE
uint8 * hashesArr
Definition: hyperloglog.h:58
unsigned char uint8
Definition: c.h:427
Definition: type.h:89
static uint8 rho(uint32 x, uint8 b)
Definition: hyperloglog.c:242
unsigned int uint32
Definition: c.h:429
#define Max(x, y)
Definition: c.h:976
static unsigned hash(unsigned *uv, int n)
Definition: rege_dfa.c:541

◆ estimateHyperLogLog()

double estimateHyperLogLog ( hyperLogLogState cState)

Definition at line 186 of file hyperloglog.c.

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().

187 {
188  double result;
189  double sum = 0.0;
190  int i;
191 
192  for (i = 0; i < cState->nRegisters; i++)
193  {
194  sum += 1.0 / pow(2.0, cState->hashesArr[i]);
195  }
196 
197  /* result set to "raw" HyperLogLog estimate (E in the HyperLogLog paper) */
198  result = cState->alphaMM / sum;
199 
200  if (result <= (5.0 / 2.0) * cState->nRegisters)
201  {
202  /* Small range correction */
203  int zero_count = 0;
204 
205  for (i = 0; i < cState->nRegisters; i++)
206  {
207  if (cState->hashesArr[i] == 0)
208  zero_count++;
209  }
210 
211  if (zero_count != 0)
212  result = cState->nRegisters * log((double) cState->nRegisters /
213  zero_count);
214  }
215  else if (result > (1.0 / 30.0) * POW_2_32)
216  {
217  /* Large range correction */
218  result = NEG_POW_2_32 * log(1.0 - (result / POW_2_32));
219  }
220 
221  return result;
222 }
#define POW_2_32
Definition: hyperloglog.c:54
uint8 * hashesArr
Definition: hyperloglog.h:58
int i
#define NEG_POW_2_32
Definition: hyperloglog.c:55

◆ freeHyperLogLog()

void freeHyperLogLog ( hyperLogLogState cState)

Definition at line 151 of file hyperloglog.c.

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

Referenced by hashagg_spill_finish().

152 {
153  Assert(cState->hashesArr != NULL);
154  pfree(cState->hashesArr);
155 }
uint8 * hashesArr
Definition: hyperloglog.h:58
void pfree(void *pointer)
Definition: mcxt.c:1057
#define Assert(condition)
Definition: c.h:800

◆ initHyperLogLog()

void initHyperLogLog ( hyperLogLogState cState,
uint8  bwidth 
)

Definition at line 66 of file hyperloglog.c.

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().

67 {
68  double alpha;
69 
70  if (bwidth < 4 || bwidth > 16)
71  elog(ERROR, "bit width must be between 4 and 16 inclusive");
72 
73  cState->registerWidth = bwidth;
74  cState->nRegisters = (Size) 1 << bwidth;
75  cState->arrSize = sizeof(uint8) * cState->nRegisters + 1;
76 
77  /*
78  * Initialize hashes array to zero, not negative infinity, per discussion
79  * of the coupon collector problem in the HyperLogLog paper
80  */
81  cState->hashesArr = palloc0(cState->arrSize);
82 
83  /*
84  * "alpha" is a value that for each possible number of registers (m) is
85  * used to correct a systematic multiplicative bias present in m ^ 2 Z (Z
86  * is "the indicator function" through which we finally compute E,
87  * estimated cardinality).
88  */
89  switch (cState->nRegisters)
90  {
91  case 16:
92  alpha = 0.673;
93  break;
94  case 32:
95  alpha = 0.697;
96  break;
97  case 64:
98  alpha = 0.709;
99  break;
100  default:
101  alpha = 0.7213 / (1.0 + 1.079 / cState->nRegisters);
102  }
103 
104  /*
105  * Precalculate alpha m ^ 2, later used to generate "raw" HyperLogLog
106  * estimate E
107  */
108  cState->alphaMM = alpha * cState->nRegisters * cState->nRegisters;
109 }
uint8 * hashesArr
Definition: hyperloglog.h:58
unsigned char uint8
Definition: c.h:427
#define ERROR
Definition: elog.h:43
void * palloc0(Size size)
Definition: mcxt.c:981
size_t Size
Definition: c.h:528
#define elog(elevel,...)
Definition: elog.h:228

◆ initHyperLogLogError()

void initHyperLogLogError ( hyperLogLogState cState,
double  error 
)

Definition at line 128 of file hyperloglog.c.

References error(), and initHyperLogLog().

129 {
130  uint8 bwidth = 4;
131 
132  while (bwidth < 16)
133  {
134  double m = (Size) 1 << bwidth;
135 
136  if (1.04 / sqrt(m) < error)
137  break;
138  bwidth++;
139  }
140 
141  initHyperLogLog(cState, bwidth);
142 }
static void error(void)
Definition: sql-dyntest.c:147
unsigned char uint8
Definition: c.h:427
void initHyperLogLog(hyperLogLogState *cState, uint8 bwidth)
Definition: hyperloglog.c:66
size_t Size
Definition: c.h:528

◆ rho()

static uint8 rho ( uint32  x,
uint8  b 
)
inlinestatic

Definition at line 242 of file hyperloglog.c.

References pg_leftmost_one_pos32().

Referenced by addHyperLogLog().

243 {
244  uint8 j = 1;
245 
246  if (x == 0)
247  return b + 1;
248 
249  j = 32 - pg_leftmost_one_pos32(x);
250 
251  if (j > b)
252  return b + 1;
253 
254  return j;
255 }
unsigned char uint8
Definition: c.h:427
static int pg_leftmost_one_pos32(uint32 word)
Definition: pg_bitutils.h:32