ExDataSketch.CQF (ExDataSketch v0.10.3)

Copy Markdown View Source

Counting Quotient Filter (CQF) for multiset membership with approximate counting.

A CQF extends the Quotient filter with variable-length counter encoding, enabling not just "is this item present?" but "how many times has this item been inserted?" It uses the same quotient/remainder hash split as a standard Quotient filter, but stores counts inline using a monotonicity-violation encoding scheme within runs.

Counter Encoding

Remainders within a run are stored in strictly increasing order. A count of N for one remainder is represented as N-1 consecutive duplicate copies of that remainder immediately following the original (count is recovered at read time by counting how many consecutive slots repeat the same value) -- there is no compact run-length/bracketing scheme; every unit of count beyond the first costs one physical slot. See "Sizing :q" below for what this means for capacity planning.

Parameters

  • :q -- quotient bits (default: 16). Determines the number of slots: 2^q.
  • :r -- remainder bits (default: 8). Determines false positive rate: ~1/2^r. Constraint: q + r <= 64.
  • :seed -- hash seed (default: 0).

Sizing :q: budget for total occurrences, not distinct keys

Every occurrence of every item costs one physical slot -- not just distinct keys (see "Counter Encoding" above). Size 2^q against the sum of all expected insert counts (total_count, what count/1 returns), not the number of distinct items you expect to track.

put/2 and put_many/2 return {:ok, cqf} / {:ok, cqf} | {:error, :full, partial_cqf} when the table has no room left for an insert, mirroring ExDataSketch.Cuckoo -- put!/2 and update/2/ update_many/2 raise ExDataSketch.Errors.FilterFullError instead of returning the error tuple. Before this signal existed, an undersized :q failed silently and expensively rather than raising: as the table filled, each insert searched further for a free slot (the shift-right cascade is bounded to slot_count steps specifically so it terminates rather than looping forever), and once genuinely full, further inserts were dropped without any error. A table sized at roughly a third of its needed capacity (e.g. q: 18, 262,144 slots, for 1,000,000 total occurrences) could take from minutes to hours to build instead of a fraction of a second at a properly-sized q (confirmed: q: 21, 2,097,152 slots, ~2x headroom, builds the same 1,000,000-event dataset in well under a second) -- size generously rather than relying on the error signal alone. See livebooks/sketches/cqf.livemd's "Sizing: q must budget for total occurrences, not distinct keys" section for a worked example.

Merge Semantics

CQF merge is a multiset union: counts for identical fingerprints are summed, not OR'd. This enables distributed counting use cases where partial counts from multiple workers are combined.

member?/estimate_count/2 Performance

member?/2, estimate_count/2, and delete/2 decode only the 40-byte header plus whichever slots the lookup actually touches -- typically a handful, the length of one run -- rather than the whole slot table. This is independent of which :backend is configured: there's no per-item Rust NIF for these (only put_many/2/put_many_raw/2 do), so they always run through this path. Earlier versions of this module decoded the entire table into a tuple on every single call regardless of backend, making these calls cost O(slot_count) per call -- confirmed at roughly 190ms per single call against a q: 18 (262,144-slot) filter, purely from that decode.

Binary State Layout (CQF1)

40-byte header followed by a packed slot array. Each slot contains 3 metadata bits (is_occupied, is_continuation, is_shifted) and r remainder bits, packed LSB-first. The header includes a 64-bit total_count field tracking the sum of all item multiplicities.

Summary

Types

t()

Functions

capabilities()

Returns the set of capabilities supported by CQF.

compatible_with?(cqf1, cqf2)

Returns true if two CQFs have compatible parameters.

count(cqf)

Returns the total count of all items (sum of all multiplicities).

delete(cqf, item)

Deletes a single occurrence of an item (decrements its count).

deserialize(binary)

Deserializes an EXSK binary into a CQF.

estimate_count(cqf, item)

Returns the estimated count (multiplicity) of an item.

from_enumerable(enumerable, opts \\ [])

Creates a CQF from an enumerable of items.

member?(cqf, item)

Tests whether an item may be a member of the multiset.

merge(cqf, cqf)

Merges two CQFs via multiset union (counts are summed).

merge_many(filters)

Merges a non-empty enumerable of CQFs into one.

merger(opts \\ [])

Returns a 2-arity merge function for combining filters.

new(opts \\ [])

Creates a new empty Counting Quotient Filter.

put(cqf, item)

Inserts a single item into the filter, incrementing its count.

put!(cqf, item)

Inserts a single item, raising on failure.

put_many(cqf, items)

Inserts multiple items in a single pass.

reducer()

Returns a 2-arity reducer function for use with Enum.reduce/3.

serialize(cqf, serialize_opts \\ [])

Serializes the filter to the EXSK binary format.

size_bytes(cqf)

Returns the byte size of the state binary.

update(cqf, item)

Alias for put!/2, added so ExDataSketch.CQF satisfies the ExDataSketch.Sketch behaviour's generic update/2 callback (which returns a bare sketch, not {:ok, ...} | {:error, ...}).

update_many(cqf, items)

