duckdb::HyperLogLog Class Reference

#include <duckdb.hpp>

Public Member Functions
void	InsertElement (hash_t h)
	Algorithm 1.
void	Update (const idx_t &i, const uint8_t &z)
uint8_t	GetRegister (const idx_t &i) const
idx_t	Count () const
void	Merge (const HyperLogLog &other)
	Algorithm 2.
void	Update (Vector &input, Vector &hashes, idx_t count)
	Add data to this HLL.
unique_ptr< HyperLogLog >	Copy () const
	Get copy of the HLL.
void	Serialize (Serializer &serializer) const
void	ExtractCounts (uint32_t *c) const
	Algorithm 4.

Static Public Member Functions
static double	GetErrorRate ()
static unique_ptr< HyperLogLog >	Deserialize (Deserializer &deserializer)
static int64_t	EstimateCardinality (uint32_t *c)
	Algorithm 6.

Static Public Attributes
static constexpr idx_t	P = 6
static constexpr idx_t	Q = 64 - P
static constexpr idx_t	M = 1 << P
static constexpr double	ALPHA = 0.721347520444481703680

Private Attributes
uint8_t	k [M]

Detailed Description

Algorithms from "New cardinality estimation algorithms for HyperLogLog sketches" Otmar Ertl, arXiv:1702.01284

Constructor & Destructor Documentation

HyperLogLog()

duckdb::HyperLogLog::HyperLogLog ( )

inline

                  {
        memset(k, 0, sizeof(k));
    }

Member Function Documentation

GetErrorRate()

static double duckdb::HyperLogLog::GetErrorRate ( )

inlinestatic

                                 {
        return std::sqrt(PI / 2.0) / sqrt(M);
    }

InsertElement()

void duckdb::HyperLogLog::InsertElement ( hash_t  h )

inline

Algorithm 1.

                                        {
        const auto i = h & ((1 << P) - 1);
        h >>= P;
        h |= hash_t(1) << Q;
        const uint8_t z = UnsafeNumericCast<uint8_t>(CountZeros<hash_t>::Trailing(h) + 1);
        Update(i, z);
    }

Update()

void duckdb::HyperLogLog::Update ( const idx_t &  i, const uint8_t &  z  )

inline

                                                         {
        k[i] = MaxValue<uint8_t>(k[i], z);
    }

GetRegister()

uint8_t duckdb::HyperLogLog::GetRegister ( const idx_t &  i ) const

inline

                                                     {
        return k[i];
    }

---

The documentation for this class was generated from the following file:

• external/duckdb/duckdb.hpp