A Bloom-Filter Positive Is a Candidate, Not a Retrieved Record

Name the set before interpreting the result

Apache Cassandra 4.1's Bloom-filter documentation describes a read path that combines SSTables on disk with memtables in memory. Its filter helps exclude an SSTable that cannot contain the requested partition. A retained file remains a candidate for lookup.

The storage-engine documentation identifies Filter.db as a Bloom filter of the partition keys in an SSTable. It separately identifies the partition index and the file containing row data. A partition-key screen therefore supplies neither row contents nor evidence that a requested live row reached the consumer.

Ask what the proposal means by a key: a Cassandra partition key, a document identifier or another application-defined identifier. Identify the exact represented set and its dataset revision. The Cassandra documentation supports its named per-SSTable boundary, rather than every product described as using Bloom filters.

References: [BF1][BF3]

Why an unset bit can exclude a key

A classic insertion-only Bloom filter starts with unset bits. Inserting a key sets the positions assigned to it. Probing that key tests the same positions. One unset required bit gives a negative; all required bits set give a positive. Apache's source tagged cassandra-4.1.0 exposes this distinction in add() and isPresent().

The exclusion follows from what insertion would have done. If the key had been inserted, all its required bits would be set. But set bits do not identify which keys supplied them. Several insertions can collectively satisfy another key's probe.

This argument assumes every member of the represented set was inserted, insertion and probing use the same mapping, and the resulting bits remain intact. No deletion, clearing or corruption is included. An incomplete representation cannot establish absence from a larger intended set, and this argument supplies no guarantee for every probabilistic filter design.

References: [BF2]

BF-50: follow three insertions through eight bits

Fictional example BF-50 has eight bits, numbered 0 through 7, initially all zero. Assign exactly two positions to each key: A uses 1 and 3, B uses 3 and 5, and C uses 5 and 7. These are stipulated positions for explanation, not Cassandra hash outputs or a sizing recommendation.

Insert A, B and C. A sets bits 1 and 3. B finds 3 already set and additionally sets 5. C finds 5 already set and additionally sets 7. The final set positions are 1, 3, 5 and 7. Reading positions 0 through 7 gives 0, 1, 0, 1, 0, 1, 0, 1.

Probe A at 1 and 3. Both bits are set, so A tests positive. The example's insertion list confirms that A is a member.

Now assign never-inserted D positions 1 and 7. Both are set too, so D tests positive despite being absent. No inserted key needed to have D's exact pair: A supplied bit 1 and C supplied bit 7. The array combines their contributions without retaining that provenance. This shared-bit collision explains the false positive.

Finally, assign E positions 2 and 5. Bit 5 is set, but bit 2 is zero. E tests negative. Had E been inserted under the assumptions above, bit 2 would have been set. One missing required bit is sufficient to exclude E from this represented set.

The filter has correctly applied its candidate rule in all three probes. D's positive leaves work for lookup; it does not make the screening mechanism useless.

References: [BF2]

Two positive counts can conceal different records

Extend BF-50 into two hypothetical offers. Offer One represents exactly A, B and C. Offer Two represents A, B, C and D, using the same assigned positions. For this comparison, stipulate one retrievable record per present key and a lookup that returns the present requested records without other selection conditions.

Inserting D into Offer Two sets positions 1 and 7, which were already set. Both offers therefore have the identical eight-bit array. Probe the same requested keys A, D and E: both filters report two positives, A and D, and one negative, E.

Actual lookup separates the offers. Offer One returns A only; D was a false-positive candidate. Offer Two returns A and D. Identical filter contents and positive counts coexist with different represented populations and different returned records.

The example changes dataset membership, rather than comparing algorithm performance. For a real comparison, hold the required dataset revision and requested keys fixed. If that required dataset includes D, Offer One's two positives cannot establish that its representation includes D.

A positive also provides no numerical probability that an individual record exists. Interpreting how many positive probes correspond to members needs information about the requested population and filter behavior. These deliberately chosen probes supply no statistical false-positive estimate.

Ask for evidence at the stage your requirement names

Read a supplier's count against its unit. Does it count key-and-file probes, distinct candidate keys, successful key lookups or records actually returned? The same requested key can remain a candidate in more than one SSTable, so a per-file positive count need not equal a distinct-key count. A negative from one file leaves other SSTables and memtables outside that conclusion.

For the same named request and required dataset revision, ask the software provider to distinguish each requested key's screen result, its resolved lookup result and the returned record identity where applicable. For BF-50, the consequential question is explicit: did D merely pass the filter, or did lookup return D's record? An aggregate positive count hides that answer.

Use the evidence to classify the offer. A filter-only explanation can support a candidate-screening claim. Evidence identifying found keys can support the stated lookup result. A delivered-data requirement additionally needs evidence of the records the intended consumer receives. Establishing a partition's presence in a file does not complete that application-level assessment.

The filter's useful purpose is to exclude impossible file matches before further lookup. Its retained candidates explain possible remaining work. Neither the toy's candidate counts nor a claimed false-positive setting establishes physical reads avoided, transferred bytes, elapsed time or AI output quality. Ask for evidence of any such promised result at its own stated boundary.

References: [BF1][BF3]

Connect an identified physical storage-network requirement

If the wider deployment also needs physical connections between storage and compute equipment, Leviathan's Structured Cabling & Fiber Installation service and its project inquiry provide a route to discuss agreed cabling, routing, labels and connection records.

Share a nonconfidential endpoint schedule, approved assemblies, material-supply responsibilities, site constraints and required physical handoff. Database implementation, filter configuration and application-data acceptance remain with the appointed software and storage owners.

References: [L1]