Alias for put_many/2, added so ExDataSketch.CQF satisfies the ExDataSketch.Sketch behaviour's generic update_many/2 callback. Raises ExDataSketch.Errors.FilterFullError if the table fills up partway through -- use put_many/2 directly to keep the partial result instead.

Types

t()

@type t() :: %ExDataSketch.CQF{backend: module(), opts: keyword(), state: binary()}

Functions

capabilities()

Returns the set of capabilities supported by CQF.

compatible_with?(cqf1, cqf2)

@spec compatible_with?(t(), t()) :: boolean()

Returns true if two CQFs have compatible parameters.

Examples

iex> a = ExDataSketch.CQF.new(q: 10, r: 8)
iex> b = ExDataSketch.CQF.new(q: 10, r: 8)
iex> ExDataSketch.CQF.compatible_with?(a, b)
true

count(cqf)

@spec count(t()) :: non_neg_integer()

Returns the total count of all items (sum of all multiplicities).

Examples

iex> ExDataSketch.CQF.new(q: 10, r: 8) |> ExDataSketch.CQF.count()
0

delete(cqf, item)

@spec delete(t(), term()) :: t()

Deletes a single occurrence of an item (decrements its count).

If the item's count reaches 0, it is removed entirely. Deleting a non-member is a no-op.

Examples

iex> cqf = ExDataSketch.CQF.new(q: 10, r: 8) |> ExDataSketch.CQF.put!("hello")
iex> cqf = ExDataSketch.CQF.delete(cqf, "hello")
iex> ExDataSketch.CQF.member?(cqf, "hello")
false

deserialize(binary)

@spec deserialize(binary()) :: {:ok, t()} | {:error, Exception.t()}

Deserializes an EXSK binary into a CQF.

Returns {:ok, cqf} on success or {:error, reason} on failure.

Examples

iex> cqf = ExDataSketch.CQF.new(q: 10, r: 8) |> ExDataSketch.CQF.put!("test")
iex> {:ok, recovered} = ExDataSketch.CQF.deserialize(ExDataSketch.CQF.serialize(cqf))
iex> ExDataSketch.CQF.member?(recovered, "test")
true

estimate_count(cqf, item)

@spec estimate_count(t(), term()) :: non_neg_integer()

Returns the estimated count (multiplicity) of an item.

Returns 0 if the item is not present. Due to hash collisions, the count may be an overestimate but never an underestimate.

Examples

iex> cqf = ExDataSketch.CQF.new(q: 10, r: 8)
iex> cqf = cqf |> ExDataSketch.CQF.put!("x") |> ExDataSketch.CQF.put!("x") |> ExDataSketch.CQF.put!("x")
iex> ExDataSketch.CQF.estimate_count(cqf, "x")
3

from_enumerable(enumerable, opts \\ [])

@spec from_enumerable(
  Enumerable.t(),
  keyword()
) :: {:ok, t()} | {:error, :full, t()}

Creates a CQF from an enumerable of items.

Equivalent to new(opts) |> put_many(enumerable). Returns {:ok, cqf} or {:error, :full, partial_cqf} -- see put_many/2.

Examples

iex> {:ok, cqf} = ExDataSketch.CQF.from_enumerable(["a", "b", "c"])
iex> ExDataSketch.CQF.member?(cqf, "a")
true

member?(cqf, item)

@spec member?(t(), term()) :: boolean()

Tests whether an item may be a member of the multiset.

Returns true if the item is possibly in the set (may be a false positive), false if the item is definitely not in the set.

Examples

iex> cqf = ExDataSketch.CQF.new(q: 10, r: 8) |> ExDataSketch.CQF.put!("hello")
iex> ExDataSketch.CQF.member?(cqf, "hello")
true

iex> cqf = ExDataSketch.CQF.new(q: 10, r: 8)
iex> ExDataSketch.CQF.member?(cqf, "hello")
false

merge(cqf, cqf)

@spec merge(t(), t()) :: t()

Merges two CQFs via multiset union (counts are summed).

Both filters must have identical q, r, and seed. Raises ExDataSketch.Errors.IncompatibleSketchesError if parameters differ.

Examples

iex> a = ExDataSketch.CQF.new(q: 10, r: 8) |> ExDataSketch.CQF.put!("x")
iex> b = ExDataSketch.CQF.new(q: 10, r: 8) |> ExDataSketch.CQF.put!("y")
iex> merged = ExDataSketch.CQF.merge(a, b)
iex> ExDataSketch.CQF.member?(merged, "x") and ExDataSketch.CQF.member?(merged, "y")
true

merge_many(filters)

@spec merge_many(Enumerable.t()) :: t()

Merges a non-empty enumerable of CQFs into one.

Examples

iex> filters = Enum.map(1..3, fn i ->
...>   ExDataSketch.CQF.new(q: 10, r: 8) |> ExDataSketch.CQF.put!("item_#{i}")
...> end)
iex> merged = ExDataSketch.CQF.merge_many(filters)
iex> ExDataSketch.CQF.member?(merged, "item_1")
true

merger(opts \\ [])

@spec merger(keyword()) :: (t(), t() -> t())

Returns a 2-arity merge function for combining filters.

