ExDataSketch.FilterChain (ExDataSketch v0.7.1)

Capability-aware composition framework for chaining membership filters.

FilterChain composes membership filter structures into ordered query pipelines. It enables lifecycle-tier patterns such as a hot Cuckoo filter (absorbing writes) followed by a cold XorFilter (compacted snapshot).

Chain Roles

Each filter type has valid chain positions:

Front/Middle/Terminal: Bloom, Cuckoo, Quotient, CQF -- dynamic filters that support member? and put.
Terminal only: XorFilter -- static, no incremental insert. Must be the last query stage.
Adjunct only: IBLT -- reconciliation helper, not in the query path.

Query Semantics

member?/2 evaluates query stages in order with short-circuit semantics: a definite "no" from any stage returns false immediately. Adjuncts are never queried.

Insert Semantics

put/2 forwards to all query stages that support :put, skipping static stages (XorFilter). Returns {:ok, chain} or {:error, :full} if a Cuckoo stage is full.

Delete Semantics

delete/2 checks that ALL query stages support :delete. If any stage lacks delete support (e.g., Bloom), raises UnsupportedOperationError.

Binary Format (FCN1)

FilterChain serializes each stage independently using its own serialize/1, wrapped in a chain manifest with magic bytes "FCN1".

Summary

Types

t()

Functions

add_stage(chain, filter)

Adds a filter stage to the chain.

adjuncts(filter_chain)

Returns the list of adjunct stages.

capabilities()

Returns the set of capabilities supported by FilterChain.

count(filter_chain)

Returns the sum of counts across all query stages.

delete(chain, item)

Deletes an item from all query stages.

deserialize(arg1)

Deserializes an FCN1 binary into a FilterChain.

member?(filter_chain, item)

Tests whether an item may be a member by querying all stages in order.

new()

Creates an empty FilterChain.

put(chain, item)

Inserts an item into all query stages that support :put.

serialize(filter_chain)

Serializes the FilterChain to the FCN1 binary format.

size_bytes(filter_chain)

stages(filter_chain)

Returns the list of query stages.

Types

t()

@type t() :: %ExDataSketch.FilterChain{adjuncts: [struct()], stages: [struct()]}

Functions

add_stage(chain, filter)

@spec add_stage(
  t(),
  struct()
) :: t()

Adds a filter stage to the chain.

The stage is automatically classified based on its module type:

IBLT goes to the adjuncts list (not in query path)
XorFilter is appended as a terminal query stage
All other filters are appended as query stages

Raises InvalidChainCompositionError if the composition is invalid (e.g., adding a query stage after a XorFilter terminal).

Examples

iex> chain = ExDataSketch.FilterChain.new()
iex> chain = ExDataSketch.FilterChain.add_stage(chain, ExDataSketch.Bloom.new(capacity: 100))
iex> length(ExDataSketch.FilterChain.stages(chain))
1

adjuncts(filter_chain)

@spec adjuncts(t()) :: [struct()]

Returns the list of adjunct stages.

Examples

iex> ExDataSketch.FilterChain.adjuncts(ExDataSketch.FilterChain.new())
[]

capabilities()

Returns the set of capabilities supported by FilterChain.

count(filter_chain)

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

Returns the sum of counts across all query stages.

Examples

iex> ExDataSketch.FilterChain.count(ExDataSketch.FilterChain.new())
0

delete(chain, item)

@spec delete(t(), term()) :: {:ok, t()}

Deletes an item from all query stages.

Raises UnsupportedOperationError if any query stage does not support :delete (e.g., Bloom or XorFilter).

Examples

iex> chain = ExDataSketch.FilterChain.new()
iex> cuckoo = ExDataSketch.Cuckoo.new()
iex> {:ok, cuckoo} = ExDataSketch.Cuckoo.put(cuckoo, "hello")
iex> chain = ExDataSketch.FilterChain.add_stage(chain, cuckoo)
iex> {:ok, chain} = ExDataSketch.FilterChain.delete(chain, "hello")
iex> ExDataSketch.FilterChain.member?(chain, "hello")
false

deserialize(arg1)

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

Deserializes an FCN1 binary into a FilterChain.

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

Examples

iex> chain = ExDataSketch.FilterChain.new()
iex> chain = ExDataSketch.FilterChain.add_stage(chain, ExDataSketch.Bloom.new(capacity: 100))
iex> binary = ExDataSketch.FilterChain.serialize(chain)
iex> {:ok, recovered} = ExDataSketch.FilterChain.deserialize(binary)
iex> length(ExDataSketch.FilterChain.stages(recovered))
1

member?(filter_chain, item)

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

Tests whether an item may be a member by querying all stages in order.

Short-circuits on the first false result. Adjuncts are not queried. Returns false if the chain has no query stages.

Examples

iex> chain = ExDataSketch.FilterChain.new()
iex> bloom = ExDataSketch.Bloom.new(capacity: 100) |> ExDataSketch.Bloom.put("hello")
iex> chain = ExDataSketch.FilterChain.add_stage(chain, bloom)
iex> ExDataSketch.FilterChain.member?(chain, "hello")
true

new()

@spec new() :: t()

Creates an empty FilterChain.

Examples

iex> chain = ExDataSketch.FilterChain.new()
iex> ExDataSketch.FilterChain.stages(chain)
[]

put(chain, item)

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

Inserts an item into all query stages that support :put.

Skips static stages (XorFilter). Returns {:ok, chain} on success or {:error, :full} if a Cuckoo stage is full.

Examples

iex> chain = ExDataSketch.FilterChain.new()
iex> chain = ExDataSketch.FilterChain.add_stage(chain, ExDataSketch.Bloom.new(capacity: 100))
iex> {:ok, chain} = ExDataSketch.FilterChain.put(chain, "hello")
iex> ExDataSketch.FilterChain.member?(chain, "hello")
true

serialize(filter_chain)

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

Serializes the FilterChain to the FCN1 binary format.

Each stage is serialized independently using its own serialize/1, then wrapped in a chain manifest.

Examples

iex> chain = ExDataSketch.FilterChain.new()
iex> chain = ExDataSketch.FilterChain.add_stage(chain, ExDataSketch.Bloom.new(capacity: 100))
iex> binary = ExDataSketch.FilterChain.serialize(chain)
iex> <<"FCN1", _rest::binary>> = binary
iex> byte_size(binary) > 0
true

size_bytes(filter_chain)

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

stages(filter_chain)

@spec stages(t()) :: [struct()]

Returns the list of query stages.

Examples

iex> ExDataSketch.FilterChain.stages(ExDataSketch.FilterChain.new())
[]