Support for HyperLogLog aggregate functions

HyperLogLog is an algorithm/structure by which cardinality of a set may be estimated. It is much more efficient than count(distinct x) when a degree of error is permissible and can be used in warehousing applications, where multiple estimates of set cardinality can be merged to produce an estimate of the set union.

See blog.aggregateknowledge.com for a lot of discussion of the algorithm and for an PostgreSQL based implementation similar to what would be suggested for inclusion in Maria.

http://blog.aggregateknowledge.com/2013/02/04/open-source-release-postgresql-hll/

Proposed design (v1)

A server C++ plugin type_hll.so (INSTALL SONAME 'type_hll') that provides:

• a Pluggable Data Type HLL for storing sketches;
• Pluggable Aggregate Functions to build and merge sketches;
• native scalar functions for sketch operations.

Binary compatibility with pg_hll, ClickHouse, Redis or DuckDB is a non-goal. The format is compact, canonical, versioned and independent of C++ struct layout.

Algorithm parameters

• Classic HyperLogLog with linear-counting correction for the small range.
• Fixed precision p = 14 (m = 16384 registers), 6-bit registers, standard error ~0.81%.
• 64-bit hash: XXH3_64bits_withSeed() from bundled mysys/xxhash.h, seed 0, fixed by the format version.
• Register index = low 14 bits of the hash; rank = countr_zero(hash >> 14) + 1 (51 if the tail is zero).
• No removal / inverse transition.

Representations

• EMPTY - no payload.
• EXPLICIT - up to 256 sorted unique 64-bit hashes; exact cardinality for small sets.
• FULL - 16384 bit-packed 6-bit registers (12288 bytes).
• Promotion EXPLICIT -> FULL on the 257th distinct hash. No SPARSE in v1.

Persisted format

One header byte: bits 7..4 = format version (1), bits 3..0 = representation (1 EMPTY, 2 EXPLICIT, 3 FULL, others reserved).

• EMPTY: 0x11 (1 byte)
• EXPLICIT: 0x12 + N big-endian UInt64 hashes (1 + 8*N bytes, N = 1..256)
• FULL: 0x13 + 12288 bytes of LSB-first packed registers (12289 bytes)

No magic, length, precision, checksum or derived caches are stored. A central Hll_codec decodes and validates every input path (INSERT, CAST, binlog): length rules, strictly increasing hashes, register range 0..51, reserved/unknown version rejection. Upgrade policy: a future version reads v1+v2 but writes v1 until all nodes are upgraded; no hidden write-back on SELECT. HLL_FORMAT_VERSION(hll) is available for diagnostics.

Hash input canonicalization

Each hashed value is prefixed with a stable 1-byte type tag, so equal bytes from different domains are different elements:

• integers (all signed/unsigned widths, BOOLEAN) - one domain, so TINYINT 5 = BIGINT UNSIGNED 5;
• FLOAT/DOUBLE - IEEE-754 big-endian, -0 normalized to +0, single canonical NaN;
• DATE/TIME/DATETIME - packed semantic value (pack_time-like formula, precision-independent);
• TIMESTAMP - seconds + microseconds, independent of @@time_zone;
• YEAR, BINARY/VARBINARY/BLOB (length-prefixed bytes);
• known PDTs via explicit adapters: UUID, INET4, INET6 (INET4 and INET6 are separate domains).

Not supported in v1: DECIMAL, BIT, JSON, collatable text (CHAR/VARCHAR/TEXT/ENUM/SET) and unknown PDTs - they raise an unsupported-type error. Text must be hashed explicitly, e.g. HLL_BUILD_AGG(CAST(s AS BINARY)). The hashing helper hll_hash_item() is shared so that a future HLL_HASH() / HLL_ADD_AGG() API yields bit-identical results.

HLL data type

• Field_hll derives from Field_blob, binary charset, variable-length storage; native value = serialized format.
• Sent to clients as a binary BLOB with extended type name HLL; lossless dump/restore via mariadb-dump --hex-blob.
• Opaque non-key type: comparison operators, ORDER BY / GROUP BY / DISTINCT, MIN/MAX, indexes and partitioning on HLL are rejected.

SQL API

NULL semantics: aggregates skip NULLs; empty or all-NULL input returns HLL_EMPTY() (unlike pg_hll); scalar functions return NULL on NULL input.

Aggregates

• Implemented via Item_sum_plugin, registered with MariaDB_FUNCTION_PLUGIN.
• HLL_BUILD_AGG(DISTINCT expr) is supported; HLL_UNION_AGG(DISTINCT ...) is rejected.
• Window functions: supports_removal() = false, so moving frames are recomputed by rescan.
• Runtime state (e.g. unpacked byte-per-register array, caches) is separate from the persisted format; results are always re-encoded canonically.