Examples

iex> is_function(ExDataSketch.CQF.merger(), 2)
true

new(opts \\ [])

@spec new(keyword()) :: t()

Creates a new empty Counting Quotient Filter.

Options

  • :q -- quotient bits (default: 16). Range: 1..28.
  • :r -- remainder bits (default: 8). Range: 1..32. Constraint: q + r <= 64.
  • :seed -- hash seed (default: 0).
  • :backend -- backend module (default: ExDataSketch.Backend.Pure).
  • :hash_fn -- custom hash function (term -> non_neg_integer).

Examples

iex> cqf = ExDataSketch.CQF.new()
iex> cqf.opts[:q]
16

iex> cqf = ExDataSketch.CQF.new(q: 12, r: 10)
iex> cqf.opts[:r]
10

put(cqf, item)

@spec put(t(), term()) :: {:ok, t()} | {:error, :full}

Inserts a single item into the filter, incrementing its count.

Returns {:ok, cqf}, or {:error, :full} if the table has no capacity left for the insertion -- see the "Sizing :q" section above. Unlike put_many/2, there is no partial state to return on failure: the filter is unchanged. See put!/2 for a raising, chainable variant.

Examples

iex> {:ok, cqf} = ExDataSketch.CQF.new(q: 10, r: 8) |> ExDataSketch.CQF.put("hello")
iex> ExDataSketch.CQF.member?(cqf, "hello")
true

put!(cqf, item)

@spec put!(t(), term()) :: t()

Inserts a single item, raising on failure.

Added for chaining convenience (new() |> put!(...) |> put!(...)) -- put/2 remains the family-idiomatic name for callers that want to handle a full table explicitly.

Examples

iex> cqf = ExDataSketch.CQF.new(q: 10, r: 8) |> ExDataSketch.CQF.put!("hello")
iex> ExDataSketch.CQF.member?(cqf, "hello")
true

put_many(cqf, items)

@spec put_many(t(), Enumerable.t()) :: {:ok, t()} | {:error, :full, t()}

Inserts multiple items in a single pass.

Returns {:ok, cqf} if all items were inserted, or {:error, :full, partial_cqf} if the table filled up partway through -- partial_cqf reflects every item inserted before the one that didn't fit.

Examples

iex> {:ok, cqf} = ExDataSketch.CQF.new(q: 10, r: 8) |> ExDataSketch.CQF.put_many(["a", "b"])
iex> ExDataSketch.CQF.member?(cqf, "a")
true

reducer()

@spec reducer() :: (term(), t() -> t())

Returns a 2-arity reducer function for use with Enum.reduce/3.

The reducer calls put!/2 and raises if the filter becomes full.

Examples

iex> is_function(ExDataSketch.CQF.reducer(), 2)
true

serialize(cqf, serialize_opts \\ [])

@spec serialize(
  t(),
  keyword()
) :: binary()

Serializes the filter to the EXSK binary format.

Options

  • :format - serialization format: :v2 (default, EXSK v2 with CRC32C) or :v1 (legacy EXSK v1, compatible with v0.7.x readers). The v1 format is only valid for filters using :phash2 hash strategy.

Examples

iex> cqf = ExDataSketch.CQF.new(q: 10, r: 8)
iex> binary = ExDataSketch.CQF.serialize(cqf)
iex> <<"EXSK", _rest::binary>> = binary
iex> byte_size(binary) > 0
true

iex> cqf = ExDataSketch.CQF.new(q: 10, r: 8, hash_strategy: :phash2)
iex> binary = ExDataSketch.CQF.serialize(cqf, format: :v1)
iex> <<"EXSK", 1, 10, _rest::binary>> = binary

size_bytes(cqf)

@spec size_bytes(t()) :: non_neg_integer()

Returns the byte size of the state binary.

Examples

iex> cqf = ExDataSketch.CQF.new()
iex> ExDataSketch.CQF.size_bytes(cqf) > 0
true

update(cqf, item)

@spec update(t(), term()) :: t()

Alias for put!/2, added so ExDataSketch.CQF satisfies the ExDataSketch.Sketch behaviour's generic update/2 callback (which returns a bare sketch, not {:ok, ...} | {:error, ...}).

put/2/put!/2 remain the family-idiomatic names and the ones used throughout this module's own documentation; update/2 exists purely for cross-family generic code (see ExDataSketch.update/2).

Examples

iex> cqf = ExDataSketch.CQF.new() |> ExDataSketch.CQF.update("hello")
iex> ExDataSketch.CQF.member?(cqf, "hello")
true

update_many(cqf, items)

@spec update_many(t(), Enumerable.t()) :: t()

Alias for put_many/2, added so ExDataSketch.CQF satisfies the ExDataSketch.Sketch behaviour's generic update_many/2 callback. Raises ExDataSketch.Errors.FilterFullError if the table fills up partway through -- use put_many/2 directly to keep the partial result instead.

Examples

iex> cqf = ExDataSketch.CQF.new() |> ExDataSketch.CQF.update_many(["a", "b", "c"])
iex> ExDataSketch.CQF.member?(cqf, "a")
true