How bloom filters made SQLite 10x faster

So maybe this is built for every query? Would be needed anyway if there is a where clause for the joined table.

There are advantages and disadvantages to using WAL instead of a rollback journal. Advantages include:

    WAL is significantly faster in most scenarios.
    WAL provides more concurrency as readers do not block writers and a writer does not block readers. Reading and writing can proceed concurrently.
    Disk I/O operations tends to be more sequential using WAL.
    WAL uses many fewer fsync() operations and is thus less vulnerable to problems on systems where the fsync() system call is broken.*

In any event, to address your question, most of the time people truncate to some round number of bytes (8, 16, 32, 64 bits, really) because this is very cheap, but it’s actually barely more expensive to truncate to any smaller than 64 number of bits with masks & shifts. Doing so with a back-to-back array of such truncated b-bit numbers (https://github.com/c-blake/adix/blob/master/adix/sequint.nim) structured as a regular hash table (such as robin hood linear probing (https://github.com/c-blake/adix/blob/master/adix/bltab.nim) where a hit or miss will likely only induce a nearly guaranteed single cache line miss up to ~90..95+% utilization) lets you make a filter with many fewer CPU cache misses (~10X fewer, but everything always depends on where you land in the parameter space) than a Bloom filter at a small 2..4X cost in more space.

There are some example numbers and a “calculus analysis” at the bottom of https://github.com/c-blake/adix/blob/master/tests/bl.nim, but it’s all only a few hundred lines of Nim and you could re-do a test in your favorite ProgLang. This table does eventually "fill up" like Cuckoo or any fixed malloc'd arena at which point people usually double/whatever to make more space resulting in a linear amortized cost growing up from zero. I would just call this a b-bit hash existence filter or maybe b-filter or bit-level filter if you want to get brief.

FWIW, I believe this was even understood by the aboriginal paper by Bloom in his 1970 CACM article (https://cacm.acm.org/research/space-time-trade-offs-in-hash-...) based upon his footnote2, though I think he was referring less to a CPU cache and more to "loading a whole word of memory at a time" like the 36-bit word IBM mainframes of the day, though these are similar mathematically (just think of a 64B cache-line as a 512-bit aligned word). Somehow it got lost in the teaching of Bloom filters.

To speculate on that "somehow", once you have a new dimension (accuracy in space-time-accuracy here), it is easy/natural to only consider "projections", but such oversimplifications can lead one astray. E.g., most people I know optimize for space only to indirectly optimize for time, but most discussion on this topic is about space-accuracy.