Module 2 · Indexes

Episode 17 Bloom Filters

8 min · SQL · Postgres

Title card of Episode 17: Bloom Filters

▶ This video is coming to YouTube soon.

How can 10 bits per key tell an LSM tree which files to skip? This episode animates a Bloom filter on our customers' cities, catches a false positive in the act, checks the formula (1 - e^(-kn/m))^k against a simulation, and shows 6 false positives being rechecked in a real Postgres bloom index.

Chapters

  1. 0:00Intro
  2. 0:16Skip the files that don't have it
  3. 0:40Insert: k hashes set k bits
  4. 1:22Lookup: any 0 means no, all 1s mean maybe
  5. 2:08The code: add and mightContain
  6. 2:38Bloom filters, precisely
  7. 3:30More hashes help, until the bits fill up
  8. 4:01The formula against the simulation
  9. 4:33In an LSM tree: skip the files that can't have it
  10. 4:54Files read per missing key, measured
  11. 5:16Proof: false positives in Postgres's bloom index
  12. 6:29Where Bloom filters live
  13. 6:58Recap
  14. 7:29Next: Lab: The Index That Wasn't Used