# FilterChain Tutorial ```elixir Mix.install([ {:ex_data_sketch, "~> 0.10"} ], config: [ ex_data_sketch: [ backend: ExDataSketch.Backend.Rust, integrations: [opentelemetry: false] ] ]) ``` ## Introduction `ExDataSketch.FilterChain` composes multiple membership filters into a single query pipeline -- a cheap, larger first-pass filter to reject most non-members fast, backed by a smaller, more precise second-pass filter for the items that survive the first check. It's not a new sketch algorithm; it's a capability-aware wrapper around the filters covered in the other tutorials here (`Bloom`, `Cuckoo`, `Quotient`, `CQF`, `XorFilter`) plus `IBLT` as a non-queryable "adjunct." `member?/2` short-circuits on the first stage that says "definitely not": ```mermaid flowchart LR A[item] --> B["Stage 1\n(cheap, looser FPR)"] B -->|no| C["definitely\nnot present"] B -->|maybe| D["Stage 2\n(pricier, tighter FPR)"] D -->|no| C D -->|maybe| E["... more stages"] E --> F["every stage said maybe:\nprobably present"] ``` A false positive now requires *every* stage to independently false-positive on the same item -- since each stage's false-positive rate is (roughly) independent, chaining multiplies them together, not adds them. `put/2` fans an insert out to every stage that supports writes (skipping static `XorFilter` stages); `delete/2` requires *every* stage to support deletion or it raises. **Use it for:** squeezing a much lower compound false-positive rate out of filters you'd use anyway, at the cost of a second lookup only for items that survive the first -- most non-members get rejected cheaply by the first stage and never reach the second. Also for attaching an `IBLT` stage alongside a query chain for reconciliation. **Don't use it for:** cases where a single filter already meets your accuracy target -- chaining adds real per-query overhead (another hash, another lookup) for items that pass the first stage, which buys you nothing if the first stage alone was already precise enough. Deletion across a chain that includes any non-deletable stage (`Bloom`, `XorFilter`) isn't possible either -- `delete/2` raises upfront rather than silently skipping that stage. **What it buys you:** chaining a `Bloom` (5% target FPR) with a `Cuckoo` stage measured __~0.14%__ observed false-positive rate against 100,000 novel items -- versus `Bloom` alone's __~4.8%__ on the exact same input, roughly a __34x__ reduction, from filters you'd likely reach for individually anyway: | Approach | Observed FPR (100,000 novel items) | | ------------------------------------ | -------------------------------------- | | `ExDataSketch.Bloom` alone (5% target) | ~4.8% | | `FilterChain` (Bloom + Cuckoo) | ~0.14% | ## Sample data (cached locally) ```elixir {inserted, novel} = ExDataSketch.SampleData.filter_chain_users() IO.puts("#{length(inserted)} inserted, #{length(novel)} novel users") ``` ## Building a chain ```elixir alias ExDataSketch.{Bloom, Cuckoo, FilterChain} chain = FilterChain.new() |> FilterChain.add_stage(Bloom.new(capacity: 500_000, false_positive_rate: 0.05)) |> FilterChain.add_stage(Cuckoo.new(capacity: 500_000)) FilterChain.stages(chain) |> Enum.map(& &1.__struct__) ``` ## Inserting: fans out to every writable stage ```elixir {:ok, chain} = FilterChain.put(chain, "hello") FilterChain.member?(chain, "hello") ``` `put_many/2` for a batch -- it batches through each stage's own `put_many/2` (Rust-accelerated where a stage's backend supports it) instead of looping `put/2` once per item, which matters a lot at this scale: for 500,000 items across two 500,000-capacity stages, item-by-item `put/2` calls would take on the order of a minute, since every family's single-item `put/2` always runs in the Pure backend (no per-item Rust NIF exists for any family) and reconstructs its entire state binary per call. Returns `{:ok, chain}` or `{:error, :full, partial_chain}`: ```elixir {:ok, chain} = FilterChain.put_many(chain, inserted) IO.puts("Both stages now contain the inserted set") ``` `update_many/2` (its `Sketch`-behaviour-compatible name, raising instead of returning `{:error, :full, ...}`) delegates to `put_many/2` and is equally fast. ## Querying: short-circuit AND across stages `member?/2` only reports "yes" if *every* stage agrees -- it stops at the first "no." A false positive requires every stage to independently false-positive on the same item, which is far less likely than any one filter false-positiving alone -- the compounding accuracy gain is the whole point of chaining: ```elixir false_positives = Enum.count(novel, &FilterChain.member?(chain, &1)) observed_fpr = false_positives / length(novel) IO.puts("Chain false positives: #{false_positives} / #{length(novel)} (#{Float.round(observed_fpr * 100, 5)}%)") # Compare against the first stage (Bloom, configured at a loose 5% FPR) alone: bloom_only = Bloom.new(capacity: 500_000, false_positive_rate: 0.05) |> Bloom.put_many(inserted) bloom_fps = Enum.count(Enum.take(novel, 100_000), &Bloom.member?(bloom_only, &1)) IO.puts("Bloom stage alone (5% target): #{Float.round(bloom_fps / 100_000 * 100, 2)}% observed") ``` ## Deletion requires every stage to support it This chain has a `Bloom` stage, and Bloom has no `delete/2` -- calling `FilterChain.delete/2` on it raises: ```elixir try do FilterChain.delete(chain, "hello") rescue e in ExDataSketch.Errors.UnsupportedOperationError -> IO.puts("Raised as expected: #{Exception.message(e)}") end ``` A chain built entirely from delete-capable stages (`Cuckoo`, `Quotient`, `CQF`) supports it: ```elixir alias ExDataSketch.Quotient deletable_chain = FilterChain.new() |> FilterChain.add_stage(Cuckoo.new(capacity: 1000)) |> FilterChain.add_stage(Quotient.new(q: 12, r: 8)) {:ok, deletable_chain} = FilterChain.put(deletable_chain, "temp_item") IO.puts("Before delete: #{FilterChain.member?(deletable_chain, "temp_item")}") deletable_chain = FilterChain.delete(deletable_chain, "temp_item") IO.puts("After delete: #{FilterChain.member?(deletable_chain, "temp_item")}") ``` ## A static terminal stage: XorFilter `XorFilter` can only be the *last* query stage (no incremental `put/2` after construction) -- useful as a precise, space-efficient final check behind a mutable first pass that absorbs new writes. There's a real limitation worth understanding here: `member?/2` requires *every* stage to agree, XorFilter included. `put/2` correctly skips writing to the static XorFilter stage, so a genuinely new item lands in Cuckoo but *not* in XorFilter -- meaning `FilterChain.member?/2` on the whole chain will (correctly) say "no" for it, forever, until the XorFilter stage is rebuilt to include it. Absorbing new writes into Cuckoo doesn't make them queryable through the combined chain; it just means Cuckoo, queried on its own, already has the answer XorFilter doesn't have yet: ```elixir alias ExDataSketch.XorFilter {:ok, xor} = XorFilter.build(Enum.take(inserted, 100_000)) hybrid_chain = FilterChain.new() |> FilterChain.add_stage(Cuckoo.new(capacity: 500_000)) |> FilterChain.add_stage(xor) # put/2 skips the static XorFilter stage automatically -- only the # Cuckoo stage actually receives new writes. {:ok, hybrid_chain} = FilterChain.put(hybrid_chain, "newly_seen_item") [cuckoo_stage, _xor_stage] = FilterChain.stages(hybrid_chain) IO.puts("Present in Cuckoo stage alone: #{Cuckoo.member?(cuckoo_stage, "newly_seen_item")}") IO.puts("Present via the whole chain (Cuckoo AND XorFilter): #{FilterChain.member?(hybrid_chain, "newly_seen_item")}") ``` ## Serialization ```elixir binary = FilterChain.serialize(chain) {:ok, restored} = FilterChain.deserialize(binary) IO.puts("Round-tripped membership check: #{FilterChain.member?(restored, hd(inserted))}") ``` ## See also * `ExDataSketch.FilterChain` module documentation -- full API reference, including `IBLT` adjunct stages for reconciliation alongside a query chain. * `livebooks/sketches/bloom.livemd`, `cuckoo.livemd`, `quotient.livemd`, `cqf.livemd`, `xor_filter.livemd` -- the individual filter families this module composes.