The description of nested loop join is confusing; it's mainly a single pass through the outer table with one B-tree probe per row to each inner table. The link

The description of nested loop join is confusing; it's mainly a single pass through the outer table with one B-tree probe per row to each inner table. The linked paper is clearer: "However, the inner loops in the join are typically accelerated with existing primary key indexes or temporary indexes built on the fly." "Note that SQLite probes the part table index for every tuple in the lineorder table." The Bloom filter does not reduce the cardinality of the join, it simply replaces each B-tree probe and filter with a Bloom probe on a pre-filtered key set. This technique is well-known; the paper cites several examples, and Bloom filter pushdown is common to many commercial systems.