CardinalityEstimation 1.15 released

by

I shipped CardinalityEstimation 1.15.0 to NuGet today – the largest batch of changes the library has seen, with twenty-one changes all landing together. The theme this release is “tighten the screws everywhere”: real bugs in the concurrent estimator, real allocations in the hot path, and a serializer that wasn’t safe to point at untrusted input. Here’s the rundown.

Security

  • Hardened CardinalityEstimatorSerializer.Read against DoS via crafted streams. The deserializer used to read bitsPerIndex and array count values straight off the wire – a malicious payload could ask for bitsPerIndex = 30 (≈1 GB allocation) or count = Int32.MaxValue (≈2 GB read). All sizes are now bounded against the same limits the public constructors enforce.
  • Bumped transitive Newtonsoft.Json to 13.0.3 to clear NU1903 in the test project.

Concurrency bug fixes

  • ConcurrentCardinalityEstimator(GetHashCodeSpanDelegate, …) was silently discarding the supplied span delegate – it chained to this(state), then the null check on hashFunction was always true and overwrote everything with the default XxHash128. Fixed.
  • Add(string) and Add(byte[]) on the concurrent estimator threw NullReferenceException instead of the documented ArgumentNullException when passed null. The non-concurrent version had always validated; now both do.
  • ParallelMerge accepted a parallelismDegree argument and silently ignored it. The code built a ParallelQuery into a local that was never read, then called .AsParallel() again four lines later without the degree. The local is gone and WithDegreeOfParallelism is applied to the real query.
  • Merge and Equals ordered their two ReaderWriterLockSlim acquisitions by comparing GetHashCode(). object.GetHashCode is not unique, so two distinct instances with colliding hashes produced an undefined ordering – an AB/BA deadlock window when one thread did a.Merge(b) while another did b.Merge(a). Replaced with a per-instance ID assigned via Interlocked.Increment at construction, so the order is strict and total.

Correctness bug fixes

  • CardinalityEstimator.Merge(IEnumerable<…>) doubled CountAdditions for the first element. The first non-null estimator was copied into result (which already copied CountAdditions) and then immediately merged with itself. Fixed by skipping the merge on the seeded element.
  • ConcurrentCardinalityEstimator(CardinalityEstimator other) substituted the default XxHash128 because CardinalityEstimator exposed no API to read its hash function back. Conversion in either direction now preserves both the byte-array and span hash delegates losslessly via new HashFunction / HashFunctionSpan properties on both types.

Performance

  • ConcurrentCardinalityEstimator direct-count storage was a ConcurrentBag<ulong> – every Add was O(1) but Count and the bag→HashSet conversion in GetState were O(n) with locking. Swapped to ConcurrentDictionary<ulong, byte>, which deduplicates on insert and gives O(1) Count.
  • Eliminated heap allocations in primitive Add overloads. Add(int) / Add(long) / Add(double) etc. used to call BitConverter.GetBytes, allocating a fresh byte[4] or byte[8] on every call. They now write into a stackalloc buffer with BinaryPrimitives and route through the span hash delegate. Add(string) does the same for short strings via Encoding.UTF8.TryGetBytes into a stackalloc buffer.
  • Replaced Math.Pow(2, -sigma) in the Count() summation loop with a precomputed InversePowersOfTwo table. The transcendental call ran up to 65,536 times per Count(); the table lookup shaves a measurable chunk off large-cardinality reads.
  • Replaced (int)Math.Pow(2, bitsPerIndex) with 1 << bitsPerIndex in estimator constructors. Exact, no floating-point round trip, no transcendental call.
  • Bulk-write the dense lookup array in the serializer. The 2^b-byte array was being written one byte at a time through BinaryWriter.Write(byte) (up to 65,536 individual calls); now it’s a single Write(byte[]).

API additions

  • Public HashFunction and HashFunctionSpan properties on CardinalityEstimator and ConcurrentCardinalityEstimator, so callers can introspect or preserve the hash function across copies, conversions, and serialization round-trips.
  • CardinalityEstimator now implements ICardinalityEstimatorMemory with Add overloads for Span<byte>, ReadOnlySpan<byte>, Memory<byte>, and ReadOnlyMemory<byte>. These route through GetHashCodeSpanDelegate and avoid the byte-array allocation of the legacy path entirely.

Refactor

  • Hoisted the duplicated estimator constants (DirectCounterMaxElements, StackallocByteThreshold) and helpers (GetAlphaM, GetSubAlgorithmSelectionThreshold, CreateEmptyState) out of both estimator classes into a shared HllConstants type. Two implementations, one source of truth.
  • Documented the intentionally empty if (dataFormatMajorVersion >= 3) { … } branch in the serializer. The block looked dead but actually intercepts v3+ payloads so they don’t fall through to the v2 byte read; the comment now explains why.

Tests & tooling

  • Switched target frameworks from net8.0 / net9.0 to net8.0 / net10.0.
  • Added 30+ tests closing coverage gaps across the estimators, serializer, hash functions, and extensions. Final coverage on version-1.15: 98% line / 91% branch.

Documentation

  • README rewrite. The previous version had an empty “Release Notes” section and no mention of thread safety, the b parameter, merging, serialization, the span/memory overloads, or hash function selection. All of those now have their own section with runnable examples. Added the dotnet add package CardinalityEstimation install snippet alongside the legacy Install-Package form, and fixed a dead Google paper link.
  • XML doc tightening on ICardinalityEstimatorMemory (clarified that Span<byte> / ReadOnlySpan<byte> are the true zero-allocation paths, not Memory<byte>) and on CardinalityEstimatorExtensions.CreateMultiple (the b parameter doc now matches the constructor’s: range, default, accuracy implication).

NuGet: CardinalityEstimation 1.15.0 · Strong-named: CardinalityEstimation.Signed 1.15.0 · Source: github.com/saguiitay/CardinalityEstimation

Should be a drop-in upgrade from 1.14.x – the binary serialization format is unchanged (same major version), the public API is additive, and the deserializer’s new validation only rejects payloads that wouldn’t have come from a legitimate serializer in the first place. Two things worth double-checking if you’ve been using the library in anger:

  1. If you ever passed a GetHashCodeSpanDelegate to ConcurrentCardinalityEstimator, your delegate was being silently dropped before this release. After upgrading you’ll start getting the hash you actually asked for, which means counts may shift slightly on existing in-memory instances (serialized state is unaffected).
  2. If you converted between CardinalityEstimator and ConcurrentCardinalityEstimator while using a non-default hash, the converted instance was using XxHash128 instead. Same situation – your hash is preserved now, so post-upgrade counts on freshly-converted instances will match the source.