PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
hyperloglog.h File Reference
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  hyperLogLogState
 

Typedefs

typedef struct hyperLogLogState hyperLogLogState
 

Functions

void initHyperLogLog (hyperLogLogState *cState, uint8 bwidth)
 
void initHyperLogLogError (hyperLogLogState *cState, double error)
 
void addHyperLogLog (hyperLogLogState *cState, uint32 hash)
 
double estimateHyperLogLog (hyperLogLogState *cState)
 
void freeHyperLogLog (hyperLogLogState *cState)
 

Typedef Documentation

Function Documentation

void addHyperLogLog ( hyperLogLogState cState,
uint32  hash 
)

Definition at line 166 of file hyperloglog.c.

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

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

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

Definition at line 185 of file hyperloglog.c.

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

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

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

Definition at line 150 of file hyperloglog.c.

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

151 {
152  Assert(cState->hashesArr != NULL);
153  pfree(cState->hashesArr);
154 }
uint8 * hashesArr
Definition: hyperloglog.h:58
void pfree(void *pointer)
Definition: mcxt.c:950
#define NULL
Definition: c.h:229
#define Assert(condition)
Definition: c.h:675
void initHyperLogLog ( hyperLogLogState cState,
uint8  bwidth 
)

Definition at line 65 of file hyperloglog.c.

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

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

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

Definition at line 127 of file hyperloglog.c.

References error(), and initHyperLogLog().

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